curvedraw
view src/curve.cc @ 12:84a647283237
added all the extra functionality to the curve class
first pass at a project-to-curve function (needs more work)
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Sun, 20 Dec 2015 07:21:32 +0200 |
| parents | 2b7ae76c173f |
| children | 4da693339d99 |
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 /* Projection to the curve is not correct, but should be good enough for
266 * most purposes.
267 *
268 * First we find the nearest segment (pair of control points), and then
269 * we subdivide between them to find the nearest interpolated point in that
270 * segment.
271 * The incorrect assumption here is that the nearest segment as defined by
272 * the distance of its control points to p, will contain the nearest point
273 * on the curve. This only holds for polylines, and *possibly* bsplines, but
274 * certainly not hermite splines.
275 */
276 Vector3 Curve::proj_point(const Vector3 &p) const
277 {
278 // TODO fix: select nearest segment based on point-line distance, not distance from the CPs
279 int num_cp = size();
280 if(num_cp <= 0) return p;
281 if(num_cp == 1) return cp[0];
283 int idx0 = nearest_point(p);
284 int next_idx = idx0 + 1;
285 int prev_idx = idx0 - 1;
287 float next_distsq = next_idx >= num_cp ? FLT_MAX : (get_point3(next_idx) - p).length_sq();
288 float prev_distsq = prev_idx < 0 ? FLT_MAX : (get_point3(prev_idx) - p).length_sq();
289 int idx1 = next_distsq < prev_distsq ? next_idx : prev_idx;
290 assert(idx1 >= 0 && idx1 < num_cp - 1);
291 if(idx0 > idx1) std::swap(idx0, idx1);
293 float t0 = 0.0f, t1 = 1.0f;
294 Vector3 pp0 = interpolate_segment(idx0, idx1, 0.0f);
295 Vector3 pp1 = interpolate_segment(idx0, idx1, 1.0f);
296 float dist0 = (pp0 - p).length_sq();
297 float dist1 = (pp1 - p).length_sq();
298 Vector3 pp;
300 for(int i=0; i<32; i++) { // max iterations
301 float t = (t0 + t1) / 2.0;
302 pp = interpolate_segment(idx0, idx1, t);
303 float dist = (pp - p).length_sq();
305 // mid point more distant than both control points, nearest cp is closest
306 if(dist > dist0 && dist > dist1) {
307 pp = dist0 < dist1 ? pp0 : pp1;
308 break;
309 }
311 if(dist0 < dist1) {
312 t1 = t;
313 dist1 = dist;
314 pp1 = pp;
315 } else {
316 t0 = t;
317 dist0 = dist;
318 pp0 = pp;
319 }
321 if(fabs(dist0 - dist1) < 1e-4) {
322 break;
323 }
324 }
325 return pp;
326 }
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 }
350 }
351 }
353 return Vector3(res.x, res.y, res.z);
354 }
356 Vector3 Curve::interpolate(float t) const
357 {
358 if(empty()) {
359 return Vector3(0, 0, 0);
360 }
362 int num_cp = (int)cp.size();
363 if(num_cp == 1) {
364 return Vector3(cp[0].x, cp[0].y, cp[0].z);
365 }
367 int idx0 = std::min((int)floor(t * (num_cp - 1)), num_cp - 2);
368 int idx1 = idx0 + 1;
370 float dt = 1.0 / (float)(num_cp - 1);
371 float t0 = (float)idx0 * dt;
372 float t1 = (float)idx1 * dt;
374 t = (t - t0) / (t1 - t0);
376 return interpolate_segment(idx0, idx1, t);
377 }
379 Vector2 Curve::interpolate2(float t) const
380 {
381 Vector3 res = interpolate(t);
382 return Vector2(res.x, res.y);
383 }
385 Vector3 Curve::operator ()(float t) const
386 {
387 return interpolate(t);
388 }