code.vuplus.com Git - vuplus_webkit/blob - Source/WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp

   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