curve_tools/internal.py

   1 #  ***** GPL LICENSE BLOCK *****
   2 #
   3 #  This program is free software: you can redistribute it and/or modify
   4 #  it under the terms of the GNU General Public License as published by
   5 #  the Free Software Foundation, either version 3 of the License, or
   6 #  (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, see <http://www.gnu.org/licenses/>.
  15 #  All rights reserved.
  16 #
  17 #  ***** GPL LICENSE BLOCK *****
  18
  19 import bpy, math, cmath
  20 from mathutils import Vector, Matrix
  21 from collections import namedtuple
  22
  23 units = [
  24     ('-', 'None', '1.0', 0),
  25     ('px', 'Pixel', '1.0', 1),
  26     ('m', 'Meter', '1.0', 2),
  27     ('dm', 'Decimeter', '0.1', 3),
  28     ('cm', 'Centimeter', '0.01', 4),
  29     ('mm', 'Millimeter', '0.001', 5),
  30     ('yd', 'Yard', '0.9144', 6),
  31     ('ft', 'Foot', '0.3048', 7),
  32     ('in', 'Inch', '0.0254', 8)
  33 ]
  34
  35 param_tollerance = 0.0001
  36 AABB = namedtuple('AxisAlignedBoundingBox', 'center dimensions')
  37 Plane = namedtuple('Plane', 'normal distance')
  38 Circle = namedtuple('Circle', 'orientation center radius')
  39
  40 def circleOfTriangle(a, b, c):
  41     # https://en.wikipedia.org/wiki/Circumscribed_circle#Cartesian_coordinates_from_cross-_and_dot-products
  42     dirBA = a-b
  43     dirCB = b-c
  44     dirAC = c-a
  45     normal = dirBA.cross(dirCB)
  46     lengthBA = dirBA.length
  47     lengthCB = dirCB.length
  48     lengthAC = dirAC.length
  49     lengthN = normal.length
  50     if lengthN == 0:
  51         return None
  52     factor = -1/(2*lengthN*lengthN)
  53     alpha = (dirBA@dirAC)*(lengthCB*lengthCB*factor)
  54     beta = (dirBA@dirCB)*(lengthAC*lengthAC*factor)
  55     gamma = (dirAC@dirCB)*(lengthBA*lengthBA*factor)
  56     center = a*alpha+b*beta+c*gamma
  57     radius = (lengthBA*lengthCB*lengthAC)/(2*lengthN)
  58     tangent = (a-center).normalized()
  59     orientation = Matrix.Identity(3)
  60     orientation.col[2] = normal/lengthN
  61     orientation.col[1] = (a-center).normalized()
  62     orientation.col[0] = orientation.col[1].xyz.cross(orientation.col[2].xyz)
  63     return Circle(orientation=orientation, center=center, radius=radius)
  64
  65 def circleOfBezier(points, tollerance=0.000001, samples=16):
  66     circle = circleOfTriangle(points[0], bezierPointAt(points, 0.5), points[3])
  67     if circle == None:
  68         return None
  69     variance = 0
  70     for t in range(0, samples):
  71         variance += ((circle.center-bezierPointAt(points, (t+1)/(samples-1))).length/circle.radius-1) ** 2
  72     variance /= samples
  73     return None if variance > tollerance else circle
  74
  75 def areaOfPolygon(vertices):
  76     area = 0
  77     for index, current in enumerate(vertices):
  78         prev = vertices[index-1]
  79         area += (current[0]+prev[0])*(current[1]-prev[1])
  80     return area*0.5
  81
  82 def linePointDistance(begin, dir, point):
  83     return (point-begin).cross(dir.normalized()).length
  84
  85 def linePlaneIntersection(origin, dir, plane):
  86     det = dir@plane.normal
  87     return float('nan') if det == 0 else (plane.distance-origin@plane.normal)/det
  88
  89 def nearestPointOfLines(originA, dirA, originB, dirB, tollerance=0.0):
  90     # https://en.wikipedia.org/wiki/Skew_lines#Nearest_Points
  91     normal = dirA.cross(dirB)
  92     normalA = dirA.cross(normal)
  93     normalB = dirB.cross(normal)
  94     divisorA = dirA@normalB
  95     divisorB = dirB@normalA
  96     if abs(divisorA) <= tollerance or abs(divisorB) <= tollerance:
  97         return (float('nan'), float('nan'), None, None)
  98     else:
  99         paramA = (originB-originA)@normalB/divisorA
 100         paramB = (originA-originB)@normalA/divisorB
 101         return (paramA, paramB, originA+dirA*paramA, originB+dirB*paramB)
 102
 103 def lineSegmentLineSegmentIntersection(beginA, endA, beginB, endB, tollerance=0.001):
 104     dirA = endA-beginA
 105     dirB = endB-beginB
 106     paramA, paramB, pointA, pointB = nearestPointOfLines(beginA, dirA, beginB, dirB)
 107     if math.isnan(paramA) or (pointA-pointB).length > tollerance or \
 108        paramA < 0 or paramA > 1 or paramB < 0 or paramB > 1:
 109         return None
 110     return (paramA, paramB, pointA, pointB)
 111
 112 def aabbOfPoints(points):
 113     min = Vector(points[0])
 114     max = Vector(points[0])
 115     for point in points:
 116         for i in range(0, 3):
 117             if min[i] > point[i]:
 118                 min[i] = point[i]
 119             if max[i] < point[i]:
 120                 max[i] = point[i]
 121     return AABB(center=(max+min)*0.5, dimensions=(max-min)*0.5)
 122
 123 def aabbIntersectionTest(a, b, tollerance=0.0):
 124     for i in range(0, 3):
 125         if abs(a.center[i]-b.center[i]) > a.dimensions[i]+b.dimensions[i]+tollerance:
 126             return False
 127     return True
 128
 129 def isPointInAABB(point, aabb, tollerance=0.0, ignore_axis=None):
 130     for i in range(0, 3):
 131         if i != ignore_axis and (point[i] < aabb.center[i]-aabb.dimensions[i]-tollerance or point[i] > aabb.center[i]+aabb.dimensions[i]+tollerance):
 132             return False
 133     return True
 134
 135 def lineAABBIntersection(lineBegin, lineEnd, aabb):
 136     intersections = []
 137     for i in range(0, 3):
 138         normal = [0, 0, 0]
 139         normal = Vector(normal[0:i] + [1] + normal[i+1:])
 140         for j in range(-1, 2, 2):
 141             plane = Plane(normal=normal, distance=aabb.center[i]+j*aabb.dimensions[i])
 142             param = linePlaneIntersection(lineBegin, lineEnd-lineBegin, plane)
 143             if param < 0 or param > 1 or math.isnan(param):
 144                 continue
 145             point = lineBegin+param*(lineEnd-lineBegin)
 146             if isPointInAABB(point, aabb, 0.0, i):
 147                 intersections.append((param, point))
 148     return intersections
 149
 150 def bezierPointAt(points, t):
 151     s = 1-t
 152     return s*s*s*points[0] + 3*s*s*t*points[1] + 3*s*t*t*points[2] + t*t*t*points[3]
 153
 154 def bezierTangentAt(points, t):
 155     s = 1-t
 156     return s*s*(points[1]-points[0])+2*s*t*(points[2]-points[1])+t*t*(points[3]-points[2])
 157     # return s*s*points[0] + (s*s-2*s*t)*points[1] + (2*s*t-t*t)*points[2] + t*t*points[3]
 158
 159 def bezierLength(points, beginT=0, endT=1, samples=1024):
 160     # https://en.wikipedia.org/wiki/Arc_length#Finding_arc_lengths_by_integrating
 161     vec = [points[1]-points[0], points[2]-points[1], points[3]-points[2]]
 162     dot = [vec[0]@vec[0], vec[0]@vec[1], vec[0]@vec[2], vec[1]@vec[1], vec[1]@vec[2], vec[2]@vec[2]]
 163     factors = [
 164         dot[0],
 165         4*(dot[1]-dot[0]),
 166         6*dot[0]+4*dot[3]+2*dot[2]-12*dot[1],
 167         12*dot[1]+4*(dot[4]-dot[0]-dot[2])-8*dot[3],
 168         dot[0]+dot[5]+2*dot[2]+4*(dot[3]-dot[1]-dot[4])
 169     ]
 170     # https://en.wikipedia.org/wiki/Trapezoidal_rule
 171     length = 0
 172     prev_value = math.sqrt(factors[4]+factors[3]+factors[2]+factors[1]+factors[0])
 173     for index in range(0, samples+1):
 174         t = beginT+(endT-beginT)*index/samples
 175         # value = math.sqrt(factors[4]*(t**4)+factors[3]*(t**3)+factors[2]*(t**2)+factors[1]*t+factors[0])
 176         value = math.sqrt((((factors[4]*t+factors[3])*t+factors[2])*t+factors[1])*t+factors[0])
 177         length += (prev_value+value)*0.5
 178         prev_value = value
 179     return length*3/samples
 180
 181 # https://en.wikipedia.org/wiki/Root_of_unity
 182 # cubic_roots_of_unity = [cmath.rect(1, i/3*2*math.pi) for i in range(0, 3)]
 183 cubic_roots_of_unity = [complex(1, 0), complex(-1, math.sqrt(3))*0.5, complex(-1, -math.sqrt(3))*0.5]
 184 def bezierRoots(dists, tollerance=0.0001):
 185     # https://en.wikipedia.org/wiki/Cubic_function
 186     # y(t) = a*t^3 +b*t^2 +c*t^1 +d*t^0
 187     a = 3*(dists[1]-dists[2])+dists[3]-dists[0]
 188     b = 3*(dists[0]-2*dists[1]+dists[2])
 189     c = 3*(dists[1]-dists[0])
 190     d = dists[0]
 191     if abs(a) > tollerance: # Cubic
 192         E2 = a*c
 193         E3 = a*a*d
 194         A = (2*b*b-9*E2)*b+27*E3
 195         B = b*b-3*E2
 196         C = ((A+cmath.sqrt(A*A-4*B*B*B))*0.5) ** (1/3)
 197         roots = []
 198         for root in cubic_roots_of_unity:
 199             root *= C
 200             root = -1/(3*a)*(b+root+B/root)
 201             if abs(root.imag) < tollerance and root.real > -param_tollerance and root.real < 1.0+param_tollerance:
 202                 roots.append(max(0.0, min(root.real, 1.0)))
 203         # Remove doubles
 204         roots.sort()
 205         for index in range(len(roots)-1, 0, -1):
 206             if abs(roots[index-1]-roots[index]) < param_tollerance:
 207                 roots.pop(index)
 208         return roots
 209     elif abs(b) > tollerance: # Quadratic
 210         disc = c*c-4*b*d
 211         if disc < 0:
 212             return []
 213         disc = math.sqrt(disc)
 214         return [(-c-disc)/(2*b), (-c+disc)/(2*b)]
 215     elif abs(c) > tollerance: # Linear
 216         root = -d/c
 217         return [root] if root >= 0.0 and root <= 1.0 else []
 218     else: # Constant / Parallel
 219         return [] if abs(d) > tollerance else float('inf')
 220
 221 def xRaySplineIntersectionTest(spline, origin):
 222     spline_points = spline.bezier_points if spline.type == 'BEZIER' else spline.points
 223     cyclic_parallel_fix_flag = False
 224     intersections = []
 225
 226     def areIntersectionsAdjacent(index):
 227         if len(intersections) < 2:
 228             return
 229         prev = intersections[index-1]
 230         current = intersections[index]
 231         if prev[1] == current[0] and \
 232            prev[2] > 1.0-param_tollerance and current[2] < param_tollerance and \
 233            ((prev[3] < 0 and current[3] < 0) or (prev[3] > 0 and current[3] > 0)):
 234             intersections.pop(index)
 235
 236     def appendIntersection(index, root, tangentY, intersectionX):
 237         beginPoint = spline_points[index-1]
 238         endPoint = spline_points[index]
 239         if root == float('inf'): # Segment is parallel to ray
 240             if index == 0 and spline.use_cyclic_u:
 241                 cyclic_parallel_fix_flag = True
 242             if len(intersections) > 0 and intersections[-1][1] == beginPoint:
 243                 intersections[-1][1] = endPoint # Skip in adjacency test
 244         elif intersectionX >= origin[0]:
 245             intersections.append([beginPoint, endPoint, root, tangentY, intersectionX])
 246             areIntersectionsAdjacent(len(intersections)-1)
 247
 248     if spline.type == 'BEZIER':
 249         for index, endPoint in enumerate(spline.bezier_points):
 250             if index == 0 and not spline.use_cyclic_u:
 251                 continue
 252             beginPoint = spline_points[index-1]
 253             points = (beginPoint.co, beginPoint.handle_right, endPoint.handle_left, endPoint.co)
 254             roots = bezierRoots((points[0][1]-origin[1], points[1][1]-origin[1], points[2][1]-origin[1], points[3][1]-origin[1]))
 255             if roots == float('inf'): # Intersection
 256                 appendIntersection(index, float('inf'), None, None)
 257             else:
 258                 for root in roots:
 259                     appendIntersection(index, root, bezierTangentAt(points, root)[1], bezierPointAt(points, root)[0])
 260     elif spline.type == 'POLY':
 261         for index, endPoint in enumerate(spline.points):
 262             if index == 0 and not spline.use_cyclic_u:
 263                 continue
 264             beginPoint = spline_points[index-1]
 265             points = (beginPoint.co, endPoint.co)
 266             if (points[0][0] < origin[0] and points[1][0] < origin[0]) or \
 267                (points[0][1] < origin[1] and points[1][1] < origin[1]) or \
 268                (points[0][1] > origin[1] and points[1][1] > origin[1]):
 269                 continue
 270             diff = points[1]-points[0]
 271             height = origin[1]-points[0][1]
 272             if diff[1] == 0: # Parallel
 273                 if height == 0: # Intersection
 274                     appendIntersection(index, float('inf'), None, None)
 275             else: # Not parallel
 276                 root = height/diff[1]
 277                 appendIntersection(index, root, diff[1], points[0][0]+diff[0]*root)
 278
 279     if cyclic_parallel_fix_flag:
 280         appendIntersection(0, float('inf'), None, None)
 281     areIntersectionsAdjacent(0)
 282     return intersections
 283
 284 def isPointInSpline(point, spline):
 285     return spline.use_cyclic_u and len(xRaySplineIntersectionTest(spline, point))%2 == 1
 286
 287 def isSegmentLinear(points, tollerance=0.0001):
 288     return 1.0-(points[1]-points[0]).normalized()@(points[3]-points[2]).normalized() < tollerance
 289
 290 def bezierSegmentPoints(begin, end):
 291     return [begin.co, begin.handle_right, end.handle_left, end.co]
 292
 293 def grab_cursor(context, event):
 294     if event.mouse_region_x < 0:
 295         context.window.cursor_warp(context.region.x+context.region.width, event.mouse_y)
 296     elif event.mouse_region_x > context.region.width:
 297         context.window.cursor_warp(context.region.x, event.mouse_y)
 298     elif event.mouse_region_y < 0:
 299         context.window.cursor_warp(event.mouse_x, context.region.y+context.region.height)
 300     elif event.mouse_region_y > context.region.height:
 301         context.window.cursor_warp(event.mouse_x, context.region.y)
 302
 303 def deleteFromArray(item, array):
 304     for index, current in enumerate(array):
 305         if current is item:
 306             array.pop(index)
 307             break
 308
 309 def copyAttributes(dst, src):
 310     for attribute in dir(src):
 311         try:
 312             setattr(dst, attribute, getattr(src, attribute))
 313         except:
 314             pass
 315
 316 def bezierSliceFromTo(points, minParam, maxParam):
 317     fromP = bezierPointAt(points, minParam)
 318     fromT = bezierTangentAt(points, minParam)
 319     toP = bezierPointAt(points, maxParam)
 320     toT = bezierTangentAt(points, maxParam)
 321     paramDiff = maxParam-minParam
 322     return [fromP, fromP+fromT*paramDiff, toP-toT*paramDiff, toP]
 323
 324 def bezierIntersectionBroadPhase(solutions, pointsA, pointsB, aMin=0.0, aMax=1.0, bMin=0.0, bMax=1.0, depth=8, tollerance=0.001):
 325     if aabbIntersectionTest(aabbOfPoints(bezierSliceFromTo(pointsA, aMin, aMax)), aabbOfPoints(bezierSliceFromTo(pointsB, bMin, bMax)), tollerance) == False:
 326         return
 327     if depth == 0:
 328         solutions.append([aMin, aMax, bMin, bMax])
 329         return
 330     depth -= 1
 331     aMid = (aMin+aMax)*0.5
 332     bMid = (bMin+bMax)*0.5
 333     bezierIntersectionBroadPhase(solutions, pointsA, pointsB, aMin, aMid, bMin, bMid, depth, tollerance)
 334     bezierIntersectionBroadPhase(solutions, pointsA, pointsB, aMin, aMid, bMid, bMax, depth, tollerance)
 335     bezierIntersectionBroadPhase(solutions, pointsA, pointsB, aMid, aMax, bMin, bMid, depth, tollerance)
 336     bezierIntersectionBroadPhase(solutions, pointsA, pointsB, aMid, aMax, bMid, bMax, depth, tollerance)
 337
 338 def bezierIntersectionNarrowPhase(broadPhase, pointsA, pointsB, tollerance=0.000001):
 339     aMin = broadPhase[0]
 340     aMax = broadPhase[1]
 341     bMin = broadPhase[2]
 342     bMax = broadPhase[3]
 343     while (aMax-aMin > tollerance) or (bMax-bMin > tollerance):
 344         aMid = (aMin+aMax)*0.5
 345         bMid = (bMin+bMax)*0.5
 346         a1 = bezierPointAt(pointsA, (aMin+aMid)*0.5)
 347         a2 = bezierPointAt(pointsA, (aMid+aMax)*0.5)
 348         b1 = bezierPointAt(pointsB, (bMin+bMid)*0.5)
 349         b2 = bezierPointAt(pointsB, (bMid+bMax)*0.5)
 350         a1b1Dist = (a1-b1).length
 351         a2b1Dist = (a2-b1).length
 352         a1b2Dist = (a1-b2).length
 353         a2b2Dist = (a2-b2).length
 354         minDist = min(a1b1Dist, a2b1Dist, a1b2Dist, a2b2Dist)
 355         if a1b1Dist == minDist:
 356             aMax = aMid
 357             bMax = bMid
 358         elif a2b1Dist == minDist:
 359             aMin = aMid
 360             bMax = bMid
 361         elif a1b2Dist == minDist:
 362             aMax = aMid
 363             bMin = bMid
 364         else:
 365             aMin = aMid
 366             bMin = bMid
 367     return [aMin, bMin, minDist]
 368
 369 def segmentIntersection(segmentA, segmentB, tollerance=0.001):
 370     pointsA = bezierSegmentPoints(segmentA['beginPoint'], segmentA['endPoint'])
 371     pointsB = bezierSegmentPoints(segmentB['beginPoint'], segmentB['endPoint'])
 372     result = []
 373     def addCut(paramA, paramB):
 374         cutA = {'param': paramA, 'segment': segmentA}
 375         cutB = {'param': paramB, 'segment': segmentB}
 376         cutA['otherCut'] = cutB
 377         cutB['otherCut'] = cutA
 378         segmentA['cuts'].append(cutA)
 379         segmentB['cuts'].append(cutB)
 380         result.append([cutA, cutB])
 381     if isSegmentLinear(pointsA) and isSegmentLinear(pointsB):
 382         intersection = lineSegmentLineSegmentIntersection(pointsA[0], pointsA[3], pointsB[0], pointsB[3])
 383         if intersection != None:
 384             addCut(intersection[0], intersection[1])
 385         return result
 386     solutions = []
 387     bezierIntersectionBroadPhase(solutions, pointsA, pointsB)
 388     for index in range(0, len(solutions)):
 389         solutions[index] = bezierIntersectionNarrowPhase(solutions[index], pointsA, pointsB)
 390     for index in range(0, len(solutions)):
 391         for otherIndex in range(0, len(solutions)):
 392             if solutions[index][2] == float('inf'):
 393                 break
 394             if index == otherIndex or solutions[otherIndex][2] == float('inf'):
 395                 continue
 396             diffA = solutions[index][0]-solutions[otherIndex][0]
 397             diffB = solutions[index][1]-solutions[otherIndex][1]
 398             if diffA*diffA+diffB*diffB < 0.01:
 399                 if solutions[index][2] < solutions[otherIndex][2]:
 400                     solutions[otherIndex][2] = float('inf')
 401                 else:
 402                     solutions[index][2] = float('inf')
 403     def areIntersectionsAdjacent(segmentA, segmentB, paramA, paramB):
 404         return segmentA['endIndex'] == segmentB['beginIndex'] and paramA > 1-param_tollerance and paramB < param_tollerance
 405     for solution in solutions:
 406         if (solution[2] > tollerance) or \
 407           (segmentA['spline'] == segmentB['spline'] and \
 408           (areIntersectionsAdjacent(segmentA, segmentB, solution[0], solution[1]) or \
 409            areIntersectionsAdjacent(segmentB, segmentA, solution[1], solution[0]))):
 410             continue
 411         addCut(solution[0], solution[1])
 412     return result
 413
 414 def bezierMultiIntersection(segments):
 415     for index in range(0, len(segments)):
 416         for otherIndex in range(index+1, len(segments)):
 417             segmentIntersection(segments[index], segments[otherIndex])
 418     prepareSegmentIntersections(segments)
 419     subdivideBezierSegments(segments)
 420
 421 def bezierProjectHandles(segments):
 422     insertions = []
 423     index_offset = 0
 424     for segment in segments:
 425         if len(insertions) > 0 and insertions[-1][0] != segment['spline']:
 426             index_offset = 0
 427         points = bezierSegmentPoints(segment['beginPoint'], segment['endPoint'])
 428         paramA, paramB, pointA, pointB = nearestPointOfLines(points[0], points[1]-points[0], points[3], points[2]-points[3])
 429         if pointA and pointB:
 430             segment['cuts'].append({'param': 0.5})
 431             insertions.append((segment['spline'], segment['beginIndex']+1+index_offset, (pointA+pointB)*0.5))
 432             index_offset += 1
 433     subdivideBezierSegments(segments)
 434     for insertion in insertions:
 435         bezier_point = insertion[0].bezier_points[insertion[1]]
 436         bezier_point.co = insertion[2]
 437         bezier_point.handle_left_type = 'VECTOR'
 438         bezier_point.handle_right_type = 'VECTOR'
 439
 440 def bezierSubivideAt(points, params):
 441     if len(params) == 0:
 442         return []
 443     newPoints = []
 444     newPoints.append(points[0]+(points[1]-points[0])*params[0])
 445     for index, param in enumerate(params):
 446         paramLeft = param
 447         if index > 0:
 448             paramLeft -= params[index-1]
 449         paramRight = -param
 450         if index == len(params)-1:
 451             paramRight += 1.0
 452         else:
 453             paramRight += params[index+1]
 454         point = bezierPointAt(points, param)
 455         tangent = bezierTangentAt(points, param)
 456         newPoints.append(point-tangent*paramLeft)
 457         newPoints.append(point)
 458         newPoints.append(point+tangent*paramRight)
 459     newPoints.append(points[3]-(points[3]-points[2])*(1.0-params[-1]))
 460     return newPoints
 461
 462 def subdivideBezierSegment(segment):
 463     # Blender only allows uniform subdivision. Use this method to subdivide at arbitrary params.
 464     # NOTE: segment['cuts'] must be sorted by param
 465     if len(segment['cuts']) == 0:
 466         return
 467
 468     segment['beginPoint'] = segment['spline'].bezier_points[segment['beginIndex']]
 469     segment['endPoint'] = segment['spline'].bezier_points[segment['endIndex']]
 470     params = [cut['param'] for cut in segment['cuts']]
 471     newPoints = bezierSubivideAt(bezierSegmentPoints(segment['beginPoint'], segment['endPoint']), params)
 472     bpy.ops.curve.select_all(action='DESELECT')
 473     segment['beginPoint'] = segment['spline'].bezier_points[segment['beginIndex']]
 474     segment['beginPoint'].select_right_handle = True
 475     segment['beginPoint'].handle_left_type = 'FREE'
 476     segment['beginPoint'].handle_right_type = 'FREE'
 477     segment['endPoint'] = segment['spline'].bezier_points[segment['endIndex']]
 478     segment['endPoint'].select_left_handle = True
 479     segment['endPoint'].handle_left_type = 'FREE'
 480     segment['endPoint'].handle_right_type = 'FREE'
 481
 482     bpy.ops.curve.subdivide(number_cuts=len(params))
 483     if segment['endIndex'] > 0:
 484         segment['endIndex'] += len(params)
 485     segment['beginPoint'] = segment['spline'].bezier_points[segment['beginIndex']]
 486     segment['endPoint'] = segment['spline'].bezier_points[segment['endIndex']]
 487     segment['beginPoint'].select_right_handle = False
 488     segment['beginPoint'].handle_right = newPoints[0]
 489     segment['endPoint'].select_left_handle = False
 490     segment['endPoint'].handle_left = newPoints[-1]
 491
 492     for index, cut in enumerate(segment['cuts']):
 493         cut['index'] = segment['beginIndex']+1+index
 494         newPoint = segment['spline'].bezier_points[cut['index']]
 495         newPoint.handle_left_type = 'FREE'
 496         newPoint.handle_right_type = 'FREE'
 497         newPoint.select_left_handle = False
 498         newPoint.select_control_point = False
 499         newPoint.select_right_handle = False
 500         newPoint.handle_left = newPoints[index*3+1]
 501         newPoint.co = newPoints[index*3+2]
 502         newPoint.handle_right = newPoints[index*3+3]
 503
 504 def prepareSegmentIntersections(segments):
 505     def areCutsAdjacent(cutA, cutB):
 506         return cutA['segment']['beginIndex'] == cutB['segment']['endIndex'] and \
 507                cutA['param'] < param_tollerance and cutB['param'] > 1.0-param_tollerance
 508     for segment in segments:
 509         segment['cuts'].sort(key=(lambda cut: cut['param']))
 510         for index in range(len(segment['cuts'])-1, 0, -1):
 511             prev = segment['cuts'][index-1]
 512             current = segment['cuts'][index]
 513             if abs(prev['param']-current['param']) < param_tollerance and \
 514                prev['otherCut']['segment']['spline'] == current['otherCut']['segment']['spline'] and \
 515                (areCutsAdjacent(prev['otherCut'], current['otherCut']) or \
 516                 areCutsAdjacent(current['otherCut'], prev['otherCut'])):
 517                 deleteFromArray(prev['otherCut'], prev['otherCut']['segment']['cuts'])
 518                 deleteFromArray(current['otherCut'], current['otherCut']['segment']['cuts'])
 519                 segment['cuts'].pop(index-1 if current['otherCut']['param'] < param_tollerance else index)
 520                 current = segment['cuts'][index-1]['otherCut']
 521                 current['segment']['extraCut'] = current
 522
 523 def subdivideBezierSegmentsOfSameSpline(segments):
 524     # NOTE: segment['cuts'] must be sorted by param
 525     indexOffset = 0
 526     for segment in segments:
 527         segment['beginIndex'] += indexOffset
 528         if segment['endIndex'] > 0:
 529             segment['endIndex'] += indexOffset
 530         subdivideBezierSegment(segment)
 531         indexOffset += len(segment['cuts'])
 532     for segment in segments:
 533         segment['beginPoint'] = segment['spline'].bezier_points[segment['beginIndex']]
 534         segment['endPoint'] = segment['spline'].bezier_points[segment['endIndex']]
 535
 536 def subdivideBezierSegments(segments):
 537     # NOTE: segment['cuts'] must be sorted by param
 538     groups = {}
 539     for segment in segments:
 540         spline = segment['spline']
 541         if (spline in groups) == False:
 542             groups[spline] = []
 543         group = groups[spline]
 544         group.append(segment)
 545     for spline in groups:
 546         subdivideBezierSegmentsOfSameSpline(groups[spline])
 547
 548 def curveObject():
 549     obj = bpy.context.object
 550     return obj if obj != None and obj.type == 'CURVE' and obj.mode == 'EDIT' else None
 551
 552 def bezierSegments(splines, selection_only):
 553     segments = []
 554     for spline in splines:
 555         if spline.type != 'BEZIER':
 556             continue
 557         for index, current in enumerate(spline.bezier_points):
 558             next = spline.bezier_points[(index+1) % len(spline.bezier_points)]
 559             if next == spline.bezier_points[0] and not spline.use_cyclic_u:
 560                 continue
 561             if not selection_only or (current.select_right_handle and next.select_left_handle):
 562                 segments.append({
 563                     'spline': spline,
 564                     'beginIndex': index,
 565                     'endIndex': index+1 if index < len(spline.bezier_points)-1 else 0,
 566                     'beginPoint': current,
 567                     'endPoint': next,
 568                     'cuts': []
 569                 })
 570     return segments
 571
 572 def getSelectedSplines(include_bezier, include_polygon, allow_partial_selection=False):
 573     result = []
 574     for spline in bpy.context.object.data.splines:
 575         selected = not allow_partial_selection
 576         if spline.type == 'BEZIER':
 577             if not include_bezier:
 578                 continue
 579             for index, point in enumerate(spline.bezier_points):
 580                 if point.select_left_handle == allow_partial_selection or \
 581                    point.select_control_point == allow_partial_selection or \
 582                    point.select_right_handle == allow_partial_selection:
 583                     selected = allow_partial_selection
 584                     break
 585         elif spline.type == 'POLY':
 586             if not include_polygon:
 587                 continue
 588             for index, point in enumerate(spline.points):
 589                 if point.select == allow_partial_selection:
 590                     selected = allow_partial_selection
 591                     break
 592         else:
 593             continue
 594         if selected:
 595             result.append(spline)
 596     return result
 597
 598 def addObject(type, name):
 599     if type == 'CURVE':
 600         data = bpy.data.curves.new(name=name, type='CURVE')
 601         data.dimensions = '3D'
 602     elif type == 'MESH':
 603         data = bpy.data.meshes.new(name=name, type='MESH')
 604     obj = bpy.data.objects.new(name, data)
 605     obj.location = bpy.context.scene.cursor.location
 606     bpy.context.scene.collection.objects.link(obj)
 607     obj.select_set(True)
 608     bpy.context.view_layer.objects.active = obj
 609     return obj
 610
 611 def addPolygonSpline(obj, cyclic, vertices, weights=None, select=False):
 612     spline = obj.data.splines.new(type='POLY')
 613     spline.use_cyclic_u = cyclic
 614     spline.points.add(len(vertices)-1)
 615     for index, point in enumerate(spline.points):
 616         point.co.xyz = vertices[index]
 617         point.select = select
 618         if weights:
 619             point.weight_softbody = weights[index]
 620     return spline
 621
 622 def addBezierSpline(obj, cyclic, vertices, weights=None, select=False):
 623     spline = obj.data.splines.new(type='BEZIER')
 624     spline.use_cyclic_u = cyclic
 625     spline.bezier_points.add(len(vertices)-1)
 626     for index, point in enumerate(spline.bezier_points):
 627         point.handle_left = vertices[index][0]
 628         point.co = vertices[index][1]
 629         point.handle_right = vertices[index][2]
 630         if weights:
 631             point.weight_softbody = weights[index]
 632         point.select_left_handle = select
 633         point.select_control_point = select
 634         point.select_right_handle = select
 635         if isSegmentLinear([vertices[index-1][1], vertices[index-1][2], vertices[index][0], vertices[index][1]]):
 636             spline.bezier_points[index-1].handle_right_type = 'VECTOR'
 637             point.handle_left_type = 'VECTOR'
 638     return spline
 639
 640 def mergeEnds(splines, points, is_last_point):
 641     bpy.ops.curve.select_all(action='DESELECT')
 642     points[0].handle_left_type = points[0].handle_right_type = 'FREE'
 643     new_co = (points[0].co+points[1].co)*0.5
 644     handle = (points[1].handle_left if is_last_point[1] else points[1].handle_right)+new_co-points[1].co
 645     points[0].select_left_handle = points[0].select_right_handle = True
 646     if is_last_point[0]:
 647         points[0].handle_left += new_co-points[0].co
 648         points[0].handle_right = handle
 649     else:
 650         points[0].handle_right += new_co-points[0].co
 651         points[0].handle_left = handle
 652     points[0].co = new_co
 653     points[0].select_control_point = points[1].select_control_point = True
 654     bpy.ops.curve.make_segment()
 655     spline = splines[0] if splines[0] in bpy.context.object.data.splines.values() else splines[1]
 656     point = next(point for point in spline.bezier_points if point.select_left_handle)
 657     point.select_left_handle = point.select_right_handle = point.select_control_point = False
 658     bpy.ops.curve.delete()
 659     return spline
 660
 661 def polygonArcAt(center, radius, begin_angle, angle, step_angle, include_ends):
 662     vertices = []
 663     circle_samples = math.ceil(abs(angle)/step_angle)
 664     for t in (range(0, circle_samples+1) if include_ends else range(1, circle_samples)):
 665         t = begin_angle+angle*t/circle_samples
 666         normal = Vector((math.cos(t), math.sin(t), 0))
 667         vertices.append(center+normal*radius)
 668     return vertices
 669
 670 def bezierArcAt(tangent, normal, center, radius, angle, tollerance=0.99999):
 671     transform = Matrix.Identity(4)
 672     transform.col[0].xyz = tangent.cross(normal)*radius
 673     transform.col[1].xyz = tangent*radius
 674     transform.col[2].xyz = normal*radius
 675     transform.col[3].xyz = center
 676     segments = []
 677     segment_count = math.ceil(abs(angle)/(math.pi*0.5)*tollerance)
 678     angle /= segment_count
 679     x0 = math.cos(angle*0.5)
 680     y0 = math.sin(angle*0.5)
 681     x1 = (4.0-x0)/3.0
 682     y1 = (1.0-x0)*(3.0-x0)/(3.0*y0)
 683     points = [
 684         Vector((x0, -y0, 0)),
 685         Vector((x1, -y1, 0)),
 686         Vector((x1, y1, 0)),
 687         Vector((x0, y0, 0))
 688     ]
 689     for i in range(0, segment_count):
 690         rotation = Matrix.Rotation((i+0.5)*angle, 4, 'Z')
 691         segments.append(list(map(lambda v: transform@(rotation@v), points)))
 692     return segments
 693
 694 def iterateSpline(spline, callback):
 695     spline_points = spline.bezier_points if spline.type == 'BEZIER' else spline.points
 696     for index, spline_point in enumerate(spline_points):
 697         prev = spline_points[index-1]
 698         current = spline_points[index]
 699         next = spline_points[(index+1)%len(spline_points)]
 700         if spline.type == 'BEZIER':
 701             selected = current.select_control_point
 702             prev_segment_points = bezierSegmentPoints(prev, current)
 703             next_segment_points = bezierSegmentPoints(current, next)
 704             prev_tangent = (prev_segment_points[3]-prev_segment_points[2]).normalized()
 705             current_tangent = (next_segment_points[1]-next_segment_points[0]).normalized()
 706             next_tangent = (next_segment_points[3]-next_segment_points[2]).normalized()
 707         else:
 708             selected = current.select
 709             prev_segment_points = [prev.co.xyz, None, None, current.co.xyz]
 710             next_segment_points = [current.co.xyz, None, None, next.co.xyz]
 711             prev_tangent = (prev_segment_points[3]-prev_segment_points[0]).normalized()
 712             current_tangent = next_tangent = (next_segment_points[3]-next_segment_points[0]).normalized()
 713         normal = prev_tangent.cross(current_tangent).normalized()
 714         angle = prev_tangent@current_tangent
 715         angle = 0 if abs(angle-1.0) < 0.0001 else math.acos(angle)
 716         is_first = (index == 0) and not spline.use_cyclic_u
 717         is_last = (index == len(spline_points)-1) and not spline.use_cyclic_u
 718         callback(prev_segment_points, next_segment_points, selected, prev_tangent, current_tangent, next_tangent, normal, angle, is_first, is_last)
 719     return spline_points
 720
 721 def offsetPolygonOfSpline(spline, offset, step_angle, round_line_join, bezier_samples=128, tollerance=0.000001):
 722     def offsetVertex(position, tangent):
 723         normal = Vector((-tangent[1], tangent[0], 0))
 724         return position+normal*offset
 725     vertices = []
 726     def handlePoint(prev_segment_points, next_segment_points, selected, prev_tangent, current_tangent, next_tangent, normal, angle, is_first, is_last):
 727         sign = math.copysign(1, normal[2])
 728         angle *= sign
 729         if is_last:
 730             return
 731         is_protruding = (abs(angle) > tollerance and abs(offset) > tollerance)
 732         if is_protruding and not is_first and sign != math.copysign(1, offset): # Convex Corner
 733             if round_line_join:
 734                 begin_angle = math.atan2(prev_tangent[1], prev_tangent[0])+math.pi*0.5
 735                 vertices.extend(polygonArcAt(next_segment_points[0], offset, begin_angle, angle, step_angle, False))
 736             else:
 737                 distance = offset*math.tan(angle*0.5)
 738                 vertices.append(offsetVertex(next_segment_points[0], current_tangent)+current_tangent*distance)
 739         if is_protruding or is_first:
 740             vertices.append(offsetVertex(next_segment_points[0], current_tangent))
 741         if spline.type == 'POLY' or isSegmentLinear(next_segment_points):
 742             vertices.append(offsetVertex(next_segment_points[3], next_tangent))
 743         else: # Trace Bezier Segment
 744             prev_tangent = bezierTangentAt(next_segment_points, 0).normalized()
 745             for t in range(1, bezier_samples+1):
 746                 t /= bezier_samples
 747                 tangent = bezierTangentAt(next_segment_points, t).normalized()
 748                 if t == 1 or math.acos(min(max(-1, prev_tangent@tangent), 1)) >= step_angle:
 749                     vertices.append(offsetVertex(bezierPointAt(next_segment_points, t), tangent))
 750                     prev_tangent = tangent
 751     spline_points = iterateSpline(spline, handlePoint)
 752
 753     # Solve Self Intersections
 754     original_area = areaOfPolygon([point.co for point in spline_points])
 755     sign = -1 if offset < 0 else 1
 756     i = (0 if spline.use_cyclic_u else 1)
 757     while i < len(vertices):
 758         j = i+2
 759         while j < len(vertices) - (0 if i > 0 else 1):
 760             intersection = lineSegmentLineSegmentIntersection(vertices[i-1], vertices[i], vertices[j-1], vertices[j])
 761             if intersection == None:
 762                 j += 1
 763                 continue
 764             intersection = (intersection[2]+intersection[3])*0.5
 765             areaInner = sign*areaOfPolygon([intersection, vertices[i], vertices[j-1]])
 766             areaOuter = sign*areaOfPolygon([intersection, vertices[j], vertices[i-1]])
 767             if areaInner > areaOuter:
 768                 vertices = vertices[i:j]+[intersection]
 769                 i = (0 if spline.use_cyclic_u else 1)
 770             else:
 771                 vertices = vertices[:i]+[intersection]+vertices[j:]
 772             j = i+2
 773         i += 1
 774     new_area = areaOfPolygon(vertices)
 775     return [vertices] if original_area*new_area >= 0 else []
 776
 777 def filletSpline(spline, radius, chamfer_mode, limit_half_way, tollerance=0.0001):
 778     vertices = []
 779     distance_limit_factor = 0.5 if limit_half_way else 1.0
 780     def handlePoint(prev_segment_points, next_segment_points, selected, prev_tangent, current_tangent, next_tangent, normal, angle, is_first, is_last):
 781         distance = min((prev_segment_points[0]-prev_segment_points[3]).length*distance_limit_factor, (next_segment_points[0]-next_segment_points[3]).length*distance_limit_factor)
 782         if not selected or is_first or is_last or angle == 0 or distance == 0 or \
 783            (spline.type == 'BEZIER' and not (isSegmentLinear(prev_segment_points) and isSegmentLinear(next_segment_points))):
 784             prev_handle = next_segment_points[0] if is_first else prev_segment_points[2] if spline.type == 'BEZIER' else prev_segment_points[0]
 785             next_handle = next_segment_points[0] if is_last else next_segment_points[1] if spline.type == 'BEZIER' else next_segment_points[3]
 786             vertices.append([prev_handle, next_segment_points[0], next_handle])
 787             return
 788         tan_factor = math.tan(angle*0.5)
 789         offset = min(radius, distance/tan_factor)
 790         distance = offset*tan_factor
 791         circle_center = next_segment_points[0]+normal.cross(prev_tangent)*offset-prev_tangent*distance
 792         segments = bezierArcAt(prev_tangent, normal, circle_center, offset, angle)
 793         if chamfer_mode:
 794             vertices.append([prev_segment_points[0], segments[0][0], segments[-1][3]])
 795             vertices.append([segments[0][0], segments[-1][3], next_segment_points[3]])
 796         else:
 797             for i in range(0, len(segments)+1):
 798                 vertices.append([
 799                     segments[i-1][2] if i > 0 else prev_segment_points[0],
 800                     segments[i][0] if i < len(segments) else segments[i-1][3],
 801                     segments[i][1] if i < len(segments) else next_segment_points[3]
 802                 ])
 803     iterateSpline(spline, handlePoint)
 804     i = 0 if spline.use_cyclic_u else 1
 805     while(i < len(vertices)):
 806         if (vertices[i-1][1]-vertices[i][1]).length < tollerance:
 807             vertices[i-1][2] = vertices[i][2]
 808             del vertices[i]
 809         else:
 810             i = i+1
 811     return addBezierSpline(bpy.context.object, spline.use_cyclic_u, vertices)
 812
 813 def dogBone(spline, radius):
 814     vertices = []
 815     def handlePoint(prev_segment_points, next_segment_points, selected, prev_tangent, current_tangent, next_tangent, normal, angle, is_first, is_last):
 816         if not selected or is_first or is_last or angle == 0 or normal[2] > 0.0 or \
 817            (spline.type == 'BEZIER' and not (isSegmentLinear(prev_segment_points) and isSegmentLinear(next_segment_points))):
 818             prev_handle = next_segment_points[0] if is_first else prev_segment_points[2] if spline.type == 'BEZIER' else prev_segment_points[0]
 819             next_handle = next_segment_points[0] if is_last else next_segment_points[1] if spline.type == 'BEZIER' else next_segment_points[3]
 820             vertices.append([prev_handle, next_segment_points[0], next_handle])
 821             return
 822         tan_factor = math.tan(angle*0.5)
 823         corner = next_segment_points[0]+normal.cross(prev_tangent)*radius-prev_tangent*radius*tan_factor
 824         direction = next_segment_points[0]-corner
 825         distance = direction.length
 826         corner = next_segment_points[0]+direction/distance*(distance-radius)
 827         vertices.append([prev_segment_points[0], next_segment_points[0], corner])
 828         vertices.append([next_segment_points[0], corner, next_segment_points[0]])
 829         vertices.append([corner, next_segment_points[0], next_segment_points[3]])
 830     iterateSpline(spline, handlePoint)
 831     return vertices
 832
 833 def discretizeCurve(spline, step_angle, samples):
 834     vertices = []
 835     def handlePoint(prev_segment_points, next_segment_points, selected, prev_tangent, current_tangent, next_tangent, normal, angle, is_first, is_last):
 836         if is_last:
 837             return
 838         if isSegmentLinear(next_segment_points):
 839             vertices.append(next_segment_points[3])
 840         else:
 841             prev_tangent = bezierTangentAt(next_segment_points, 0).normalized()
 842             for t in range(1, samples+1):
 843                 t /= samples
 844                 tangent = bezierTangentAt(next_segment_points, t).normalized()
 845                 if t == 1 or math.acos(min(max(-1, prev_tangent@tangent), 1)) >= step_angle:
 846                     vertices.append(bezierPointAt(next_segment_points, t))
 847                     prev_tangent = tangent
 848     iterateSpline(spline, handlePoint)
 849     return vertices
 850
 851 def bezierBooleanGeometry(splineA, splineB, operation):
 852     if not splineA.use_cyclic_u or not splineB.use_cyclic_u:
 853         return False
 854     segmentsA = bezierSegments([splineA], False)
 855     segmentsB = bezierSegments([splineB], False)
 856
 857     deletionFlagA = isPointInSpline(splineA.bezier_points[0].co, splineB)
 858     deletionFlagB = isPointInSpline(splineB.bezier_points[0].co, splineA)
 859     if operation == 'DIFFERENCE':
 860         deletionFlagB = not deletionFlagB
 861     elif operation == 'INTERSECTION':
 862         deletionFlagA = not deletionFlagA
 863         deletionFlagB = not deletionFlagB
 864     elif operation != 'UNION':
 865         return False
 866
 867     intersections = []
 868     for segmentA in segmentsA:
 869         for segmentB in segmentsB:
 870             intersections.extend(segmentIntersection(segmentA, segmentB))
 871     if len(intersections) == 0:
 872         if deletionFlagA:
 873             bpy.context.object.data.splines.remove(splineA)
 874         if deletionFlagB:
 875             bpy.context.object.data.splines.remove(splineB)
 876         return True
 877
 878     prepareSegmentIntersections(segmentsA)
 879     prepareSegmentIntersections(segmentsB)
 880     subdivideBezierSegmentsOfSameSpline(segmentsA)
 881     subdivideBezierSegmentsOfSameSpline(segmentsB)
 882
 883     def collectCuts(cuts, segments, deletionFlag):
 884         for segmentIndex, segment in enumerate(segments):
 885             if 'extraCut' in segment:
 886                 deletionFlag = not deletionFlag
 887                 segment['extraCut']['index'] = segment['beginIndex']
 888                 segment['extraCut']['deletionFlag'] = deletionFlag
 889                 cuts.append(segment['extraCut'])
 890             else:
 891                 cuts.append(None)
 892             cuts.extend(segments[segmentIndex]['cuts'])
 893             segment['deletionFlag'] = deletionFlag
 894             for cutIndex, cut in enumerate(segment['cuts']):
 895                 deletionFlag = not deletionFlag
 896                 cut['deletionFlag'] = deletionFlag
 897     cutsA = []
 898     cutsB = []
 899     collectCuts(cutsA, segmentsA, deletionFlagA)
 900     collectCuts(cutsB, segmentsB, deletionFlagB)
 901
 902     beginIndex = 0
 903     for segment in segmentsA:
 904         if segment['deletionFlag'] == False:
 905             beginIndex = segment['beginIndex']
 906             break
 907         for cut in segment['cuts']:
 908             if cut['deletionFlag'] == False:
 909                 beginIndex = cut['index']
 910                 break
 911
 912     cuts = cutsA
 913     spline = splineA
 914     index = beginIndex
 915     backward = False
 916     vertices = []
 917     while True:
 918         current = spline.bezier_points[index]
 919         vertices.append([current.handle_left, current.co, current.handle_right])
 920         if backward:
 921             current.handle_left, current.handle_right = current.handle_right.copy(), current.handle_left.copy()
 922         index += len(spline.bezier_points)-1 if backward else 1
 923         index %= len(spline.bezier_points)
 924         if spline == splineA and index == beginIndex:
 925             break
 926
 927         cut = cuts[index]
 928         if cut != None:
 929             current = spline.bezier_points[index]
 930             current_handle = current.handle_right if backward else current.handle_left
 931             spline = splineA if spline == splineB else splineB
 932             cuts = cutsA if spline == splineA else cutsB
 933             index = cut['otherCut']['index']
 934             backward = cut['otherCut']['deletionFlag']
 935             next = spline.bezier_points[index]
 936             if backward:
 937                 next.handle_right = current_handle
 938             else:
 939                 next.handle_left = current_handle
 940             if spline == splineA and index == beginIndex:
 941                 break
 942
 943     spline = addBezierSpline(bpy.context.object, True, vertices)
 944     bpy.context.object.data.splines.remove(splineA)
 945     bpy.context.object.data.splines.remove(splineB)
 946     bpy.context.object.data.splines.active = spline
 947     return True
 948
 949 def truncateToFitBox(transform, spline, aabb):
 950     spline_points = spline.points
 951     aux = {
 952         'traces': [],
 953         'vertices': [],
 954         'weights': []
 955     }
 956     def terminateTrace(aux):
 957         if len(aux['vertices']) > 0:
 958             aux['traces'].append((aux['vertices'], aux['weights']))
 959         aux['vertices'] = []
 960         aux['weights'] = []
 961     for index, point in enumerate(spline_points):
 962         begin = transform@point.co.xyz
 963         end = spline_points[(index+1)%len(spline_points)]
 964         inside = isPointInAABB(begin, aabb)
 965         if inside:
 966             aux['vertices'].append(begin)
 967             aux['weights'].append(point.weight_softbody)
 968         if index == len(spline_points)-1 and not spline.use_cyclic_u:
 969             break
 970         intersections = lineAABBIntersection(begin, transform@end.co.xyz, aabb)
 971         if len(intersections) == 2:
 972             terminateTrace(aux)
 973             aux['traces'].append((
 974                 [intersections[0][1], intersections[1][1]],
 975                 [end.weight_softbody, end.weight_softbody]
 976             ))
 977         elif len(intersections) == 1:
 978             aux['vertices'].append(intersections[0][1])
 979             aux['weights'].append(end.weight_softbody)
 980             if inside:
 981                 terminateTrace(aux)
 982         elif inside and index == len(spline_points)-1 and spline.use_cyclic_u:
 983             terminateTrace(aux)
 984             aux['traces'][0] = (aux['traces'][-1][0]+aux['traces'][0][0], aux['traces'][-1][1]+aux['traces'][0][1])
 985             aux['traces'].pop()
 986     terminateTrace(aux)
 987     return aux['traces']
 988
 989 def arrayModifier(splines, offset, count, connect, serpentine):
 990     if connect:
 991         for spline in splines:
 992             if spline.use_cyclic_u:
 993                 spline.use_cyclic_u = False
 994                 points = spline.points if spline.type == 'POLY' else spline.bezier_points
 995                 points.add(1)
 996                 copyAttributes(points[-1], points[0])
 997     bpy.ops.curve.select_all(action='DESELECT')
 998     for spline in splines:
 999         if spline.type == 'BEZIER':
1000             for point in spline.bezier_points:
1001                 point.select_left_handle = point.select_control_point = point.select_right_handle = True
1002         elif spline.type == 'POLY':
1003             for point in spline.points:
1004                 point.select = True
1005     splines_at_layer = [splines]
1006     for i in range(1, count):
1007         bpy.ops.curve.duplicate()
1008         bpy.ops.transform.translate(value=offset)
1009         splines_at_layer.append(getSelectedSplines(True, True))
1010         if serpentine:
1011             bpy.ops.curve.switch_direction()
1012     if connect:
1013         for i in range(1, count):
1014             prev_layer = splines_at_layer[i-1]
1015             next_layer = splines_at_layer[i]
1016             for j in range(0, len(next_layer)):
1017                 bpy.ops.curve.select_all(action='DESELECT')
1018                 if prev_layer[j].type == 'POLY':
1019                     prev_layer[j].points[-1].select = True
1020                 else:
1021                     prev_layer[j].bezier_points[-1].select_control_point = True
1022                 if next_layer[j].type == 'POLY':
1023                     next_layer[j].points[0].select = True
1024                 else:
1025                     next_layer[j].bezier_points[0].select_control_point = True
1026                 bpy.ops.curve.make_segment()
1027     bpy.ops.curve.select_all(action='DESELECT')