こんにちわ，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アルゴリズムの基本的な実装の擬似コードが載っています。計算量は、\(\mathcal{O}(n^2)\)ですが，効率的に計算する方法がいくつかあるそうです。例としては，三角形の接続性を利用して，すべての三角形をチェックせずに円周上の新しい点を含む三角形を見つけるようにするなどで\(\mathcal{O}(n log n)\)まで減らすことができるそうです。

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

これらを参考に実装すると良さそうです。