Skip to main content

より良い凸面分解を求めて

9月

17, 2020

by Khanovich


テック

Robloxは2014年に空間領域構成法(Constructive Solid Geometry) を公開し、このプロジェクトの物理シミュレーションをサポートすることは、ティム・ロデューハ(Tim Loduha)と一緒のシミュレーションチームでの私の最初の大規模なプロジェクトでした。 その頃は会社がもっと小さく、物理チームには他の開発と関係のない仕事も兼任していた2人しか人員がいませんでした。 そして、結果を早く出すという精神から、非常に人気のあるBullet Physicsというライブラリの助けを求めました。 Bullet Physicsは現在、そのアクセスしやすさと機能の豊富さ、そしてオープンソースであるということ、そして拡張性のために数多くのゲームで使用されていることから、 Robloxのニーズに合う自然な選択となりました。

Robloxの物理エンジンは、社内で作成されましたが、PartOperationsをシミュレーションで機能させるために2つの主要な構成要素をBullet Physicsから採用しました。

    1. 複雑な幾何学衝突の検知
    2. 任意の3D幾何学(解決スペースと性能の制約のために業界の基準になっている)の衝突検知のために凸面オブジェクトの集まりを生成する凸面分解

私たちが当初、プロジェクトの凸面分解の部分の作業をしていたとき、BulletPhysicsについてきた2件のアルゴリズムで実験しました。

  • 階層的近似凸面分解 (HACD)
  • 近似凸面分解 (ACD)

HACDの結果は気に入ったのですが、私たちにとって最初の製品出荷ではACDの頑強さと一貫性のほうを取りました。

精密なフィードバック

この機能を出荷した後、衝突検知でより良い幾何学結果を期待していたというユーザーからのフィードバックが山のように届きました。 ACDの粗いボクセル化の使用は、廊下や棚から重要な表面がずれたり覆われたりするなど様々なものを生み出す原因となりました。

これらの凹面がどのように封じられているかをイメージするには、ボクセライザー(下)の目で複雑な形がどのように見えるかをイメージすればできます。

元の幾何学を尊重した何かで、よりよいものが必要でした。 表面がボクセルグリッドにどれだけ「装着」しがちかによって、ボクセル化は関係しなくなりました。 必要としていたのは、入力幾何学の大多数で手動の修正をまったくなしに自動的に機能する何かでした。

階層的近似凸面分解

最終的には、以下の品質のためにHACDに戻ってきました。

  • 最初のアルゴリズムの状態として入力メッシュが利用されました。
  • 元の入力幾何学に基づいたエラーチェック済み
  • 非多様体を処理済み(ACDも)
  • ボクセル(体積要素)化なし

上記でリンクされた紙に基づくと、HACDには3つの主要な構成要素があります。

  • 双対グラフの除去
  • 凸包(とつほう)生成
  • 凹面(おうめん)エラー計算

アルゴリズム概要

1. 入力メッシュが取得され、それぞれの三角形がノードで、2つの三角形の間のそれぞれのエッジがグラフ上のエッジであるときにグラフ化されます。 これは、それぞれの三角形が最初の凸包として処理される 双対グラフの始まりです。

2. グラフ上のすべてのエッジを見ていって、エッジが結合するノードの凸包を組み合わせることによって得られる結果である予測凸包を計算します。

3. この予測凸包を使って、元の幾何学が招く凹面エラーを計算します。 これらのエラーは、グラフ上のすべてのエッジを最も間違いが少ないものから最も多い順に並べ替えるのに使われます。

4. 最後に、最小のエラーと一緒にエッジを取ります。

a. もし、エラーが環境設定で許可される最大以下の凹面エラーの場合、エッジ (edge-collapse)を削除し、2つのノードをエッジの予測凸包で置き換えます。

b. もし、エラーが環境設定で許容される最大値以上の凹面エラーの場合、終結させます。

5. edge-collapseによってエッジが削除されるたびにこれは隣接するエッジの前の凹面エラー結果を無効化するため、 隣接するエッジのためにステップ#2と#3を繰り返します。

6. 新しい凹面エラーに基づいた並べ替え済みのエッジリストにある再計算済みのエッジをアップデートしています。

7. 残っているエッジがグローバル許容エラーよりも高いエラー値があるものだけになるまで、ステップ4から6までを繰り返します(これは、アルゴリズムを開始する前にユーザーによって環境設定されます)。

オープンソースHACDコードで入手可能な最新のものを手に入れて、いくつかのメッシュでテストしました。 車のような形のうちのいくつかは、今までのものよりもさらに改善された衝突幾何学という結果を生みましたが、その他の入力メッシュは疑わしい出力という結果をもたらしました。 アルゴリズムが理論上は大丈夫に見えたので、次の段階は何かこのようなおかしな結果を生んでいる原因か突き止めることでした。

ビジュアルデバッグ

導入の内部業務をよく知らなかったため、調査をスピードアップするためにできるただ一つのことをしました。 双対グラフエッジ削除プロセスのすべてのステップを記録するビジュアルデバッガーを書き、すべての変更を元の幾何学に一歩ずつステップスルーで実行することができるようにしました。

このツールで以下の両方に問題があることを確認することができました。 凹面エラー計算凸包生成 ステップスルーし、正しく形成された凸包が重要で大きな凹面をブロックしたケースを発見することができましたが、それでもまだ 凹面エラー計算は、まったくエラーがないとしてこの閉包を形成したエッジ崩壊を報告します。 凸包生成のほうでは、エッジ崩壊は頂点と表面全体がなくなる原因となることがあることを発見しました。 これは、小規模の表面がなくなっていたり、完全な破壊という結果をもたらすこともあります。

そのため、より深く調べてそれぞれの構成要素に対して独自の論理をもって書く必要性を認識していました。

凹面エラー計算(アルゴリズム概要のステップ3から)

凹面エラー計算の目的は、閉包とエッジの結合部分を組み合わせることによってできる新しい凸包生成によってエッジの削除が元の幾何学に引き起こす「ダメージ」の量を数値化することです。 元の書類では、このエラーは数多くの方法で追跡できると言及されており、導入は元の表面から新しく形成された予測凸包の中で新しく形成された表面から一番遠い距離を使っています。 同じ定義を使います。

この量を獲得するには、2つの情報が必要です。

  • ソース形状の数値化可能な表現
  • このエッジの削除から形成される予測凸包(概要のステップ2)。

元のHACD導入には元の表面(概要のステップ1の間)の表現として、三角形1つにつきいくつかのサンプルポイントを使いました。 これらのポイントは、凹面を妨げている凸包の背面を見つけるために、フェース法線と一緒にレイキャストから使われます。 元の表面から背面までの最大距離はエラーだとされました。 これは、妥当なアプローチですが抽出密度が各三角形ごとの操作であるため、凹面をブロックしているかもしれないオブジェクトをスキャンするのに大きな三角形の面を持った簡単な形に巨大な死角ができてしまうという問題に遭遇しました。

理想的なシステムは、本質的に元の表面の三角形からテストされている凸包の上に表面の押出成形をしようとしますが、これは解決して最適化するにはとても高価な問題なので、かわりにもっと一貫性のある配分で元の三角形をサンプリングしようとします。

環境設定されたグリッド距離(左を参照)に基づいて、それぞれの三角形に均一に表面サンプルポイントを生成します。 これは、多量のポイントを生成するため、凹面エラー計算の過程中、どのポイントが新しく生成された凸包生成と比べてチェックする必要があるかを素早くフィルタする方法が必要でした。 これを達成するのに、衝突検知で使われるものに似た空間グリッドにすべてのサンプルポイントを投げ入れ、テスト中の凸包の境界ボックスを使って、テストする対象の表面サンプルポイント群を素早く選択します。

いったん境界ボックスの内側にあると思われるポイントを掴んだら、現在の凸包によって封じられた凹面をキャッチしようとするため、新しく形成された凸包の内側のポイントをさらにフィルタします。 それらのサンプルポイントを閉包の三角形からレイキャストします。 もし、追加されたエラーがない場合、すべてはゼロの距離を返しますが、上の図解のような問題のある凸包は元の表面からのレイキャストが予測凸包の三角形の一つの背面に影響します。

要約すると、エラー生成は以下のように説明できます。

  • (アルゴリズム概要からステップ1の間) それぞれの三角形で均一にポイントをサンプリングして、空間グリッドに投げ入れます。
  • テスト中の凸包の境界ボックスをつかんで、この境界ボックスの内側のグリッドにあるすべてのポイントを集めます。
  • 集めたポイントから、凸包の内部のすべてのサンプルポイントに対して、もしも凸包の背面に当たれば通常は見られる元の表面に沿ってレイキャストします。
  • 背面に当たる最大距離の光線が最終的に凹面エラーとなります。
  • もし、凸包が元の表面の外に突き出していない場合、結果は0であるべきです。
  • これは、最初のサンプルレイキャストが最大許容グローバルエラーを超過したらすぐに早期に退出することで最適化できて、これはエッジ崩壊を止めるのに十分です。

このシステムは、元の形に対して凸包がどの程度のエラーをもたらすかをチェックする確固とした方法を提供してくれますが、ここで一つ足りないことがあります。 この方法は、3D凸包でのみよく機能します。 もし、凸包が平たい場合、サンプルポイントは決して2D凸包形成の間にテストする必要がある方向には整列することはありません。 右の環境設定を例に取ると、もし青と緑の三角形が凸包を形成して、赤と組み合わさろうとする場合、この凸包の内側にあるどのサンプルポイントも0以外のどの距離でも凸包の背面に影響しない確率が高いです。 これを正しく解決するためには、すでに説明したものと同じくらい入り組んだまったく異なる2Dエラー計算のプロセスを考えなくてはなりません。

かわりにできる小さな仕掛けがあります。 元の2つの凸包の合計の領域と結果の領域を比較することができます。 もし、結果となる閉包に2つのソース閉包の合計よりも大きなエリアがある場合、凹面が閉鎖するかもしれないのが分かるでしょう。そして、そのため余剰エリアの平方根は、この場合に凹面エラーとして扱うことができます。 そして最後に、入力凸包が正しく形成されていると過程すれば、潜在的な凸包候補のエラー探知にいい方法があります!

凸包生成、Quickhull (アルゴリズム概要のステップ2)

凹面エラー計算を微調整した後、まだ問題があることを確認するためにビジュアルデバッガーを使いました。

  1. 大きな凹面を封じる特定の凸包は、それでも0の結果で凹面エラーテストに合格します。
  2. 2つの凸包を組み合わせることで、元の形に穴を残して頂点が消える原因となることがあります。

元のHACD導入は、Quickhullアルゴリズムの変形型を使ったのですが、アルゴリズムが素早く既存の凸包に新しいポイントを追加するため完璧な選択となり、これはエッジを崩壊させるときにすることでした。 当社の視覚化するデバッガーによって集められたデータの最初のレビューが明かしたことは、結果となる閉包にはしばしば逆三角形があり、当社が以前に説明した凹面エラー計算手法にとっては画期的なものでした。

このアルゴリズムが機能するはずの方法というのは、既存の閉包に対して新しいポイントを選ぶとき、次にポイントが外にある平面の三角形を見つけます。 これらの三角形は削除のためにマーキングされ、他の三角形に対するエッジは、ポイントが凸包を封じるために処理をしている新しい三角形のセットを形成するのに使われます。 バルブの講演からQuickhullアルゴリズムについて学べることは、閉包のうちの一つがコプラナー三角形であるときに特に不動少数エラーに非常に敏感であるということです。 右側にある例は、Valveによって説明された問題を例証しない簡単なケースの断面です。

問題を理解するために、左のような形の断面を考慮しなければなりません。 三角形EとFがポイントが外にあるとみなすか平面の内側にあるとみなすかよくわからないQuickhullの状態を想定してください。 実際、最悪のシナリオはFが内側の点と思われる時にEが外にある点だと想定することです。 Quickhullでは三角形の配向は隣接する三角形によるため、この種類の整合性のないトポロジーは、配向の悪い三角形を作り出すか完全な失敗という結果になり得ます。

バルブ(Valve)のダーク・グレゴリウス(Dirk Gregorius)は、このような種類の矛盾は不可能だとされているこの問題を単一表面のオブジェクトをコプラナー三角形に融合させることで対処しましたが、個々の三角形同士の区別はまだ重要であるので、このアプローチは使えません。 かわりに、複数のコプラナー三角形が属して使う厚い平面を作って、連結し合って平面の中に収まっているどんな三角形もポイントが1つの方法で内側か外側にあるかを割り出す計算を確実に解けるようにしています。 これは、個々の三角形への言及を保持することを許容しながら、ダークの表面融合の解決法がするのに似た方法で本質的に問題を解決します。

以前の凹面エラー計算のように、2Dの例も考えなければなりません。 さまざまな入力データから凸包分解コードを守るためには、こプラナー三角形の組み合わせを許容するために必ず 2D Quickhull3D Quickhullも導入しなければなりません。 もし、私たちが共角三角形と同じ過程を使おうとしたら機能せず、しばしば入力頂点を削除するか失敗するでしょう。

無矛盾浮動少数処理

信頼して理解した凸面生成凹面エラーに対する解決法を見出した後でも、まだ問題が起きていましたが、ビジュアル・デバッガーは半変形平面のケースにおいてよくあるということを明らかにしました。

これは、3Dジオメトリにおいて一番の懸念の一つに立ち返ります。不動少数の首尾一貫した処理が必須です。 このアルゴリズムを強靭に作用させるためには、イプシロンの概念と量子化情報が統合されなければなりません。

アルゴリズムを通じて、イプシロンの概念が使われた様々なポイントは、以下の通りです。

  • 入力ジオメトリから双対グラフを作成するときに、複数の縮退頂点が一つの頂点に合併されました。
  • 凸包生成の段階を通じて、2Dか3Dモードのどちらで操作しなければならないかを決定するために凸包が互いに同一平面上かをテストする必要がありました。
  • 凹面エラー計算の間、現在の閉包の平たさをチェックする必要があり、凸包の内部に対して例キャストするには、首尾一貫したイプシロンが必要でした。

一度、アルゴリズムの環境設定としての量子化距離 (s) が決定したら、sをイプシロンとして扱うことが必須であり、私たちの平さの定義もそうです。 これは、一つの平面の幅 sに収まるすべてのポイントは、コプラナーとされなければならないという意味です。 平面幅 sに収まるポイントのセット上にあるどんな凸包生成も、純粋な2D操作として処理されなければなりません。 さらに、イプシロンに関するすべてのクエリは、1つの次元で行なわなければならず、オブジェクトのエリアや量に関するどのようなクエリも、平面からの最大距離と比較してチェックされなければいけないという意味です。

結論

プロセスの最後では、ちょっと振り返って「何を学んだんだろう?」と自問自答することは常に楽しいことです。 HACDには、一貫した質の高い結果を得るには、絶対的に高レベルのコンセプトを実行することの重要性を強調します。

  • 均一表面サンプリング – アルゴリズムがどれだけうまく処理をしているかを測る元の幾何学を良く妥当に見る必要があります。
  • 凹面エラー計算そして 凸包生成の間の2Dと3D操作の区別。アルゴリズムは、入力幾何学がコプラナー面のないオブジェクトを滑らかにしない限り、その時間の大部分を2D操作に使います。 アルゴリズムの2D段階は非常に重要です。
  • 入力三角形の連結性を計算するために重大で、Quickhullコプラナー平面問題の助力となり、2Dと3D操作を分かつ量子化と浮動少数処理のための首尾一貫したシステム。

これらの3つの概念は、HACDライブラリの大規模な内部リファクターにつながる基本となる柱であり、これによってRobloxの三角形メッシュとCSGオブジェクトのための一般的な自動衝突幾何学の出荷ができるようになります。 この作業が終わっていても、このシステムをさらに良くするためにはかなりの仕事量が残っています。

この方法で続けたい調査には、さまざまな道のりがあります。

  • パラレリズム(平行構造)、性能の向上。
  • 容積測定保存: 当社の現在のアルゴリズムは容積を保存せず、これはVHACDが集中して解決するものです。
  • 改良済み2D凹面エラー: 当社の現在の2D凹面エラー計算は、凹面の閉鎖に対して場所の変更をチェックしているため偽陽性を生み出します。 エッジ崩壊をブロックすることは、アルゴリズムの収束から不必要に潜在的に有効な解決方法を削除するため、これは問題となり得ます。
  • 上級ユーザーのための微調整の結果にアルゴリズム微調整を合わせます。

Robloxはデフォルトで動く機能を常に大事にしてきました。そして、手動で衝突ジオメトリをマッサージすることなしに高品質な衝突を達成できるようにするのは、私たちが常に目指している難しいゴールです。 ピクセル的に完璧な衝突に到達したわけではありませんが、困難なCSG操作の結果を自動的にシミュレーションできることを非常に嬉しく思います。 これは、Robloxの任意幾何学での衝突生成の向上においてエキサイティングな新しい段階のほんの最初のステップであり、チームの調査がどこにあり、ユーザーフィードバックが私たちの努力を後押ししているのを見るのはエキサイティングなことです!

結果

すべての結果は、元のHACDとRoblox HACDで一環した設定で計算されています。 そえぞれの色は、違う凸包です。

SetNClusters 1
ScaleFactor 1000 // 操作のために、すべてのオブジェクトは1000 x 1000 x 1000の立方体にリスケールされます
ConnectDist 0.1 // これは量子化距離です
Concavity 10 // これは、エッジ削除のための許容凹面エラーです
CompacityWeight 0 // この設定は外周によるエッジ崩壊順序を好み、当社は使いません。
VolumeWeight 0 // この設定は、量によるエッジ崩壊順序を好み、当社は使いません。

 

左: RoHACD 中央: 入力Geom 右: HACD


Robloxコーポレーションとこのブログは、いかなる企業もサービスも推奨も支持もしません。 また、このブログに含まれる情報の正確さや完全性について、いかなる保証または約束もしません。

このブログ記事は、元はRobloxテックブログ に掲載されたものです。