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