absence_thelab
view src/common/curves.cpp @ 1:4d5933c261c3
todo and .hgignore
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Thu, 23 Oct 2014 02:18:43 +0300 |
| parents | |
| children |
line source
1 #include <cmath>
2 #include "curves.h"
4 Curve::Curve() {
5 ArcParametrize = false;
6 ease_curve = 0;
7 Samples = 0;
9 SetEaseSampleCount(100);
10 }
12 Curve::~Curve() {
13 delete [] Samples;
15 }
17 void Curve::SetArcParametrization(bool state) {
18 ArcParametrize = state;
19 }
21 #define Param 0
22 #define ArcLen 1
24 void Curve::SampleArcLengths() {
25 const int SamplesPerSegment = 30;
26 SampleCount = GetSegmentCount() * SamplesPerSegment;
28 ArcParametrize = false; // to be able to interpolate with the original values
30 Samples = new Vector2[SampleCount];
31 Vector3 prevpos;
32 float step = 1.0f / (float)(SampleCount-1);
33 for(int i=0; i<SampleCount; i++) {
34 float t = step * (float)i;
35 Vector3 pos = Interpolate(t);
36 Samples[i][Param] = t;
37 if(!i) {
38 Samples[i][ArcLen] = 0.0f;
39 } else {
40 Samples[i][ArcLen] = (pos - prevpos).Length() + Samples[i-1][ArcLen];
41 }
42 prevpos = pos;
43 }
45 // normalize arc lenghts
46 float maxlen = Samples[SampleCount-1][ArcLen];
47 for(int i=0; i<SampleCount; i++) {
48 Samples[i][ArcLen] /= maxlen;
49 }
51 ArcParametrize = true;
52 }
54 int BinarySearch(Vector2 *array, float key, int begin, int end) {
55 int middle = begin + ((end - begin)>>1);
57 if(array[middle][ArcLen] == key) return middle;
58 if(end == begin) return middle;
60 if(key < array[middle][ArcLen]) return BinarySearch(array, key, begin, middle);
61 if(key > array[middle][ArcLen]) return BinarySearch(array, key, middle+1, end);
62 return -1; // just to make the compiler shut the fuck up
63 }
65 float Curve::Parametrize(float t) {
66 if(!Samples) SampleArcLengths();
68 int samplepos = BinarySearch(Samples, t, 0, SampleCount);
69 float par = Samples[samplepos][Param];
70 float len = Samples[samplepos][ArcLen];
71 if((len - t) < XSmallNumber) return par;
73 if(len < t) {
74 if(!samplepos) return par;
75 float prevlen = Samples[samplepos-1][ArcLen];
76 float prevpar = Samples[samplepos-1][Param];
77 float p = (t - prevlen) / (len - prevlen);
78 return prevpar + (par - prevpar) * p;
79 } else {
80 if(samplepos >= SampleCount) return par;
81 float nextlen = Samples[samplepos+1][ArcLen];
82 float nextpar = Samples[samplepos+1][Param];
83 float p = (t - len) / (nextlen - len);
84 return par + (nextpar - par) * p;
85 }
87 return par; // not gonna happen
88 }
91 #define MIN(a, b) ((a) < (b) ? (a) : (b))
92 #define MAX(a, b) ((a) > (b) ? (a) : (b))
94 float Curve::Ease(float t) {
95 if(!ease_curve) return t;
97 ease_curve->SetArcParametrization(true);
98 float et = ease_curve->Interpolate(t).y;
100 return MIN(MAX(et, 0.0f), 1.0f);
101 }
104 void Curve::AddControlPoint(const Vector3 &cp) {
105 ControlPoints.PushBack(cp);
106 delete [] Samples;
107 Samples = 0;
108 }
110 void Curve::SetEaseCurve(Curve *curve) {
111 ease_curve = curve;
112 }
114 void Curve::SetEaseSampleCount(int count) {
115 ease_sample_count = count;
116 ease_step = 1.0f / ease_sample_count;
117 }
120 ///////////////// B-Spline implementation ////////////////////
122 int BSpline::GetSegmentCount() const {
123 return ControlPoints.Size() - 3;
124 }
126 Vector3 BSpline::Interpolate(float t) {
128 if(ControlPoints.Size() < 4) return Vector3(0, 0, 0);
130 if(ArcParametrize) {
131 t = Ease(Parametrize(t));
132 }
134 // find the appropriate segment of the spline that t lies and calculate the piecewise parameter
135 t = (float)(ControlPoints.Size() - 3) * t;
136 int seg = (int)t;
137 t -= (float)floor(t);
138 if(seg >= GetSegmentCount()) {
139 seg = GetSegmentCount() - 1;
140 t = 1.0f;
141 }
143 ListNode<Vector3> *iter = ControlPoints.Begin();
144 for(int i=0; i<seg; i++) iter = iter->next;
146 Vector3 Cp[4];
147 for(int i=0; i<4; i++) {
148 Cp[i] = iter->data;
149 iter = iter->next;
150 }
152 Matrix4x4 BSplineMat(-1, 3, -3, 1, 3, -6, 3, 0, -3, 0, 3, 0, 1, 4, 1, 0);
153 BSplineMat.Transpose();
154 Vector4 Params(t*t*t, t*t, t, 1);
155 Vector4 CpX(Cp[0].x, Cp[1].x, Cp[2].x, Cp[3].x);
156 Vector4 CpY(Cp[0].y, Cp[1].y, Cp[2].y, Cp[3].y);
157 Vector4 CpZ(Cp[0].z, Cp[1].z, Cp[2].z, Cp[3].z);
159 CpX.Transform(BSplineMat);
160 CpY.Transform(BSplineMat);
161 CpZ.Transform(BSplineMat);
163 CpX /= 6.0f;
164 CpY /= 6.0f;
165 CpZ /= 6.0f;
167 Vector3 res;
169 res.x = Params.DotProduct(CpX);
170 res.y = Params.DotProduct(CpY);
171 res.z = Params.DotProduct(CpZ);
173 return res;
174 }
176 //////////////// Catmull-Rom Spline implementation //////////////////
178 int CatmullRomSpline::GetSegmentCount() const {
179 return ControlPoints.Size() - 1;
180 }
182 Vector3 CatmullRomSpline::Interpolate(float t) {
184 if(ControlPoints.Size() < 2) return Vector3(0, 0, 0);
186 if(ArcParametrize) {
187 t = Ease(Parametrize(t));
188 }
190 // find the appropriate segment of the spline that t lies and calculate the piecewise parameter
191 t = (float)(ControlPoints.Size() - 1) * t;
192 int seg = (int)t;
193 t -= (float)floor(t);
194 if(seg >= GetSegmentCount()) {
195 seg = GetSegmentCount() - 1;
196 t = 1.0f;
197 }
199 Vector3 Cp[4];
200 ListNode<Vector3> *iter = ControlPoints.Begin();
201 for(int i=0; i<seg; i++) iter = iter->next;
203 Cp[1] = iter->data;
204 Cp[2] = iter->next->data;
206 if(!seg) {
207 Cp[0] = Cp[1];
208 } else {
209 Cp[0] = iter->prev->data;
210 }
212 if(seg == ControlPoints.Size() - 2) {
213 Cp[3] = Cp[2];
214 } else {
215 Cp[3] = iter->next->next->data;
216 }
218 Matrix4x4 BSplineMat(-1, 3, -3, 1, 2, -5, 4, -1, -1, 0, 1, 0, 0, 2, 0, 0);
219 BSplineMat.Transpose();
220 Vector4 Params(t*t*t, t*t, t, 1);
221 Vector4 CpX(Cp[0].x, Cp[1].x, Cp[2].x, Cp[3].x);
222 Vector4 CpY(Cp[0].y, Cp[1].y, Cp[2].y, Cp[3].y);
223 Vector4 CpZ(Cp[0].z, Cp[1].z, Cp[2].z, Cp[3].z);
225 CpX.Transform(BSplineMat);
226 CpY.Transform(BSplineMat);
227 CpZ.Transform(BSplineMat);
229 CpX /= 2.0f;
230 CpY /= 2.0f;
231 CpZ /= 2.0f;
233 Vector3 res;
235 res.x = Params.DotProduct(CpX);
236 res.y = Params.DotProduct(CpY);
237 res.z = Params.DotProduct(CpZ);
239 return res;
240 }