カーブやジオメトリへノイズを適用すると、カーブのもつれ、ジオメトリの裏返りに悩まされることがあります。
この記事はそれらを予防する方法ではなく、発生してしまった自己交差部分を除去するためのアプローチを検討したものです。
サンプルのシーンファイルは こちら からダウンロードできます。
記事内ではアプローチの説明に終始し、実装都合の説明はサンプルシーン内へ記載する形を採っております。
カーブの自己交差を除去
前提条件
元のカーブは枝別れしておらず、変形によって交差ができてしまった、という前提で話をすすめていきます。
肝となるSOP
Find Shortest Path SOP を使用します。このノードは、指定した二点間の最短経路を見つけ出します。
アプローチ
交差点の作成
交差する線分は、見た目では交差していてもジオメトリの構造上は繋がっていません。そのままでは Find Shortest Path が走査する際に交差点を考慮できないため、交差点を作る必要があります。
そのためには Intersect Stitch SOP を使用します。このノードはジオメトリの交差部分へ point を作成して縫合します。ただし、デフォルトでは検出精度が低いため、より精度を高めるために Proximity Tolerance 値を小さくします（処理は重くなります）。
下図の赤矢印は、Intersect Stitch 実行前後での、Find Shortest Path によって抽出されるパスのイメージです。
最短経路の抽出
Find Shortest Path は経路探索の始点と終点 の point をグループとして指定することで機能するため、どの point へ start, end のグループを割り当てるかを考える必要があります。
カーブが開いている場合
この場合は非常にシンプルで、開いている場所（隣接pointの数が1の部分）を start, end にします。
カーブが閉じている場合
Find Shortest Path 実行後は、検出された道のり以外は残りません。そこで次のような手順を踏みます。
- 閉じたカーブの一部を取り除き、開いている状態にする
- 開いたカーブへ start, end を割り振り、Find Shortest Path を実行
- 取り除いていた部分を元にもどす
その際、取り除く場所はどこでもよいという訳ではありません。場所によっては下図のように望まない結果になり得ます。
完璧な解決策ではありませんが、交差点から交差点の道のりが最も長い一本道の、中ほどを取り除くと良さそうです。（交差点と交差点の道のりを測る方法は後述します。）
上の図は、交差点同士をつなぐ道のり毎に色分けし、それぞれの長さを表示したものです。この場合、最も長い道のりは右側の黄緑色の道で、その中ほどを取り除くことにします。
取り除かなかった部分へ Find Shortest Path を適用するため、取り除く部分は最小限にしたほうが良いでしょう。
この状態へ Find Shortest Path を適用し、その後に取り除いた部分を元に戻せば完了です。
交差点から交差点への道のりを調べる
交差点間の道のりを調べるには Measure SOP を使用します。
ただし Measure は各 primitive に対して処理を行うため、交差点から交差点までの道のりが一つの primitive である必要があります。
下図は交差点を含む道の各 primitive を色分けした例ですが、交差点毎に primitive が分かれていない状態です。(primitive 番号 0 が交差点をまたいでいます）
そこで Poly Path SOP を使用します。Poly Path はまさにこのためのノードで、交差点間を一つの primitive にします。
こうすることで、交差点間の距離を Measure で取得することができるようになります。
別アプローチによる自己交差除去
次に説明するアプローチは、最短経路以外の道のりを結果として得られることがあります。このアプローチでは Find Shortest Path を使用しません。
サンプルシーンでの実装は詰めが甘く、汎用的に使用できるものではありません。アプローチの参考程度としてご覧ください。
自己交差の除去
図の自己交差について、道の流れが矢印のようであるとします。なお、このカーブへは既に Intersect Stitch を適用して交差点の縫合を行っています。
以下のようにして自己交差を取り除きます。
- スタート地点から最初の交差点まで進む
- 交差点をそのまま進み、再び最初の交差点に到達するまで進む
- 2で通った道のりを削除する
- 1へ戻る
こうすることで、最終的に自己交差を取り除くことができます。
次項は、それを行うために留意することです。
交差点到達後の進行方向
交差点のほとんどは、２本のまっすぐな道が交差することで出来ているように見えます。
ですが下図のような道が Intersect Stitch によって接続された結果である場合もあります。
今回のアプローチで交差点侵入後に進む道は、Intersect Stitch を適用する前の道順と同じである必要があります。そうでないと辿った道のりを戻ることになりかねません。
Intersect Stitch 前の道順を利用する
下図の左は Intersect Stitch を適用する前（交差点作成前）の道のりで、primitive番号 （ピンクの数字）は道のり順に並んでいます。この ID をアトリビュートとして記憶させます（黄色の数字）。
図の右では、Intersect Stitch により primitive が再構築されたため primitive番号 は道のり順ではなくなっています。ですが記憶した数字（黄色の数字）の並びは壊れていません。
これを利用して、交差点侵入前の道が記憶していた数字を、交差点に接している他の道から探します。そうすれば、交差点到達後に進む道を間違えずにすみます。
このアプローチであれば、下図のように同じ番号が交差点で見つからないケースでも対応できます。同じ番号の道が見つからない場合、自分が持つ番号の前後を探せば問題ありません。
primitive番号の整理
前項の内容は、Intersect Stitch 前の primitive 番号が道のり順になっている前提で成立しています。もし最初の時点で primitive 番号がバラバラになっている場合、Poly Path SOP と Convert Line SOP を使用することで、道のりの順に primitive 番号を並び替えることができます。
- Poly Path SOP
- カーブの分岐と分岐の間を、一つの primitive にします
- Convert Line SOP
- point と point の間を一つひとつの primitive にします。その際、元カーブの道のり順に primitive 番号が割り振られます
この Poly Path と Convert Line は、カーブのクリーンアップを行うためにセットで使用されることがよくあります。
アプローチの違いによる比較
多くの場合は結果的に同じ出力になりますが、下図のような違いを得られることもあります。
下図の左が処理前のカーブ、右上がFind Shortest Path によるアプローチ、右下が別アプローチによるものです。
ジオメトリの裏返った部分を除去
前提条件
ボーダーエッジのない、閉じた形状のジオメトリであるという前提で話を進めます。
肝となるSOP
意外にも？Boolean SOP 単体で裏返り部分を除去できます。
自己交差を取り除くという本来の目的はこれで解決しますが、この図でも確認できるように細かな破片が残ったり、他にも極端に尖ったエッジが残ったりします。下記はそれらを掃除するアプローチです。
トポロジが大きく変わっても構わない場合のアプローチ
シルエットがある程度維持できれば良い場合のアプローチです。
細かなディティールは失われますが、この次に紹介するアプローチに比べて不具合がなく、高速に処理できます。
ボリュームの利用
VDB from Polygons SOP によるボリュームへの変換と、Convert SOP または Convert VDB SOP によるポリゴンへの変換により、尖りすぎた形状を除去できます。
ただし、面の表裏が考慮されない結果になるため、自己交差を除去するには先に Boolean を適用しておく必要があります。
なお、VDB from Polygon と Convert VDB の組み合わせは、Remesh to Grid SOP でも代用できます。
細かな破片の除去
複雑な形状の場合、Boolean や ボリュームの適用後にさまざまな大きさの破片が残ります。最も大きな破片を残すために、破片毎の表面積を取得し、最大の表面積ではない破片を除去します。
そのためには、以下の各 SOP を使用します。
- Connectivity SOP
- 繋がっているジオメトリ毎に、番号を割り振ります。同じ破片の primitive は、同じ番号を持ちます。
- Measure SOP
- 番号が同じ primitive の合計面積を取得します。つまり、破片毎の合計面積を取得します。
- Attribute Promote SOP
- 各破片の合計面積のうち、最大値を記憶します。
- Attribute Wrangle SOP
- 破片の面積が最大面積でないものを削除するために使用します。
結果
このアプローチを採った場合の結果は図の通りです。
トポロジを出来るだけ維持したい場合のアプローチ
鋭利な部位の除去
全体的に Boolean を適用した部分は、鋭利な形状が残りがちです。
また、極端に細くなった部位によって、塊同士が繋がってしまう場合があります。
これらを除去するために以下を行います
- Boolean を適用した部分に接する場所を把握（Boolean と関係ない元々の形状を処理しないようにするため）
- その中で、鋭利な形状や厚みが少なすぎるとみなせる部分を把握
- 2で把握した部分を除去
- 除去によって開いた穴を閉じる
1, Boolean を適用した部分に接する場所を把握
Boolean SOP の A-B Seams パラメータにより、裏返りを除去した部分へ Group を残すことができます。
2, 鋭利な部分、厚みの少なすぎる部分を把握
この判定には、Measure Thickness SOP を使用します。このノードは、point から計測したジオメトリの厚さ情報を取得します。
前項で把握した裏返り除去部分にあたる point が、小さすぎる thickness 値を持っている場合、その部分を除去の対象とします。
3, 4, 鋭利な部分、厚みの少なすぎる部分を修正
除去の対象となる point だけでなく、その隣接した primitive ごと除去し、 Poly Fill SOP で穴埋めします。つまり面を張りなおします。
問題点として、この段階で不正なジオメトリが発生していると Poly Fill が上手く機能しません。その前に Poly Doctor SOP で不正部分を修正する必要があります。
極端に尖った point をならす
ここまでの処理でも取り切れない、極端に尖った point が残ることはあります。
これを近隣の point となじませるため、次のようにします。
- 各 point の場所から、接している primitive の重心へ向かうベクトルを集める
- それらの平均ベクトルと各ベクトルの角度を、内積を使用して調べる
- どの角度も小さい場合、とても尖っている point だとみなす
- その point の位置について、Attribute Blur SOP で周辺となじませる
For-Loop With Feedback による繰り返し処理
上記の処理を一通り行っても、primitive の削除や再生成、point 位置の調整を行ったことによる新たな自己交差が発生する可能性はあります。
それでも、これまでの一連の処理を繰り返すことで少しずつ自己交差は減り、そのうちに自己交差のないジオメトリになります。
結果
このアプローチを採った場合の結果は図の通りです。
Boolean が使えない場合の裏返り除去
あまりに複雑なジオメトリでは Boolean が失敗したり、ポリゴン数が多すぎて処理に時間のかかりすぎることがあります。その場合のために別のアプローチを紹介します。
このアプローチではトポロジは維持されず、シルエットも他のアプローチと比べて滑らかになってしまいますが、安定して結果を得ることができます。
肝となるSOP
Point Cloud Surface SOP を使用します。この SOP は主にフォトグラメトリで使用されるもので、法線を持つ点群をもとにポリゴンを作成します。
また、Point Cloud Surface は裏返っていると判断されるような部分を生成対象から除外します。
アプローチ
非常にシンプルで、以下のように行います。
- Scatter SOP で、ジオメトリから沢山の点を生成
- Attribute Wrangle SOP で、点群へ直近のジオメトリが持つ法線を転写
- Point Cloud Surface SOP でメッシュを生成
結果
このアプローチを採った場合の結果は図の通りです。
アプローチの違いによる比較
左上が処理前のジオメトリ、右上がボリュームを使用したアプローチ、左下がトポロジの維持を重視したアプローチ、右下が Point Cloud Surface SOP を使用したアプローチです。
このうち、不正ジオメトリによるエラーが最も少ないのは Point Cloud Surface を使用したものになります。
最後に
Houdiniは検証をし易く、試行錯誤する際のイテレーションを早く回せるのが強みだと思います。
また、意外なノードが意外な用途に役立つことも多いため、色々なアプローチを模索してみることが新たな思い付きと発見につながります。
事実、この記事の最終確認をしている段階で、Point Cloud Surface SOP の挙動について「まさか......」と思いついたことがありました。試してみると予想通りで、土壇場で記事の修正を行いました。
それを思いつく前のアプローチも 次の記事 へ残しております。そのアプローチは遠回りで、かつ仕上がりも悪いものですが、何らかのヒントにでもなればと思います。
（サンプルシーン内でも、approach_mesh OBJ 内の右端へ omitted_approach ノードとしてひっそりと置いています。）
それでは、良い年末を。