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     intersection = nearestPointOfLines(beginA, dirA, beginB, dirB)
 107     if math.isnan(intersection[0]) or (intersection[2]-intersection[3]).length > tollerance or \
 108        intersection[0] < 0 or intersection[0] > 1 or intersection[1] < 0 or intersection[1] > 1:
 109         return None
 110     return intersection
 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 deleteFromArray(item, array):
 294     for index, current in enumerate(array):
 295         if current is item:
 296             array.pop(index)
 297             break
 298
 299 def copyAttributes(dst, src):
 300     for attribute in dir(src):
 301         try:
 302             setattr(dst, attribute, getattr(src, attribute))
 303         except:
 304             pass
 305
 306 def bezierSliceFromTo(points, minParam, maxParam):
 307     fromP = bezierPointAt(points, minParam)
 308     fromT = bezierTangentAt(points, minParam)
 309     toP = bezierPointAt(points, maxParam)
 310     toT = bezierTangentAt(points, maxParam)
 311     paramDiff = maxParam-minParam
 312     return [fromP, fromP+fromT*paramDiff, toP-toT*paramDiff, toP]
 313
 314 def bezierIntersectionBroadPhase(solutions, pointsA, pointsB, aMin=0.0, aMax=1.0, bMin=0.0, bMax=1.0, depth=8, tollerance=0.001):
 315     if aabbIntersectionTest(aabbOfPoints(bezierSliceFromTo(pointsA, aMin, aMax)), aabbOfPoints(bezierSliceFromTo(pointsB, bMin, bMax)), tollerance) == False:
 316         return
 317     if depth == 0:
 318         solutions.append([aMin, aMax, bMin, bMax])
 319         return
 320     depth -= 1
 321     aMid = (aMin+aMax)*0.5
 322     bMid = (bMin+bMax)*0.5
 323     bezierIntersectionBroadPhase(solutions, pointsA, pointsB, aMin, aMid, bMin, bMid, depth, tollerance)
 324     bezierIntersectionBroadPhase(solutions, pointsA, pointsB, aMin, aMid, bMid, bMax, depth, tollerance)
 325     bezierIntersectionBroadPhase(solutions, pointsA, pointsB, aMid, aMax, bMin, bMid, depth, tollerance)
 326     bezierIntersectionBroadPhase(solutions, pointsA, pointsB, aMid, aMax, bMid, bMax, depth, tollerance)
 327
 328 def bezierIntersectionNarrowPhase(broadPhase, pointsA, pointsB, tollerance=0.000001):
 329     aMin = broadPhase[0]
 330     aMax = broadPhase[1]
 331     bMin = broadPhase[2]
 332     bMax = broadPhase[3]
 333     while (aMax-aMin > tollerance) or (bMax-bMin > tollerance):
 334         aMid = (aMin+aMax)*0.5
 335         bMid = (bMin+bMax)*0.5
 336         a1 = bezierPointAt(pointsA, (aMin+aMid)*0.5)
 337         a2 = bezierPointAt(pointsA, (aMid+aMax)*0.5)
 338         b1 = bezierPointAt(pointsB, (bMin+bMid)*0.5)
 339         b2 = bezierPointAt(pointsB, (bMid+bMax)*0.5)
 340         a1b1Dist = (a1-b1).length
 341         a2b1Dist = (a2-b1).length
 342         a1b2Dist = (a1-b2).length
 343         a2b2Dist = (a2-b2).length
 344         minDist = min(a1b1Dist, a2b1Dist, a1b2Dist, a2b2Dist)
 345         if a1b1Dist == minDist:
 346             aMax = aMid
 347             bMax = bMid
 348         elif a2b1Dist == minDist:
 349             aMin = aMid
 350             bMax = bMid
 351         elif a1b2Dist == minDist:
 352             aMax = aMid
 353             bMin = bMid
 354         else:
 355             aMin = aMid
 356             bMin = bMid
 357     return [aMin, bMin, minDist]
 358
 359 def segmentIntersection(segmentA, segmentB, tollerance=0.001):
 360     pointsA = bezierSegmentPoints(segmentA['beginPoint'], segmentA['endPoint'])
 361     pointsB = bezierSegmentPoints(segmentB['beginPoint'], segmentB['endPoint'])
 362     result = []
 363     def addCut(paramA, paramB):
 364         cutA = {'param': paramA, 'segment': segmentA}
 365         cutB = {'param': paramB, 'segment': segmentB}
 366         cutA['otherCut'] = cutB
 367         cutB['otherCut'] = cutA
 368         segmentA['cuts'].append(cutA)
 369         segmentB['cuts'].append(cutB)
 370         result.append([cutA, cutB])
 371     if isSegmentLinear(pointsA) and isSegmentLinear(pointsB):
 372         intersection = lineSegmentLineSegmentIntersection(pointsA[0], pointsA[3], pointsB[0], pointsB[3])
 373         if intersection != None:
 374             addCut(intersection[0], intersection[1])
 375         return result
 376     solutions = []
 377     bezierIntersectionBroadPhase(solutions, pointsA, pointsB)
 378     for index in range(0, len(solutions)):
 379         solutions[index] = bezierIntersectionNarrowPhase(solutions[index], pointsA, pointsB)
 380     for index in range(0, len(solutions)):
 381         for otherIndex in range(0, len(solutions)):
 382             if solutions[index][2] == float('inf'):
 383                 break
 384             if index == otherIndex or solutions[otherIndex][2] == float('inf'):
 385                 continue
 386             diffA = solutions[index][0]-solutions[otherIndex][0]
 387             diffB = solutions[index][1]-solutions[otherIndex][1]
 388             if diffA*diffA+diffB*diffB < 0.01:
 389                 if solutions[index][2] < solutions[otherIndex][2]:
 390                     solutions[otherIndex][2] = float('inf')
 391                 else:
 392                     solutions[index][2] = float('inf')
 393     def areIntersectionsAdjacent(segmentA, segmentB, paramA, paramB):
 394         return segmentA['endIndex'] == segmentB['beginIndex'] and paramA > 1-param_tollerance and paramB < param_tollerance
 395     for solution in solutions:
 396         if (solution[2] > tollerance) or \
 397           (segmentA['spline'] == segmentB['spline'] and \
 398           (areIntersectionsAdjacent(segmentA, segmentB, solution[0], solution[1]) or \
 399            areIntersectionsAdjacent(segmentB, segmentA, solution[1], solution[0]))):
 400             continue
 401         addCut(solution[0], solution[1])
 402     return result
 403
 404 def bezierMultiIntersection(segments):
 405     for index in range(0, len(segments)):
 406         for otherIndex in range(index+1, len(segments)):
 407             segmentIntersection(segments[index], segments[otherIndex])
 408     prepareSegmentIntersections(segments)
 409     subdivideBezierSegments(segments)
 410
 411 def bezierSubivideAt(points, params):
 412     if len(params) == 0:
 413         return []
 414     newPoints = []
 415     newPoints.append(points[0]+(points[1]-points[0])*params[0])
 416     for index, param in enumerate(params):
 417         paramLeft = param
 418         if index > 0:
 419             paramLeft -= params[index-1]
 420         paramRight = -param
 421         if index == len(params)-1:
 422             paramRight += 1.0
 423         else:
 424             paramRight += params[index+1]
 425         point = bezierPointAt(points, param)
 426         tangent = bezierTangentAt(points, param)
 427         newPoints.append(point-tangent*paramLeft)
 428         newPoints.append(point)
 429         newPoints.append(point+tangent*paramRight)
 430     newPoints.append(points[3]-(points[3]-points[2])*(1.0-params[-1]))
 431     return newPoints
 432
 433 def subdivideBezierSegment(segment):
 434     # Blender only allows uniform subdivision. Use this method to subdivide at arbitrary params.
 435     # NOTE: segment['cuts'] must be sorted by param
 436     if len(segment['cuts']) == 0:
 437         return
 438
 439     segment['beginPoint'] = segment['spline'].bezier_points[segment['beginIndex']]
 440     segment['endPoint'] = segment['spline'].bezier_points[segment['endIndex']]
 441     params = [cut['param'] for cut in segment['cuts']]
 442     newPoints = bezierSubivideAt(bezierSegmentPoints(segment['beginPoint'], segment['endPoint']), params)
 443     bpy.ops.curve.select_all(action='DESELECT')
 444     segment['beginPoint'] = segment['spline'].bezier_points[segment['beginIndex']]
 445     segment['beginPoint'].select_right_handle = True
 446     segment['beginPoint'].handle_left_type = 'FREE'
 447     segment['beginPoint'].handle_right_type = 'FREE'
 448     segment['endPoint'] = segment['spline'].bezier_points[segment['endIndex']]
 449     segment['endPoint'].select_left_handle = True
 450     segment['endPoint'].handle_left_type = 'FREE'
 451     segment['endPoint'].handle_right_type = 'FREE'
 452
 453     bpy.ops.curve.subdivide(number_cuts=len(params))
 454     if segment['endIndex'] > 0:
 455         segment['endIndex'] += len(params)
 456     segment['beginPoint'] = segment['spline'].bezier_points[segment['beginIndex']]
 457     segment['endPoint'] = segment['spline'].bezier_points[segment['endIndex']]
 458     segment['beginPoint'].select_right_handle = False
 459     segment['beginPoint'].handle_right = newPoints[0]
 460     segment['endPoint'].select_left_handle = False
 461     segment['endPoint'].handle_left = newPoints[-1]
 462
 463     for index, cut in enumerate(segment['cuts']):
 464         cut['index'] = segment['beginIndex']+1+index
 465         newPoint = segment['spline'].bezier_points[cut['index']]
 466         newPoint.handle_left_type = 'FREE'
 467         newPoint.handle_right_type = 'FREE'
 468         newPoint.select_left_handle = False
 469         newPoint.select_control_point = False
 470         newPoint.select_right_handle = False
 471         newPoint.handle_left = newPoints[index*3+1]
 472         newPoint.co = newPoints[index*3+2]
 473         newPoint.handle_right = newPoints[index*3+3]
 474
 475 def prepareSegmentIntersections(segments):
 476     def areCutsAdjacent(cutA, cutB):
 477         return cutA['segment']['beginIndex'] == cutB['segment']['endIndex'] and \
 478                cutA['param'] < param_tollerance and cutB['param'] > 1.0-param_tollerance
 479     for segment in segments:
 480         segment['cuts'].sort(key=(lambda cut: cut['param']))
 481         for index in range(len(segment['cuts'])-1, 0, -1):
 482             prev = segment['cuts'][index-1]
 483             current = segment['cuts'][index]
 484             if abs(prev['param']-current['param']) < param_tollerance and \
 485                prev['otherCut']['segment']['spline'] == current['otherCut']['segment']['spline'] and \
 486                (areCutsAdjacent(prev['otherCut'], current['otherCut']) or \
 487                 areCutsAdjacent(current['otherCut'], prev['otherCut'])):
 488                 deleteFromArray(prev['otherCut'], prev['otherCut']['segment']['cuts'])
 489                 deleteFromArray(current['otherCut'], current['otherCut']['segment']['cuts'])
 490                 segment['cuts'].pop(index-1 if current['otherCut']['param'] < param_tollerance else index)
 491                 current = segment['cuts'][index-1]['otherCut']
 492                 current['segment']['extraCut'] = current
 493
 494 def subdivideBezierSegmentsOfSameSpline(segments):
 495     # NOTE: segment['cuts'] must be sorted by param
 496     indexOffset = 0
 497     for segment in segments:
 498         segment['beginIndex'] += indexOffset
 499         if segment['endIndex'] > 0:
 500             segment['endIndex'] += indexOffset
 501         subdivideBezierSegment(segment)
 502         indexOffset += len(segment['cuts'])
 503     for segment in segments:
 504         segment['beginPoint'] = segment['spline'].bezier_points[segment['beginIndex']]
 505         segment['endPoint'] = segment['spline'].bezier_points[segment['endIndex']]
 506
 507 def subdivideBezierSegments(segments):
 508     # NOTE: segment['cuts'] must be sorted by param
 509     groups = {}
 510     for segment in segments:
 511         spline = segment['spline']
 512         if (spline in groups) == False:
 513             groups[spline] = []
 514         group = groups[spline]
 515         group.append(segment)
 516     for spline in groups:
 517         subdivideBezierSegmentsOfSameSpline(groups[spline])
 518
 519 def curveObject():
 520     obj = bpy.context.object
 521     return obj if obj != None and obj.type == 'CURVE' and obj.mode == 'EDIT' else None
 522
 523 def bezierSegments(splines, selection_only):
 524     segments = []
 525     for spline in splines:
 526         if spline.type != 'BEZIER':
 527             continue
 528         for index, current in enumerate(spline.bezier_points):
 529             next = spline.bezier_points[(index+1) % len(spline.bezier_points)]
 530             if next == spline.bezier_points[0] and not spline.use_cyclic_u:
 531                 continue
 532             if not selection_only or (current.select_right_handle and next.select_left_handle):
 533                 segments.append({
 534                     'spline': spline,
 535                     'beginIndex': index,
 536                     'endIndex': index+1 if index < len(spline.bezier_points)-1 else 0,
 537                     'beginPoint': current,
 538                     'endPoint': next,
 539                     'cuts': []
 540                 })
 541     return segments
 542
 543 def getSelectedSplines(include_bezier, include_polygon, allow_partial_selection=False):
 544     result = []
 545     for spline in bpy.context.object.data.splines:
 546         selected = not allow_partial_selection
 547         if spline.type == 'BEZIER':
 548             if not include_bezier:
 549                 continue
 550             for index, point in enumerate(spline.bezier_points):
 551                 if point.select_left_handle == allow_partial_selection or \
 552                    point.select_control_point == allow_partial_selection or \
 553                    point.select_right_handle == allow_partial_selection:
 554                     selected = allow_partial_selection
 555                     break
 556         elif spline.type == 'POLY':
 557             if not include_polygon:
 558                 continue
 559             for index, point in enumerate(spline.points):
 560                 if point.select == allow_partial_selection:
 561                     selected = allow_partial_selection
 562                     break
 563         else:
 564             continue
 565         if selected:
 566             result.append(spline)
 567     return result
 568
 569 def addObject(type, name):
 570     bpy.ops.object.select_all(action='DESELECT')
 571     if type == 'CURVE':
 572         data = bpy.data.curves.new(name=name, type='CURVE')
 573         data.dimensions = '3D'
 574     elif type == 'MESH':
 575         data = bpy.data.meshes.new(name=name, type='MESH')
 576     obj = bpy.data.objects.new(name, data)
 577     obj.location = bpy.context.scene.cursor.location
 578     bpy.context.scene.collection.objects.link(obj)
 579     obj.select_set(True)
 580     bpy.context.view_layer.objects.active = obj
 581     return obj
 582
 583 def addPolygonSpline(obj, cyclic, vertices, weights=None, select=False):
 584     spline = obj.data.splines.new(type='POLY')
 585     spline.use_cyclic_u = cyclic
 586     spline.points.add(len(vertices)-1)
 587     for index, point in enumerate(spline.points):
 588         point.co.xyz = vertices[index]
 589         point.select = select
 590         if weights:
 591             point.weight_softbody = weights[index]
 592     return spline
 593
 594 def addBezierSpline(obj, cyclic, vertices, weights=None, select=False):
 595     spline = obj.data.splines.new(type='BEZIER')
 596     spline.use_cyclic_u = cyclic
 597     spline.bezier_points.add(len(vertices)-1)
 598     for index, point in enumerate(spline.bezier_points):
 599         point.handle_left = vertices[index][0]
 600         point.co = vertices[index][1]
 601         point.handle_right = vertices[index][2]
 602         if weights:
 603             point.weight_softbody = weights[index]
 604         point.select_left_handle = select
 605         point.select_control_point = select
 606         point.select_right_handle = select
 607         if isSegmentLinear([vertices[index-1][1], vertices[index-1][2], vertices[index][0], vertices[index][1]]):
 608             spline.bezier_points[index-1].handle_right_type = 'VECTOR'
 609             point.handle_left_type = 'VECTOR'
 610     return spline
 611
 612 def polygonArcAt(center, radius, begin_angle, angle, step_angle, include_ends):
 613     vertices = []
 614     circle_samples = math.ceil(abs(angle)/step_angle)
 615     for t in (range(0, circle_samples+1) if include_ends else range(1, circle_samples)):
 616         t = begin_angle+angle*t/circle_samples
 617         normal = Vector((math.cos(t), math.sin(t), 0))
 618         vertices.append(center+normal*radius)
 619     return vertices
 620
 621 def bezierArcAt(tangent, normal, center, radius, angle, tollerance=0.99999):
 622     transform = Matrix.Identity(4)
 623     transform.col[0].xyz = tangent.cross(normal)*radius
 624     transform.col[1].xyz = tangent*radius
 625     transform.col[2].xyz = normal*radius
 626     transform.col[3].xyz = center
 627     segments = []
 628     segment_count = math.ceil(abs(angle)/(math.pi*0.5)*tollerance)
 629     angle /= segment_count
 630     x0 = math.cos(angle*0.5)
 631     y0 = math.sin(angle*0.5)
 632     x1 = (4.0-x0)/3.0
 633     y1 = (1.0-x0)*(3.0-x0)/(3.0*y0)
 634     points = [
 635         Vector((x0, -y0, 0)),
 636         Vector((x1, -y1, 0)),
 637         Vector((x1, y1, 0)),
 638         Vector((x0, y0, 0))
 639     ]
 640     for i in range(0, segment_count):
 641         rotation = Matrix.Rotation((i+0.5)*angle, 4, 'Z')
 642         segments.append(list(map(lambda v: transform@(rotation@v), points)))
 643     return segments
 644
 645 def iterateSpline(spline, callback):
 646     spline_points = spline.bezier_points if spline.type == 'BEZIER' else spline.points
 647     for index, spline_point in enumerate(spline_points):
 648         prev = spline_points[index-1]
 649         current = spline_points[index]
 650         next = spline_points[(index+1)%len(spline_points)]
 651         if spline.type == 'BEZIER':
 652             selected = current.select_control_point
 653             prev_segment_points = bezierSegmentPoints(prev, current)
 654             next_segment_points = bezierSegmentPoints(current, next)
 655             prev_tangent = (prev_segment_points[3]-prev_segment_points[2]).normalized()
 656             current_tangent = (next_segment_points[1]-next_segment_points[0]).normalized()
 657             next_tangent = (next_segment_points[3]-next_segment_points[2]).normalized()
 658         else:
 659             selected = current.select
 660             prev_segment_points = [prev.co.xyz, None, None, current.co.xyz]
 661             next_segment_points = [current.co.xyz, None, None, next.co.xyz]
 662             prev_tangent = (prev_segment_points[3]-prev_segment_points[0]).normalized()
 663             current_tangent = next_tangent = (next_segment_points[3]-next_segment_points[0]).normalized()
 664         normal = prev_tangent.cross(current_tangent).normalized()
 665         angle = prev_tangent@current_tangent
 666         angle = 0 if abs(angle-1.0) < 0.0001 else math.acos(angle)
 667         is_first = (index == 0) and not spline.use_cyclic_u
 668         is_last = (index == len(spline_points)-1) and not spline.use_cyclic_u
 669         callback(prev_segment_points, next_segment_points, selected, prev_tangent, current_tangent, next_tangent, normal, angle, is_first, is_last)
 670     return spline_points
 671
 672 def offsetPolygonOfSpline(spline, offset, step_angle, round_line_join, bezier_samples=128, tollerance=0.000001):
 673     def offsetVertex(position, tangent):
 674         normal = Vector((-tangent[1], tangent[0], 0))
 675         return position+normal*offset
 676     vertices = []
 677     def handlePoint(prev_segment_points, next_segment_points, selected, prev_tangent, current_tangent, next_tangent, normal, angle, is_first, is_last):
 678         sign = math.copysign(1, normal[2])
 679         angle *= sign
 680         if is_last:
 681             return
 682         is_protruding = (abs(angle) > tollerance and abs(offset) > tollerance)
 683         if is_protruding and not is_first and sign != math.copysign(1, offset): # Convex Corner
 684             if round_line_join:
 685                 begin_angle = math.atan2(prev_tangent[1], prev_tangent[0])+math.pi*0.5
 686                 vertices.extend(polygonArcAt(next_segment_points[0], offset, begin_angle, angle, step_angle, False))
 687             else:
 688                 distance = offset*math.tan(angle*0.5)
 689                 vertices.append(offsetVertex(next_segment_points[0], current_tangent)+current_tangent*distance)
 690         if is_protruding or is_first:
 691             vertices.append(offsetVertex(next_segment_points[0], current_tangent))
 692         if spline.type == 'POLY' or isSegmentLinear(next_segment_points):
 693             vertices.append(offsetVertex(next_segment_points[3], next_tangent))
 694         else: # Trace Bezier Segment
 695             prev_tangent = bezierTangentAt(next_segment_points, 0).normalized()
 696             for t in range(1, bezier_samples+1):
 697                 t /= bezier_samples
 698                 tangent = bezierTangentAt(next_segment_points, t).normalized()
 699                 if t == 1 or math.acos(min(max(-1, prev_tangent@tangent), 1)) >= step_angle:
 700                     vertices.append(offsetVertex(bezierPointAt(next_segment_points, t), tangent))
 701                     prev_tangent = tangent
 702     spline_points = iterateSpline(spline, handlePoint)
 703
 704     # Solve Self Intersections
 705     original_area = areaOfPolygon([point.co for point in spline_points])
 706     sign = -1 if offset < 0 else 1
 707     i = (0 if spline.use_cyclic_u else 1)
 708     while i < len(vertices):
 709         j = i+2
 710         while j < len(vertices) - (0 if i > 0 else 1):
 711             intersection = lineSegmentLineSegmentIntersection(vertices[i-1], vertices[i], vertices[j-1], vertices[j])
 712             if intersection == None:
 713                 j += 1
 714                 continue
 715             intersection = (intersection[2]+intersection[3])*0.5
 716             areaInner = sign*areaOfPolygon([intersection, vertices[i], vertices[j-1]])
 717             areaOuter = sign*areaOfPolygon([intersection, vertices[j], vertices[i-1]])
 718             if areaInner > areaOuter:
 719                 vertices = vertices[i:j]+[intersection]
 720                 i = (0 if spline.use_cyclic_u else 1)
 721             else:
 722                 vertices = vertices[:i]+[intersection]+vertices[j:]
 723             j = i+2
 724         i += 1
 725     new_area = areaOfPolygon(vertices)
 726     return [vertices] if original_area*new_area >= 0 else []
 727
 728 def filletSpline(spline, radius, chamfer_mode, limit_half_way, tollerance=0.0001):
 729     vertices = []
 730     distance_limit_factor = 0.5 if limit_half_way else 1.0
 731     def handlePoint(prev_segment_points, next_segment_points, selected, prev_tangent, current_tangent, next_tangent, normal, angle, is_first, is_last):
 732         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)
 733         if not selected or is_first or is_last or angle == 0 or distance == 0 or \
 734            (spline.type == 'BEZIER' and not (isSegmentLinear(prev_segment_points) and isSegmentLinear(next_segment_points))):
 735             prev_handle = next_segment_points[0] if is_first else prev_segment_points[2] if spline.type == 'BEZIER' else prev_segment_points[0]
 736             next_handle = next_segment_points[0] if is_last else next_segment_points[1] if spline.type == 'BEZIER' else next_segment_points[3]
 737             vertices.append([prev_handle, next_segment_points[0], next_handle])
 738             return
 739         tan_factor = math.tan(angle*0.5)
 740         offset = min(radius, distance/tan_factor)
 741         distance = offset*tan_factor
 742         circle_center = next_segment_points[0]+normal.cross(prev_tangent)*offset-prev_tangent*distance
 743         segments = bezierArcAt(prev_tangent, normal, circle_center, offset, angle)
 744         if chamfer_mode:
 745             vertices.append([prev_segment_points[0], segments[0][0], segments[-1][3]])
 746             vertices.append([segments[0][0], segments[-1][3], next_segment_points[3]])
 747         else:
 748             for i in range(0, len(segments)+1):
 749                 vertices.append([
 750                     segments[i-1][2] if i > 0 else prev_segment_points[0],
 751                     segments[i][0] if i < len(segments) else segments[i-1][3],
 752                     segments[i][1] if i < len(segments) else next_segment_points[3]
 753                 ])
 754     iterateSpline(spline, handlePoint)
 755     i = 0 if spline.use_cyclic_u else 1
 756     while(i < len(vertices)):
 757         if (vertices[i-1][1]-vertices[i][1]).length < tollerance:
 758             vertices[i-1][2] = vertices[i][2]
 759             del vertices[i]
 760         else:
 761             i = i+1
 762     return addBezierSpline(bpy.context.object, spline.use_cyclic_u, vertices)
 763
 764 def discretizeCurve(spline, step_angle, samples):
 765     vertices = []
 766     def handlePoint(prev_segment_points, next_segment_points, selected, prev_tangent, current_tangent, next_tangent, normal, angle, is_first, is_last):
 767         if is_last:
 768             return
 769         if isSegmentLinear(next_segment_points):
 770             vertices.append(next_segment_points[3])
 771         else:
 772             prev_tangent = bezierTangentAt(next_segment_points, 0).normalized()
 773             for t in range(1, samples+1):
 774                 t /= samples
 775                 tangent = bezierTangentAt(next_segment_points, t).normalized()
 776                 if t == 1 or math.acos(min(max(-1, prev_tangent@tangent), 1)) >= step_angle:
 777                     vertices.append(bezierPointAt(next_segment_points, t))
 778                     prev_tangent = tangent
 779     iterateSpline(spline, handlePoint)
 780     return vertices
 781
 782 def bezierBooleanGeometry(splineA, splineB, operation):
 783     if not splineA.use_cyclic_u or not splineB.use_cyclic_u:
 784         return False
 785     segmentsA = bezierSegments([splineA], False)
 786     segmentsB = bezierSegments([splineB], False)
 787
 788     deletionFlagA = isPointInSpline(splineA.bezier_points[0].co, splineB)
 789     deletionFlagB = isPointInSpline(splineB.bezier_points[0].co, splineA)
 790     if operation == 'DIFFERENCE':
 791         deletionFlagB = not deletionFlagB
 792     elif operation == 'INTERSECTION':
 793         deletionFlagA = not deletionFlagA
 794         deletionFlagB = not deletionFlagB
 795     elif operation != 'UNION':
 796         return False
 797
 798     intersections = []
 799     for segmentA in segmentsA:
 800         for segmentB in segmentsB:
 801             intersections.extend(segmentIntersection(segmentA, segmentB))
 802     if len(intersections) == 0:
 803         if deletionFlagA:
 804             bpy.context.object.data.splines.remove(splineA)
 805         if deletionFlagB:
 806             bpy.context.object.data.splines.remove(splineB)
 807         return True
 808
 809     prepareSegmentIntersections(segmentsA)
 810     prepareSegmentIntersections(segmentsB)
 811     subdivideBezierSegmentsOfSameSpline(segmentsA)
 812     subdivideBezierSegmentsOfSameSpline(segmentsB)
 813
 814     def collectCuts(cuts, segments, deletionFlag):
 815         for segmentIndex, segment in enumerate(segments):
 816             if 'extraCut' in segment:
 817                 deletionFlag = not deletionFlag
 818                 segment['extraCut']['index'] = segment['beginIndex']
 819                 segment['extraCut']['deletionFlag'] = deletionFlag
 820                 cuts.append(segment['extraCut'])
 821             else:
 822                 cuts.append(None)
 823             cuts.extend(segments[segmentIndex]['cuts'])
 824             segment['deletionFlag'] = deletionFlag
 825             for cutIndex, cut in enumerate(segment['cuts']):
 826                 deletionFlag = not deletionFlag
 827                 cut['deletionFlag'] = deletionFlag
 828     cutsA = []
 829     cutsB = []
 830     collectCuts(cutsA, segmentsA, deletionFlagA)
 831     collectCuts(cutsB, segmentsB, deletionFlagB)
 832
 833     beginIndex = 0
 834     for segment in segmentsA:
 835         if segment['deletionFlag'] == False:
 836             beginIndex = segment['beginIndex']
 837             break
 838         for cut in segment['cuts']:
 839             if cut['deletionFlag'] == False:
 840                 beginIndex = cut['index']
 841                 break
 842
 843     cuts = cutsA
 844     spline = splineA
 845     index = beginIndex
 846     backward = False
 847     vertices = []
 848     while True:
 849         current = spline.bezier_points[index]
 850         vertices.append([current.handle_left, current.co, current.handle_right])
 851         if backward:
 852             current.handle_left, current.handle_right = current.handle_right.copy(), current.handle_left.copy()
 853         index += len(spline.bezier_points)-1 if backward else 1
 854         index %= len(spline.bezier_points)
 855         if spline == splineA and index == beginIndex:
 856             break
 857
 858         cut = cuts[index]
 859         if cut != None:
 860             current = spline.bezier_points[index]
 861             current_handle = current.handle_right if backward else current.handle_left
 862             spline = splineA if spline == splineB else splineB
 863             cuts = cutsA if spline == splineA else cutsB
 864             index = cut['otherCut']['index']
 865             backward = cut['otherCut']['deletionFlag']
 866             next = spline.bezier_points[index]
 867             if backward:
 868                 next.handle_right = current_handle
 869             else:
 870                 next.handle_left = current_handle
 871             if spline == splineA and index == beginIndex:
 872                 break
 873
 874     spline = addBezierSpline(bpy.context.object, True, vertices)
 875     bpy.context.object.data.splines.remove(splineA)
 876     bpy.context.object.data.splines.remove(splineB)
 877     bpy.context.object.data.splines.active = spline
 878     return True
 879
 880 def truncateToFitBox(transform, spline, aabb):
 881     spline_points = spline.points
 882     aux = {
 883         'traces': [],
 884         'vertices': [],
 885         'weights': []
 886     }
 887     def terminateTrace(aux):
 888         if len(aux['vertices']) > 0:
 889             aux['traces'].append((aux['vertices'], aux['weights']))
 890         aux['vertices'] = []
 891         aux['weights'] = []
 892     for index, point in enumerate(spline_points):
 893         begin = transform@point.co.xyz
 894         end = spline_points[(index+1)%len(spline_points)]
 895         inside = isPointInAABB(begin, aabb)
 896         if inside:
 897             aux['vertices'].append(begin)
 898             aux['weights'].append(point.weight_softbody)
 899         if index == len(spline_points)-1 and not spline.use_cyclic_u:
 900             break
 901         intersections = lineAABBIntersection(begin, transform@end.co.xyz, aabb)
 902         if len(intersections) == 2:
 903             terminateTrace(aux)
 904             aux['traces'].append((
 905                 [intersections[0][1], intersections[1][1]],
 906                 [end.weight_softbody, end.weight_softbody]
 907             ))
 908         elif len(intersections) == 1:
 909             aux['vertices'].append(intersections[0][1])
 910             aux['weights'].append(end.weight_softbody)
 911             if inside:
 912                 terminateTrace(aux)
 913         elif inside and index == len(spline_points)-1 and spline.use_cyclic_u:
 914             terminateTrace(aux)
 915             aux['traces'][0] = (aux['traces'][-1][0]+aux['traces'][0][0], aux['traces'][-1][1]+aux['traces'][0][1])
 916             aux['traces'].pop()
 917     terminateTrace(aux)
 918     return aux['traces']
 919
 920 def arrayModifier(splines, offset, count, connect, serpentine):
 921     if connect:
 922         for spline in splines:
 923             if spline.use_cyclic_u:
 924                 spline.use_cyclic_u = False
 925                 points = spline.points if spline.type == 'POLY' else spline.bezier_points
 926                 points.add(1)
 927                 copyAttributes(points[-1], points[0])
 928     bpy.ops.curve.select_all(action='DESELECT')
 929     for spline in splines:
 930         if spline.type == 'BEZIER':
 931             for point in spline.bezier_points:
 932                 point.select_left_handle = point.select_control_point = point.select_right_handle = True
 933         elif spline.type == 'POLY':
 934             for point in spline.points:
 935                 point.select = True
 936     splines_at_layer = [splines]
 937     for i in range(1, count):
 938         bpy.ops.curve.duplicate()
 939         bpy.ops.transform.translate(value=offset)
 940         splines_at_layer.append(getSelectedSplines(True, True))
 941         if serpentine:
 942             bpy.ops.curve.switch_direction()
 943     if connect:
 944         for i in range(1, count):
 945             prev_layer = splines_at_layer[i-1]
 946             next_layer = splines_at_layer[i]
 947             for j in range(0, len(next_layer)):
 948                 bpy.ops.curve.select_all(action='DESELECT')
 949                 if prev_layer[j].type == 'POLY':
 950                     prev_layer[j].points[-1].select = True
 951                 else:
 952                     prev_layer[j].bezier_points[-1].select_control_point = True
 953                 if next_layer[j].type == 'POLY':
 954                     next_layer[j].points[0].select = True
 955                 else:
 956                     next_layer[j].bezier_points[0].select_control_point = True
 957                 bpy.ops.curve.make_segment()
 958     bpy.ops.curve.select_all(action='DESELECT')