adf49b1af7b261a90fab90097e21fd1bfaed7754
[blender.git] / release / scripts / skin.py
1 #!BPY
2
3 """
4 Name: 'Bridge Faces/Edge-Loops'
5 Blender: 237
6 Group: 'Mesh'
7 Tooltip: 'Select 2 vert loops, then run this script.'
8 """
9
10 __author__ = "Campbell Barton AKA Ideasman"
11 __url__ = ["http://members.iinet.net.au/~cpbarton/ideasman/", "blender", "elysiun"]
12 __version__ = "1.0 2004/04/25"
13
14 __bpydoc__ = """\
15 With this script vertex loops can be skinned: faces are created to connect the
16 selected loops of vertices.
17
18 Usage:
19
20 In mesh Edit mode select the vertices of the loops (closed paths / curves of
21 vertices: circles, for example) that should be skinned, then run this script.
22 A pop-up will provide further options, if the results of a method are not adequate try one of the others.
23 """
24
25
26 # $Id$
27 #
28 # -------------------------------------------------------------------------- 
29 # Skin Selected edges 1.0 By Campbell Barton (AKA Ideasman)
30 # -------------------------------------------------------------------------- 
31 # ***** BEGIN GPL LICENSE BLOCK ***** 
32
33 # This program is free software; you can redistribute it and/or 
34 # modify it under the terms of the GNU General Public License 
35 # as published by the Free Software Foundation; either version 2 
36 # of the License, or (at your option) any later version. 
37
38 # This program is distributed in the hope that it will be useful, 
39 # but WITHOUT ANY WARRANTY; without even the implied warranty of 
40 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
41 # GNU General Public License for more details. 
42
43 # You should have received a copy of the GNU General Public License 
44 # along with this program; if not, write to the Free Software Foundation, 
45 # Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA. 
46
47 # ***** END GPL LICENCE BLOCK ***** 
48 # -------------------------------------------------------------------------- 
49
50 # Made by Ideasman/Campbell 2005/06/15 - ideasman@linuxmail.org
51
52 import Blender
53 from Blender import *
54
55 BIG_NUM = 1<<30
56
57 global CULL_METHOD
58 CULL_METHOD = 0
59
60 class edge:
61         def __init__(self, v1,v2):
62                 self.v1 = v1
63                 self.v2 = v2
64                 
65                 # uv1 uv2 vcol1 vcol2 # Add later
66                 self.length = (v1.co - v2.co).length
67                 
68                 self.removed = 0 # Have we been culled from the eloop
69                 self.match = None # The other edge were making a face with
70
71
72 class edgeLoop:
73         def __init__(self, loop): # Vert loop
74                 # Use next and prev, nextDist, prevDist
75                 
76                 # Get Loops centre.
77                 self.centre = Mathutils.Vector()
78                 f = 1.0/len(loop)
79                 for v in loop:
80                         self.centre += v.co * f
81                 
82                 
83                 
84                 
85                 # Convert Vert loop to Edges.
86                 self.edges = []
87                 vIdx = 0
88                 while vIdx < len(loop):
89                         self.edges.append( edge(loop[vIdx-1], loop[vIdx]) )
90                         vIdx += 1
91                 
92                 # Assign linked list
93                 for eIdx in range(len(self.edges)-1):
94                         self.edges[eIdx].next = self.edges[eIdx+1]
95                         self.edges[eIdx].prev = self.edges[eIdx-1]
96                 # Now last
97                 self.edges[-1].next = self.edges[0]
98                 self.edges[-1].prev = self.edges[-2]
99                 
100                 
101                 
102                 # GENERATE AN AVERAGE NORMAL FOR THE WHOLE LOOP.
103                 self.normal = Mathutils.Vector()
104                 for e in self.edges:
105                         n = Mathutils.CrossVecs(self.centre-e.v1.co, self.centre-e.v2.co)
106                         # Do we realy need tot normalize?
107                         n.normalize()
108                         self.normal += n
109                 self.normal.normalize()
110                 
111                 
112                 # Generate a normal for each edge.
113                 for e in self.edges:
114                         
115                         n1 = e.v1.co
116                         n2 = e.v2.co
117                         n3 = e.prev.v1.co
118                         
119                         a = n1-n2
120                         b = n1-n3
121                         normal1 = Mathutils.CrossVecs(a,b)
122                         normal1.normalize()
123                         
124                         n1 = e.v2.co
125                         n3 = e.next.v2.co
126                         n2 = e.v1.co
127                         
128                         a = n1-n2
129                         b = n1-n3
130                         
131                         normal2 = Mathutils.CrossVecs(a,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                 
144         def backup(self):
145                 # Keep a backup of the edges
146                 self.backupEdges = self.edges[:]
147                         
148         def restore(self):
149                 self.edges = self.backupEdges[:]
150                 for e in self.edges:
151                         e.removed = 0
152                 
153         def reverse(self):
154                 self.edges.reverse()
155                 for e in self.edges:
156                         e.normal = -e.normal
157                         e.v1, e.v2 = e.v2, e.v1
158                 self.normal = -self.normal
159         
160         # Removes N Smallest edges and backs up
161         def removeSmallest(self, cullNum, otherLoopLen):
162                 global CULL_METHOD
163                 if CULL_METHOD == 0: # Shortest edge
164                         
165                         eloopCopy = self.edges[:]
166                         eloopCopy.sort(lambda e1, e2: cmp(e1.length, e2.length )) # Length sort, smallest first
167                         eloopCopy = eloopCopy[:cullNum]
168                         for e in eloopCopy:
169                                 e.removed = 1
170                                 self.edges.remove( e ) # Remove from own list, still in linked list.
171                         
172                 else: # CULL METHOD is even
173                                 
174                         culled = 0
175                         
176                         step = int(otherLoopLen / float(cullNum))
177                         
178                         currentEdge = self.edges[0]
179                         while culled < cullNum:
180                                 
181                                 # Get the shortest face in the next STEP
182                                 while currentEdge.removed == 1:
183                                         # Bug here!
184                                         currentEdge = currentEdge.next
185                                 smallestEdge = currentEdge
186                                 
187                                 for i in range(step):
188                                         currentEdge = currentEdge.next
189                                         while currentEdge.removed == 1:
190                                                 currentEdge = currentEdge.next
191                                         if smallestEdge.length > currentEdge.length:
192                                                 smallestEdge = currentEdge
193                                 
194                                 # In that stepping length we have the smallest edge.remove it
195                                 smallestEdge.removed = 1
196                                 self.edges.remove(smallestEdge)
197                                 
198                                 culled+=1
199         
200
201 # Returns face edges.
202 # face must have edge data.
203 def faceEdges(me, f):
204         if len(f) == 3:
205                 return [\
206                  me.findEdge(f[0], f[1]),\
207                  me.findEdge(f[1], f[2]),\
208                  me.findEdge(f[2], f[0])\
209                 ]
210         elif len(f) == 4:
211                 return [\
212                  me.findEdge(f[0], f[1]),\
213                  me.findEdge(f[1], f[2]),\
214                  me.findEdge(f[2], f[3]),\
215                  me.findEdge(f[3], f[0])\
216                 ]
217
218
219 def getSelectedEdges(me, ob):   
220         SEL_FLAG = NMesh.EdgeFlags['SELECT']
221         FGON_FLAG = NMesh.EdgeFlags['FGON']     
222         
223         edges = [e for e in me.edges if e.flag & SEL_FLAG if (e.flag & FGON_FLAG) == 0 ]
224         
225         # Now remove edges that face 2 or more selected faces usoing them
226         edgeFromSelFaces = []
227         for f in me.faces:
228                 if len(f) >2 and f.sel:
229                         edgeFromSelFaces.extend(faceEdges(me, f))
230         
231         # Remove all edges with 2 or more selected faces as uses.
232         for e in edgeFromSelFaces:
233                 if edgeFromSelFaces.count(e) > 1:
234                         me.removeEdge(e.v1, e.v2)
235         
236         # Remove selected faces?
237         fIdx = len(me.faces)
238         while fIdx:
239                 fIdx-=1
240                 if len(me.faces[fIdx]) > 2:
241                         if me.faces[fIdx].sel:
242                                 me.faces.pop(fIdx)
243         return [e for e in edges if edgeFromSelFaces.count(e) < 2]
244         
245         
246 # Like vert loops 
247 def getVertLoops(selEdges):
248         mainVertLoops = []
249         while selEdges:
250                 e = selEdges.pop()
251                 contextVertLoop= [e.v1, e.v2] # start the vert loop
252                 
253                 eIdx = 1 # Get us into the loop. dummy var.
254                 
255                 # if eIdx == 0 then it means we searched and found no matches... 
256                 # time for a new vert loop,
257                 while eIdx:
258                         eIdx = len(selEdges)
259                         while eIdx:
260                                 eIdx-=1
261                                 
262                                 # Check for edge attached at the head of the loop.
263                                 if contextVertLoop[0] == selEdges[eIdx].v1:
264                                         contextVertLoop.insert(0, selEdges.pop(eIdx).v2)
265                                 elif contextVertLoop[0] == selEdges[eIdx].v2:
266                                         contextVertLoop.insert(0, selEdges.pop(eIdx).v1)
267                                         
268                                 # Chech for edge vert at the tail.
269                                 elif contextVertLoop[-1] == selEdges[eIdx].v1:
270                                         contextVertLoop.append(selEdges.pop(eIdx).v2)
271                                 elif contextVertLoop[-1] == selEdges[eIdx].v2:
272                                         contextVertLoop.append(selEdges.pop(eIdx).v1)
273                                 else:
274                                         # None found? Keep looking
275                                         continue
276                                 
277                                 # Once found we.
278                                 break
279                 
280                 # Is this a loop? if so then its forst and last vert must be teh same.
281                 if contextVertLoop[0].index == contextVertLoop[-1].index:
282                         contextVertLoop.pop() # remove double vert
283                         mainVertLoops.append(contextVertLoop)
284                 
285                 # Build context vert loops
286         return mainVertLoops
287
288
289 def skin2EdgeLoops(eloop1, eloop2, me, ob, MODE):
290         # Make sure e1 loops is bigger then e2
291         if len(eloop1.edges) != len(eloop2.edges):
292                 if len(eloop1.edges) < len(eloop2.edges):
293                         eloop1, eloop2 = eloop2, eloop1
294                 
295                 eloop1.backup() # were about to cull faces
296                 CULL_FACES = len(eloop1.edges) - len(eloop2.edges)
297                 eloop1.removeSmallest(CULL_FACES, len(eloop1.edges))
298         else:
299                 CULL_FACES = 0
300         # First make sure poly vert loops are in sync with eachother.
301         
302         # The vector allong which we are skinning.
303         skinVector = eloop1.centre - eloop2.centre
304         
305         loopDist = skinVector.length
306         
307         
308         # IS THE LOOP FLIPPED, IF SO FLIP BACK.
309         angleBetweenLoopNormals = Mathutils.AngleBetweenVecs(eloop1.normal, eloop2.normal)
310         
311         if angleBetweenLoopNormals > 90:
312                 eloop2.reverse()
313         
314         
315         bestEloopDist = BIG_NUM
316         bestOffset = 0
317         # Loop rotation offset to test.1
318         eLoopIdxs = range(len(eloop1.edges))
319         for offset in range(len(eloop1.edges)):
320                 totEloopDist = 0 # Measure this total distance for thsi loop.
321                 
322                 offsetIndexLs = eLoopIdxs[offset:] + eLoopIdxs[:offset] # Make offset index list
323                 
324                 # e1Idx is always from 0 to N, e2Idx is offset.
325                 for e1Idx, e2Idx in enumerate(offsetIndexLs):
326                         # Measure the vloop distance ===============
327                         totEloopDist += ((eloop1.edges[e1Idx].v1.co - eloop2.edges[e2Idx].v1.co).length / loopDist) #/ nangle1
328                         totEloopDist += ((eloop1.edges[e1Idx].v2.co - eloop2.edges[e2Idx].v2.co).length / loopDist) #/ nangle1
329                         
330                         # Premeture break if where no better off
331                         if totEloopDist > bestEloopDist:
332                                 break
333                 
334                 if totEloopDist < bestEloopDist:
335                         bestOffset = offset
336                         bestEloopDist = totEloopDist
337         
338         # Modify V2 LS for Best offset
339         eloop2.edges = eloop2.edges[bestOffset:] + eloop2.edges[:bestOffset]
340         
341         
342         
343         for loopIdx in range(len(eloop2.edges)):
344                 e1 = eloop1.edges[loopIdx]
345                 e2 = eloop2.edges[loopIdx]
346                 
347                 # Remember the pairs for fan filling culled edges.
348                 e1.match = e2; e2.match = e1
349                 
350                 # need some smart face flipping code here.
351                 f = NMesh.Face([e1.v1, e1.v2, e2.v2, e2.v1])
352                 
353                 f.sel = 1
354                 me.faces.append(f)
355         
356         # FAN FILL MISSING FACES.
357         if CULL_FACES:
358                 # Culled edges will be in eloop1.
359                 FAN_FILLED_FACES = 0
360                 
361                 contextEdge = eloop1.edges[0] # The larger of teh 2
362                 while FAN_FILLED_FACES < CULL_FACES:
363                         while contextEdge.next.removed == 0:
364                                 contextEdge = contextEdge.next
365                         
366                         vertFanPivot = contextEdge.match.v2
367                         
368                         while contextEdge.next.removed == 1:
369                                 
370                                 f = NMesh.Face([contextEdge.next.v1, contextEdge.next.v2, vertFanPivot] )
371                                 
372                                 
373                                 f.sel = 1
374                                 me.faces.append(f)
375                                 
376                                 # Should we use another var?, this will work for now.
377                                 contextEdge.next.removed = 1
378                                 
379                                 contextEdge = contextEdge.next
380                                 FAN_FILLED_FACES += 1
381                 
382                 eloop1.restore() # Add culled back into the list.
383         #if angleBetweenLoopNormals > 90:
384         #       eloop2.reverse()
385
386
387 def main():
388         global CULL_METHOD
389         
390         is_editmode = Window.EditMode()
391         if is_editmode: Window.EditMode(0)
392         ob = Scene.GetCurrent().getActiveObject()
393         if ob == None or ob.getType() != 'Mesh':
394                 return
395         
396         me = ob.getData()
397         if not me.edges:
398                 Draw.PupMenu('Error, add edge data first')
399                 if is_editmode: Window.EditMode(1)
400                 return
401         
402         # BAD BLENDER PYTHON API, NEED TO ENTER EXIT EDIT MODE FOR ADDING EDGE DATA.
403         # ADD EDGE DATA HERE, Python API CANT DO IT YET, LOOSES SELECTION
404         
405         selEdges = getSelectedEdges(me, ob)
406         vertLoops = getVertLoops(selEdges) # list of lists of edges.
407         
408         if len(vertLoops) > 2:
409                 choice = Draw.PupMenu('Loft '+str(len(vertLoops))+' edge loops%t|loop|segment')
410                 if choice == -1:
411                         if is_editmode: Window.EditMode(1)
412                         return
413         elif len(vertLoops) < 2:
414                 Draw.PupMenu('Error, No Vertloops found%t|if you have a valid selection, go in and out of face edit mode to update the selection state.')
415                 if is_editmode: Window.EditMode(1)      
416                 return
417         else:
418                 choice = 2
419         
420         
421         # The line below checks if any of the vert loops are differenyt in length.
422         if False in [len(v) == len(vertLoops[0]) for v in vertLoops]:
423                 CULL_METHOD = Draw.PupMenu('Small to large edge loop distrobution method%t|remove edges evenly|remove smallest edges edges')
424                 if CULL_METHOD == -1:
425                         if is_editmode: Window.EditMode(1)
426                         return
427                 
428                 if CULL_METHOD ==1: # RESET CULL_METHOD
429                         CULL_METHOD = 0 # shortest
430                 else:
431                         CULL_METHOD = 1 # even
432         
433         
434         time1 = sys.time()
435         # Convert to special edge data.
436         edgeLoops = []
437         for vloop in vertLoops:
438                 edgeLoops.append(edgeLoop(vloop))
439                 
440         
441         # VERT LOOP ORDERING CODE
442         # Build a worm list - grow from Both ends
443         edgeOrderedList = [edgeLoops.pop()]
444         
445         # Find the closest.
446         bestSoFar = BIG_NUM
447         bestIdxSoFar = None
448         for edLoopIdx, edLoop in enumerate(edgeLoops):
449                 l =(edgeOrderedList[-1].centre - edLoop.centre).length 
450                 if l < bestSoFar:
451                         bestIdxSoFar = edLoopIdx
452                         bestSoFar = l
453                         
454         edgeOrderedList.append( edgeLoops.pop(bestIdxSoFar) )
455         
456         # Now we have the 2 closest, append to either end-
457         # Find the closest.
458         while edgeLoops:
459                 bestSoFar = BIG_NUM
460                 bestIdxSoFar = None
461                 first_or_last = 0 # Zero is first
462                 for edLoopIdx, edLoop in enumerate(edgeLoops):
463                         l1 =(edgeOrderedList[-1].centre - edLoop.centre).length 
464                         
465                         if l1 < bestSoFar:
466                                 bestIdxSoFar = edLoopIdx
467                                 bestSoFar = l1
468                                 first_or_last = 1 # last
469                         
470                         l2 =(edgeOrderedList[0].centre - edLoop.centre).length 
471                         if l2 < bestSoFar:
472                                 bestIdxSoFar = edLoopIdx
473                                 bestSoFar = l2
474                                 first_or_last = 0 # last
475                 
476                 if first_or_last: # add closest Last
477                         edgeOrderedList.append( edgeLoops.pop(bestIdxSoFar) )   
478                 else: # Add closest First
479                         edgeOrderedList.insert(0, edgeLoops.pop(bestIdxSoFar) )  # First
480         
481         for i in range(len(edgeOrderedList)-1):
482                 skin2EdgeLoops(edgeOrderedList[i], edgeOrderedList[i+1], me, ob, 0)     
483         if choice == 1 and len(edgeOrderedList) > 2: # Loop
484                 skin2EdgeLoops(edgeOrderedList[0], edgeOrderedList[-1], me, ob, 0)      
485         
486         me.update(1, 1, 0)
487         if is_editmode: Window.EditMode(1)
488
489 main()