What is the best initial form for incremental 3D Delaunay?

Question

I am doing 3D Delaunay with an incremental method. I tested it in 2D with an initial triangle to insert vertices, and it works fine, but if I use a triangle for 3D, some vertices do not fall into any described sphere, so they are not inserted. I tried using a tetrahedron, but if the first node falls in four directions, all vertices create new edges with respect to this new vertex and delete all the initial triangles.

Answer 1

Whatever form you choose, you will always have to deal with side effects. The best form is not a form. This is what we do in the CGAL library http://www.cgal.org See the manual, chapters "2D triangulation" and "3D triangulation". See also or paper of the journal https://hal.inria.fr/inria-00167199/

Answer 2

You can read my answer to this question ( Boyer-Watson algorithm: how to fill the “holes” on the left by deleting triangles with super triangular vertices ). If the super-triangle is too small, sometimes you end up with a circle outside the super-triangle. You can try the point-to-polygon test to avoid it.