curve_simplify.py

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