What is the best initial shape for 3D Delaunay incremental algorithm?

Question

I'm doing 3D Delaunay, with the incremental method. I've tested it in 2D with an initial triangle for inserting the vertices and it works great, but if I use a triangle for 3D, some vertices do not fall into any circumscribed sphere therefore they don't get inserted. I've tried with a tetrahedron but if the first node falls into the four of the faces, all vertices create new edges towards this new vertex, and deletes all of the initial triangles.

Answer 1

Whichever shape you take, you will always have to deal with side effects. The best shape is no shape. This is what we are doing in the CGAL library http://www.cgal.org Look at the manual, chapters "2D triangulations" and "3D triangulations". See also or the journal paper https://hal.inria.fr/inria-00167199/

Answer 2

You can read my answer for this question (Bowyer-Watson algorithm: how to fill "holes" left by removing triangles with super triangle vertices). If the supertriangle is too small sometimes you end with circumcircle outside of the supertriangle. You can try a point-in-polygon test to avoid it.