summaryrefslogtreecommitdiffstats
path: root/o3d/core
diff options
context:
space:
mode:
Diffstat (limited to 'o3d/core')
-rw-r--r--o3d/core/core.gyp4
-rw-r--r--o3d/core/cross/gpu2d/cubic_math_utils.cc97
-rw-r--r--o3d/core/cross/gpu2d/cubic_math_utils.h16
-rw-r--r--o3d/core/cross/gpu2d/local_triangulator.cc302
-rw-r--r--o3d/core/cross/gpu2d/local_triangulator.h255
-rw-r--r--o3d/core/cross/gpu2d/local_triangulator_test.cc134
6 files changed, 808 insertions, 0 deletions
diff --git a/o3d/core/core.gyp b/o3d/core/core.gyp
index 33e8740..1b8ee2d 100644
--- a/o3d/core/core.gyp
+++ b/o3d/core/core.gyp
@@ -272,10 +272,13 @@
'cross/gpu2d/arena.h',
'cross/gpu2d/cubic_classifier.cc',
'cross/gpu2d/cubic_classifier.h',
+ 'cross/gpu2d/cubic_math_utils.cc',
'cross/gpu2d/cubic_math_utils.h',
'cross/gpu2d/cubic_texture_coords.cc',
'cross/gpu2d/cubic_texture_coords.h',
'cross/gpu2d/interval_tree.h',
+ 'cross/gpu2d/local_triangulator.cc',
+ 'cross/gpu2d/local_triangulator.h',
'cross/gpu2d/red_black_tree.h',
],
'direct_dependent_settings': {
@@ -520,6 +523,7 @@
'cross/gpu2d/arena_test.cc',
'cross/gpu2d/cubic_classifier_test.cc',
'cross/gpu2d/interval_tree_test.cc',
+ 'cross/gpu2d/local_triangulator_test.cc',
'cross/gpu2d/red_black_tree_test.cc',
'cross/gpu2d/tree_test_helpers.cc',
'cross/gpu2d/tree_test_helpers.h',
diff --git a/o3d/core/cross/gpu2d/cubic_math_utils.cc b/o3d/core/cross/gpu2d/cubic_math_utils.cc
new file mode 100644
index 0000000..a62ba3b
--- /dev/null
+++ b/o3d/core/cross/gpu2d/cubic_math_utils.cc
@@ -0,0 +1,97 @@
+/*
+ * 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/cubic_math_utils.h"
+
+namespace o3d {
+namespace gpu2d {
+namespace cubic {
+
+namespace {
+
+// Utility functions local to this file
+
+int Orientation(float x1, float y1,
+ float x2, float y2,
+ float x3, float y3) {
+ // p1 = (x1, y1)
+ // p2 = (x2, y2)
+ // p3 = (x3, y3)
+ float cross_product = (y2 - y1) * (x3 - x2) - (y3 - y2) * (x2 - x1);
+ return (cross_product < 0.0f) ? -1 : ((cross_product > 0.0f) ? 1 : 0);
+}
+
+} // anonymous namespace
+
+bool LinesIntersect(float p1x, float p1y,
+ float q1x, float q1y,
+ float p2x, float p2y,
+ float q2x, float q2y) {
+ return ((Orientation(p1x, p1y, q1x, q1y, p2x, p2y) !=
+ Orientation(p1x, p1y, q1x, q1y, q2x, q2y)) &&
+ (Orientation(p2x, p2y, q2x, q2y, p1x, p1y) !=
+ Orientation(p2x, p2y, q2x, q2y, q1x, q1y)));
+}
+
+bool PointInTriangle(float px, float py,
+ float ax, float ay,
+ float bx, float by,
+ float cx, float cy) {
+ // Algorithm from http://www.blackpawn.com/texts/pointinpoly/default.html
+ float x0 = cx - ax;
+ float y0 = cy - ay;
+ float x1 = bx - ax;
+ float y1 = by - ay;
+ float x2 = px - ax;
+ float y2 = py - ay;
+
+ float dot00 = x0 * x0 + y0 * y0;
+ float dot01 = x0 * x1 + y0 * y1;
+ float dot02 = x0 * x2 + y0 * y2;
+ float dot11 = x1 * x1 + y1 * y1;
+ float dot12 = x1 * x2 + y1 * y2;
+ float denom = dot00 * dot11 - dot01 * dot01;
+ if (denom == 0.0f) {
+ // Triangle is zero-area. Treat query point as not being inside.
+ return false;
+ }
+ // Compute
+ float invDenom = 1.0f / denom;
+ float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
+ float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
+
+ return (u > 0.0f) && (v > 0.0f) && (u + v < 1.0f);
+}
+
+} // 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 2581c7f..0e03939 100644
--- a/o3d/core/cross/gpu2d/cubic_math_utils.h
+++ b/o3d/core/cross/gpu2d/cubic_math_utils.h
@@ -80,6 +80,22 @@ inline bool ApproxEqual(float f0, float f1) {
return fabsf(f0 - f1) < kEpsilon;
}
+// Determines whether the line segment between (p1, q1) intersects
+// that between (p2, q2).
+bool LinesIntersect(float p1x, float p1y,
+ float q1x, float q1y,
+ float p2x, float p2y,
+ float q2x, float q2y);
+
+// Determines whether the 2D point defined by (px, py) is inside the
+// 2D triangle defined by vertices (ax, ay), (bx, by), and (cx, cy).
+// This test defines that points exactly on an edge are not considered
+// to be inside the triangle.
+bool PointInTriangle(float px, float py,
+ float ax, float ay,
+ float bx, float by,
+ float cx, float cy);
+
} // namespace cubic
} // namespace gpu2d
} // namespace o3d
diff --git a/o3d/core/cross/gpu2d/local_triangulator.cc b/o3d/core/cross/gpu2d/local_triangulator.cc
new file mode 100644
index 0000000..00f33d9
--- /dev/null
+++ b/o3d/core/cross/gpu2d/local_triangulator.cc
@@ -0,0 +1,302 @@
+/*
+ * 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/local_triangulator.h"
+
+#include <algorithm>
+
+#include "core/cross/gpu2d/cubic_math_utils.h"
+
+namespace o3d {
+namespace gpu2d {
+
+using cubic::ApproxEqual;
+using cubic::Distance;
+using cubic::LinesIntersect;
+using cubic::PointInTriangle;
+
+bool LocalTriangulator::Triangle::Contains(LocalTriangulator::Vertex* v) {
+ for (int i = 0; i < 3; i++) {
+ if (v_[i] == v)
+ return true;
+ }
+ return false;
+}
+
+LocalTriangulator::Vertex* LocalTriangulator::Triangle::NextVertex(
+ LocalTriangulator::Vertex* cur,
+ bool ccw) {
+ int idx = IndexForVertex(cur);
+ DCHECK(idx >= 0);
+ if (ccw) {
+ ++idx;
+ } else {
+ --idx;
+ }
+ if (idx < 0) {
+ idx += 3;
+ } else {
+ idx = idx % 3;
+ }
+ return v_[idx];
+}
+
+int LocalTriangulator::Triangle::IndexForVertex(
+ LocalTriangulator::Vertex* vertex) {
+ for (int i = 0; i < 3; i++) {
+ if (v_[i] == vertex)
+ return i;
+ }
+ return -1;
+}
+
+void LocalTriangulator::Triangle::MakeCCW() {
+ // Possibly swaps two vertices so that the triangle's vertices are
+ // always specified in counterclockwise order. This orders the
+ // vertices canonically when walking the interior edges from the
+ // start to the end vertex.
+ Vector3 vec0(v_[0]->x(), v_[0]->y(), 0.0f);
+ Vector3 vec1(v_[1]->x(), v_[1]->y(), 0.0f);
+ Vector3 vec2(v_[2]->x(), v_[2]->y(), 0.0f);
+ Vector3 diff1 = vec1 - vec0;
+ Vector3 diff2 = vec2 - vec0;
+ Vector3 cp = cross(diff1, diff2);
+ if (cp.getZ() < 0.0f) {
+ std::swap(v_[1], v_[2]);
+ }
+}
+
+LocalTriangulator::LocalTriangulator() {
+ Reset();
+}
+
+void LocalTriangulator::Reset() {
+ num_triangles_ = 0;
+ num_interior_vertices_ = 0;
+ for (int i = 0; i < 4; i++) {
+ interior_vertices_[i] = NULL;
+ vertices_[i].ResetFlags();
+ }
+}
+
+void LocalTriangulator::Triangulate(bool compute_interior_vertices,
+ bool fill_right_side) {
+ Reset();
+
+ bool done = false;
+
+ vertices_[3].set_end(true);
+
+ // First test for degenerate cases.
+ for (int i = 0; i < 4 && !done; i++) {
+ for (int j = i + 1; j < 4 && !done; j++) {
+ if (ApproxEqual(vertices_[i].x(), vertices_[i].y(),
+ vertices_[j].x(), vertices_[j].y())) {
+ // Two of the vertices are coincident, so we can eliminate at
+ // least one triangle. We might be able to eliminate the other
+ // as well, but this seems sufficient to avoid degenerate
+ // triangulations.
+ int indices[3] = { 0 };
+ int index = 0;
+ for (int k = 0; k < 4; k++) {
+ if (k != j)
+ indices[index++] = k;
+ }
+ AddTriangle(&vertices_[indices[0]],
+ &vertices_[indices[1]],
+ &vertices_[indices[2]]);
+ done = true;
+ }
+ }
+ }
+
+ if (!done) {
+ // See whether any of the points are fully contained in the
+ // triangle defined by the other three.
+ for (int i = 0; i < 4 && !done; i++) {
+ int indices[3] = { 0 };
+ int index = 0;
+ for (int j = 0; j < 4; j++) {
+ if (i != j)
+ indices[index++] = j;
+ }
+ if (PointInTriangle(
+ vertices_[i].x(), vertices_[i].y(),
+ vertices_[indices[0]].x(), vertices_[indices[0]].y(),
+ vertices_[indices[1]].x(), vertices_[indices[1]].y(),
+ vertices_[indices[2]].x(), vertices_[indices[2]].y())) {
+ // Produce three triangles surrounding this interior vertex.
+ for (int j = 0; j < 3; j++) {
+ AddTriangle(&vertices_[indices[j % 3]],
+ &vertices_[indices[(j + 1) % 3]],
+ &vertices_[i]);
+ }
+ // Mark the interior vertex so we ignore it if trying to trace
+ // the interior edge.
+ vertices_[i].set_interior(true);
+ done = true;
+ }
+ }
+ }
+
+ if (!done) {
+ // There are only a few permutations of the vertices, ignoring
+ // rotations, which are irrelevant:
+ //
+ // 0--3 0--2 0--3 0--1 0--2 0--1
+ // | | | | | | | | | | | |
+ // | | | | | | | | | | | |
+ // 1--2 1--3 2--1 2--3 3--1 3--2
+ //
+ // Note that three of these are reflections of each other.
+ // Therefore there are only three possible triangulations:
+ //
+ // 0--3 0--2 0--3
+ // |\ | |\ | |\ |
+ // | \| | \| | \|
+ // 1--2 1--3 2--1
+ //
+ // From which we can choose by seeing which of the potential
+ // diagonals intersect. Note that we choose the shortest diagonal
+ // to split the quad.
+ if (LinesIntersect(vertices_[0].x(), vertices_[0].y(),
+ vertices_[2].x(), vertices_[2].y(),
+ vertices_[1].x(), vertices_[1].y(),
+ vertices_[3].x(), vertices_[3].y())) {
+ if (Distance(vertices_[0].x(), vertices_[0].y(),
+ vertices_[2].x(), vertices_[2].y()) <
+ Distance(vertices_[1].x(), vertices_[1].y(),
+ vertices_[3].x(), vertices_[3].y())) {
+ AddTriangle(&vertices_[0], &vertices_[1], &vertices_[2]);
+ AddTriangle(&vertices_[0], &vertices_[2], &vertices_[3]);
+ } else {
+ AddTriangle(&vertices_[0], &vertices_[1], &vertices_[3]);
+ AddTriangle(&vertices_[1], &vertices_[2], &vertices_[3]);
+ }
+ } else if (LinesIntersect(
+ vertices_[0].x(), vertices_[0].y(),
+ vertices_[3].x(), vertices_[3].y(),
+ vertices_[1].x(), vertices_[1].y(),
+ vertices_[2].x(), vertices_[2].y())) {
+ if (Distance(vertices_[0].x(), vertices_[0].y(),
+ vertices_[3].x(), vertices_[3].y()) <
+ Distance(vertices_[1].x(), vertices_[1].y(),
+ vertices_[2].x(), vertices_[2].y())) {
+ AddTriangle(&vertices_[0], &vertices_[1], &vertices_[3]);
+ AddTriangle(&vertices_[0], &vertices_[3], &vertices_[2]);
+ } else {
+ AddTriangle(&vertices_[0], &vertices_[1], &vertices_[2]);
+ AddTriangle(&vertices_[2], &vertices_[1], &vertices_[3]);
+ }
+ } else {
+ // Lines (0->1), (2->3) intersect -- or should, modulo numerical
+ // precision issues
+ if (Distance(vertices_[0].x(), vertices_[0].y(),
+ vertices_[1].x(), vertices_[1].y()) <
+ Distance(vertices_[2].x(), vertices_[2].y(),
+ vertices_[3].x(), vertices_[3].y())) {
+ AddTriangle(&vertices_[0], &vertices_[2], &vertices_[1]);
+ AddTriangle(&vertices_[0], &vertices_[1], &vertices_[3]);
+ } else {
+ AddTriangle(&vertices_[0], &vertices_[2], &vertices_[3]);
+ AddTriangle(&vertices_[3], &vertices_[2], &vertices_[1]);
+ }
+ }
+ }
+
+ if (compute_interior_vertices) {
+ // We need to compute which vertices describe the path along the
+ // interior portion of the shape, to feed these vertices to the
+ // more general tessellation algorithm. It is possible that we
+ // could determine this directly while producing triangles above.
+ // Here we try to do it generally just by examining the triangles
+ // that have already been produced. We walk around them in a
+ // specific direction determined by which side of the curve is
+ // being filled. We ignore the interior vertex unless it is also
+ // the ending vertex, and skip the edges shared between two
+ // triangles.
+ Vertex* v = &vertices_[0];
+ AddInteriorVertex(v);
+ int num_steps = 0;
+ while (!v->end() && num_steps < 4) {
+ // Find the next vertex according to the above rules
+ bool got_next = false;
+ for (int i = 0; i < num_triangles() && !got_next; i++) {
+ Triangle* tri = get_triangle(i);
+ if (tri->Contains(v)) {
+ Vertex* next = tri->NextVertex(v, fill_right_side);
+ if (!next->marked() &&
+ !IsSharedEdge(v, next) &&
+ (!next->interior() || next->end())) {
+ AddInteriorVertex(next);
+ v = next;
+ // Break out of for loop
+ got_next = true;
+ }
+ }
+ }
+ ++num_steps;
+ }
+ if (!v->end()) {
+ // Something went wrong with the above algorithm; add the last
+ // vertex to the interior vertices anyway.
+ AddInteriorVertex(&vertices_[3]);
+ }
+ }
+}
+
+void LocalTriangulator::AddTriangle(Vertex* v0, Vertex* v1, Vertex* v2) {
+ DCHECK(num_triangles_ < 3);
+ triangles_[num_triangles_++].SetVertices(v0, v1, v2);
+}
+
+void LocalTriangulator::AddInteriorVertex(Vertex* v) {
+ DCHECK(num_interior_vertices_ < 4);
+ interior_vertices_[num_interior_vertices_++] = v;
+ v->set_marked(true);
+}
+
+bool LocalTriangulator::IsSharedEdge(Vertex* v0, Vertex* v1) {
+ bool haveEdge01 = false;
+ bool haveEdge10 = false;
+ for (int i = 0; i < num_triangles(); i++) {
+ Triangle* tri = get_triangle(i);
+ if (tri->Contains(v0) && tri->NextVertex(v0, true) == v1)
+ haveEdge01 = true;
+ if (tri->Contains(v1) && tri->NextVertex(v1, true) == v0)
+ haveEdge10 = true;
+ }
+ return haveEdge01 && haveEdge10;
+}
+
+} // namespace gpu2d
+} // namespace o3d
+
diff --git a/o3d/core/cross/gpu2d/local_triangulator.h b/o3d/core/cross/gpu2d/local_triangulator.h
new file mode 100644
index 0000000..39894ea
--- /dev/null
+++ b/o3d/core/cross/gpu2d/local_triangulator.h
@@ -0,0 +1,255 @@
+/*
+ * 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_LOCAL_TRIANGULATOR_H_
+#define O3D_CORE_CROSS_GPU2D_LOCAL_TRIANGULATOR_H_
+
+#include "base/basictypes.h"
+#include "base/logging.h"
+
+namespace o3d {
+namespace gpu2d {
+
+// Performs a localized triangulation of the triangle mesh
+// corresponding to the four control point vertices of a cubic curve
+// segment.
+class LocalTriangulator {
+ public:
+ // The vertices that the triangulator operates upon, containing both
+ // the position information as well as the cubic texture
+ // coordinates.
+ class Vertex {
+ public:
+ Vertex() {
+ }
+
+ float x() { return x_; }
+ float y() { return y_; }
+
+ float k() { return k_; }
+ float l() { return l_; }
+ float m() { return m_; }
+
+ // Sets the position and texture coordinates of the vertex.
+ void Set(float x, float y,
+ float k, float l, float m) {
+ x_ = x;
+ y_ = y;
+ k_ = k;
+ l_ = l;
+ m_ = m;
+ }
+
+ // Flags for walking from the start vertex to the end vertex.
+ bool end() {
+ return end_;
+ }
+
+ void set_end(bool end) {
+ end_ = end;
+ }
+
+ bool marked() {
+ return marked_;
+ }
+
+ void set_marked(bool marked) {
+ marked_ = marked;
+ }
+
+ bool interior() {
+ return interior_;
+ }
+
+ void set_interior(bool interior) {
+ interior_ = interior;
+ }
+
+ void ResetFlags() {
+ end_ = false;
+ marked_ = false;
+ interior_ = false;
+ }
+
+ private:
+ // 2D coordinates of the vertex in the plane.
+ float x_;
+ float y_;
+ // Cubic texture coordinates for rendering the curve.
+ float k_, l_, m_;
+
+ // Flags for walking from the start vertex to the end vertex.
+ bool end_;
+ bool marked_;
+ bool interior_;
+ DISALLOW_COPY_AND_ASSIGN(Vertex);
+ };
+
+ // The triangles the Triangulator produces.
+ class Triangle {
+ public:
+ Triangle() {
+ v_[0] = NULL;
+ v_[1] = NULL;
+ v_[2] = NULL;
+ }
+
+ // Gets the vertex at the given index, 0 <= index < 3.
+ Vertex* get_vertex(int index) {
+ DCHECK(index >= 0 && index < 3);
+ return v_[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* cur, bool ccw);
+
+ // Sets the vertices of this triangle, potentially reordering them
+ // to produce a canonical orientation.
+ void SetVertices(Vertex* v0,
+ Vertex* v1,
+ Vertex* v2) {
+ v_[0] = v0;
+ v_[1] = v1;
+ v_[2] = v2;
+ MakeCCW();
+ }
+
+ 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 MakeCCW();
+
+ Vertex* v_[3];
+
+ DISALLOW_COPY_AND_ASSIGN(Triangle);
+ };
+
+ LocalTriangulator();
+
+ // 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* get_vertex(int index) {
+ DCHECK(index >= 0 && index < 4);
+ return &vertices_[index];
+ }
+
+ // Once the vertices' contents have been set up, call Triangulate()
+ // to recompute the triangles.
+ //
+ // If compute_inside_edges is true, then fill_right_side 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(bool compute_inside_edges,
+ bool fill_right_side);
+
+ // Number of triangles computed by Triangulate().
+ int num_triangles() {
+ return num_triangles_;
+ }
+
+ // Returns the computed triangle at index, 0 <= index <
+ // num_triangles().
+ Triangle* get_triangle(int index) {
+ DCHECK(index >= 0 && index < num_triangles_);
+ return &triangles_[index];
+ }
+
+ // Number of vertices facing the inside of the shape, if
+ // compute_inside_edges was true when Triangulate() was called.
+ int num_interior_vertices() {
+ return num_interior_vertices_;
+ }
+
+ // Fetches the given interior vertex, 0 <= index <
+ // num_interior_vertices(). Returns NULL if index is out of range.
+ Vertex* get_interior_vertex(int index) {
+ DCHECK(index >= 0 && index < num_interior_vertices_);
+ return interior_vertices_[index];
+ }
+
+ private:
+ // 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 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* interior_vertices_[4];
+ // The number of interior vertices that are valid for the current
+ // triangulation.
+ int num_interior_vertices_;
+
+ // 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 triangles_[3];
+ int num_triangles_;
+
+ DISALLOW_COPY_AND_ASSIGN(LocalTriangulator);
+};
+
+} // namespace gpu2d
+} // namespace o3d
+
+#endif // O3D_CORE_CROSS_GPU2D_LOCAL_TRIANGULATOR_H_
+
diff --git a/o3d/core/cross/gpu2d/local_triangulator_test.cc b/o3d/core/cross/gpu2d/local_triangulator_test.cc
new file mode 100644
index 0000000..4ceba99
--- /dev/null
+++ b/o3d/core/cross/gpu2d/local_triangulator_test.cc
@@ -0,0 +1,134 @@
+/*
+ * 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.
+ */
+
+// Tests for the local triangulator.
+
+#include "core/cross/gpu2d/cubic_math_utils.h"
+#include "core/cross/gpu2d/local_triangulator.h"
+#include "gtest/gtest.h"
+
+namespace o3d {
+namespace gpu2d {
+
+using cubic::ApproxEqual;
+
+namespace {
+
+// Sets up control point vertices for (approximately) a serpentine
+// curve.
+void SetupSerpentineVertices(LocalTriangulator* triangulator) {
+ triangulator->get_vertex(0)->Set(0.0f, 0.0f, 0.0f, 0.0f, 0.0f);
+ triangulator->get_vertex(1)->Set(75.0f, 25.0f, 0.0f, 0.0f, 0.0f);
+ triangulator->get_vertex(2)->Set(25.0f, 75.0f, 0.0f, 0.0f, 0.0f);
+ triangulator->get_vertex(3)->Set(100.0f, 100.0f, 0.0f, 0.0f, 0.0f);
+}
+
+} // anonymous namespace
+
+TEST(LocalTriangulatorTest, TestShortestEdgeGuarantee) {
+ LocalTriangulator triangulator;
+ SetupSerpentineVertices(&triangulator);
+ triangulator.Triangulate(false, false);
+ EXPECT_EQ(triangulator.num_triangles(), 2);
+ // It would be an error if the edge from (0, 0) to (100, 100) was
+ // contained in either of the two triangles.
+ for (int i = 0; i < triangulator.num_triangles(); i++) {
+ LocalTriangulator::Triangle* triangle = triangulator.get_triangle(i);
+ bool has_0_0 = false;
+ bool has_100_100 = false;
+ for (int j = 0; j < 3; j++) {
+ LocalTriangulator::Vertex* vertex = triangle->get_vertex(j);
+ if (ApproxEqual(vertex->x(), 0) && ApproxEqual(vertex->y(), 0)) {
+ has_0_0 = true;
+ }
+ if (ApproxEqual(vertex->x(), 100) && ApproxEqual(vertex->y(), 100)) {
+ has_100_100 = true;
+ }
+ }
+ EXPECT_FALSE(has_0_0 && has_100_100);
+ }
+}
+
+TEST(LocalTriangulatorTest, TestInteriorVertexGuarantee) {
+ LocalTriangulator triangulator;
+ triangulator.get_vertex(0)->Set(0.0f, 0.0f, 0.0f, 0.0f, 0.0f);
+ triangulator.get_vertex(1)->Set(100.0f, 0.0f, 0.0f, 0.0f, 0.0f);
+ triangulator.get_vertex(2)->Set(50.0f, 50.0f, 0.0f, 0.0f, 0.0f);
+ triangulator.get_vertex(3)->Set(50.0f, 100.0f, 0.0f, 0.0f, 0.0f);
+ triangulator.Triangulate(false, false);
+ EXPECT_EQ(triangulator.num_triangles(), 3);
+}
+
+TEST(LocalTriangulatorTest, TestInteriorVertexComputationFillingRightSide) {
+ LocalTriangulator triangulator;
+ SetupSerpentineVertices(&triangulator);
+ triangulator.Triangulate(true, true);
+ EXPECT_EQ(triangulator.num_triangles(), 2);
+ // In this configuration, vertex (75, 25) should be among the
+ // interior vertices, and vertex (25, 75) should not.
+ bool found_correct_interior_vertex = false;
+ for (int i = 0; i < triangulator.num_interior_vertices(); i++) {
+ LocalTriangulator::Vertex* vertex = triangulator.get_interior_vertex(i);
+ if (ApproxEqual(vertex->x(), 75) && ApproxEqual(vertex->y(), 25)) {
+ found_correct_interior_vertex = true;
+ }
+ }
+ EXPECT_TRUE(found_correct_interior_vertex);
+ for (int i = 0; i < triangulator.num_interior_vertices(); i++) {
+ LocalTriangulator::Vertex* vertex = triangulator.get_interior_vertex(i);
+ EXPECT_FALSE(ApproxEqual(vertex->x(), 25) && ApproxEqual(vertex->y(), 75));
+ }
+}
+
+TEST(LocalTriangulatorTest, TestInteriorVertexComputationFillingLeftSide) {
+ LocalTriangulator triangulator;
+ SetupSerpentineVertices(&triangulator);
+ triangulator.Triangulate(true, false);
+ EXPECT_EQ(triangulator.num_triangles(), 2);
+ // In this configuration, vertex (25, 75) should be among the
+ // interior vertices, and vertex (75, 25) should not.
+ bool found_correct_interior_vertex = false;
+ for (int i = 0; i < triangulator.num_interior_vertices(); i++) {
+ LocalTriangulator::Vertex* vertex = triangulator.get_interior_vertex(i);
+ if (ApproxEqual(vertex->x(), 25) && ApproxEqual(vertex->y(), 75)) {
+ found_correct_interior_vertex = true;
+ }
+ }
+ EXPECT_TRUE(found_correct_interior_vertex);
+ for (int i = 0; i < triangulator.num_interior_vertices(); i++) {
+ LocalTriangulator::Vertex* vertex = triangulator.get_interior_vertex(i);
+ EXPECT_FALSE(ApproxEqual(vertex->x(), 75) && ApproxEqual(vertex->y(), 25));
+ }
+}
+
+} // namespace gpu2d
+} // namespace o3d
+
generated by cgit v1.1 at 2025-01-21 10:39:21 +0000