diff options
Diffstat (limited to 'WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp')
| -rw-r--r-- | WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp | 275 |
1 files changed, 275 insertions, 0 deletions
diff --git a/WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp b/WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp new file mode 100644 index 0000000..3b73ff6 --- /dev/null +++ b/WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp @@ -0,0 +1,275 @@ +/* + * Copyright (C) 2010 Google Inc. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "config.h" + +#include "LoopBlinnLocalTriangulator.h" + +#include "LoopBlinnMathUtils.h" +#include <algorithm> + +namespace WebCore { + +using LoopBlinnMathUtils::approxEqual; +using LoopBlinnMathUtils::linesIntersect; +using LoopBlinnMathUtils::pointInTriangle; + +bool LoopBlinnLocalTriangulator::Triangle::contains(LoopBlinnLocalTriangulator::Vertex* v) +{ + return indexForVertex(v) >= 0; +} + +LoopBlinnLocalTriangulator::Vertex* LoopBlinnLocalTriangulator::Triangle::nextVertex(LoopBlinnLocalTriangulator::Vertex* current, bool traverseCounterClockwise) +{ + int index = indexForVertex(current); + ASSERT(index >= 0); + if (traverseCounterClockwise) + ++index; + else + --index; + if (index < 0) + index += 3; + else + index = index % 3; + return m_vertices[index]; +} + +int LoopBlinnLocalTriangulator::Triangle::indexForVertex(LoopBlinnLocalTriangulator::Vertex* vertex) +{ + for (int i = 0; i < 3; ++i) + if (m_vertices[i] == vertex) + return i; + return -1; +} + +void LoopBlinnLocalTriangulator::Triangle::makeCounterClockwise() +{ + // Possibly swaps two vertices so that the triangle's vertices are + // always specified in counterclockwise order. This orders the + // vertices canonically when walking the interior edges from the + // start to the end vertex. + FloatPoint3D point0(m_vertices[0]->xyCoordinates()); + FloatPoint3D point1(m_vertices[1]->xyCoordinates()); + FloatPoint3D point2(m_vertices[2]->xyCoordinates()); + FloatPoint3D crossProduct = (point1 - point0).cross(point2 - point0); + if (crossProduct.z() < 0) + std::swap(m_vertices[1], m_vertices[2]); +} + +LoopBlinnLocalTriangulator::LoopBlinnLocalTriangulator() +{ + reset(); +} + +void LoopBlinnLocalTriangulator::reset() +{ + m_numberOfTriangles = 0; + m_numberOfInteriorVertices = 0; + for (int i = 0; i < 4; ++i) { + m_interiorVertices[i] = 0; + m_vertices[i].resetFlags(); + } +} + +void LoopBlinnLocalTriangulator::triangulate(InsideEdgeComputation computeInsideEdges, LoopBlinnConstants::FillSide sideToFill) +{ + triangulateHelper(sideToFill); + + if (computeInsideEdges == ComputeInsideEdges) { + // We need to compute which vertices describe the path along the + // interior portion of the shape, to feed these vertices to the + // more general tessellation algorithm. It is possible that we + // could determine this directly while producing triangles above. + // Here we try to do it generally just by examining the triangles + // that have already been produced. We walk around them in a + // specific direction determined by which side of the curve is + // being filled. We ignore the interior vertex unless it is also + // the ending vertex, and skip the edges shared between two + // triangles. + Vertex* v = &m_vertices[0]; + addInteriorVertex(v); + int numSteps = 0; + while (!v->end() && numSteps < 4) { + // Find the next vertex according to the above rules + bool gotNext = false; + for (int i = 0; i < numberOfTriangles() && !gotNext; ++i) { + Triangle* tri = getTriangle(i); + if (tri->contains(v)) { + Vertex* next = tri->nextVertex(v, sideToFill == LoopBlinnConstants::RightSide); + if (!next->marked() && !isSharedEdge(v, next) && (!next->interior() || next->end())) { + addInteriorVertex(next); + v = next; + // Break out of for loop + gotNext = true; + } + } + } + ++numSteps; + } + if (!v->end()) { + // Something went wrong with the above algorithm; add the last + // vertex to the interior vertices anyway. (FIXME: should we + // add an assert here and do more extensive testing?) + addInteriorVertex(&m_vertices[3]); + } + } +} + +void LoopBlinnLocalTriangulator::triangulateHelper(LoopBlinnConstants::FillSide sideToFill) +{ + reset(); + + m_vertices[3].setEnd(true); + + // First test for degenerate cases. + for (int i = 0; i < 4; ++i) { + for (int j = i + 1; j < 4; ++j) { + if (approxEqual(m_vertices[i].xyCoordinates(), m_vertices[j].xyCoordinates())) { + // Two of the vertices are coincident, so we can eliminate at + // least one triangle. We might be able to eliminate the other + // as well, but this seems sufficient to avoid degenerate + // triangulations. + int indices[3] = { 0 }; + int index = 0; + for (int k = 0; k < 4; ++k) + if (k != j) + indices[index++] = k; + addTriangle(&m_vertices[indices[0]], + &m_vertices[indices[1]], + &m_vertices[indices[2]]); + return; + } + } + } + + // See whether any of the points are fully contained in the + // triangle defined by the other three. + for (int i = 0; i < 4; ++i) { + int indices[3] = { 0 }; + int index = 0; + for (int j = 0; j < 4; ++j) + if (i != j) + indices[index++] = j; + if (pointInTriangle(m_vertices[i].xyCoordinates(), + m_vertices[indices[0]].xyCoordinates(), + m_vertices[indices[1]].xyCoordinates(), + m_vertices[indices[2]].xyCoordinates())) { + // Produce three triangles surrounding this interior vertex. + for (int j = 0; j < 3; ++j) + addTriangle(&m_vertices[indices[j % 3]], + &m_vertices[indices[(j + 1) % 3]], + &m_vertices[i]); + // Mark the interior vertex so we ignore it if trying to trace + // the interior edge. + m_vertices[i].setInterior(true); + return; + } + } + + // There are only a few permutations of the vertices, ignoring + // rotations, which are irrelevant: + // + // 0--3 0--2 0--3 0--1 0--2 0--1 + // | | | | | | | | | | | | + // | | | | | | | | | | | | + // 1--2 1--3 2--1 2--3 3--1 3--2 + // + // Note that three of these are reflections of each other. + // Therefore there are only three possible triangulations: + // + // 0--3 0--2 0--3 + // |\ | |\ | |\ | + // | \| | \| | \| + // 1--2 1--3 2--1 + // + // From which we can choose by seeing which of the potential + // diagonals intersect. Note that we choose the shortest diagonal + // to split the quad. + if (linesIntersect(m_vertices[0].xyCoordinates(), + m_vertices[2].xyCoordinates(), + m_vertices[1].xyCoordinates(), + m_vertices[3].xyCoordinates())) { + if ((m_vertices[2].xyCoordinates() - m_vertices[0].xyCoordinates()).diagonalLengthSquared() < + (m_vertices[3].xyCoordinates() - m_vertices[1].xyCoordinates()).diagonalLengthSquared()) { + addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[2]); + addTriangle(&m_vertices[0], &m_vertices[2], &m_vertices[3]); + } else { + addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[3]); + addTriangle(&m_vertices[1], &m_vertices[2], &m_vertices[3]); + } + } else if (linesIntersect(m_vertices[0].xyCoordinates(), + m_vertices[3].xyCoordinates(), + m_vertices[1].xyCoordinates(), + m_vertices[2].xyCoordinates())) { + if ((m_vertices[3].xyCoordinates() - m_vertices[0].xyCoordinates()).diagonalLengthSquared() < + (m_vertices[2].xyCoordinates() - m_vertices[1].xyCoordinates()).diagonalLengthSquared()) { + addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[3]); + addTriangle(&m_vertices[0], &m_vertices[3], &m_vertices[2]); + } else { + addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[2]); + addTriangle(&m_vertices[2], &m_vertices[1], &m_vertices[3]); + } + } else { + // Lines (0->1), (2->3) intersect -- or should, modulo numerical + // precision issues + if ((m_vertices[1].xyCoordinates() - m_vertices[0].xyCoordinates()).diagonalLengthSquared() < + (m_vertices[3].xyCoordinates() - m_vertices[2].xyCoordinates()).diagonalLengthSquared()) { + addTriangle(&m_vertices[0], &m_vertices[2], &m_vertices[1]); + addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[3]); + } else { + addTriangle(&m_vertices[0], &m_vertices[2], &m_vertices[3]); + addTriangle(&m_vertices[3], &m_vertices[2], &m_vertices[1]); + } + } +} + +void LoopBlinnLocalTriangulator::addTriangle(Vertex* v0, Vertex* v1, Vertex* v2) +{ + ASSERT(m_numberOfTriangles < 3); + m_triangles[m_numberOfTriangles++].setVertices(v0, v1, v2); +} + +void LoopBlinnLocalTriangulator::addInteriorVertex(Vertex* v) +{ + ASSERT(m_numberOfInteriorVertices < 4); + m_interiorVertices[m_numberOfInteriorVertices++] = v; + v->setMarked(true); +} + +bool LoopBlinnLocalTriangulator::isSharedEdge(Vertex* v0, Vertex* v1) +{ + bool haveEdge01 = false; + bool haveEdge10 = false; + for (int i = 0; i < numberOfTriangles(); ++i) { + Triangle* tri = getTriangle(i); + if (tri->contains(v0) && tri->nextVertex(v0, true) == v1) + haveEdge01 = true; + if (tri->contains(v1) && tri->nextVertex(v1, true) == v0) + haveEdge10 = true; + } + return haveEdge01 && haveEdge10; +} + +} // namespace WebCore |