見つける顔

Question

説明：

私はメッシュとそのすべての頂点顔情報（頂点インデックス、頂点位置、顔インデックスなど）を持っていると私はこれのサブパーツをレンダリングしたいですメッシュ。たとえば、私が手メッシュを持っている場合、私は指のうちの1つだけをレンダリングしたい。

私は、私がレンダリングしたい指の頂点インデックス、頂点位置などを知っていることを意味する各サブパーツの関連頂点の情報を持っています。しかし、私はどの顔が指に関連しているのかわかりません。だから、私は、サブパーツをレンダリングするために、関連する顔のインデックスを見つける必要があります。

質問：

私が設定し顔全体指数でサブ部品の関連する指標を見つけることができますどのように？私は徹底的な検索アルゴリズムを使用することができますが、私はより良いアプローチ、それを行うための既知のアルゴリズムがあることを願っています。三角形、正方形メッシュの

class Vertex 
{ 
    Vertex(float _x, float _y, float _z) 
    { 
     x = _x; y = _y; z = _z; 
    } 
    float x, y, z; // Positions 
}; 

class Face 
{ 
    Face(int _v1, int _v2, int _v3) 
    { 
     vertIndex1 = _v1; vertIndex2 = _v2; vertIndex3 = _v3; 
    } 
    int vertIndex1, vertIndex2, vertIndex3; // Vertex indices 
}; 

使用例：

詳しく

一部ベクターようstd::vector<Vertex> vertsとstd::vector<Face> facesとして。私はVertex v1（0,0,0）、v2（1,0,0）、v3（0,1,0）、およびv4（1,1,0）を持っています。したがって、対応するFaceオブジェクトはf1（0,1,2）およびf2（0,3,4）です。ここで0,1,2および4はVertexオブジェクトのインデックスで、vertsベクトルです。ご覧のように、頂点は異なるFaceにある可能性があります。

ここで、verts.size()が6000、faces.size()が12000であるハンドメッシュがあるとしましょう。ただし、ハンドメッシュ全体ではなく、ピンクの指だけをレンダリングしたいのですが、ピンクの指の頂点インデックス（345,369,541、...）として計算される。

私は使用する必要がある頂点を知っています。私は顔情報全体を知っています。これらの与えられた頂点についてのみ顔のインデックスを探したいと思います。

Answer 1

コメントに記載されている単純なO（m + n）時間、O（n） - 空間アルゴリズムが遅すぎる場合は、さまざまなことができますが、 （a）幅がまたは、高さがまたはの場合は、すべてのサブパーツの頂点を含むバウンディングボックスの奥行きが「小」であり、（b）ほとんどの面が「広すぎ」でない場合は、

各次元（x、y、z）の2つの面のリストを事前計算します。1つは、その次元の最小頂点座標を増やしてソートし、もう1つはその方向に最大頂点座標を増やしてソートします。与えられた部分部分頂点のリストから、3つの次元（したがって6つの数字、mx、my、mz、Mx、My、Mz）のそれぞれの最小値と最大値の位置を見つけます。 Mxの最小頂点x座標でソートされた面のリスト内のバイナリ検索、そしてMxの場合はリストiとj内の位置をそれぞれ与える。定義されている他のすべての面は、範囲mx .. xx外のx座標を有する少なくとも1つの頂点を有するので、実際には範囲i ... j内の面をテストするだけでよい。（最小x座標が< mx、範囲外の頂点が少なくとも1つあり、その最小x頂点が> Mxの場合、3つの頂点のすべてが範囲外です）。 j-iを記憶し、他の5つのソートされたリストについても同様にして、j-iの値が最も小さいものを追跡する。最後に、可能な限り小さなリストにあるすべての顔を「難しい方法」でテストします。