Search Unity

  1. Unity 2020.1 has been released.
    Dismiss Notice
  2. We are looking for feedback on the experimental Unity Safe Mode which is aiming to help you resolve compilation errors faster during project startup.
    Dismiss Notice
  3. Good news ✨ We have more Unite Now videos available for you to watch on-demand! Come check them out and ask our experts any questions!
    Dismiss Notice

Triangulation of spline to mesh, questions and results.

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

  1. dchen05

    dchen05

    Joined:
    Aug 28, 2012
    Posts:
    43
    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.

    $unityTri.png

    It also seems the most accurate version of triangulation is "Constrained Delaunay Triangulation", which I have yet to try, but looks pretty good.
    https://code.google.com/p/poly2tri/

    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?

    $mayaQuad.png
     
    JovanD likes this.
  2. Eric5h5

    Eric5h5

    Volunteer Moderator Moderator

    Joined:
    Jul 19, 2006
    Posts:
    32,244
    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.

    --Eric
     
  3. dchen05

    dchen05

    Joined:
    Aug 28, 2012
    Posts:
    43
    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

    obidobi

    Joined:
    May 12, 2013
    Posts:
    2
    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

    dchen05

    Joined:
    Aug 28, 2012
    Posts:
    43
    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

    dchen05

    Joined:
    Aug 28, 2012
    Posts:
    43
    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 http://farseerphysics.codeplex.com/documentation 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

    dchen05

    Joined:
    Aug 28, 2012
    Posts:
    43
    Heyo!

    I found a really good paper on the subject here which has pointed me in the right direction.
    http://www.cs.berkeley.edu/~jrs/papers/2dj.pdf

    $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.
     
  8. meta87

    meta87

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

    dchen05

    Joined:
    Aug 28, 2012
    Posts:
    43
    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 http://en.wikipedia.org/wiki/Ruppert's_algorithm
    Chews 2nd Algorithm http://en.wikipedia.org/wiki/Chew'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 https://code.google.com/p/poly2tri-c/

    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:
    $AETriangulate.png


    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 http://javascript.poly2tri.googlecode.com/hg/index.html

    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)
    $sphereGrid.png

    Then I factor in that point data as steiner points to get this as the final!
    $steinerTriangulate.png
    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

    joshimoo

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

    obidobi

    Joined:
    May 12, 2013
    Posts:
    2
    @dchen05

    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

    made-on-jupiter

    Joined:
    May 19, 2013
    Posts:
    25
    @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
    http://www.youtube.com/watch?v=FMjjVn8B7Vw


    $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:
    http://spokecreator.com/#spoke/steiner point bunny
    (You'll need to run this in Chrome)
     
    Last edited: Jun 10, 2013
  13. dchen05

    dchen05

    Joined:
    Aug 28, 2012
    Posts:
    43
    @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.
    http://wiki.unity3d.com/index.php?title=PolyContainsPoint

    Good luck!
     
  14. EmeralLotus

    EmeralLotus

    Joined:
    Aug 10, 2012
    Posts:
    1,337
    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

    funshark

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

    funshark

    Joined:
    Mar 24, 2009
    Posts:
    225
  17. TheValar

    TheValar

    Joined:
    Nov 12, 2012
    Posts:
    759
    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 -> Triangle.net 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

    jonbro5556

    Joined:
    Jan 1, 2013
    Posts:
    24
    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 triangle.net. Triangle.net 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>>;
    10.  
    11. public class UnityTriangle : MonoBehaviour {
    12.  
    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));
    23.  
    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));
    28.  
    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.         }
    34.  
    35.         solution = new Polygons();
    36.  
    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);
    42.  
    43.         // then need to convert the solution into a mesh that can be displayed
    44.         TriangleNet.Mesh tmesh = new TriangleNet.Mesh ();
    45.  
    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);
    58.  
    59.  
    60.         if(mesh == null){
    61.             GetComponent<MeshFilter>().mesh = mesh = new Mesh();
    62.             mesh.name = "Star Mesh";
    63.             mesh.hideFlags = HideFlags.HideAndDontSave;
    64.         }
    65.         mesh.Clear();
    66.  
    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();
    83.  
    84.     }
    85.    
    86.     void Update () {
    87.         Vector3 lastPoint = Vector3.zero;
    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), Color.red);
    93.                 lastPoint = new Vector3 (point.X, point.Y, 0);
    94.                 hasPoint = true;
    95.             }
    96.             hasPoint = false;
    97.         }
    98.     }
    99. }
    100.  
     
    AShim-3D likes this.
  19. TheValar

    TheValar

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

    check out this discussion http://triangle.codeplex.com/discussions/445376
     
  20. jonbro5556

    jonbro5556

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

    $Bh-O-LbCIAEfHGr.png

    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

    NicolasHognon

    Joined:
    Nov 15, 2010
    Posts:
    31
  22. TheValar

    TheValar

    Joined:
    Nov 12, 2012
    Posts:
    759
    What subset of the Triangle.net 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

    NicolasHognon

    Joined:
    Nov 15, 2010
    Posts:
    31
    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 $Triangle.NET.zip

    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

    TheValar

    Joined:
    Nov 12, 2012
    Posts:
    759
    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

    CoderPro

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

    roryo

    Joined:
    May 21, 2009
    Posts:
    1,404
    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.

    Steiner2.gif
    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:

    SteinerHeart.gif
     
    Last edited: Feb 5, 2019
    logixworx likes this.
  27. logixworx

    logixworx

    Joined:
    Jun 29, 2017
    Posts:
    76
    so awesome :)
     
    roryo likes this.
unityunity