From 1ecfffeced1386f15e2f33696388a60237bd4b19 Mon Sep 17 00:00:00 2001 From: Bastien Montagne Date: Mon, 8 Jun 2015 14:41:26 +0200 Subject: 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. --- release/scripts/modules/bpy_extras/anim_utils.py | 303 +++++++++++++++++++++++ release/scripts/startup/bl_operators/anim.py | 10 +- 2 files changed, 312 insertions(+), 1 deletion(-) diff --git a/release/scripts/modules/bpy_extras/anim_utils.py b/release/scripts/modules/bpy_extras/anim_utils.py index 4ee5e685668..435169c39b0 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 (marked as not removable), skip. + new_curve2 += 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_keyframes2.append(curve[i + 1][2]) + tot_error2 += error + # Center points of knots do not change - ever! + new_curve2[-1][0][2] = points[1] + new_curve2.append(curve[i + 2]) + new_curve2[-1][0][0] = points[2] + simplified2 += 1 + else: + new_curve2 += curve[i + 1:i + 3] # Mere copy of org curve... + #~ new_curve2[-2][1] = True # Lock that center knot from now on. + + if (simplified2 > simplified1) or (simplified2 and ((tot_error2 < tot_error1) or not simplified1)): + new_curve1 = new_curve2 + del_keyframes1 = del_keyframes2 + step_simplified = step_simplified or (simplified2 > 0) + + if (len(new_curve1) < curve_len): + curve[:] = new_curve1 + del_keyframes += del_keyframes1 + else: + crv[1] = True # That segment of curve cannot be simplified further. + + ret = len(del_keyframes) + if not del_keyframes: + return ret + + # Now! Update our fcurve. + + # 'Flatten' our curve segments into a single curve again. + curve = [] + for c, _ in curves: + if len(c) >= 2: + if curve and curve[-1][2] == c[0][2]: + curve[-1][0][2] = c[0][2] + curve += c[1:] + else: + curve += c + + # Update handles of kept, modified keyframes. + for bezt, _, pt in c: + # Tag 'auto' handles as 'aligned'. + if pt.handle_left_type in SIMPLIFIED_TYPES_AUTO: + pt.handle_left_type = 'ALIGNED' + if pt.handle_right_type in SIMPLIFIED_TYPES_AUTO: + pt.handle_right_type = 'ALIGNED' + pt.handle_left, pt.co, pt.handle_right = bezt + + # Remove deleted keyframes - WARNING must be the last thing done! Otherwise, other points become invalid... + for pt in sorted(del_keyframes, key=lambda pt: pt.co.x, reverse=True): + fcurve.keyframe_points.remove(pt, fast=True) + + fcurve.update() + return ret + + # XXX visual keying is actually always considered as True in this code... def bake_action(frame_start, frame_end, @@ -37,6 +335,7 @@ def bake_action(frame_start, do_parents_clear=False, do_clean=False, action=None, + clean_threshold=0.0, ): """ @@ -66,6 +365,8 @@ def bake_action(frame_start, :arg action: An action to bake the data into, or None for a new action to be created. :type action: :class:`bpy.types.Action` or None + :arg clean_threshold: How much approximation do we accept while simplifying fcurves. + :type clean_threshold: float :return: an action or None :rtype: :class:`bpy.types.Action` @@ -241,6 +542,8 @@ def bake_action(frame_start, keyframe_points.remove(keyframe_points[i]) else: i += 1 + if clean_threshold != 0.0: + simplify_fcurve(fcu, keyframe_points[0].co.x, keyframe_points[-1].co.x + 1, clean_threshold) scene.frame_set(frame_back) diff --git a/release/scripts/startup/bl_operators/anim.py b/release/scripts/startup/bl_operators/anim.py index f3575f26890..a1b10976fe0 100644 --- a/release/scripts/startup/bl_operators/anim.py +++ b/release/scripts/startup/bl_operators/anim.py @@ -29,6 +29,7 @@ import bpy from bpy.types import Operator from bpy.props import ( IntProperty, + FloatProperty, BoolProperty, EnumProperty, StringProperty, @@ -216,6 +217,13 @@ class BakeAction(Operator): "(useful for baking only part of bones in an armature)", default=False, ) + clean_threshold = FloatProperty( + name="Clean Threshold", + description="Allowed error when simplifying baked curves (set to zero to disable)", + default=0.1, + min=0.0, + max=1.0, + ) bake_types = EnumProperty( name="Bake Data", description="Which data's transformations to bake", @@ -227,7 +235,6 @@ class BakeAction(Operator): ) def execute(self, context): - from bpy_extras import anim_utils action = None @@ -246,6 +253,7 @@ class BakeAction(Operator): do_constraint_clear=self.clear_constraints, do_parents_clear=self.clear_parents, do_clean=True, + clean_threshold=self.clean_threshold, action=action, ) -- cgit v1.2.3