Export_3ds: Added distance cue chunk export
[blender-addons.git] / curve_simplify.py
blob386fc57bdc3ff39b80f3b6e4f8e434858ebb1fc2
1 # SPDX-FileCopyrightText: 2010-2022 Blender Foundation
3 # SPDX-License-Identifier: GPL-2.0-or-later
5 bl_info = {
6 "name": "Simplify Curves+",
7 "author": "testscreenings, Michael Soluyanov",
8 "version": (1, 1, 2),
9 "blender": (2, 80, 0),
10 "location": "3D View, Dopesheet & Graph Editors",
11 "description": "Simplify Curves: 3dview, Dopesheet, Graph. Distance Merge: 3d view curve edit",
12 "warning": "",
13 "doc_url": "{BLENDER_MANUAL_URL}/addons/add_curve/simplify_curves.html",
14 "category": "Add Curve",
17 """
18 This script simplifies Curve objects and animation F-Curves
19 This script will also Merge by Distance 3d view curves in edit mode
20 """
22 import bpy
23 from bpy.props import (
24 BoolProperty,
25 EnumProperty,
26 FloatProperty,
27 IntProperty,
29 import mathutils
30 from math import (
31 sin,
32 pow,
34 from bpy.types import Operator
37 def error_handlers(self, op_name, errors, reports="ERROR"):
38 if self and reports:
39 self.report({'INFO'},
40 reports + ": some operations could not be performed "
41 "(See Console for more info)")
43 print("\n[Simplify Curves]\nOperator: {}\nErrors: {}\n".format(op_name, errors))
46 # Check for curve
48 # ### simplipoly algorithm ###
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
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)
72 # average the curvatures
73 for i in range(len(points)):
74 avgCurva = sum(pointCurva[i]) / (order - 1)
75 curvatures.append(avgCurva)
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
85 # generate list of vert indices 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 or distances[i] >= dis_error * 0.1):
90 newVerts.append(i)
91 newVerts.append(len(curvatures) - 1) # last vert is always kept
93 return newVerts
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]
109 # get nth derivative of order(len(verts)) bezier curve
110 def getDerivative(verts, t, nth):
111 order = len(verts) - 1 - nth
112 QVerts = []
114 if nth:
115 for i in range(nth):
116 if QVerts:
117 verts = QVerts
118 derivVerts = []
119 for i in range(len(verts) - 1):
120 derivVerts.append(verts[i + 1] - verts[i])
121 QVerts = derivVerts
122 else:
123 QVerts = verts
125 if len(verts[0]) == 3:
126 point = Vector((0, 0, 0))
127 if len(verts[0]) == 2:
128 point = Vector((0, 0))
130 for i, vert in enumerate(QVerts):
131 point += binom(order, i) * pow(t, i) * pow(1 - t, order - i) * vert
132 deriv = point
134 return deriv
137 # get curvature from first, second derivative
138 def getCurvature(deriv1, deriv2):
139 if deriv1.length == 0: # in case of points in straight line
140 curvature = 0
141 return curvature
142 curvature = (deriv1.cross(deriv2)).length / pow(deriv1.length, 3)
143 return curvature
146 # ### Ramer-Douglas-Peucker algorithm ###
148 # get altitude of vert
149 def altitude(point1, point2, pointn):
150 edge1 = point2 - point1
151 edge2 = pointn - point1
152 if edge2.length == 0:
153 altitude = 0
154 return altitude
155 if edge1.length == 0:
156 altitude = edge2.length
157 return altitude
158 alpha = edge1.angle(edge2)
159 altitude = sin(alpha) * edge2.length
160 return altitude
163 # iterate through verts
164 def iterate(points, newVerts, error):
165 new = []
166 for newIndex in range(len(newVerts) - 1):
167 bigVert = 0
168 alti_store = 0
169 for i, point in enumerate(points[newVerts[newIndex] + 1: newVerts[newIndex + 1]]):
170 alti = altitude(points[newVerts[newIndex]], points[newVerts[newIndex + 1]], point)
171 if alti > alti_store:
172 alti_store = alti
173 if alti_store >= error:
174 bigVert = i + 1 + newVerts[newIndex]
175 if bigVert:
176 new.append(bigVert)
177 if new == []:
178 return False
179 return new
182 # get SplineVertIndices to keep
183 def simplify_RDP(splineVerts, options):
184 # main vars
185 error = options[4]
187 # set first and last vert
188 newVerts = [0, len(splineVerts) - 1]
190 # iterate through the points
191 new = 1
192 while new is not False:
193 new = iterate(splineVerts, newVerts, error)
194 if new:
195 newVerts += new
196 newVerts.sort()
197 return newVerts
200 # ### CURVE GENERATION ###
202 # set bezierhandles to auto
203 def setBezierHandles(newCurve):
204 # Faster:
205 for spline in newCurve.data.splines:
206 for p in spline.bezier_points:
207 p.handle_left_type = 'AUTO'
208 p.handle_right_type = 'AUTO'
211 # get array of new coords for new spline from vertindices
212 def vertsToPoints(newVerts, splineVerts, splineType):
213 # main vars
214 newPoints = []
216 # array for BEZIER spline output
217 if splineType == 'BEZIER':
218 for v in newVerts:
219 newPoints += splineVerts[v].to_tuple()
221 # array for nonBEZIER output
222 else:
223 for v in newVerts:
224 newPoints += (splineVerts[v].to_tuple())
225 if splineType == 'NURBS':
226 newPoints.append(1) # for nurbs w = 1
227 else: # for poly w = 0
228 newPoints.append(0)
229 return newPoints
232 # ### MAIN OPERATIONS ###
234 def main(context, obj, options, curve_dimension):
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()
243 # create curvedatablock
244 curve = bpy.data.curves.new("Simple_" + obj.name, type='CURVE')
245 curve.dimensions = curve_dimension
247 # go through splines
248 for spline_i, spline in enumerate(splines):
249 # test if spline is a long enough
250 if len(spline.points) >= 3 or keepShort:
251 # check what type of spline to create
252 if output == 'INPUT':
253 splineType = spline.type
254 else:
255 splineType = output
257 # get vec3 list to simplify
258 if spline.type == 'BEZIER': # get bezierverts
259 splineVerts = [splineVert.co.copy()
260 for splineVert in spline.bezier_points.values()]
262 else: # verts from all other types of curves
263 splineVerts = [splineVert.co.to_3d()
264 for splineVert in spline.points.values()]
266 # simplify spline according to mode
267 if mode == 'DISTANCE':
268 newVerts = simplify_RDP(splineVerts, options)
270 if mode == 'CURVATURE':
271 newVerts = simplypoly(splineVerts, options)
273 # convert indices into vectors3D
274 newPoints = vertsToPoints(newVerts, splineVerts, splineType)
276 # create new spline
277 newSpline = curve.splines.new(type=splineType)
279 # put newPoints into spline according to type
280 if splineType == 'BEZIER':
281 newSpline.bezier_points.add(int(len(newPoints) * 0.33))
282 newSpline.bezier_points.foreach_set('co', newPoints)
283 else:
284 newSpline.points.add(int(len(newPoints) * 0.25 - 1))
285 newSpline.points.foreach_set('co', newPoints)
287 # set degree of outputNurbsCurve
288 if output == 'NURBS':
289 newSpline.order_u = degreeOut
291 # splineoptions
292 newSpline.use_endpoint_u = spline.use_endpoint_u
294 # create new object and put into scene
295 newCurve = bpy.data.objects.new("Simple_" + obj.name, curve)
296 coll = context.view_layer.active_layer_collection.collection
297 coll.objects.link(newCurve)
298 newCurve.select_set(True)
300 context.view_layer.objects.active = newCurve
301 newCurve.matrix_world = obj.matrix_world
303 # set bezierhandles to auto
304 setBezierHandles(newCurve)
306 return
309 # get preoperator fcurves
310 def getFcurveData(obj):
311 fcurves = []
312 for fc in obj.animation_data.action.fcurves:
313 if fc.select:
314 fcVerts = [vcVert.co.to_3d()
315 for vcVert in fc.keyframe_points.values()]
316 fcurves.append(fcVerts)
317 return fcurves
320 def selectedfcurves(obj):
321 fcurves_sel = []
322 for i, fc in enumerate(obj.animation_data.action.fcurves):
323 if fc.select:
324 fcurves_sel.append(fc)
325 return fcurves_sel
328 # fCurves Main
329 def fcurves_simplify(context, obj, options, fcurves):
330 # main vars
331 mode = options[0]
333 # get indices of selected fcurves
334 fcurve_sel = selectedfcurves(obj)
336 # go through fcurves
337 for fcurve_i, fcurve in enumerate(fcurves):
338 # test if fcurve is long enough
339 if len(fcurve) >= 3:
340 # simplify spline according to mode
341 if mode == 'DISTANCE':
342 newVerts = simplify_RDP(fcurve, options)
344 if mode == 'CURVATURE':
345 newVerts = simplypoly(fcurve, options)
347 # convert indices into vectors3D
348 newPoints = []
350 # this is different from the main() function for normal curves, different api...
351 for v in newVerts:
352 newPoints.append(fcurve[v])
354 # remove all points from curve first
355 for i in range(len(fcurve) - 1, 0, -1):
356 fcurve_sel[fcurve_i].keyframe_points.remove(fcurve_sel[fcurve_i].keyframe_points[i])
357 # put newPoints into fcurve
358 for v in newPoints:
359 fcurve_sel[fcurve_i].keyframe_points.insert(frame=v[0], value=v[1])
360 return
363 # ### MENU append ###
365 def menu_func(self, context):
366 self.layout.operator("graph.simplify")
369 def menu(self, context):
370 self.layout.operator("curve.simplify", text="Curve Simplify", icon="CURVE_DATA")
374 # ### ANIMATION CURVES OPERATOR ###
376 class GRAPH_OT_simplify(Operator):
377 bl_idname = "graph.simplify"
378 bl_label = "Simplify F-Curves"
379 bl_description = ("Simplify selected Curves\n"
380 "Does not operate on short Splines (less than 3 points)")
381 bl_options = {'REGISTER', 'UNDO'}
383 # Properties
384 opModes = [
385 ('DISTANCE', 'Distance', 'Distance-based simplification (Poly)'),
386 ('CURVATURE', 'Curvature', 'Curvature-based simplification (RDP)')]
387 mode: EnumProperty(
388 name="Mode",
389 description="Choose algorithm to use",
390 items=opModes
392 k_thresh: FloatProperty(
393 name="k",
394 min=0, soft_min=0,
395 default=0, precision=5,
396 description="Threshold"
398 pointsNr: IntProperty(
399 name="n",
400 min=5, soft_min=5,
401 max=16, soft_max=9,
402 default=5,
403 description="Degree of curve to get averaged curvatures"
405 error: FloatProperty(
406 name="Error",
407 description="Maximum allowed distance error",
408 min=0.0, soft_min=0.0,
409 default=0, precision=5,
410 step = 0.1
412 degreeOut: IntProperty(
413 name="Degree",
414 min=3, soft_min=3,
415 max=7, soft_max=7,
416 default=5,
417 description="Degree of new curve"
419 dis_error: FloatProperty(
420 name="Distance error",
421 description="Maximum allowed distance error in Blender Units",
422 min=0, soft_min=0,
423 default=0.0, precision=5
425 fcurves = []
427 def draw(self, context):
428 layout = self.layout
429 col = layout.column()
431 col.label(text="Distance Error:")
432 col.prop(self, "error", expand=True)
434 @classmethod
435 def poll(cls, context):
436 # Check for animdata
437 obj = context.active_object
438 fcurves = False
439 if obj:
440 animdata = obj.animation_data
441 if animdata:
442 act = animdata.action
443 if act:
444 fcurves = act.fcurves
445 return (obj and fcurves)
447 def execute(self, context):
448 options = [
449 self.mode, # 0
450 self.mode, # 1
451 self.k_thresh, # 2
452 self.pointsNr, # 3
453 self.error, # 4
454 self.degreeOut, # 6
455 self.dis_error # 7
458 obj = context.active_object
460 if not self.fcurves:
461 self.fcurves = getFcurveData(obj)
463 fcurves_simplify(context, obj, options, self.fcurves)
465 return {'FINISHED'}
468 # ### Curves OPERATOR ###
469 class CURVE_OT_simplify(Operator):
470 bl_idname = "curve.simplify"
471 bl_label = "Simplify Curves"
472 bl_description = ("Simplify the existing Curve based upon the chosen settings\n"
473 "Notes: Needs an existing Curve object,\n"
474 "Outputs a new Curve with the Simple prefix in the name")
475 bl_options = {'REGISTER', 'UNDO'}
477 # Properties
478 opModes = [
479 ('DISTANCE', 'Distance', 'Distance-based simplification (Poly)'),
480 ('CURVATURE', 'Curvature', 'Curvature-based simplification (RDP)')
482 mode: EnumProperty(
483 name="Mode",
484 description="Choose algorithm to use",
485 items=opModes
487 SplineTypes = [
488 ('INPUT', 'Input', 'Same type as input spline'),
489 ('NURBS', 'Nurbs', 'NURBS'),
490 ('BEZIER', 'Bezier', 'BEZIER'),
491 ('POLY', 'Poly', 'POLY')
493 output: EnumProperty(
494 name="Output splines",
495 description="Type of splines to output",
496 items=SplineTypes
498 k_thresh: FloatProperty(
499 name="k",
500 min=0, soft_min=0,
501 default=0, precision=5,
502 description="Threshold"
504 pointsNr: IntProperty(
505 name="n",
506 min=5, soft_min=5,
507 max=9, soft_max=9,
508 default=5,
509 description="Degree of curve to get averaged curvatures"
511 error: FloatProperty(
512 name="Error",
513 description="Maximum allowed distance error in Blender Units",
514 min=0, soft_min=0,
515 default=0.0, precision=5,
516 step = 0.1
518 degreeOut: IntProperty(
519 name="Degree",
520 min=3, soft_min=3,
521 max=7, soft_max=7,
522 default=5,
523 description="Degree of new curve"
525 dis_error: FloatProperty(
526 name="Distance error",
527 description="Maximum allowed distance error in Blender Units",
528 min=0, soft_min=0,
529 default=0.0
531 keepShort: BoolProperty(
532 name="Keep short splines",
533 description="Keep short splines (less than 3 points)",
534 default=True
537 def draw(self, context):
538 layout = self.layout
539 col = layout.column()
541 col.label(text="Distance Error:")
542 col.prop(self, "error", expand=True)
543 col.prop(self, "output", text="Output", icon="OUTLINER_OB_CURVE")
544 if self.output == "NURBS":
545 col.prop(self, "degreeOut", expand=True)
546 col.separator()
547 col.prop(self, "keepShort", expand=True)
549 @classmethod
550 def poll(cls, context):
551 obj = context.active_object
552 return (obj and obj.type == 'CURVE')
554 def execute(self, context):
555 options = [
556 self.mode, # 0
557 self.output, # 1
558 self.k_thresh, # 2
559 self.pointsNr, # 3
560 self.error, # 4
561 self.degreeOut, # 5
562 self.dis_error, # 6
563 self.keepShort # 7
565 try:
566 bpy.ops.object.mode_set(mode='OBJECT')
567 obj = context.active_object
568 curve_dimension = obj.data.dimensions
570 main(context, obj, options, curve_dimension)
571 except Exception as e:
572 error_handlers(self, "curve.simplify", e, "Simplify Curves")
573 return {'CANCELLED'}
575 return {'FINISHED'}
577 ## Initial use Curve Remove Doubles ##
579 def main_rd(context, distance = 0.01):
581 selected_Curves = context.selected_objects
582 if bpy.ops.object.mode_set.poll():
583 bpy.ops.object.mode_set(mode='EDIT')
585 bezier_dellist = []
586 dellist = []
588 for curve in selected_Curves:
589 for spline in curve.data.splines:
590 if spline.type == 'BEZIER':
591 if len(spline.bezier_points) > 1:
592 for i in range(0, len(spline.bezier_points)):
594 if i == 0:
595 ii = len(spline.bezier_points) - 1
596 else:
597 ii = i - 1
599 dot = spline.bezier_points[i];
600 dot1 = spline.bezier_points[ii];
602 while dot1 in bezier_dellist and i != ii:
603 ii -= 1
604 if ii < 0:
605 ii = len(spline.bezier_points)-1
606 dot1 = spline.bezier_points[ii]
608 if dot.select_control_point and dot1.select_control_point and (i!=0 or spline.use_cyclic_u):
610 if (dot.co-dot1.co).length < distance:
611 # remove points and recreate hangles
612 dot1.handle_right_type = "FREE"
613 dot1.handle_right = dot.handle_right
614 dot1.co = (dot.co + dot1.co) / 2
615 bezier_dellist.append(dot)
617 else:
618 # Handles that are on main point position converts to vector,
619 # if next handle are also vector
620 if dot.handle_left_type == 'VECTOR' and (dot1.handle_right - dot1.co).length < distance:
621 dot1.handle_right_type = "VECTOR"
622 if dot1.handle_right_type == 'VECTOR' and (dot.handle_left - dot.co).length < distance:
623 dot.handle_left_type = "VECTOR"
624 else:
625 if len(spline.points) > 1:
626 for i in range(0, len(spline.points)):
628 if i == 0:
629 ii = len(spline.points) - 1
630 else:
631 ii = i - 1
633 dot = spline.points[i];
634 dot1 = spline.points[ii];
636 while dot1 in dellist and i != ii:
637 ii -= 1
638 if ii < 0:
639 ii = len(spline.points)-1
640 dot1 = spline.points[ii]
642 if dot.select and dot1.select and (i!=0 or spline.use_cyclic_u):
644 if (dot.co-dot1.co).length < distance:
645 dot1.co = (dot.co + dot1.co) / 2
646 dellist.append(dot)
648 bpy.ops.curve.select_all(action = 'DESELECT')
650 for dot in bezier_dellist:
651 dot.select_control_point = True
653 for dot in dellist:
654 dot.select = True
656 bezier_count = len(bezier_dellist)
657 count = len(dellist)
659 bpy.ops.curve.delete(type = 'VERT')
661 bpy.ops.curve.select_all(action = 'DESELECT')
663 return bezier_count + count
667 class Curve_OT_CurveRemvDbs(bpy.types.Operator):
668 """Merge consecutive points that are near to each other"""
669 bl_idname = 'curve.remove_double'
670 bl_label = 'Merge By Distance'
671 bl_options = {'REGISTER', 'UNDO'}
673 distance: bpy.props.FloatProperty(name = 'Distance', default = 0.01, soft_min = 0.001, step = 0.1)
675 @classmethod
676 def poll(cls, context):
677 obj = context.active_object
678 return (obj and obj.type == 'CURVE')
680 def execute(self, context):
681 removed=main_rd(context, self.distance)
682 self.report({'INFO'}, "Removed %d bezier points" % removed)
683 return {'FINISHED'}
685 def menu_func_rd(self, context):
686 self.layout.operator(Curve_OT_CurveRemvDbs.bl_idname, text='Merge By Distance')
688 # Register
689 classes = [
690 GRAPH_OT_simplify,
691 CURVE_OT_simplify,
692 Curve_OT_CurveRemvDbs,
696 def register():
697 from bpy.utils import register_class
698 for cls in classes:
699 register_class(cls)
701 #bpy.types.GRAPH_MT_channel.append(menu_func)
702 #bpy.types.DOPESHEET_MT_channel.append(menu_func)
703 bpy.types.VIEW3D_MT_curve_add.append(menu)
704 bpy.types.VIEW3D_MT_edit_curve_context_menu.prepend(menu)
705 bpy.types.VIEW3D_MT_edit_curve_context_menu.prepend(menu_func_rd)
708 def unregister():
709 from bpy.utils import unregister_class
710 for cls in reversed(classes):
711 unregister_class(cls)
713 #bpy.types.GRAPH_MT_channel.remove(menu_func)
714 #bpy.types.DOPESHEET_MT_channel.remove(menu_func)
715 bpy.types.VIEW3D_MT_curve_add.remove(menu)
716 bpy.types.VIEW3D_MT_edit_curve_context_menu.remove(menu)
717 bpy.types.VIEW3D_MT_edit_curve_context_menu.remove(menu_func_rd)
719 if __name__ == "__main__":
720 register()