curvedraw

annotate src/curve.cc @ 12:84a647283237

find changesets by author, revision, files, or words in the commit message
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
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@12 265 /* Projection to the curve is not correct, but should be good enough for
nuclear@12 266 * most purposes.
nuclear@12 267 *
nuclear@12 268 * First we find the nearest segment (pair of control points), and then
nuclear@12 269 * we subdivide between them to find the nearest interpolated point in that
nuclear@12 270 * segment.
nuclear@12 271 * The incorrect assumption here is that the nearest segment as defined by
nuclear@12 272 * the distance of its control points to p, will contain the nearest point
nuclear@12 273 * on the curve. This only holds for polylines, and *possibly* bsplines, but
nuclear@12 274 * certainly not hermite splines.
nuclear@12 275 */
nuclear@12 276 Vector3 Curve::proj_point(const Vector3 &p) const
nuclear@12 277 {
nuclear@12 278 // TODO fix: select nearest segment based on point-line distance, not distance from the CPs
nuclear@12 279 int num_cp = size();
nuclear@12 280 if(num_cp <= 0) return p;
nuclear@12 281 if(num_cp == 1) return cp[0];
nuclear@12 282
nuclear@12 283 int idx0 = nearest_point(p);
nuclear@12 284 int next_idx = idx0 + 1;
nuclear@12 285 int prev_idx = idx0 - 1;
nuclear@12 286
nuclear@12 287 float next_distsq = next_idx >= num_cp ? FLT_MAX : (get_point3(next_idx) - p).length_sq();
nuclear@12 288 float prev_distsq = prev_idx < 0 ? FLT_MAX : (get_point3(prev_idx) - p).length_sq();
nuclear@12 289 int idx1 = next_distsq < prev_distsq ? next_idx : prev_idx;
nuclear@12 290 assert(idx1 >= 0 && idx1 < num_cp - 1);
nuclear@12 291 if(idx0 > idx1) std::swap(idx0, idx1);
nuclear@12 292
nuclear@12 293 float t0 = 0.0f, t1 = 1.0f;
nuclear@12 294 Vector3 pp0 = interpolate_segment(idx0, idx1, 0.0f);
nuclear@12 295 Vector3 pp1 = interpolate_segment(idx0, idx1, 1.0f);
nuclear@12 296 float dist0 = (pp0 - p).length_sq();
nuclear@12 297 float dist1 = (pp1 - p).length_sq();
nuclear@12 298 Vector3 pp;
nuclear@12 299
nuclear@12 300 for(int i=0; i<32; i++) { // max iterations
nuclear@12 301 float t = (t0 + t1) / 2.0;
nuclear@12 302 pp = interpolate_segment(idx0, idx1, t);
nuclear@12 303 float dist = (pp - p).length_sq();
nuclear@12 304
nuclear@12 305 // mid point more distant than both control points, nearest cp is closest
nuclear@12 306 if(dist > dist0 && dist > dist1) {
nuclear@12 307 pp = dist0 < dist1 ? pp0 : pp1;
nuclear@12 308 break;
nuclear@12 309 }
nuclear@12 310
nuclear@12 311 if(dist0 < dist1) {
nuclear@12 312 t1 = t;
nuclear@12 313 dist1 = dist;
nuclear@12 314 pp1 = pp;
nuclear@12 315 } else {
nuclear@12 316 t0 = t;
nuclear@12 317 dist0 = dist;
nuclear@12 318 pp0 = pp;
nuclear@12 319 }
nuclear@12 320
nuclear@12 321 if(fabs(dist0 - dist1) < 1e-4) {
nuclear@12 322 break;
nuclear@12 323 }
nuclear@12 324 }
nuclear@12 325 return pp;
nuclear@12 326 }
nuclear@12 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@12 349 }
nuclear@12 350 }
nuclear@12 351 }
nuclear@12 352
nuclear@12 353 return Vector3(res.x, res.y, res.z);
nuclear@12 354 }
nuclear@12 355
nuclear@12 356 Vector3 Curve::interpolate(float t) const
nuclear@12 357 {
nuclear@12 358 if(empty()) {
nuclear@12 359 return Vector3(0, 0, 0);
nuclear@0 360 }
nuclear@2 361
nuclear@2 362 int num_cp = (int)cp.size();
nuclear@0 363 if(num_cp == 1) {
nuclear@12 364 return Vector3(cp[0].x, cp[0].y, cp[0].z);
nuclear@0 365 }
nuclear@0 366
nuclear@2 367 int idx0 = std::min((int)floor(t * (num_cp - 1)), num_cp - 2);
nuclear@0 368 int idx1 = idx0 + 1;
nuclear@0 369
nuclear@0 370 float dt = 1.0 / (float)(num_cp - 1);
nuclear@0 371 float t0 = (float)idx0 * dt;
nuclear@0 372 float t1 = (float)idx1 * dt;
nuclear@0 373
nuclear@0 374 t = (t - t0) / (t1 - t0);
nuclear@0 375
nuclear@12 376 return interpolate_segment(idx0, idx1, t);
nuclear@12 377 }
nuclear@0 378
nuclear@12 379 Vector2 Curve::interpolate2(float t) const
nuclear@12 380 {
nuclear@12 381 Vector3 res = interpolate(t);
nuclear@0 382 return Vector2(res.x, res.y);
nuclear@0 383 }
nuclear@0 384
nuclear@12 385 Vector3 Curve::operator ()(float t) const
nuclear@0 386 {
nuclear@0 387 return interpolate(t);
nuclear@0 388 }