1 /* 2 * Copyright (C) 2010 Google Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 17 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 19 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 20 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 21 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26 #include "config.h" 27 28 #if ENABLE(ACCELERATED_2D_CANVAS) 29 30 #include "LoopBlinnLocalTriangulator.h" 31 32 #include "LoopBlinnMathUtils.h" 33 #include <algorithm> 34 35 namespace WebCore { 36 37 using LoopBlinnMathUtils::approxEqual; 38 using LoopBlinnMathUtils::linesIntersect; 39 using LoopBlinnMathUtils::pointInTriangle; 40 41 bool LoopBlinnLocalTriangulator::Triangle::contains(LoopBlinnLocalTriangulator::Vertex* v) 42 { 43 return indexForVertex(v) >= 0; 44 } 45 46 LoopBlinnLocalTriangulator::Vertex* LoopBlinnLocalTriangulator::Triangle::nextVertex(LoopBlinnLocalTriangulator::Vertex* current, bool traverseCounterClockwise) 47 { 48 int index = indexForVertex(current); 49 ASSERT(index >= 0); 50 if (traverseCounterClockwise) 51 ++index; 52 else 53 --index; 54 if (index < 0) 55 index += 3; 56 else 57 index = index % 3; 58 return m_vertices[index]; 59 } 60 61 int LoopBlinnLocalTriangulator::Triangle::indexForVertex(LoopBlinnLocalTriangulator::Vertex* vertex) 62 { 63 for (int i = 0; i < 3; ++i) 64 if (m_vertices[i] == vertex) 65 return i; 66 return -1; 67 } 68 69 void LoopBlinnLocalTriangulator::Triangle::makeCounterClockwise() 70 { 71 // Possibly swaps two vertices so that the triangle's vertices are 72 // always specified in counterclockwise order. This orders the 73 // vertices canonically when walking the interior edges from the 74 // start to the end vertex. 75 FloatPoint3D point0(m_vertices[0]->xyCoordinates()); 76 FloatPoint3D point1(m_vertices[1]->xyCoordinates()); 77 FloatPoint3D point2(m_vertices[2]->xyCoordinates()); 78 FloatPoint3D crossProduct = (point1 - point0).cross(point2 - point0); 79 if (crossProduct.z() < 0) 80 std::swap(m_vertices[1], m_vertices[2]); 81 } 82 83 LoopBlinnLocalTriangulator::LoopBlinnLocalTriangulator() 84 { 85 reset(); 86 } 87 88 void LoopBlinnLocalTriangulator::reset() 89 { 90 m_numberOfTriangles = 0; 91 m_numberOfInteriorVertices = 0; 92 for (int i = 0; i < 4; ++i) { 93 m_interiorVertices[i] = 0; 94 m_vertices[i].resetFlags(); 95 } 96 } 97 98 void LoopBlinnLocalTriangulator::triangulate(InsideEdgeComputation computeInsideEdges, LoopBlinnConstants::FillSide sideToFill) 99 { 100 triangulateHelper(sideToFill); 101 102 if (computeInsideEdges == ComputeInsideEdges) { 103 // We need to compute which vertices describe the path along the 104 // interior portion of the shape, to feed these vertices to the 105 // more general tessellation algorithm. It is possible that we 106 // could determine this directly while producing triangles above. 107 // Here we try to do it generally just by examining the triangles 108 // that have already been produced. We walk around them in a 109 // specific direction determined by which side of the curve is 110 // being filled. We ignore the interior vertex unless it is also 111 // the ending vertex, and skip the edges shared between two 112 // triangles. 113 Vertex* v = &m_vertices[0]; 114 addInteriorVertex(v); 115 int numSteps = 0; 116 while (!v->end() && numSteps < 4) { 117 // Find the next vertex according to the above rules 118 bool gotNext = false; 119 for (int i = 0; i < numberOfTriangles() && !gotNext; ++i) { 120 Triangle* tri = getTriangle(i); 121 if (tri->contains(v)) { 122 Vertex* next = tri->nextVertex(v, sideToFill == LoopBlinnConstants::RightSide); 123 if (!next->marked() && !isSharedEdge(v, next) && (!next->interior() || next->end())) { 124 addInteriorVertex(next); 125 v = next; 126 // Break out of for loop 127 gotNext = true; 128 } 129 } 130 } 131 ++numSteps; 132 } 133 if (!v->end()) { 134 // Something went wrong with the above algorithm; add the last 135 // vertex to the interior vertices anyway. (FIXME: should we 136 // add an assert here and do more extensive testing?) 137 addInteriorVertex(&m_vertices[3]); 138 } 139 } 140 } 141 142 void LoopBlinnLocalTriangulator::triangulateHelper(LoopBlinnConstants::FillSide sideToFill) 143 { 144 reset(); 145 146 m_vertices[3].setEnd(true); 147 148 // First test for degenerate cases. 149 for (int i = 0; i < 4; ++i) { 150 for (int j = i + 1; j < 4; ++j) { 151 if (approxEqual(m_vertices[i].xyCoordinates(), m_vertices[j].xyCoordinates())) { 152 // Two of the vertices are coincident, so we can eliminate at 153 // least one triangle. We might be able to eliminate the other 154 // as well, but this seems sufficient to avoid degenerate 155 // triangulations. 156 int indices[3] = { 0 }; 157 int index = 0; 158 for (int k = 0; k < 4; ++k) 159 if (k != j) 160 indices[index++] = k; 161 addTriangle(&m_vertices[indices[0]], 162 &m_vertices[indices[1]], 163 &m_vertices[indices[2]]); 164 return; 165 } 166 } 167 } 168 169 // See whether any of the points are fully contained in the 170 // triangle defined by the other three. 171 for (int i = 0; i < 4; ++i) { 172 int indices[3] = { 0 }; 173 int index = 0; 174 for (int j = 0; j < 4; ++j) 175 if (i != j) 176 indices[index++] = j; 177 if (pointInTriangle(m_vertices[i].xyCoordinates(), 178 m_vertices[indices[0]].xyCoordinates(), 179 m_vertices[indices[1]].xyCoordinates(), 180 m_vertices[indices[2]].xyCoordinates())) { 181 // Produce three triangles surrounding this interior vertex. 182 for (int j = 0; j < 3; ++j) 183 addTriangle(&m_vertices[indices[j % 3]], 184 &m_vertices[indices[(j + 1) % 3]], 185 &m_vertices[i]); 186 // Mark the interior vertex so we ignore it if trying to trace 187 // the interior edge. 188 m_vertices[i].setInterior(true); 189 return; 190 } 191 } 192 193 // There are only a few permutations of the vertices, ignoring 194 // rotations, which are irrelevant: 195 // 196 // 0--3 0--2 0--3 0--1 0--2 0--1 197 // | | | | | | | | | | | | 198 // | | | | | | | | | | | | 199 // 1--2 1--3 2--1 2--3 3--1 3--2 200 // 201 // Note that three of these are reflections of each other. 202 // Therefore there are only three possible triangulations: 203 // 204 // 0--3 0--2 0--3 205 // |\ | |\ | |\ | 206 // | \| | \| | \| 207 // 1--2 1--3 2--1 208 // 209 // From which we can choose by seeing which of the potential 210 // diagonals intersect. Note that we choose the shortest diagonal 211 // to split the quad. 212 if (linesIntersect(m_vertices[0].xyCoordinates(), 213 m_vertices[2].xyCoordinates(), 214 m_vertices[1].xyCoordinates(), 215 m_vertices[3].xyCoordinates())) { 216 if ((m_vertices[2].xyCoordinates() - m_vertices[0].xyCoordinates()).diagonalLengthSquared() < 217 (m_vertices[3].xyCoordinates() - m_vertices[1].xyCoordinates()).diagonalLengthSquared()) { 218 addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[2]); 219 addTriangle(&m_vertices[0], &m_vertices[2], &m_vertices[3]); 220 } else { 221 addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[3]); 222 addTriangle(&m_vertices[1], &m_vertices[2], &m_vertices[3]); 223 } 224 } else if (linesIntersect(m_vertices[0].xyCoordinates(), 225 m_vertices[3].xyCoordinates(), 226 m_vertices[1].xyCoordinates(), 227 m_vertices[2].xyCoordinates())) { 228 if ((m_vertices[3].xyCoordinates() - m_vertices[0].xyCoordinates()).diagonalLengthSquared() < 229 (m_vertices[2].xyCoordinates() - m_vertices[1].xyCoordinates()).diagonalLengthSquared()) { 230 addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[3]); 231 addTriangle(&m_vertices[0], &m_vertices[3], &m_vertices[2]); 232 } else { 233 addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[2]); 234 addTriangle(&m_vertices[2], &m_vertices[1], &m_vertices[3]); 235 } 236 } else { 237 // Lines (0->1), (2->3) intersect -- or should, modulo numerical 238 // precision issues 239 if ((m_vertices[1].xyCoordinates() - m_vertices[0].xyCoordinates()).diagonalLengthSquared() < 240 (m_vertices[3].xyCoordinates() - m_vertices[2].xyCoordinates()).diagonalLengthSquared()) { 241 addTriangle(&m_vertices[0], &m_vertices[2], &m_vertices[1]); 242 addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[3]); 243 } else { 244 addTriangle(&m_vertices[0], &m_vertices[2], &m_vertices[3]); 245 addTriangle(&m_vertices[3], &m_vertices[2], &m_vertices[1]); 246 } 247 } 248 } 249 250 void LoopBlinnLocalTriangulator::addTriangle(Vertex* v0, Vertex* v1, Vertex* v2) 251 { 252 ASSERT(m_numberOfTriangles < 3); 253 m_triangles[m_numberOfTriangles++].setVertices(v0, v1, v2); 254 } 255 256 void LoopBlinnLocalTriangulator::addInteriorVertex(Vertex* v) 257 { 258 ASSERT(m_numberOfInteriorVertices < 4); 259 m_interiorVertices[m_numberOfInteriorVertices++] = v; 260 v->setMarked(true); 261 } 262 263 bool LoopBlinnLocalTriangulator::isSharedEdge(Vertex* v0, Vertex* v1) 264 { 265 bool haveEdge01 = false; 266 bool haveEdge10 = false; 267 for (int i = 0; i < numberOfTriangles(); ++i) { 268 Triangle* tri = getTriangle(i); 269 if (tri->contains(v0) && tri->nextVertex(v0, true) == v1) 270 haveEdge01 = true; 271 if (tri->contains(v1) && tri->nextVertex(v1, true) == v0) 272 haveEdge10 = true; 273 } 274 return haveEdge01 && haveEdge10; 275 } 276 277 } // namespace WebCore 278 279 #endif 280
