GDX EarClippingTriangulator

EarClippingTriangulator.java

package com.badlogic.gdx;

/**
 * A simple implementation of the ear cutting algorithm to triangulate simple
 * polygons without holes. For more information:
 * <ul>
 * <li><a href=
 * "http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/algorithm2.html">http://cgm.cs.mcgill.ca/~godfried/
 * teaching/cg-projects/97/Ian/algorithm2.html</a></li>
 * <li><a href=
 * "http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf">http://www.geometrictools.com/Documentation
 * /TriangulationByEarClipping.pdf</a></li>
 * </ul>
 * If the input polygon is not simple (self-intersects), there will be output
 * but it is of unspecified quality (garbage in, garbage out).
 * <p>
 * If the polygon vertices are very large or very close together then
 * {@link GeometryUtils#isClockwise(float[], int, int)} may not be able to
 * properly assess the winding (because it uses floats). In that case the
 * vertices should be adjusted, eg by finding the smallest X and Y values and
 * subtracting that from each vertex.
 *
 * @author badlogicgames@gmail.com
 * @author Nicolas Gramlich (optimizations, collinear edge support)
 * @author Eric Spitz
 * @author Thomas ten Cate (bugfixes, optimizations)
 * @author Nathan Sweet (rewrite, return indices, no allocation, optimizations)
 */
public class EarClippingTriangulator {

	static private final int CONCAVE = -1;
	static private final int CONVEX = 1;

	private final ShortArray indicesArray = new ShortArray();
	private short[] indices;
	private float[] vertices;
	private int vertexCount;
	private final IntArray vertexTypes = new IntArray();
	private final ShortArray triangles = new ShortArray();

	/** @see #computeTriangles(float[], int, int) */
	public ShortArray computeTriangles(float[] vertices) {
		return computeTriangles(vertices, 0, vertices.length);
	}

	/**
	 * Triangulates the given (convex or concave) simple polygon to a list of
	 * triangle vertices.
	 *
	 * @param vertices pairs describing vertices of the polygon, in either clockwise
	 *                 or counterclockwise order.
	 * @return triples of triangle indices in clockwise order. Note the returned
	 *         array is reused for later calls to the same method.
	 */
	public ShortArray computeTriangles(float[] vertices, int offset, int count) {
		this.vertices = vertices;
		int vertexCount = this.vertexCount = count / 2;
		int vertexOffset = offset / 2;

		ShortArray indicesArray = this.indicesArray;
		indicesArray.clear();
		indicesArray.ensureCapacity(vertexCount);
		indicesArray.size = vertexCount;
		short[] indices = this.indices = indicesArray.items;
		if (isClockwise(vertices, offset, count)) {
			for (short i = 0; i < vertexCount; i++) {
				indices[i] = (short) (vertexOffset + i);
			}
		} else {
			for (int i = 0, n = vertexCount - 1; i < vertexCount; i++) {
				indices[i] = (short) (vertexOffset + n - i); // Reversed.
			}
		}

		IntArray vertexTypes = this.vertexTypes;
		vertexTypes.clear();
		vertexTypes.ensureCapacity(vertexCount);
		for (int i = 0, n = vertexCount; i < n; ++i) {
			vertexTypes.add(classifyVertex(i));
		}

		// A polygon with n vertices has a triangulation of n-2 triangles.
		ShortArray triangles = this.triangles;
		triangles.clear();
		triangles.ensureCapacity(Math.max(0, vertexCount - 2) * 3);
		triangulate();
		return triangles;
	}

	private void triangulate() {
		int[] vertexTypes = this.vertexTypes.items;

		while (vertexCount > 3) {
			int earTipIndex = findEarTip();
			cutEarTip(earTipIndex);

			// The type of the two vertices adjacent to the clipped vertex may have changed.
			int previousIndex = previousIndex(earTipIndex);
			int nextIndex = earTipIndex == vertexCount ? 0 : earTipIndex;
			vertexTypes[previousIndex] = classifyVertex(previousIndex);
			vertexTypes[nextIndex] = classifyVertex(nextIndex);
		}

		if (vertexCount == 3) {
			ShortArray triangles = this.triangles;
			short[] indices = this.indices;
			triangles.add(indices[0]);
			triangles.add(indices[1]);
			triangles.add(indices[2]);
		}
	}

	/** @return {@link #CONCAVE} or {@link #CONVEX} */
	private int classifyVertex(int index) {
		short[] indices = this.indices;
		int previous = indices[previousIndex(index)] * 2;
		int current = indices[index] * 2;
		int next = indices[nextIndex(index)] * 2;
		float[] vertices = this.vertices;
		return computeSpannedAreaSign(vertices[previous], vertices[previous + 1], vertices[current],
				vertices[current + 1], vertices[next], vertices[next + 1]);
	}

	private int findEarTip() {
		int vertexCount = this.vertexCount;
		for (int i = 0; i < vertexCount; i++) {
			if (isEarTip(i)) {
				return i;
			}
		}

		// Desperate mode: if no vertex is an ear tip, we are dealing with a degenerate
		// polygon (e.g. nearly collinear).
		// Note that the input was not necessarily degenerate, but we could have made it
		// so by clipping some valid ears.

		// Idea taken from Martin Held, "FIST: Fast industrial-strength triangulation of
		// polygons", Algorithmica (1998),
		// http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.291

		// Return a convex or tangential vertex if one exists.
		int[] vertexTypes = this.vertexTypes.items;
		for (int i = 0; i < vertexCount; i++) {
			if (vertexTypes[i] != CONCAVE) {
				return i;
			}
		}
		return 0; // If all vertices are concave, just return the first one.
	}

	private boolean isEarTip(int earTipIndex) {
		int[] vertexTypes = this.vertexTypes.items;
		if (vertexTypes[earTipIndex] == CONCAVE) {
			return false;
		}

		int previousIndex = previousIndex(earTipIndex);
		int nextIndex = nextIndex(earTipIndex);
		short[] indices = this.indices;
		int p1 = indices[previousIndex] * 2;
		int p2 = indices[earTipIndex] * 2;
		int p3 = indices[nextIndex] * 2;
		float[] vertices = this.vertices;
		float p1x = vertices[p1], p1y = vertices[p1 + 1];
		float p2x = vertices[p2], p2y = vertices[p2 + 1];
		float p3x = vertices[p3], p3y = vertices[p3 + 1];

		// Check if any point is inside the triangle formed by previous, current and
		// next vertices.
		// Only consider vertices that are not part of this triangle, or else we'll
		// always find one inside.
		for (int i = nextIndex(nextIndex); i != previousIndex; i = nextIndex(i)) {
			// Concave vertices can obviously be inside the candidate ear, but so can
			// tangential vertices
			// if they coincide with one of the triangle's vertices.
			if (vertexTypes[i] != CONVEX) {
				int v = indices[i] * 2;
				float vx = vertices[v];
				float vy = vertices[v + 1];
				// Because the polygon has clockwise winding order, the area sign will be
				// positive if the point is strictly inside.
				// It will be 0 on the edge, which we want to include as well.
				// note: check the edge defined by p1->p3 first since this fails _far_ more then
				// the other 2 checks.
				if (computeSpannedAreaSign(p3x, p3y, p1x, p1y, vx, vy) >= 0) {
					if (computeSpannedAreaSign(p1x, p1y, p2x, p2y, vx, vy) >= 0) {
						if (computeSpannedAreaSign(p2x, p2y, p3x, p3y, vx, vy) >= 0) {
							return false;
						}
					}
				}
			}
		}
		return true;
	}

	private void cutEarTip(int earTipIndex) {
		short[] indices = this.indices;
		ShortArray triangles = this.triangles;

		triangles.add(indices[previousIndex(earTipIndex)]);
		triangles.add(indices[earTipIndex]);
		triangles.add(indices[nextIndex(earTipIndex)]);

		indicesArray.removeIndex(earTipIndex);
		vertexTypes.removeIndex(earTipIndex);
		vertexCount--;
	}

	private int previousIndex(int index) {
		return (index == 0 ? vertexCount : index) - 1;
	}

	private int nextIndex(int index) {
		return (index + 1) % vertexCount;
	}

	static private int computeSpannedAreaSign(float p1x, float p1y, float p2x, float p2y, float p3x, float p3y) {
		float area = p1x * (p3y - p2y);
		area += p2x * (p1y - p3y);
		area += p3x * (p2y - p1y);
		return (int) Math.signum(area);
	}

	private static boolean isClockwise(float[] polygon, int offset, int count) {
		if (count <= 2) {
			return false;
		}
		float area = 0;
		int last = offset + count - 2;
		float x1 = polygon[last], y1 = polygon[last + 1];
		for (int i = offset; i <= last; i += 2) {
			float x2 = polygon[i], y2 = polygon[i + 1];
			area += x1 * y2 - x2 * y1;
			x1 = x2;
			y1 = y2;
		}
		return area < 0;
	}
}