[Bf-blender-cvs] [1ecfffe] fcurves-simplify: Initial fcurve simplification code.
Bastien Montagne
noreply at git.blender.org
Mon Jun 8 15:14:44 CEST 2015
Commit: 1ecfffeced1386f15e2f33696388a60237bd4b19
Author: Bastien Montagne
Date: Mon Jun 8 14:41:26 2015 +0200
Branches: fcurves-simplify
https://developer.blender.org/rB1ecfffeced1386f15e2f33696388a60237bd4b19
Initial fcurve simplification code.
Notes:
* This is own coocking, since it seems hard to find papers on simplifying already existing bezier curves,
and we do not really need the 'generic' least-square fitting of bezier in a set of points, here.
* It takes advantage of specificities of FCurves (e.g. only difference that matters here is Y value at same X frame,
no vertical overlapping, etc.).
* It gives reasonably good results, but could most likely be enhanced quite a bit still.
* Only 'hooked' to bake action operator right now (needs more work to add it to graph editor too).
* Ultimately should probably be redone in C. Would keep it in Python until we have a real good
cleanup behavior though, much easier to experiment in later language.
===================================================================
M release/scripts/modules/bpy_extras/anim_utils.py
M release/scripts/startup/bl_operators/anim.py
===================================================================
diff --git a/release/scripts/modules/bpy_extras/anim_utils.py b/release/scripts/modules/bpy_extras/anim_utils.py
index 4ee5e68..435169c 100644
--- a/release/scripts/modules/bpy_extras/anim_utils.py
+++ b/release/scripts/modules/bpy_extras/anim_utils.py
@@ -25,6 +25,304 @@ __all__ = (
import bpy
+def frange(start, stop, step=1.0):
+ while start < stop:
+ yield start
+ start += step
+
+
+def ref_curve_eval(curve, frame_start, frame_stop, frame_step, x):
+ fac = (x - frame_start) / frame_step
+ idx = int(fac)
+ fac = abs(fac - idx)
+ if idx < 0:
+ return curve[0]
+ elif idx + 1 >= len(curve):
+ return curve[-1]
+ return (1.0 - fac) * curve[idx] + fac * curve[idx + 1]
+
+
+def bezt_optimize(points, threshold, res, steps, org_ref_curve, frame_start, frame_stop, frame_step):
+ """
+ Try to optimize given pair of Bezier segments (triplet of contiguous control points).
+ """
+ # Trying to remove the center point and adjusting relevant handles of each end points.
+ # If resulting curve gives error below threshold (i.e. average difference between y-values of original
+ # and simplified curve is small enough), we keep it (i.e. remove its center point).
+
+ from mathutils.geometry import interpolate_bezier
+ from math import sqrt
+
+ def correct_bezpart(points):
+ # Same as in C code...
+ h1 = points[0] - points[1]
+ h2 = points[3] - points[2]
+ d = points[3].x - points[0].x
+ d1 = abs(h1.x)
+ d2 = abs(h2.x)
+
+ if d != 0.0 and d1 + d2 > d:
+ fac = d / (d1 + d2)
+ points[1] = points[0] - h1 * fac
+ points[2] = points[3] - h2 * fac
+
+ def bez_diff(ref_curve, cur_curve, res):
+ # start and end values shall be the same!
+ start_diff = end_diff = 0
+ for i, (ref_v, cur_pt) in enumerate(zip(ref_curve[1:-1], cur_curve[1:-1])):
+ # Note we give much higher importance (quadratic rate) to difference near matching end.
+ start_fac = (i + 1) / res
+ end_fac = 1.0 - start_fac
+ start_diff += (cur_pt.y - ref_v) / (start_fac * start_fac)
+ end_diff += (cur_pt.y - ref_v) / (end_fac * end_fac)
+ return start_diff / (res - 2), end_diff / (res - 2)
+
+ correct_bezpart(points)
+
+ start_vec = points[1] - points[0]
+ end_vec = points[2] - points[3]
+
+ neg_slope = points[1].y < points[0].y if points[1].y != points[0].y else points[2].y < points[0].y if points[2].y != points[0].y else points[3].y < points[0].y
+
+ cur_curve = interpolate_bezier(points[0], points[1], points[2], points[3], res)
+ ref_curve = [ref_curve_eval(org_ref_curve, frame_start, frame_stop, frame_step, pt.x) for pt in cur_curve]
+
+ start_diff, end_diff = bez_diff(ref_curve, cur_curve, res)
+ prev_start_diff, prev_end_diff = start_diff, end_diff
+ do_start = 0
+ #~ print(points)
+ #~ print(start_diff, end_diff)
+
+ f = 1.0
+ for i in range(steps):
+ error = max(abs(start_diff), abs(end_diff))
+ if error < threshold:
+ return error
+
+ prev_points = list(points)
+ prev_start_vec, prev_end_vec = start_vec.copy(), end_vec.copy()
+
+ if do_start > 0 or (do_start == 0 and abs(start_diff) > abs(end_diff)):
+ do_start += 1
+ if neg_slope:
+ if start_diff > 0.0:
+ start_vec /= 1 + start_diff * f
+ else:
+ start_vec *= 1 - start_diff * f
+ else:
+ if start_diff < 0.0:
+ start_vec /= 1 - start_diff * f
+ else:
+ start_vec *= 1 + start_diff * f
+ points[1] = points[0] + start_vec
+ else:
+ do_start -= 1
+ if neg_slope:
+ if end_diff > 0.0:
+ end_vec *= 1 + end_diff * f
+ else:
+ end_vec /= 1 - end_diff * f
+ else:
+ if end_diff < 0.0:
+ end_vec *= 1 - end_diff * f
+ else:
+ end_vec /= 1 + end_diff * f
+ points[2] = points[3] + end_vec
+
+ correct_bezpart(points)
+ cur_curve = interpolate_bezier(points[0], points[1], points[2], points[3], res)
+ ref_curve = [ref_curve_eval(org_ref_curve, frame_start, frame_stop, frame_step, pt.x) for pt in cur_curve]
+
+ start_diff, end_diff = bez_diff(ref_curve, cur_curve, res)
+ #~ print(points)
+ #~ print(start_diff, end_diff, f, do_start, neg_slope)
+
+ if ((do_start > 0 and abs(start_diff) > abs(prev_start_diff)) or
+ (do_start < 0 and abs(end_diff) > abs(prev_end_diff))):
+ #~ print("WRONG!!!", (start_diff, prev_start_diff) if do_start > 0 else (end_diff, prev_end_diff))
+ points[:] = prev_points
+ start_diff, end_diff = prev_start_diff, prev_end_diff
+ start_vec, end_vec = prev_start_vec, prev_end_vec
+ do_start *= -1
+ if not (do_start % 2):
+ f /= 2
+ else:
+ do_start = 0
+ prev_start_diff, prev_end_diff = start_diff, end_diff
+
+ return max(abs(start_diff), abs(end_diff))
+
+
+def simplify_fcurve(fcurve, frame_start, frame_stop, threshold):
+ """
+ This function simplifies given fcurve, removing some existing control points and adjusting the others' handles.
+ Note that it does not remove non-aligned (or auto) points, nor any using something else than Bezier interpolation.
+
+ :arg frame_start: First frame to simplify.
+ :type frame_start: int
+ :arg frame_stop: Last frame to simplify (excluded).
+ :type frame_stop: int
+ :arg threshold: Precision of simplification
+ (the smaller the more precise, never zero, typically 0.1 gives best results).
+ :type threshold: float
+
+ :return: The number of deleted keyframes.
+ :rtype: int
+ """
+
+ # * We make several passes on the curve, removing each time at most (n - 1) / 2 of its control points.
+ # * End points are never removed.
+ # * Points which do not have aligned handles are never removed, neither are points using non-Bezier interpolation.
+ # * Each set of contiguous, aligned/auto points define a single curve segment.
+ # * At each pass, for each segment, we check a set of triplets, and try to optimize it.
+
+ SIMPLIFIED_TYPES_AUTO = {'AUTO', 'AUTO_CLAMPED'}
+ SIMPLIFIED_TYPES = {'ALIGNED'} | SIMPLIFIED_TYPES_AUTO
+ SIMPLIFIED_INTERPOLATION = {'BEZIER'}
+
+ frame_step = max(0.001, threshold / 10.0)
+ res = min(1000, int(1 / threshold * 10))
+ steps = min(100, int(1 / threshold * 5))
+
+ ref_curve = [fcurve.evaluate(x) for x in frange(frame_start, frame_stop, frame_step)]
+
+ curves = [[[], False]]
+ for pt in fcurve.keyframe_points:
+ if pt.co.x < frame_start:
+ continue
+ if pt.co.x >= frame_stop:
+ break
+ if pt.interpolation not in SIMPLIFIED_INTERPOLATION:
+ # 'Break' point.
+ if len(curves[-1][0]) > 2:
+ curves.append([[], False])
+ else: # Current curve segment is too short to be simplifiable, simply ignore it!
+ curves[-1][0][:] = []
+ #~ print("breaking")
+ continue
+ if pt.handle_left_type not in SIMPLIFIED_TYPES or pt.handle_right_type not in SIMPLIFIED_TYPES:
+ # 'Break' point.
+ if len(curves[-1][0]) > 1:
+ curves[-1][0].append([[pt.handle_left, pt.co, pt.handle_right], False, pt])
+ curves.append([[], False])
+ else: # Current curve segment is too short to be simplifiable, simply ignore it!
+ curves[-1][0][:] = []
+ #~ print("breaking")
+ curves[-1][0].append([[pt.handle_left, pt.co, pt.handle_right], False, pt])
+
+ if not curves[-1][0]:
+ del curves[-1] # Cleanup.
+
+ if not curves:
+ return 0
+
+ del_keyframes = []
+ step_simplified = True
+ while step_simplified:
+ step_simplified = False
+ for crv in curves:
+ if crv[1]:
+ continue # that whole segment of curve is considered impossible to simplify further.
+
+ curve = crv[0]
+ curve_len = len(curve)
+ new_curve1 = curve[0:1]
+ del_keyframes1 = []
+ simplified1 = 0
+ tot_error1 = 0.0
+ if curve_len <= 2:
+ continue
+
+ for i in range(0, curve_len - 2, 2):
+ if curve[i + 1][1]:
+ # Center knot of this triplet is locked (marked as not removable), skip.
+ new_curve1 += curve[i + 1:i + 3]
+ points = [curve[i][0][1].copy(), curve[i][0][2].copy(), curve[i + 2][0][0].copy(), curve[i + 2][0][1].copy()]
+ error = bezt_optimize(points, threshold, res, steps, ref_curve, frame_start, frame_stop, frame_step)
+ #~ print(error)
+ if (error < threshold):
+ del_keyframes1.append(curve[i + 1][2])
+ tot_error1 += error
+ # Center points of knots do not change - ever!
+ new_curve1[-1][0][2] = points[1]
+ new_curve1.append(curve[i + 2])
+ new_curve1[-1][0][0] = points[2]
+ simplified1 += 1
+ else:
+ new_curve1 += curve[i + 1:i + 3] # Mere copy of org curve...
+ #~ new_curve1[-2][1] = True # Lock that center knot from now on.
+ step_simplified = step_simplified or (simplified1 > 0)
+
+ if curve_len > 3:
+ # If we have four or more control points, we also have to check the other possible set of triplets...
+ new_curve2 = curve[0:1]
+ del_keyframes2 = []
+ simplified2 = 0
+ tot_error2 = 0.0
+
+ for i in range(1, curve_len - 2, 2):
+ if curve[i + 1][1]:
+ # Center knot of this triplet is locked (ma
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list