85df6463eb0a78823480ea253ec86802a4857238
[blender-staging.git] / release / scripts / op / mesh_skin.py
1 # ##### BEGIN GPL LICENSE BLOCK #####
2 #
3 #  This program is free software; you can redistribute it and/or
4 #  modify it under the terms of the GNU General Public License
5 #  as published by the Free Software Foundation; either version 2
6 #  of the License, or (at your option) any later version.
7
8 #  This program is distributed in the hope that it will be useful,
9 #  but WITHOUT ANY WARRANTY; without even the implied warranty of
10 #  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11 #  GNU General Public License for more details.
12
13 #  You should have received a copy of the GNU General Public License
14 #  along with this program; if not, write to the Free Software Foundation,
15 #  Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
16 #
17 # ##### END GPL LICENSE BLOCK #####
18
19 # import Blender
20 import time, functools
21 import bpy
22 # from Blender import Window
23 from Mathutils import MidpointVecs, Vector
24 from Mathutils import AngleBetweenVecs as _AngleBetweenVecs_
25 # import BPyMessages
26
27 # from Blender.Draw import PupMenu
28
29 BIG_NUM = 1<<30
30
31 global CULL_METHOD
32 CULL_METHOD = 0 
33
34 def AngleBetweenVecs(a1,a2):
35         import math
36         try:
37                 return math.degrees(_AngleBetweenVecs_(a1,a2))
38         except:
39                 return 180.0
40
41 class edge(object):
42         __slots__ = 'v1', 'v2', 'co1', 'co2', 'length', 'removed', 'match', 'cent', 'angle', 'next', 'prev', 'normal', 'fake'
43         def __init__(self, v1,v2):
44                 self.v1 = v1
45                 self.v2 = v2
46                 co1, co2= v1.co, v2.co
47                 self.co1= co1
48                 self.co2= co2
49                 
50                 # uv1 uv2 vcol1 vcol2 # Add later
51                 self.length = (co1 - co2).length
52                 self.removed = 0        # Have we been culled from the eloop
53                 self.match = None       # The other edge were making a face with
54                 
55                 self.cent= MidpointVecs(co1, co2)
56                 self.angle= 0.0
57                 self.fake= False
58
59 class edgeLoop(object):
60         __slots__ = 'centre', 'edges', 'normal', 'closed', 'backup_edges'
61         def __init__(self, loop, me, closed): # Vert loop
62                 # Use next and prev, nextDist, prevDist
63                 
64                 # Get Loops centre.
65                 fac= len(loop)
66                 verts = me.verts
67                 self.centre= functools.reduce(lambda a,b: a+verts[b].co/fac, loop, Vector())
68                 
69                 # Convert Vert loop to Edges.
70                 self.edges = [edge(verts[loop[vIdx-1]], verts[loop[vIdx]]) for vIdx in range(len(loop))]
71                 
72                 if not closed:
73                         self.edges[0].fake = True # fake edge option
74                         
75                 self.closed = closed
76                         
77                 
78                 # Assign linked list
79                 for eIdx in range(len(self.edges)-1):
80                         self.edges[eIdx].next = self.edges[eIdx+1]
81                         self.edges[eIdx].prev = self.edges[eIdx-1]
82                 # Now last
83                 self.edges[-1].next = self.edges[0]
84                 self.edges[-1].prev = self.edges[-2]
85                 
86                 
87                 
88                 # GENERATE AN AVERAGE NORMAL FOR THE WHOLE LOOP.
89                 self.normal = Vector()
90                 for e in self.edges:
91                         n = (self.centre-e.co1).cross(self.centre-e.co2)
92                         # Do we realy need tot normalize?
93                         n.normalize()
94                         self.normal += n
95                         
96                         # Generate the angle
97                         va= e.cent - e.prev.cent
98                         vb= e.next.cent - e.cent
99                         
100                         e.angle= AngleBetweenVecs(va, vb)
101                 
102                 # Blur the angles
103                 #for e in self.edges:
104                 #       e.angle= (e.angle+e.next.angle)/2
105                 
106                 # Blur the angles
107                 #for e in self.edges:
108                 #       e.angle= (e.angle+e.prev.angle)/2
109                         
110                 self.normal.normalize()
111                 
112                 # Generate a normal for each edge.
113                 for e in self.edges:
114                         
115                         n1 = e.co1
116                         n2 = e.co2
117                         n3 = e.prev.co1
118                         
119                         a = n1-n2
120                         b = n1-n3
121                         normal1 = a.cross(b)
122                         normal1.normalize()
123                         
124                         n1 = e.co2
125                         n3 = e.next.co2
126                         n2 = e.co1
127                         
128                         a = n1-n2
129                         b = n1-n3
130                         
131                         normal2 = a.cross(b)
132                         normal2.normalize()
133                         
134                         # Reuse normal1 var
135                         normal1 += normal1 + normal2
136                         normal1.normalize()
137                         
138                         e.normal = normal1
139                         #print e.normal
140
141
142                 
143         def backup(self):
144                 # Keep a backup of the edges
145                 self.backup_edges = self.edges[:]
146                         
147         def restore(self):
148                 self.edges = self.backup_edges[:]
149                 for e in self.edges:
150                         e.removed = 0
151                 
152         def reverse(self):
153                 self.edges.reverse()
154                 self.normal.negate()
155                 
156                 for e in self.edges:
157                         e.normal.negate()
158                         e.v1, e.v2 = e.v2, e.v1
159                         e.co1, e.co2 = e.co2, e.co1
160                         e.next, e.prev = e.prev, e.next
161                 
162         
163         def removeSmallest(self, cullNum, otherLoopLen):
164                 '''
165                 Removes N Smallest edges and backs up the loop,
166                 this is so we can loop between 2 loops as if they are the same length,
167                 backing up and restoring incase the loop needs to be skinned with another loop of a different length.
168                 '''
169                 global CULL_METHOD
170                 if CULL_METHOD == 1: # Shortest edge
171                         eloopCopy = self.edges[:]
172                         
173                         # Length sort, smallest first
174                         try:    eloopCopy.sort(key = lambda e1: e1.length)
175                         except: eloopCopy.sort(lambda e1, e2: cmp(e1.length, e2.length ))
176                         
177                         # Dont use atm
178                         #eloopCopy.sort(lambda e1, e2: cmp(e1.angle*e1.length, e2.angle*e2.length)) # Length sort, smallest first
179                         #eloopCopy.sort(lambda e1, e2: cmp(e1.angle, e2.angle)) # Length sort, smallest first
180                         
181                         remNum = 0
182                         for i, e in enumerate(eloopCopy):
183                                 if not e.fake:
184                                         e.removed = 1
185                                         self.edges.remove( e ) # Remove from own list, still in linked list.
186                                         remNum += 1
187                                 
188                                         if not remNum < cullNum:
189                                                 break
190                         
191                 else: # CULL METHOD is even
192                                 
193                         culled = 0
194                         
195                         step = int(otherLoopLen / float(cullNum)) * 2
196                         
197                         currentEdge = self.edges[0]
198                         while culled < cullNum:
199                                 
200                                 # Get the shortest face in the next STEP
201                                 step_count= 0
202                                 bestAng= 360.0
203                                 smallestEdge= None
204                                 while step_count<=step or smallestEdge==None:
205                                         step_count+=1
206                                         if not currentEdge.removed: # 0 or -1 will not be accepted
207                                                 if currentEdge.angle<bestAng and not currentEdge.fake:
208                                                         smallestEdge= currentEdge
209                                                         bestAng= currentEdge.angle
210                                         
211                                         currentEdge = currentEdge.next
212                                 
213                                 # In that stepping length we have the smallest edge.remove it
214                                 smallestEdge.removed = 1
215                                 self.edges.remove(smallestEdge)
216                                 
217                                 # Start scanning from the edge we found? - result is over fanning- no good.
218                                 #currentEdge= smallestEdge.next
219                                 
220                                 culled+=1
221         
222
223 # Returns face edges.
224 # face must have edge data.
225         
226 def mesh_faces_extend(me, faces, mat_idx = 0):
227         orig_facetot = len(me.faces)
228         new_facetot = len(faces)
229         me.add_geometry(0, 0, new_facetot)
230         tot = orig_facetot+new_facetot
231         me_faces = me.faces
232         i= 0
233         while i < new_facetot:
234                 
235                 f = [v.index for v in faces[i]]
236                 if len(f)==4 and f[3]==0:
237                         f = f[1], f[2], f[3], f[0]
238                 
239                 mf = me_faces[orig_facetot+i]
240                 mf.verts_raw =  f
241                 mf.material_index = mat_idx
242                 i+=1
243 # end utils
244
245
246 def getSelectedEdges(context, me, ob):
247         MESH_MODE= context.scene.tool_settings.mesh_selection_mode
248         
249         if MESH_MODE in ('EDGE', 'VERTEX'):
250                 context.scene.tool_settings.mesh_selection_mode = 'EDGE'
251                 edges= [ ed for ed in me.edges if ed.selected ]
252                 # print len(edges), len(me.edges)
253                 context.scene.tool_settings.mesh_selection_mode = MESH_MODE
254                 return edges
255         
256         if MESH_MODE == 'FACE':
257                 context.scene.tool_settings.mesh_selection_mode = 'EDGE'
258                 # value is [edge, face_sel_user_in]
259                 edge_dict=  dict((ed.key(), [ed, 0]) for ed in me.edges)
260                 
261                 for f in me.faces:
262                         if f.selected:
263                                 for edkey in f.edge_keys():
264                                         edge_dict[edkey][1] += 1
265                 
266                 context.scene.tool_settings.mesh_selection_mode = MESH_MODE
267                 return [ ed_data[0] for ed_data in edge_dict.values() if ed_data[1] == 1 ]
268         
269         
270
271 def getVertLoops(selEdges, me):
272         '''
273         return a list of vert loops, closed and open [(loop, closed)...]
274         '''
275         
276         mainVertLoops = []
277         # second method
278         tot = len(me.verts)
279         vert_siblings = [[] for i in range(tot)]
280         vert_used = [False] * tot
281         
282         for ed in selEdges:
283                 i1, i2 = ed.key()
284                 vert_siblings[i1].append(i2)
285                 vert_siblings[i2].append(i1)
286         
287         # find the first used vert and keep looping.
288         for i in range(tot):
289                 if vert_siblings[i] and not vert_used[i]:
290                         sbl = vert_siblings[i] # siblings
291                         
292                         if len(sbl) > 2:
293                                 return None
294                         
295                         vert_used[i] = True
296                         
297                         # do an edgeloop seek
298                         if len(sbl) == 2:
299                                 contextVertLoop= [sbl[0], i, sbl[1]] # start the vert loop
300                                 vert_used[contextVertLoop[ 0]] = True
301                                 vert_used[contextVertLoop[-1]] = True
302                         else:
303                                 contextVertLoop= [i, sbl[0]]
304                                 vert_used[contextVertLoop[ 1]] = True
305                         
306                         # Always seek up
307                         ok = True
308                         while ok:
309                                 ok = False
310                                 closed = False
311                                 sbl = vert_siblings[contextVertLoop[-1]]
312                                 if len(sbl) == 2:
313                                         next = sbl[not sbl.index( contextVertLoop[-2] )]
314                                         if vert_used[next]:
315                                                 closed = True
316                                                 # break
317                                         else:
318                                                 contextVertLoop.append( next ) # get the vert that isnt the second last
319                                                 vert_used[next] = True
320                                                 ok = True
321                         
322                         # Seek down as long as the starting vert was not at the edge.
323                         if not closed and len(vert_siblings[i]) == 2:
324                                 
325                                 ok = True
326                                 while ok:
327                                         ok = False
328                                         sbl = vert_siblings[contextVertLoop[0]]
329                                         if len(sbl) == 2:
330                                                 next = sbl[not sbl.index( contextVertLoop[1] )]
331                                                 if vert_used[next]:
332                                                         closed = True
333                                                 else:
334                                                         contextVertLoop.insert(0, next) # get the vert that isnt the second last
335                                                         vert_used[next] = True
336                                                         ok = True
337                         
338                         mainVertLoops.append((contextVertLoop, closed))
339         
340         
341         verts = me.verts
342         # convert from indicies to verts
343         # mainVertLoops = [([verts[i] for i in contextVertLoop], closed) for contextVertLoop, closed in  mainVertLoops]
344         # print len(mainVertLoops)
345         return mainVertLoops
346         
347
348
349 def skin2EdgeLoops(eloop1, eloop2, me, ob, MODE):
350         
351         new_faces= [] # 
352         
353         # Make sure e1 loops is bigger then e2
354         if len(eloop1.edges) != len(eloop2.edges):
355                 if len(eloop1.edges) < len(eloop2.edges):
356                         eloop1, eloop2 = eloop2, eloop1
357                 
358                 eloop1.backup() # were about to cull faces
359                 CULL_FACES = len(eloop1.edges) - len(eloop2.edges)
360                 eloop1.removeSmallest(CULL_FACES, len(eloop1.edges))
361         else:
362                 CULL_FACES = 0
363         # First make sure poly vert loops are in sync with eachother.
364         
365         # The vector allong which we are skinning.
366         skinVector = eloop1.centre - eloop2.centre
367         
368         loopDist = skinVector.length
369         
370         # IS THE LOOP FLIPPED, IF SO FLIP BACK. we keep it flipped, its ok,
371         if eloop1.closed or eloop2.closed:
372                 angleBetweenLoopNormals = AngleBetweenVecs(eloop1.normal, eloop2.normal)
373                 if angleBetweenLoopNormals > 90:
374                         eloop2.reverse()
375                         
376
377                 DIR= eloop1.centre - eloop2.centre
378                 
379                 # if eloop2.closed:
380                 bestEloopDist = BIG_NUM
381                 bestOffset = 0
382                 # Loop rotation offset to test.1
383                 eLoopIdxs = list(range(len(eloop1.edges)))
384                 for offset in range(len(eloop1.edges)):
385                         totEloopDist = 0 # Measure this total distance for thsi loop.
386                         
387                         offsetIndexLs = eLoopIdxs[offset:] + eLoopIdxs[:offset] # Make offset index list
388                         
389                         
390                         # e1Idx is always from 0uu to N, e2Idx is offset.
391                         for e1Idx, e2Idx in enumerate(offsetIndexLs):
392                                 e1= eloop1.edges[e1Idx]
393                                 e2= eloop2.edges[e2Idx]
394                                 
395                                 
396                                 # Include fan connections in the measurement.
397                                 OK= True
398                                 while OK or e1.removed:
399                                         OK= False
400                                         
401                                         # Measure the vloop distance ===============
402                                         diff= ((e1.cent - e2.cent).length) #/ nangle1
403                                         
404                                         ed_dir= e1.cent-e2.cent
405                                         a_diff= AngleBetweenVecs(DIR, ed_dir)/18 # 0 t0 18
406                                         
407                                         totEloopDist += (diff * (1+a_diff)) / (1+loopDist)
408                                         
409                                         # Premeture break if where no better off
410                                         if totEloopDist > bestEloopDist:
411                                                 break
412                                         
413                                         e1=e1.next
414                                         
415                         if totEloopDist < bestEloopDist:
416                                 bestOffset = offset
417                                 bestEloopDist = totEloopDist
418                 
419                 # Modify V2 LS for Best offset
420                 eloop2.edges = eloop2.edges[bestOffset:] + eloop2.edges[:bestOffset]
421                         
422         else:
423                 # Both are open loops, easier to calculate.
424                 
425                 
426                 # Make sure the fake edges are at the start.
427                 for i, edloop in enumerate((eloop1, eloop2)):
428                         # print "LOOPO"
429                         if edloop.edges[0].fake:
430                                 # alredy at the start
431                                 #print "A"
432                                 pass
433                         elif edloop.edges[-1].fake:
434                                 # put the end at the start
435                                 edloop.edges.insert(0, edloop.edges.pop())
436                                 #print "B"
437                                 
438                         else:
439                                 for j, ed in enumerate(edloop.edges):
440                                         if ed.fake:
441                                                 #print "C"
442                                                 edloop.edges = edloop.edges = edloop.edges[j:] + edloop.edges[:j]
443                                                 break
444                 # print "DONE"
445                 ed1, ed2 = eloop1.edges[0], eloop2.edges[0]
446                 
447                 if not ed1.fake or not ed2.fake:
448                         raise "Error"
449                 
450                 # Find the join that isnt flipped (juts like detecting a bow-tie face)
451                 a1 = (ed1.co1 - ed2.co1).length + (ed1.co2 - ed2.co2).length
452                 a2 = (ed1.co1 - ed2.co2).length + (ed1.co2 - ed2.co1).length
453                 
454                 if a1 > a2:
455                         eloop2.reverse()
456                         # make the first edge the start edge still
457                         eloop2.edges.insert(0, eloop2.edges.pop())
458         
459         
460         
461         
462         for loopIdx in range(len(eloop2.edges)):
463                 e1 = eloop1.edges[loopIdx]
464                 e2 = eloop2.edges[loopIdx]
465                 
466                 # Remember the pairs for fan filling culled edges.
467                 e1.match = e2; e2.match = e1
468                 
469                 if not (e1.fake or e2.fake):
470                         new_faces.append([e1.v1, e1.v2, e2.v2, e2.v1])
471         
472         # FAN FILL MISSING FACES.
473         if CULL_FACES:
474                 # Culled edges will be in eloop1.
475                 FAN_FILLED_FACES = 0
476                 
477                 contextEdge = eloop1.edges[0] # The larger of teh 2
478                 while FAN_FILLED_FACES < CULL_FACES:
479                         while contextEdge.next.removed == 0:
480                                 contextEdge = contextEdge.next
481                         
482                         vertFanPivot = contextEdge.match.v2
483                         
484                         while contextEdge.next.removed == 1:
485                                 #if not contextEdge.next.fake:
486                                 new_faces.append([contextEdge.next.v1, contextEdge.next.v2, vertFanPivot])
487                                 
488                                 # Should we use another var?, this will work for now.
489                                 contextEdge.next.removed = 1
490                                 
491                                 contextEdge = contextEdge.next
492                                 FAN_FILLED_FACES += 1
493                 
494                 # may need to fan fill backwards 1 for non closed loops.
495                 
496                 eloop1.restore() # Add culled back into the list.
497         
498         return new_faces
499
500 def main(context):
501         global CULL_METHOD
502         
503         ob = context.object
504         
505         is_editmode = (ob.mode=='EDIT')
506         if is_editmode: bpy.ops.object.mode_set(mode='OBJECT', toggle=False)
507         if ob == None or ob.type != 'MESH':
508                 raise Exception("BPyMessages.Error_NoMeshActive()")
509                 return
510         
511         me = ob.data
512         
513         time1 = time.time()
514         selEdges = getSelectedEdges(context, me, ob)
515         vertLoops = getVertLoops(selEdges, me) # list of lists of edges.
516         if vertLoops == None:
517                 raise Exception('Error%t|Selection includes verts that are a part of more then 1 loop')
518                 if is_editmode: bpy.ops.object.mode_set(mode='EDIT', toggle=False)
519                 return
520         # print len(vertLoops)
521         
522         
523         if len(vertLoops) > 2:
524                 choice = PupMenu('Loft '+str(len(vertLoops))+' edge loops%t|loop|segment')
525                 if choice == -1:
526                         if is_editmode: bpy.ops.object.mode_set(mode='EDIT', toggle=False)
527                         return
528                 
529         elif len(vertLoops) < 2:
530                 raise Exception('Error%t|No Vertloops found!')
531                 if is_editmode: bpy.ops.object.mode_set(mode='EDIT', toggle=False)
532                 return
533         else:
534                 choice = 2
535         
536         
537         # The line below checks if any of the vert loops are differenyt in length.
538         if False in [len(v[0]) == len(vertLoops[0][0]) for v in vertLoops]:
539                 CULL_METHOD = PupMenu('Small to large edge loop distrobution method%t|remove edges evenly|remove smallest edges')
540                 if CULL_METHOD == -1:
541                         if is_editmode: Window.EditMode(1)
542                         return
543                 
544                 if CULL_METHOD ==1: # RESET CULL_METHOD
545                         CULL_METHOD = 0 # shortest
546                 else:
547                         CULL_METHOD = 1 # even
548         
549         
550         time1 = time.time()
551         # Convert to special edge data.
552         edgeLoops = []
553         for vloop, closed in vertLoops:
554                 edgeLoops.append(edgeLoop(vloop, me, closed))
555                 
556         
557         # VERT LOOP ORDERING CODE
558         # "Build a worm" list - grow from Both ends
559         edgeOrderedList = [edgeLoops.pop()]
560         
561         # Find the closest.
562         bestSoFar = BIG_NUM
563         bestIdxSoFar = None
564         for edLoopIdx, edLoop in enumerate(edgeLoops):
565                 l =(edgeOrderedList[-1].centre - edLoop.centre).length 
566                 if l < bestSoFar:
567                         bestIdxSoFar = edLoopIdx
568                         bestSoFar = l
569                         
570         edgeOrderedList.append( edgeLoops.pop(bestIdxSoFar) )
571         
572         # Now we have the 2 closest, append to either end-
573         # Find the closest.
574         while edgeLoops:
575                 bestSoFar = BIG_NUM
576                 bestIdxSoFar = None
577                 first_or_last = 0 # Zero is first
578                 for edLoopIdx, edLoop in enumerate(edgeLoops):
579                         l1 =(edgeOrderedList[-1].centre - edLoop.centre).length 
580                         
581                         if l1 < bestSoFar:
582                                 bestIdxSoFar = edLoopIdx
583                                 bestSoFar = l1
584                                 first_or_last = 1 # last
585                         
586                         l2 =(edgeOrderedList[0].centre - edLoop.centre).length 
587                         if l2 < bestSoFar:
588                                 bestIdxSoFar = edLoopIdx
589                                 bestSoFar = l2
590                                 first_or_last = 0 # last
591                 
592                 if first_or_last: # add closest Last
593                         edgeOrderedList.append( edgeLoops.pop(bestIdxSoFar) )   
594                 else: # Add closest First
595                         edgeOrderedList.insert(0, edgeLoops.pop(bestIdxSoFar) )  # First
596         
597         faces = []
598         
599         for i in range(len(edgeOrderedList)-1):
600                 faces.extend( skin2EdgeLoops(edgeOrderedList[i], edgeOrderedList[i+1], me, ob, 0) )
601         if choice == 1 and len(edgeOrderedList) > 2: # Loop
602                 faces.extend( skin2EdgeLoops(edgeOrderedList[0], edgeOrderedList[-1], me, ob, 0) )
603         
604         # REMOVE SELECTED FACES.
605         MESH_MODE= ob.mode
606         if MESH_MODE == 'EDGE' or MESH_MODE == 'VERTEX': pass
607         elif MESH_MODE == 'FACE':
608                 try: me.faces.delete(1, [ f for f in me.faces if f.sel ])
609                 except: pass
610         
611         if 1: # 2.5
612                 mesh_faces_extend(me, faces, ob.active_material_index)
613                 me.update(calc_edges=True)
614         else:
615                 me.faces.extend(faces, smooth = True)
616         
617         print('\nSkin done in %.4f sec.' % (time.time()-time1))
618                 
619         if is_editmode: bpy.ops.object.mode_set(mode='EDIT', toggle=False)
620
621
622 class MESH_OT_skin(bpy.types.Operator):
623         '''Bridge face loops.'''
624         
625         bl_idname = "mesh.skin"
626         bl_label = "Add Torus"
627         bl_register = True
628         bl_undo = True
629         
630         '''
631         loft_method = EnumProperty(attr="loft_method", items=[(), ()], description="", default= True)
632         
633         '''
634         
635         def execute(self, context):
636                 main(context)
637                 return ('FINISHED',)
638
639
640 # Register the operator
641 bpy.ops.add(MESH_OT_skin)
642
643 # Add to a menu
644 import dynamic_menu
645 menu_item = dynamic_menu.add(bpy.types.VIEW3D_MT_edit_mesh_faces, (lambda self, context: self.layout.itemO("mesh.skin", text="Bridge Faces")) )
646
647 if __name__ == "__main__":
648         bpy.ops.mesh.skin()