[Bf-blender-cvs] [7a765e7afa5] smooth-fcurves: Implement a new automatic handle algorithm to produce smooth F-Curves.
Alexander Gavrilov
noreply at git.blender.org
Sun Aug 20 16:10:27 CEST 2017
Commit: 7a765e7afa5ab3b624297beb29b78c34c718f75d
Author: Alexander Gavrilov
Date: Thu Aug 10 21:48:23 2017 +0300
Branches: smooth-fcurves
https://developer.blender.org/rB7a765e7afa5ab3b624297beb29b78c34c718f75d
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.
===================================================================
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 be05f7d4136..75bf4b07805 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 ece33786940..c62685b51ac 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,13 @@ 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 handlers transition to be 1/3 */
+ len = 6.0f/2.5614f;
+ }
+ else {
+ len = tvec[0];
+ }
}
else {
len = len_v3(tvec);
@@ -3210,10 +3220,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 +3236,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 +3263,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 +3411,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 +3426,519 @@ static void calchandlesNurb_intern(Nurb *nu, bool skip_align)
}
}
-void BKE_nurb_handle_calc(BezTriple *bezt, BezTriple *prev, BezTriple *next, const bool is_fcurve)
+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;
+}
+
+/* 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 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)) {
+ MEM_freeN(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])) {
+ /* restore equation coefficients */
+ a[i] = a0[i]; b[i] = b0[i]; c[i] = c0[i]; d[i] = d0[i];
+
+ is_locked[i] = 0;
+ num_unlocks[i]++;
+ unlocked = true;
+ }
+ }
+ }
+ }
+ while (overshoot || unlocked);
+
+ MEM_freeN(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 specifies second derivative continuity
+ * at every point:
+ *
+ * l[i]^2 * h[i-1] + (2*l[i]+2) * h[i] + 1/l[i+1] * h[i+1] = (y[i]-y[i-1])*l[i]^2 + y[i+1]-y[i]
+ *
+ * 3. If this point is adjacent to a manually set handle with X size not equal to 1/3
+ * of the horizontal interval, this equation becomes slightly more complex:
+ *
+ * l[i]^2 * h[i-1] + (3*(1-R[i-1])*l[i] + 3*(1-L[i+1])) * h[i] + 1/l[i+1] * h[i+1] = (y[i]-y[i-1])*l[i]^2 + y[i+1]-y[i]
+ *
+ * The difference between equations amounts to this, and it's obvious that when R[i-1]
+ * and L[i+1] are both 1/3, it becomes zero:
+ *
+ * ( (1-3*R[i-1])*l[i] + (1-3*L[i+1]) ) * h[i]
+ *
+ * 4. The equations for zero acceleration border conditions are basically the above
+ * equation with part
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list