VB.netでSTLファイルの分離

STLファイルをVB.netで読み込んで連結したポリゴン毎にグルーピングを行って
最終的に別々のSTLファイルとして出力したいです。

添付画像の例ですと、３つの塊がありますので３つにグルーピングを行いたいです。

STLファイルのフォーマットは以下のように
ポリゴンの面法線ベクトル３値と三角形の３頂点のxyz値が並んで
７行で１ポリゴンとなっています。
---------------------------------------------------------------------------
solid STL generated by MeshLab
facet normal -2.184899e-01 -4.266318e-01 -8.776374e-01
outer loop
vertex 1.992444e+02 -3.197685e+02 4.095370e+02
vertex 1.992444e+02 -3.231958e+02 4.112031e+02
vertex 1.970056e+02 -3.228066e+02 4.115713e+02
endloop
endfacet
facet normal -2.179973e-01 -9.024491e-01 -3.715682e-01
outer loop
vertex 1.992444e+02 -3.245304e+02 4.144445e+02
vertex 1.970056e+02 -3.228066e+02 4.115713e+02
vertex 1.992444e+02 -3.231958e+02 4.112031e+02
endloop
endfacet
facet normal -9.165897e-01 -1.748030e-01 -3.595934e-01
outer loop
vertex 1.952990e+02 -3.197685e+02 4.144445e+02
vertex 1.966203e+02 -3.197685e+02 4.110767e+02
vertex 1.970056e+02 -3.228066e+02 4.115713e+02
endloop
endfacet
facet normal -4.957781e-01 -2.004494e-01 -8.449995e-01
outer loop
vertex 1.992444e+02 -3.197685e+02 4.095370e+02
vertex 1.970056e+02 -3.228066e+02 4.115713e+02
vertex 1.966203e+02 -3.197685e+02 4.110767e+02
endloop
endfacet
facet normal -4.487110e-01 -8.761682e-01 -1.760334e-01
outer loop
vertex 1.992444e+02 -3.245304e+02 4.144445e+02
vertex 1.966968e+02 -3.232257e+02 4.144445e+02
vertex 1.970056e+02 -3.228066e+02 4.115713e+02
endloop
endfacet
facet normal -9.162475e-01 -3.704427e-01 -1.525211e-01
outer loop
vertex 1.952990e+02 -3.197685e+02 4.144445e+02
vertex 1.970056e+02 -3.228066e+02 4.115713e+02
vertex 1.966968e+02 -3.232257e+02 4.144445e+02
endloop
endfacet
endsolid vcg
---------------------------------------------------------------------------

上記のポリゴン順は塊ごとに連続しているわけではなく
ランダム順に記述されていると考えてください。

STLファイルを読み込んだり、座標値をdouble型の配列に格納する等の
処理はできているのですが、肝心のグルーピングするアルゴリズムが
で悩んでおります。

最初に頂点座標値の一致を見る総当りアルゴリズムで作成したのですが
処理が遅すぎて実用に耐えません。

この手の処理を高速に行えるアルゴリズムをご教授願えればと思います。
宜しくお願い致します。

No.1 ベストアンサー 回答者： fujillin 回答日時： 2017/09/08 09:50

こんにちは

長文失礼。　まったくの門外漢です。
それなので、ご質問のような処理をする際に、実際に通常用いられているであろう方法は知りません。
素人の浅知恵レベルの思いつきですが、回答が無いようなので、何かの参考にでもなればと・・・

想像するところ、実際には最初に大雑把なクラスタリングを行っておいて、検索する対象を減らすような工夫が行われているのではないかと思いますが、そのような知識もありませんので、ひとまず、総当たりに近いけれども少しは速くなるのでは（？）という考えです。


基本的な方法はご質問文と同様で、連続しているポリゴン（座標値が一致）するものは同じグループと判断して順次探索して行くというものです。
実際の座標値は完全一致なのか計算誤差を含んで一致なのかわかりませんが、以下の説明上は単に「一致」として記すことにします。

1）元データとなっているポリゴン（3座標+法線ベクトル）の配列を「ポリゴン配列」と言うことにします。
2）各ポリゴンがどのグループに属するかを示す、ポリゴン配列と同じ要素数の配列を用意し、「所属配列」とします。（初期値はどこにも所属していないので0とかnullなど）
3）別に、ポリゴン配列の3つの座標を分解してバラバラの座標値群のリストを用意します。
どのポリゴンの座標値かがわかるように、この座標値にはポリゴン配列を参照できるインデックス付加します。
4）3）の座標値リストをＸ座標（他の軸でも可）でソーティングしておきます。

ここまでが準備計算です。
ソーティングしておくことで、総当たりよりも効率よく探索が可能になるのが狙いです。
また、あるグループに属した座標をリストから取除いてゆくことで、対象のリストを小さくする（すでにやっていらっしゃるかも知れませんが）ことができ、効率が上がるものと考えます。

グループ化は概ね以下のような手順で。
1）事前にグループがいくつ存在するかは不明なので、新しくグループを探索する毎に、グループに属するポリゴンのインデックスを収納するための配列を用意します。
2）座標リストの最初の要素のインデックスをグループに入れます。
　同時に、そのインデックスの所蔵配列にグループ（番号など）を記し、その座標値はリストから削除します。
3）以下をグループの要素が終わるまで繰り返します。
（最初はグループの要素数は1ですが、追加されます）
4）対象要素の3つの座標値についてリストを探索し同じ座標値を探します。
（ソーティングしてあるので、2分法などで対象を特定し、同じ値が連続しているところだけをチェックすれば良いことになります。）
5）XYZ座標全て一致する場合、インデックスから所蔵配列を調べ、未所属ならそのインデックスをグループに加え、所属配列に所属を記載。
一致する座標値のデータは、リストから削除します。（既登録でも今回登録でも）
XYZ座標値が一致しないものについては何もしません。
6）ポリゴンの3点の座標値の照合が終わったら、グループに追加されている次のポリゴンがあれば、その3点に対して同様の処理を行います。
グループ内に次のポリゴンが存在しなければ、そのグループの探索は終了です。
7）座標値のリストがまだ残っている場合は、その最初のインデックスを新しいグループとして、2）～の処理を繰り返します。
8）座標値リストの要素がなくなれば、全体の処理が終了です。


・・・と、ここまで書いたところで気がついてしまいました！
上記の方法だと、一つの頂点に対して、隣接するポリゴンの数だけ同じ座標についての探索を無駄に繰り返してしまいますね。
これを省かないと、効率化とは言えなさそうです。（汗）

付け焼刃的な修正案ですが、元のポリゴンの各座標値に探索済みのマーキング欄を追加しておいて（元データを変えたくない時は、所属配列に欄を追加するのが良いかも）、探索でヒットした際に、グループに登録すると同時に該当する座標値にマークしておき、次の探索時にはマーク済の頂点をスキップすることで、同じ頂点での探索を繰り返さずに済むと思います。
（ヒットした際の1座標しかマークしないので、完全に重複を省くことはできませんが、それでもそれなりの効果は期待できると思います）


結果的に、座標値をほぼダブルで持つことになるので、一時的にメモリが必要にはなりそうですが、多少なりとも効率化が計れるのではないでしょうか？
数が多い場合に、探索を高速化するため、第二、第三キーとしてY,Zについてもソーティングしておくとかが有効かも知れません。
あるいは、Ｘ座標の範囲をを事前に何分割かしておいて、探索の対象を小さくすることなどでも効率が上がる可能性があるかもしれません。


※ よくわかっていない者の文章なので、わかりにくく、また、不足な部分もあると思いますが、何かのヒントにでもなれば幸いです。

この回答へのお礼

ご回答ありがとうございます。

大変参考になり、以下のような処理にさせて頂きました。

XYZ値とポリゴン番号を持ったpoint構造体を定義し
Dim ps As IOrderedEnumerable(Of point) = pt.OrderBy(Function(s) s.x).ThenBy(Function(s) s.y).ThenBy(Function(s) s.z)
でソートを行いました。
ソート後は同一座標が連続する間のポリゴン番号をグループ化し、すでに見つかっている
グループが内包するポリゴン番号と一致するものがあればグループを連結しながら
進むループを作成

おかげさまでループ処理を大幅に減らす事ができ満足しております。
ありがとうございました。

お礼日時：2017/09/11 10:49