Added classifier which determines the type of a cubic curve input.

Its output will be used by the forthcoming texture coordinate
generator.

BUG=none
TEST=CubicClassifierTest

Review URL: http://codereview.chromium.org/626015

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@39373 0039d316-1c4b-4281-b951-d872f2087c98

5 files changed, 419 insertions, 0 deletions

diff --git a/o3d/core/core.gyp b/o3d/core/core.gyp
index 92db6f7..c979bae 100644
--- a/o3d/core/core.gyp
+++ b/o3d/core/core.gyp
@@ -270,6 +270,9 @@
         'cross/visitor_base.h',
         'cross/weak_ptr.h',
         'cross/gpu2d/arena.h',
+        'cross/gpu2d/cubic_classifier.cc',
+        'cross/gpu2d/cubic_classifier.h',
+        'cross/gpu2d/cubic_math_utils.h',
         'cross/gpu2d/interval_tree.h',
         'cross/gpu2d/red_black_tree.h',
       ],
@@ -513,6 +516,7 @@
           'cross/visitor_base_test.cc',
           'cross/weak_ptr_test.cc',
           'cross/gpu2d/arena_test.cc',
+          'cross/gpu2d/cubic_classifier_test.cc',
           'cross/gpu2d/interval_tree_test.cc',
           'cross/gpu2d/red_black_tree_test.cc',
           'cross/gpu2d/tree_test_helpers.cc',
diff --git a/o3d/core/cross/gpu2d/cubic_classifier.cc b/o3d/core/cross/gpu2d/cubic_classifier.cc
new file mode 100644
index 0000000..725fec6
--- /dev/null
+++ b/o3d/core/cross/gpu2d/cubic_classifier.cc
@@ -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.
+ */
+
+#include "core/cross/gpu2d/cubic_classifier.h"
+
+#include "core/cross/math_types.h"
+#include "core/cross/gpu2d/cubic_math_utils.h"
+
+namespace o3d {
+namespace gpu2d {
+
+using cubic::ApproxEqual;
+using cubic::RoundToZero;
+
+CubicClassifier::Result CubicClassifier::Classify(float b0x, float b0y,
+                                                  float b1x, float b1y,
+                                                  float b2x, float b2y,
+                                                  float b3x, float b3y) {
+  Vector3 b0(b0x, b0y, 1);
+  Vector3 b1(b1x, b1y, 1);
+  Vector3 b2(b2x, b2y, 1);
+  Vector3 b3(b3x, b3y, 1);
+
+  // Compute a1..a3
+  float a1 = dot(b0, cross(b3, b2));
+  float a2 = dot(b1, cross(b0, b3));
+  float a3 = dot(b2, cross(b1, b0));
+
+  // Compute d1..d3
+  float d1 = a1 - 2 * a2 + 3 * a3;
+  float d2 = -a2 + 3 * a3;
+  float d3 = 3 * a3;
+
+  // Experimentation has shown that the texture coordinates computed
+  // from these values quickly become huge, leading to roundoff errors
+  // and artifacts in the shader. It turns out that if we normalize
+  // the vector defined by (d1, d2, d3), this fixes the problem of the
+  // texture coordinates getting too large without affecting the
+  // classification results.
+  Vector3 nd = normalize(Vector3(d1, d2, d3));
+  d1 = nd.getX();
+  d2 = nd.getY();
+  d3 = nd.getZ();
+
+  // Compute the discriminant.
+  // term0 is a common term in the computation which helps decide
+  // which way to classify the cusp case: as serpentine or loop.
+  float term0 = (3 * d2 * d2 - 4 * d1 * d3);
+  float discr = d1 * d1 * term0;
+
+  // Experimentation has also shown that when the classification is
+  // near the boundary between one curve type and another, the shader
+  // becomes numerically unstable, particularly with the cusp case.
+  // Correct for this by rounding d1..d3 and the discriminant to zero
+  // when they get near it.
+  d1 = RoundToZero(d1);
+  d2 = RoundToZero(d2);
+  d3 = RoundToZero(d3);
+  discr = RoundToZero(discr);
+
+  // Do the classification
+  if (ApproxEqual(b0, b1) &&
+      ApproxEqual(b0, b2) &&
+      ApproxEqual(b0, b3)) {
+    return Result(kPoint, d1, d2, d3);
+  }
+
+  if (discr == 0) {
+    if (d1 == 0 && d2 == 0) {
+      if (d3 == 0)
+        return Result(kLine, d1, d2, d3);
+      return Result(kQuadratic, d1, d2, d3);
+    }
+
+    if (d1 == 0)
+      return Result(kCusp, d1, d2, d3);
+
+    // This is the boundary case described in Loop and Blinn's
+    // SIGGRAPH '05 paper of a cusp with inflection at infinity.
+    // Because term0 might not be exactly 0, we decide between using
+    // the serpentine and loop cases depending on its sign to avoid
+    // taking the square root of a negative number when computing the
+    // cubic texture coordinates.
+    if (term0 < 0)
+      return Result(kLoop, d1, d2, d3);
+
+    return Result(kSerpentine, d1, d2, d3);
+  } else if (discr > 0) {
+    return Result(kSerpentine, d1, d2, d3);
+  } else {
+    // discr < 0
+    return Result(kLoop, d1, d2, d3);
+  }
+}
+
+}  // namespace gpu2d
+}  // namespace o3d
+
diff --git a/o3d/core/cross/gpu2d/cubic_classifier.h b/o3d/core/cross/gpu2d/cubic_classifier.h
new file mode 100644
index 0000000..8b3c03a
--- /dev/null
+++ b/o3d/core/cross/gpu2d/cubic_classifier.h
@@ -0,0 +1,108 @@
+/*
+ * 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.
+ */
+
+// Cubic curve classification algorithm from "Rendering Vector Art on
+// the GPU" by Loop and Blinn, GPU Gems 3, Chapter 25.
+
+#ifndef O3D_CORE_CROSS_GPU2D_CUBIC_CLASSIFIER_H_
+#define O3D_CORE_CROSS_GPU2D_CUBIC_CLASSIFIER_H_
+
+#include "base/basictypes.h"
+
+namespace o3d {
+namespace gpu2d {
+
+// Classifies cubic curves into specific types.
+class CubicClassifier {
+ public:
+  // The types of cubic curves.
+  enum CurveType {
+    kSerpentine,
+    kCusp,
+    kLoop,
+    kQuadratic,
+    kLine,
+    kPoint
+  };
+
+  // The result of the classifier.
+  class Result {
+   public:
+    Result(CurveType curve_type,
+           float d1, float d2, float d3)
+        : curve_type_(curve_type),
+          d1_(d1),
+          d2_(d2),
+          d3_(d3) {
+    }
+
+    CurveType curve_type() const {
+      return curve_type_;
+    }
+
+    float d1() const {
+      return d1_;
+    }
+
+    float d2() const {
+      return d2_;
+    }
+
+    float d3() const {
+      return d3_;
+    }
+
+   private:
+    CurveType curve_type_;
+    float d1_;
+    float d2_;
+    float d3_;
+  };
+
+  // Classifies the given cubic bezier curve starting at (b0x, b0y),
+  // ending at (b3x, b3y), and affected by control points (b1x, b1y)
+  // and (b2x, b2y).
+  static Result Classify(float b0x, float b0y,
+                         float b1x, float b1y,
+                         float b2x, float b2y,
+                         float b3x, float b3y);
+
+ private:
+  // This class does not need to be instantiated.
+  CubicClassifier() {}
+  DISALLOW_COPY_AND_ASSIGN(CubicClassifier);
+};
+
+}  // namespace gpu2d
+}  // namespace o3d
+
+#endif  // O3D_CORE_CROSS_GPU2D_CUBIC_CLASSIFIER_H_
+
diff --git a/o3d/core/cross/gpu2d/cubic_classifier_test.cc b/o3d/core/cross/gpu2d/cubic_classifier_test.cc
new file mode 100644
index 0000000..a0ef475
--- /dev/null
+++ b/o3d/core/cross/gpu2d/cubic_classifier_test.cc
@@ -0,0 +1,93 @@
+/*
+ * 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 cubic classifier.
+
+#include "core/cross/gpu2d/cubic_classifier.h"
+#include "gtest/gtest.h"
+
+namespace o3d {
+namespace gpu2d {
+
+// The data points in the following tests were determined by hand in
+// an interactive program.
+
+TEST(CubicClassifierTest, TestSerpentine) {
+  CubicClassifier::Result result =
+      CubicClassifier::Classify(100, 100,
+                                125, 175,
+                                200, 100,
+                                200, 200);
+  EXPECT_EQ(CubicClassifier::kSerpentine, result.curve_type());
+}
+
+TEST(CubicClassifierTest, TestCusp) {
+  CubicClassifier::Result result =
+      CubicClassifier::Classify(100, 400,
+                                200, 200,
+                                300, 300,
+                                400, 400);
+  EXPECT_EQ(CubicClassifier::kCusp, result.curve_type());
+}
+
+TEST(CubicClassifierTest, TestLoop) {
+  CubicClassifier::Result result =
+      CubicClassifier::Classify(200, 200,
+                                400, 100,
+                                100, 100,
+                                300, 200);
+  EXPECT_EQ(CubicClassifier::kLoop, result.curve_type());
+}
+
+TEST(CubicClassifierTest, TestQuadratic) {
+  CubicClassifier::Result result =
+      CubicClassifier::Classify(100, 100,
+                                166.66667f, 166.66667f,
+                                233.33333f, 166.66667f,
+                                300, 100);
+  EXPECT_EQ(CubicClassifier::kQuadratic, result.curve_type());
+}
+
+// Can't figure out how to get the classifier to return kLine.
+
+TEST(CubicClassifierTest, TestPoint) {
+  CubicClassifier::Result result =
+      CubicClassifier::Classify(100, 100,
+                                100, 100,
+                                100, 100,
+                                100, 100);
+  EXPECT_EQ(CubicClassifier::kPoint, result.curve_type());
+}
+
+
+}  // namespace gpu2d
+}  // namespace o3d
+
diff --git a/o3d/core/cross/gpu2d/cubic_math_utils.h b/o3d/core/cross/gpu2d/cubic_math_utils.h
new file mode 100644
index 0000000..2581c7f
--- /dev/null
+++ b/o3d/core/cross/gpu2d/cubic_math_utils.h
@@ -0,0 +1,88 @@
+/*
+ * 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_CUBIC_MATH_UTILS_H_
+#define O3D_CORE_CROSS_GPU2D_CUBIC_MATH_UTILS_H_
+
+#include <math.h>
+
+#include "core/cross/math_types.h"
+
+namespace o3d {
+namespace gpu2d {
+namespace cubic {
+
+// A roundoff factor in the cubic classification and texture
+// coordinate generation algorithms. This primarily determines the
+// handling of corner cases during the classification process. Be
+// careful when adjusting this; it has been determined emprically to
+// work well.
+const float kEpsilon = 5.0e-4f;
+
+// Returns zero if value is within +/-kEpsilon of zero.
+inline float RoundToZero(float val) {
+  if (val < kEpsilon && val > -kEpsilon)
+    return 0;
+  return val;
+}
+
+// Returns distance between two points in the 2D plane.
+inline float Distance(float x0, float y0,
+                      float x1, float y1) {
+  float xd = x1 - x0;
+  float yd = y1 - y0;
+  return sqrtf(xd * xd + yd * yd);
+}
+
+// Returns true if the given points are within kEpsilon distance of
+// each other.
+inline bool ApproxEqual(const Vector3& v0, const Vector3& v1) {
+  return lengthSqr(v0 - v1) < kEpsilon * kEpsilon;
+}
+
+// Returns true if the given 2D points are within kEpsilon distance of
+// each other.
+inline bool ApproxEqual(float x0, float y0,
+                        float x1, float y1) {
+  return Distance(x0, y0, x1, y1) < kEpsilon;
+}
+
+// Returns true if the given scalar values are within kEpsilon of each other.
+inline bool ApproxEqual(float f0, float f1) {
+  return fabsf(f0 - f1) < kEpsilon;
+}
+
+}  // namespace cubic
+}  // namespace gpu2d
+}  // namespace o3d
+
+#endif  // O3D_CORE_CROSS_GPU2D_CUBIC_MATH_UTILS_H_
+