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, 1),
  23     "blender": (2, 75, 0),
  24     "location": "Search > Simplify Curves",
  25     "description": "Simplifies 3D Curve objects and animation F-Curves",
  26     "warning": "",
  27     "wiki_url": "http://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 ####################################################
  37 import bpy
  38 from bpy.props import *
  39 import mathutils
  40 import math
  41
  42 from bpy.types import Menu
  43
  44
  45     ## Check for curve
  46
  47 ##############################
  48 #### simplipoly algorithm ####
  49 ##############################
  50 # get SplineVertIndices to keep
  51 def simplypoly(splineVerts, options):
  52     # main vars
  53     newVerts = [] # list of vertindices to keep
  54     points = splineVerts # list of 3dVectors
  55     pointCurva = [] # table with curvatures
  56     curvatures = [] # averaged curvatures per vert
  57     for p in points:
  58         pointCurva.append([])
  59     order = options[3] # order of sliding beziercurves
  60     k_thresh = options[2] # curvature threshold
  61     dis_error = options[6] # additional distance error
  62
  63     # get curvatures per vert
  64     for i, point in enumerate(points[:-(order-1)]):
  65         BVerts = points[i:i+order]
  66         for b, BVert in enumerate(BVerts[1:-1]):
  67             deriv1 = getDerivative(BVerts, 1/(order-1), order-1)
  68             deriv2 = getDerivative(BVerts, 1/(order-1), order-2)
  69             curva = getCurvature(deriv1, deriv2)
  70             pointCurva[i+b+1].append(curva)
  71
  72     # average the curvatures
  73     for i in range(len(points)):
  74         avgCurva = sum(pointCurva[i]) / (order-1)
  75         curvatures.append(avgCurva)
  76
  77     # get distancevalues per vert - same as Ramer-Douglas-Peucker
  78     # but for every vert
  79     distances = [0.0] #first vert is always kept
  80     for i, point in enumerate(points[1:-1]):
  81         dist = altitude(points[i], points[i+2], points[i+1])
  82         distances.append(dist)
  83     distances.append(0.0) # last vert is always kept
  84
  85     # generate list of vertindices to keep
  86     # tested against averaged curvatures and distances of neighbour verts
  87     newVerts.append(0) # first vert is always kept
  88     for i, curv in enumerate(curvatures):
  89         if (curv >= k_thresh*0.01
  90         or distances[i] >= dis_error*0.1):
  91             newVerts.append(i)
  92     newVerts.append(len(curvatures)-1) # last vert is always kept
  93
  94     return newVerts
  95
  96 # get binomial coefficient
  97 def binom(n, m):
  98     b = [0] * (n+1)
  99     b[0] = 1
 100     for i in range(1, n+1):
 101         b[i] = 1
 102         j = i-1
 103         while j > 0:
 104             b[j] += b[j-1]
 105             j-= 1
 106     return b[m]
 107
 108 # get nth derivative of order(len(verts)) bezier curve
 109 def getDerivative(verts, t, nth):
 110     order = len(verts) - 1 - nth
 111     QVerts = []
 112
 113     if nth:
 114         for i in range(nth):
 115             if QVerts:
 116                 verts = QVerts
 117             derivVerts = []
 118             for i in range(len(verts)-1):
 119                 derivVerts.append(verts[i+1] - verts[i])
 120             QVerts = derivVerts
 121     else:
 122         QVerts = verts
 123
 124     if len(verts[0]) == 3:
 125         point = mathutils.Vector((0, 0, 0))
 126     if len(verts[0]) == 2:
 127         point = mathutils.Vector((0, 0))
 128
 129     for i, vert in enumerate(QVerts):
 130         point += binom(order, i) * math.pow(t, i) * math.pow(1-t, order-i) * vert
 131     deriv = point
 132
 133     return deriv
 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 / math.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 = math.sin(alpha) * edge2.length
 158     return altitude
 159
 160 # iterate through verts
 161 def iterate(points, newVerts, error):
 162     new = []
 163     for newIndex in range(len(newVerts)-1):
 164         bigVert = 0
 165         alti_store = 0
 166         for i, point in enumerate(points[newVerts[newIndex]+1:newVerts[newIndex+1]]):
 167             alti = altitude(points[newVerts[newIndex]], points[newVerts[newIndex+1]], point)
 168             if alti > alti_store:
 169                 alti_store = alti
 170                 if alti_store >= error:
 171                     bigVert = i+1+newVerts[newIndex]
 172         if bigVert:
 173             new.append(bigVert)
 174     if new == []:
 175         return False
 176     return new
 177
 178 #### get SplineVertIndices to keep
 179 def simplify_RDP(splineVerts, options):
 180     #main vars
 181     error = options[4]
 182
 183     # set first and last vert
 184     newVerts = [0, len(splineVerts)-1]
 185
 186     # iterate through the points
 187     new = 1
 188     while new != False:
 189         new = iterate(splineVerts, newVerts, error)
 190         if new:
 191             newVerts += new
 192             newVerts.sort()
 193     return newVerts
 194
 195 ##########################
 196 #### CURVE GENERATION ####
 197 ##########################
 198 # set bezierhandles to auto
 199 def setBezierHandles(newCurve):
 200
 201     #bpy.ops.object.mode_set(mode='EDIT', toggle=True)
 202     #bpy.ops.curve.select_all(action='SELECT')
 203     #bpy.ops.curve.handle_type_set(type='AUTOMATIC')
 204     #bpy.ops.object.mode_set(mode='OBJECT', toggle=True)
 205
 206     # Faster:
 207     for spline in newCurve.data.splines:
 208         for p in spline.bezier_points:
 209             p.handle_left_type = 'AUTO'
 210             p.handle_right_type = 'AUTO'
 211
 212 # get array of new coords for new spline from vertindices
 213 def vertsToPoints(newVerts, splineVerts, splineType):
 214     # main vars
 215     newPoints = []
 216
 217     # array for BEZIER spline output
 218     if splineType == 'BEZIER':
 219         for v in newVerts:
 220             newPoints += splineVerts[v].to_tuple()
 221
 222     # array for nonBEZIER output
 223     else:
 224         for v in newVerts:
 225             newPoints += (splineVerts[v].to_tuple())
 226             if splineType == 'NURBS':
 227                 newPoints.append(1) #for nurbs w=1
 228             else: #for poly w=0
 229                 newPoints.append(0)
 230     return newPoints
 231
 232 #########################
 233 #### MAIN OPERATIONS ####
 234 #########################
 235
 236 def main(context, obj, options):
 237     #print("\n_______START_______")
 238     # main vars
 239     mode = options[0]
 240     output = options[1]
 241     degreeOut = options[5]
 242     keepShort = options[7]
 243     bpy.ops.object.select_all(action='DESELECT')
 244     scene = context.scene
 245     splines = obj.data.splines.values()
 246
 247     # create curvedatablock
 248     curve = bpy.data.curves.new("Simple_"+obj.name, type = 'CURVE')
 249
 250     # go through splines
 251     for spline_i, spline in enumerate(splines):
 252         # test if spline is a long enough
 253         if len(spline.points) >= 7 or keepShort:
 254             #check what type of spline to create
 255             if output == 'INPUT':
 256                 splineType = spline.type
 257             else:
 258                 splineType = output
 259
 260             # get vec3 list to simplify
 261             if spline.type == 'BEZIER': # get bezierverts
 262                 splineVerts = [splineVert.co.copy()
 263                                 for splineVert in spline.bezier_points.values()]
 264
 265             else: # verts from all other types of curves
 266                 splineVerts = [splineVert.co.to_3d()
 267                                 for splineVert in spline.points.values()]
 268
 269             # simplify spline according to mode
 270             if mode == 'DISTANCE':
 271                 newVerts = simplify_RDP(splineVerts, options)
 272
 273             if mode == 'CURVATURE':
 274                 newVerts = simplypoly(splineVerts, options)
 275
 276             # convert indices into vectors3D
 277             newPoints = vertsToPoints(newVerts, splineVerts, splineType)
 278
 279             # create new spline
 280             newSpline = curve.splines.new(type = splineType)
 281
 282             # put newPoints into spline according to type
 283             if splineType == 'BEZIER':
 284                 newSpline.bezier_points.add(int(len(newPoints)*0.33))
 285                 newSpline.bezier_points.foreach_set('co', newPoints)
 286             else:
 287                 newSpline.points.add(int(len(newPoints)*0.25 - 1))
 288                 newSpline.points.foreach_set('co', newPoints)
 289
 290             # set degree of outputNurbsCurve
 291             if output == 'NURBS':
 292                 newSpline.order_u = degreeOut
 293
 294             # splineoptions
 295             newSpline.use_endpoint_u = spline.use_endpoint_u
 296
 297     # create ne object and put into scene
 298     newCurve = bpy.data.objects.new("Simple_"+obj.name, curve)
 299     scene.objects.link(newCurve)
 300     newCurve.select = True
 301     scene.objects.active = newCurve
 302     newCurve.matrix_world = obj.matrix_world
 303
 304     # set bezierhandles to auto
 305     setBezierHandles(newCurve)
 306
 307     #print("________END________\n")
 308     return
 309
 310 ##################
 311 ## get preoperator fcurves
 312 def getFcurveData(obj):
 313     fcurves = []
 314     for fc in obj.animation_data.action.fcurves:
 315         if fc.select:
 316             fcVerts = [vcVert.co.to_3d()
 317                         for vcVert in fc.keyframe_points.values()]
 318             fcurves.append(fcVerts)
 319     return fcurves
 320
 321 def selectedfcurves(obj):
 322     fcurves_sel = []
 323     for i, fc in enumerate(obj.animation_data.action.fcurves):
 324         if fc.select:
 325             fcurves_sel.append(fc)
 326     return fcurves_sel
 327
 328 ###########################################################
 329 ## fCurves Main
 330 def fcurves_simplify(context, obj, options, fcurves):
 331     # main vars
 332     mode = options[0]
 333
 334     #get indices of selected fcurves
 335     fcurve_sel = selectedfcurves(obj)
 336
 337     # go through fcurves
 338     for fcurve_i, fcurve in enumerate(fcurves):
 339         # test if fcurve is long enough
 340         if len(fcurve) >= 7:
 341
 342             # simplify spline according to mode
 343             if mode == 'DISTANCE':
 344                 newVerts = simplify_RDP(fcurve, options)
 345
 346             if mode == 'CURVATURE':
 347                 newVerts = simplypoly(fcurve, options)
 348
 349             # convert indices into vectors3D
 350             newPoints = []
 351
 352             #this is different from the main() function for normal curves, different api...
 353             for v in newVerts:
 354                 newPoints.append(fcurve[v])
 355
 356             #remove all points from curve first
 357             for i in range(len(fcurve)-1,0,-1):
 358                 fcurve_sel[fcurve_i].keyframe_points.remove(fcurve_sel[fcurve_i].keyframe_points[i])
 359             # put newPoints into fcurve
 360             for v in newPoints:
 361                 fcurve_sel[fcurve_i].keyframe_points.insert(frame=v[0],value=v[1])
 362             #fcurve.points.foreach_set('co', newPoints)
 363     return
 364
 365 ### MENU ###
 366
 367 class GRAPH_OT_simplifyf(bpy.types.Menu):
 368     bl_space_type = "GRAPH_EDITOR"
 369     bl_label = "Simplify F Curves"
 370
 371     def draw(self, context):
 372         layout = self.layout
 373
 374 def menu_func(self, context):
 375         self.layout.operator(GRAPH_OT_simplify.bl_idname)
 376
 377 class CurveMenu(Menu):
 378     bl_space_type = "3D_VIEW"
 379     bl_label = "Simplify Curves"
 380
 381     def draw(self, context):
 382         layout = self.layout
 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(bpy.types.Operator):
 391     """"""
 392     bl_idname = "graph.simplify"
 393     bl_label = "Simplifiy F-Curves"
 394     bl_description = "Simplify selected Curves"
 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(name="Mode",
 402                             description="Choose algorithm to use",
 403                             items=opModes)
 404     k_thresh = FloatProperty(name="k",
 405                             min=0, soft_min=0,
 406                             default=0, precision=3,
 407                             description="Threshold")
 408     pointsNr = IntProperty(name="n",
 409                             min=5, soft_min=5,
 410                             max=16, soft_max=9,
 411                             default=5,
 412                             description="Degree of curve to get averaged curvatures")
 413     error = FloatProperty(name="Error",
 414                             description="Maximum error to allow - distance",
 415                             min=0.0, soft_min=0.0,
 416                             default=0, precision=3)
 417     degreeOut = IntProperty(name="Degree",
 418                             min=3, soft_min=3,
 419                             max=7, soft_max=7,
 420                             default=5,
 421                             description="Degree of new curve")
 422     dis_error = FloatProperty(name="Distance error",
 423                             description="Maximum error in Blender Units to allow - distance",
 424                             min=0, soft_min=0,
 425                             default=0.0, precision=3)
 426     fcurves = []
 427
 428     '''  Remove curvature mode as long as it isn't significantly improved
 429
 430     def draw(self, context):
 431         layout = self.layout
 432         col = layout.column()
 433         col.label('Mode:')
 434         col.prop(self, 'mode', expand=True)
 435         if self.mode == 'DISTANCE':
 436             box = layout.box()
 437             box.label(self.mode, icon='ARROW_LEFTRIGHT')
 438             box.prop(self, 'error', expand=True)
 439         if self.mode == 'CURVATURE':
 440             box = layout.box()
 441             box.label('Degree', icon='SMOOTHCURVE')
 442             box.prop(self, 'pointsNr', expand=True)
 443             box.label('Threshold', icon='PARTICLE_PATH')
 444             box.prop(self, 'k_thresh', expand=True)
 445             box.label('Distance', icon='ARROW_LEFTRIGHT')
 446             box.prop(self, 'dis_error', expand=True)
 447         col = layout.column()
 448     '''
 449
 450     def draw(self, context):
 451         layout = self.layout
 452         col = layout.column()
 453         col.label(text = "Simplify F-Curves")
 454         col.prop(self, 'error', expand=True)
 455
 456     ## Check for animdata
 457     @classmethod
 458     def poll(cls, context):
 459         obj = context.active_object
 460         fcurves = False
 461         if obj:
 462             animdata = obj.animation_data
 463             if animdata:
 464                 act = animdata.action
 465                 if act:
 466                     fcurves = act.fcurves
 467         return (obj and fcurves)
 468
 469     ## execute
 470     def execute(self, context):
 471         #print("------START------")
 472
 473         options = [
 474                 self.mode,       #0
 475                 self.mode,       #1
 476                 self.k_thresh,   #2
 477                 self.pointsNr,   #3
 478                 self.error,      #4
 479                 self.degreeOut,  #6
 480                 self.dis_error]  #7
 481
 482         obj = context.active_object
 483
 484         if not self.fcurves:
 485             self.fcurves = getFcurveData(obj)
 486
 487         fcurves_simplify(context, obj, options, self.fcurves)
 488
 489         #print("-------END-------")
 490         return {'FINISHED'}
 491
 492 ###########################
 493 ##### Curves OPERATOR #####
 494 ###########################
 495 class CURVE_OT_simplify(bpy.types.Operator):
 496     """"""
 497     bl_idname = "curve.simplify"
 498     bl_label = "Simplifiy Curves"
 499     bl_description = "Simplify Curves"
 500     bl_options = {'REGISTER', 'UNDO'}
 501
 502     ## Properties
 503     opModes = [
 504             ('DISTANCE', 'Distance', 'Distance-based simplification (Poly)'),
 505             ('CURVATURE', 'Curvature', 'Curvature-based simplification (RDP)')]
 506     mode = EnumProperty(name="Mode",
 507                             description="Choose algorithm to use",
 508                             items=opModes)
 509     SplineTypes = [
 510                 ('INPUT', 'Input', 'Same type as input spline'),
 511                 ('NURBS', 'Nurbs', 'NURBS'),
 512                 ('BEZIER', 'Bezier', 'BEZIER'),
 513                 ('POLY', 'Poly', 'POLY')]
 514     output = EnumProperty(name="Output splines",
 515                             description="Type of splines to output",
 516                             items=SplineTypes)
 517     k_thresh = FloatProperty(name="k",
 518                             min=0, soft_min=0,
 519                             default=0, precision=3,
 520                             description="Threshold")
 521     pointsNr = IntProperty(name="n",
 522                             min=5, soft_min=5,
 523                             max=9, soft_max=9,
 524                             default=5,
 525                             description="Degree of curve to get averaged curvatures")
 526     error = FloatProperty(name="Error in Blender Units",
 527                             description="Maximum error in Blender Units to allow - distance",
 528                             min=0, soft_min=0,
 529                             default=0.0, precision=3)
 530     degreeOut = IntProperty(name="Degree",
 531                             min=3, soft_min=3,
 532                             max=7, soft_max=7,
 533                             default=5,
 534                             description="Degree of new curve")
 535     dis_error = FloatProperty(name="Distance error",
 536                             description="Maximum error in Blender Units to allow - distance",
 537                             min=0, soft_min=0,
 538                             default=0.0)
 539     keepShort = BoolProperty(name="Keep short splines",
 540                             description="Keep short splines (less then 7 points)",
 541                             default=True)
 542
 543     '''  Remove curvature mode as long as it isn't significantly improved
 544
 545     def draw(self, context):
 546         layout = self.layout
 547         col = layout.column()
 548         col.label('Mode:')
 549         col.prop(self, 'mode', expand=True)
 550         if self.mode == 'DISTANCE':
 551             box = layout.box()
 552             box.label(self.mode, icon='ARROW_LEFTRIGHT')
 553             box.prop(self, 'error', expand=True)
 554         if self.mode == 'CURVATURE':
 555             box = layout.box()
 556             box.label('Degree', icon='SMOOTHCURVE')
 557             box.prop(self, 'pointsNr', expand=True)
 558             box.label('Threshold', icon='PARTICLE_PATH')
 559             box.prop(self, 'k_thresh', expand=True)
 560             box.label('Distance', icon='ARROW_LEFTRIGHT')
 561             box.prop(self, 'dis_error', expand=True)
 562         col = layout.column()
 563         col.separator()
 564         col.prop(self, 'output', text='Output', icon='OUTLINER_OB_CURVE')
 565         if self.output == 'NURBS':
 566             col.prop(self, 'degreeOut', expand=True)
 567         col.prop(self, 'keepShort', expand=True)
 568     '''
 569
 570     def draw(self, context):
 571         layout = self.layout
 572         col = layout.column()
 573         col.prop(self, 'error', expand=True)
 574         col.prop(self, 'output', text='Output', icon='OUTLINER_OB_CURVE')
 575         if self.output == 'NURBS':
 576             col.prop(self, 'degreeOut', expand=True)
 577         col.prop(self, 'keepShort', expand=True)
 578
 579
 580     @classmethod
 581     def poll(cls, context):
 582         obj = context.active_object
 583         return (obj and obj.type == 'CURVE')
 584
 585     ## execute
 586     def execute(self, context):
 587         #print("------START------")
 588
 589         options = [
 590                 self.mode,       #0
 591                 self.output,     #1
 592                 self.k_thresh,   #2
 593                 self.pointsNr,   #3
 594                 self.error,      #4
 595                 self.degreeOut,  #5
 596                 self.dis_error,  #6
 597                 self.keepShort]  #7
 598
 599
 600         bpy.context.user_preferences.edit.use_global_undo = False
 601
 602         bpy.ops.object.mode_set(mode='OBJECT', toggle=True)
 603         obj = context.active_object
 604
 605         main(context, obj, options)
 606
 607         bpy.context.user_preferences.edit.use_global_undo = True
 608
 609         #print("-------END-------")
 610         return {'FINISHED'}
 611
 612 #################################################
 613 #### REGISTER ###################################
 614 #################################################
 615 def register():
 616     bpy.utils.register_module(__name__)
 617
 618     bpy.types.GRAPH_MT_channel.append(menu_func)
 619     bpy.types.DOPESHEET_MT_channel.append(menu_func)
 620     bpy.types.INFO_MT_curve_add.append(menu)
 621
 622 def unregister():
 623
 624     bpy.types.GRAPH_MT_channel.remove(menu_func)
 625     bpy.types.DOPESHEET_MT_channel.remove(menu_func)
 626     bpy.types.INFO_MT_curve_add.remove(menu)
 627
 628     bpy.utils.unregister_module(__name__)
 629
 630 if __name__ == "__main__":
 631     register()
 632