include/BezierCurve.hpp

   1 //
   2 //  Copyright (C) 2009  Nick Gasson
   3 //
   4 //  This program is free software: you can redistribute it and/or modify
   5 //  it under the terms of the GNU General Public License as published by
   6 //  the Free Software Foundation, either version 3 of the License, or
   7 //  (at your option) any later version.
   8 //
   9 //  This program is distributed in the hope that it will be useful,
  10 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 //  GNU General Public License for more details.
  13 //
  14 //  You should have received a copy of the GNU General Public License
  15 //  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16 //
  17
  18 #ifndef INC_BEZIER_CURVE_HPP
  19 #define INC_BEZIER_CURVE_HPP
  20
  21 #include "Platform.hpp"
  22 #include "Maths.hpp"
  23
  24 // Three-dimensional Bezier curve
  25 template <typename T>
  26 struct BezierCurve {
  27    Vector<T> p[4];
  28    T length;  // Approximate
  29
  30    BezierCurve(Vector<T> p1, Vector<T> p2, Vector<T> p3, Vector<T> p4)
  31    {
  32       p[0] = p1;
  33       p[1] = p2;
  34       p[2] = p3;
  35       p[3] = p4;
  36
  37       // Approximate the length
  38       Vector<T> cur = operator()(0.0), prev;
  39
  40       length = 0.0;
  41
  42       const T step = static_cast<T>(0.0001);
  43       const T max = static_cast<T>(1.0);
  44
  45       for (T t = step; t <= max; t += step) {
  46          prev = cur;
  47          cur = operator()(t);
  48
  49          const Vector<T> diff = cur - prev;
  50
  51          length += diff.length();
  52       }
  53    }
  54
  55    BezierCurve()
  56       : length(0)
  57    {
  58
  59    }
  60
  61    Vector<T> operator()(T t) const
  62    {
  63       return make_vector
  64          (// X
  65           p[0].x * (1 - t) * (1 - t) * (1 - t)
  66           + p[1].x * 3 * t * (1 - t) * (1 - t)
  67           + p[2].x * 3 * t * t * (1 - t)
  68           + p[3].x * t * t * t,
  69
  70           // Y
  71           p[0].y * (1 - t) * (1 - t) * (1 - t)
  72           + p[1].y * 3 * t * (1 - t) * (1 - t)
  73           + p[2].y * 3 * t * t * (1 - t)
  74           + p[3].y * t * t * t,
  75
  76           // Z
  77           p[0].z * (1 - t) * (1 - t) * (1 - t)
  78           + p[1].z * 3 * t * (1 - t) * (1 - t)
  79           + p[2].z * 3 * t * t * (1 - t)
  80           + p[3].z * t * t * t
  81           );
  82    }
  83
  84    // A slower approximation to the curve function that guarantees
  85    // a linear relationship between s and the arc length
  86    Vector<T> linear(T s, T *out = NULL) const
  87    {
  88       Vector<T> cur = operator()(0.0), prev;
  89
  90       T now = static_cast<T>(0.0);
  91       const T target = length * s;
  92
  93       const T step = static_cast<T>(0.0001);
  94       const T max = static_cast<T>(1.0);
  95
  96       // TODO: could speed this up using a lookup table
  97       T t;
  98       for (t = step; t <= max && now < target; t += step) {
  99          prev = cur;
 100          cur = operator()(t);
 101
 102          const Vector<T> diff = cur - prev;
 103          now += diff.length();
 104       }
 105
 106       if (out)
 107          *out = std::max(static_cast<T>(0.0),
 108                          std::min(t, static_cast<T>(1.0)));
 109       return cur;
 110    }
 111
 112    // The derivative with respect to t at a point
 113    Vector<T> deriv(T t) const
 114    {
 115       return make_vector
 116          (// X
 117           p[0].x * -3 * (1 - t) * (1 - t)
 118           + p[1].x * (3 - 12*t + 9*t*t)
 119           + p[2].x * (6*t - 9*t*t)
 120           + p[3].x * 3 * t * t,
 121
 122           // Y
 123           p[0].y * -3 * (1 - t) * (1 - t)
 124           + p[1].y * (3 - 12*t + 9*t*t)
 125           + p[2].y * (6*t - 9*t*t)
 126           + p[3].y * 3 * t * t,
 127
 128           // Z
 129           p[0].z * -3 * (1 - t) * (1 - t)
 130           + p[1].z * (3 - 12*t + 9*t*t)
 131           + p[2].z * (6*t - 9*t*t)
 132           + p[3].z * 3 * t * t
 133           );
 134    }
 135
 136    // Value of the function at a constant radius in the XZ-plane
 137    Vector<T> offset(T t, T p) const
 138    {
 139       Vector<T> v = (*this)(t);
 140       const Vector<T> d = deriv(t);
 141
 142       const T o =
 143          p / sqrt((d.x * d.x) + (d.z * d.z));
 144
 145       v.x += o * d.z;
 146       v.z -= o * d.x;
 147
 148       return v;
 149    }
 150 };
 151
 152 // Generate Bezier curves
 153 template <typename T>
 154 BezierCurve<T> make_bezier_curve(Vector<T> p1, Vector<T> p2,
 155                                Vector<T> p3, Vector<T> p4)
 156 {
 157    return BezierCurve<T>(p1, p2, p3, p4);
 158 }
 159
 160 #endif
 161