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

Polygon triangulation code

Discussion in 'Scripting' started by runevision, Jul 26, 2009.

  1. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    I'm doing some mesh generation for a spare time project, and I've come to a point where I really need to be able to triangulate any specified 2D polygon - i.e. split a 2D polygon (convex or not) into triangles so that I can use those to generate a mesh.

    I've looked a bit on what's already available on the Net, and I found these two projects written in C#:

    - http://www.codeproject.com/KB/recipes/cspolygontriangulation.aspx

    - http://www.codeproject.com/KB/recipes/Art_Gallery_Problem.aspx

    However, I've tested both, and they're both buggy, meaning that they produce incorrect results for many polygons, where some triangles are outside the polygon.

    There are much more promising projects with source code floating around, but unfortunately not in C#. For example:

    - http://www.codeproject.com/KB/recipes/hgrd.aspx

    - http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html

    If anyone have done polygon triangulation in Unity before (or just in C#) I'd be very interested in the code for that.

    Rune
     
  2. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    Well, I finally have an algorithm that actually works. I'll clean it up and post it.

    Rune
     
  3. jcarpay

    jcarpay

    Joined:
    Aug 15, 2008
    Posts:
    561
  4. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
  5. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    Sorry, didn't see your post at first. :)

    Yeah, the script I posted uses the ear clipping method too. It's not the most efficient method. I believe it's O(n * n) and there are more advanced methods that can do it in O(n log n) - but it gets the job done.

    Rune
     
  6. jcarpay

    jcarpay

    Joined:
    Aug 15, 2008
    Posts:
    561
  7. MH

    MH

    Joined:
    Jul 19, 2010
    Posts:
    1
    Hi Rune,

    Do you happen to have a code for Java Script?

    Also, what if the polygon is 3D with vertices having (x,y,z) values?! Does it really matter if the object is or is not in 3d. From what I understand the trinagles' corners attach to the vertices in the order they are added. Is this right?!

    I desparately need a working JS code, please.
    Thanks for your reponse, in advance.
     
  8. runevision

    runevision

    Joined:
    Nov 28, 2007
    Posts:
    1,892
    No, I'm afraid not.

    A polygon is planar by definition. If you have points in 3d space that are not co-planar then it's not a polygon and the algorithm won't apply.

    For example, the algorithm needs to be able to test whether a certain point is on one side or the other side of a line defined by two other points. Such a test makes sense in 2d but not in 3d.

    If you have points in 3d space that are co-planar, you can convert them into 2d points, then use the algorithm on those, and then use the returned vertex indices on the original 3d points.

    I'm not sure what you mean. How the triangels are formed depend on the shape of the polygon.

    If you're desperate, it should be no problem to learn the small differences between C# and JavaScript to be able to translate the script yourself. :)

    Rune
     
  9. nicoptere

    nicoptere

    Joined:
    Nov 18, 2011
    Posts:
    1
    [I know this thread is getting old... ]

    it works very well!
    a nice feature would be to have a first pass to decompose complex ( self intersecting ) polygons.

    thank you very much for sharing :)
     
  10. karl_

    karl_

    Joined:
    Mar 4, 2010
    Posts:
    464
    This code was very helpful in helping me get a grip on triangulation. Thanks a ton for sharing this.
     
  11. adven

    adven

    Joined:
    Jan 18, 2012
    Posts:
    1
  12. Demonwhisperer

    Demonwhisperer

    Joined:
    Mar 30, 2012
    Posts:
    4
    Hi Guys. I thought I'd post a version of this triangulation code I translated into javascript for anyone who needs it.

    You just need to create a Triangulator object like this:

    var tr:Triangulator = new Triangulator();
    tr.initTriangulator(verts2d);
    var triangles:int[] = tr.Triangulate();

    and then assign the triangles array to mesh.triangles of your desired mesh object.

    Hope somebody finds it useful.
    Enjoy

    Paul
     

    Attached Files:

  13. mcadesigns

    mcadesigns

    Joined:
    Aug 3, 2011
    Posts:
    1
    I managed to convert to code to display the 2D shape in 3D world if that's what you mean.
     
  14. Sjiggle

    Sjiggle

    Joined:
    Sep 12, 2012
    Posts:
    10
    I just wanted to share the following code. It allows both 2d and 3d points to be added to it. It's not the fastest method, I am sure there are improvements possible. Dear runevision, do you have any improvements ready?

    btw it's C#.

    Adding holes to the ear clipping is not as hard as it seems. If your edge finding tool is good enough, you will be able to make a difference between CCW and CW edges. Then sort these edges on their bounding box size (big to small) and cut a non visible line from the closest point of the inside to the outside edge (connecting the edges as a line). Then it's just a matter of triangulating.

    The version I am posting only tests if a point is inside a triangle, not on a triangle. If this is a problem, change

    Code (csharp):
    1.  
    2.         return ((aCROSSbp > 0.0)  (bCROSScp > 0.0)  (cCROSSap > 0.0));
    to

    Code (csharp):
    1.  
    2.         return ((aCROSSbp >= 0.0)  (bCROSScp >= 0.0)  (cCROSSap >= 0.0));
    Cheers and happy coding,

    View attachment $Triangulator.cs
     
  15. Eric5h5

    Eric5h5

    Volunteer Moderator Moderator

    Joined:
    Jul 19, 2006
    Posts:
    32,401
    Actually it is; I've done this and there are a lot of edge cases that aren't immediately obvious.

    --Eric
     
    Bunny83 likes this.
  16. Sjiggle

    Sjiggle

    Joined:
    Sep 12, 2012
    Posts:
    10
    You are right, I am still not done.
     
    Bunny83 likes this.
  17. Mark Duffill

    Mark Duffill

    Joined:
    May 2, 2013
    Posts:
    21
    Hi, I've fixed an issue where if you have degenerates (triangle with two or more points the same) it would fail to triangulate.

    To fix this inside Snip where it does:

    if (Mathf.Epsilon > (((B.x - A.x) * (C.y - A.y)) - ((B.y - A.y) * (C.x - A.x))))
    return false;

    I added:

    if (Mathf.Epsilon > (((B.x - A.x) * (C.y - A.y)) - ((B.y - A.y) * (C.x - A.x)))
    (A.SqDist(B) > SmallEpsilon A.SqDist(C) > SmallEpsilon B.SqDist(C) > SmallEpsilon)
    )
    return false;

    Where SmallEpsilon = 0.1 // you may want to tune this
    and SqDist = {var d = A-B; return d.X*d.X + d.Y*d.Y;}

    Thanks
     
  18. Lumen-Digital

    Lumen-Digital

    Joined:
    Aug 3, 2012
    Posts:
    16
    Hi Mark

    That was a useful addition - here it is again in a directly applicable format...

    float smallEpsilon = 0.1f;
    if ( Mathf.Epsilon > (((B.x - A.x) * (C.y - A.y)) - ((B.y - A.y) * (C.x - A.x)))
    Vector2.SqrMagnitude(A-B) > smallEpsilon
    Vector2.SqrMagnitude(A-C) > smallEpsilon
    Vector2.SqrMagnitude(B-C) > smallEpsilon)
    return false;
     
  19. remigillig

    remigillig

    Joined:
    Jul 4, 2013
    Posts:
    9
    For those visiting this thread later (like I just did), I made a C# port of the original SGI tesselator (which does 2D polygon decomposition/triangulation). It behaves quite nicely and is quite fast. You can find it at https://github.com/speps/LibTessDotNet
     
  20. MajorBulldozer

    MajorBulldozer

    Joined:
    Mar 14, 2014
    Posts:
    5
    Thanks a lot for sharing it.
    it's very useful.
     
    Last edited: Aug 3, 2014
  21. RobAtWestpierstudio

    RobAtWestpierstudio

    Joined:
    Oct 10, 2013
    Posts:
    1
    Hi. This project doesn't build out of the box: "Type or namespace 'Poly2Tri' does not exist in the current context". I don't see any external dependencies mentioned in your readme. Please advise!

    -Rob.
     
  22. keenanwoodall

    keenanwoodall

    Joined:
    May 30, 2014
    Posts:
    597
    Ok, so when you say this splits a 2d polygon into triangles, what do you mean? Are you saying that it forms a mesh from a spline or something? what is the difference between a 2d and a 3d polygon? The reason I'm asking this is because I'm trying to create an in game tool that lets you draw a mesh. It'll work pretty much exactly the same as the PolyDraw unity asset, but I want to make my own.
     
  23. PrefabEvolution

    PrefabEvolution

    Joined:
    Mar 27, 2014
    Posts:
    225
    I found rally fast and working solution inside Farseer unity plugin. It's can split your polygon into convex polygons that can be rendered with fans.
     
    Henry00IS likes this.
  24. ArnePannemans

    ArnePannemans

    Joined:
    Nov 3, 2021
    Posts:
    2
    Thank you so much! didn't understand why there were 1/50 of my roofs of my buildings that missed a single triangle
     
  25. scrawk

    scrawk

    Joined:
    Nov 22, 2012
    Posts:
    804