Triangulation of spline to mesh, questions and results.

[dchen05]

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.

GitHub - greenm01/poly2tri: Automatically exported from...

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?

[Eric5h5]

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

[dchen05]

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?

[obidobi]

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.

[dchen05]

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!

[dchen05]

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.

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.

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

[dchen05]

Heyo!

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

2dj.pdf

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.

[meta87]

I’m finding this very useful/interesting so thanks and keep posting.

[dchen05]

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 Delaunay refinement - Wikipedia
Chews 2nd Algorithm Delaunay refinement - Wikipedia

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 Google Code Archive - Long-term storage for Google Code Project Hosting.

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 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)

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.

[joshimoo]

Interesting Thread, subscribed.
Thanks for sharing your findings about triangulation =)

[obidobi]

@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.

[made-on-jupiter]

@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.

triangulation tribulations

In 1080p HD on YouTube

triangulation tribulations

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%20point%20bunny
(You’ll need to run this in Chrome)

[dchen05]

@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!

[EmeralLotus]

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.

[funshark]

Any news on this? It would be perfect for 2D skinning solutions

[funshark]

I found some interesting stuff if you’re still interested

https://triangle.codeplex.com/ << this is a C# port of the triangle library ( Triangle: A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator )

I assume you can obtain things like in After effect with this : Triangle: Quality meshing

[TheValar]

@funshark

I found some interesting stuff if you’re still interested

https://triangle.codeplex.com/ << this is a C# port of the triangle library ( http://www.cs.cmu.edu/~quake/triangle.html )

I assume you can obtain things like in After effect with this : http://www.cs.cmu.edu/~quake/triangle.quality.html

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.

[jonbro5556]

@TheValar

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.

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

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.

using UnityEngine;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Globalization;
using ClipperLib;
using Polygon = System.Collections.Generic.List<ClipperLib.IntPoint>;
using Polygons = System.Collections.Generic.List<System.Collections.Generic.List<ClipperLib.IntPoint>>;

public class UnityTriangle : MonoBehaviour {

	Mesh mesh;
	private Vector2[] uv;
	private Color32[] cs;
	private Vector3[] vertices;
	Polygons solution;
	Polygons clip = new Polygons(1);
	// Use this for initialization
	void Start () {
		Polygons subj = new Polygons(2);
		subj.Add (new Polygon(4));

		subj[0].Add(new IntPoint(0, 0));
		subj[0].Add(new IntPoint(0, 300));	
		subj[0].Add(new IntPoint(300, 300));
		subj[0].Add(new IntPoint(300, 0));

		int polyCount = 30;
		clip.Add(new Polygon(polyCount));
		for (int i = 0; i < polyCount; i++) {
			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));
		}

		solution = new Polygons();

		Clipper c = new Clipper();
		c.AddPaths (subj, PolyType.ptSubject, true);
		c.AddPaths (clip, PolyType.ptClip, true);
		c.Execute(ClipType.ctDifference, solution, 
			PolyFillType.pftEvenOdd, PolyFillType.pftEvenOdd);

		// then need to convert the solution into a mesh that can be displayed
		TriangleNet.Mesh tmesh = new TriangleNet.Mesh ();

		TriangleNet.Geometry.InputGeometry input = new TriangleNet.Geometry.InputGeometry ();
		int m = 0;
		foreach (Polygon p in solution) {
			foreach(ClipperLib.IntPoint point in p){
				input.AddPoint (point.X, point.Y);
				m++;
			}
		}	
		for (int i = 0; i < m; i++) {
			input.AddSegment (i, (i+1)%m);
		}
		tmesh.Triangulate(input);


		if(mesh == null){
			GetComponent<MeshFilter>().mesh = mesh = new Mesh();
			mesh.name = "Star Mesh";
			mesh.hideFlags = HideFlags.HideAndDontSave;
		}
		mesh.Clear();

		// feel free to waste triangles, I have plenty!
		vertices = new Vector3[tmesh.Vertices.Count()];
		TriangleNet.Data.Vertex[] tVertices = tmesh.Vertices.ToArray ();
		Debug.Log (tmesh.Triangles.Count ());
		int[] tri = new int[tmesh.Triangles.Count()*3];
		for(int i=0;i<vertices.Count();i++){
			vertices[i] = new Vector3((float)tVertices[i].X, (float)tVertices[i].Y, 0);
		}
		for(int i=0;i<tmesh.Triangles.Count();i++){
			tri[0+i*3] = tmesh.Triangles.ElementAt(i).P0;
			tri[1+i*3] = tmesh.Triangles.ElementAt(i).P1;
			tri[2+i*3] = tmesh.Triangles.ElementAt(i).P2;
		}
		mesh.vertices = vertices;
		mesh.triangles = tri;
		mesh.RecalculateNormals();

	}
	
	void Update () {
		Vector3 lastPoint = Vector3.zero;
		bool hasPoint = false;
		foreach (Polygon p in solution) {
			foreach(ClipperLib.IntPoint point in p){
				if(hasPoint)
					Debug.DrawLine (lastPoint, new Vector3(point.X, point.Y,0), Color.red);
				lastPoint = new Vector3 (point.X, point.Y, 0);
				hasPoint = true;
			}
			hasPoint = false;
		}
	}
}

[TheValar]

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

[jonbro5556]

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.