curve_assign_shapekey.py

   1 # SPDX-License-Identifier: GPL-3.0-or-later
   2 # Copyright (C) 2019  Shrinivas Kulkarni
   3
   4 # This Blender add-on assigns one or more Bezier Curves as shape keys to another
   5 # Bezier Curve
   6 #
   7 # Supported Blender Versions: 2.8x
   8 #
   9 # https://github.com/Shriinivas/assignshapekey/blob/master/LICENSE
  10
  11 import bpy, bmesh, gpu
  12 from gpu_extras.batch import batch_for_shader
  13 from bpy.props import BoolProperty, EnumProperty, StringProperty
  14 from collections import OrderedDict
  15 from mathutils import Vector
  16 from math import sqrt, floor
  17 from functools import cmp_to_key
  18 from bpy.types import Panel, Operator, AddonPreferences
  19
  20
  21 bl_info = {
  22     "name": "Assign Shape Keys",
  23     "author": "Shrinivas Kulkarni",
  24     "version": (1, 0, 2),
  25     "blender": (3, 0, 0),
  26     "location": "View 3D > Sidebar > Edit Tab",
  27     "description": "Assigns one or more Bezier curves as shape keys to another Bezier curve",
  28     "doc_url": "{BLENDER_MANUAL_URL}/addons/add_curve/assign_shape_keys.html",
  29     "category": "Add Curve",
  30 }
  31
  32 alignList = [('minX', 'Min X', 'Align vertices with Min X'),
  33             ('maxX', 'Max X', 'Align vertices with Max X'),
  34             ('minY', 'Min Y', 'Align vertices with Min Y'),
  35             ('maxY', 'Max Y', 'Align vertices with Max Y'),
  36             ('minZ', 'Min Z', 'Align vertices with Min Z'),
  37             ('maxZ', 'Max Z', 'Align vertices with Max Z')]
  38
  39 matchList = [('vCnt', 'Vertex Count', 'Match by vertex count'),
  40             ('bbArea', 'Area', 'Match by surface area of the bounding box'), \
  41             ('bbHeight', 'Height', 'Match by bounding box height'), \
  42             ('bbWidth', 'Width', 'Match by bounding box width'),
  43             ('bbDepth', 'Depth', 'Match by bounding box depth'),
  44             ('minX', 'Min X', 'Match by bounding box Min X'),
  45             ('maxX', 'Max X', 'Match by bounding box Max X'),
  46             ('minY', 'Min Y', 'Match by bounding box Min Y'),
  47             ('maxY', 'Max Y', 'Match by bounding box Max Y'),
  48             ('minZ', 'Min Z', 'Match by bounding box Min Z'),
  49             ('maxZ', 'Max Z', 'Match by bounding box Max Z')]
  50
  51 DEF_ERR_MARGIN = 0.0001
  52
  53 def isBezier(obj):
  54     return obj.type == 'CURVE' and len(obj.data.splines) > 0 \
  55         and obj.data.splines[0].type == 'BEZIER'
  56
  57 #Avoid errors due to floating point conversions/comparisons
  58 #TODO: return -1, 0, 1
  59 def floatCmpWithMargin(float1, float2, margin = DEF_ERR_MARGIN):
  60     return abs(float1 - float2) < margin
  61
  62 def vectCmpWithMargin(v1, v2, margin = DEF_ERR_MARGIN):
  63     return all(floatCmpWithMargin(v1[i], v2[i], margin) for i in range(0, len(v1)))
  64
  65 class Segment():
  66
  67     #pts[0] - start, pts[1] - ctrl1, pts[2] - ctrl2, , pts[3] - end
  68     def pointAtT(pts, t):
  69         return pts[0] + t * (3 * (pts[1] - pts[0]) +
  70             t* (3 * (pts[0] + pts[2]) - 6 * pts[1] +
  71                 t * (-pts[0] + 3 * (pts[1] - pts[2]) + pts[3])))
  72
  73     def getSegLenRecurs(pts, start, end, t1 = 0, t2 = 1, error = DEF_ERR_MARGIN):
  74         t1_5 = (t1 + t2)/2
  75         mid = Segment.pointAtT(pts, t1_5)
  76         l = (end - start).length
  77         l2 = (mid - start).length + (end - mid).length
  78         if (l2 - l > error):
  79             return (Segment.getSegLenRecurs(pts, start, mid, t1, t1_5, error) +
  80                     Segment.getSegLenRecurs(pts, mid, end, t1_5, t2, error))
  81         return l2
  82
  83     def __init__(self, start, ctrl1, ctrl2, end):
  84         self.start = start
  85         self.ctrl1 = ctrl1
  86         self.ctrl2 = ctrl2
  87         self.end = end
  88         pts = [start, ctrl1, ctrl2, end]
  89         self.length = Segment.getSegLenRecurs(pts, start, end)
  90
  91     #see https://stackoverflow.com/questions/878862/drawing-part-of-a-b%c3%a9zier-curve-by-reusing-a-basic-b%c3%a9zier-curve-function/879213#879213
  92     def partialSeg(self, t0, t1):
  93         pts = [self.start, self.ctrl1, self.ctrl2, self.end]
  94
  95         if(t0 > t1):
  96             tt = t1
  97             t1 = t0
  98             t0 = tt
  99
 100         #Let's make at least the line segments of predictable length :)
 101         if(pts[0] == pts[1] and pts[2] == pts[3]):
 102             pt0 = Vector([(1 - t0) * pts[0][i] + t0 * pts[2][i] for i in range(0, 3)])
 103             pt1 = Vector([(1 - t1) * pts[0][i] + t1 * pts[2][i] for i in range(0, 3)])
 104             return Segment(pt0, pt0, pt1, pt1)
 105
 106         u0 = 1.0 - t0
 107         u1 = 1.0 - t1
 108
 109         qa = [pts[0][i]*u0*u0 + pts[1][i]*2*t0*u0 + pts[2][i]*t0*t0 for i in range(0, 3)]
 110         qb = [pts[0][i]*u1*u1 + pts[1][i]*2*t1*u1 + pts[2][i]*t1*t1 for i in range(0, 3)]
 111         qc = [pts[1][i]*u0*u0 + pts[2][i]*2*t0*u0 + pts[3][i]*t0*t0 for i in range(0, 3)]
 112         qd = [pts[1][i]*u1*u1 + pts[2][i]*2*t1*u1 + pts[3][i]*t1*t1 for i in range(0, 3)]
 113
 114         pta = Vector([qa[i]*u0 + qc[i]*t0 for i in range(0, 3)])
 115         ptb = Vector([qa[i]*u1 + qc[i]*t1 for i in range(0, 3)])
 116         ptc = Vector([qb[i]*u0 + qd[i]*t0 for i in range(0, 3)])
 117         ptd = Vector([qb[i]*u1 + qd[i]*t1 for i in range(0, 3)])
 118
 119         return Segment(pta, ptb, ptc, ptd)
 120
 121     #see https://stackoverflow.com/questions/24809978/calculating-the-bounding-box-of-cubic-bezier-curve
 122     #(3 D - 9 C + 9 B - 3 A) t^2 + (6 A - 12 B + 6 C) t + 3 (B - A)
 123     #pts[0] - start, pts[1] - ctrl1, pts[2] - ctrl2, , pts[3] - end
 124     #TODO: Return Vectors to make world space calculations consistent
 125     def bbox(self, mw = None):
 126         def evalBez(AA, BB, CC, DD, t):
 127             return AA * (1 - t) * (1 - t) * (1 - t) + \
 128                     3 * BB * t * (1 - t) * (1 - t) + \
 129                         3 * CC * t * t * (1 - t) + \
 130                             DD * t * t * t
 131
 132         A = self.start
 133         B = self.ctrl1
 134         C = self.ctrl2
 135         D = self.end
 136
 137         if(mw != None):
 138             A = mw @ A
 139             B = mw @ B
 140             C = mw @ C
 141             D = mw @ D
 142
 143         MINXYZ = [min([A[i], D[i]]) for i in range(0, 3)]
 144         MAXXYZ = [max([A[i], D[i]]) for i in range(0, 3)]
 145         leftBotBack_rgtTopFront = [MINXYZ, MAXXYZ]
 146
 147         a = [3 * D[i] - 9 * C[i] + 9 * B[i] - 3 * A[i] for i in range(0, 3)]
 148         b = [6 * A[i] - 12 * B[i] + 6 * C[i] for i in range(0, 3)]
 149         c = [3 * (B[i] - A[i]) for i in range(0, 3)]
 150
 151         solnsxyz = []
 152         for i in range(0, 3):
 153             solns = []
 154             if(a[i] == 0):
 155                 if(b[i] == 0):
 156                     solns.append(0)#Independent of t so lets take the starting pt
 157                 else:
 158                     solns.append(c[i] / b[i])
 159             else:
 160                 rootFact = b[i] * b[i] - 4 * a[i] * c[i]
 161                 if(rootFact >=0 ):
 162                     #Two solutions with + and - sqrt
 163                     solns.append((-b[i] + sqrt(rootFact)) / (2 * a[i]))
 164                     solns.append((-b[i] - sqrt(rootFact)) / (2 * a[i]))
 165             solnsxyz.append(solns)
 166
 167         for i, soln in enumerate(solnsxyz):
 168             for j, t in enumerate(soln):
 169                 if(t < 1 and t > 0):
 170                     co = evalBez(A[i], B[i], C[i], D[i], t)
 171                     if(co < leftBotBack_rgtTopFront[0][i]):
 172                         leftBotBack_rgtTopFront[0][i] = co
 173                     if(co > leftBotBack_rgtTopFront[1][i]):
 174                         leftBotBack_rgtTopFront[1][i] = co
 175
 176         return leftBotBack_rgtTopFront
 177
 178
 179 class Part():
 180     def __init__(self, parent, segs, isClosed):
 181         self.parent = parent
 182         self.segs = segs
 183
 184         #use_cyclic_u
 185         self.isClosed = isClosed
 186
 187         #Indicates if this should be closed based on its counterparts in other paths
 188         self.toClose = isClosed
 189
 190         self.length = sum(seg.length for seg in self.segs)
 191         self.bbox = None
 192         self.bboxWorldSpace = None
 193
 194     def getSeg(self, idx):
 195         return self.segs[idx]
 196
 197     def getSegs(self):
 198         return self.segs
 199
 200     def getSegsCopy(self, start, end):
 201         if(start == None):
 202             start = 0
 203         if(end == None):
 204             end = len(self.segs)
 205         return self.segs[start:end]
 206
 207     def getBBox(self, worldSpace):
 208         #Avoid frequent calculations, as this will be called in compare method
 209         if(not worldSpace and self.bbox != None):
 210             return self.bbox
 211
 212         if(worldSpace and self.bboxWorldSpace != None):
 213             return self.bboxWorldSpace
 214
 215         leftBotBack_rgtTopFront = [[None]*3,[None]*3]
 216
 217         for seg in self.segs:
 218
 219             if(worldSpace):
 220                 bb = seg.bbox(self.parent.curve.matrix_world)
 221             else:
 222                 bb = seg.bbox()
 223
 224             for i in range(0, 3):
 225                 if (leftBotBack_rgtTopFront[0][i] == None or \
 226                     bb[0][i] < leftBotBack_rgtTopFront[0][i]):
 227                     leftBotBack_rgtTopFront[0][i] = bb[0][i]
 228
 229             for i in range(0, 3):
 230                 if (leftBotBack_rgtTopFront[1][i] == None or \
 231                     bb[1][i] > leftBotBack_rgtTopFront[1][i]):
 232                     leftBotBack_rgtTopFront[1][i] = bb[1][i]
 233
 234         if(worldSpace):
 235             self.bboxWorldSpace = leftBotBack_rgtTopFront
 236         else:
 237             self.bbox = leftBotBack_rgtTopFront
 238
 239         return leftBotBack_rgtTopFront
 240
 241     #private
 242     def getBBDiff(self, axisIdx, worldSpace):
 243         obj = self.parent.curve
 244         bbox = self.getBBox(worldSpace)
 245         diff = abs(bbox[1][axisIdx] - bbox[0][axisIdx])
 246         return diff
 247
 248     def getBBWidth(self, worldSpace):
 249         return self.getBBDiff(0, worldSpace)
 250
 251     def getBBHeight(self, worldSpace):
 252         return self.getBBDiff(1, worldSpace)
 253
 254     def getBBDepth(self, worldSpace):
 255         return self.getBBDiff(2, worldSpace)
 256
 257     def bboxSurfaceArea(self, worldSpace):
 258         leftBotBack_rgtTopFront = self.getBBox(worldSpace)
 259         w = abs( leftBotBack_rgtTopFront[1][0] - leftBotBack_rgtTopFront[0][0] )
 260         l = abs( leftBotBack_rgtTopFront[1][1] - leftBotBack_rgtTopFront[0][1] )
 261         d = abs( leftBotBack_rgtTopFront[1][2] - leftBotBack_rgtTopFront[0][2] )
 262
 263         return 2 * (w * l + w * d + l * d)
 264
 265     def getSegCnt(self):
 266         return len(self.segs)
 267
 268     def getBezierPtsInfo(self):
 269         prevSeg = None
 270         bezierPtsInfo = []
 271
 272         for j, seg in enumerate(self.getSegs()):
 273
 274             pt = seg.start
 275             handleRight = seg.ctrl1
 276
 277             if(j == 0):
 278                 if(self.toClose):
 279                     handleLeft = self.getSeg(-1).ctrl2
 280                 else:
 281                     handleLeft = pt
 282             else:
 283                 handleLeft = prevSeg.ctrl2
 284
 285             bezierPtsInfo.append([pt, handleLeft, handleRight])
 286             prevSeg = seg
 287
 288         if(self.toClose == True):
 289             bezierPtsInfo[-1][2] = seg.ctrl1
 290         else:
 291             bezierPtsInfo.append([prevSeg.end, prevSeg.ctrl2, prevSeg.end])
 292
 293         return bezierPtsInfo
 294
 295     def __repr__(self):
 296         return str(self.length)
 297
 298
 299 class Path:
 300     def __init__(self, curve, objData = None, name = None):
 301
 302         if(objData == None):
 303             objData = curve.data
 304
 305         if(name == None):
 306             name = curve.name
 307
 308         self.name = name
 309         self.curve = curve
 310
 311         self.parts = [Part(self, getSplineSegs(s), s.use_cyclic_u) for s in objData.splines]
 312
 313     def getPartCnt(self):
 314         return len(self.parts)
 315
 316     def getPartView(self):
 317         p = Part(self, [seg for part in self.parts for seg in part.getSegs()], None)
 318         return p
 319
 320     def getPartBoundaryIdxs(self):
 321         cumulCntList = set()
 322         cumulCnt = 0
 323
 324         for p in self.parts:
 325             cumulCnt += p.getSegCnt()
 326             cumulCntList.add(cumulCnt)
 327
 328         return cumulCntList
 329
 330     def updatePartsList(self, segCntsPerPart, byPart):
 331         monolithicSegList = [seg for part in self.parts for seg in part.getSegs()]
 332         oldParts = self.parts[:]
 333         currPart = oldParts[0]
 334         partIdx = 0
 335         self.parts.clear()
 336
 337         for i in range(0, len(segCntsPerPart)):
 338             if( i == 0):
 339                 currIdx = 0
 340             else:
 341                 currIdx = segCntsPerPart[i-1]
 342
 343             nextIdx = segCntsPerPart[i]
 344             isClosed = False
 345
 346             if(vectCmpWithMargin(monolithicSegList[currIdx].start, \
 347                     currPart.getSegs()[0].start) and \
 348                 vectCmpWithMargin(monolithicSegList[nextIdx-1].end, \
 349                     currPart.getSegs()[-1].end)):
 350                 isClosed = currPart.isClosed
 351
 352             self.parts.append(Part(self, \
 353                 monolithicSegList[currIdx:nextIdx], isClosed))
 354
 355             if(monolithicSegList[nextIdx-1] == currPart.getSegs()[-1]):
 356                 partIdx += 1
 357                 if(partIdx < len(oldParts)):
 358                     currPart = oldParts[partIdx]
 359
 360     def getBezierPtsBySpline(self):
 361         data = []
 362
 363         for i, part in enumerate(self.parts):
 364             data.append(part.getBezierPtsInfo())
 365
 366         return data
 367
 368     def getNewCurveData(self):
 369
 370         newCurveData = self.curve.data.copy()
 371         newCurveData.splines.clear()
 372
 373         splinesData = self.getBezierPtsBySpline()
 374
 375         for i, newPoints in enumerate(splinesData):
 376
 377             spline = newCurveData.splines.new('BEZIER')
 378             spline.bezier_points.add(len(newPoints)-1)
 379             spline.use_cyclic_u = self.parts[i].toClose
 380
 381             for j in range(0, len(spline.bezier_points)):
 382                 newPoint = newPoints[j]
 383                 spline.bezier_points[j].co = newPoint[0]
 384                 spline.bezier_points[j].handle_left = newPoint[1]
 385                 spline.bezier_points[j].handle_right = newPoint[2]
 386                 spline.bezier_points[j].handle_right_type = 'FREE'
 387
 388         return newCurveData
 389
 390     def updateCurve(self):
 391         curveData = self.curve.data
 392         #Remove existing shape keys first
 393         if(curveData.shape_keys != None):
 394             keyblocks = reversed(curveData.shape_keys.key_blocks)
 395             for sk in keyblocks:
 396                 self.curve.shape_key_remove(sk)
 397         self.curve.data = self.getNewCurveData()
 398         bpy.data.curves.remove(curveData)
 399
 400 def main(targetObj, shapekeyObjs, removeOriginal, space, matchParts, \
 401     matchCriteria, alignBy, alignValues):
 402
 403     target = Path(targetObj)
 404
 405     shapekeys = [Path(c) for c in shapekeyObjs]
 406
 407     existingKeys = getExistingShapeKeyPaths(target)
 408     shapekeys = existingKeys + shapekeys
 409     userSel = [target] + shapekeys
 410
 411     for path in userSel:
 412         alignPath(path, matchParts, matchCriteria, alignBy, alignValues)
 413
 414     addMissingSegs(userSel, byPart = (matchParts != "-None-"))
 415
 416     bIdxs = set()
 417     for path in userSel:
 418         bIdxs = bIdxs.union(path.getPartBoundaryIdxs())
 419
 420     for path in userSel:
 421         path.updatePartsList(sorted(list(bIdxs)), byPart = False)
 422
 423     #All will have the same part count by now
 424     allToClose = [all(path.parts[j].isClosed for path in userSel)
 425         for j in range(0, len(userSel[0].parts))]
 426
 427     #All paths will have the same no of splines with the same no of bezier points
 428     for path in userSel:
 429         for j, part in enumerate(path.parts):
 430             part.toClose = allToClose[j]
 431
 432     target.updateCurve()
 433
 434     if(len(existingKeys) == 0):
 435         target.curve.shape_key_add(name = 'Basis')
 436
 437     addShapeKeys(target.curve, shapekeys, space)
 438
 439     if(removeOriginal):
 440         for path in userSel:
 441             if(path.curve != target.curve):
 442                 safeRemoveObj(path.curve)
 443
 444 def getSplineSegs(spline):
 445     p = spline.bezier_points
 446     segs = [Segment(p[i-1].co, p[i-1].handle_right, p[i].handle_left, p[i].co) \
 447         for i in range(1, len(p))]
 448     if(spline.use_cyclic_u):
 449         segs.append(Segment(p[-1].co, p[-1].handle_right, p[0].handle_left, p[0].co))
 450     return segs
 451
 452 def subdivideSeg(origSeg, noSegs):
 453     if(noSegs < 2):
 454         return [origSeg]
 455
 456     segs = []
 457     oldT = 0
 458     segLen = origSeg.length / noSegs
 459
 460     for i in range(0, noSegs-1):
 461         t = float(i+1) / noSegs
 462         seg = origSeg.partialSeg(oldT, t)
 463         segs.append(seg)
 464         oldT = t
 465
 466     seg = origSeg.partialSeg(oldT, 1)
 467     segs.append(seg)
 468
 469     return segs
 470
 471
 472 def getSubdivCntPerSeg(part, toAddCnt):
 473
 474     class SegWrapper:
 475         def __init__(self, idx, seg):
 476             self.idx = idx
 477             self.seg = seg
 478             self.length = seg.length
 479
 480     class PartWrapper:
 481         def __init__(self, part):
 482             self.segList = []
 483             self.segCnt = len(part.getSegs())
 484             for idx, seg in enumerate(part.getSegs()):
 485                 self.segList.append(SegWrapper(idx, seg))
 486
 487     partWrapper = PartWrapper(part)
 488     partLen = part.length
 489     avgLen = partLen / (partWrapper.segCnt + toAddCnt)
 490
 491     segsToDivide = [sr for sr in partWrapper.segList if sr.seg.length >= avgLen]
 492     segToDivideCnt = len(segsToDivide)
 493     avgLen = sum(sr.seg.length for sr in segsToDivide) / (segToDivideCnt + toAddCnt)
 494
 495     segsToDivide = sorted(segsToDivide, key=lambda x: x.length, reverse = True)
 496
 497     cnts = [0] * partWrapper.segCnt
 498     addedCnt = 0
 499
 500
 501     for i in range(0, segToDivideCnt):
 502         segLen = segsToDivide[i].seg.length
 503
 504         divideCnt = int(round(segLen/avgLen)) - 1
 505         if(divideCnt == 0):
 506             break
 507
 508         if((addedCnt + divideCnt) >= toAddCnt):
 509             cnts[segsToDivide[i].idx] = toAddCnt - addedCnt
 510             addedCnt = toAddCnt
 511             break
 512
 513         cnts[segsToDivide[i].idx] = divideCnt
 514
 515         addedCnt += divideCnt
 516
 517     #TODO: Verify if needed
 518     while(toAddCnt > addedCnt):
 519         for i in range(0, segToDivideCnt):
 520             cnts[segsToDivide[i].idx] += 1
 521             addedCnt += 1
 522             if(toAddCnt == addedCnt):
 523                 break
 524
 525     return cnts
 526
 527 #Just distribute equally; this is likely a rare condition. So why complicate?
 528 def distributeCnt(maxSegCntsByPart, startIdx, extraCnt):
 529     added = 0
 530     elemCnt = len(maxSegCntsByPart) - startIdx
 531     cntPerElem = floor(extraCnt / elemCnt)
 532     remainder = extraCnt % elemCnt
 533
 534     for i in range(startIdx, len(maxSegCntsByPart)):
 535         maxSegCntsByPart[i] += cntPerElem
 536         if(i < remainder + startIdx):
 537             maxSegCntsByPart[i] += 1
 538
 539 #Make all the paths to have the maximum number of segments in the set
 540 #TODO: Refactor
 541 def addMissingSegs(selPaths, byPart):
 542     maxSegCntsByPart = []
 543     maxSegCnt = 0
 544
 545     resSegCnt = []
 546     sortedPaths = sorted(selPaths, key = lambda c: -len(c.parts))
 547
 548     for i, path in enumerate(sortedPaths):
 549         if(byPart == False):
 550             segCnt = path.getPartView().getSegCnt()
 551             if(segCnt > maxSegCnt):
 552                 maxSegCnt = segCnt
 553         else:
 554             resSegCnt.append([])
 555             for j, part in enumerate(path.parts):
 556                 partSegCnt = part.getSegCnt()
 557                 resSegCnt[i].append(partSegCnt)
 558
 559                 #First path
 560                 if(j == len(maxSegCntsByPart)):
 561                     maxSegCntsByPart.append(partSegCnt)
 562
 563                 #last part of this path, but other paths in set have more parts
 564                 elif((j == len(path.parts) - 1) and
 565                     len(maxSegCntsByPart) > len(path.parts)):
 566
 567                     remainingSegs = sum(maxSegCntsByPart[j:])
 568                     if(partSegCnt <= remainingSegs):
 569                         resSegCnt[i][j] = remainingSegs
 570                     else:
 571                         #This part has more segs than the sum of the remaining part segs
 572                         #So distribute the extra count
 573                         distributeCnt(maxSegCntsByPart, j, (partSegCnt - remainingSegs))
 574
 575                         #Also, adjust the seg count of the last part of the previous
 576                         #segments that had fewer than max number of parts
 577                         for k in range(0, i):
 578                             if(len(sortedPaths[k].parts) < len(maxSegCntsByPart)):
 579                                 totalSegs = sum(maxSegCntsByPart)
 580                                 existingSegs = sum(maxSegCntsByPart[:len(sortedPaths[k].parts)-1])
 581                                 resSegCnt[k][-1] = totalSegs - existingSegs
 582
 583                 elif(partSegCnt > maxSegCntsByPart[j]):
 584                     maxSegCntsByPart[j] = partSegCnt
 585     for i, path in enumerate(sortedPaths):
 586
 587         if(byPart == False):
 588             partView = path.getPartView()
 589             segCnt = partView.getSegCnt()
 590             diff = maxSegCnt - segCnt
 591
 592             if(diff > 0):
 593                 cnts = getSubdivCntPerSeg(partView, diff)
 594                 cumulSegIdx = 0
 595                 for j in range(0, len(path.parts)):
 596                     part = path.parts[j]
 597                     newSegs = []
 598                     for k, seg in enumerate(part.getSegs()):
 599                         numSubdivs = cnts[cumulSegIdx] + 1
 600                         newSegs += subdivideSeg(seg, numSubdivs)
 601                         cumulSegIdx += 1
 602
 603                     path.parts[j] = Part(path, newSegs, part.isClosed)
 604         else:
 605             for j in range(0, len(path.parts)):
 606                 part = path.parts[j]
 607                 newSegs = []
 608
 609                 partSegCnt = part.getSegCnt()
 610
 611                 #TODO: Adding everything in the last part?
 612                 if(j == (len(path.parts)-1) and
 613                     len(maxSegCntsByPart) > len(path.parts)):
 614                     diff = resSegCnt[i][j] - partSegCnt
 615                 else:
 616                     diff = maxSegCntsByPart[j] - partSegCnt
 617
 618                 if(diff > 0):
 619                     cnts = getSubdivCntPerSeg(part, diff)
 620
 621                     for k, seg in enumerate(part.getSegs()):
 622                         seg = part.getSeg(k)
 623                         subdivCnt = cnts[k] + 1 #1 for the existing one
 624                         newSegs += subdivideSeg(seg, subdivCnt)
 625
 626                     #isClosed won't be used, but let's update anyway
 627                     path.parts[j] = Part(path, newSegs, part.isClosed)
 628
 629 #TODO: Simplify (Not very readable)
 630 def alignPath(path, matchParts, matchCriteria, alignBy, alignValues):
 631
 632     parts = path.parts[:]
 633
 634     if(matchParts == 'custom'):
 635         fnMap = {'vCnt' : lambda part: -1 * part.getSegCnt(), \
 636                  'bbArea': lambda part: -1 * part.bboxSurfaceArea(worldSpace = True), \
 637                  'bbHeight' : lambda part: -1 * part.getBBHeight(worldSpace = True), \
 638                  'bbWidth' : lambda part: -1 * part.getBBWidth(worldSpace = True), \
 639                  'bbDepth' : lambda part: -1 * part.getBBDepth(worldSpace = True)
 640                 }
 641         matchPartCmpFns = []
 642         for criterion in matchCriteria:
 643             fn = fnMap.get(criterion)
 644             if(fn == None):
 645                 minmax = criterion[:3] == 'max' #0 if min; 1 if max
 646                 axisIdx = ord(criterion[3:]) - ord('X')
 647
 648                 fn = eval('lambda part: part.getBBox(worldSpace = True)[' + \
 649                     str(minmax) + '][' + str(axisIdx) + ']')
 650
 651             matchPartCmpFns.append(fn)
 652
 653         def comparer(left, right):
 654             for fn in matchPartCmpFns:
 655                 a = fn(left)
 656                 b = fn(right)
 657
 658                 if(floatCmpWithMargin(a, b)):
 659                     continue
 660                 else:
 661                     return (a > b) - ( a < b) #No cmp in python3
 662
 663             return 0
 664
 665         parts = sorted(parts, key = cmp_to_key(comparer))
 666
 667     alignCmpFn = None
 668     if(alignBy == 'vertCo'):
 669         def evalCmp(criteria, pt1, pt2):
 670             if(len(criteria) == 0):
 671                 return True
 672
 673             minmax = criteria[0][0]
 674             axisIdx = criteria[0][1]
 675             val1 = pt1[axisIdx]
 676             val2 = pt2[axisIdx]
 677
 678             if(floatCmpWithMargin(val1, val2)):
 679                 criteria = criteria[:]
 680                 criteria.pop(0)
 681                 return evalCmp(criteria, pt1, pt2)
 682
 683             return val1 < val2 if minmax == 'min' else val1 > val2
 684
 685         alignCri = [[a[:3], ord(a[3:]) - ord('X')] for a in alignValues]
 686         alignCmpFn = lambda pt1, pt2, curve: (evalCmp(alignCri, \
 687             curve.matrix_world @ pt1, curve.matrix_world @ pt2))
 688
 689     startPt = None
 690     startIdx = None
 691
 692     for i in range(0, len(parts)):
 693         #Only truly closed parts
 694         if(alignCmpFn != None and parts[i].isClosed):
 695             for j in range(0, parts[i].getSegCnt()):
 696                 seg = parts[i].getSeg(j)
 697                 if(j == 0 or alignCmpFn(seg.start, startPt, path.curve)):
 698                     startPt = seg.start
 699                     startIdx = j
 700
 701             path.parts[i]= Part(path, parts[i].getSegsCopy(startIdx, None) + \
 702                 parts[i].getSegsCopy(None, startIdx), parts[i].isClosed)
 703         else:
 704             path.parts[i] = parts[i]
 705
 706 #TODO: Other shape key attributes like interpolation...?
 707 def getExistingShapeKeyPaths(path):
 708     obj = path.curve
 709     paths = []
 710
 711     if(obj.data.shape_keys != None):
 712         keyblocks = obj.data.shape_keys.key_blocks[:]
 713         for key in keyblocks:
 714             datacopy = obj.data.copy()
 715             i = 0
 716             for spline in datacopy.splines:
 717                 for pt in spline.bezier_points:
 718                     pt.co = key.data[i].co
 719                     pt.handle_left = key.data[i].handle_left
 720                     pt.handle_right = key.data[i].handle_right
 721                     i += 1
 722             paths.append(Path(obj, datacopy, key.name))
 723     return paths
 724
 725 def addShapeKeys(curve, paths, space):
 726     for path in paths:
 727         key = curve.shape_key_add(name = path.name)
 728         pts = [pt for pset in path.getBezierPtsBySpline() for pt in pset]
 729         for i, pt in enumerate(pts):
 730             if(space == 'worldspace'):
 731                 pt = [curve.matrix_world.inverted() @ (path.curve.matrix_world @ p) for p in pt]
 732             key.data[i].co = pt[0]
 733             key.data[i].handle_left = pt[1]
 734             key.data[i].handle_right = pt[2]
 735
 736 #TODO: Remove try
 737 def safeRemoveObj(obj):
 738     try:
 739         collections = obj.users_collection
 740
 741         for c in collections:
 742             c.objects.unlink(obj)
 743
 744         if(obj.name in bpy.context.scene.collection.objects):
 745             bpy.context.scene.collection.objects.unlink(obj)
 746
 747         if(obj.data.users == 1):
 748             if(obj.type == 'CURVE'):
 749                 bpy.data.curves.remove(obj.data) #This also removes object?
 750             elif(obj.type == 'MESH'):
 751                 bpy.data.meshes.remove(obj.data)
 752
 753         bpy.data.objects.remove(obj)
 754     except:
 755         pass
 756
 757
 758 def markVertHandler(self, context):
 759     if(self.markVertex):
 760         bpy.ops.wm.mark_vertex()
 761
 762
 763 #################### UI and Registration ####################
 764
 765 class AssignShapeKeysOp(Operator):
 766     bl_idname = "object.assign_shape_keys"
 767     bl_label = "Assign Shape Keys"
 768     bl_options = {'REGISTER', 'UNDO'}
 769
 770     def execute(self, context):
 771         params = context.window_manager.AssignShapeKeyParams
 772         removeOriginal = params.removeOriginal
 773         space = params.space
 774
 775         matchParts = params.matchParts
 776         matchCri1 = params.matchCri1
 777         matchCri2 = params.matchCri2
 778         matchCri3 = params.matchCri3
 779
 780         alignBy = params.alignCos
 781         alignVal1 = params.alignVal1
 782         alignVal2 = params.alignVal2
 783         alignVal3 = params.alignVal3
 784
 785         targetObj = bpy.context.active_object
 786         shapekeyObjs = [obj for obj in bpy.context.selected_objects if isBezier(obj) \
 787             and obj != targetObj]
 788
 789         if(targetObj != None and isBezier(targetObj) and len(shapekeyObjs) > 0):
 790             main(targetObj, shapekeyObjs, removeOriginal, space, \
 791                     matchParts, [matchCri1, matchCri2, matchCri3], \
 792                             alignBy, [alignVal1, alignVal2, alignVal3])
 793
 794         return {'FINISHED'}
 795
 796
 797 class MarkerController:
 798     drawHandlerRef = None
 799     defPointSize = 6
 800     ptColor = (0, .8, .8, 1)
 801
 802     def createSMMap(self, context):
 803         objs = context.selected_objects
 804         smMap = {}
 805         for curve in objs:
 806             if(not isBezier(curve)):
 807                 continue
 808
 809             smMap[curve.name] = {}
 810             mw = curve.matrix_world
 811             for splineIdx, spline in enumerate(curve.data.splines):
 812                 if(not spline.use_cyclic_u):
 813                     continue
 814
 815                 #initialize to the curr start vert co and idx
 816                 smMap[curve.name][splineIdx] = \
 817                     [mw @ curve.data.splines[splineIdx].bezier_points[0].co, 0]
 818
 819                 for pt in spline.bezier_points:
 820                     pt.select_control_point = False
 821
 822             if(len(smMap[curve.name]) == 0):
 823                 del smMap[curve.name]
 824
 825         return smMap
 826
 827     def createBatch(self, context):
 828         positions = [s[0] for cn in self.smMap.values() for s in cn.values()]
 829         colors = [MarkerController.ptColor for i in range(0, len(positions))]
 830
 831         self.batch = batch_for_shader(self.shader, \
 832             "POINTS", {"pos": positions, "color": colors})
 833
 834         if context.area:
 835             context.area.tag_redraw()
 836
 837     def drawHandler(self):
 838         gpu.state.point_size_set(MarkerController.defPointSize)
 839         self.batch.draw(self.shader)
 840
 841     def removeMarkers(self, context):
 842         if(MarkerController.drawHandlerRef != None):
 843             bpy.types.SpaceView3D.draw_handler_remove(MarkerController.drawHandlerRef, \
 844                 "WINDOW")
 845
 846             if(context.area and hasattr(context.space_data, 'region_3d')):
 847                 context.area.tag_redraw()
 848
 849             MarkerController.drawHandlerRef = None
 850
 851         self.deselectAll()
 852
 853     def __init__(self, context):
 854         self.smMap = self.createSMMap(context)
 855         self.shader = gpu.shader.from_builtin('3D_FLAT_COLOR')
 856         # self.shader.bind()
 857
 858         MarkerController.drawHandlerRef = \
 859             bpy.types.SpaceView3D.draw_handler_add(self.drawHandler, \
 860                 (), "WINDOW", "POST_VIEW")
 861
 862         self.createBatch(context)
 863
 864     def saveStartVerts(self):
 865         for curveName in self.smMap.keys():
 866             curve = bpy.data.objects[curveName]
 867             splines = curve.data.splines
 868             spMap = self.smMap[curveName]
 869
 870             for splineIdx in spMap.keys():
 871                 markerInfo = spMap[splineIdx]
 872                 if(markerInfo[1] != 0):
 873                     pts = splines[splineIdx].bezier_points
 874                     loc, idx = markerInfo[0], markerInfo[1]
 875                     cnt = len(pts)
 876
 877                     ptCopy = [[p.co.copy(), p.handle_right.copy(), \
 878                         p.handle_left.copy(), p.handle_right_type, \
 879                             p.handle_left_type] for p in pts]
 880
 881                     for i, pt in enumerate(pts):
 882                         srcIdx = (idx + i) % cnt
 883                         p = ptCopy[srcIdx]
 884
 885                         #Must set the types first
 886                         pt.handle_right_type = p[3]
 887                         pt.handle_left_type = p[4]
 888                         pt.co = p[0]
 889                         pt.handle_right = p[1]
 890                         pt.handle_left = p[2]
 891
 892     def updateSMMap(self):
 893         for curveName in self.smMap.keys():
 894             curve = bpy.data.objects[curveName]
 895             spMap = self.smMap[curveName]
 896             mw = curve.matrix_world
 897
 898             for splineIdx in spMap.keys():
 899                 markerInfo = spMap[splineIdx]
 900                 loc, idx = markerInfo[0], markerInfo[1]
 901                 pts = curve.data.splines[splineIdx].bezier_points
 902
 903                 selIdxs = [x for x in range(0, len(pts)) \
 904                     if pts[x].select_control_point == True]
 905
 906                 selIdx = selIdxs[0] if(len(selIdxs) > 0 ) else idx
 907                 co = mw @ pts[selIdx].co
 908                 self.smMap[curveName][splineIdx] = [co, selIdx]
 909
 910     def deselectAll(self):
 911         for curveName in self.smMap.keys():
 912             curve = bpy.data.objects[curveName]
 913             for spline in curve.data.splines:
 914                 for pt in spline.bezier_points:
 915                     pt.select_control_point = False
 916
 917     def getSpaces3D(context):
 918         areas3d  = [area for area in context.window.screen.areas \
 919             if area.type == 'VIEW_3D']
 920
 921         return [s for a in areas3d for s in a.spaces if s.type == 'VIEW_3D']
 922
 923     def hideHandles(context):
 924         states = []
 925         spaces = MarkerController.getSpaces3D(context)
 926         for s in spaces:
 927             if(hasattr(s.overlay, 'show_curve_handles')):
 928                 states.append(s.overlay.show_curve_handles)
 929                 s.overlay.show_curve_handles = False
 930             elif(hasattr(s.overlay, 'display_handle')): # 2.90
 931                 states.append(s.overlay.display_handle)
 932                 s.overlay.display_handle = 'NONE'
 933         return states
 934
 935     def resetShowHandleState(context, handleStates):
 936         spaces = MarkerController.getSpaces3D(context)
 937         for i, s in enumerate(spaces):
 938             if(hasattr(s.overlay, 'show_curve_handles')):
 939                 s.overlay.show_curve_handles = handleStates[i]
 940             elif(hasattr(s.overlay, 'display_handle')): # 2.90
 941                 s.overlay.display_handle = handleStates[i]
 942
 943
 944 class ModalMarkSegStartOp(Operator):
 945     bl_description = "Mark Vertex"
 946     bl_idname = "wm.mark_vertex"
 947     bl_label = "Mark Start Vertex"
 948
 949     def cleanup(self, context):
 950         wm = context.window_manager
 951         wm.event_timer_remove(self._timer)
 952         self.markerState.removeMarkers(context)
 953         MarkerController.resetShowHandleState(context, self.handleStates)
 954         context.window_manager.AssignShapeKeyParams.markVertex = False
 955
 956     def modal (self, context, event):
 957         params = context.window_manager.AssignShapeKeyParams
 958
 959         if(context.mode  == 'OBJECT' or event.type == "ESC" or\
 960             not context.window_manager.AssignShapeKeyParams.markVertex):
 961             self.cleanup(context)
 962             return {'CANCELLED'}
 963
 964         elif(event.type == "RET"):
 965             self.markerState.saveStartVerts()
 966             self.cleanup(context)
 967             return {'FINISHED'}
 968
 969         if(event.type == 'TIMER'):
 970             self.markerState.updateSMMap()
 971             self.markerState.createBatch(context)
 972
 973         return {"PASS_THROUGH"}
 974
 975     def execute(self, context):
 976         #TODO: Why such small step?
 977         self._timer = context.window_manager.event_timer_add(time_step = 0.0001, \
 978             window = context.window)
 979
 980         context.window_manager.modal_handler_add(self)
 981         self.markerState = MarkerController(context)
 982
 983         #Hide so that users don't accidentally select handles instead of points
 984         self.handleStates = MarkerController.hideHandles(context)
 985
 986         return {"RUNNING_MODAL"}
 987
 988
 989 class AssignShapeKeyParams(bpy.types.PropertyGroup):
 990
 991     removeOriginal : BoolProperty(name = "Remove Shape Key Objects", \
 992         description = "Remove shape key objects after assigning to target", \
 993             default = True)
 994
 995     space : EnumProperty(name = "Space", \
 996         items = [('worldspace', 'World Space', 'worldspace'),
 997                  ('localspace', 'Local Space', 'localspace')], \
 998         description = 'Space that shape keys are evluated in')
 999
1000     alignCos : EnumProperty(name="Vertex Alignment", items = \
1001         [("-None-", 'Manual Alignment', "Align curve segments based on starting vertex"), \
1002          ('vertCo', 'Vertex Coordinates', 'Align curve segments based on vertex coordinates')], \
1003         description = 'Start aligning the vertices of target and shape keys from',
1004         default = '-None-')
1005
1006     alignVal1 : EnumProperty(name="Value 1",
1007         items = alignList, default = 'minX', description='First align criterion')
1008
1009     alignVal2 : EnumProperty(name="Value 2",
1010         items = alignList, default = 'maxY', description='Second align criterion')
1011
1012     alignVal3 : EnumProperty(name="Value 3",
1013         items = alignList, default = 'minZ', description='Third align criterion')
1014
1015     matchParts : EnumProperty(name="Match Parts", items = \
1016         [("-None-", 'None', "Don't match parts"), \
1017         ('default', 'Default', 'Use part (spline) order as in curve'), \
1018         ('custom', 'Custom', 'Use one of the custom criteria for part matching')], \
1019         description='Match disconnected parts', default = 'default')
1020
1021     matchCri1 : EnumProperty(name="Value 1",
1022         items = matchList, default = 'minX', description='First match criterion')
1023
1024     matchCri2 : EnumProperty(name="Value 2",
1025         items = matchList, default = 'maxY', description='Second match criterion')
1026
1027     matchCri3 : EnumProperty(name="Value 3",
1028         items = matchList, default = 'minZ', description='Third match criterion')
1029
1030     markVertex : BoolProperty(name="Mark Starting Vertices", \
1031         description='Mark first vertices in all splines of selected curves', \
1032             default = False, update = markVertHandler)
1033
1034
1035 class AssignShapeKeysPanel(Panel):
1036
1037     bl_label = "Curve Shape Keys"
1038     bl_idname = "CURVE_PT_assign_shape_keys"
1039     bl_space_type = 'VIEW_3D'
1040     bl_region_type = 'UI'
1041     bl_category = "Edit"
1042     bl_options = {'DEFAULT_CLOSED'}
1043
1044     @classmethod
1045     def poll(cls, context):
1046         return context.mode in {'OBJECT', 'EDIT_CURVE'}
1047
1048     def draw(self, context):
1049
1050         layout = self.layout
1051         layout.label(text='Morph Curves:')
1052         col = layout.column()
1053         params = context.window_manager.AssignShapeKeyParams
1054
1055         if(context.mode  == 'OBJECT'):
1056             row = col.row()
1057             row.prop(params, "removeOriginal")
1058
1059             row = col.row()
1060             row.prop(params, "space")
1061
1062             row = col.row()
1063             row.prop(params, "alignCos")
1064
1065             if(params.alignCos == 'vertCo'):
1066                 row = col.row()
1067                 row.prop(params, "alignVal1")
1068                 row.prop(params, "alignVal2")
1069                 row.prop(params, "alignVal3")
1070
1071             row = col.row()
1072             row.prop(params, "matchParts")
1073
1074             if(params.matchParts == 'custom'):
1075                 row = col.row()
1076                 row.prop(params, "matchCri1")
1077                 row.prop(params, "matchCri2")
1078                 row.prop(params, "matchCri3")
1079
1080             row = col.row()
1081             row.operator("object.assign_shape_keys")
1082         else:
1083             col.prop(params, "markVertex", \
1084                 toggle = True)
1085
1086
1087 def updatePanel(self, context):
1088     try:
1089         panel = AssignShapeKeysPanel
1090         if "bl_rna" in panel.__dict__:
1091             bpy.utils.unregister_class(panel)
1092
1093         panel.bl_category = context.preferences.addons[__name__].preferences.category
1094         bpy.utils.register_class(panel)
1095
1096     except Exception as e:
1097         print("Assign Shape Keys: Updating Panel locations has failed", e)
1098
1099 class AssignShapeKeysPreferences(AddonPreferences):
1100     bl_idname = __name__
1101
1102     category: StringProperty(
1103             name = "Tab Category",
1104             description = "Choose a name for the category of the panel",
1105             default = "Edit",
1106             update = updatePanel
1107     )
1108
1109     def draw(self, context):
1110         layout = self.layout
1111         row = layout.row()
1112         col = row.column()
1113         col.label(text="Tab Category:")
1114         col.prop(self, "category", text="")
1115
1116 # registering and menu integration
1117 def register():
1118     bpy.utils.register_class(AssignShapeKeysPanel)
1119     bpy.utils.register_class(AssignShapeKeysOp)
1120     bpy.utils.register_class(AssignShapeKeyParams)
1121     bpy.types.WindowManager.AssignShapeKeyParams = \
1122         bpy.props.PointerProperty(type=AssignShapeKeyParams)
1123     bpy.utils.register_class(ModalMarkSegStartOp)
1124     bpy.utils.register_class(AssignShapeKeysPreferences)
1125     updatePanel(None, bpy.context)
1126
1127 def unregister():
1128     bpy.utils.unregister_class(AssignShapeKeysOp)
1129     bpy.utils.unregister_class(AssignShapeKeysPanel)
1130     del bpy.types.WindowManager.AssignShapeKeyParams
1131     bpy.utils.unregister_class(AssignShapeKeyParams)
1132     bpy.utils.unregister_class(ModalMarkSegStartOp)
1133     bpy.utils.unregister_class(AssignShapeKeysPreferences)
1134
1135 if __name__ == "__main__":
1136     register()