Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Triangulation of 3D polygons with holes?

Discussion in 'Scripting' started by JoeStrout, Aug 17, 2015.

  1. JoeStrout

    JoeStrout

    Joined:
    Jan 14, 2011
    Posts:
    9,859
    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.

    Any suggestions?

    Thanks,
    - Joe
     
  2. mholub

    mholub

    Joined:
    Oct 3, 2012
    Posts:
    123
  3. JoeStrout

    JoeStrout

    Joined:
    Jan 14, 2011
    Posts:
    9,859
    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!
     
  4. Duugu

    Duugu

    Joined:
    May 23, 2015
    Posts:
    241
    So your "polygons" are flat but in a 3D space, correct?

    [e]
    That is what my question was about. :)
     
    eisenpony likes this.
  5. JoeStrout

    JoeStrout

    Joined:
    Jan 14, 2011
    Posts:
    9,859
    Yes, that's correct.
     
  6. mholub

    mholub

    Joined:
    Oct 3, 2012
    Posts:
    123
    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

    https://www.dropbox.com/s/ppghgsv4fp054e9/polyWithHoles.PNG?dl=0
     
    Last edited: Aug 18, 2015
  7. JoeStrout

    JoeStrout

    Joined:
    Jan 14, 2011
    Posts:
    9,859
    Yes, that's the tricky bit I think.

    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.
     
  8. mholub

    mholub

    Joined:
    Oct 3, 2012
    Posts:
    123
    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.
     
  9. JoeStrout

    JoeStrout

    Joined:
    Jan 14, 2011
    Posts:
    9,859
    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.

    Cheers,
    - Joe
     
  10. JoeStrout

    JoeStrout

    Joined:
    Jan 14, 2011
    Posts:
    9,859
  11. eisenpony

    eisenpony

    Joined:
    May 8, 2015
    Posts:
    974
    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.
     
  12. JoeStrout

    JoeStrout

    Joined:
    Jan 14, 2011
    Posts:
    9,859
    No... the word "polygon" already means two-dimensional (references: 1, 2, 3, and noting that "plane figure" means a figure in a plane).

    But these particular two-dimensional figures are in a 3D space, defined by 3D points (Vector3's), so I call them 3D polygons for short.

    I'm not sure what the term "3D polygons" means to you, but if they're not planar, they're not polygons.

    Finally, note that I'm not projecting the polygons into 2D; I'm rotating them into the XY plane. I agree that projection wouldn't do it in general.
     
    eisenpony likes this.
  13. eisenpony

    eisenpony

    Joined:
    May 8, 2015
    Posts:
    974
    Touché. I wasn't familiar with polytopes until today!