curvedraw
view src/curve.cc @ 13:4da693339d99
- distance from curve
- hover/selection of curves directly on the curve
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Sun, 20 Dec 2015 08:22:24 +0200 |
| parents | 84a647283237 |
| children | 7f795f7fecd6 |
line source
1 #include <float.h>
2 #include <assert.h>
3 #include <algorithm>
4 #include "curve.h"
6 Curve::Curve(CurveType type)
7 {
8 this->type = type;
9 bbvalid = true;
10 }
12 Curve::Curve(const Vector4 *cp, int numcp, CurveType type)
13 : Curve(type)
14 {
15 this->cp.resize(numcp);
16 for(int i=0; i<numcp; i++) {
17 this->cp[i] = cp[i];
18 }
19 }
21 Curve::Curve(const Vector3 *cp, int numcp, CurveType type)
22 : Curve(type)
23 {
24 this->cp.resize(numcp);
25 for(int i=0; i<numcp; i++) {
26 this->cp[i] = Vector4(cp[i].x, cp[i].y, cp[i].z, 1.0f);
27 }
28 }
30 Curve::Curve(const Vector2 *cp, int numcp, CurveType type)
31 : Curve(type)
32 {
33 this->cp.resize(numcp);
34 for(int i=0; i<numcp; i++) {
35 this->cp[i] = Vector4(cp[i].x, cp[i].y, 0.0f, 1.0f);
36 }
37 }
39 void Curve::set_type(CurveType type)
40 {
41 this->type = type;
42 }
44 CurveType Curve::get_type() const
45 {
46 return type;
47 }
49 void Curve::add_point(const Vector4 &p)
50 {
51 cp.push_back(p);
52 inval_bounds();
53 }
55 void Curve::add_point(const Vector3 &p, float weight)
56 {
57 add_point(Vector4(p.x, p.y, p.z, weight));
58 }
60 void Curve::add_point(const Vector2 &p, float weight)
61 {
62 add_point(Vector4(p.x, p.y, 0.0f, weight));
63 }
65 bool Curve::remove_point(int idx)
66 {
67 if(idx < 0 || idx >= (int)cp.size()) {
68 return false;
69 }
70 cp.erase(cp.begin() + idx);
71 inval_bounds();
72 return true;
73 }
75 void Curve::clear()
76 {
77 cp.clear();
78 inval_bounds();
79 }
81 bool Curve::empty() const
82 {
83 return cp.empty();
84 }
86 int Curve::size() const
87 {
88 return (int)cp.size();
89 }
91 Vector4 &Curve::operator [](int idx)
92 {
93 inval_bounds();
94 return cp[idx];
95 }
97 const Vector4 &Curve::operator [](int idx) const
98 {
99 return cp[idx];
100 }
102 const Vector4 &Curve::get_point(int idx) const
103 {
104 return cp[idx];
105 }
107 Vector3 Curve::get_point3(int idx) const
108 {
109 return Vector3(cp[idx].x, cp[idx].y, cp[idx].z);
110 }
112 Vector2 Curve::get_point2(int idx) const
113 {
114 return Vector2(cp[idx].x, cp[idx].y);
115 }
117 float Curve::get_weight(int idx) const
118 {
119 return cp[idx].w;
120 }
122 bool Curve::set_point(int idx, const Vector3 &p, float weight)
123 {
124 if(idx < 0 || idx >= (int)cp.size()) {
125 return false;
126 }
127 cp[idx] = Vector4(p.x, p.y, p.z, weight);
128 inval_bounds();
129 return true;
130 }
132 bool Curve::set_point(int idx, const Vector2 &p, float weight)
133 {
134 if(idx < 0 || idx >= (int)cp.size()) {
135 return false;
136 }
137 cp[idx] = Vector4(p.x, p.y, 0.0, weight);
138 inval_bounds();
139 return true;
140 }
142 bool Curve::set_weight(int idx, float weight)
143 {
144 if(idx < 0 || idx >= (int)cp.size()) {
145 return false;
146 }
147 cp[idx].w = weight;
148 return true;
149 }
151 bool Curve::move_point(int idx, const Vector3 &p)
152 {
153 if(idx < 0 || idx >= (int)cp.size()) {
154 return false;
155 }
156 cp[idx] = Vector4(p.x, p.y, p.z, cp[idx].w);
157 inval_bounds();
158 return true;
159 }
161 bool Curve::move_point(int idx, const Vector2 &p)
162 {
163 if(idx < 0 || idx >= (int)cp.size()) {
164 return false;
165 }
166 cp[idx] = Vector4(p.x, p.y, 0.0f, cp[idx].w);
167 inval_bounds();
168 return true;
169 }
172 int Curve::nearest_point(const Vector3 &p) const
173 {
174 int res = -1;
175 float bestsq = FLT_MAX;
177 for(size_t i=0; i<cp.size(); i++) {
178 float d = (get_point3(i) - p).length_sq();
179 if(d < bestsq) {
180 bestsq = d;
181 res = i;
182 }
183 }
184 return res;
185 }
187 int Curve::nearest_point(const Vector2 &p) const
188 {
189 int res = -1;
190 float bestsq = FLT_MAX;
192 for(size_t i=0; i<cp.size(); i++) {
193 float d = (get_point2(i) - p).length_sq();
194 if(d < bestsq) {
195 bestsq = d;
196 res = i;
197 }
198 }
199 return res;
200 }
203 void Curve::inval_bounds() const
204 {
205 bbvalid = false;
206 }
208 void Curve::calc_bounds() const
209 {
210 calc_bbox(&bbmin, &bbmax);
211 bbvalid = true;
212 }
214 void Curve::get_bbox(Vector3 *bbmin, Vector3 *bbmax) const
215 {
216 if(!bbvalid) {
217 calc_bounds();
218 }
219 *bbmin = this->bbmin;
220 *bbmax = this->bbmax;
221 }
223 void Curve::calc_bbox(Vector3 *bbmin, Vector3 *bbmax) const
224 {
225 if(empty()) {
226 *bbmin = *bbmax = Vector3(0, 0, 0);
227 return;
228 }
230 Vector3 bmin = cp[0];
231 Vector3 bmax = bmin;
232 for(size_t i=1; i<cp.size(); i++) {
233 const Vector4 &v = cp[i];
234 for(int j=0; j<3; j++) {
235 if(v[j] < bmin[j]) bmin[j] = v[j];
236 if(v[j] > bmax[j]) bmax[j] = v[j];
237 }
238 }
239 *bbmin = bmin;
240 *bbmax = bmax;
241 }
243 void Curve::normalize()
244 {
245 if(!bbvalid) {
246 calc_bounds();
247 }
249 Vector3 bsize = bbmax - bbmin;
250 Vector3 boffs = (bbmin + bbmax) * 0.5;
252 Vector3 bscale;
253 bscale.x = bsize.x == 0.0f ? 1.0f : 1.0f / bsize.x;
254 bscale.y = bsize.y == 0.0f ? 1.0f : 1.0f / bsize.y;
255 bscale.z = bsize.z == 0.0f ? 1.0f : 1.0f / bsize.z;
257 for(size_t i=0; i<cp.size(); i++) {
258 cp[i].x = (cp[i].x - boffs.x) * bscale.x;
259 cp[i].y = (cp[i].y - boffs.y) * bscale.y;
260 cp[i].z = (cp[i].z - boffs.z) * bscale.z;
261 }
262 inval_bounds();
263 }
265 Vector3 Curve::proj_point(const Vector3 &p, float refine_thres) const
266 {
267 // first step through the curve a few times and find the nearest of them
268 int num_cp = size();
269 int num_steps = num_cp * 5; // arbitrary number; sounds ok
270 float dt = 1.0f / (float)(num_steps - 1);
272 float best_distsq = FLT_MAX;
273 float best_t = 0.0f;
274 Vector3 best_pp;
276 float t = 0.0f;
277 for(int i=0; i<num_steps; i++) {
278 Vector3 pp = interpolate(t);
279 float distsq = (pp - p).length_sq();
280 if(distsq < best_distsq) {
281 best_distsq = distsq;
282 best_pp = pp;
283 best_t = t;
284 }
285 t += dt;
286 }
288 // refine by gradient descent
289 float dist = best_distsq;
290 t = best_t;
291 dt *= 0.05;
292 for(;;) {
293 float tn = t + dt;
294 float tp = t - dt;
296 float dn = (interpolate(tn) - p).length_sq();
297 float dp = (interpolate(tp) - p).length_sq();
299 if(fabs(dn - dp) < refine_thres * refine_thres) {
300 break;
301 }
303 if(dn < dist) {
304 t = tn;
305 dist = dn;
306 } else if(dp < dist) {
307 t = tp;
308 dist = dp;
309 } else {
310 break; // found the minimum
311 }
312 }
314 return interpolate(t);
315 }
317 float Curve::distance(const Vector3 &p) const
318 {
319 return (proj_point(p) - p).length();
320 }
322 float Curve::distance_sq(const Vector3 &p) const
323 {
324 return fabs((proj_point(p) - p).length_sq());
325 }
328 Vector3 Curve::interpolate_segment(int a, int b, float t) const
329 {
330 int num_cp = size();
332 if(t < 0.0) t = 0.0;
333 if(t > 1.0) t = 1.0;
335 Vector4 res;
336 if(type == CURVE_LINEAR || num_cp == 2) {
337 res = lerp(cp[a], cp[b], t);
338 } else {
339 int prev = a <= 0 ? a : a - 1;
340 int next = b >= num_cp - 1 ? b : b + 1;
342 if(type == CURVE_HERMITE) {
343 res = catmull_rom_spline(cp[prev], cp[a], cp[b], cp[next], t);
344 } else {
345 res = bspline(cp[prev], cp[a], cp[b], cp[next], t);
346 if(res.w != 0.0f) {
347 res.x /= res.w;
348 res.y /= res.w;
349 res.z /= res.w;
350 }
351 }
352 }
354 return Vector3(res.x, res.y, res.z);
355 }
357 Vector3 Curve::interpolate(float t) const
358 {
359 if(empty()) {
360 return Vector3(0, 0, 0);
361 }
363 int num_cp = (int)cp.size();
364 if(num_cp == 1) {
365 return Vector3(cp[0].x, cp[0].y, cp[0].z);
366 }
368 if(t < 0.0) t = 0.0;
369 if(t > 1.0) t = 1.0;
371 int idx0 = std::min((int)floor(t * (num_cp - 1)), num_cp - 2);
372 int idx1 = idx0 + 1;
374 float dt = 1.0 / (float)(num_cp - 1);
375 float t0 = (float)idx0 * dt;
376 float t1 = (float)idx1 * dt;
378 t = (t - t0) / (t1 - t0);
380 return interpolate_segment(idx0, idx1, t);
381 }
383 Vector2 Curve::interpolate2(float t) const
384 {
385 Vector3 res = interpolate(t);
386 return Vector2(res.x, res.y);
387 }
389 Vector3 Curve::operator ()(float t) const
390 {
391 return interpolate(t);
392 }