java - 查找 3D 对象外部的三角形

Question

我正在尝试获取一组顶点(vi = xi,yi,zi)并用它们制作一个实体对象。为了绘制物体，我使用三角形，所以我需要找到一组三角形 t = v1, v2, v3，它们形成一个实体表面。

我知道，如果我从顶点构建每个可能的三角形，我将看到一个实体表面，但这会在隐藏在对象内部的三角形上浪费大量资源，并且计算它们的成本为 O(N ^3) 其中 N 是顶点数。如何仅找到外部的三角形？

这是我的代码(java)，用于生成具有随机顶点的对象中的所有三角形。

public class myObject {

    public ArrayList<float[]> Vertex_Coords;
    ArrayList<float[]> Vertex_Colors;
    ArrayList<int[]> triangles;


    public myObject() {

        Vertex_Colors = new ArrayList<float[]>();
        Vertex_Coords = new ArrayList<float[]>();
        triangles = new ArrayList<int[]>();

        addball(20);
    }

    public void addvertex() {
        float[] coords = new float[3];
        float[] colors = new float[4];
        int i;

        for (i = 0; i < 3; i++)
            coords[i] = maxModelSize * ((float) Math.random()-0.5f);

        for (i = 0; i < 4; i++)
            colors[i] =  (float) Math.random();

        Vertex_Coords.add(coords);
        Vertex_Colors.add(colors);
    }

    public void addball(int numpoints)
    {
        int i;
        for(i = 0;i<numpoints;i++)
        {
            addvertex(false,true);
        }
        connectalltriangles();
    }

    public void connectalltriangles()
    {
        int i,j,k;
        int [] tri;
        for(i=0;i<Vertex_Coords.size();i++)
        for(j=i+1;j<Vertex_Coords.size();j++)
            for(k=j+1;k<Vertex_Coords.size();k++)
        {
            tri = new int[3];
            tri[0]=i;
            tri[1]=j;
            tri[2]=k;
            triangles.add(tri);
        }
    }

}

Answer 1

如果您确定您的几何形状是否始终是凸的，那么您真正需要的是凸包算法。

凸包:此算法通过仅连接 3d 空间中给定点集的最外层顶点来创建网格。显然，您将失去凸结构内部的顶点，并且不会在任何三角形中使用。这仅适用于凸形状。

下面是凸包结构的一个很好的例子。

有许多库实现凸包算法。例如:CGAL、BulletPhysics 和 OpenMesh。如果您正在寻找一种快速构建凸包的方法，QuickHull 是最好的地方。 http://www.qhull.org