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, 80, 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     coll = context.view_layer.active_layer_collection.collection
 311     coll.objects.link(newCurve)
 312     newCurve.select_set(True)
 313
 314     context.view_layer.objects.active = newCurve
 315     newCurve.matrix_world = obj.matrix_world
 316
 317     # set bezierhandles to auto
 318     setBezierHandles(newCurve)
 319
 320     return
 321
 322
 323 # get preoperator fcurves
 324 def getFcurveData(obj):
 325     fcurves = []
 326     for fc in obj.animation_data.action.fcurves:
 327         if fc.select:
 328             fcVerts = [vcVert.co.to_3d()
 329                        for vcVert in fc.keyframe_points.values()]
 330             fcurves.append(fcVerts)
 331     return fcurves
 332
 333
 334 def selectedfcurves(obj):
 335     fcurves_sel = []
 336     for i, fc in enumerate(obj.animation_data.action.fcurves):
 337         if fc.select:
 338             fcurves_sel.append(fc)
 339     return fcurves_sel
 340
 341
 342 # fCurves Main
 343 def fcurves_simplify(context, obj, options, fcurves):
 344     # main vars
 345     mode = options[0]
 346
 347     # get indices of selected fcurves
 348     fcurve_sel = selectedfcurves(obj)
 349
 350     # go through fcurves
 351     for fcurve_i, fcurve in enumerate(fcurves):
 352         # test if fcurve is long enough
 353         if len(fcurve) >= 7:
 354             # simplify spline according to mode
 355             if mode == 'DISTANCE':
 356                 newVerts = simplify_RDP(fcurve, options)
 357
 358             if mode == 'CURVATURE':
 359                 newVerts = simplypoly(fcurve, options)
 360
 361             # convert indices into vectors3D
 362             newPoints = []
 363
 364             # this is different from the main() function for normal curves, different api...
 365             for v in newVerts:
 366                 newPoints.append(fcurve[v])
 367
 368             # remove all points from curve first
 369             for i in range(len(fcurve) - 1, 0, -1):
 370                 fcurve_sel[fcurve_i].keyframe_points.remove(fcurve_sel[fcurve_i].keyframe_points[i])
 371             # put newPoints into fcurve
 372             for v in newPoints:
 373                 fcurve_sel[fcurve_i].keyframe_points.insert(frame=v[0], value=v[1])
 374     return
 375
 376
 377 # ### MENU append ###
 378
 379 def menu_func(self, context):
 380     self.layout.operator("graph.simplify")
 381
 382
 383 def menu(self, context):
 384     self.layout.operator("curve.simplify", text="Curve Simplify", icon="CURVE_DATA")
 385
 386
 387 # ### ANIMATION CURVES OPERATOR ###
 388
 389 class GRAPH_OT_simplify(Operator):
 390     bl_idname = "graph.simplify"
 391     bl_label = "Simplify F-Curves"
 392     bl_description = ("Simplify selected Curves\n"
 393                       "Does not operate on short Splines (less than 6 points)")
 394     bl_options = {'REGISTER', 'UNDO'}
 395
 396     # Properties
 397     opModes = [
 398             ('DISTANCE', 'Distance', 'Distance-based simplification (Poly)'),
 399             ('CURVATURE', 'Curvature', 'Curvature-based simplification (RDP)')]
 400     mode: EnumProperty(
 401             name="Mode",
 402             description="Choose algorithm to use",
 403             items=opModes
 404             )
 405     k_thresh: FloatProperty(
 406             name="k",
 407             min=0, soft_min=0,
 408             default=0, precision=3,
 409             description="Threshold"
 410             )
 411     pointsNr: IntProperty(
 412             name="n",
 413             min=5, soft_min=5,
 414             max=16, soft_max=9,
 415             default=5,
 416             description="Degree of curve to get averaged curvatures"
 417             )
 418     error: FloatProperty(
 419             name="Error",
 420             description="Maximum allowed distance error",
 421             min=0.0, soft_min=0.0,
 422             default=0, precision=3
 423             )
 424     degreeOut: IntProperty(
 425             name="Degree",
 426             min=3, soft_min=3,
 427             max=7, soft_max=7,
 428             default=5,
 429             description="Degree of new curve"
 430             )
 431     dis_error: FloatProperty(
 432             name="Distance error",
 433             description="Maximum allowed distance error in Blender Units",
 434             min=0, soft_min=0,
 435             default=0.0, precision=3
 436             )
 437     fcurves = []
 438
 439     def draw(self, context):
 440         layout = self.layout
 441         col = layout.column()
 442
 443         col.label(text="Distance Error:")
 444         col.prop(self, "error", expand=True)
 445
 446     @classmethod
 447     def poll(cls, context):
 448         # Check for animdata
 449         obj = context.active_object
 450         fcurves = False
 451         if obj:
 452             animdata = obj.animation_data
 453             if animdata:
 454                 act = animdata.action
 455                 if act:
 456                     fcurves = act.fcurves
 457         return (obj and fcurves)
 458
 459     def execute(self, context):
 460         options = [
 461                 self.mode,       # 0
 462                 self.mode,       # 1
 463                 self.k_thresh,   # 2
 464                 self.pointsNr,   # 3
 465                 self.error,      # 4
 466                 self.degreeOut,  # 6
 467                 self.dis_error   # 7
 468                 ]
 469
 470         obj = context.active_object
 471
 472         if not self.fcurves:
 473             self.fcurves = getFcurveData(obj)
 474
 475         fcurves_simplify(context, obj, options, self.fcurves)
 476
 477         return {'FINISHED'}
 478
 479
 480 # ### Curves OPERATOR ###
 481 class CURVE_OT_simplify(Operator):
 482     bl_idname = "curve.simplify"
 483     bl_label = "Simplify Curves"
 484     bl_description = ("Simplify the existing Curve based upon the chosen settings\n"
 485                       "Notes: Needs an existing Curve object,\n"
 486                       "Outputs a new Curve with the Simple prefix in the name")
 487     bl_options = {'REGISTER', 'UNDO'}
 488
 489     # Properties
 490     opModes = [
 491             ('DISTANCE', 'Distance', 'Distance-based simplification (Poly)'),
 492             ('CURVATURE', 'Curvature', 'Curvature-based simplification (RDP)')
 493             ]
 494     mode: EnumProperty(
 495             name="Mode",
 496             description="Choose algorithm to use",
 497             items=opModes
 498             )
 499     SplineTypes = [
 500             ('INPUT', 'Input', 'Same type as input spline'),
 501             ('NURBS', 'Nurbs', 'NURBS'),
 502             ('BEZIER', 'Bezier', 'BEZIER'),
 503             ('POLY', 'Poly', 'POLY')
 504             ]
 505     output: EnumProperty(
 506             name="Output splines",
 507             description="Type of splines to output",
 508             items=SplineTypes
 509             )
 510     k_thresh: FloatProperty(
 511             name="k",
 512             min=0, soft_min=0,
 513             default=0, precision=3,
 514             description="Threshold"
 515             )
 516     pointsNr: IntProperty(
 517             name="n",
 518             min=5, soft_min=5,
 519             max=9, soft_max=9,
 520             default=5,
 521             description="Degree of curve to get averaged curvatures"
 522             )
 523     error: FloatProperty(
 524             name="Error",
 525             description="Maximum allowed distance error in Blender Units",
 526             min=0, soft_min=0,
 527             default=0.0, precision=3
 528             )
 529     degreeOut: IntProperty(
 530             name="Degree",
 531             min=3, soft_min=3,
 532             max=7, soft_max=7,
 533             default=5,
 534             description="Degree of new curve"
 535             )
 536     dis_error: FloatProperty(
 537             name="Distance error",
 538             description="Maximum allowed distance error in Blender Units",
 539             min=0, soft_min=0,
 540             default=0.0
 541             )
 542     keepShort: BoolProperty(
 543             name="Keep short splines",
 544             description="Keep short splines (less than 7 points)",
 545             default=True
 546             )
 547
 548     def draw(self, context):
 549         layout = self.layout
 550         col = layout.column()
 551
 552         col.label(text="Distance Error:")
 553         col.prop(self, "error", expand=True)
 554         col.prop(self, "output", text="Output", icon="OUTLINER_OB_CURVE")
 555         if self.output == "NURBS":
 556             col.prop(self, "degreeOut", expand=True)
 557         col.separator()
 558         col.prop(self, "keepShort", expand=True)
 559
 560     @classmethod
 561     def poll(cls, context):
 562         obj = context.active_object
 563         return (obj and obj.type == 'CURVE')
 564
 565     def execute(self, context):
 566         options = [
 567                 self.mode,       # 0
 568                 self.output,     # 1
 569                 self.k_thresh,   # 2
 570                 self.pointsNr,   # 3
 571                 self.error,      # 4
 572                 self.degreeOut,  # 5
 573                 self.dis_error,  # 6
 574                 self.keepShort   # 7
 575                 ]
 576         try:
 577             global_undo = bpy.context.preferences.edit.use_global_undo
 578             context.preferences.edit.use_global_undo = False
 579
 580             bpy.ops.object.mode_set(mode='OBJECT')
 581             obj = context.active_object
 582             curve_dimension = obj.data.dimensions
 583
 584             main(context, obj, options, curve_dimension)
 585
 586             context.preferences.edit.use_global_undo = global_undo
 587         except Exception as e:
 588             error_handlers(self, "curve.simplify", e, "Simplify Curves")
 589
 590             context.preferences.edit.use_global_undo = global_undo
 591             return {'CANCELLED'}
 592
 593         return {'FINISHED'}
 594
 595
 596 # Register
 597 classes = [
 598     GRAPH_OT_simplify,
 599     CURVE_OT_simplify,
 600 ]
 601
 602
 603 def register():
 604     from bpy.utils import register_class
 605     for cls in classes:
 606         register_class(cls)
 607
 608     bpy.types.GRAPH_MT_channel.append(menu_func)
 609     bpy.types.DOPESHEET_MT_channel.append(menu_func)
 610     bpy.types.VIEW3D_MT_curve_add.append(menu)
 611
 612
 613 def unregister():
 614     from bpy.utils import unregister_class
 615     for cls in reversed(classes):
 616         unregister_class(cls)
 617
 618     bpy.types.GRAPH_MT_channel.remove(menu_func)
 619     bpy.types.DOPESHEET_MT_channel.remove(menu_func)
 620     bpy.types.VIEW3D_MT_curve_add.remove(menu)
 621
 622
 623 if __name__ == "__main__":
 624     register()