[Bf-blender-cvs] [8bdc391c548] master: Implement a new automatic handle algorithm to produce smooth F-Curves.
Alexander Gavrilov
noreply at git.blender.org
Wed Nov 1 20:01:58 CET 2017
Commit: 8bdc391c5488228dfe9c9e995277d67558293f08
Author: Alexander Gavrilov
Date: Wed Nov 1 21:34:30 2017 +0300
Branches: master
https://developer.blender.org/rB8bdc391c5488228dfe9c9e995277d67558293f08
Implement a new automatic handle algorithm to produce smooth F-Curves.
The legacy algorithm only considers two adjacent points when computing
the bezier handles, which cannot produce satisfactory results. Animators
are often forced to manually adjust all curves.
The new approach instead solves a system of equations to trace a cubic spline
with continuous second derivative through the whole segment of auto points,
delimited at ends by keyframes with handles set by other requirements.
This algorithm also adjusts Vector handles that face ordinary bezier keyframes
to achieve zero acceleration at the Vector keyframe, instead of simply pointing
it at the adjacent point.
Original idea and implementation by Benoit Bolsee <benoit.bolsee at online.be>;
code mostly rewritten to improve code clarity and extensibility.
Reviewers: aligorith
Differential Revision: https://developer.blender.org/D2884
===================================================================
M source/blender/blenkernel/BKE_curve.h
M source/blender/blenkernel/intern/curve.c
M source/blender/blenkernel/intern/fcurve.c
M source/blender/blenkernel/intern/mask.c
M source/blender/blenkernel/intern/nla.c
M source/blender/blenlib/BLI_math_solvers.h
M source/blender/blenlib/intern/math_solvers.c
M source/blender/editors/animation/drivers.c
M source/blender/editors/animation/keyframing.c
M source/blender/editors/curve/editcurve.c
M source/blender/editors/space_graph/graph_buttons.c
M source/blender/makesdna/DNA_anim_types.h
M source/blender/makesdna/DNA_curve_types.h
M source/blender/makesrna/intern/rna_fcurve.c
===================================================================
diff --git a/source/blender/blenkernel/BKE_curve.h b/source/blender/blenkernel/BKE_curve.h
index 30db8f45059..175fa1dad79 100644
--- a/source/blender/blenkernel/BKE_curve.h
+++ b/source/blender/blenkernel/BKE_curve.h
@@ -202,10 +202,12 @@ void BKE_nurb_bpoint_calc_normal(struct Nurb *nu, struct BPoint *bp, float r_nor
void BKE_nurb_bpoint_calc_plane(struct Nurb *nu, struct BPoint *bp, float r_plane[3]);
void BKE_nurb_handle_calc(struct BezTriple *bezt, struct BezTriple *prev, struct BezTriple *next,
- const bool is_fcurve);
+ const bool is_fcurve, const char smoothing);
void BKE_nurb_handle_calc_simple(struct Nurb *nu, struct BezTriple *bezt);
void BKE_nurb_handle_calc_simple_auto(struct Nurb *nu, struct BezTriple *bezt);
+void BKE_nurb_handle_smooth_fcurve(struct BezTriple *bezt, int total, bool cyclic);
+
void BKE_nurb_handles_calc(struct Nurb *nu);
void BKE_nurb_handles_autocalc(struct Nurb *nu, int flag);
void BKE_nurb_bezt_handle_test(struct BezTriple *bezt, const bool use_handle);
diff --git a/source/blender/blenkernel/intern/curve.c b/source/blender/blenkernel/intern/curve.c
index 6c6019748d6..98e4cb85981 100644
--- a/source/blender/blenkernel/intern/curve.c
+++ b/source/blender/blenkernel/intern/curve.c
@@ -41,6 +41,7 @@
#include "BLI_utildefines.h"
#include "BLI_ghash.h"
+#include "DNA_anim_types.h"
#include "DNA_curve_types.h"
#include "DNA_material_types.h"
@@ -3134,7 +3135,7 @@ void BKE_curve_bevelList_make(Object *ob, ListBase *nurbs, bool for_render)
static void calchandleNurb_intern(
BezTriple *bezt, const BezTriple *prev, const BezTriple *next,
- bool is_fcurve, bool skip_align)
+ bool is_fcurve, bool skip_align, char fcurve_smoothing)
{
/* defines to avoid confusion */
#define p2_h1 ((p2) - 3)
@@ -3148,6 +3149,9 @@ static void calchandleNurb_intern(
float len_ratio;
const float eps = 1e-5;
+ /* assume normal handle until we check */
+ bezt->f5 = HD_AUTOTYPE_NORMAL;
+
if (bezt->h1 == 0 && bezt->h2 == 0) {
return;
}
@@ -3199,7 +3203,14 @@ static void calchandleNurb_intern(
tvec[2] = dvec_b[2] / len_b + dvec_a[2] / len_a;
if (is_fcurve) {
- len = tvec[0];
+ if (fcurve_smoothing != FCURVE_SMOOTH_NONE) {
+ /* force the horizontal handle size to be 1/3 of the key interval so that
+ * the X component of the parametric bezier curve is a linear spline */
+ len = 6.0f/2.5614f;
+ }
+ else {
+ len = tvec[0];
+ }
}
else {
len = len_v3(tvec);
@@ -3210,10 +3221,12 @@ static void calchandleNurb_intern(
/* only for fcurves */
bool leftviolate = false, rightviolate = false;
- if (len_a > 5.0f * len_b)
- len_a = 5.0f * len_b;
- if (len_b > 5.0f * len_a)
- len_b = 5.0f * len_a;
+ if (!is_fcurve || fcurve_smoothing == FCURVE_SMOOTH_NONE) {
+ if (len_a > 5.0f * len_b)
+ len_a = 5.0f * len_b;
+ if (len_b > 5.0f * len_a)
+ len_b = 5.0f * len_a;
+ }
if (ELEM(bezt->h1, HD_AUTO, HD_AUTO_ANIM)) {
len_a /= len;
@@ -3224,6 +3237,7 @@ static void calchandleNurb_intern(
float ydiff2 = next->vec[1][1] - bezt->vec[1][1];
if ((ydiff1 <= 0.0f && ydiff2 <= 0.0f) || (ydiff1 >= 0.0f && ydiff2 >= 0.0f)) {
bezt->vec[0][1] = bezt->vec[1][1];
+ bezt->f5 = HD_AUTOTYPE_SPECIAL;
}
else { /* handles should not be beyond y coord of two others */
if (ydiff1 <= 0.0f) {
@@ -3250,6 +3264,7 @@ static void calchandleNurb_intern(
float ydiff2 = next->vec[1][1] - bezt->vec[1][1];
if ( (ydiff1 <= 0.0f && ydiff2 <= 0.0f) || (ydiff1 >= 0.0f && ydiff2 >= 0.0f) ) {
bezt->vec[2][1] = bezt->vec[1][1];
+ bezt->f5 = HD_AUTOTYPE_SPECIAL;
}
else { /* handles should not be beyond y coord of two others */
if (ydiff1 <= 0.0f) {
@@ -3397,7 +3412,7 @@ static void calchandlesNurb_intern(Nurb *nu, bool skip_align)
next = bezt + 1;
while (a--) {
- calchandleNurb_intern(bezt, prev, next, 0, skip_align);
+ calchandleNurb_intern(bezt, prev, next, 0, skip_align, 0);
prev = bezt;
if (a == 1) {
if (nu->flagu & CU_NURB_CYCLIC)
@@ -3412,9 +3427,543 @@ static void calchandlesNurb_intern(Nurb *nu, bool skip_align)
}
}
-void BKE_nurb_handle_calc(BezTriple *bezt, BezTriple *prev, BezTriple *next, const bool is_fcurve)
+/* A utility function for allocating a number of arrays of the same length
+ * with easy error checking and deallocation, and an easy way to add or remove
+ * arrays that are processed in this way when changing code.
+ *
+ * floats, chars: NULL-terminated arrays of pointers to array pointers that need to be allocated.
+ *
+ * Returns: pointer to the buffer that contains all of the arrays.
+ */
+static void *allocate_arrays(int count, float ***floats, char ***chars, const char *name)
+{
+ int num_floats = 0, num_chars = 0;
+
+ while (floats && floats[num_floats]) {
+ num_floats++;
+ }
+
+ while (chars && chars[num_chars]) {
+ num_chars++;
+ }
+
+ void *buffer = (float*)MEM_mallocN(count * (sizeof(float)*num_floats + num_chars), name);
+
+ if (!buffer)
+ return NULL;
+
+ float *fptr = buffer;
+
+ for (int i = 0; i < num_floats; i++, fptr += count) {
+ *floats[i] = fptr;
+ }
+
+ char *cptr = (char*)fptr;
+
+ for (int i = 0; i < num_chars; i++, cptr += count) {
+ *chars[i] = cptr;
+ }
+
+ return buffer;
+}
+
+static void free_arrays(void *buffer)
+{
+ MEM_freeN(buffer);
+}
+
+/* computes in which direction to change h[i] to satisfy conditions better */
+static float bezier_relax_direction(float *a, float *b, float *c, float *d, float *h, int i, int count)
+{
+ /* current deviation between sides of the equation */
+ float state = a[i] * h[(i+count-1) % count]
+ + b[i] * h[i]
+ + c[i] * h[(i+1) % count]
+ - d[i];
+
+ /* only the sign is meaningful */
+ return -state * b[i];
+}
+
+static void bezier_lock_unknown(float *a, float *b, float *c, float *d, int i, float value)
+{
+ a[i] = c[i] = 0.0f;
+ b[i] = 1.0f;
+ d[i] = value;
+}
+
+static void bezier_restore_equation(float *a, float *b, float *c, float *d, float *a0, float *b0, float *c0, float *d0, int i)
+{
+ a[i] = a0[i];
+ b[i] = b0[i];
+ c[i] = c0[i];
+ d[i] = d0[i];
+}
+
+static bool tridiagonal_solve_with_limits(float *a, float *b, float *c, float *d, float *h, float *hmin, float *hmax, int solve_count)
+{
+ float *a0, *b0, *c0, *d0;
+ float **arrays[] = { &a0, &b0, &c0, &d0, NULL };
+ char *is_locked, *num_unlocks;
+ char **flagarrays[] = { &is_locked, &num_unlocks, NULL };
+
+ void *tmps = allocate_arrays(solve_count, arrays, flagarrays, "tridiagonal_solve_with_limits");
+ if (!tmps)
+ return false;
+
+ memcpy(a0, a, sizeof(float)*solve_count);
+ memcpy(b0, b, sizeof(float)*solve_count);
+ memcpy(c0, c, sizeof(float)*solve_count);
+ memcpy(d0, d, sizeof(float)*solve_count);
+
+ memset(is_locked, 0, solve_count);
+ memset(num_unlocks, 0, solve_count);
+
+ bool overshoot, unlocked;
+
+ do
+ {
+ if (!BLI_tridiagonal_solve_cyclic(a, b, c, d, h, solve_count)) {
+ free_arrays(tmps);
+ return false;
+ }
+
+ /* first check if any handles overshoot the limits, and lock them */
+ bool all = false, locked = false;
+
+ overshoot = unlocked = false;
+
+ do
+ {
+ for (int i = 0; i < solve_count; i++) {
+ if (h[i] >= hmin[i] && h[i] <= hmax[i])
+ continue;
+
+ overshoot = true;
+
+ float target = h[i] > hmax[i] ? hmax[i] : hmin[i];
+
+ /* heuristically only lock handles that go in the right direction if there are such ones */
+ if (target != 0.0f || all) {
+ /* mark item locked */
+ is_locked[i] = 1;
+
+ bezier_lock_unknown(a, b, c, d, i, target);
+ locked = true;
+ }
+ }
+
+ all = true;
+ }
+ while (overshoot && !locked);
+
+ /* if no handles overshot and were locked, see if it may be a good idea to unlock some handles */
+ if (!locked) {
+ for (int i = 0; i < solve_count; i++) {
+ // to definitely avoid infinite loops limit this to 2 times
+ if (!is_locked[i] || num_unlocks[i] >= 2)
+ continue;
+
+ /* if the handle wants to move in allowable direction, release it */
+ float relax = bezier_relax_direction(a0, b0, c0, d0, h, i, solve_count);
+
+ if ((relax > 0 && h[i] < hmax[i]) || (relax < 0 && h[i] > hmin[i])) {
+ bezier_restore_equation(a, b, c, d, a0, b0, c0, d0, i);
+
+ is_locked[i] = 0;
+ num_unlocks[i]++;
+ unlocked = true;
+ }
+ }
+ }
+ }
+ while (overshoot || unlocked);
+
+ free_arrays(tmps);
+ return true;
+}
+
+/*
+ * This function computes the handles of a series of auto bezier points
+ * on the basis of 'no acceleration discontinuities' at the points.
+ * The first and last bezier points are considered 'fixed' (their handles are not touched)
+ * The result is the smoothest possible trajectory going through intemediate points.
+ * The difficulty is that the handles depends on their neighbours.
+ *
+ * The exact solution is found by solving a tridiagonal matrix equation formed
+ * by the continuity and boundary conditions. Although theoretically handle position
+ * is affected by all other points of the curve segment, in practice the influence
+ * decreases exponentially with distance.
+ *
+ * Note: this algorithm assumes that the handle horizontal size if always 1/3 of the
+ * of the interval to the next point. This rule ensures linear interpolation of time.
+ *
+ * ^ height (co 1)
+ * | yN
+ * | yN-1 |
+ * | y2 | |
+ * | y1 | | |
+ * | y0 | | | |
+ * | | | | | |
+ * | | | | | |
+ * | | | | | |
+ * |-------t1---------t2--------- ~ --------tN-------------------> time (co 0)
+ *
+ *
+ * Mathematical basis:
+ *
+ * 1. Handle lengths on either side of each point are connected by a factor
+ * ensuring continuity of the first derivative:
+ *
+ * l[i] = t[i+1]/t[i]
+ *
+ * 2. The tridiagonal system is formed by the following equation, which is derived
+ * by differentiating the bezier curve and specifi
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list