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 curves and fcurves",
  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 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     bpy.ops.object.mode_set(mode='EDIT', toggle=True)
 197     bpy.ops.curve.select_all(action='SELECT')
 198     bpy.ops.curve.handle_type_set(type='AUTOMATIC')
 199     bpy.ops.object.mode_set(mode='OBJECT', toggle=True)
 200
 201 # get array of new coords for new spline from vertindices
 202 def vertsToPoints(newVerts, splineVerts, splineType):
 203     # main vars
 204     newPoints = []
 205
 206     # array for BEZIER spline output
 207     if splineType == 'BEZIER':
 208         for v in newVerts:
 209             newPoints += splineVerts[v].to_tuple()
 210
 211     # array for nonBEZIER output
 212     else:
 213         for v in newVerts:
 214             newPoints += (splineVerts[v].to_tuple())
 215             if splineType == 'NURBS':
 216                 newPoints.append(1) #for nurbs w=1
 217             else: #for poly w=0
 218                 newPoints.append(0)
 219     return newPoints
 220
 221 #########################
 222 #### MAIN OPERATIONS ####
 223 #########################
 224
 225 def main(context, obj, options):
 226     #print("\n_______START_______")
 227     # main vars
 228     mode = options[0]
 229     output = options[1]
 230     degreeOut = options[5]
 231     keepShort = options[7]
 232     bpy.ops.object.select_all(action='DESELECT')
 233     scene = context.scene
 234     splines = obj.data.splines.values()
 235
 236     # create curvedatablock
 237     curve = bpy.data.curves.new("simple_"+obj.name, type = 'CURVE')
 238
 239     # go through splines
 240     for spline_i, spline in enumerate(splines):
 241         # test if spline is a long enough
 242         if len(spline.points) >= 7 or keepShort:
 243             #check what type of spline to create
 244             if output == 'INPUT':
 245                 splineType = spline.type
 246             else:
 247                 splineType = output
 248
 249             # get vec3 list to simplify
 250             if spline.type == 'BEZIER': # get bezierverts
 251                 splineVerts = [splineVert.co.copy()
 252                                 for splineVert in spline.bezier_points.values()]
 253
 254             else: # verts from all other types of curves
 255                 splineVerts = [splineVert.co.to_3d()
 256                                 for splineVert in spline.points.values()]
 257
 258             # simplify spline according to mode
 259             if mode == 'distance':
 260                 newVerts = simplify_RDP(splineVerts, options)
 261
 262             if mode == 'curvature':
 263                 newVerts = simplypoly(splineVerts, options)
 264
 265             # convert indices into vectors3D
 266             newPoints = vertsToPoints(newVerts, splineVerts, splineType)
 267
 268             # create new spline
 269             newSpline = curve.splines.new(type = splineType)
 270
 271             # put newPoints into spline according to type
 272             if splineType == 'BEZIER':
 273                 newSpline.bezier_points.add(int(len(newPoints)*0.33))
 274                 newSpline.bezier_points.foreach_set('co', newPoints)
 275             else:
 276                 newSpline.points.add(int(len(newPoints)*0.25 - 1))
 277                 newSpline.points.foreach_set('co', newPoints)
 278
 279             # set degree of outputNurbsCurve
 280             if output == 'NURBS':
 281                 newSpline.order_u = degreeOut
 282
 283             # splineoptions
 284             newSpline.use_endpoint_u = spline.use_endpoint_u
 285
 286     # create ne object and put into scene
 287     newCurve = bpy.data.objects.new("simple_"+obj.name, curve)
 288     scene.objects.link(newCurve)
 289     newCurve.select = True
 290     scene.objects.active = newCurve
 291     newCurve.matrix_world = obj.matrix_world
 292
 293     # set bezierhandles to auto
 294     setBezierHandles(newCurve)
 295
 296     #print("________END________\n")
 297     return
 298
 299 ##################
 300 ## get preoperator fcurves
 301 def getFcurveData(obj):
 302     fcurves = []
 303     for fc in obj.animation_data.action.fcurves:
 304         if fc.select:
 305             fcVerts = [vcVert.co.to_3d()
 306                         for vcVert in fc.keyframe_points.values()]
 307             fcurves.append(fcVerts)
 308     return fcurves
 309
 310 def selectedfcurves(obj):
 311     fcurves_sel = []
 312     for i, fc in enumerate(obj.animation_data.action.fcurves):
 313         if fc.select:
 314             fcurves_sel.append(fc)
 315     return fcurves_sel
 316
 317 ###########################################################
 318 ## fCurves Main
 319 def fcurves_simplify(context, obj, options, fcurves):
 320     # main vars
 321     mode = options[0]
 322
 323     #get indices of selected fcurves
 324     fcurve_sel = selectedfcurves(obj)
 325
 326     # go through fcurves
 327     for fcurve_i, fcurve in enumerate(fcurves):
 328         # test if fcurve is long enough
 329         if len(fcurve) >= 7:
 330
 331             # simplify spline according to mode
 332             if mode == 'distance':
 333                 newVerts = simplify_RDP(fcurve, options)
 334
 335             if mode == 'curvature':
 336                 newVerts = simplypoly(fcurve, options)
 337
 338             # convert indices into vectors3D
 339             newPoints = []
 340
 341             #this is different from the main() function for normal curves, different api...
 342             for v in newVerts:
 343                 newPoints.append(fcurve[v])
 344
 345             #remove all points from curve first
 346             for i in range(len(fcurve)-1,0,-1):
 347                 fcurve_sel[fcurve_i].keyframe_points.remove(fcurve_sel[fcurve_i].keyframe_points[i])
 348             # put newPoints into fcurve
 349             for v in newPoints:
 350                 fcurve_sel[fcurve_i].keyframe_points.insert(frame=v[0],value=v[1])
 351             #fcurve.points.foreach_set('co', newPoints)
 352     return
 353
 354 #################################################
 355 #### ANIMATION CURVES OPERATOR ##################
 356 #################################################
 357 class GRAPH_OT_simplify(bpy.types.Operator):
 358     """"""
 359     bl_idname = "graph.simplify"
 360     bl_label = "simplifiy f-curves"
 361     bl_description = "simplify selected f-curves"
 362     bl_options = {'REGISTER', 'UNDO'}
 363
 364     ## Properties
 365     opModes = [
 366             ('distance', 'distance', 'distance'),
 367             ('curvature', 'curvature', 'curvature')]
 368     mode = EnumProperty(name="Mode",
 369                             description="choose algorithm to use",
 370                             items=opModes)
 371     k_thresh = FloatProperty(name="k",
 372                             min=0, soft_min=0,
 373                             default=0, precision=3,
 374                             description="threshold")
 375     pointsNr = IntProperty(name="n",
 376                             min=5, soft_min=5,
 377                             max=16, soft_max=9,
 378                             default=5,
 379                             description="degree of curve to get averaged curvatures")
 380     error = FloatProperty(name="error",
 381                             description="maximum error to allow - distance",
 382                             min=0.0, soft_min=0.0,
 383                             default=0, precision=3)
 384     degreeOut = IntProperty(name="degree",
 385                             min=3, soft_min=3,
 386                             max=7, soft_max=7,
 387                             default=5,
 388                             description="degree of new curve")
 389     dis_error = FloatProperty(name="distance error",
 390                             description="maximum error in Blenderunits to allow - distance",
 391                             min=0, soft_min=0,
 392                             default=0.0, precision=3)
 393     fcurves = []
 394
 395     '''  Remove curvature mode as long as it isnn't significantly improved
 396
 397     def draw(self, context):
 398         layout = self.layout
 399         col = layout.column()
 400         col.label('Mode:')
 401         col.prop(self, 'mode', expand=True)
 402         if self.mode == 'distance':
 403             box = layout.box()
 404             box.label(self.mode, icon='ARROW_LEFTRIGHT')
 405             box.prop(self, 'error', expand=True)
 406         if self.mode == 'curvature':
 407             box = layout.box()
 408             box.label('degree', icon='SMOOTHCURVE')
 409             box.prop(self, 'pointsNr', expand=True)
 410             box.label('threshold', icon='PARTICLE_PATH')
 411             box.prop(self, 'k_thresh', expand=True)
 412             box.label('distance', icon='ARROW_LEFTRIGHT')
 413             box.prop(self, 'dis_error', expand=True)
 414         col = layout.column()
 415     '''
 416
 417     def draw(self, context):
 418         layout = self.layout
 419         col = layout.column()
 420         col.prop(self, 'error', expand=True)
 421
 422     ## Check for animdata
 423     @classmethod
 424     def poll(cls, context):
 425         obj = context.active_object
 426         fcurves = False
 427         if obj:
 428             animdata = obj.animation_data
 429             if animdata:
 430                 act = animdata.action
 431                 if act:
 432                     fcurves = act.fcurves
 433         return (obj and fcurves)
 434
 435     ## execute
 436     def execute(self, context):
 437         #print("------START------")
 438
 439         options = [
 440                 self.mode,       #0
 441                 self.mode,       #1
 442                 self.k_thresh,   #2
 443                 self.pointsNr,   #3
 444                 self.error,      #4
 445                 self.degreeOut,  #6
 446                 self.dis_error]  #7
 447
 448         obj = context.active_object
 449
 450         if not self.fcurves:
 451             self.fcurves = getFcurveData(obj)
 452
 453         fcurves_simplify(context, obj, options, self.fcurves)
 454
 455         #print("-------END-------")
 456         return {'FINISHED'}
 457
 458 ###########################
 459 ##### Curves OPERATOR #####
 460 ###########################
 461 class CURVE_OT_simplify(bpy.types.Operator):
 462     """"""
 463     bl_idname = "curve.simplify"
 464     bl_label = "simplifiy curves"
 465     bl_description = "simplify curves"
 466     bl_options = {'REGISTER', 'UNDO'}
 467
 468     ## Properties
 469     opModes = [
 470             ('distance', 'distance', 'distance'),
 471             ('curvature', 'curvature', 'curvature')]
 472     mode = EnumProperty(name="Mode",
 473                             description="choose algorithm to use",
 474                             items=opModes)
 475     SplineTypes = [
 476                 ('INPUT', 'Input', 'same type as input spline'),
 477                 ('NURBS', 'Nurbs', 'NURBS'),
 478                 ('BEZIER', 'Bezier', 'BEZIER'),
 479                 ('POLY', 'Poly', 'POLY')]
 480     output = EnumProperty(name="Output splines",
 481                             description="Type of splines to output",
 482                             items=SplineTypes)
 483     k_thresh = FloatProperty(name="k",
 484                             min=0, soft_min=0,
 485                             default=0, precision=3,
 486                             description="threshold")
 487     pointsNr = IntProperty(name="n",
 488                             min=5, soft_min=5,
 489                             max=9, soft_max=9,
 490                             default=5,
 491                             description="degree of curve to get averaged curvatures")
 492     error = FloatProperty(name="error in Bu",
 493                             description="maximum error in Blenderunits to allow - distance",
 494                             min=0, soft_min=0,
 495                             default=0.0, precision=3)
 496     degreeOut = IntProperty(name="degree",
 497                             min=3, soft_min=3,
 498                             max=7, soft_max=7,
 499                             default=5,
 500                             description="degree of new curve")
 501     dis_error = FloatProperty(name="distance error",
 502                             description="maximum error in Blenderunits to allow - distance",
 503                             min=0, soft_min=0,
 504                             default=0.0)
 505     keepShort = BoolProperty(name="keep short Splines",
 506                             description="keep short splines (less then 7 points)",
 507                             default=True)
 508
 509     '''  Remove curvature mode as long as it isnn't significantly improved
 510
 511     def draw(self, context):
 512         layout = self.layout
 513         col = layout.column()
 514         col.label('Mode:')
 515         col.prop(self, 'mode', expand=True)
 516         if self.mode == 'distance':
 517             box = layout.box()
 518             box.label(self.mode, icon='ARROW_LEFTRIGHT')
 519             box.prop(self, 'error', expand=True)
 520         if self.mode == 'curvature':
 521             box = layout.box()
 522             box.label('degree', icon='SMOOTHCURVE')
 523             box.prop(self, 'pointsNr', expand=True)
 524             box.label('threshold', icon='PARTICLE_PATH')
 525             box.prop(self, 'k_thresh', expand=True)
 526             box.label('distance', icon='ARROW_LEFTRIGHT')
 527             box.prop(self, 'dis_error', expand=True)
 528         col = layout.column()
 529         col.separator()
 530         col.prop(self, 'output', text='Output', icon='OUTLINER_OB_CURVE')
 531         if self.output == 'NURBS':
 532             col.prop(self, 'degreeOut', expand=True)
 533         col.prop(self, 'keepShort', expand=True)
 534     '''
 535
 536     def draw(self, context):
 537         layout = self.layout
 538         col = layout.column()
 539         col.prop(self, 'error', expand=True)
 540         col.prop(self, 'output', text='Output', icon='OUTLINER_OB_CURVE')
 541         if self.output == 'NURBS':
 542             col.prop(self, 'degreeOut', expand=True)
 543         col.prop(self, 'keepShort', expand=True)
 544
 545
 546     ## Check for curve
 547     @classmethod
 548     def poll(cls, context):
 549         obj = context.active_object
 550         return (obj and obj.type == 'CURVE')
 551
 552     ## execute
 553     def execute(self, context):
 554         #print("------START------")
 555
 556         options = [
 557                 self.mode,       #0
 558                 self.output,     #1
 559                 self.k_thresh,   #2
 560                 self.pointsNr,   #3
 561                 self.error,      #4
 562                 self.degreeOut,  #5
 563                 self.dis_error,  #6
 564                 self.keepShort]  #7
 565
 566
 567         bpy.context.user_preferences.edit.use_global_undo = False
 568
 569         bpy.ops.object.mode_set(mode='OBJECT', toggle=True)
 570         obj = context.active_object
 571
 572         main(context, obj, options)
 573
 574         bpy.context.user_preferences.edit.use_global_undo = True
 575
 576         #print("-------END-------")
 577         return {'FINISHED'}
 578
 579 #################################################
 580 #### REGISTER ###################################
 581 #################################################
 582 def register():
 583     bpy.utils.register_module(__name__)
 584
 585     pass
 586
 587 def unregister():
 588     bpy.utils.unregister_module(__name__)
 589
 590     pass
 591
 592 if __name__ == "__main__":
 593     register()