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
contains(LoopBlinnLocalTriangulator::Vertex * v)41 bool LoopBlinnLocalTriangulator::Triangle::contains(LoopBlinnLocalTriangulator::Vertex* v)
42 {
43 return indexForVertex(v) >= 0;
44 }
45
nextVertex(LoopBlinnLocalTriangulator::Vertex * current,bool traverseCounterClockwise)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
indexForVertex(LoopBlinnLocalTriangulator::Vertex * vertex)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
makeCounterClockwise()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
LoopBlinnLocalTriangulator()83 LoopBlinnLocalTriangulator::LoopBlinnLocalTriangulator()
84 {
85 reset();
86 }
87
reset()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
triangulate(InsideEdgeComputation computeInsideEdges,LoopBlinnConstants::FillSide sideToFill)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
triangulateHelper(LoopBlinnConstants::FillSide sideToFill)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
addTriangle(Vertex * v0,Vertex * v1,Vertex * v2)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
addInteriorVertex(Vertex * v)256 void LoopBlinnLocalTriangulator::addInteriorVertex(Vertex* v)
257 {
258 ASSERT(m_numberOfInteriorVertices < 4);
259 m_interiorVertices[m_numberOfInteriorVertices++] = v;
260 v->setMarked(true);
261 }
262
isSharedEdge(Vertex * v0,Vertex * v1)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