3Dオブジェクトの外形に三角形を見つける

Question

私は、頂点のセット（vi = xi、yi、zi）を取り出し、それらからソリッドオブジェクトを作成しようとしています。オブジェクトを描画するには、三角形を使用するので、三角形のセットt = v1、v2、v3を見つける必要があります。これはソリッドなサーフェスを形成します。

私は、頂点からすべての可能な三角形を構築すると、頑丈な面が見えますが、これはオブジェクトの内部に隠れている三角形に多くのリソースを浪費し、 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

あなたのジオメトリが常に凸であれば確実であるならばどのようなあなたが正確に必要なのは、凸包アルゴリズムです。

凸包：このアルゴリズムは、3次元空間内の与えられた点集合の最も外側の頂点のみを接続することによってメッシュを作成します。明らかに、凸構造の内部にある頂点を緩め、いずれの三角形にも使用しません。これは、凸形状の場合にのみ機能します。

以下は凸包構造の良い例です。

凸籾摺りアルゴリズムを実装する多くのライブラリがあります。例：CGAL、Bullet Physics、OpenMesh。凸包を簡単に作成する方法を探しているなら、QuickHullが最適です。 http://www.qhull.org