Simple Concave 2D Triangulator for Unity

When making BuildR, I came across the need for a triangulation algorithm. I’ve not really looked into this much in the past apart from playing with Delaunay triangulation on previous projects. Searching Unity and the web there are many resources – but nothing that actually worked for me in my use case.

  • simple polygon – no holes or line intersections
  • concave – so I can’t rely on any convex hull knowledge
  • only in 2D

One of the first stops was the Triangulator on the Unify Wiki. This looked great but it didn’t work for me, I’m not sure why as it seams to work for everyone else. I stumbled upon this article¬†however and got the idea that I could just write my own one from scratch – which I did! Yay.

EarClipper.cs
Vector2z.cs

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class EarClipTriangle
{
	public Vector2z a;
	public Vector2z b;
	public Vector2z c;
	public Rect bounds;
	
	public EarClipTriangle(Vector2z a, Vector2z b, Vector2z c)
	{
		bounds = new Rect(a.x,a.z,0,0);
		Vector2z[] points = new Vector2z[]{a,b,c};
		for(int i=1; i<3; i++)
		{
			if(bounds.xMin < points[i].x)
				bounds.xMin = points[i].x;
			if(bounds.xMax < points[i].x)
				bounds.xMax = points[i].x;
			if(bounds.yMin < points[i].z)
				bounds.yMin = points[i].z;
			if(bounds.yMax < points[i].z)
				bounds.yMax = points[i].z;
		}
	}
}

public class EarClipper 
{

	public static int[] Triangulate( Vector2z[] points)
	{
		int numberOfPoints = points.Length;
		List<int> usePoints = new List<int>();
		for(int p=0; p<numberOfPoints; p++)
			usePoints.Add(p);
		int numberOfUsablePoints = usePoints.Count;
		List<int> indices = new List<int>();
		
        if (numberOfPoints < 3)
            return indices.ToArray();
		
		int it = 100;
		while(numberOfUsablePoints > 3)
		{
			for(int i=0; i<numberOfUsablePoints; i++)
			{
				int a,b,c;
				
				a=usePoints[i];
				
				if(i>=numberOfUsablePoints-1)
					b=usePoints[0];
				else
					b=usePoints[i+1];
				
				if(i>=numberOfUsablePoints-2)
					c=usePoints[(i+2)-numberOfUsablePoints];
				else
					c=usePoints[i+2];
				
				Vector2 pA = points[b].vector2;
				Vector2 pB = points[a].vector2;
				Vector2 pC = points[c].vector2;
				
				float dA = Vector2.Distance(pA,pB);
				float dB = Vector2.Distance(pB,pC);
				float dC = Vector2.Distance(pC,pA);
				
				float angle = Mathf.Acos((Mathf.Pow(dB,2)-Mathf.Pow(dA,2)-Mathf.Pow(dC,2))/(2*dA*dC))*Mathf.Rad2Deg * Mathf.Sign(Sign(points[a],points[b],points[c]));
				if(angle < 0)
				{
					continue;//angle is not reflex
				}
				
				bool freeOfIntersections = true;
				for(int p=0; p<numberOfUsablePoints; p++)
				{
					int pu = usePoints[p];
					if(pu==a || pu==b || pu==c)
						continue;
					
					if(IntersectsTriangle2(points[a],points[b],points[c],points[pu]))
					{
						freeOfIntersections=false;
						break;
					}
				}
				
				if(freeOfIntersections)
				{
					indices.Add(a);
					indices.Add(b);
					indices.Add(c);
					usePoints.Remove(b);
					it=100;
					numberOfUsablePoints = usePoints.Count;
					i--;
					break;
				}
			}
			it--;
			if(it<0)
				break;
		}
		
		indices.Add(usePoints[0]);
		indices.Add(usePoints[1]);
		indices.Add(usePoints[2]);
		indices.Reverse();
		
		return indices.ToArray();
	}
	
	private static bool IntersectsTriangle(Vector2z A, Vector2z B, Vector2z C, Vector2z P)
	{
		bool b1, b2, b3;

		b1 = Sign(P, A, B) < 0.0f;
		b2 = Sign(P, B, C) < 0.0f;
		b3 = Sign(P, C, A) < 0.0f;
		
		return ((b1 == b2) && (b2 == b3));
	}
	
	private static float Sign(Vector2z p1, Vector2z p2, Vector2z p3)
	{
		return (p1.x - p3.x) * (p2.z - p3.z) - (p2.x - p3.x) * (p1.z - p3.z);
	}
					
	private static bool IntersectsTriangle2(Vector2z A, Vector2z B, Vector2z C, Vector2z P)
	{
			float planeAB = (A.x-P.x)*(B.y-P.y)-(B.x-P.x)*(A.y-P.y);
			float planeBC = (B.x-P.x)*(C.y-P.y)-(C.x - P.x)*(B.y-P.y);
			float planeCA = (C.x-P.x)*(A.y-P.y)-(A.x - P.x)*(C.y-P.y);
			return Sign(planeAB)==Sign(planeBC) && Sign(planeBC)==Sign(planeCA);
	}
	
	private static int Sign(float n) 
	{
		return (int)(Mathf.Abs(n)/n);
	}
}

// THIS CODE AND INFORMATION ARE PROVIDED "AS IS" WITHOUT WARRANTY OF ANY 
// KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR A
// PARTICULAR PURPOSE.

Tagged , , , , , , , , , . Bookmark the permalink.

4 Responses to Simple Concave 2D Triangulator for Unity

  1. Ricardo Reis says:

    Hey man, thanks for sharing this.

    Can I use any set of connected vertices with this code?
    I have a list of vertices aligned with an arbitrary plane
    Should my vertices must be aligned with a specific plane (like x-z plane) or not?

  2. Jasper Stocker says:

    The input is 2D so it’s going to be xy or xz.

  3. Andres Ortiz says:

    Thanks for sharing this, Jasper!
    I have to ask, though, I’m getting a bizarre result, and I think it’s because my vertices are in the array in a fairly random order. Should I be sorting the vertices by some particular constraints?

  4. Jasper Stocker says:

    Hi Andres, yes, they need to be in order clockwise (i think).

Leave a Reply