/* * 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. */ #ifndef LoopBlinnLocalTriangulator_h #define LoopBlinnLocalTriangulator_h #include "FloatPoint.h" #include "FloatPoint3D.h" #include "LoopBlinnConstants.h" #include <wtf/Assertions.h> #include <wtf/Noncopyable.h> namespace WebCore { // Performs a localized triangulation of the triangle mesh // corresponding to the four control point vertices of a cubic curve // segment. class LoopBlinnLocalTriangulator { WTF_MAKE_NONCOPYABLE(LoopBlinnLocalTriangulator); public: // The vertices that the triangulator operates upon, containing both // the position information as well as the cubic texture // coordinates. class Vertex { WTF_MAKE_NONCOPYABLE(Vertex); public: Vertex() { resetFlags(); } const FloatPoint& xyCoordinates() const { return m_xyCoordinates; } const FloatPoint3D& klmCoordinates() const { return m_klmCoordinates; } // Sets the position and texture coordinates of the vertex. void set(float x, float y, float k, float l, float m) { m_xyCoordinates.set(x, y); m_klmCoordinates.set(k, l, m); } // Flags for walking from the start vertex to the end vertex. bool end() { return m_end; } void setEnd(bool end) { m_end = end; } bool marked() { return m_marked; } void setMarked(bool marked) { m_marked = marked; } bool interior() { return m_interior; } void setInterior(bool interior) { m_interior = interior; } void resetFlags() { m_end = false; m_marked = false; m_interior = false; } private: // 2D coordinates of the vertex in the plane. FloatPoint m_xyCoordinates; // Cubic texture coordinates for rendering the curve. FloatPoint3D m_klmCoordinates; // Flags for walking from the start vertex to the end vertex. bool m_end; bool m_marked; bool m_interior; }; // The triangles the Triangulator produces. class Triangle { public: Triangle() { m_vertices[0] = 0; m_vertices[1] = 0; m_vertices[2] = 0; } // Gets the vertex at the given index, 0 <= index < 3. Vertex* getVertex(int index) { ASSERT(index >= 0 && index < 3); return m_vertices[index]; } // Returns true if this triangle contains the given vertex (by // identity, not geometrically). bool contains(Vertex* v); // Returns the vertex following the current one in the specified // direction, counterclockwise or clockwise. Vertex* nextVertex(Vertex* current, bool traverseCounterClockwise); // Sets the vertices of this triangle, potentially reordering them // to produce a canonical orientation. void setVertices(Vertex* v0, Vertex* v1, Vertex* v2) { m_vertices[0] = v0; m_vertices[1] = v1; m_vertices[2] = v2; makeCounterClockwise(); } private: // Returns the index [0..2] associated with the given vertex, or // -1 if not found. int indexForVertex(Vertex* vertex); // Reorders the vertices in this triangle to make them // counterclockwise when viewed in the 2D plane, in order to // achieve a canonical ordering. void makeCounterClockwise(); // Note: these are raw pointers because they point to the // m_vertices contained in the surrounding triangulator. Vertex* m_vertices[3]; }; LoopBlinnLocalTriangulator(); // Resets the triangulator's state. After each triangulation and // before the next, call this to re-initialize the internal // vertices' state. void reset(); // Returns a mutable vertex stored in the triangulator. Use this to // set up the vertices before a triangulation. Vertex* getVertex(int index) { ASSERT(index >= 0 && index < 4); return &m_vertices[index]; } enum InsideEdgeComputation { ComputeInsideEdges, DontComputeInsideEdges }; // Once the vertices' contents have been set up, call triangulate() // to recompute the triangles. // // If computeInsideEdges is ComputeInsideEdges, then sideToFill // will be used to determine which side of the cubic curve defined // by the four control points is to be filled. // // The triangulation obeys the following guarantees: // - If the convex hull is a quadrilateral, then the shortest edge // will be chosen for the cut into two triangles. // - If one of the vertices is contained in the triangle spanned // by the other three, three triangles will be produced. void triangulate(InsideEdgeComputation computeInsideEdges, LoopBlinnConstants::FillSide sideToFill); // Number of triangles computed by triangulate(). int numberOfTriangles() const { return m_numberOfTriangles; } // Returns the computed triangle at index, 0 <= index < numberOfTriangles(). Triangle* getTriangle(int index) { ASSERT(index >= 0 && index < m_numberOfTriangles); return &m_triangles[index]; } // Number of vertices facing the inside of the shape, if // ComputeInsideEdges was passed when triangulate() was called. int numberOfInteriorVertices() const { return m_numberOfInteriorVertices; } // Fetches the given interior vertex, 0 <= index < numberOfInteriorVertices(). Vertex* getInteriorVertex(int index) { ASSERT(index >= 0 && index < m_numberOfInteriorVertices); return m_interiorVertices[index]; } private: void triangulateHelper(LoopBlinnConstants::FillSide sideToFill); // Adds a triangle to the triangulation. void addTriangle(Vertex* v0, Vertex* v1, Vertex* v2); // Adds a vertex to the list of interior vertices. void addInteriorVertex(Vertex* v); // Indicates whether the edge between vertex v0 and v1 is shared // between two or more triangles. bool isSharedEdge(Vertex* v0, Vertex* v1); // The vertices being triangulated. Vertex m_vertices[4]; // The vertices corresponding to the edges facing the inside of the // shape, in order from the start vertex to the end vertex. The more // general triangulation algorithm tessellates this interior region. Vertex* m_interiorVertices[4]; // The number of interior vertices that are valid for the current // triangulation. int m_numberOfInteriorVertices; // There can be at most three triangles computed by this local // algorithm, which occurs when one of the vertices is contained in // the triangle spanned by the other three. Most of the time the // algorithm computes two triangles. Triangle m_triangles[3]; int m_numberOfTriangles; }; } // namespace WebCore #endif // LoopBlinnLocalTriangulator_h