# Delaunay Triangulation in 3D

I am planning to construct a CAD model from a point cloud.

• The point cloud is a list of unique 3D point.

• The CAD model is a list of triangles (2D triangles not tetrahedra) in a 3D space.

Lets say there is a triangle with vertices $(A,B,C)$ and there is a point $P$.

I would like to check if the $P$ is inside the inner region (sphere, ellipsoid or what ever based on Delaunay) belonging to the triangle.

Based on Delaunay method, how can I perform such a check?

I am looking for the mathematical details not just a English description.

• I believe a direct use of the Delaunay "triangulation" in higher dimension yields higher dimensional "triangles", so in 3D you would obtain tetrahedra, not 2D triangles. There may be methods or heuristics to pick some "good" triangles from a Delaunay tetrahedralization though, is that what you're looking for? – N.Bach Apr 10 '18 at 15:50
• Are you looking to implement a "point in polyhedron" test? The extension of 2D "point in polygon" to 3D? In your case, the polyhedron being one or more closed objects defined by triangle meshes. – Nominal Animal Apr 10 '18 at 18:20
• @NominalAnimal One way to compute a 2D Delaunay triangulation is to ensure every triangle satisfy a "Delaunay condition" : the circumcircle of the triangle must not have any point (from the point cloud) in its interior. So I assume the question is about how to transpose this into 3D, which normally uses spheres circumscribing a tetrahedron. – N.Bach Apr 10 '18 at 23:52
• @NominalAnimal, Consider that I have a depth image point cloud like this. Forget the color at the moment. I look for a method to convert this point cloud to a mesh. Unfortunately, in 3D the points are not projectable in a 2D plane nor triangles define a circum-hypersphere which is referred in wiki. – ar2015 Apr 10 '18 at 23:56
• @N.Bach, but when I am comparing a poin against a triangle, how can I create a tetrahedron from a triangle? Do you think I should consider the sphere with minimum radius circumscribing the triangle? – ar2015 Apr 10 '18 at 23:57