Blender V5.3
FitCurve.cpp
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2008-2022 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
10
11#include <cmath>
12#include <cstdio>
13#include <cstdlib> // for malloc and free
14
15#include "FitCurve.h"
16
17#include "BLI_sys_types.hh"
18
19using namespace std;
20
21namespace Freestyle {
22
24
25/* Forward declarations */
26static double *Reparameterize(
27 Vector2 *d, int first, int last, double *u, BezierCurvePoints2D bezCurve);
28static double NewtonRaphsonRootFind(BezierCurvePoints2D Q, Vector2 P, double u);
29static Vector2 BezierII(int degree, Vector2 *V, double t);
30static double B0(double u);
31static double B1(double u);
32static double B2(double u);
33static double B3(double u);
34static Vector2 ComputeLeftTangent(Vector2 *d, int end);
35static double ComputeMaxError(
36 Vector2 *d, int first, int last, BezierCurvePoints2D bezCurve, double *u, int *splitPoint);
37static double *ChordLengthParameterize(Vector2 *d, int first, int last);
39 Vector2 *d, int first, int last, double *uPrime, Vector2 tHat1, Vector2 tHat2);
41static Vector2 V2ScaleIII(Vector2 v, double s);
43
44/* returns squared length of input vector */
45static double V2SquaredLength(Vector2 *a)
46{
47 return (((*a)[0] * (*a)[0]) + ((*a)[1] * (*a)[1]));
48}
49
50/* returns length of input vector */
51static double V2Length(Vector2 *a)
52{
53 return sqrt(V2SquaredLength(a));
54}
55
56static Vector2 *V2Scale(Vector2 *v, double newlen)
57{
58 double len = V2Length(v);
59 if (len != 0.0) {
60 (*v)[0] *= newlen / len;
61 (*v)[1] *= newlen / len;
62 }
63 return v;
64}
65
66/* return the dot product of vectors a and b */
67static double V2Dot(Vector2 *a, Vector2 *b)
68{
69 return (((*a)[0] * (*b)[0]) + ((*a)[1] * (*b)[1]));
70}
71
72/* return the distance between two points */
74{
75 double dx = (*a)[0] - (*b)[0];
76 double dy = (*a)[1] - (*b)[1];
77 return sqrt((dx * dx) + (dy * dy));
78}
79
80/* return vector sum c = a+b */
82{
83 (*c)[0] = (*a)[0] + (*b)[0];
84 (*c)[1] = (*a)[1] + (*b)[1];
85 return c;
86}
87
88/* normalizes the input vector and returns it */
90{
91 double len = V2Length(v);
92 if (len != 0.0) {
93 (*v)[0] /= len;
94 (*v)[1] /= len;
95 }
96 return v;
97}
98
99/* negates the input vector and returns it */
101{
102 (*v)[0] = -(*v)[0];
103 (*v)[1] = -(*v)[1];
104 return v;
105}
106
107/* GenerateBezier:
108 * Use least-squares method to find Bezier control points for region.
109 * Vector2 *d; Array of digitized points
110 * int first, last; Indices defining region
111 * double *uPrime; Parameter values for region
112 * Vector2 tHat1, tHat2; Unit tangents at endpoints
113 */
115 Vector2 *d, int first, int last, double *uPrime, Vector2 tHat1, Vector2 tHat2)
116{
117 int i;
118 Vector2 A[2]; /* rhs for eqn */
119 int nPts; /* Number of pts in sub-curve */
120 double C[2][2]; /* Matrix C */
121 double X[2]; /* Matrix X */
122 double det_C0_C1; /* Determinants of matrices */
123 double det_C0_X;
124 double det_X_C1;
125 double alpha_l; /* Alpha values, left and right */
126 double alpha_r;
127 Vector2 tmp; /* Utility variable */
128 BezierCurvePoints2D bezCurve; /* RETURN bezier curve control points. */
129
130 bezCurve = (Vector2 *)malloc(4 * sizeof(Vector2));
131 nPts = last - first + 1;
132
133 /* Create the C and X matrices */
134 C[0][0] = 0.0;
135 C[0][1] = 0.0;
136 C[1][0] = 0.0;
137 C[1][1] = 0.0;
138 X[0] = 0.0;
139 X[1] = 0.0;
140 for (i = 0; i < nPts; i++) {
141 /* Compute the A's */
142 A[0] = tHat1;
143 A[1] = tHat2;
144 V2Scale(&A[0], B1(uPrime[i]));
145 V2Scale(&A[1], B2(uPrime[i]));
146
147 C[0][0] += V2Dot(&A[0], &A[0]);
148 C[0][1] += V2Dot(&A[0], &A[1]);
149 // C[1][0] += V2Dot(&A[0], &A[1]);
150 C[1][0] = C[0][1];
151 C[1][1] += V2Dot(&A[1], &A[1]);
152
153 tmp = V2SubII(d[first + i],
154 V2AddII(V2ScaleIII(d[first], B0(uPrime[i])),
155 V2AddII(V2ScaleIII(d[first], B1(uPrime[i])),
156 V2AddII(V2ScaleIII(d[last], B2(uPrime[i])),
157 V2ScaleIII(d[last], B3(uPrime[i]))))));
158
159 X[0] += V2Dot(&A[0], &tmp);
160 X[1] += V2Dot(&A[1], &tmp);
161 }
162
163 /* Compute the determinants of C and X */
164 det_C0_C1 = C[0][0] * C[1][1] - C[1][0] * C[0][1];
165 det_C0_X = C[0][0] * X[1] - C[0][1] * X[0];
166 det_X_C1 = X[0] * C[1][1] - X[1] * C[0][1];
167
168 /* Finally, derive alpha values */
169 if (det_C0_C1 == 0.0) {
170 det_C0_C1 = (C[0][0] * C[1][1]) * 10.0e-12;
171 }
172 alpha_l = det_X_C1 / det_C0_C1;
173 alpha_r = det_C0_X / det_C0_C1;
174
175 /* If alpha negative, use the Wu/Barsky heuristic (see text) (if alpha is 0, you get coincident
176 * control points that lead to divide by zero in any subsequent NewtonRaphsonRootFind() call).
177 */
178 if (alpha_l < 1.0e-6 || alpha_r < 1.0e-6) {
179 double dist = V2DistanceBetween2Points(&d[last], &d[first]) / 3.0;
180
181 bezCurve[0] = d[first];
182 bezCurve[3] = d[last];
183 V2Add(&(bezCurve[0]), V2Scale(&(tHat1), dist), &(bezCurve[1]));
184 V2Add(&(bezCurve[3]), V2Scale(&(tHat2), dist), &(bezCurve[2]));
185 return bezCurve;
186 }
187
188 /* First and last control points of the Bezier curve are positioned exactly at the first and last
189 * data points Control points 1 and 2 are positioned an alpha distance out on the tangent
190 * vectors, left and right, respectively
191 */
192 bezCurve[0] = d[first];
193 bezCurve[3] = d[last];
194 V2Add(&bezCurve[0], V2Scale(&tHat1, alpha_l), &bezCurve[1]);
195 V2Add(&bezCurve[3], V2Scale(&tHat2, alpha_r), &bezCurve[2]);
196 return bezCurve;
197}
198
199/*
200 * Reparameterize:
201 * Given set of points and their parameterization, try to find a better parameterization.
202 * Vector2 *d; Array of digitized points
203 * int first, last; Indices defining region
204 * double *u; Current parameter values
205 * BezierCurve bezCurve; Current fitted curve
206 */
207static double *Reparameterize(
208 Vector2 *d, int first, int last, double *u, BezierCurvePoints2D bezCurve)
209{
210 int nPts = last - first + 1;
211 int i;
212 double *uPrime; /* New parameter values */
213
214 uPrime = (double *)malloc(nPts * sizeof(double));
215 for (i = first; i <= last; i++) {
216 uPrime[i - first] = NewtonRaphsonRootFind(bezCurve, d[i], u[i - first]);
217 }
218 return uPrime;
219}
220
221/*
222 * NewtonRaphsonRootFind:
223 * Use Newton-Raphson iteration to find better root.
224 * BezierCurve Q; Current fitted curve
225 * Vector2 P; Digitized point
226 * double u; Parameter value for "P"
227 */
229{
230 double numerator, denominator;
231 Vector2 Q1[3], Q2[2]; /* Q' and Q'' */
232 Vector2 Q_u, Q1_u, Q2_u; /* u evaluated at Q, Q', & Q'' */
233 double uPrime; /* Improved u */
234 int i;
235
236 /* Compute Q(u) */
237 Q_u = BezierII(3, Q, u);
238
239 /* Generate control vertices for Q' */
240 for (i = 0; i <= 2; i++) {
241 Q1[i][0] = (Q[i + 1][0] - Q[i][0]) * 3.0;
242 Q1[i][1] = (Q[i + 1][1] - Q[i][1]) * 3.0;
243 }
244
245 /* Generate control vertices for Q'' */
246 for (i = 0; i <= 1; i++) {
247 Q2[i][0] = (Q1[i + 1][0] - Q1[i][0]) * 2.0;
248 Q2[i][1] = (Q1[i + 1][1] - Q1[i][1]) * 2.0;
249 }
250
251 /* Compute Q'(u) and Q''(u) */
252 Q1_u = BezierII(2, Q1, u);
253 Q2_u = BezierII(1, Q2, u);
254
255 /* Compute f(u)/f'(u) */
256 numerator = (Q_u[0] - P[0]) * (Q1_u[0]) + (Q_u[1] - P[1]) * (Q1_u[1]);
257 denominator = (Q1_u[0]) * (Q1_u[0]) + (Q1_u[1]) * (Q1_u[1]) + (Q_u[0] - P[0]) * (Q2_u[0]) +
258 (Q_u[1] - P[1]) * (Q2_u[1]);
259
260 /* u = u - f(u)/f'(u) */
261 if (denominator == 0) { // FIXME
262 return u;
263 }
264 uPrime = u - (numerator / denominator);
265 return uPrime;
266}
267
268/*
269 * Bezier:
270 * Evaluate a Bezier curve at a particular parameter value
271 * int degree; The degree of the bezier curve
272 * Vector2 *V; Array of control points
273 * double t; Parametric value to find point for
274 */
275static Vector2 BezierII(int degree, Vector2 *V, double t)
276{
277 int i, j;
278 Vector2 Q; /* Point on curve at parameter t */
279 Vector2 *Vtemp; /* Local copy of control points */
280
281 /* Copy array */
282 Vtemp = (Vector2 *)malloc(uint((degree + 1) * sizeof(Vector2)));
283 for (i = 0; i <= degree; i++) {
284 Vtemp[i] = V[i];
285 }
286
287 /* Triangle computation */
288 for (i = 1; i <= degree; i++) {
289 for (j = 0; j <= degree - i; j++) {
290 Vtemp[j][0] = (1.0 - t) * Vtemp[j][0] + t * Vtemp[j + 1][0];
291 Vtemp[j][1] = (1.0 - t) * Vtemp[j][1] + t * Vtemp[j + 1][1];
292 }
293 }
294
295 Q = Vtemp[0];
296 free((void *)Vtemp);
297 return Q;
298}
299
300/*
301 * B0, B1, B2, B3:
302 * Bezier multipliers
303 */
304static double B0(double u)
305{
306 double tmp = 1.0 - u;
307 return (tmp * tmp * tmp);
308}
309
310static double B1(double u)
311{
312 double tmp = 1.0 - u;
313 return (3 * u * (tmp * tmp));
314}
315
316static double B2(double u)
317{
318 double tmp = 1.0 - u;
319 return (3 * u * u * tmp);
320}
321
322static double B3(double u)
323{
324 return (u * u * u);
325}
326
327/*
328 * ComputeLeftTangent, ComputeRightTangent, ComputeCenterTangent:
329 * Approximate unit tangents at endpoints and "center" of digitized curve
330 */
331/* Vector2 *d; Digitized points
332 * int end; Index to "left" end of region
333 */
335{
336 Vector2 tHat1;
337 tHat1 = V2SubII(d[end + 1], d[end]);
338 tHat1 = *V2Normalize(&tHat1);
339 return tHat1;
340}
341
342/* Vector2 *d; Digitized points
343 * int end; Index to "right" end of region
344 */
346{
347 Vector2 tHat2;
348 tHat2 = V2SubII(d[end - 1], d[end]);
349 tHat2 = *V2Normalize(&tHat2);
350 return tHat2;
351}
352
353/* Vector2 *d; Digitized points
354 * int end; Index to point inside region
355 */
357{
358 Vector2 V1, V2, tHatCenter;
359
360 V1 = V2SubII(d[center - 1], d[center]);
361 V2 = V2SubII(d[center], d[center + 1]);
362 tHatCenter[0] = (V1[0] + V2[0]) / 2.0;
363 tHatCenter[1] = (V1[1] + V2[1]) / 2.0;
364 tHatCenter = *V2Normalize(&tHatCenter);
365
366 /* avoid numerical singularity in the special case when V1 == -V2 */
367 if (V2Length(&tHatCenter) < M_EPSILON) {
368 tHatCenter = *V2Normalize(&V1);
369 }
370
371 return tHatCenter;
372}
373
374/*
375 * ChordLengthParameterize:
376 * Assign parameter values to digitized points using relative distances between points.
377 * Vector2 *d; Array of digitized points
378 * int first, last; Indices defining region
379 */
380static double *ChordLengthParameterize(Vector2 *d, int first, int last)
381{
382 int i;
383 double *u; /* Parameterization */
384
385 u = (double *)malloc(uint(last - first + 1) * sizeof(double));
386
387 u[0] = 0.0;
388 for (i = first + 1; i <= last; i++) {
389 u[i - first] = u[i - first - 1] + V2DistanceBetween2Points(&d[i], &d[i - 1]);
390 }
391
392 for (i = first + 1; i <= last; i++) {
393 u[i - first] = u[i - first] / u[last - first];
394 }
395
396 return u;
397}
398
399/*
400 * ComputeMaxError :
401 * Find the maximum squared distance of digitized points to fitted curve.
402 * Vector2 *d; Array of digitized points
403 * int first, last; Indices defining region
404 * BezierCurve bezCurve; Fitted Bezier curve
405 * double *u; Parameterization of points
406 * int *splitPoint; Point of maximum error
407 */
408static double ComputeMaxError(
409 Vector2 *d, int first, int last, BezierCurvePoints2D bezCurve, double *u, int *splitPoint)
410{
411 int i;
412 double maxDist; /* Maximum error */
413 double dist; /* Current error */
414 Vector2 P; /* Point on curve */
415 Vector2 v; /* Vector from point to curve */
416
417 *splitPoint = (last - first + 1) / 2;
418 maxDist = 0.0;
419 for (i = first + 1; i < last; i++) {
420 P = BezierII(3, bezCurve, u[i - first]);
421 v = V2SubII(P, d[i]);
422 dist = V2SquaredLength(&v);
423 if (dist >= maxDist) {
424 maxDist = dist;
425 *splitPoint = i;
426 }
427 }
428 return maxDist;
429}
430
432{
433 Vector2 c;
434 c[0] = a[0] + b[0];
435 c[1] = a[1] + b[1];
436 return c;
437}
438
439static Vector2 V2ScaleIII(Vector2 v, double s)
440{
441 Vector2 result;
442 result[0] = v[0] * s;
443 result[1] = v[1] * s;
444 return result;
445}
446
448{
449 Vector2 c;
450 c[0] = a[0] - b[0];
451 c[1] = a[1] - b[1];
452 return c;
453}
454
455//------------------------- WRAPPER -----------------------------//
456
458{
459 _vertices.clear();
460}
461
463{
464 for (int i = 0; i <= n; ++i) {
465 _vertices.push_back(curve[i]);
466 }
467}
468
469void FitCurveWrapper::FitCurve(vector<Vec2d> &data, vector<Vec2d> &oCurve, double error)
470{
471 int size = data.size();
472 Vector2 *d = new Vector2[size];
473 for (int i = 0; i < size; ++i) {
474 d[i][0] = data[i][0];
475 d[i][1] = data[i][1];
476 }
477
478 FitCurve(d, size, error);
479
480 delete[] d;
481
482 // copy results
483 for (vector<Vector2>::iterator v = _vertices.begin(), vend = _vertices.end(); v != vend; ++v) {
484 oCurve.emplace_back(v->x(), v->y());
485 }
486}
487
488void FitCurveWrapper::FitCurve(Vector2 *d, int nPts, double error)
489{
490 Vector2 tHat1, tHat2; /* Unit tangent vectors at endpoints */
491
492 tHat1 = ComputeLeftTangent(d, 0);
493 tHat2 = ComputeRightTangent(d, nPts - 1);
494 FitCubic(d, 0, nPts - 1, tHat1, tHat2, error);
495}
496
498 Vector2 *d, int first, int last, Vector2 tHat1, Vector2 tHat2, double error)
499{
500 BezierCurvePoints2D bezCurve; /* Control points of fitted Bezier curve */
501 double *u; /* Parameter values for point */
502 double *uPrime; /* Improved parameter values */
503 double maxError; /* Maximum fitting error */
504 int splitPoint; /* Point to split point set at */
505 int nPts; /* Number of points in subset */
506 double iterationError; /* Error below which you try iterating */
507 int maxIterations = 4; /* Max times to try iterating */
508 Vector2 tHatCenter; /* Unit tangent vector at splitPoint */
509 int i;
510
511 iterationError = error * error;
512 nPts = last - first + 1;
513
514 /* Use heuristic if region only has two points in it */
515 if (nPts == 2) {
516 double dist = V2DistanceBetween2Points(&d[last], &d[first]) / 3.0;
517
518 bezCurve = (Vector2 *)malloc(4 * sizeof(Vector2));
519 bezCurve[0] = d[first];
520 bezCurve[3] = d[last];
521 V2Add(&bezCurve[0], V2Scale(&tHat1, dist), &bezCurve[1]);
522 V2Add(&bezCurve[3], V2Scale(&tHat2, dist), &bezCurve[2]);
523 DrawBezierCurve(3, bezCurve);
524 free((void *)bezCurve);
525 return;
526 }
527
528 /* Parameterize points, and attempt to fit curve */
529 u = ChordLengthParameterize(d, first, last);
530 bezCurve = GenerateBezier(d, first, last, u, tHat1, tHat2);
531
532 /* Find max deviation of points to fitted curve */
533 maxError = ComputeMaxError(d, first, last, bezCurve, u, &splitPoint);
534 if (maxError < error) {
535 DrawBezierCurve(3, bezCurve);
536 free((void *)u);
537 free((void *)bezCurve);
538 return;
539 }
540
541 /* If error not too large, try some reparameterization and iteration */
542 if (maxError < iterationError) {
543 for (i = 0; i < maxIterations; i++) {
544 uPrime = Reparameterize(d, first, last, u, bezCurve);
545
546 free((void *)u);
547 free((void *)bezCurve);
548 u = uPrime;
549
550 bezCurve = GenerateBezier(d, first, last, u, tHat1, tHat2);
551 maxError = ComputeMaxError(d, first, last, bezCurve, u, &splitPoint);
552
553 if (maxError < error) {
554 DrawBezierCurve(3, bezCurve);
555 free((void *)u);
556 free((void *)bezCurve);
557 return;
558 }
559 }
560 }
561
562 /* Fitting failed -- split at max error point and fit recursively */
563 free((void *)u);
564 free((void *)bezCurve);
565 tHatCenter = ComputeCenterTangent(d, splitPoint);
566 FitCubic(d, first, splitPoint, tHat1, tHatCenter, error);
567 V2Negate(&tHatCenter);
568 FitCubic(d, splitPoint, last, tHatCenter, tHat2, error);
569}
570
571} /* namespace Freestyle */
An Algorithm for Automatically Fitting Digitized Curves by Philip J. Schneider,.
#define A
void DrawBezierCurve(int n, Vector2 *curve)
Definition FitCurve.cpp:462
void FitCubic(Vector2 *d, int first, int last, Vector2 tHat1, Vector2 tHat2, double error)
Definition FitCurve.cpp:497
void FitCurve(std::vector< Vec2d > &data, std::vector< Vec2d > &oCurve, double error)
#define sqrt
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
inherits from class Rep
Definition AppCanvas.cpp:20
static Vector2 BezierII(int degree, Vector2 *V, double t)
Definition FitCurve.cpp:275
static Vector2 * V2Normalize(Vector2 *v)
Definition FitCurve.cpp:89
static Vector2 * V2Negate(Vector2 *v)
Definition FitCurve.cpp:100
static Vector2 V2AddII(Vector2 a, Vector2 b)
Definition FitCurve.cpp:431
static double B1(double u)
Definition FitCurve.cpp:310
static double ComputeMaxError(Vector2 *d, int first, int last, BezierCurvePoints2D bezCurve, double *u, int *splitPoint)
Definition FitCurve.cpp:408
static Vector2 ComputeRightTangent(Vector2 *d, int end)
Definition FitCurve.cpp:345
static double NewtonRaphsonRootFind(BezierCurvePoints2D Q, Vector2 P, double u)
Definition FitCurve.cpp:228
static Vector2 * V2Add(Vector2 *a, Vector2 *b, Vector2 *c)
Definition FitCurve.cpp:81
static Vector2 V2ScaleIII(Vector2 v, double s)
Definition FitCurve.cpp:439
static double V2Dot(Vector2 *a, Vector2 *b)
Definition FitCurve.cpp:67
static double B0(double u)
Definition FitCurve.cpp:304
static BezierCurvePoints2D GenerateBezier(Vector2 *d, int first, int last, double *uPrime, Vector2 tHat1, Vector2 tHat2)
Definition FitCurve.cpp:114
static Vector2 ComputeLeftTangent(Vector2 *d, int end)
Definition FitCurve.cpp:334
static Vector2 * V2Scale(Vector2 *v, double newlen)
Definition FitCurve.cpp:56
static double V2SquaredLength(Vector2 *a)
Definition FitCurve.cpp:45
static double * ChordLengthParameterize(Vector2 *d, int first, int last)
Definition FitCurve.cpp:380
static double B3(double u)
Definition FitCurve.cpp:322
static double B2(double u)
Definition FitCurve.cpp:316
static double * Reparameterize(Vector2 *d, int first, int last, double *u, BezierCurvePoints2D bezCurve)
Definition FitCurve.cpp:207
Point2 Vector2
Definition FitCurve.h:54
static double V2DistanceBetween2Points(Vector2 *a, Vector2 *b)
Definition FitCurve.cpp:73
static double V2Length(Vector2 *a)
Definition FitCurve.cpp:51
Vector2 * BezierCurvePoints2D
Definition FitCurve.cpp:23
static Vector2 V2SubII(Vector2 a, Vector2 b)
Definition FitCurve.cpp:447
static Vector2 ComputeCenterTangent(Vector2 *d, int center)
Definition FitCurve.cpp:356
#define X(TYPE)
CCL_NAMESPACE_BEGIN struct Window V