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