curve_simplify.py

   1 # ##### BEGIN GPL LICENSE BLOCK #####
   2 #
   3 #  This program is free software; you can redistribute it and/or
   4 #  modify it under the terms of the GNU General Public License
   5 #  as published by the Free Software Foundation; either version 2
   6 #  of the License, or (at your option) any later version.
   7 #
   8 #  This program is distributed in the hope that it will be useful,
   9 #  but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 #  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 #  GNU General Public License for more details.
  12 #
  13 #  You should have received a copy of the GNU General Public License
  14 #  along with this program; if not, write to the Free Software Foundation,
  15 #  Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  16 #
  17 # ##### END GPL LICENSE BLOCK #####
  18
  19 bl_info = {
  20     "name": "Simplify Curves",
  21     "author": "testscreenings",
  22     "version": (1, 0, 3),
  23     "blender": (2, 75, 0),
  24     "location": "View3D > Add > Curve > Simplify Curves",
  25     "description": "Simplifies 3D Curve objects and animation F-Curves",
  26     "warning": "",
  27     "wiki_url": "https://wiki.blender.org/index.php/Extensions:2.6/Py/"
  28                 "Scripts/Curve/Curve_Simplify",
  29     "category": "Add Curve",
  30 }
  31
  32 """
  33 This script simplifies Curve objects and animation F-Curves.
  34 """
  35
  36 import bpy
  37 from bpy.props import (
  38         BoolProperty,
  39         EnumProperty,
  40         FloatProperty,
  41         IntProperty,
  42         )
  43 from mathutils import Vector
  44 from math import (
  45         sin,
  46         pow,
  47         )
  48 from bpy.types import Operator
  49
  50
  51 def error_handlers(self, op_name, errors, reports="ERROR"):
  52     if self and reports:
  53         self.report({'INFO'},
  54                     reports + ": some operations could not be performed "
  55                     "(See Console for more info)")
  56
  57     print("\n[Simplify Curves]\nOperator: {}\nErrors: {}\n".format(op_name, errors))
  58
  59
  60 # Check for curve
  61
  62 # ### simplipoly algorithm ###
  63
  64 # get SplineVertIndices to keep
  65 def simplypoly(splineVerts, options):
  66     # main vars
  67     newVerts = []           # list of vertindices to keep
  68     points = splineVerts    # list of 3dVectors
  69     pointCurva = []         # table with curvatures
  70     curvatures = []         # averaged curvatures per vert
  71     for p in points:
  72         pointCurva.append([])
  73     order = options[3]      # order of sliding beziercurves
  74     k_thresh = options[2]   # curvature threshold
  75     dis_error = options[6]  # additional distance error
  76
  77     # get curvatures per vert
  78     for i, point in enumerate(points[: -(order - 1)]):
  79         BVerts = points[i: i + order]
  80         for b, BVert in enumerate(BVerts[1: -1]):
  81             deriv1 = getDerivative(BVerts, 1 / (order - 1), order - 1)
  82             deriv2 = getDerivative(BVerts, 1 / (order - 1), order - 2)
  83             curva = getCurvature(deriv1, deriv2)
  84             pointCurva[i + b + 1].append(curva)
  85
  86     # average the curvatures
  87     for i in range(len(points)):
  88         avgCurva = sum(pointCurva[i]) / (order - 1)
  89         curvatures.append(avgCurva)
  90
  91     # get distancevalues per vert - same as Ramer-Douglas-Peucker
  92     # but for every vert
  93     distances = [0.0]  # first vert is always kept
  94     for i, point in enumerate(points[1: -1]):
  95         dist = altitude(points[i], points[i + 2], points[i + 1])
  96         distances.append(dist)
  97     distances.append(0.0)  # last vert is always kept
  98
  99     # generate list of vert indices to keep
 100     # tested against averaged curvatures and distances of neighbour verts
 101     newVerts.append(0)  # first vert is always kept
 102     for i, curv in enumerate(curvatures):
 103         if (curv >= k_thresh * 0.01 or distances[i] >= dis_error * 0.1):
 104             newVerts.append(i)
 105     newVerts.append(len(curvatures) - 1)  # last vert is always kept
 106
 107     return newVerts
 108
 109
 110 # get binomial coefficient
 111 def binom(n, m):
 112     b = [0] * (n + 1)
 113     b[0] = 1
 114     for i in range(1, n + 1):
 115         b[i] = 1
 116         j = i - 1
 117         while j > 0:
 118             b[j] += b[j - 1]
 119             j -= 1
 120     return b[m]
 121
 122
 123 # get nth derivative of order(len(verts)) bezier curve
 124 def getDerivative(verts, t, nth):
 125     order = len(verts) - 1 - nth
 126     QVerts = []
 127
 128     if nth:
 129         for i in range(nth):
 130             if QVerts:
 131                 verts = QVerts
 132             derivVerts = []
 133             for i in range(len(verts) - 1):
 134                 derivVerts.append(verts[i + 1] - verts[i])
 135             QVerts = derivVerts
 136     else:
 137         QVerts = verts
 138
 139     if len(verts[0]) == 3:
 140         point = Vector((0, 0, 0))
 141     if len(verts[0]) == 2:
 142         point = Vector((0, 0))
 143
 144     for i, vert in enumerate(QVerts):
 145         point += binom(order, i) * pow(t, i) * pow(1 - t, order - i) * vert
 146     deriv = point
 147
 148     return deriv
 149
 150
 151 # get curvature from first, second derivative
 152 def getCurvature(deriv1, deriv2):
 153     if deriv1.length == 0:  # in case of points in straight line
 154         curvature = 0
 155         return curvature
 156     curvature = (deriv1.cross(deriv2)).length / pow(deriv1.length, 3)
 157     return curvature
 158
 159
 160 # ### Ramer-Douglas-Peucker algorithm ###
 161
 162 # get altitude of vert
 163 def altitude(point1, point2, pointn):
 164     edge1 = point2 - point1
 165     edge2 = pointn - point1
 166     if edge2.length == 0:
 167         altitude = 0
 168         return altitude
 169     if edge1.length == 0:
 170         altitude = edge2.length
 171         return altitude
 172     alpha = edge1.angle(edge2)
 173     altitude = sin(alpha) * edge2.length
 174     return altitude
 175
 176
 177 # iterate through verts
 178 def iterate(points, newVerts, error):
 179     new = []
 180     for newIndex in range(len(newVerts) - 1):
 181         bigVert = 0
 182         alti_store = 0
 183         for i, point in enumerate(points[newVerts[newIndex] + 1: newVerts[newIndex + 1]]):
 184             alti = altitude(points[newVerts[newIndex]], points[newVerts[newIndex + 1]], point)
 185             if alti > alti_store:
 186                 alti_store = alti
 187                 if alti_store >= error:
 188                     bigVert = i + 1 + newVerts[newIndex]
 189         if bigVert:
 190             new.append(bigVert)
 191     if new == []:
 192         return False
 193     return new
 194
 195
 196 # get SplineVertIndices to keep
 197 def simplify_RDP(splineVerts, options):
 198     # main vars
 199     error = options[4]
 200
 201     # set first and last vert
 202     newVerts = [0, len(splineVerts) - 1]
 203
 204     # iterate through the points
 205     new = 1
 206     while new is not False:
 207         new = iterate(splineVerts, newVerts, error)
 208         if new:
 209             newVerts += new
 210             newVerts.sort()
 211     return newVerts
 212
 213
 214 # ### CURVE GENERATION ###
 215
 216 # set bezierhandles to auto
 217 def setBezierHandles(newCurve):
 218     # Faster:
 219     for spline in newCurve.data.splines:
 220         for p in spline.bezier_points:
 221             p.handle_left_type = 'AUTO'
 222             p.handle_right_type = 'AUTO'
 223
 224
 225 # get array of new coords for new spline from vertindices
 226 def vertsToPoints(newVerts, splineVerts, splineType):
 227     # main vars
 228     newPoints = []
 229
 230     # array for BEZIER spline output
 231     if splineType == 'BEZIER':
 232         for v in newVerts:
 233             newPoints += splineVerts[v].to_tuple()
 234
 235     # array for nonBEZIER output
 236     else:
 237         for v in newVerts:
 238             newPoints += (splineVerts[v].to_tuple())
 239             if splineType == 'NURBS':
 240                 newPoints.append(1)  # for nurbs w = 1
 241             else:                    # for poly w = 0
 242                 newPoints.append(0)
 243     return newPoints
 244
 245
 246 # ### MAIN OPERATIONS ###
 247
 248 def main(context, obj, options, curve_dimension):
 249     mode = options[0]
 250     output = options[1]
 251     degreeOut = options[5]
 252     keepShort = options[7]
 253     bpy.ops.object.select_all(action='DESELECT')
 254     scene = context.scene
 255     splines = obj.data.splines.values()
 256
 257     # create curvedatablock
 258     curve = bpy.data.curves.new("Simple_" + obj.name, type='CURVE')
 259     curve.dimensions = curve_dimension
 260
 261     # go through splines
 262     for spline_i, spline in enumerate(splines):
 263         # test if spline is a long enough
 264         if len(spline.points) >= 7 or keepShort:
 265             # check what type of spline to create
 266             if output == 'INPUT':
 267                 splineType = spline.type
 268             else:
 269                 splineType = output
 270
 271             # get vec3 list to simplify
 272             if spline.type == 'BEZIER':  # get bezierverts
 273                 splineVerts = [splineVert.co.copy()
 274                                for splineVert in spline.bezier_points.values()]
 275
 276             else:  # verts from all other types of curves
 277                 splineVerts = [splineVert.co.to_3d()
 278                                for splineVert in spline.points.values()]
 279
 280             # simplify spline according to mode
 281             if mode == 'DISTANCE':
 282                 newVerts = simplify_RDP(splineVerts, options)
 283
 284             if mode == 'CURVATURE':
 285                 newVerts = simplypoly(splineVerts, options)
 286
 287             # convert indices into vectors3D
 288             newPoints = vertsToPoints(newVerts, splineVerts, splineType)
 289
 290             # create new spline
 291             newSpline = curve.splines.new(type=splineType)
 292
 293             # put newPoints into spline according to type
 294             if splineType == 'BEZIER':
 295                 newSpline.bezier_points.add(int(len(newPoints) * 0.33))
 296                 newSpline.bezier_points.foreach_set('co', newPoints)
 297             else:
 298                 newSpline.points.add(int(len(newPoints) * 0.25 - 1))
 299                 newSpline.points.foreach_set('co', newPoints)
 300
 301             # set degree of outputNurbsCurve
 302             if output == 'NURBS':
 303                 newSpline.order_u = degreeOut
 304
 305             # splineoptions
 306             newSpline.use_endpoint_u = spline.use_endpoint_u
 307
 308     # create new object and put into scene
 309     newCurve = bpy.data.objects.new("Simple_" + obj.name, curve)
 310     scene.objects.link(newCurve)
 311     newCurve.select = True
 312
 313     scene.objects.active = newCurve
 314     newCurve.matrix_world = obj.matrix_world
 315
 316     # set bezierhandles to auto
 317     setBezierHandles(newCurve)
 318
 319     return
 320
 321
 322 # get preoperator fcurves
 323 def getFcurveData(obj):
 324     fcurves = []
 325     for fc in obj.animation_data.action.fcurves:
 326         if fc.select:
 327             fcVerts = [vcVert.co.to_3d()
 328                         for vcVert in fc.keyframe_points.values()]
 329             fcurves.append(fcVerts)
 330     return fcurves
 331
 332
 333 def selectedfcurves(obj):
 334     fcurves_sel = []
 335     for i, fc in enumerate(obj.animation_data.action.fcurves):
 336         if fc.select:
 337             fcurves_sel.append(fc)
 338     return fcurves_sel
 339
 340
 341 # fCurves Main
 342 def fcurves_simplify(context, obj, options, fcurves):
 343     # main vars
 344     mode = options[0]
 345
 346     # get indices of selected fcurves
 347     fcurve_sel = selectedfcurves(obj)
 348
 349     # go through fcurves
 350     for fcurve_i, fcurve in enumerate(fcurves):
 351         # test if fcurve is long enough
 352         if len(fcurve) >= 7:
 353             # simplify spline according to mode
 354             if mode == 'DISTANCE':
 355                 newVerts = simplify_RDP(fcurve, options)
 356
 357             if mode == 'CURVATURE':
 358                 newVerts = simplypoly(fcurve, options)
 359
 360             # convert indices into vectors3D
 361             newPoints = []
 362
 363             # this is different from the main() function for normal curves, different api...
 364             for v in newVerts:
 365                 newPoints.append(fcurve[v])
 366
 367             # remove all points from curve first
 368             for i in range(len(fcurve) - 1, 0, -1):
 369                 fcurve_sel[fcurve_i].keyframe_points.remove(fcurve_sel[fcurve_i].keyframe_points[i])
 370             # put newPoints into fcurve
 371             for v in newPoints:
 372                 fcurve_sel[fcurve_i].keyframe_points.insert(frame=v[0], value=v[1])
 373     return
 374
 375
 376 # ### MENU append ###
 377
 378 def menu_func(self, context):
 379     self.layout.operator("graph.simplify")
 380
 381
 382 def menu(self, context):
 383     self.layout.operator("curve.simplify", text="Curve Simplify", icon="CURVE_DATA")
 384
 385
 386 # ### ANIMATION CURVES OPERATOR ###
 387
 388 class GRAPH_OT_simplify(Operator):
 389     bl_idname = "graph.simplify"
 390     bl_label = "Simplify F-Curves"
 391     bl_description = ("Simplify selected Curves\n"
 392                       "Does not operate on short Splines (less than 6 points)")
 393     bl_options = {'REGISTER', 'UNDO'}
 394
 395     # Properties
 396     opModes = [
 397             ('DISTANCE', 'Distance', 'Distance-based simplification (Poly)'),
 398             ('CURVATURE', 'Curvature', 'Curvature-based simplification (RDP)')]
 399     mode = EnumProperty(
 400             name="Mode",
 401             description="Choose algorithm to use",
 402             items=opModes
 403             )
 404     k_thresh = FloatProperty(
 405             name="k",
 406             min=0, soft_min=0,
 407             default=0, precision=3,
 408             description="Threshold"
 409             )
 410     pointsNr = IntProperty(
 411             name="n",
 412             min=5, soft_min=5,
 413             max=16, soft_max=9,
 414             default=5,
 415             description="Degree of curve to get averaged curvatures"
 416             )
 417     error = FloatProperty(
 418             name="Error",
 419             description="Maximum allowed distance error",
 420             min=0.0, soft_min=0.0,
 421             default=0, precision=3
 422             )
 423     degreeOut = IntProperty(
 424             name="Degree",
 425             min=3, soft_min=3,
 426             max=7, soft_max=7,
 427             default=5,
 428             description="Degree of new curve"
 429             )
 430     dis_error = FloatProperty(
 431             name="Distance error",
 432             description="Maximum allowed distance error in Blender Units",
 433             min=0, soft_min=0,
 434             default=0.0, precision=3
 435             )
 436     fcurves = []
 437
 438     def draw(self, context):
 439         layout = self.layout
 440         col = layout.column()
 441
 442         col.label(text="Distance Error:")
 443         col.prop(self, "error", expand=True)
 444
 445     @classmethod
 446     def poll(cls, context):
 447         # Check for animdata
 448         obj = context.active_object
 449         fcurves = False
 450         if obj:
 451             animdata = obj.animation_data
 452             if animdata:
 453                 act = animdata.action
 454                 if act:
 455                     fcurves = act.fcurves
 456         return (obj and fcurves)
 457
 458     def execute(self, context):
 459         options = [
 460                 self.mode,       # 0
 461                 self.mode,       # 1
 462                 self.k_thresh,   # 2
 463                 self.pointsNr,   # 3
 464                 self.error,      # 4
 465                 self.degreeOut,  # 6
 466                 self.dis_error   # 7
 467                 ]
 468
 469         obj = context.active_object
 470
 471         if not self.fcurves:
 472             self.fcurves = getFcurveData(obj)
 473
 474         fcurves_simplify(context, obj, options, self.fcurves)
 475
 476         return {'FINISHED'}
 477
 478
 479 # ### Curves OPERATOR ###
 480 class CURVE_OT_simplify(Operator):
 481     bl_idname = "curve.simplify"
 482     bl_label = "Simplify Curves"
 483     bl_description = ("Simplify the existing Curve based upon the chosen settings\n"
 484                       "Notes: Needs an existing Curve object,\n"
 485                       "Outputs a new Curve with the Simple prefix in the name")
 486     bl_options = {'REGISTER', 'UNDO'}
 487
 488     # Properties
 489     opModes = [
 490             ('DISTANCE', 'Distance', 'Distance-based simplification (Poly)'),
 491             ('CURVATURE', 'Curvature', 'Curvature-based simplification (RDP)')
 492             ]
 493     mode = EnumProperty(
 494             name="Mode",
 495             description="Choose algorithm to use",
 496             items=opModes
 497             )
 498     SplineTypes = [
 499             ('INPUT', 'Input', 'Same type as input spline'),
 500             ('NURBS', 'Nurbs', 'NURBS'),
 501             ('BEZIER', 'Bezier', 'BEZIER'),
 502             ('POLY', 'Poly', 'POLY')
 503             ]
 504     output = EnumProperty(
 505             name="Output splines",
 506             description="Type of splines to output",
 507             items=SplineTypes
 508             )
 509     k_thresh = FloatProperty(
 510             name="k",
 511             min=0, soft_min=0,
 512             default=0, precision=3,
 513             description="Threshold"
 514             )
 515     pointsNr = IntProperty(name="n",
 516             min=5, soft_min=5,
 517             max=9, soft_max=9,
 518             default=5,
 519             description="Degree of curve to get averaged curvatures"
 520             )
 521     error = FloatProperty(
 522             name="Error",
 523             description="Maximum allowed distance error in Blender Units",
 524             min=0, soft_min=0,
 525             default=0.0, precision=3
 526             )
 527     degreeOut = IntProperty(name="Degree",
 528             min=3, soft_min=3,
 529             max=7, soft_max=7,
 530             default=5,
 531             description="Degree of new curve"
 532             )
 533     dis_error = FloatProperty(
 534             name="Distance error",
 535             description="Maximum allowed distance error in Blender Units",
 536             min=0, soft_min=0,
 537             default=0.0
 538             )
 539     keepShort = BoolProperty(
 540             name="Keep short splines",
 541             description="Keep short splines (less than 7 points)",
 542             default=True
 543             )
 544
 545     def draw(self, context):
 546         layout = self.layout
 547         col = layout.column()
 548
 549         col.label("Distance Error:")
 550         col.prop(self, "error", expand=True)
 551         col.prop(self, "output", text="Output", icon="OUTLINER_OB_CURVE")
 552         if self.output == "NURBS":
 553             col.prop(self, "degreeOut", expand=True)
 554         col.separator()
 555         col.prop(self, "keepShort", expand=True)
 556
 557     @classmethod
 558     def poll(cls, context):
 559         obj = context.active_object
 560         return (obj and obj.type == 'CURVE')
 561
 562     def execute(self, context):
 563         options = [
 564                 self.mode,       # 0
 565                 self.output,     # 1
 566                 self.k_thresh,   # 2
 567                 self.pointsNr,   # 3
 568                 self.error,      # 4
 569                 self.degreeOut,  # 5
 570                 self.dis_error,  # 6
 571                 self.keepShort   # 7
 572                 ]
 573         try:
 574             global_undo = bpy.context.user_preferences.edit.use_global_undo
 575             context.user_preferences.edit.use_global_undo = False
 576
 577             bpy.ops.object.mode_set(mode='OBJECT')
 578             obj = context.active_object
 579             curve_dimension = obj.data.dimensions
 580
 581             main(context, obj, options, curve_dimension)
 582
 583             context.user_preferences.edit.use_global_undo = global_undo
 584         except Exception as e:
 585             error_handlers(self, "curve.simplify", e, "Simplify Curves")
 586
 587             context.user_preferences.edit.use_global_undo = global_undo
 588             return {'CANCELLED'}
 589
 590         return {'FINISHED'}
 591
 592
 593 # Register
 594
 595 def register():
 596     bpy.utils.register_module(__name__)
 597
 598     bpy.types.GRAPH_MT_channel.append(menu_func)
 599     bpy.types.DOPESHEET_MT_channel.append(menu_func)
 600     bpy.types.INFO_MT_curve_add.append(menu)
 601
 602
 603 def unregister():
 604     bpy.types.GRAPH_MT_channel.remove(menu_func)
 605     bpy.types.DOPESHEET_MT_channel.remove(menu_func)
 606     bpy.types.INFO_MT_curve_add.remove(menu)
 607
 608     bpy.utils.unregister_module(__name__)
 609
 610
 611 if __name__ == "__main__":
 612     register()