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