5f1ae46b8c924e493e5b73c955978b20ebc7f1e1
[traingame.git] / 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