[Core] DelaunayTriangulation is generating improper triangles with points lying on a sphere surface

[bkrahmer]

Hi. I wrote a quick test against the DelaunayTriangulation, to verify if it could create a tessellation from all of the vertices from an existing generated sphere. I know it's valid because I can output it as an STL and view it in Blender. Of 2048 original faces, only 1088 were generated from the DelaunayTriangulation, and approximately 130 of them had at least one of the Points of the resulting Triangles set to null.

Version 1.0.2

This is the heart of the code. I'm not doing something wrong by chance? I can provide a complete working test case if someone can look into it. I browsed through the code, and it's way over my head.

//...build up tessPoints from my existing mesh DelaunayTriangulation triangulation = new DelaunayTriangulation(tessPoints); Iterator<Triangle> iter = triangulation.trianglesIterator(); //...convert back to my representations and output as STL. no bueno.

thanks!

[martinpernollet]

The author of this algorithm told me long time ago that it was written for terrain generation - thus assuming you should not have two surfaces for the same Z. Your sphere is not satifying this constraint. I also notice that the algorithm might provide unsatisfying results for a set of points lying around a vertical plane. This led me to investigate other algorithms :

• alpha shapes are good but require an annoying parameter tuning (I found a Java version that is on my computer)
• poisson recognition - there is an implementation in the famous point cloud library. I did not really evaluate it on my vertical plan use case but it appeared to me that it is the most satisfying approach. There is no official java version to my knowledge , but in the mean time I found someone on github providing a binding (pcl-java or cpl-swig)

Clean 3D interpolation is a very complex topic...

Le mar., mai 19, 2020 à 11:57, Brian Krahmer [email protected] a écrit :

Hi. I wrote a quick test against the DelaunayTriangulation, to verify if it could create a tessellation from all of the vertices from an existing generated sphere. I know it's valid because I can output it as an STL and view it in Blender. Of 2048 original faces, only 1088 were generated from the DelaunayTriangulation, and approximately 130 of them had at least one of the Points of the resulting Triangles set to null.

Version 1.0.2

This is the heart of the code. I'm not doing something wrong by chance? I can provide a complete working test case if someone can look into it. I browsed through the code, and it's way over my head.

//...build up tessPoints from my existing mesh DelaunayTriangulation triangulation = new DelaunayTriangulation(tessPoints); Iterator iter = triangulation.trianglesIterator(); //...convert back to my representations and output as STL. no bueno.

thanks!

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or unsubscribe.

[bkrahmer]

Ok, thanks for the feedback! My end result will be much more complex than a sphere, but I know that it will be possible to generate a manifold with all the points. Perhaps there is a brute-force solution? Correctness is much higher value than speed for me. cheers

[vocobox]

I think your only “brute force” might be to apply domain specific knowledge

[jzy3d]

Hi, I would be interested by the dataset to try reproducing and analysing the problem. If you have the blender image available, I am interested. Thanks!

[bkrahmer]

@jzy3d sorry, I don't have the data anymore. IIRC, I just generated a sphere in blender and then output it as an STL...