blender
/
blender
134
398
Fork 580
Code Issues 6.3k Pull Requests 758 Projects 19 Wiki Activity

Patch T36209: Use binary search function for evaluating F-Curves 

This provides a speedup to evaluating long F-Curves in fcurve_eval_keyframes()
by using the pre-existing binarysearch_bezt_index() function (used for keyframe
insertion) to find the relevant BezTriple on the FCurve at the current evaltime.
The current code loops over all BezTriples (sometimes not even breaking from the
loop after cvalue has been evaluated).

Reviewer Notes:
- Unlike in the original patch, we use the old/existing logic instead of
  checking that (exact == true). See comments in code and also on the tracker
  entry for this patch for more details.

Patch By: Josh Wedlake
This commit is contained in:
Joshua Leung 2014-03-15 11:45:14 +13:00
parent 0dd52d1b26
commit 2aff2435f0
Notes: blender-bot 2023-02-14 12:00:53 +01:00 
Referenced by commit 3406ef8e03, Fix T39207: FCurve evaluation regressions following 2aff243 (again)
Referenced by commit f0ac7294fa, Fix T39207: FCurve evaluation regressions following 2aff243
Referenced by issue #39207, Wrong evaluation of Action Constraint
Referenced by issue #39209, Nodes in 2.70-RC2 and source build 211f08d extremely unstable (segfault crash)
Referenced by issue #39210, Grid Fill is generating mesh that's inconsistent with selected edge loops
Referenced by issue #38897, Problems moving animation channels up and down in dope sheet/action editor
Referenced by issue #38259, Animation of bones not exported properly
Referenced by issue #36209, Use binary search function for evaluating fcurves to find relevant bezt instead of looping over all bezts
1 changed files with 58 additions and 45 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

103
source/blender/blenkernel/intern/fcurve.c
View File

@ -1924,6 +1924,7 @@ static float fcurve_eval_keyframes(FCurve *fcu, BezTriple *bezts, float evaltime
unsigned int a;
int b;
float cvalue = 0.0f;
bool exact = false;
/* get pointers */
a = fcu->totvert - 1;
@ -2038,54 +2039,66 @@ static float fcurve_eval_keyframes(FCurve *fcu, BezTriple *bezts, float evaltime
}
else {
/* evaltime occurs somewhere in the middle of the curve */
for (a = 0; prevbezt && bezt && (a < fcu->totvert - 1); a++, prevbezt = bezt, bezt++) {
/* use if the key is directly on the frame, rare cases this is needed else we get 0.0 instead. */
if (fabsf(bezt->vec[1][0] - evaltime) < SMALL_NUMBER) {
cvalue = bezt->vec[1][1];
/* - use binary search to find appropriate keyframes */
a = binarysearch_bezt_index(bezts, evaltime, fcu->totvert, &exact);
BLI_assert(a > 0); /* a == 0, prevbezt = invalid access */
bezt = bezts;
bezt += a;
prevbezt = bezt - 1;
/* use if the key is directly on the frame, rare cases this is needed else we get 0.0 instead. */
/* NOTE: Although we could just check if exact == true here, the thresholds for equality are
* different (0.01 for exact, vs 1e-8 for SMALL_NUMBER). For backwards compatibility,
* and to avoid introducing regressions for a few rare cases, let's keep the old
* method/thresholds here for now.
* -- Aligorith (2014Mar14)
*/
if (fabsf(bezt->vec[1][0] - evaltime) < SMALL_NUMBER) {
cvalue = bezt->vec[1][1];
}
/* evaltime occurs within the interval defined by these two keyframes */
else if ((prevbezt->vec[1][0] <= evaltime) && (bezt->vec[1][0] >= evaltime)) {
/* value depends on interpolation mode */
if ((prevbezt->ipo == BEZT_IPO_CONST) || (fcu->flag & FCURVE_DISCRETE_VALUES)) {
/* constant (evaltime not relevant, so no interpolation needed) */
cvalue = prevbezt->vec[1][1];
}
/* evaltime occurs within the interval defined by these two keyframes */
else if ((prevbezt->vec[1][0] <= evaltime) && (bezt->vec[1][0] >= evaltime)) {
/* value depends on interpolation mode */
if ((prevbezt->ipo == BEZT_IPO_CONST) || (fcu->flag & FCURVE_DISCRETE_VALUES)) {
/* constant (evaltime not relevant, so no interpolation needed) */
cvalue = prevbezt->vec[1][1];
}
else if (prevbezt->ipo == BEZT_IPO_LIN) {
/* linear - interpolate between values of the two keyframes */
fac = bezt->vec[1][0] - prevbezt->vec[1][0];
/* prevent division by zero */
if (fac) {
fac = (evaltime - prevbezt->vec[1][0]) / fac;
cvalue = prevbezt->vec[1][1] + (fac * (bezt->vec[1][1] - prevbezt->vec[1][1]));
}
else {
cvalue = prevbezt->vec[1][1];
}
else if (prevbezt->ipo == BEZT_IPO_LIN) {
/* linear - interpolate between values of the two keyframes */
fac = bezt->vec[1][0] - prevbezt->vec[1][0];
/* prevent division by zero */
if (fac) {
fac = (evaltime - prevbezt->vec[1][0]) / fac;
cvalue = prevbezt->vec[1][1] + (fac * (bezt->vec[1][1] - prevbezt->vec[1][1]));
}
else {
/* bezier interpolation */
/* (v1, v2) are the first keyframe and its 2nd handle */
v1[0] = prevbezt->vec[1][0];
v1[1] = prevbezt->vec[1][1];
v2[0] = prevbezt->vec[2][0];
v2[1] = prevbezt->vec[2][1];
/* (v3, v4) are the last keyframe's 1st handle + the last keyframe */
v3[0] = bezt->vec[0][0];
v3[1] = bezt->vec[0][1];
v4[0] = bezt->vec[1][0];
v4[1] = bezt->vec[1][1];
/* adjust handles so that they don't overlap (forming a loop) */
correct_bezpart(v1, v2, v3, v4);
/* try to get a value for this position - if failure, try another set of points */
b = findzero(evaltime, v1[0], v2[0], v3[0], v4[0], opl);
if (b) {
berekeny(v1[1], v2[1], v3[1], v4[1], opl, 1);
cvalue = opl[0];
break;
}
cvalue = prevbezt->vec[1][1];
}
}
else {
/* bezier interpolation */
/* (v1, v2) are the first keyframe and its 2nd handle */
v1[0] = prevbezt->vec[1][0];
v1[1] = prevbezt->vec[1][1];
v2[0] = prevbezt->vec[2][0];
v2[1] = prevbezt->vec[2][1];
/* (v3, v4) are the last keyframe's 1st handle + the last keyframe */
v3[0] = bezt->vec[0][0];
v3[1] = bezt->vec[0][1];
v4[0] = bezt->vec[1][0];
v4[1] = bezt->vec[1][1];
/* adjust handles so that they don't overlap (forming a loop) */
correct_bezpart(v1, v2, v3, v4);
/* try to get a value for this position - if failure, try another set of points */
b = findzero(evaltime, v1[0], v2[0], v3[0], v4[0], opl);
if (b) {
berekeny(v1[1], v2[1], v3[1], v4[1], opl, 1);
cvalue = opl[0];
/* break; */
}
}
}