Wed Sep 22 05:28:12 CDT 2004

```Author: spog
Date: 2004-09-21 15:49:06 -0500 (Tue, 21 Sep 2004)
New Revision: 4794

Modified:
Log:
specialised cubic bezier-curve evaluation

===================================================================
--- GtkRadiant/trunk/libs/math/curve.h	2004-09-21 19:11:36 UTC (rev 4793)
+++ GtkRadiant/trunk/libs/math/curve.h	2004-09-21 20:49:06 UTC (rev 4794)
@@ -4,89 +4,153 @@

#include "auto_array.h"
-#include "math/vector.h"
+#include <math/matrix.h>

-typedef double(*BernsteinPolynomialFunc)(double t);

-inline double bernstein_0_0(double t)
+template<typename I, typename Degree>
+struct BernsteinPolynomial
{
-  return 1;
-}
+  static double apply(double t)
+  {
+    return 1; // general case not implemented
+  }
+};

-inline double bernstein_0_1(double t)
+typedef ct_int<0> Zero;
+typedef ct_int<1> One;
+typedef ct_int<2> Two;
+typedef ct_int<3> Three;
+typedef ct_int<4> Four;
+
+template<>
+struct BernsteinPolynomial<Zero, Zero>
{
-  return 1 - t;
-}
+  static double apply(double t)
+  {
+    return 1;
+  }
+};

-inline double bernstein_1_1(double t)
+template<>
+struct BernsteinPolynomial<Zero, One>
{
-  return t;
-}
+  static double apply(double t)
+  {
+    return 1 - t;
+  }
+};

-inline double bernstein_0_2(double t)
+template<>
+struct BernsteinPolynomial<One, One>
{
-  return (1 - t) * (1 - t);
-}
+  static double apply(double t)
+  {
+    return t;
+  }
+};

-inline double bernstein_1_2(double t)
+template<>
+struct BernsteinPolynomial<Zero, Two>
{
-  return 2 * (1 - t) * t;
-}
+  static double apply(double t)
+  {
+    return (1 - t) * (1 - t);
+  }
+};

-inline double bernstein_2_2(double t)
+template<>
+struct BernsteinPolynomial<One, Two>
{
-  return t * t;
-}
+  static double apply(double t)
+  {
+    return 2 * (1 - t) * t;
+  }
+};

-inline double bernstein_0_3(double t)
+template<>
+struct BernsteinPolynomial<Two, Two>
{
-  return (1 - t) * (1 - t) * (1 - t);
-}
+  static double apply(double t)
+  {
+    return t * t;
+  }
+};

-inline double bernstein_1_3(double t)
+template<>
+struct BernsteinPolynomial<Zero, Three>
{
-  return 3 * (1 - t) * (1 - t) * t;
-}
+  static double apply(double t)
+  {
+    return (1 - t) * (1 - t) * (1 - t);
+  }
+};

-inline double bernstein_2_3(double t)
+template<>
+struct BernsteinPolynomial<One, Three>
{
-  return 3 * (1 - t) * t * t;
-}
+  static double apply(double t)
+  {
+    return 3 * (1 - t) * (1 - t) * t;
+  }
+};

-inline double bernstein_3_3(double t)
+template<>
+struct BernsteinPolynomial<Two, Three>
{
-  return t * t * t;
-}
+  static double apply(double t)
+  {
+    return 3 * (1 - t) * t * t;
+  }
+};

-const BernsteinPolynomialFunc bernsteinPolynomialsDegree0[1] = { bernstein_0_0, };
-const BernsteinPolynomialFunc bernsteinPolynomialsDegree1[2] = { bernstein_0_1, bernstein_1_1, };
-const BernsteinPolynomialFunc bernsteinPolynomialsDegree2[3] = { bernstein_0_2, bernstein_1_2, bernstein_2_2, };
-const BernsteinPolynomialFunc bernsteinPolynomialsDegree3[4] = { bernstein_0_3, bernstein_1_3, bernstein_2_3, bernstein_3_3, };
-typedef const BernsteinPolynomialFunc* BernsteinPolynomialFuncs;
-const BernsteinPolynomialFuncs bernsteinPolynomials[4] = { bernsteinPolynomialsDegree0, bernsteinPolynomialsDegree1, bernsteinPolynomialsDegree2, bernsteinPolynomialsDegree3, };
-
-
-inline double Bezier_basis(int i, int degree, double t)
+template<>
+struct BernsteinPolynomial<Three, Three>
{
-  RADIANT_ASSERT(degree < 4 && i <= degree, "only supporting curves of degree 3 or less");
-  return bernsteinPolynomials[degree][i](t);
-}
+  static double apply(double t)
+  {
+    return t * t * t;
+  }
+};

typedef auto_array<Vector3> ControlPoints;

-inline Vector3 Bezier_evaluate(const Vector3* firstPoint, int degree, double t)
+inline Vector3 CubicBezier_evaluate(const Vector3* firstPoint, double t)
{
Vector3 result(0, 0, 0);
double denominator = 0;
-  for(int i = 0; i < degree + 1; ++i)
+
{
-    double weight = Bezier_basis(i, degree, t);
+    double weight = BernsteinPolynomial<Zero, Three>::apply(t);
result += vector3_scaled(*firstPoint++, weight);
denominator += weight;
}
+  {
+    double weight = BernsteinPolynomial<One, Three>::apply(t);
+    result += vector3_scaled(*firstPoint++, weight);
+    denominator += weight;
+  }
+  {
+    double weight = BernsteinPolynomial<Two, Three>::apply(t);
+    result += vector3_scaled(*firstPoint++, weight);
+    denominator += weight;
+  }
+  {
+    double weight = BernsteinPolynomial<Three, Three>::apply(t);
+    result += vector3_scaled(*firstPoint++, weight);
+    denominator += weight;
+  }
+
return result / denominator;
}

+inline Vector3 CubicBezier_evaluateMid(const Vector3* firstPoint)
+{
+  return vector3_scaled(firstPoint[0], 0.125)
+    + vector3_scaled(firstPoint[1], 0.375)
+    + vector3_scaled(firstPoint[2], 0.375)
+    + vector3_scaled(firstPoint[3], 0.125);
+}
+
inline Vector3 CatmullRom_evaluate(const ControlPoints& controlPoints, double t)
{
// scale t to be segment-relative
@@ -115,7 +179,7 @@
? controlPoints[i + 1] + vector3_scaled(controlPoints[i] - controlPoints[i + 2], reciprocal_alpha * 0.5)
: controlPoints[i + 1] + vector3_scaled(controlPoints[i] - controlPoints[i + 1], reciprocal_alpha);
bezierPoints[3] = controlPoints[i + 1];
-  return Bezier_evaluate(bezierPoints, 3, t);
+  return CubicBezier_evaluate(bezierPoints, t);
}

typedef auto_array<float> Knots;

```