Initial fcurve simplification code.fcurves-simplify

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.

2 files changed, 312 insertions, 1 deletions

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,
                                         )