2 * Copyright (C) 2010 Google Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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.
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.
26 #ifndef LoopBlinnLocalTriangulator_h
27 #define LoopBlinnLocalTriangulator_h
29 #include "FloatPoint.h"
30 #include "FloatPoint3D.h"
31 #include "LoopBlinnConstants.h"
32 #include <wtf/Assertions.h>
33 #include <wtf/Noncopyable.h>
37 // Performs a localized triangulation of the triangle mesh
38 // corresponding to the four control point vertices of a cubic curve
40 class LoopBlinnLocalTriangulator {
41 WTF_MAKE_NONCOPYABLE(LoopBlinnLocalTriangulator);
43 // The vertices that the triangulator operates upon, containing both
44 // the position information as well as the cubic texture
47 WTF_MAKE_NONCOPYABLE(Vertex);
54 const FloatPoint& xyCoordinates() const
56 return m_xyCoordinates;
59 const FloatPoint3D& klmCoordinates() const
61 return m_klmCoordinates;
64 // Sets the position and texture coordinates of the vertex.
65 void set(float x, float y,
66 float k, float l, float m)
68 m_xyCoordinates.set(x, y);
69 m_klmCoordinates.set(k, l, m);
72 // Flags for walking from the start vertex to the end vertex.
88 void setMarked(bool marked)
98 void setInterior(bool interior)
100 m_interior = interior;
111 // 2D coordinates of the vertex in the plane.
112 FloatPoint m_xyCoordinates;
113 // Cubic texture coordinates for rendering the curve.
114 FloatPoint3D m_klmCoordinates;
116 // Flags for walking from the start vertex to the end vertex.
122 // The triangles the Triangulator produces.
132 // Gets the vertex at the given index, 0 <= index < 3.
133 Vertex* getVertex(int index)
135 ASSERT(index >= 0 && index < 3);
136 return m_vertices[index];
139 // Returns true if this triangle contains the given vertex (by
140 // identity, not geometrically).
141 bool contains(Vertex* v);
143 // Returns the vertex following the current one in the specified
144 // direction, counterclockwise or clockwise.
145 Vertex* nextVertex(Vertex* current, bool traverseCounterClockwise);
147 // Sets the vertices of this triangle, potentially reordering them
148 // to produce a canonical orientation.
149 void setVertices(Vertex* v0,
156 makeCounterClockwise();
160 // Returns the index [0..2] associated with the given vertex, or
162 int indexForVertex(Vertex* vertex);
164 // Reorders the vertices in this triangle to make them
165 // counterclockwise when viewed in the 2D plane, in order to
166 // achieve a canonical ordering.
167 void makeCounterClockwise();
169 // Note: these are raw pointers because they point to the
170 // m_vertices contained in the surrounding triangulator.
171 Vertex* m_vertices[3];
174 LoopBlinnLocalTriangulator();
176 // Resets the triangulator's state. After each triangulation and
177 // before the next, call this to re-initialize the internal
181 // Returns a mutable vertex stored in the triangulator. Use this to
182 // set up the vertices before a triangulation.
183 Vertex* getVertex(int index)
185 ASSERT(index >= 0 && index < 4);
186 return &m_vertices[index];
189 enum InsideEdgeComputation {
191 DontComputeInsideEdges
194 // Once the vertices' contents have been set up, call triangulate()
195 // to recompute the triangles.
197 // If computeInsideEdges is ComputeInsideEdges, then sideToFill
198 // will be used to determine which side of the cubic curve defined
199 // by the four control points is to be filled.
201 // The triangulation obeys the following guarantees:
202 // - If the convex hull is a quadrilateral, then the shortest edge
203 // will be chosen for the cut into two triangles.
204 // - If one of the vertices is contained in the triangle spanned
205 // by the other three, three triangles will be produced.
206 void triangulate(InsideEdgeComputation computeInsideEdges,
207 LoopBlinnConstants::FillSide sideToFill);
209 // Number of triangles computed by triangulate().
210 int numberOfTriangles() const
212 return m_numberOfTriangles;
215 // Returns the computed triangle at index, 0 <= index < numberOfTriangles().
216 Triangle* getTriangle(int index)
218 ASSERT(index >= 0 && index < m_numberOfTriangles);
219 return &m_triangles[index];
222 // Number of vertices facing the inside of the shape, if
223 // ComputeInsideEdges was passed when triangulate() was called.
224 int numberOfInteriorVertices() const
226 return m_numberOfInteriorVertices;
229 // Fetches the given interior vertex, 0 <= index < numberOfInteriorVertices().
230 Vertex* getInteriorVertex(int index)
232 ASSERT(index >= 0 && index < m_numberOfInteriorVertices);
233 return m_interiorVertices[index];
237 void triangulateHelper(LoopBlinnConstants::FillSide sideToFill);
239 // Adds a triangle to the triangulation.
240 void addTriangle(Vertex* v0, Vertex* v1, Vertex* v2);
242 // Adds a vertex to the list of interior vertices.
243 void addInteriorVertex(Vertex* v);
245 // Indicates whether the edge between vertex v0 and v1 is shared
246 // between two or more triangles.
247 bool isSharedEdge(Vertex* v0, Vertex* v1);
249 // The vertices being triangulated.
250 Vertex m_vertices[4];
252 // The vertices corresponding to the edges facing the inside of the
253 // shape, in order from the start vertex to the end vertex. The more
254 // general triangulation algorithm tessellates this interior region.
255 Vertex* m_interiorVertices[4];
256 // The number of interior vertices that are valid for the current
258 int m_numberOfInteriorVertices;
260 // There can be at most three triangles computed by this local
261 // algorithm, which occurs when one of the vertices is contained in
262 // the triangle spanned by the other three. Most of the time the
263 // algorithm computes two triangles.
264 Triangle m_triangles[3];
265 int m_numberOfTriangles;
268 } // namespace WebCore
270 #endif // LoopBlinnLocalTriangulator_h