こんにちわ，Pocolです。
相変わらずGI周りの資料を漁っているのですが，ふと見たGDC 2012の”Light probe interpolation using tetrahedral tessellations”のAppendixの四面体化に関するところで，Bowyer-Watsonアルゴリズムというのが出てきました。
※図は，Robert Cupisz, “Light probe interpolation using tetrahedral tessellation”, GDC 2012より引用。
Bowyer-Watsonアルゴリズムというものを知らなかったので，あとで実装するためのメモを残しておこうと思います。
https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm
Bowyer-Watsonアルゴリズムは、インクリメンタルアルゴリズムだそうです。
Wikipediaに、Bowyer-Watsonアルゴリズムの基本的な実装の擬似コードが載っています。計算量は、
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | function BowyerWatson (pointList) // pointListは、三角化する点を定義する座標の集合です。 triangulation := empty triangle mesh data structure add super-triangle to triangulation // pointList内のすべてのポイントを完全に含むことができるように十分な大きさを持たなければならない. for each point in pointList do // 三角化にすべての点を一度に追加します. badTriangles := empty set for each triangle in triangulation do // まず、挿入によって無効になった三角形をすべて見つけます。 if point is inside circumcircle of triangle add triangle to badTriangles polygon := empty set for each triangle in badTriangles do // ポリゴンの穴の境界を求めます. for each edge in triangle do if edge is not shared by any other triangles in badTriangles add edge to polygon for each triangle in badTriangles do // データ構造から削除します. remove triangle from triangulation for each edge in polygon do // ポリゴンの穴を再三角形化します. newTri := form a triangle from edge to point add newTri to triangulation for each triangle in triangulation // ポイントの挿入が終わったので，お掃除する. if triangle contains a vertex from original super-triangle remove triangle from triangulation return triangulation |
GDCのスライドには「すぐに使えるソリューションが必要な場合は、Hang Siによる[TetGen]が非常にまともで、四面体メッシュの精密化のような追加機能や潜在的に有用な機能を持っています。」と書いてあります。該当する参考文献なのですが，https://www.berlios.de/software/tetgen/経由でC++の実装があるダウンロードページに飛べるようです。ライセンスはGNU Affero Public License v.3.0なので注意してください。
あとは，ちゃんとソースコードの中身見れていないのですが，Stride3d(元Xenko)のリポジトリにも四面体化のコードが上がっているようです。
https://github.com/stride3d/stride/blob/master/sources/engine/Stride.Rendering/Rendering/LightProbes/BowyerWatsonTetrahedralization.cs
これらを参考に実装すると良さそうです。