curvedraw

annotate src/curve.cc @ 15:37ab3a4c02f8

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