Search Unity

  1. Welcome to the Unity Forums! Please take the time to read our Code of Conduct to familiarize yourself with the forum rules and how to post constructively.

Triangulation of spline to mesh, questions and results.

Discussion in 'Scripting' started by dchen05, May 9, 2013.

  1. dchen05


    Aug 28, 2012
    My goal here is to procedurally generate a spline and turn it into a somewhat usable mesh for deforming and animating.

    Many of the packages I have tried use a some kind of triangulation, (Megafiers, GameDraw, UCLA Gamelab)

    With these I've gotten close, but when these meshes are deformed (which will happen a lot when they are animated) there are some really undesirable results due to the arrangement of the triangles. The main problem is how unpredictable they are, with long uninterrupted lines causing problems.


    It also seems the most accurate version of triangulation is "Constrained Delaunay Triangulation", which I have yet to try, but looks pretty good.

    In Maya I get the best results using quads. When I import from Maya it converts the quads to tris and it works well. This may be a dumb question, but is this possible to do this type of quadrangulation procedurally in unity, and if not why?

    JovanD likes this.
  2. Eric5h5


    Volunteer Moderator Moderator

    Jul 19, 2006
    Unity 4 has the ability to use quads in addition to triangles, however quads don't necessarily work properly on all platforms. Or you could work with quads initially, and do a conversion to triangles as the final step.

  3. dchen05


    Aug 28, 2012
    Thanks for the quick response Eric,

    I probably wrote too much. I'm not working in Maya at all, just using it for a reference for the result I'm looking for.

    All geometry in my project needs to be created procedurally from a spline.

    Working in quads initially sounds good, I'm just looking for an algorithm to create them...
    Is there any quadragulation algorithms out there that anyone knows of? Or is Constrained Delaunay Triangulation the cream of the crop for now?
  4. obidobi


    May 12, 2013
    How are the "long uninterrupted lines causing problems" when you use triangles? Problems with texturing or some physics calculations?

    poly2tri has the ability to add something called steiner points. You can add these inside a polygon to get a triangulation with shorter edges. But even when doing this you will get some thin triangles near the polygon edge, hard to get away from that.

    So if you try poly2tri add a grid of points to the polygon and you will get a triangulation that looks like something in your second screenshot.
  5. dchen05


    Aug 28, 2012
    Thanks @obidobi

    The long uninterrupted lines are causing problems with morphing and animation. For example in my image, If I try to move the characters right hand up, it creates very noticeable creases and tears up the right arm, since there aren't more triangles to break it up.

    I should add that the next step to this is using the mesh with as a character with a custom SkinnedMeshRenderer, so the topology of the mesh is important that it is somewhat uniform and predictable.

    Poly2tri is looking like it will do exactly what I want, so I'm looking to convert it to work with Unity now. Thanks for the tip about steiner points, I will look into that!
    KeiTagura likes this.
  6. dchen05


    Aug 28, 2012
    Updates on the progress.

    I found that Poly2Tri library exists in the Farseer Physics Library for Unity.
    It has a few different triangulation algorithms, 2 of which are shown here under "Convex Decomposition"

    CDTDecomposer.cs produces these results. This is somewhat better, because the lines are mainly horizontal, but its still not there.

    $Screen Shot 2013-05-13 at 11.29.49 PM.png

    I also messed around with Maya some more and found that the pictured settings make for a really good result that uses triangles. The 3D delta paramater seems to be important.

    $Screen Shot 2013-05-13 at 11.34.24 PM.png

    About to look into steiner points and dig deeper, I will report back.
  7. dchen05


    Aug 28, 2012

    I found a really good paper on the subject here which has pointed me in the right direction.

    $Screen Shot 2013-05-14 at 1.55.16 PM.png

    It seems that minimum angle is what I'm looking for.
    My mesh currently matches the top right image, which has no minimum angle. I'm currently searching through the Farseer implementation of Poly2Tri to see if minimum angle is built in. I see a few references to it, but nothing working yet.

    I'm somewhat confused if this is something that is built in to the delauny algorithm, or part of an add-on pass and cleanup check once the polygons have been created.

    I'm documenting this because hopefully someone will find it helpful if they are searching for the same thing, there isn't a ton of triangulation talk in the forums.
    richardfu71 likes this.
  8. meta87


    Dec 31, 2012
    I'm finding this very useful/interesting so thanks and keep posting.
  9. dchen05


    Aug 28, 2012
    Thanks @meta87!

    So I know you are all on the edge of your seat for this, so here it goes.

    It turns out, Delaunay Triangulation by itself is a good start, but the link to the research paper I posted before is for Delaunay REFINEMENT algorithms, which take place after the original Delaunay triangulation and are very iterative, going through and cleaning up non ideal triangles and so forth.

    They are kinda fascinating, if you wanna read more.
    Ruppert's Algorithm's_algorithm
    Chews 2nd Algorithm's_second_algorithm

    These are awesome algorithms, but are not included in any of the c# poly2tri implementations out there, and I am also not sure if mobile can hang with them. They were however, added in the C version of poly2tri within the past year, dubbed the Delaunay Terminator

    Another side note, Adobe After Effects puppet tool has a really boss triangulation algorithm.I have no idea but would guess it uses one of these algorithms or something similar. it does take about 5 seconds to work on the desktop, so that made me think its probably a bit overkill for a mobile project.
    After Effects:

    So I scratched that and decided to use steiner points as @obidobi suggested, so now the task was to figure out where to place the steiner points.
    A good visual example of how steiner points work is with this web demo

    I am currently generating a grid of points based on the bounds of the mesh, then I check if they are inside or outside the shape, and delete the ones that are outside.
    This leaves me with this (points being shown with spheres)

    Then I factor in that point data as steiner points to get this as the final!
    Yes, there is room for improvement, but this is good enough for now.

    As someone who spends most of his time in JS, there was a good learning curve here of how to get this all set up and working. At the end of this (after I get further in my project and make sure this battle tested) I will put up a nice happy Poly2Tri repo for Unity that is easy to integrate into projects and can be called with 1 line from C# and JS.
    Last edited: May 16, 2013
  10. joshimoo


    Jun 23, 2011
    Interesting Thread, subscribed.
    Thanks for sharing your findings about triangulation =)
  11. obidobi


    May 12, 2013

    Nice to see your progress!

    As long as the steinerpoints you add are inside the bounding rectangle of the polygon you can do without the point in polygon tests. Edit: After thinking some more I'm not 100% sure :). Might have been a bit to fast to make this statement before trying it out.

    There will be some more work done when the triangulation algorithm runs but triangles outside the polygon will be discarded. So it might be faster to just add the steinerpoints and run the triangulation then checking if they are inside the polygon before adding them.

    Might be worth to test and see which gives the best performance.
    Last edited: May 29, 2013
  12. made-on-jupiter


    May 19, 2013
    @obidobi Thank you for pointing me to this thread.

    We enabled poly2tri Steiner points in our triangulation module today, with success. We had to make sure the points stayed within the polygon contour, and even to make sure they stayed away from the edges a bit.

    In 1080p HD on YouTube

    $Screen Shot 2013-06-10 at 7.50.41 PM.png $Screen Shot 2013-06-10 at 7.50.29 PM.png

    Any tips on techniques to test whether a point is within a polygon boundary?

    Play with the bunny in Spoke Creator: point bunny
    (You'll need to run this in Chrome)
    Last edited: Jun 10, 2013
  13. dchen05


    Aug 28, 2012
    @made on jupiter looks awesome guys!

    Glad this thread was helpful, Spoke Creator definitely looks cool and very ambitious. Thanks for the shout out in the video!

    As far as testing if a point is within a poly, I've been using this, which seems to work very very well.

    Good luck!
  14. EmeralLotus


    Aug 10, 2012
    This thread is really awesome.

    Been wanting to do the same thing but it seems that there are many great minds already at work on this problem.

    Would someone be willing to share working code either on Unity Wiki or here.

    Many Thanks.
  15. funshark


    Mar 24, 2009
    Any news on this? It would be perfect for 2D skinning solutions
  16. funshark


    Mar 24, 2009
  17. TheValar


    Nov 12, 2012
    I've peaked at that library a few times and it looks really awesome. I assume it wouldn't be too much trouble to use in unity for someone who knows what they're doing. I think all it would take is...

    - get rid of specific interface/rendering code that is not helpful for Unity
    - provide interfaces to and from the libraries own Classes i.e. Unity Mesh -> Mesh -> Unity Mesh

    I think it could be applied to mesh destruction as well if you create a Conforming Delaunay mesh -> get voronoi regions -> Triangulate vertices of each voronoi region seperately -> convert meshes of the regions back into Unity Meshes.
  18. jonbro5556


    Jan 1, 2013
    This solution seems totally doable, I have it working on some very simple cases

    $Screen Shot 2014-03-04 at 4.53.25 PM.png

    red line is the output from clipper lib, mesh is from required two code changes to get it to work with mono 2.0. Clipperlib examples on the home page aren't working correctly, but some modification will do it. I am not sure how to put holes in meshes yet, but should be doable (I think).

    here is my code that is producing that image.

    Code (csharp):
    1. using UnityEngine;
    2. using System.Collections.Generic;
    3. using System.Linq;
    4. using System.Text;
    5. using System.IO;
    6. using System.Globalization;
    7. using ClipperLib;
    8. using Polygon = System.Collections.Generic.List<ClipperLib.IntPoint>;
    9. using Polygons = System.Collections.Generic.List<System.Collections.Generic.List<ClipperLib.IntPoint>>;
    11. public class UnityTriangle : MonoBehaviour {
    13.     Mesh mesh;
    14.     private Vector2[] uv;
    15.     private Color32[] cs;
    16.     private Vector3[] vertices;
    17.     Polygons solution;
    18.     Polygons clip = new Polygons(1);
    19.     // Use this for initialization
    20.     void Start () {
    21.         Polygons subj = new Polygons(2);
    22.         subj.Add (new Polygon(4));
    24.         subj[0].Add(new IntPoint(0, 0));
    25.         subj[0].Add(new IntPoint(0, 300)); 
    26.         subj[0].Add(new IntPoint(300, 300));
    27.         subj[0].Add(new IntPoint(300, 0));
    29.         int polyCount = 30;
    30.         clip.Add(new Polygon(polyCount));
    31.         for (int i = 0; i < polyCount; i++) {
    32.             clip[0].Add(new IntPoint(Mathf.Cos((float)i/30.0f*Mathf.PI*2.0f)*100.0f, Mathf.Sin((float)i/30.0f*Mathf.PI*2.0f)*100.0f));
    33.         }
    35.         solution = new Polygons();
    37.         Clipper c = new Clipper();
    38.         c.AddPaths (subj, PolyType.ptSubject, true);
    39.         c.AddPaths (clip, PolyType.ptClip, true);
    40.         c.Execute(ClipType.ctDifference, solution,
    41.             PolyFillType.pftEvenOdd, PolyFillType.pftEvenOdd);
    43.         // then need to convert the solution into a mesh that can be displayed
    44.         TriangleNet.Mesh tmesh = new TriangleNet.Mesh ();
    46.         TriangleNet.Geometry.InputGeometry input = new TriangleNet.Geometry.InputGeometry ();
    47.         int m = 0;
    48.         foreach (Polygon p in solution) {
    49.             foreach(ClipperLib.IntPoint point in p){
    50.                 input.AddPoint (point.X, point.Y);
    51.                 m++;
    52.             }
    53.         }  
    54.         for (int i = 0; i < m; i++) {
    55.             input.AddSegment (i, (i+1)%m);
    56.         }
    57.         tmesh.Triangulate(input);
    60.         if(mesh == null){
    61.             GetComponent<MeshFilter>().mesh = mesh = new Mesh();
    62.    = "Star Mesh";
    63.             mesh.hideFlags = HideFlags.HideAndDontSave;
    64.         }
    65.         mesh.Clear();
    67.         // feel free to waste triangles, I have plenty!
    68.         vertices = new Vector3[tmesh.Vertices.Count()];
    69.         TriangleNet.Data.Vertex[] tVertices = tmesh.Vertices.ToArray ();
    70.         Debug.Log (tmesh.Triangles.Count ());
    71.         int[] tri = new int[tmesh.Triangles.Count()*3];
    72.         for(int i=0;i<vertices.Count();i++){
    73.             vertices[i] = new Vector3((float)tVertices[i].X, (float)tVertices[i].Y, 0);
    74.         }
    75.         for(int i=0;i<tmesh.Triangles.Count();i++){
    76.             tri[0+i*3] = tmesh.Triangles.ElementAt(i).P0;
    77.             tri[1+i*3] = tmesh.Triangles.ElementAt(i).P1;
    78.             tri[2+i*3] = tmesh.Triangles.ElementAt(i).P2;
    79.         }
    80.         mesh.vertices = vertices;
    81.         mesh.triangles = tri;
    82.         mesh.RecalculateNormals();
    84.     }
    86.     void Update () {
    87.         Vector3 lastPoint =;
    88.         bool hasPoint = false;
    89.         foreach (Polygon p in solution) {
    90.             foreach(ClipperLib.IntPoint point in p){
    91.                 if(hasPoint)
    92.                     Debug.DrawLine (lastPoint, new Vector3(point.X, point.Y,0),;
    93.                 lastPoint = new Vector3 (point.X, point.Y, 0);
    94.                 hasPoint = true;
    95.             }
    96.             hasPoint = false;
    97.         }
    98.     }
    99. }
    AShim-3D likes this.
  19. TheValar


    Nov 12, 2012
    I haven't tried this yet but it appears that you can get unity triangles from triangles much easier if you use the "renderData" of the mesh.

    check out this discussion
  20. jonbro5556


    Jan 1, 2013
    ah cool! will give that a shot. Thanks for looking into it.


    I spent some more time bashing against this, and now have it supporting holes in the mesh. I also cleaned it up so it can be called from other systems.

    I want to figure out how to reuse the original clipped poly output as an input to a future clipping. Also I can't figure out how to optimize the output mesh, so they are pretty ugly.
    AShim-3D likes this.
  21. NicolasHognon


    Nov 15, 2010
  22. TheValar


    Nov 12, 2012
    What subset of the source code did you use in order to get everything to compile? I'm having some difficulty figuring out what needs to be stripped from the original package.
  23. NicolasHognon


    Nov 15, 2010
    I replace/comment things until it compile. not so much modification but hard to explain here.
    here is the version I used for my test.
    View attachment $

    at this time I only made a quick and did note use it on a project .. it is just a test to help someone.
  24. TheValar


    Nov 12, 2012
    Sweet thanks! I've got your improvepolygoncollider script working and I've added the ability to uv map the generated mesh based on the extents of the original gameobject. Of course this is assuming that the original object is a Unity Sprite.

    I'm excited to work on it more this weekend!
  25. CoderPro


    Feb 21, 2014
    @TheValar Could you share your script for everyone ? Thanks
  26. roryo


    May 21, 2009
    For those of you interested in node-based parametric modeling in Unity, Archimatix adds Steiner points to the bottom and top caps generated by the Mesher nodes, such as Extrude and PlanSweep nodes, when you increase the subdivision value of the Shape input for their nodes.

    Instead of a grid of points, Archimatix places the Steiner points on concentric shapes based on the Input Shape. This tends to look better than a grid when the result mesh (which is a standard Unity Mesh) is subjected to deformation, either with the Deformer nodes in AX or in Megafiers, etc.

    Capto_Capture 2019-02-05_04-33-25_PM.jpg

    This works with holes as well. Here a heart Shape is ShapeMerged in as a hole:

    Last edited: Feb 5, 2019
    dchen05 and SpindizzyGames like this.
  27. SpindizzyGames


    Jun 29, 2017
    so awesome :)
    roryo likes this.