I’m loading data where faces are defined as (properly coplanar) polygons with holes. That is, I have a list of 3D points for the outside of the polygon; and then I have zero or more lists of points defining holes to be cut out of that polygon.
The Triangulator script on the wiki is great, except that it doesn’t support holes.
This “Advanced Triangulation” script looks good, except that it only works with 2D points. And fixing that isn’t a simple matter of changing Vector2 to Vector3, because the code is making much use of the X and Y coordinates of the points. (And actually, so is Triangulator.)
Another option is to combine the C# version of poly2tri with Clipper, which looks pretty robust but way more complex than I was hoping for.
I suppose what I could do is figure out a transform between the original 3D points, and the XY plane, then use Advanced Triangulation to break it up, and apply the inverse transform to get back to proper 3D points. It’s not immediately obvious to me how to do that transformation, though.
That’s an interesting thought. But how to do that, when the holes are arbitrary? It strikes me as a nontrivial problem in itself. And, Triangulator is also only 2D… if I can convert my polygon into 2D, I may as well use that Advanced Triangulation script, which handles holes.
After thinking about it more, maybe converting into 2D isn’t all that hard. I can take any three points in the polygon and find the normal to the plane they define. Then I just need to rotate from that normal, to Vector3.forward (which is a normal to the XY plane). I think I can find that rotation with Quaternion.FromToRotation.
I’ll need to actually try it to be sure, but it makes sense in my head at least!
So as I understand, You have outer polygon and polygons for each hole.
You just need to go from point of outer polygon to point of first hole, then from point of first hole to second hole…to last hole than go backwards. Should be pretty easy to implement
update:
Hm. It seems you probably need to connect to closest hole and avoid hole/edge intersections
But, even after doing all that, I would still need to rotate the whole polygon into the XY plane in order to use Triangulator (which is based on Vector2). So, I may as well just use the Advanced Triangulation code, which already handles holes.
I’ll probably be tackling this later today… I’ll report back with the results, in case anyone’s interested.
I missed that your polygons are planar. Yeah, it should be easy to calculate matrix which rotates polygon to XY plane. Then triangulate everything and rotate by inverse matrix to original position.
I’ve got this working now, but not with the Advanced Triangulation blog post — I hadn’t read that carefully, and totally missed that it was writing the data out to a file, invoking an external command-line executable to triangulate it, and read it back in. That won’t do for my purposes.
So I instead got the C# port of poly2tri to work. This was a bit of an adventure, since the API is (as far as I can tell) completely undocumented, but with enough code-spelunking one can figure it out. It works nicely now, and even for (planar) polygons in any arbitrary plane (using the rotation trick we discussed above).
I’ll write it all up in a blog post when I get the chance, since this seems to be something people ask for perodically, and it was surprisingly hard to find.
I read this a few days ago and got scared off by the 3d aspect. What you described doing – projecting 3d polygons into 2d, cutting them, and then projecting back again would not have the results you expect. I think it would be similar to that snowflake craft for kids… I also didn’t realize your polygons were two dimensional but in 3d space.
I really don’t mean to be negative, especially since this is a great contribution, but isn’t your title slightly misleading? As I understand it now you are, not triangulating 3D polygons but actually, triangulating 2D polygons in 3D space.
