Unity Community


Page 1 of 2 12 LastLast
Results 1 to 20 of 21
  1. Creative Programmer

    Location
    Copenhagen, Denmark
    Posts
    636

    Polygon triangulation code

    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/recipe...ngulation.aspx

    - http://www.codeproject.com/KB/recipe...y_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
    Rune Skovbo Johansen - Creative Programmer at Unity Technologies
    unity3d.com | runevision.com | my blog

  2. Creative Programmer

    Location
    Copenhagen, Denmark
    Posts
    636
    Well, I finally have an algorithm that actually works. I'll clean it up and post it.

    Rune
    Rune Skovbo Johansen - Creative Programmer at Unity Technologies
    unity3d.com | runevision.com | my blog


  3. Location
    Netherlands
    Posts
    381
    That's great. I'm about to start a similar project. Here a link I found earlier: http://www.codesuppository.blogspot.com/

    Uses the ear clipping method, which is nice.

  4. Creative Programmer

    Location
    Copenhagen, Denmark
    Posts
    636
    Sorry for the triple post, but the script is now up here:
    http://www.unifycommunity.com/wiki/i...e=Triangulator

    Rune
    Rune Skovbo Johansen - Creative Programmer at Unity Technologies
    unity3d.com | runevision.com | my blog

  5. Creative Programmer

    Location
    Copenhagen, Denmark
    Posts
    636
    Quote Originally Posted by jcarpay
    That's great. I'm about to start a similar project. Here a link I found earlier: http://www.codesuppository.blogspot.com/

    Uses the ear clipping method, which is nice.
    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
    Rune Skovbo Johansen - Creative Programmer at Unity Technologies
    unity3d.com | runevision.com | my blog


  6. Location
    Netherlands
    Posts
    381
    Quote Originally Posted by runevision
    Sorry for the triple post, but the script is now up here:
    http://www.unifycommunity.com/wiki/i...e=Triangulator

    Rune
    Great stuff, thanks for sharing this!

  7. MH MH is offline

    Posts
    1

    Triangulator in JS

    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. Creative Programmer

    Location
    Copenhagen, Denmark
    Posts
    636

    Re: Triangulator in JS

    Quote Originally Posted by MH
    Do you happen to have a code for Java Script?
    No, I'm afraid not.

    Quote Originally Posted by MH
    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.
    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.

    Quote Originally Posted by MH
    From what I understand the trinagles' corners attach to the vertices in the order they are added. Is this right?!
    I'm not sure what you mean. How the triangels are formed depend on the shape of the polygon.

    Quote Originally Posted by MH
    I desparately need a working JS code, please.
    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
    Rune Skovbo Johansen - Creative Programmer at Unity Technologies
    unity3d.com | runevision.com | my blog


  9. 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. Posts
    220
    This code was very helpful in helping me get a grip on triangulation. Thanks a ton for sharing this.


  11. Location
    Katowice, Poland
    Posts
    1


  12. Posts
    4

    Javascript version of Triangulation Code

    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. Posts
    1
    Quote Originally Posted by MH View Post
    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.
    I managed to convert to code to display the 2D shape in 3D world if that's what you mean.


  14. Posts
    6
    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:  
    1.        return ((aCROSSbp > 0.0) && (bCROSScp > 0.0) && (cCROSSap > 0.0));

    to

    Code:  
    1.        return ((aCROSSbp >= 0.0) && (bCROSScp >= 0.0) && (cCROSSap >= 0.0));

    Cheers and happy coding,

    Triangulator.cs

  15. Volunteer Moderator
    Posts
    23,699
    Quote Originally Posted by Sjiggle View Post
    Adding holes to the ear clipping is not as hard as it seems.
    Actually it is; I've done this and there are a lot of edge cases that aren't immediately obvious.

    --Eric
    SpriteTile: new tile system that works seamlessly with Unity 4.3 sprites
    FlyingText3D: dynamic 3D text with TTF fonts | Vectrosity: fast & easy line drawing
    Nifty utilities! Stitch terrains together - runtime model importing - file browser - fractal landscapes


  16. Posts
    6
    You are right, I am still not done.


  17. 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. Posts
    3
    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. Location
    Midlands yeah!
    Posts
    8
    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
    Portfolio, bio and more : http://speps.fr/
    XInput.NET - to use your XBox 360 controller in Unity, full triggers support + vibration
    LibTess.NET - a pure .NET implementation of the OpenGL GLU tesselator, for triangulating your awesome polygons 90s style


  20. Posts
    1
    Thanks a lot for sharing it, very very useful.

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •