三角測量とは何ですか？
一般的な場合、 三角形分割は、幾何学的オブジェクトを三角形に分割することです。 この概念自体は非常に単純です。 ゲームエンジンの場合の三角測量の基本的な例は、メッシュです。 厳密に言えば、メッシュは三角形だけでなく、さまざまな理由でゲームエンジンで構成できるのは、三角形で構成されるメッシュです。
三角形分割は異なりますが、最も一般的な三角形分割のタイプの1つはドロネー三角形分割です。 このタイプの三角形分割は、各三角形の外接円内に、この三角形の頂点のみがあるという特性によって区別されます。
なぜ必要なのですか？
一般に、ゲーム業界以外では、三角測量の助けを借りて、多くの問題が解決されています。 ゲーム開発では、最初に頭に浮かぶタスクはナビゲーションメッシュです。 Navmeshは、プレーヤーが歩くことができるスペースを決定するデータ構造です。 環境の一部との衝突を判断するような複雑な計算タスクを回避します。
ゲーム開発でDelaunay三角形分割を使用して解決できる2番目の興味深い問題は、ポイントのセットとして表される地形とオブジェクトの生成です。 この場合のDelaunay三角形分割の主な利点は、その特性に基づいて、非常に鋭い三角形が回避されて、地形に干渉してアーティファクトが作成されることです。
さらに、制約付きのDelaunay三角形分割とChewの2番目のアルゴリズムやRuppertのアルゴリズムなどのアルゴリズムを使用して、メッシュをより適切に生成し、別のアプリケーション（有限要素法）に適したメッシュを生成できます。
有限要素法自体は、応用物理学の問題を解決する方法の1つです。 gamedevでは、変形のシミュレーション、流体シミュレーション、その他の特殊なシミュレーションに関連する多くの問題を解決できます。 エフェクト。 通常、リアルタイムではメソッドの計算の複雑さが高すぎるため、アニメーションのエフェクトを記録するために使用します。 メソッドを使用する際の重要な詳細は、メソッドの誤差がグリッド内の三角形の角度に依存することです。 グリッドに非常に鋭い角度がある場合、この方法は大きな誤差を与えます。このため、上記のアルゴリズムが必要です。
そしてもちろん、一般に、手続き型メッシュ生成。 例として、githubプロジェクトは、メッシュを描画する機能を備えたシーンを示しています。 一部の物理パズルでは、このアプリケーションを基本的なメカニズムとして使用しています。 ただし、さらに、三角測量アルゴリズムを使用すると、手続き型生成を使用して、手続き型破壊性などの問題を解決できます。
gamedev三角形分割に加えて、ネットワーク、コンピュータービジョン、さまざまな分析アルゴリズム、および相互のポリゴンの結合と削除などの計算ジオメトリの問題（ゲームの開発で発生する問題で役立つことが多い）で使用されます
穴のある耳のクリッピング
おそらく最も単純な三角測量アルゴリズムの1つです。 最適なグリッドが得られず、最悪の場合に計算上の複雑さO（n ^ 2）が大きくなります。
詳細については、この記事をご覧ください。
Bowyer – Watsonアルゴリズム
一連のポイントに対してドロネー三角形分割を生成するアルゴリズム。 一般に、ほとんどのDelaunayアルゴリズムと同様に、正しく実装されている場合、アルゴリズムの複雑さはO（n log n）です。ここで、nは頂点の数です。 ただし、場合によってはO（n ^ 2）を占めることもあります。
耳切りに関する欠点は、このアルゴリズムが凸三角形分割を構築し、基本的な実装では結果のグリッドに穴が含まれないことです。
ドローネ精密化処理
Chewの2番目のアルゴリズムとRuppertのアルゴリズムは、ドロネー三角形分割に制約を入力し、グリッド内の三角形の最小角度を設定できるアルゴリズムです。 アルゴリズムの重要な詳細は、無限ループに入る可能性があり、約20.7度と29度の間の角度で結果が得られることが保証されていることです。 上記の問題を解決するには、最小角度を設定する能力が重要です。
Chewの2番目のアルゴリズムは、無料パッケージwww.cs.cmu.edu/~quake/triangle.htmlおよび.Net archive.codeplex.com/?p=triangleのポートに実装されています
Unity用のTriangle.Net
まあ、三角形分割の助けを借りて非常に多くのクールなタスクを解決できるので、休日にはUnityのラッパーを実装したかったので、いつも手元に便利なツールがありました。 この実装では、平均的な三角形分割アルゴリズムはO（n）で機能し、最悪の場合はO（n * log n）で機能します。ここで、nは頂点の数です。 たとえば、正方形にランダムに散らばった1kkの頂点をテストする場合、Intel Core i7-8700のエディターのユニットは平均7.56秒でグリッドを構築しました。
Unity向けに調整された拡張メソッドの存在下での元のライブラリとの主な違い、およびライブラリ全体でのdoubleからfloatへの置換（+キャスト用の特定の演算子の数）ユニットでのDoubleは、あまり意味がありません。 物理シミュレーションを検討する場合は、プラスライブラリ上で別のアプリケーションを使用します。計算の結果は、純粋に視覚化のためにUnityをすでに提供しています。 また、メッシュタイプをTriangleNetMeshに名前変更し、Unityからのメッシュに関連してノックダウンしないようにしました。 はい、彼らはすでに別の名前空間にありますが、それでも、新しいメッシュは、あるメッシュの助けを借りて別のメッシュを取得するという事実によって少しノックダウンされると思います。
ライブラリの本質は、最初にいわゆるポリゴンを指定する必要があるということです。 次に、それに基づいて、すでにメッシュを生成します。 これがユニットデータ構造で機能するために、いくつかの拡張メソッドが導入されました。
使用例
public void GenerateMesh() { if(_CurrentState != MeshDrawerState.Nothing) return; Polygon poly = new Polygon(); poly.Add(_Contour); foreach (var hole in _Holes) { poly.Add(hole, true); } var triangleNetMesh = (TriangleNetMesh) poly.Triangulate(); GameObject go = new GameObject("Generated mesh"); var mf = go.AddComponent<MeshFilter>(); var mesh = triangleNetMesh.GenerateUnityMesh(); mesh.uv = GenerateUv(mesh.vertices); mf.mesh = mesh; var mr = go.AddComponent<MeshRenderer>(); mr.sharedMaterial = _MeshMaterial; var collider = go.AddComponent<PolygonCollider2D>(); collider.points = _Contour.ToArray(); var rb = go.AddComponent<Rigidbody2D>(); rb.mass = triangleNetMesh.Triangles.Sum(tris => tris.Area); Clear(); }
デモンストレーションと使用例のために、メッシュを描画する機能を備えた特別なデモシーンが作成されました。 これとgithubプロジェクトのライブラリのポートに慣れることができます。
ご清聴ありがとうございました！ ポートと記事が誰かにとって有用であり、なぜ三角測量と数学全体の知識が必要なのかが少し明確になることを願っています。 ゲーム開発におけるさまざまな数学的問題を解決するためのアプリケーションと方法を引き続き開示していきます。 計算幾何学自体にはまだ多くの興味深いものがありますが、高等数学の他の多くの興味深いセクションがまだあります。