algorithm - 多角形メッシュを部分的に塗りつぶすアルゴリズム

Question

概要:
3D ポリゴン メッシュで表される単純なプラスチック サンドボックスがあります。サンドボックスに特定の量の水を注いだ後、水位を判断できるようにする必要があります。

• 注ぐと水が上から均等に分配されます
• 流体シミュレーションはありません。水は非常にゆっくりと注がれます
• 高速である必要があります

質問:
この問題にはどのような手法やアルゴリズムを使用できますか?

私はこれを行うことができるプログラムなどを探しているのではなく、アルゴリズムだけを探しています-実装を行います。

Answer 1

ただのアイデア：

まず、すべての鞍点を計算します。離散モース理論やトポロジーの永続性などのツールは、ここでは役に立ちますが、私はそれらについてほとんど知りません。次に、すべての鞍点を最も低い位置から繰り返し、水がその点を通過し始める時点を計算します。これは、隣接する2つの盆地の浅い方（体積と表面積の観点から）が、その鞍点の高さに一致するレベルに達した時間です。その時点から、その表面に注がれる水は、2つの流域が同じレベルに達するまで、他の流域に流れ込み、代わりにその水位に寄与します。その後、それらは単一の流域として扱われます。途中で、盆地に関連付けられた領域が変化するため、他の鞍点に到達する時間を修正する必要がある場合があります。高さを上げるのではなく、時間を増やす順に繰り返します（例：キー減少操作でヒープを使用する）。洗面器の最後のペアの高さが同じになると、完了です。その後、残っている盆地は1つだけです。

全体として、これは物事が根本的に変化する一連の「興味深い」時間になります。これらの間では、水位を計算するために単一の流域の形状を考慮するだけでよいため、問題ははるかに局所的になります。この局所的な問題では、その流域に含まれる水の量がわかっているので、たとえば二分法を使用してそれに適したレベルを見つけることができます。隣接する「興味深い」時間は、二等分線に役立つエンドポイントを提供する場合があります。

三角形のポリトープの体積を計算するには、靴紐の式の3Dバージョンを使用できます。すべての三角形について、その3つの頂点を取得し、それらの行列式を計算します。それらを合計して6で割ると、囲まれた空間の体積が得られます。すべての三角形を一貫して方向付けるようにしてください。つまり、すべてを内側から見た場合、またはすべてを外側から見た場合です。選択によって全体的なサインが決まります。試してみて、どれがどれであるかを確認してください。

あなたの質問は洗練が必要かもしれないことに注意してください：盆地のレベルがまったく同じ高さで2つの鞍点に達したとき、水はどこに流れますか？流体シミュレーションがなければ、これは明確に定義されていないと思います。あなたはそれがすべての隣接する盆地に均等に分配されるべきであると主張することができます。このような状況が実際のデータで発生する可能性は低いと主張できるため、1つの隣接点を任意に選択します。これは、この鞍点の高さが他の鞍点よりも非常に低いことを意味します。または、他の多くの解決策を考え出すこともできます。このケースに関心がある場合は、そこで何を期待するかを明確にする必要があるかもしれません。

Answer 2

簡単な解決策が頭に浮かびます。さまざまな高さの水を二分探索し、含まれる水の量を計算します。すなわち、サンドボックスの深さ D の水の高さの上限推定値から始めます。砂は多孔性であるため、箱の縁まで水を満たした状態で最大の体積になることに注意してください。それ以上の水は、私たちの架空の裏庭の芝生に戻ってしまいます. また、これは、ソリューション内の鞍点や複数の水位について心配する必要がないことを意味することに注意してください。ここでも、岩でできた山ではなく、通常の多孔質の砂を想定しています。高さ D に含まれる水の体積を計算します。それが近似しきい値内にある場合は終了します。それ以外の場合は、別の高さで見積もりを調整し、繰り返します。

任意の三角形の砂片について、砂の表面上の水の体積を計算するのは簡単であることに注意してください。これは、三角形のプリズムの体積に、砂と接触している四面体の体積を加えたものです。

砂線より下の水の体積も同様に計算されますが、その一部が砂で占められるため、体積は少なくなります。砂の典型的な空隙の内容、または保水能力をインターネットで検索することをお勧めします。または、どんなフレーズでも正しい結果が返されます。また、砂が喫水線より上にある場合、一部の三角形では砂の上の水がゼロになる場合があることに注意してください。

メッシュの 1 つの三角形のサンド ラインの上下両方の水の体積を取得したら、すべての三角形をループして、指定された高さのサンドボックス全体の合計体積を取得します。

これはかなりばかげたアルゴリズムであることに注意してください。しかし、より巧妙なことをしようとする派手なシュマンシエ アルゴリズムと比較して、まともなパフォーマンスが得られると思います。これは三角形ごとのほんの一握りの乗算と合計であり、ifステートメントやその他のフロー制御がほとんどないブラインド ループは、プロセッサが適切にパイプライン処理できるため、高速に実行される傾向があることに注意してください。

このメソッドは、サンドボックスの非常に詳細なメッシュがあり、計算を複数のコアに押し込みたい場合、各三角形をループする代わりに簡単に並列化できます。または、ループを維持し、各コアに異なる高さを押し込みます。または、他の何か; 並列化と高速化については、読者の課題として残しておきます。