1 /******************************************************************************* 2 * Copyright 2011 See AUTHORS file. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 ******************************************************************************/ 16 17 package com.badlogic.gdx.math; 18 19 import com.badlogic.gdx.utils.FloatArray; 20 import com.badlogic.gdx.utils.IntArray; 21 import com.badlogic.gdx.utils.ShortArray; 22 23 /** A simple implementation of the ear cutting algorithm to triangulate simple polygons without holes. For more information: 24 * <ul> 25 * <li><a href="http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/algorithm2.html">http://cgm.cs.mcgill.ca/~godfried/ 26 * teaching/cg-projects/97/Ian/algorithm2.html</a></li> 27 * <li><a 28 * href="http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf">http://www.geometrictools.com/Documentation 29 * /TriangulationByEarClipping.pdf</a></li> 30 * </ul> 31 * If the input polygon is not simple (self-intersects), there will be output but it is of unspecified quality (garbage in, 32 * garbage out). 33 * @author badlogicgames (at) gmail.com 34 * @author Nicolas Gramlich (optimizations, collinear edge support) 35 * @author Eric Spitz 36 * @author Thomas ten Cate (bugfixes, optimizations) 37 * @author Nathan Sweet (rewrite, return indices, no allocation, optimizations) */ 38 public class EarClippingTriangulator { 39 static private final int CONCAVE = -1; 40 static private final int TANGENTIAL = 0; 41 static private final int CONVEX = 1; 42 43 private final ShortArray indicesArray = new ShortArray(); 44 private short[] indices; 45 private float[] vertices; 46 private int vertexCount; 47 private final IntArray vertexTypes = new IntArray(); 48 private final ShortArray triangles = new ShortArray(); 49 50 /** @see #computeTriangles(float[], int, int) */ 51 public ShortArray computeTriangles (FloatArray vertices) { 52 return computeTriangles(vertices.items, 0, vertices.size); 53 } 54 55 /** @see #computeTriangles(float[], int, int) */ 56 public ShortArray computeTriangles (float[] vertices) { 57 return computeTriangles(vertices, 0, vertices.length); 58 } 59 60 /** Triangulates the given (convex or concave) simple polygon to a list of triangle vertices. 61 * @param vertices pairs describing vertices of the polygon, in either clockwise or counterclockwise order. 62 * @return triples of triangle indices in clockwise order. Note the returned array is reused for later calls to the same 63 * method. */ 64 public ShortArray computeTriangles (float[] vertices, int offset, int count) { 65 this.vertices = vertices; 66 int vertexCount = this.vertexCount = count / 2; 67 int vertexOffset = offset / 2; 68 69 ShortArray indicesArray = this.indicesArray; 70 indicesArray.clear(); 71 indicesArray.ensureCapacity(vertexCount); 72 indicesArray.size = vertexCount; 73 short[] indices = this.indices = indicesArray.items; 74 if (areVerticesClockwise(vertices, offset, count)) { 75 for (short i = 0; i < vertexCount; i++) 76 indices[i] = (short)(vertexOffset + i); 77 } else { 78 for (int i = 0, n = vertexCount - 1; i < vertexCount; i++) 79 indices[i] = (short)(vertexOffset + n - i); // Reversed. 80 } 81 82 IntArray vertexTypes = this.vertexTypes; 83 vertexTypes.clear(); 84 vertexTypes.ensureCapacity(vertexCount); 85 for (int i = 0, n = vertexCount; i < n; ++i) 86 vertexTypes.add(classifyVertex(i)); 87 88 // A polygon with n vertices has a triangulation of n-2 triangles. 89 ShortArray triangles = this.triangles; 90 triangles.clear(); 91 triangles.ensureCapacity(Math.max(0, vertexCount - 2) * 3); 92 triangulate(); 93 return triangles; 94 } 95 96 private void triangulate () { 97 int[] vertexTypes = this.vertexTypes.items; 98 99 while (vertexCount > 3) { 100 int earTipIndex = findEarTip(); 101 cutEarTip(earTipIndex); 102 103 // The type of the two vertices adjacent to the clipped vertex may have changed. 104 int previousIndex = previousIndex(earTipIndex); 105 int nextIndex = earTipIndex == vertexCount ? 0 : earTipIndex; 106 vertexTypes[previousIndex] = classifyVertex(previousIndex); 107 vertexTypes[nextIndex] = classifyVertex(nextIndex); 108 } 109 110 if (vertexCount == 3) { 111 ShortArray triangles = this.triangles; 112 short[] indices = this.indices; 113 triangles.add(indices[0]); 114 triangles.add(indices[1]); 115 triangles.add(indices[2]); 116 } 117 } 118 119 /** @return {@link #CONCAVE}, {@link #TANGENTIAL} or {@link #CONVEX} */ 120 private int classifyVertex (int index) { 121 short[] indices = this.indices; 122 int previous = indices[previousIndex(index)] * 2; 123 int current = indices[index] * 2; 124 int next = indices[nextIndex(index)] * 2; 125 float[] vertices = this.vertices; 126 return computeSpannedAreaSign(vertices[previous], vertices[previous + 1], vertices[current], vertices[current + 1], 127 vertices[next], vertices[next + 1]); 128 } 129 130 private int findEarTip () { 131 int vertexCount = this.vertexCount; 132 for (int i = 0; i < vertexCount; i++) 133 if (isEarTip(i)) return i; 134 135 // Desperate mode: if no vertex is an ear tip, we are dealing with a degenerate polygon (e.g. nearly collinear). 136 // Note that the input was not necessarily degenerate, but we could have made it so by clipping some valid ears. 137 138 // Idea taken from Martin Held, "FIST: Fast industrial-strength triangulation of polygons", Algorithmica (1998), 139 // http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.115.291 140 141 // Return a convex or tangential vertex if one exists. 142 int[] vertexTypes = this.vertexTypes.items; 143 for (int i = 0; i < vertexCount; i++) 144 if (vertexTypes[i] != CONCAVE) return i; 145 return 0; // If all vertices are concave, just return the first one. 146 } 147 148 private boolean isEarTip (int earTipIndex) { 149 int[] vertexTypes = this.vertexTypes.items; 150 if (vertexTypes[earTipIndex] == CONCAVE) return false; 151 152 int previousIndex = previousIndex(earTipIndex); 153 int nextIndex = nextIndex(earTipIndex); 154 short[] indices = this.indices; 155 int p1 = indices[previousIndex] * 2; 156 int p2 = indices[earTipIndex] * 2; 157 int p3 = indices[nextIndex] * 2; 158 float[] vertices = this.vertices; 159 float p1x = vertices[p1], p1y = vertices[p1 + 1]; 160 float p2x = vertices[p2], p2y = vertices[p2 + 1]; 161 float p3x = vertices[p3], p3y = vertices[p3 + 1]; 162 163 // Check if any point is inside the triangle formed by previous, current and next vertices. 164 // Only consider vertices that are not part of this triangle, or else we'll always find one inside. 165 for (int i = nextIndex(nextIndex); i != previousIndex; i = nextIndex(i)) { 166 // Concave vertices can obviously be inside the candidate ear, but so can tangential vertices 167 // if they coincide with one of the triangle's vertices. 168 if (vertexTypes[i] != CONVEX) { 169 int v = indices[i] * 2; 170 float vx = vertices[v]; 171 float vy = vertices[v + 1]; 172 // Because the polygon has clockwise winding order, the area sign will be positive if the point is strictly inside. 173 // It will be 0 on the edge, which we want to include as well. 174 // note: check the edge defined by p1->p3 first since this fails _far_ more then the other 2 checks. 175 if (computeSpannedAreaSign(p3x, p3y, p1x, p1y, vx, vy) >= 0) { 176 if (computeSpannedAreaSign(p1x, p1y, p2x, p2y, vx, vy) >= 0) { 177 if (computeSpannedAreaSign(p2x, p2y, p3x, p3y, vx, vy) >= 0) return false; 178 } 179 } 180 } 181 } 182 return true; 183 } 184 185 private void cutEarTip (int earTipIndex) { 186 short[] indices = this.indices; 187 ShortArray triangles = this.triangles; 188 189 triangles.add(indices[previousIndex(earTipIndex)]); 190 triangles.add(indices[earTipIndex]); 191 triangles.add(indices[nextIndex(earTipIndex)]); 192 193 indicesArray.removeIndex(earTipIndex); 194 vertexTypes.removeIndex(earTipIndex); 195 vertexCount--; 196 } 197 198 private int previousIndex (int index) { 199 return (index == 0 ? vertexCount : index) - 1; 200 } 201 202 private int nextIndex (int index) { 203 return (index + 1) % vertexCount; 204 } 205 206 static private boolean areVerticesClockwise (float[] vertices, int offset, int count) { 207 if (count <= 2) return false; 208 float area = 0, p1x, p1y, p2x, p2y; 209 for (int i = offset, n = offset + count - 3; i < n; i += 2) { 210 p1x = vertices[i]; 211 p1y = vertices[i + 1]; 212 p2x = vertices[i + 2]; 213 p2y = vertices[i + 3]; 214 area += p1x * p2y - p2x * p1y; 215 } 216 p1x = vertices[offset + count - 2]; 217 p1y = vertices[offset + count - 1]; 218 p2x = vertices[offset]; 219 p2y = vertices[offset + 1]; 220 return area + p1x * p2y - p2x * p1y < 0; 221 } 222 223 static private int computeSpannedAreaSign (float p1x, float p1y, float p2x, float p2y, float p3x, float p3y) { 224 float area = p1x * (p3y - p2y); 225 area += p2x * (p1y - p3y); 226 area += p3x * (p2y - p1y); 227 return (int)Math.signum(area); 228 } 229 } 230
