Concave Mesh Triangulation With Known Boundary

Question

I have a set of 3D points that (may) form a concave shape. They are already ordered clockwise. The resulting mesh will be (nearly) planar with some slight height adjustments.

What's the best algorithm for me to use in C# (Unity) to triangulate a mesh out of these points?

What you are looking for is Delaunay Triangulation algorithm. For unity you can use already existing implementation https://github.com/adamgit/Unity-delaunay — FCin, Mar 20 '17 at 16:27
Doesn't Delaunay always end up convex? Or am I misremembering? — ADaurio, Mar 20 '17 at 16:54
Delaunay allows concave shapes. If I remember correctly it had to do something with comparing angles. Here's a sample http://www.it.uu.se/edu/course/homepage/projektTDB/ht13/project10/Project-10-report.pdf — FCin, Mar 20 '17 at 19:15
When u read the paper about concave delaunay triangulation it doesn't say comparing angles. It speaks about alphashapes. Care to elaborate? Am I missing it? — Micromega, Mar 21 '17 at 23:09

score 1 · Answer 1 · answered Mar 20 '17 at 08:04

1

I would start from Triangle.NET open source project. You may need to inherit your own Vertex type to keep the Z values (triangulation is always performed on XY plane)

answered Mar 20 '17 at 08:04

abenci

8,422
19
69
134

Is that library usable in Unity? – ADaurio Mar 20 '17 at 16:22
It's a standalone library, you can use it any .NET project you like. – abenci Mar 20 '17 at 20:59

Concave Mesh Triangulation With Known Boundary

1 Answers1

Linked