diff options
Diffstat (limited to 'o3d/core/cross/gpu2d')
| -rw-r--r-- | o3d/core/cross/gpu2d/cubic_math_utils.cc | 91 | ||||
| -rw-r--r-- | o3d/core/cross/gpu2d/cubic_math_utils.h | 11 | ||||
| -rw-r--r-- | o3d/core/cross/gpu2d/path_cache.cc | 105 | ||||
| -rw-r--r-- | o3d/core/cross/gpu2d/path_cache.h | 120 | ||||
| -rw-r--r-- | o3d/core/cross/gpu2d/path_processor.cc | 1251 | ||||
| -rw-r--r-- | o3d/core/cross/gpu2d/path_processor.h | 126 |
6 files changed, 1704 insertions, 0 deletions
diff --git a/o3d/core/cross/gpu2d/cubic_math_utils.cc b/o3d/core/cross/gpu2d/cubic_math_utils.cc index a62ba3b..023ce6c 100644 --- a/o3d/core/cross/gpu2d/cubic_math_utils.cc +++ b/o3d/core/cross/gpu2d/cubic_math_utils.cc @@ -49,6 +49,59 @@ int Orientation(float x1, float y1, return (cross_product < 0.0f) ? -1 : ((cross_product > 0.0f) ? 1 : 0); } +bool EdgeEdgeTest(float ax, float ay, + float v0x, float v0y, + float u0x, float u0y, + float u1x, float u1y) { + // This edge to edge test is based on Franlin Antonio's gem: "Faster + // Line Segment Intersection", in Graphics Gems III, pp. 199-202. + float bx = u0x - u1x; + float by = u0y - u1y; + float cx = v0x - u0x; + float cy = v0y - u0y; + float f = ay * bx - ax * by; + float d = by * cx - bx * cy; + if ((f > 0 && d >= 0 && d <= f) || (f < 0 && d <= 0 && d >= f)) { + float e = ax * cy - ay * cx; + + // This additional test avoids reporting coincident edges, which + // is the behavior we want. + if (ApproxEqual(e, 0) || ApproxEqual(f, 0) || ApproxEqual(e, f)) { + return false; + } + + if (f > 0) { + return e >= 0 && e <= f; + } else { + return e <= 0 && e >= f; + } + } + return false; +} + +bool EdgeAgainstTriEdges(float v0x, float v0y, + float v1x, float v1y, + float u0x, float u0y, + float u1x, float u1y, + float u2x, float u2y) { + float ax, ay; + ax = v1x - v0x; + ay = v1y - v0y; + // Test edge u0, u1 against v0, v1. + if (EdgeEdgeTest(ax, ay, v0x, v0y, u0x, u0y, u1x, u1y)) { + return true; + } + // Test edge u1, u2 against v0, v1. + if (EdgeEdgeTest(ax, ay, v0x, v0y, u1x, u1y, u2x, u2y)) { + return true; + } + // Test edge u2, u1 against v0, v1. + if (EdgeEdgeTest(ax, ay, v0x, v0y, u2x, u2y, u0x, u0y)) { + return true; + } + return false; +} + } // anonymous namespace bool LinesIntersect(float p1x, float p1y, @@ -91,6 +144,44 @@ bool PointInTriangle(float px, float py, return (u > 0.0f) && (v > 0.0f) && (u + v < 1.0f); } +bool TrianglesOverlap(float a1x, float a1y, + float b1x, float b1y, + float c1x, float c1y, + float a2x, float a2y, + float b2x, float b2y, + float c2x, float c2y) { + // Derived from coplanar_tri_tri() at + // http://jgt.akpeters.com/papers/ShenHengTang03/tri_tri.html , + // simplified for the 2D case and modified so that overlapping edges + // do not report overlapping triangles. + + // Test all edges of triangle 1 against the edges of triangle 2. + if (EdgeAgainstTriEdges(a1x, a1y, b1x, b1y, a2x, a2y, b2x, b2y, c2x, c2y)) + return true; + if (EdgeAgainstTriEdges(b1x, b1y, c1x, c1y, a2x, a2y, b2x, b2y, c2x, c2y)) + return true; + if (EdgeAgainstTriEdges(c1x, c1y, a1x, a1y, a2x, a2y, b2x, b2y, c2x, c2y)) + return true; + // Finally, test if tri1 is totally contained in tri2 or vice versa. + if (PointInTriangle(a1x, a1y, a2x, a2y, b2x, b2y, c2x, c2y)) + return true; + if (PointInTriangle(a2x, a2y, a1x, a1y, b1x, b1y, c1x, c1y)) + return true; + + // Because we define that triangles sharing a vertex or edge don't + // overlap, we must perform additional point-in-triangle tests to + // see whether one triangle is contained in the other. + if (PointInTriangle(b1x, b1y, a2x, a2y, b2x, b2y, c2x, c2y)) + return true; + if (PointInTriangle(c1x, c1y, a2x, a2y, b2x, b2y, c2x, c2y)) + return true; + if (PointInTriangle(b2x, b2y, a1x, a1y, b1x, b1y, c1x, c1y)) + return true; + if (PointInTriangle(c2x, c2y, a1x, a1y, b1x, b1y, c1x, c1y)) + return true; + return false; +} + } // namespace cubic } // namespace gpu2d } // namespace o3d diff --git a/o3d/core/cross/gpu2d/cubic_math_utils.h b/o3d/core/cross/gpu2d/cubic_math_utils.h index 0e03939..1051bb3 100644 --- a/o3d/core/cross/gpu2d/cubic_math_utils.h +++ b/o3d/core/cross/gpu2d/cubic_math_utils.h @@ -96,6 +96,17 @@ bool PointInTriangle(float px, float py, float bx, float by, float cx, float cy); +// Determines whether the triangles defined by the points (a1, b1, c1) +// and (a2, b2, c2) overlap. The definition of this function is that +// if the two triangles only share an adjacent edge or vertex, they +// are not considered to overlap. +bool TrianglesOverlap(float a1x, float a1y, + float b1x, float b1y, + float c1x, float c1y, + float a2x, float a2y, + float b2x, float b2y, + float c2x, float c2y); + } // namespace cubic } // namespace gpu2d } // namespace o3d diff --git a/o3d/core/cross/gpu2d/path_cache.cc b/o3d/core/cross/gpu2d/path_cache.cc new file mode 100644 index 0000000..9dec156 --- /dev/null +++ b/o3d/core/cross/gpu2d/path_cache.cc @@ -0,0 +1,105 @@ +/* + * Copyright 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: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * 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. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 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 THE COPYRIGHT + * OWNER OR 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 "core/cross/gpu2d/path_cache.h" + +namespace o3d { +namespace gpu2d { + +unsigned int PathCache::num_vertices() const { + return vertices_.size() / 2; +} + +const float* PathCache::vertices() const { + if (num_vertices() == 0) + return NULL; + return &vertices_.front(); +} + +const float* PathCache::texcoords() const { + if (num_vertices() == 0) + return NULL; + return &texcoords_.front(); +} + +void PathCache::AddVertex(float x, float y, + float k, float l, float m) { + vertices_.push_back(x); + vertices_.push_back(y); + texcoords_.push_back(k); + texcoords_.push_back(l); + texcoords_.push_back(m); +} + +void PathCache::Clear() { + vertices_.clear(); + texcoords_.clear(); + interior_vertices_.clear(); +#ifdef O3D_CORE_CROSS_GPU2D_PATH_CACHE_DEBUG_INTERIOR_EDGES + interior_edge_vertices_.clear(); +#endif // O3D_CORE_CROSS_GPU2D_PATH_CACHE_DEBUG_INTERIOR_EDGES +} + +unsigned int PathCache::num_interior_vertices() const { + return interior_vertices_.size() / 2; +} + +const float* PathCache::interior_vertices() const { + if (num_interior_vertices() == 0) + return NULL; + return &interior_vertices_.front(); +} + +void PathCache::AddInteriorVertex(float x, float y) { + interior_vertices_.push_back(x); + interior_vertices_.push_back(y); +} + +#ifdef O3D_CORE_CROSS_GPU2D_PATH_CACHE_DEBUG_INTERIOR_EDGES +unsigned int PathCache::num_interior_edge_vertices() const { + return interior_edge_vertices_.size() / 2; +} + +const float* PathCache::interior_edge_vertices() const { + if (num_interior_edge_vertices() == 0) + return NULL; + return &interior_edge_vertices_.front(); +} + +void PathCache::AddInteriorEdgeVertex(float x, float y) { + interior_edge_vertices_.push_back(x); + interior_edge_vertices_.push_back(y); +} +#endif // O3D_CORE_CROSS_GPU2D_PATH_CACHE_DEBUG_INTERIOR_EDGES + +} // namespace gpu2d +} // namespace o3d + diff --git a/o3d/core/cross/gpu2d/path_cache.h b/o3d/core/cross/gpu2d/path_cache.h new file mode 100644 index 0000000..93ba86c0 --- /dev/null +++ b/o3d/core/cross/gpu2d/path_cache.h @@ -0,0 +1,120 @@ +/* + * Copyright 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: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * 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. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 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 THE COPYRIGHT + * OWNER OR 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 O3D_CORE_CROSS_GPU2D_PATH_CACHE_H_ +#define O3D_CORE_CROSS_GPU2D_PATH_CACHE_H_ + +#include <vector> + +#include "base/basictypes.h" + +namespace o3d { +namespace gpu2d { + +// A cache of the processed triangle mesh for a given path. Because +// these might be expensive to allocate (using malloc/free +// internally), it is recommended to try to reuse them when possible. + +// Uncomment the following to obtain debugging information for the edges facing +// the interior region of the mesh. +// #define O3D_CORE_CROSS_GPU2D_PATH_CACHE_DEBUG_INTERIOR_EDGES + +class PathCache { + public: + PathCache() { + } + + // The number of vertices in the mesh. + unsigned int num_vertices() const; + + // Get the base pointer to the vertex information. There are two + // coordinates per vertex. This pointer is valid until the cache is + // cleared or another vertex is added. Returns NULL if there are no + // vertices in the mesh. + const float* vertices() const; + + // Get the base pointer to the texture coordinate information. There + // are three coordinates per vertex. This pointer is valid until the + // cache is cleared or another vertex is added. Returns NULL if + // there are no vertices in the mesh. + const float* texcoords() const; + + // Adds a vertex's information to the cache. The first two arguments + // are the x and y coordinates of the vertex on the plane; the last + // three arguments are the cubic texture coordinates associated with + // this vertex. + void AddVertex(float x, float y, + float k, float l, float m); + + // The number of interior vertices. + unsigned int num_interior_vertices() const; + // Base pointer to the interior vertices; two coordinates per + // vertex, which can be drawn as GL_TRIANGLES. Returns NULL if there + // are no interior vertices in the mesh. + const float* interior_vertices() const; + // Adds an interior vertex to the cache. + void AddInteriorVertex(float x, float y); + + // Clears all of the stored vertex information in this cache. + void Clear(); + +#ifdef O3D_CORE_CROSS_GPU2D_PATH_CACHE_DEBUG_INTERIOR_EDGES + // The number of interior edge vertices + unsigned int num_interior_edge_vertices() const; + // Base pointer to the interior vertices; two coordinates per + // vertex, which can be drawn as GL_LINES. Returns NULL if there are + // no interior edge vertices in the mesh. + const float* interior_edge_vertices() const; + void AddInteriorEdgeVertex(float x, float y); +#endif // O3D_CORE_CROSS_GPU2D_PATH_CACHE_DEBUG_INTERIOR_EDGES + + private: + // The two-dimensional vertices of the triangle mesh. + std::vector<float> vertices_; + + // The three-dimensional cubic texture coordinates. + std::vector<float> texcoords_; + + std::vector<float> interior_vertices_; + +#ifdef O3D_CORE_CROSS_GPU2D_PATH_CACHE_DEBUG_INTERIOR_EDGES + // The following is only for debugging + std::vector<float> interior_edge_vertices_; +#endif // O3D_CORE_CROSS_GPU2D_PATH_CACHE_DEBUG_INTERIOR_EDGES + + DISALLOW_COPY_AND_ASSIGN(PathCache); +}; + +} // namespace gpu2d +} // namespace o3d + +#endif // O3D_CORE_CROSS_GPU2D_PATH_CACHE_H_ + diff --git a/o3d/core/cross/gpu2d/path_processor.cc b/o3d/core/cross/gpu2d/path_processor.cc new file mode 100644 index 0000000..ccc31df --- /dev/null +++ b/o3d/core/cross/gpu2d/path_processor.cc @@ -0,0 +1,1251 @@ +/* + * Copyright 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: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * 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. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 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 THE COPYRIGHT + * OWNER OR 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 "core/cross/gpu2d/path_processor.h" + +#include <algorithm> + +#include "base/logging.h" +#include "core/cross/gpu2d/arena.h" +#include "core/cross/gpu2d/cubic_classifier.h" +#include "core/cross/gpu2d/cubic_math_utils.h" +#include "core/cross/gpu2d/cubic_texture_coords.h" +#include "core/cross/gpu2d/interval_tree.h" +#include "core/cross/gpu2d/local_triangulator.h" +#include "core/cross/gpu2d/path_cache.h" +#include "third_party/skia/include/core/SkGeometry.h" +#include "third_party/skia/include/core/SkPath.h" +#include "third_party/skia/include/core/SkScalar.h" +#include "third_party/glu/internal_glu.h" + +namespace o3d { +namespace gpu2d { + +class Contour; + +//---------------------------------------------------------------------- +// min / max helpers +// + +template <typename T> +T min2(const T& v1, const T& v2) { + return std::min(v1, v2); +} + +template <typename T> +T max2(const T& v1, const T& v2) { + return std::max(v1, v2); +} + +template <typename T> +T min3(const T& v1, const T& v2, const T& v3) { + return min2(min2(v1, v2), v3); +} + +template <typename T> +T max3(const T& v1, const T& v2, const T& v3) { + return max2(max2(v1, v2), v3); +} + +template <typename T> +T min4(const T& v1, const T& v2, const T& v3, const T& v4) { + return min2(min2(v1, v2), min2(v3, v4)); +} + +template <typename T> +T max4(const T& v1, const T& v2, const T& v3, const T& v4) { + return max2(max2(v1, v2), max2(v3, v4)); +} + +//---------------------------------------------------------------------- +// BBox +// + +// Extremely simple bounding box class for Segments. +class BBox { + public: + BBox() + : min_x_(0), + min_y_(0), + max_x_(0), + max_y_(0) { + } + + // Initializes the parameters of the bounding box. + void Setup(float min_x, + float min_y, + float max_x, + float max_y) { + min_x_ = min_x; + min_y_ = min_y; + max_x_ = max_x; + max_y_ = max_y; + } + + // Initializes the bounding box to surround the given triangle. + void Setup(LocalTriangulator::Triangle* triangle) { + Setup(min3(triangle->get_vertex(0)->x(), + triangle->get_vertex(1)->x(), + triangle->get_vertex(2)->x()), + min3(triangle->get_vertex(0)->y(), + triangle->get_vertex(1)->y(), + triangle->get_vertex(2)->y()), + max3(triangle->get_vertex(0)->x(), + triangle->get_vertex(1)->x(), + triangle->get_vertex(2)->x()), + max3(triangle->get_vertex(0)->y(), + triangle->get_vertex(1)->y(), + triangle->get_vertex(2)->y())); + } + + float min_x() const { return min_x_; } + float min_y() const { return min_y_; } + float max_x() const { return max_x_; } + float max_y() const { return max_y_; } + + private: + float min_x_; + float min_y_; + float max_x_; + float max_y_; + DISALLOW_COPY_AND_ASSIGN(BBox); +}; + +//---------------------------------------------------------------------- +// Segment +// + +// Describes a segment of the path: either a cubic or a line segment. +// These are stored in a doubly linked list to speed up curve +// subdivision, which occurs due to either rendering artifacts in the +// loop case or due to overlapping triangles. +class Segment { + public: + // The kind of segment: cubic or line. + enum Kind { + kCubic, + kLine + }; + + // No-argument constructor allows construction by the Arena class. + Segment() + : arena_(NULL), + kind_(kCubic), + prev_(NULL), + next_(NULL), + contour_(NULL), + triangulator_(NULL), + marked_for_subdivision_(false) { + } + + // Initializer for cubic curve segments. + void Setup(Arena* arena, + Contour* contour, + SkPoint cp0, + SkPoint cp1, + SkPoint cp2, + SkPoint cp3) { + arena_ = arena; + contour_ = contour; + kind_ = kCubic; + points_[0] = cp0; + points_[1] = cp1; + points_[2] = cp2; + points_[3] = cp3; + ComputeBoundingBox(); + } + + // Initializer for line segments. + void Setup(Arena* arena, + Contour* contour, + SkPoint p0, + SkPoint p1) { + arena_ = arena; + contour_ = contour; + kind_ = kLine; + points_[0] = p0; + points_[1] = p1; + ComputeBoundingBox(); + } + + // Returns the kind of segment. + Kind kind() const { + return kind_; + } + + // Returns the i'th control point, 0 <= i < 4. + const SkPoint& get_point(int i) { + DCHECK(i >= 0 && i < 4); + return points_[i]; + } + + // Returns the next segment in the contour. + Segment* next() const { return next_; } + + // Returns the previous segment in the contour. + Segment* prev() const { return prev_; } + + // Sets the next segment in the contour. + void set_next(Segment* next) { next_ = next; } + + // Sets the previous segment in the contour. + void set_prev(Segment* prev) { prev_ = prev; } + + // The contour this segment belongs to. + Contour* contour() const { return contour_; } + + // Subdivides the current segment at the given parameter value (0 <= + // t <= 1) and replaces it with the two newly created Segments in + // the linked list, if possible. Returns a pointer to the leftmost + // Segment. + Segment* Subdivide(float param) { + SkPoint dst[7]; + SkChopCubicAt(points_, dst, param); + Segment* left = arena_->Alloc<Segment>(); + Segment* right = arena_->Alloc<Segment>(); + left->Setup(arena_, contour_, dst[0], dst[1], dst[2], dst[3]); + right->Setup(arena_, contour_, dst[3], dst[4], dst[5], dst[6]); + left->set_next(right); + right->set_prev(left); + // Try to set up a link between "this->prev()" and "left". + if (prev() != NULL) { + left->set_prev(prev()); + prev()->set_next(left); + } + // Try to set up a link between "this->next()" and "right". + Segment* n = next(); + if (n != NULL) { + right->set_next(n); + n->set_prev(right); + } + // Set up a link between "this" and "left"; this is only to + // provide a certain amount of continuity during forward iteration. + set_next(left); + return left; + } + + // Subdivides the current segment at the halfway point and replaces + // it with the two newly created Segments in the linked list, if + // possible. Returns a pointer to the leftmost Segment. + Segment* Subdivide() { + return Subdivide(0.5f); + } + + // Returns the bounding box of this segment. + const BBox& bbox() const { + return bbox_; + } + + // Computes the number of times a query line starting at the given + // point and extending to x=+infinity crosses this segment. + int NumCrossingsForXRay(SkPoint pt) const { + if (kind_ == kCubic) { + // Should consider caching the monotonic cubics. + return SkNumXRayCrossingsForCubic(pt, points_); + } else { + return SkXRayCrossesLine(pt, points_) ? 1 : 0; + } + } + + // Performs a local triangulation of the control points in this + // segment. This operation only makes sense for cubic type segments. + void Triangulate(bool compute_inside_edges, + CubicTextureCoords::Result* tex_coords); + + // Returns the number of control point triangles associated with + // this segment. + int num_triangles() const { + if (!triangulator_) + return 0; + return triangulator_->num_triangles(); + } + + // Fetches the given control point triangle for this segment. + LocalTriangulator::Triangle* get_triangle(int index) { + DCHECK(triangulator_); + return triangulator_->get_triangle(index); + } + + // Number of vertices along the inside edge of this segment. This + // can be called either for line or cubic type segments. + int num_interior_vertices() const { + if (kind_ == kCubic) { + if (triangulator_) { + return triangulator_->num_interior_vertices(); + } else { + return 0; + } + } + + return 2; + } + + // Returns the given interior vertex, 0 <= index < num_interior_vertices(). + SkPoint get_interior_vertex(int index) const { + DCHECK(index >= 0 && index < num_interior_vertices()); + if (kind_ == kCubic) { + SkPoint res; + if (triangulator_) { + LocalTriangulator::Vertex* vertex = + triangulator_->get_interior_vertex(index); + if (vertex) + res.set(SkFloatToScalar(vertex->x()), + SkFloatToScalar(vertex->y())); + } + return res; + } + + return points_[index]; + } + + // State to assist with curve subdivision. + bool marked_for_subdivision() { + return marked_for_subdivision_; + } + + // State to assist with curve subdivision. + void set_marked_for_subdivision(bool marked_for_subdivision) { + marked_for_subdivision_ = marked_for_subdivision; + } + + private: + // Computes the bounding box of this Segment. + void ComputeBoundingBox() { + switch (kind_) { + case kCubic: + bbox_.Setup(SkScalarToFloat(min4(points_[0].fX, + points_[1].fX, + points_[2].fX, + points_[3].fX)), + SkScalarToFloat(min4(points_[0].fY, + points_[1].fY, + points_[2].fY, + points_[3].fY)), + SkScalarToFloat(max4(points_[0].fX, + points_[1].fX, + points_[2].fX, + points_[3].fX)), + SkScalarToFloat(max4(points_[0].fY, + points_[1].fY, + points_[2].fY, + points_[3].fY))); + break; + + case kLine: + bbox_.Setup(SkScalarToFloat(min2(points_[0].fX, + points_[1].fX)), + SkScalarToFloat(min2(points_[0].fY, + points_[1].fY)), + SkScalarToFloat(max2(points_[0].fX, + points_[1].fX)), + SkScalarToFloat(max2(points_[0].fY, + points_[1].fY))); + break; + + default: + NOTREACHED(); + break; + } + } + + Arena* arena_; + Kind kind_; + SkPoint points_[4]; + Segment* prev_; + Segment* next_; + Contour* contour_; + BBox bbox_; + LocalTriangulator* triangulator_; + bool marked_for_subdivision_; + + DISALLOW_COPY_AND_ASSIGN(Segment); +}; + +//---------------------------------------------------------------------- +// Contour +// + +// Describes a closed contour of the path. +class Contour { + public: + Contour() { + first_ = &sentinel_; + first_->set_next(first_); + first_->set_prev(first_); + ccw_ = true; + fill_right_side_ = true; + } + + // Adds a segment to this contour. + void Add(Segment* segment) { + if (first_ == &sentinel_) { + // First element is the sentinel. Replace it with the incoming + // segment. + segment->set_next(first_); + segment->set_prev(first_); + first_->set_next(segment); + first_->set_prev(segment); + first_ = segment; + } else { + // first_->prev() is the sentinel. + Segment* sentinel = first_->prev(); + Segment* last = sentinel->prev(); + last->set_next(segment); + segment->set_prev(last); + segment->set_next(sentinel); + sentinel->set_prev(segment); + } + } + + // Subdivides the given segment at the given parametric value. + // Returns a pointer to the first of the two portions of the + // subdivided segment. + Segment* Subdivide(Segment* segment, float param) { + Segment* left = segment->Subdivide(param); + if (first_ == segment) + first_ = left; + return left; + } + + // Subdivides the given segment at the halfway point. Returns a + // pointer to the first of the two portions of the subdivided + // segment. + Segment* Subdivide(Segment* segment) { + Segment* left = segment->Subdivide(); + if (first_ == segment) + first_ = left; + return left; + } + + // Returns the first segment in the contour for iteration. + Segment* begin() const { + return first_; + } + + // Returns the last segment in the contour for iteration. Callers + // should not iterate over this segment. In other words: + // for (Segment* cur = contour->begin(); + // cur != contour->end(); + // cur = cur->next()) { + // // .. process cur ... + // } + Segment* end() const { + return first_->prev(); + } + + // Returns whether this contour is oriented counterclockwise. + bool ccw() const { + return ccw_; + } + + void set_ccw(bool ccw) { + ccw_ = ccw; + } + + // Returns whether the right side of this contour is filled. + bool fill_right_side() const { return fill_right_side_; } + + void set_fill_right_side(bool fill_right_side) { + fill_right_side_ = fill_right_side; + } + + private: + // The start of the segment chain. The segments are kept in a + // circular doubly linked list for rapid access to the beginning and + // end. + Segment* first_; + + // The sentinel element at the end of the chain, needed for + // reasonable iteration semantics. + Segment sentinel_; + + // Whether this contour is oriented counterclockwise. + bool ccw_; + + // Whether we should fill the right (or left) side of this contour. + bool fill_right_side_; + + DISALLOW_COPY_AND_ASSIGN(Contour); +}; + +//---------------------------------------------------------------------- +// Segment +// + +// Definition of Segment::Triangulate(), which must come after +// declaration of Contour. +void Segment::Triangulate(bool compute_inside_edges, + CubicTextureCoords::Result* tex_coords) { + DCHECK(kind_ == kCubic); + if (triangulator_ == NULL) { + triangulator_ = arena_->Alloc<LocalTriangulator>(); + } + triangulator_->Reset(); + for (int i = 0; i < 4; i++) { + LocalTriangulator::Vertex* vertex = triangulator_->get_vertex(i); + if (tex_coords) { + vertex->Set(get_point(i).fX, + get_point(i).fY, + tex_coords->coords[i].getX(), + tex_coords->coords[i].getY(), + tex_coords->coords[i].getZ()); + } else { + vertex->Set(get_point(i).fX, + get_point(i).fY, + // No texture coordinates yet + 0, 0, 0); + } + } + triangulator_->Triangulate(compute_inside_edges, + contour()->fill_right_side()); +} + +//---------------------------------------------------------------------- +// PathProcessor +// + +PathProcessor::PathProcessor() + : arena_(new Arena()), + should_delete_arena_(true), + verbose_logging_(false) { +} + +PathProcessor::PathProcessor(Arena* arena) + : arena_(arena), + should_delete_arena_(false), + verbose_logging_(false) { +} + +PathProcessor::~PathProcessor() { + if (should_delete_arena_) { + delete arena_; + } +} + +void PathProcessor::Process(const SkPath& path, PathCache* cache) { + BuildContours(path); + + // Run plane-sweep algorithm to determine overlaps of control point + // curves and subdivide curves appropriately. + SubdivideCurves(); + + // Determine orientations of countours. Based on orientation and the + // number of curve crossings at a random point on the contour, + // determine whether to fill the left or right side of the contour. + DetermineSidesToFill(); + + // Classify curves, compute texture coordinates and subdivide as + // necessary to eliminate rendering artifacts. Do the final + // triangulation of the curve segments, determining the path along + // the interior of the shape. + for (std::vector<Contour*>::iterator iter = contours_.begin(); + iter != contours_.end(); + iter++) { + Contour* cur = *iter; + for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { + if (seg->kind() == Segment::kCubic) { + CubicClassifier::Result classification = + CubicClassifier::Classify(seg->get_point(0).fX, + seg->get_point(0).fY, + seg->get_point(1).fX, + seg->get_point(1).fY, + seg->get_point(2).fX, + seg->get_point(2).fY, + seg->get_point(3).fX, + seg->get_point(3).fY); + DLOG_IF(INFO, verbose_logging_) << "Classification:" + << classification.curve_type(); + CubicTextureCoords::Result tex_coords; + CubicTextureCoords::Compute(classification, + cur->fill_right_side(), + &tex_coords); + if (tex_coords.has_rendering_artifact) { + // TODO(kbr): split at the subdivision parameter value + cur->Subdivide(seg); + // Next iteration will handle the newly subdivided halves + } else { + if (!tex_coords.is_line_or_point) { + seg->Triangulate(true, &tex_coords); + for (int i = 0; i < seg->num_triangles(); i++) { + LocalTriangulator::Triangle* triangle = + seg->get_triangle(i); + for (int j = 0; j < 3; j++) { + LocalTriangulator::Vertex* vert = + triangle->get_vertex(j); + cache->AddVertex(vert->x(), + vert->y(), + vert->k(), + vert->l(), + vert->m()); + } + } +#ifdef O3D_CORE_CROSS_GPU2D_PATH_CACHE_DEBUG_INTERIOR_EDGES + // Show the end user the interior edges as well + for (int i = 1; i < seg->num_interior_vertices(); i++) { + SkPoint vert = seg->get_interior_vertex(i); + // Duplicate previous vertex to be able to draw GL_LINES + SkPoint prev = seg->get_interior_vertex(i - 1); + cache->AddInteriorEdgeVertex(prev.fX, prev.fY); + cache->AddInteriorEdgeVertex(vert.fX, vert.fY); + } +#endif // O3D_CORE_CROSS_GPU2D_PATH_CACHE_DEBUG_INTERIOR_EDGES + } + } + } + } + } + + // Run the interior paths through a tessellation algorithm + // supporting multiple contours. + TessellateInterior(cache); +} + +void PathProcessor::BuildContours(const SkPath& path) { + // Clear out the contours + contours_.clear(); + SkPath::Iter iter(path, false); + SkPoint pts[4]; + SkPath::Verb verb; + Contour* contour = NULL; + SkPoint cur_pt; + SkPoint move_to_pt; + do { + verb = iter.next(pts); + if (verb != SkPath::kMove_Verb) { + if (contour == NULL) { + contour = arena_->Alloc<Contour>(); + contours_.push_back(contour); + } + } + switch (verb) { + case SkPath::kMove_Verb: { + contour = arena_->Alloc<Contour>(); + contours_.push_back(contour); + cur_pt = pts[0]; + move_to_pt = pts[0]; + DLOG_IF(INFO, verbose_logging_) << "MoveTo (" << pts[0].fX + << ", " << pts[0].fY << ")"; + break; + } + case SkPath::kLine_Verb: { + Segment* segment = arena_->Alloc<Segment>(); + if (iter.isCloseLine()) { + segment->Setup(arena_, contour, cur_pt, pts[1]); + DLOG_IF(INFO, verbose_logging_) << "CloseLineTo (" << cur_pt.fX + << ", " << cur_pt.fY + << "), (" << pts[1].fX + << ", " << pts[1].fY << ")"; + contour->Add(segment); + contour = NULL; + } else { + segment->Setup(arena_, contour, pts[0], pts[1]); + DLOG_IF(INFO, verbose_logging_) << "LineTo (" << pts[0].fX + << ", " << pts[0].fY + << "), (" << pts[1].fX + << ", " << pts[1].fY << ")"; + contour->Add(segment); + cur_pt = pts[1]; + } + break; + } + case SkPath::kQuad_Verb: { + // Need to degree elevate the quadratic into a cubic + SkPoint cubic[4]; + SkConvertQuadToCubic(pts, cubic); + Segment* segment = arena_->Alloc<Segment>(); + segment->Setup(arena_, contour, + cubic[0], cubic[1], cubic[2], cubic[3]); + DLOG_IF(INFO, verbose_logging_) << "Quad->CubicTo (" << cubic[0].fX + << ", " << cubic[0].fY + << "), (" << cubic[1].fX + << ", " << cubic[1].fY + << "), (" << cubic[2].fX + << ", " << cubic[2].fY + << "), (" << cubic[3].fX + << ", " << cubic[3].fY << ")"; + contour->Add(segment); + cur_pt = cubic[3]; + break; + } + case SkPath::kCubic_Verb: { + Segment* segment = arena_->Alloc<Segment>(); + segment->Setup(arena_, contour, pts[0], pts[1], pts[2], pts[3]); + DLOG_IF(INFO, verbose_logging_) << "CubicTo (" << pts[0].fX + << ", " << pts[0].fY + << "), (" << pts[1].fX + << ", " << pts[1].fY + << "), (" << pts[2].fX + << ", " << pts[2].fY + << "), (" << pts[3].fX + << ", " << pts[3].fY << ")"; + contour->Add(segment); + cur_pt = pts[3]; + break; + } + case SkPath::kClose_Verb: { + Segment* segment = arena_->Alloc<Segment>(); + segment->Setup(arena_, contour, cur_pt, move_to_pt); + DLOG_IF(INFO, verbose_logging_) << "Close (" << cur_pt.fX + << ", " << cur_pt.fY + << ") -> (" << move_to_pt.fX + << ", " << move_to_pt.fY << ")"; + contour->Add(segment); + contour = NULL; + } + default: + break; + } + } while (verb != SkPath::kDone_Verb); +} + +std::vector<Segment*> PathProcessor::AllSegmentsOverlappingY(float y) { + std::vector<Segment*> res; + for (std::vector<Contour*>::iterator iter = contours_.begin(); + iter != contours_.end(); + iter++) { + Contour* cur = *iter; + for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { + const BBox& bbox = seg->bbox(); + if (bbox.min_y() <= y && y <= bbox.max_y()) { + res.push_back(seg); + } + } + } + return res; +} + +// Uncomment this to debug the orientation computation +// #define O3D_CORE_CROSS_GPU2D_PATH_PROCESSOR_DEBUG_ORIENTATION + +void PathProcessor::DetermineSidesToFill() { + // Loop and Blinn's algorithm can only easily emulate the even/odd + // fill rule, and only for non-intersecting curves. We can determine + // which side of each curve segment to fill based on its + // clockwise/counterclockwise orientation and how many other + // contours surround it. + + // To optimize the query of all curve segments intersecting a + // horizontal line going to x=+infinity, we build up an interval + // tree whose keys are the y extents of the segments. + IntervalTree<float, Segment*> tree(arena_); + typedef IntervalTree<float, Segment*>::IntervalType IntervalType; + + for (std::vector<Contour*>::iterator iter = contours_.begin(); + iter != contours_.end(); + iter++) { + Contour* cur = *iter; + DetermineOrientation(cur); + for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { + const BBox& bbox = seg->bbox(); + tree.Insert(tree.MakeInterval(bbox.min_y(), bbox.max_y(), seg)); + } + } + + // Now iterate through the contours and pick a random segment (in + // this case we use the first) and a random point on that segment. + // Find all segments from other contours which intersect this one + // and count the number of crossings a horizontal line to + // x=+infinity makes with those contours. This combined with the + // orientation of the curve tells us which side to fill -- again, + // assuming an even/odd fill rule, which is all we can easily + // handle. + for (std::vector<Contour*>::iterator iter = contours_.begin(); + iter != contours_.end(); + iter++) { + Contour* cur = *iter; + Segment* seg = cur->begin(); + + int num_crossings = 0; + + // We use a zero-sized vertical interval for the query + std::vector<IntervalType> overlaps = + tree.AllOverlaps(IntervalType(SkScalarToFloat(seg->get_point(0).fY), + SkScalarToFloat(seg->get_point(0).fY), + NULL)); +#if !defined(O3D_CORE_CROSS_GPU2D_PATH_PROCESSOR_DEBUG_ORIENTATION) + for (std::vector<IntervalType>::iterator iter = overlaps.begin(); + iter != overlaps.end(); + iter++) { + const IntervalType& interval = *iter; + Segment* query_seg = interval.data(); + // Ignore segments coming from the same contour + if (query_seg->contour() != cur) { + num_crossings += query_seg->NumCrossingsForXRay(seg->get_point(0)); + } + } +#endif // !defined(O3D_CORE_CROSS_GPU2D_PATH_PROCESSOR_DEBUG_ORIENTATION) + +#ifdef O3D_CORE_CROSS_GPU2D_PATH_PROCESSOR_DEBUG_ORIENTATION + // For debugging + std::vector<Segment*> slow_overlaps = + AllSegmentsOverlappingY(seg->get_point(0).fY); + DCHECK(overlaps.size() == slow_overlaps.size()); + for (std::vector<Segment*>::iterator iter = slow_overlaps.begin(); + iter != slow_overlaps.end(); + iter++) { + Segment* query_seg = *iter; + // Ignore segments coming from the same contour + if (query_seg->contour() != cur) { + num_crossings += query_seg->NumCrossingsForXRay(seg->get_point(0)); + } + } +#endif // O3D_CORE_CROSS_GPU2D_PATH_PROCESSOR_DEBUG_ORIENTATION + + if (cur->ccw()) { + if (num_crossings & 1) { + cur->set_fill_right_side(true); + } else { + cur->set_fill_right_side(false); + } + } else { + if (num_crossings & 1) { + cur->set_fill_right_side(false); + } else { + cur->set_fill_right_side(true); + } + } + } +} + +void PathProcessor::DetermineOrientation(Contour* contour) { + // Determine signed area of the polygon represented by the points + // along the segments. Consider this an approximation to the true + // orientation of the polygon; it probably won't handle + // self-intersecting curves correctly. + // + // There is also a pretty basic assumption here that the contour is + // closed. + float signed_area = 0; + for (Segment* seg = contour->begin(); + seg != contour->end(); + seg = seg->next()) { + int limit = (seg->kind() == Segment::kCubic) ? 4 : 2; + for (int i = 1; i < limit; i++) { + const SkPoint& prev_point = seg->get_point(i - 1); + const SkPoint& point = seg->get_point(i); + float cur_area = prev_point.fX * point.fY - prev_point.fY * point.fX; + DLOG_IF(INFO, verbose_logging_) << "Adding to signed area (" + << prev_point.fX << ", " + << prev_point.fY << ") -> (" + << point.fX << ", " + << point.fY << ") = " + << cur_area; + signed_area += cur_area; + } + } + + if (signed_area > 0) + contour->set_ccw(true); + else + contour->set_ccw(false); +} + +//---------------------------------------------------------------------- +// Classes and typedefs needed for curve subdivision. +// Unfortunately it appears we can't scope these within the +// SubdivideCurves() method itself, because templates then fail to +// instantiate. + +// The user data which is placed in the IntervalTree. +struct SweepData { + SweepData() + : triangle(NULL), + segment(NULL) { + } + + // The triangle this interval is associated with + LocalTriangulator::Triangle* triangle; + // The segment the triangle is associated with + Segment* segment; +}; + +typedef IntervalTree<float, SweepData*> SweepTree; +typedef SweepTree::IntervalType SweepInterval; + +// The entry / exit events which occur at the minimum and maximum x +// coordinates of the control point triangles' bounding boxes. +// +// Note that this class requires its copy constructor and assignment +// operator since it needs to be stored in a std::vector. +class SweepEvent { + public: + SweepEvent() + : x_(0), + entry_(false), + interval_(0, 0, NULL) { + } + + // Initializes the SweepEvent. + void Setup(float x, bool entry, SweepInterval interval) { + x_ = x; + entry_ = entry; + interval_ = interval; + } + + float x() const { return x_; } + bool entry() const { return entry_; } + const SweepInterval& interval() const { return interval_; } + + bool operator<(const SweepEvent& other) const { + return x_ < other.x_; + } + + private: + float x_; + bool entry_; + SweepInterval interval_; +}; + +namespace { + +bool TrianglesOverlap(LocalTriangulator::Triangle* t0, + LocalTriangulator::Triangle* t1) { + LocalTriangulator::Vertex* t0v0 = t0->get_vertex(0); + LocalTriangulator::Vertex* t0v1 = t0->get_vertex(1); + LocalTriangulator::Vertex* t0v2 = t0->get_vertex(2); + LocalTriangulator::Vertex* t1v0 = t1->get_vertex(0); + LocalTriangulator::Vertex* t1v1 = t1->get_vertex(1); + LocalTriangulator::Vertex* t1v2 = t1->get_vertex(2); + return cubic::TrianglesOverlap(t0v0->x(), t0v0->y(), + t0v1->x(), t0v1->y(), + t0v2->x(), t0v2->y(), + t1v0->x(), t1v0->y(), + t1v1->x(), t1v1->y(), + t1v2->x(), t1v2->y()); +} + +} // anonymous namespace + +void PathProcessor::SubdivideCurves() { + // We need to determine all overlaps of all control point triangles + // (from different segments, not the same segment) and, if any + // exist, subdivide the associated curves. + // + // The plane-sweep algorithm determines all overlaps of a set of + // rectangles in the 2D plane. Our problem maps very well to this + // algorithm and significantly reduces the complexity compared to a + // naive implementation. + // + // Each bounding box of a control point triangle is converted into + // an "entry" event at its smallest X coordinate and an "exit" event + // at its largest X coordinate. Each event has an associated + // one-dimensional interval representing the Y span of the bounding + // box. We sort these events by increasing X coordinate. We then + // iterate through them. For each entry event we add the interval to + // a side interval tree, and query this tree for overlapping + // intervals. Any overlapping interval corresponds to an overlapping + // bounding box. For each exit event we remove the associated + // interval from the interval tree. + + std::vector<Segment*> cur_segments; + std::vector<Segment*> next_segments; + + // Start things off by considering all of the segments + for (std::vector<Contour*>::iterator iter = contours_.begin(); + iter != contours_.end(); + iter++) { + Contour* cur = *iter; + for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { + if (seg->kind() == Segment::kCubic) { + seg->Triangulate(false, NULL); + cur_segments.push_back(seg); + } + } + } + + // Subdivide curves at most this many times + const int kMaxIter = 5; + std::vector<SweepInterval> overlaps; + + for (int cur_iter = 0; cur_iter < kMaxIter; ++cur_iter) { + if (cur_segments.size() == 0) { + // Done + break; + } + + std::vector<SweepEvent> events; + SweepTree tree(arena_); + for (std::vector<Segment*>::iterator iter = cur_segments.begin(); + iter != cur_segments.end(); + iter++) { + Segment* seg = *iter; + if (seg->kind() == Segment::kCubic) { + for (int i = 0; i < seg->num_triangles(); i++) { + LocalTriangulator::Triangle* triangle = seg->get_triangle(i); + BBox bbox; + bbox.Setup(triangle); + // Ignore zero-width triangles to avoid issues with + // coincident entry and exit events for the same triangle + if (bbox.max_x() > bbox.min_x()) { + SweepData* data = arena_->Alloc<SweepData>(); + data->triangle = triangle; + data->segment = seg; + SweepInterval interval = + tree.MakeInterval(bbox.min_y(), bbox.max_y(), data); + // Add entry and exit events + SweepEvent event; + event.Setup(bbox.min_x(), true, interval); + events.push_back(event); + event.Setup(bbox.max_x(), false, interval); + events.push_back(event); + } + } + } + } + + // Sort events by increasing X coordinate + std::sort(events.begin(), events.end()); + + // Now iterate through the events + for (std::vector<SweepEvent>::iterator iter = events.begin(); + iter != events.end(); + iter++) { + SweepEvent event = *iter; + if (event.entry()) { + // Add this interval into the tree + tree.Insert(event.interval()); + // See whether the associated segment has been subdivided yet + if (!event.interval().data()->segment->marked_for_subdivision()) { + // Query the tree + overlaps.clear(); + tree.AllOverlaps(event.interval(), overlaps); + // Now see exactly which triangles overlap this one + for (std::vector<SweepInterval>::iterator iter = overlaps.begin(); + iter != overlaps.end(); + iter++) { + SweepInterval overlap = *iter; + // Only pay attention to overlaps from a different Segment + if (event.interval().data()->segment != overlap.data()->segment) { + // See whether the triangles actually overlap + if (TrianglesOverlap(event.interval().data()->triangle, + overlap.data()->triangle)) { + // Actually subdivide the segments. + // Each one might already have been subdivided. + Segment* seg = event.interval().data()->segment; + ConditionallySubdivide(seg, &next_segments); + seg = overlap.data()->segment; + ConditionallySubdivide(seg, &next_segments); + } + } + } + } + } else { + // Remove this interval from the tree + tree.Delete(event.interval()); + } + } + + cur_segments = next_segments; + next_segments.clear(); + } +} + +void PathProcessor::ConditionallySubdivide( + Segment* seg, std::vector<Segment*>* next_segments) { + if (!seg->marked_for_subdivision()) { + seg->set_marked_for_subdivision(true); + Segment* next = seg->contour()->Subdivide(seg); + // Triangulate the newly subdivided segments. + next->Triangulate(false, NULL); + next->next()->Triangulate(false, NULL); + // Add them for the next iteration. + next_segments->push_back(next); + next_segments->push_back(next->next()); + } +} + +void PathProcessor::SubdivideCurvesSlow() { + // Alternate, significantly slower algorithm for curve subdivision + // for use in debugging. + std::vector<Segment*> cur_segments; + std::vector<Segment*> next_segments; + + // Start things off by considering all of the segments + for (std::vector<Contour*>::iterator iter = contours_.begin(); + iter != contours_.end(); + iter++) { + Contour* cur = *iter; + for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { + if (seg->kind() == Segment::kCubic) { + seg->Triangulate(false, NULL); + cur_segments.push_back(seg); + } + } + } + + // Subdivide curves at most this many times + const int kMaxIter = 5; + + for (int cur_iter = 0; cur_iter < kMaxIter; ++cur_iter) { + if (cur_segments.size() == 0) { + // Done + break; + } + + for (std::vector<Segment*>::iterator iter = cur_segments.begin(); + iter != cur_segments.end(); + iter++) { + Segment* seg = *iter; + if (seg->kind() == Segment::kCubic) { + for (std::vector<Segment*>::iterator iter2 = cur_segments.begin(); + iter2 != cur_segments.end(); + iter2++) { + Segment* seg2 = *iter2; + if (seg2->kind() == Segment::kCubic && + seg != seg2) { + for (int i = 0; i < seg->num_triangles(); i++) { + LocalTriangulator::Triangle* triangle = seg->get_triangle(i); + for (int j = 0; j < seg2->num_triangles(); j++) { + LocalTriangulator::Triangle* triangle2 = seg2->get_triangle(j); + if (TrianglesOverlap(triangle, triangle2)) { + ConditionallySubdivide(seg, &next_segments); + ConditionallySubdivide(seg2, &next_segments); + } + } + } + } + } + } + } + + cur_segments = next_segments; + next_segments.clear(); + } +} + +//---------------------------------------------------------------------- +// Structures and callbacks for tessellation of the interior region of +// the contours. + +// The user data for the GLU tessellator. +struct TessellationState { + PathCache* cache; + std::vector<void*> allocated_pointers; +}; + +namespace { + +void VertexCallback(void* vertex_data, void* data) { + TessellationState* state = static_cast<TessellationState*>(data); + PathCache* cache = state->cache; + GLdouble* location = static_cast<GLdouble*>(vertex_data); + cache->AddInteriorVertex(static_cast<float>(location[0]), + static_cast<float>(location[1])); +} + +void CombineCallback(GLdouble coords[3], void* vertex_data[4], + GLfloat weight[4], void** out_data, + void* polygon_data) { + TessellationState* state = static_cast<TessellationState*>(polygon_data); + GLdouble* out_vertex = static_cast<GLdouble*>(malloc(3 * sizeof(GLdouble))); + state->allocated_pointers.push_back(out_vertex); + out_vertex[0] = coords[0]; + out_vertex[1] = coords[1]; + out_vertex[2] = coords[2]; + *out_data = out_vertex; +} + +void EdgeFlagCallback(GLboolean flag) { + // No-op just to prevent triangle strips and fans from being passed + // to us +} + +} // anonymous namespace + +void PathProcessor::TessellateInterior(PathCache* cache) { + // Because the GLU tessellator requires its input in + // double-precision format, we need to make a separate copy of the + // data. + std::vector<GLdouble> vertex_data; + std::vector<size_t> contour_endings; + // For avoiding adding coincident vertices. + float cur_x = 0, cur_y = 0; + for (std::vector<Contour*>::iterator iter = contours_.begin(); + iter != contours_.end(); + iter++) { + Contour* cur = *iter; + bool first = true; + for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) { + int num_interior_vertices = seg->num_interior_vertices(); + for (int i = 0; i < num_interior_vertices - 1; i++) { + SkPoint point = seg->get_interior_vertex(i); + if (first) { + first = false; + vertex_data.push_back(point.fX); + vertex_data.push_back(point.fY); + vertex_data.push_back(0); + cur_x = point.fX; + cur_y = point.fY; + } else if (point.fX != cur_x || point.fY != cur_y) { + vertex_data.push_back(point.fX); + vertex_data.push_back(point.fY); + vertex_data.push_back(0); + cur_x = point.fX; + cur_y = point.fY; + } + } + } + contour_endings.push_back(vertex_data.size()); + } + // Now that we have all of the vertex data in a stable location in + // memory, call the tessellator. + GLUtesselator* tess = internal_gluNewTess(); + TessellationState state; + state.cache = cache; + internal_gluTessCallback(tess, GLU_TESS_VERTEX_DATA, + reinterpret_cast<GLvoid (*)()>(VertexCallback)); + internal_gluTessCallback(tess, GLU_TESS_COMBINE_DATA, + reinterpret_cast<GLvoid (*)()>(CombineCallback)); + internal_gluTessCallback(tess, GLU_TESS_EDGE_FLAG, + reinterpret_cast<GLvoid (*)()>(EdgeFlagCallback)); + internal_gluTessBeginPolygon(tess, &state); + internal_gluTessBeginContour(tess); + GLdouble* base = &vertex_data.front(); + int contour_idx = 0; + for (size_t i = 0; i < vertex_data.size(); i += 3) { + if (i == contour_endings[contour_idx]) { + internal_gluTessEndContour(tess); + internal_gluTessBeginContour(tess); + ++contour_idx; + } + internal_gluTessVertex(tess, &base[i], &base[i]); + } + internal_gluTessEndContour(tess); + internal_gluTessEndPolygon(tess); + for (size_t i = 0; i < state.allocated_pointers.size(); i++) { + free(state.allocated_pointers[i]); + } + internal_gluDeleteTess(tess); +} + +} // namespace gpu2d +} // namespace o3d + diff --git a/o3d/core/cross/gpu2d/path_processor.h b/o3d/core/cross/gpu2d/path_processor.h new file mode 100644 index 0000000..f1af232 --- /dev/null +++ b/o3d/core/cross/gpu2d/path_processor.h @@ -0,0 +1,126 @@ +/* + * Copyright 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: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * 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. + * * Neither the name of Google Inc. nor the names of its + * contributors may be used to endorse or promote products derived from + * this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 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 THE COPYRIGHT + * OWNER OR 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. + */ + +// The main entry point for Loop and Blinn's GPU accelerated curve +// rendering algorithm. + +#ifndef O3D_CORE_CROSS_GPU2D_PATH_PROCESSOR_H_ +#define O3D_CORE_CROSS_GPU2D_PATH_PROCESSOR_H_ + +#include <vector> + +#include "base/basictypes.h" + +class SkPath; + +namespace o3d { +namespace gpu2d { + +class Arena; +class Contour; +class PathCache; +class Segment; + +// The PathProcessor turns an SkPath (assumed to contain one or more +// closed regions) into a set of exterior and interior triangles, +// stored in the PathCache. The exterior triangles have associated 3D +// texture coordinates which are used to evaluate the curve's +// inside/outside function on a per-pixel basis. The interior +// triangles are filled with 100% opacity. +// +// Note that the fill style and management of multiple layers are +// separate concerns, handled at a higher level with shaders and +// polygon offsets. +class PathProcessor { + public: + PathProcessor(); + explicit PathProcessor(Arena* arena); + ~PathProcessor(); + + // Transforms the given path into a triangle mesh for rendering + // using Loop and Blinn's shader, placing the result into the given + // PathCache. + void Process(const SkPath& path, PathCache* cache); + + // Enables or disables verbose logging in debug mode. + void set_verbose_logging(bool on_or_off); + + private: + // Builds a list of contours for the given path. + void BuildContours(const SkPath& path); + + // Determines whether the left or right side of each contour should + // be filled. + void DetermineSidesToFill(); + + // Determines whether the given (closed) contour is oriented + // clockwise or counterclockwise. + void DetermineOrientation(Contour* contour); + + // Subdivides the curves so that there are no overlaps of the + // triangles associated with the curves' control points. + void SubdivideCurves(); + + // Helper function used during curve subdivision. + void ConditionallySubdivide(Segment* seg, + std::vector<Segment*>* next_segments); + + // Tessellates the interior regions of the contours. + void TessellateInterior(PathCache* cache); + + // For debugging the orientation computation. Returns all of the + // segments overlapping the given Y coordinate. + std::vector<Segment*> AllSegmentsOverlappingY(float y); + + // For debugging the curve subdivision algorithm. Subdivides the + // curves using an alternate, slow (O(n^3)) algorithm. + void SubdivideCurvesSlow(); + + // Arena from which to allocate temporary objects. + Arena* arena_; + + // Whether to delete the arena upon deletion of the PathProcessor. + bool should_delete_arena_; + + // The contours described by the path. + std::vector<Contour*> contours_; + + // Whether or not to perform verbose logging in debug mode. + bool verbose_logging_; + + DISALLOW_COPY_AND_ASSIGN(PathProcessor); +}; + +} // namespace gpu2d +} // namespace o3d + +#endif // O3D_CORE_CROSS_GPU2D_PATH_PROCESSOR_H_ + |