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