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