fix BGE bug #8668: Behavior of os.getcwd() is not consistent between operating systems
[blender-staging.git] / release / scripts / uvcalc_smart_project.py
1 #!BPY
2
3 """ Registration info for Blender menus: <- these words are ignored
4 Name: 'Unwrap (smart projections)'
5 Blender: 240
6 Group: 'UVCalculation'
7 Tooltip: 'UV Unwrap mesh faces for all select mesh objects'
8 """
9
10
11 __author__ = "Campbell Barton"
12 __url__ = ("blender", "blenderartists.org")
13 __version__ = "1.1 12/18/05"
14
15 __bpydoc__ = """\
16 This script projection unwraps the selected faces of a mesh.
17
18 it operates on all selected mesh objects, and can be used unwrap
19 selected faces, or all faces.
20 """
21
22 # -------------------------------------------------------------------------- 
23 # Smart Projection UV Projection Unwrapper v1.1 by Campbell Barton (AKA Ideasman) 
24 # -------------------------------------------------------------------------- 
25 # ***** BEGIN GPL LICENSE BLOCK ***** 
26
27 # This program is free software; you can redistribute it and/or 
28 # modify it under the terms of the GNU General Public License 
29 # as published by the Free Software Foundation; either version 2 
30 # of the License, or (at your option) any later version. 
31
32 # This program is distributed in the hope that it will be useful, 
33 # but WITHOUT ANY WARRANTY; without even the implied warranty of 
34 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
35 # GNU General Public License for more details. 
36
37 # You should have received a copy of the GNU General Public License 
38 # along with this program; if not, write to the Free Software Foundation, 
39 # Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA. 
40
41 # ***** END GPL LICENCE BLOCK ***** 
42 # -------------------------------------------------------------------------- 
43
44
45 from Blender import Object, Draw, Window, sys, Mesh, Geometry
46 from Blender.Mathutils import CrossVecs, Matrix, Vector, RotationMatrix, DotVecs
47 import bpy
48 from math import cos
49
50 DEG_TO_RAD = 0.017453292519943295 # pi/180.0
51 SMALL_NUM = 0.000000001
52 BIG_NUM = 1e15
53
54 global USER_FILL_HOLES
55 global USER_FILL_HOLES_QUALITY
56 USER_FILL_HOLES = None
57 USER_FILL_HOLES_QUALITY = None
58
59 dict_matrix = {}
60
61 def pointInTri2D(v, v1, v2, v3):
62         global dict_matrix
63         
64         key = v1.x, v1.y, v2.x, v2.y, v3.x, v3.y
65         
66         # Commented because its slower to do teh bounds check, we should realy cache the bounds info for each face.
67         '''
68         # BOUNDS CHECK
69         xmin= 1000000
70         ymin= 1000000
71         
72         xmax= -1000000
73         ymax= -1000000
74         
75         for i in (0,2,4):
76                 x= key[i]
77                 y= key[i+1]
78                 
79                 if xmax<x:      xmax= x
80                 if ymax<y:      ymax= y
81                 if xmin>x:      xmin= x
82                 if ymin>y:      ymin= y 
83         
84         x= v.x
85         y= v.y
86         
87         if x<xmin or x>xmax or y < ymin or y > ymax:
88                 return False
89         # Done with bounds check
90         '''
91         try:
92                 mtx = dict_matrix[key]
93                 if not mtx:
94                         return False
95         except:
96                 side1 = v2 - v1
97                 side2 = v3 - v1
98                 
99                 nor = CrossVecs(side1, side2)
100                 
101                 l1 = [side1[0], side1[1], side1[2]]
102                 l2 = [side2[0], side2[1], side2[2]]
103                 l3 = [nor[0], nor[1], nor[2]]
104                 
105                 mtx = Matrix(l1, l2, l3)
106                 
107                 # Zero area 2d tri, even tho we throw away zerop area faces
108                 # the projection UV can result in a zero area UV.
109                 if not mtx.determinant():
110                         dict_matrix[key] = None
111                         return False
112                 
113                 mtx.invert()
114                 
115                 dict_matrix[key] = mtx
116         
117         uvw = (v - v1) * mtx
118         return 0 <= uvw[0] and 0 <= uvw[1] and uvw[0] + uvw[1] <= 1
119
120         
121 def boundsIsland(faces):
122         minx = maxx = faces[0].uv[0][0] # Set initial bounds.
123         miny = maxy = faces[0].uv[0][1]
124         # print len(faces), minx, maxx, miny , maxy
125         for f in faces:
126                 for uv in f.uv:
127                         x= uv.x
128                         y= uv.y
129                         if x<minx: minx= x
130                         if y<miny: miny= y
131                         if x>maxx: maxx= x
132                         if y>maxy: maxy= y
133         
134         return minx, miny, maxx, maxy
135
136 """
137 def boundsEdgeLoop(edges):
138         minx = maxx = edges[0][0] # Set initial bounds.
139         miny = maxy = edges[0][1]
140         # print len(faces), minx, maxx, miny , maxy
141         for ed in edges:
142                 for pt in ed:
143                         print 'ass'
144                         x= pt[0]
145                         y= pt[1]
146                         if x<minx: x= minx
147                         if y<miny: y= miny
148                         if x>maxx: x= maxx
149                         if y>maxy: y= maxy
150         
151         return minx, miny, maxx, maxy
152 """
153
154 # Turns the islands into a list of unpordered edges (Non internal)
155 # Onlt for UV's
156 # only returns outline edges for intersection tests. and unique points.
157
158 def island2Edge(island):
159         
160         # Vert index edges
161         edges = {}
162         
163         unique_points= {}
164         
165         for f in island:
166                 f_uvkey= map(tuple, f.uv)
167                 
168                 
169                 for vIdx, edkey in enumerate(f.edge_keys):
170                         unique_points[f_uvkey[vIdx]] = f.uv[vIdx]
171                         
172                         if f.v[vIdx].index > f.v[vIdx-1].index:
173                                 i1= vIdx-1;     i2= vIdx
174                         else:           
175                                 i1= vIdx;       i2= vIdx-1
176                         
177                         try:    edges[ f_uvkey[i1], f_uvkey[i2] ] *= 0 # sets eny edge with more then 1 user to 0 are not returned.
178                         except: edges[ f_uvkey[i1], f_uvkey[i2] ] = (f.uv[i1] - f.uv[i2]).length, 
179         
180         # If 2 are the same then they will be together, but full [a,b] order is not correct.
181         
182         # Sort by length
183         
184                 
185         length_sorted_edges = [(Vector(key[0]), Vector(key[1]), value) for key, value in edges.iteritems() if value != 0]
186         
187         try:    length_sorted_edges.sort(key = lambda A: -A[2]) # largest first
188         except: length_sorted_edges.sort(lambda A, B: cmp(B[2], A[2]))
189         
190         # Its okay to leave the length in there.
191         #for e in length_sorted_edges:
192         #       e.pop(2)
193         
194         # return edges and unique points
195         return length_sorted_edges, [v.__copy__().resize3D() for v in unique_points.itervalues()]
196         
197 # ========================= NOT WORKING????
198 # Find if a points inside an edge loop, un-orderd.
199 # pt is and x/y
200 # edges are a non ordered loop of edges.
201 # #offsets are the edge x and y offset.
202 """
203 def pointInEdges(pt, edges):
204         #
205         x1 = pt[0] 
206         y1 = pt[1]
207         
208         # Point to the left of this line.
209         x2 = -100000
210         y2 = -10000
211         intersectCount = 0
212         for ed in edges:
213                 xi, yi = lineIntersection2D(x1,y1, x2,y2, ed[0][0], ed[0][1], ed[1][0], ed[1][1])
214                 if xi != None: # Is there an intersection.
215                         intersectCount+=1
216         
217         return intersectCount % 2
218 """
219
220 def pointInIsland(pt, island):
221         vec1 = Vector(); vec2 = Vector(); vec3 = Vector()       
222         for f in island:
223                 vec1.x, vec1.y = f.uv[0]
224                 vec2.x, vec2.y = f.uv[1]
225                 vec3.x, vec3.y = f.uv[2]
226
227                 if pointInTri2D(pt, vec1, vec2, vec3):
228                         return True
229                 
230                 if len(f.v) == 4:
231                         vec1.x, vec1.y = f.uv[0]
232                         vec2.x, vec2.y = f.uv[2]
233                         vec3.x, vec3.y = f.uv[3]                        
234                         if pointInTri2D(pt, vec1, vec2, vec3):
235                                 return True
236         return False
237
238
239 # box is (left,bottom, right, top)
240 def islandIntersectUvIsland(source, target, SourceOffset):
241         # Is 1 point in the box, inside the vertLoops
242         edgeLoopsSource = source[6] # Pretend this is offset
243         edgeLoopsTarget = target[6]
244         
245         # Edge intersect test   
246         for ed in edgeLoopsSource:
247                 for seg in edgeLoopsTarget:
248                         i = Geometry.LineIntersect2D(\
249                         seg[0], seg[1], SourceOffset+ed[0], SourceOffset+ed[1])
250                         if i:
251                                 return 1 # LINE INTERSECTION
252         
253         # 1 test for source being totally inside target
254         SourceOffset.resize3D()
255         for pv in source[7]:
256                 if pointInIsland(pv+SourceOffset, target[0]):
257                         return 2 # SOURCE INSIDE TARGET
258         
259         # 2 test for a part of the target being totaly inside the source.
260         for pv in target[7]:
261                 if pointInIsland(pv-SourceOffset, source[0]):
262                         return 3 # PART OF TARGET INSIDE SOURCE.
263
264         return 0 # NO INTERSECTION
265
266
267
268
269 # Returns the X/y Bounds of a list of vectors.
270 def testNewVecLs2DRotIsBetter(vecs, mat=-1, bestAreaSoFar = -1):
271         
272         # UV's will never extend this far.
273         minx = miny = BIG_NUM
274         maxx = maxy = -BIG_NUM
275         
276         for i, v in enumerate(vecs):
277                 
278                 # Do this allong the way
279                 if mat != -1:
280                         v = vecs[i] = v*mat
281                         x= v.x
282                         y= v.y
283                         if x<minx: minx= x
284                         if y<miny: miny= y
285                         if x>maxx: maxx= x
286                         if y>maxy: maxy= y
287                 
288                 # Spesific to this algo, bail out if we get bigger then the current area
289                 if bestAreaSoFar != -1 and (maxx-minx) * (maxy-miny) > bestAreaSoFar:
290                         return (BIG_NUM, None), None
291         w = maxx-minx
292         h = maxy-miny
293         return (w*h, w,h), vecs # Area, vecs
294         
295 # Takes a list of faces that make up a UV island and rotate
296 # until they optimally fit inside a square.
297 ROTMAT_2D_POS_90D = RotationMatrix( 90, 2)
298 ROTMAT_2D_POS_45D = RotationMatrix( 45, 2)
299
300 RotMatStepRotation = []
301 rot_angle = 22.5 #45.0/2
302 while rot_angle > 0.1:
303         RotMatStepRotation.append([\
304          RotationMatrix( rot_angle, 2),\
305          RotationMatrix( -rot_angle, 2)])
306         
307         rot_angle = rot_angle/2.0
308         
309
310 def optiRotateUvIsland(faces):
311         global currentArea
312         
313         # Bestfit Rotation
314         def best2dRotation(uvVecs, MAT1, MAT2):
315                 global currentArea
316                 
317                 newAreaPos, newfaceProjectionGroupListPos =\
318                 testNewVecLs2DRotIsBetter(uvVecs[:], MAT1, currentArea[0])
319                 
320                 
321                 # Why do I use newpos here? May as well give the best area to date for an early bailout
322                 # some slight speed increase in this.
323                 # If the new rotation is smaller then the existing, we can 
324                 # avoid copying a list and overwrite the old, crappy one.
325                 
326                 if newAreaPos[0] < currentArea[0]:
327                         newAreaNeg, newfaceProjectionGroupListNeg =\
328                         testNewVecLs2DRotIsBetter(uvVecs, MAT2, newAreaPos[0])  # Reuse the old bigger list.
329                 else:
330                         newAreaNeg, newfaceProjectionGroupListNeg =\
331                         testNewVecLs2DRotIsBetter(uvVecs[:], MAT2, currentArea[0])  # Cant reuse, make a copy.
332                 
333                 
334                 # Now from the 3 options we need to discover which to use
335                 # we have cerrentArea/newAreaPos/newAreaNeg
336                 bestArea = min(currentArea[0], newAreaPos[0], newAreaNeg[0])
337                 
338                 if currentArea[0] == bestArea:
339                         return uvVecs
340                 elif newAreaPos[0] == bestArea:
341                         uvVecs = newfaceProjectionGroupListPos
342                         currentArea = newAreaPos                
343                 elif newAreaNeg[0] == bestArea:
344                         uvVecs = newfaceProjectionGroupListNeg
345                         currentArea = newAreaNeg
346                 
347                 return uvVecs
348                 
349         
350         # Serialized UV coords to Vectors
351         uvVecs = [uv for f in faces  for uv in f.uv]
352         
353         # Theres a small enough number of these to hard code it
354         # rather then a loop.
355         
356         # Will not modify anything
357         currentArea, dummy =\
358         testNewVecLs2DRotIsBetter(uvVecs)
359         
360         
361         # Try a 45d rotation
362         newAreaPos, newfaceProjectionGroupListPos = testNewVecLs2DRotIsBetter(uvVecs[:], ROTMAT_2D_POS_45D, currentArea[0])
363         
364         if newAreaPos[0] < currentArea[0]:
365                 uvVecs = newfaceProjectionGroupListPos
366                 currentArea = newAreaPos
367         # 45d done
368         
369         # Testcase different rotations and find the onfe that best fits in a square
370         for ROTMAT in RotMatStepRotation:
371                 uvVecs = best2dRotation(uvVecs, ROTMAT[0], ROTMAT[1])
372         
373         # Only if you want it, make faces verticle!
374         if currentArea[1] > currentArea[2]:
375                 # Rotate 90d
376                 # Work directly on the list, no need to return a value.
377                 testNewVecLs2DRotIsBetter(uvVecs, ROTMAT_2D_POS_90D)
378         
379         
380         # Now write the vectors back to the face UV's
381         i = 0 # count the serialized uv/vectors
382         for f in faces:
383                 #f.uv = [uv for uv in uvVecs[i:len(f)+i] ]
384                 for j, k in enumerate(xrange(i, len(f.v)+i)):
385                         f.uv[j][:] = uvVecs[k]
386                 i += len(f.v)
387
388
389 # Takes an island list and tries to find concave, hollow areas to pack smaller islands into.
390 def mergeUvIslands(islandList):
391         global USER_FILL_HOLES
392         global USER_FILL_HOLES_QUALITY
393         
394         
395         # Pack islands to bottom LHS
396         # Sync with island
397         
398         #islandTotFaceArea = [] # A list of floats, each island area
399         #islandArea = [] # a list of tuples ( area, w,h)
400         
401         
402         decoratedIslandList = []
403         
404         islandIdx = len(islandList)
405         while islandIdx:
406                 islandIdx-=1
407                 minx, miny, maxx, maxy = boundsIsland(islandList[islandIdx])
408                 w, h = maxx-minx, maxy-miny
409                 
410                 totFaceArea = 0
411                 offset= Vector(minx, miny)
412                 for f in islandList[islandIdx]:
413                         for uv in f.uv:
414                                 uv -= offset
415                         
416                         totFaceArea += f.area
417                 
418                 islandBoundsArea = w*h
419                 efficiency = abs(islandBoundsArea - totFaceArea)
420                 
421                 # UV Edge list used for intersections as well as unique points.
422                 edges, uniqueEdgePoints = island2Edge(islandList[islandIdx])
423                 
424                 decoratedIslandList.append([islandList[islandIdx], totFaceArea, efficiency, islandBoundsArea, w,h, edges, uniqueEdgePoints]) 
425                 
426         
427         # Sort by island bounding box area, smallest face area first.
428         # no.. chance that to most simple edge loop first.
429         decoratedIslandListAreaSort =decoratedIslandList[:]
430         
431         try:    decoratedIslandListAreaSort.sort(key = lambda A: A[3])
432         except: decoratedIslandListAreaSort.sort(lambda A, B: cmp(A[3], B[3]))
433         
434         
435         # sort by efficiency, Least Efficient first.
436         decoratedIslandListEfficSort = decoratedIslandList[:]
437         # decoratedIslandListEfficSort.sort(lambda A, B: cmp(B[2], A[2]))
438
439         try:    decoratedIslandListEfficSort.sort(key = lambda A: -A[2])
440         except: decoratedIslandListEfficSort.sort(lambda A, B: cmp(B[2], A[2]))
441
442         # ================================================== THESE CAN BE TWEAKED.
443         # This is a quality value for the number of tests.
444         # from 1 to 4, generic quality value is from 1 to 100
445         USER_STEP_QUALITY =   ((USER_FILL_HOLES_QUALITY - 1) / 25.0) + 1
446         
447         # If 100 will test as long as there is enough free space.
448         # this is rarely enough, and testing takes a while, so lower quality speeds this up.
449         
450         # 1 means they have the same quality 
451         USER_FREE_SPACE_TO_TEST_QUALITY = 1 + (((100 - USER_FILL_HOLES_QUALITY)/100.0) *5)
452         
453         #print 'USER_STEP_QUALITY', USER_STEP_QUALITY
454         #print 'USER_FREE_SPACE_TO_TEST_QUALITY', USER_FREE_SPACE_TO_TEST_QUALITY
455         
456         removedCount = 0
457         
458         areaIslandIdx = 0
459         ctrl = Window.Qual.CTRL
460         BREAK= False
461         while areaIslandIdx < len(decoratedIslandListAreaSort) and not BREAK:
462                 sourceIsland = decoratedIslandListAreaSort[areaIslandIdx]
463                 # Alredy packed?
464                 if not sourceIsland[0]:
465                         areaIslandIdx+=1
466                 else:
467                         efficIslandIdx = 0
468                         while efficIslandIdx < len(decoratedIslandListEfficSort) and not BREAK:
469                                 
470                                 if Window.GetKeyQualifiers() & ctrl:
471                                         BREAK= True
472                                         break
473                                 
474                                 # Now we have 2 islands, is the efficience of the islands lowers theres an
475                                 # increasing likely hood that we can fit merge into the bigger UV island.
476                                 # this ensures a tight fit.
477                                 
478                                 # Just use figures we have about user/unused area to see if they might fit.
479                                 
480                                 targetIsland = decoratedIslandListEfficSort[efficIslandIdx]
481                                 
482                                 
483                                 if sourceIsland[0] == targetIsland[0] or\
484                                 not targetIsland[0] or\
485                                 not sourceIsland[0]:
486                                         pass
487                                 else:
488                                         
489                                         # ([island, totFaceArea, efficiency, islandArea, w,h])
490                                         # Waisted space on target is greater then UV bounding island area.
491                                         
492                                         
493                                         # if targetIsland[3] > (sourceIsland[2]) and\ #
494                                         # print USER_FREE_SPACE_TO_TEST_QUALITY, 'ass'
495                                         if targetIsland[2] > (sourceIsland[1] * USER_FREE_SPACE_TO_TEST_QUALITY) and\
496                                         targetIsland[4] > sourceIsland[4] and\
497                                         targetIsland[5] > sourceIsland[5]:
498                                                 
499                                                 # DEBUG # print '%.10f  %.10f' % (targetIsland[3], sourceIsland[1])
500                                                 
501                                                 # These enough spare space lets move the box until it fits
502                                                 
503                                                 # How many times does the source fit into the target x/y
504                                                 blockTestXUnit = targetIsland[4]/sourceIsland[4]
505                                                 blockTestYUnit = targetIsland[5]/sourceIsland[5]
506                                                 
507                                                 boxLeft = 0
508                                                 
509                                                 
510                                                 # Distllllance we can move between whilst staying inside the targets bounds.
511                                                 testWidth = targetIsland[4] - sourceIsland[4]
512                                                 testHeight = targetIsland[5] - sourceIsland[5]
513                                                 
514                                                 # Increment we move each test. x/y
515                                                 xIncrement = (testWidth / (blockTestXUnit * ((USER_STEP_QUALITY/50)+0.1)))
516                                                 yIncrement = (testHeight / (blockTestYUnit * ((USER_STEP_QUALITY/50)+0.1)))
517
518                                                 # Make sure were not moving less then a 3rg of our width/height
519                                                 if xIncrement<sourceIsland[4]/3:
520                                                         xIncrement= sourceIsland[4]
521                                                 if yIncrement<sourceIsland[5]/3:
522                                                         yIncrement= sourceIsland[5]
523                                                 
524                                                 
525                                                 boxLeft = 0 # Start 1 back so we can jump into the loop.
526                                                 boxBottom= 0 #-yIncrement
527                                                 
528                                                 ##testcount= 0
529                                                 
530                                                 while boxBottom <= testHeight:
531                                                         # Should we use this? - not needed for now.
532                                                         #if Window.GetKeyQualifiers() & ctrl:
533                                                         #       BREAK= True
534                                                         #       break
535                                                         
536                                                         ##testcount+=1
537                                                         #print 'Testing intersect'
538                                                         Intersect = islandIntersectUvIsland(sourceIsland, targetIsland, Vector(boxLeft, boxBottom))
539                                                         #print 'Done', Intersect
540                                                         if Intersect == 1:  # Line intersect, dont bother with this any more
541                                                                 pass
542                                                         
543                                                         if Intersect == 2:  # Source inside target
544                                                                 '''
545                                                                 We have an intersection, if we are inside the target 
546                                                                 then move us 1 whole width accross,
547                                                                 Its possible this is a bad idea since 2 skinny Angular faces
548                                                                 could join without 1 whole move, but its a lot more optimal to speed this up
549                                                                 since we have alredy tested for it.
550                                                                 
551                                                                 It gives about 10% speedup with minimal errors.
552                                                                 '''
553                                                                 #print 'ass'
554                                                                 # Move the test allong its width + SMALL_NUM
555                                                                 #boxLeft += sourceIsland[4] + SMALL_NUM
556                                                                 boxLeft += sourceIsland[4]
557                                                         elif Intersect == 0: # No intersection?? Place it.
558                                                                 # Progress
559                                                                 removedCount +=1
560                                                                 Window.DrawProgressBar(0.0, 'Merged: %i islands, Ctrl to finish early.' % removedCount)
561                                                                 
562                                                                 # Move faces into new island and offset
563                                                                 targetIsland[0].extend(sourceIsland[0])
564                                                                 offset= Vector(boxLeft, boxBottom)
565                                                                 
566                                                                 for f in sourceIsland[0]:
567                                                                         for uv in f.uv:
568                                                                                 uv+= offset
569                                                                 
570                                                                 sourceIsland[0][:] = [] # Empty
571                                                                 
572
573                                                                 # Move edge loop into new and offset.
574                                                                 # targetIsland[6].extend(sourceIsland[6])
575                                                                 #while sourceIsland[6]:
576                                                                 targetIsland[6].extend( [ (\
577                                                                          (e[0]+offset, e[1]+offset, e[2])\
578                                                                 ) for e in sourceIsland[6] ] )
579                                                                 
580                                                                 sourceIsland[6][:] = [] # Empty
581                                                                 
582                                                                 # Sort by edge length, reverse so biggest are first.
583                                                                 
584                                                                 try:    targetIsland[6].sort(key = lambda A: A[2])
585                                                                 except: targetIsland[6].sort(lambda B,A: cmp(A[2], B[2] ))
586                                                                 
587                                                                 
588                                                                 targetIsland[7].extend(sourceIsland[7])
589                                                                 offset= Vector(boxLeft, boxBottom, 0)
590                                                                 for p in sourceIsland[7]:
591                                                                         p+= offset
592                                                                 
593                                                                 sourceIsland[7][:] = []
594                                                                 
595                                                                 
596                                                                 # Decrement the efficiency
597                                                                 targetIsland[1]+=sourceIsland[1] # Increment totFaceArea
598                                                                 targetIsland[2]-=sourceIsland[1] # Decrement efficiency
599                                                                 # IF we ever used these again, should set to 0, eg
600                                                                 sourceIsland[2] = 0 # No area if anyone wants to know
601                                                                 
602                                                                 break
603                                                         
604                                                         
605                                                         # INCREMENR NEXT LOCATION
606                                                         if boxLeft > testWidth:
607                                                                 boxBottom += yIncrement
608                                                                 boxLeft = 0.0
609                                                         else:
610                                                                 boxLeft += xIncrement
611                                                 ##print testcount
612                                 
613                                 efficIslandIdx+=1
614                 areaIslandIdx+=1
615         
616         # Remove empty islands
617         i = len(islandList)
618         while i:
619                 i-=1
620                 if not islandList[i]:
621                         del islandList[i] # Can increment islands removed here.
622
623 # Takes groups of faces. assumes face groups are UV groups.
624 def getUvIslands(faceGroups, me):
625         
626         # Get seams so we dont cross over seams
627         edge_seams = {} # shoudl be a set
628         SEAM = Mesh.EdgeFlags.SEAM
629         for ed in me.edges:
630                 if ed.flag & SEAM:
631                         edge_seams[ed.key] = None # dummy var- use sets!                        
632         # Done finding seams
633         
634         
635         islandList = []
636         
637         Window.DrawProgressBar(0.0, 'Splitting %d projection groups into UV islands:' % len(faceGroups))
638         #print '\tSplitting %d projection groups into UV islands:' % len(faceGroups),
639         # Find grouped faces
640         
641         faceGroupIdx = len(faceGroups)
642         
643         while faceGroupIdx:
644                 faceGroupIdx-=1
645                 faces = faceGroups[faceGroupIdx]
646                 
647                 if not faces:
648                         continue
649                 
650                 # Build edge dict
651                 edge_users = {}
652                 
653                 for i, f in enumerate(faces):
654                         for ed_key in f.edge_keys:
655                                 if edge_seams.has_key(ed_key): # DELIMIT SEAMS! ;)
656                                         edge_users[ed_key] = [] # so as not to raise an error
657                                 else:
658                                         try:            edge_users[ed_key].append(i)
659                                         except:         edge_users[ed_key] = [i]
660                 
661                 # Modes
662                 # 0 - face not yet touched.
663                 # 1 - added to island list, and need to search
664                 # 2 - touched and searched - dont touch again.
665                 face_modes = [0] * len(faces) # initialize zero - untested.
666                 
667                 face_modes[0] = 1 # start the search with face 1
668                 
669                 newIsland = []
670                 
671                 newIsland.append(faces[0])
672                 
673                 
674                 ok = True
675                 while ok:
676                         
677                         ok = True
678                         while ok:
679                                 ok= False
680                                 for i in xrange(len(faces)):
681                                         if face_modes[i] == 1: # search
682                                                 for ed_key in faces[i].edge_keys:
683                                                         for ii in edge_users[ed_key]:
684                                                                 if i != ii and face_modes[ii] == 0:
685                                                                         face_modes[ii] = ok = 1 # mark as searched
686                                                                         newIsland.append(faces[ii])
687                                                                 
688                                                 # mark as searched, dont look again.
689                                                 face_modes[i] = 2
690                         
691                         islandList.append(newIsland)
692                         
693                         ok = False
694                         for i in xrange(len(faces)):
695                                 if face_modes[i] == 0:
696                                         newIsland = []
697                                         newIsland.append(faces[i])
698                                         
699                                         face_modes[i] = ok = 1
700                                         break
701                         # if not ok will stop looping
702         
703         Window.DrawProgressBar(0.1, 'Optimizing Rotation for %i UV Islands' % len(islandList))
704         
705         for island in islandList:
706                 optiRotateUvIsland(island)
707         
708         return islandList
709         
710
711 def packIslands(islandList):
712         if USER_FILL_HOLES:
713                 Window.DrawProgressBar(0.1, 'Merging Islands (Ctrl: skip merge)...')
714                 mergeUvIslands(islandList) # Modify in place
715                 
716         
717         # Now we have UV islands, we need to pack them.
718         
719         # Make a synchronised list with the islands
720         # so we can box pak the islands.
721         packBoxes = []
722         
723         # Keep a list of X/Y offset so we can save time by writing the 
724         # uv's and packed data in one pass.
725         islandOffsetList = [] 
726         
727         islandIdx = 0
728         
729         while islandIdx < len(islandList):
730                 minx, miny, maxx, maxy = boundsIsland(islandList[islandIdx])
731                 
732                 w, h = maxx-minx, maxy-miny
733                 
734                 if USER_ISLAND_MARGIN:
735                         minx -= USER_ISLAND_MARGIN# *w
736                         miny -= USER_ISLAND_MARGIN# *h
737                         maxx += USER_ISLAND_MARGIN# *w
738                         maxy += USER_ISLAND_MARGIN# *h
739                 
740                         # recalc width and height
741                         w, h = maxx-minx, maxy-miny
742                 
743                 if w < 0.00001 or h < 0.00001:
744                         del islandList[islandIdx]
745                         islandIdx -=1
746                         continue
747                 
748                 '''Save the offset to be applied later,
749                 we could apply to the UVs now and allign them to the bottom left hand area
750                 of the UV coords like the box packer imagines they are
751                 but, its quicker just to remember their offset and
752                 apply the packing and offset in 1 pass '''
753                 islandOffsetList.append((minx, miny))
754                 
755                 # Add to boxList. use the island idx for the BOX id.
756                 packBoxes.append([0, 0, w, h])
757                 islandIdx+=1
758         
759         # Now we have a list of boxes to pack that syncs
760         # with the islands.
761         
762         #print '\tPacking UV Islands...'
763         Window.DrawProgressBar(0.7, 'Packing %i UV Islands...' % len(packBoxes) )
764         
765         time1 = sys.time()
766         packWidth, packHeight = Geometry.BoxPack2D(packBoxes)
767         
768         # print 'Box Packing Time:', sys.time() - time1
769         
770         #if len(pa      ckedLs) != len(islandList):
771         #       raise "Error packed boxes differes from original length"
772         
773         #print '\tWriting Packed Data to faces'
774         Window.DrawProgressBar(0.8, 'Writing Packed Data to faces')
775         
776         # Sort by ID, so there in sync again
777         islandIdx = len(islandList)
778         # Having these here avoids devide by 0
779         if islandIdx:
780                 
781                 if USER_STRETCH_ASPECT:
782                         # Maximize to uv area?? Will write a normalize function.
783                         xfactor = 1.0 / packWidth
784                         yfactor = 1.0 / packHeight      
785                 else:
786                         # Keep proportions.
787                         xfactor = yfactor = 1.0 / max(packWidth, packHeight)
788         
789         while islandIdx:
790                 islandIdx -=1
791                 # Write the packed values to the UV's
792                 
793                 xoffset = packBoxes[islandIdx][0] - islandOffsetList[islandIdx][0]
794                 yoffset = packBoxes[islandIdx][1] - islandOffsetList[islandIdx][1]
795                 
796                 for f in islandList[islandIdx]: # Offsetting the UV's so they fit in there packed box
797                         for uv in f.uv:
798                                 uv.x= (uv.x+xoffset) * xfactor
799                                 uv.y= (uv.y+yoffset) * yfactor
800                         
801                         
802
803 def VectoMat(vec):
804         a3 = vec.__copy__().normalize()
805         
806         up = Vector(0,0,1)
807         if abs(DotVecs(a3, up)) == 1.0:
808                 up = Vector(0,1,0)
809         
810         a1 = CrossVecs(a3, up).normalize()
811         a2 = CrossVecs(a3, a1)
812         return Matrix([a1[0], a1[1], a1[2]], [a2[0], a2[1], a2[2]], [a3[0], a3[1], a3[2]])
813
814
815
816 class thickface(object):
817         __slost__= 'v', 'uv', 'no', 'area', 'edge_keys'
818         def __init__(self, face):
819                 self.v = face.v
820                 self.uv = face.uv
821                 self.no = face.no
822                 self.area = face.area
823                 self.edge_keys = face.edge_keys
824
825 global ob
826 ob = None
827 def main():
828         global USER_FILL_HOLES
829         global USER_FILL_HOLES_QUALITY
830         global USER_STRETCH_ASPECT
831         global USER_ISLAND_MARGIN
832         
833         objects= bpy.data.scenes.active.objects
834         
835         # we can will tag them later.
836         obList =  [ob for ob in objects.context if ob.type == 'Mesh']
837         
838         # Face select object may not be selected.
839         ob = objects.active
840         if ob and ob.sel == 0 and ob.type == 'Mesh':
841                 # Add to the list
842                 obList =[ob]
843         del objects
844         
845         if not obList:
846                 Draw.PupMenu('error, no selected mesh objects')
847                 return
848         
849         # Create the variables.
850         USER_PROJECTION_LIMIT = Draw.Create(66)
851         USER_ONLY_SELECTED_FACES = Draw.Create(1)
852         USER_SHARE_SPACE = Draw.Create(1) # Only for hole filling.
853         USER_STRETCH_ASPECT = Draw.Create(1) # Only for hole filling.
854         USER_ISLAND_MARGIN = Draw.Create(0.0) # Only for hole filling.
855         USER_FILL_HOLES = Draw.Create(0)
856         USER_FILL_HOLES_QUALITY = Draw.Create(50) # Only for hole filling.
857         USER_VIEW_INIT = Draw.Create(0) # Only for hole filling.
858         USER_AREA_WEIGHT = Draw.Create(1) # Only for hole filling.
859         
860         
861         pup_block = [\
862         'Projection',\
863         ('Angle Limit:', USER_PROJECTION_LIMIT, 1, 89, 'lower for more projection groups, higher for less distortion.'),\
864         ('Selected Faces Only', USER_ONLY_SELECTED_FACES, 'Use only selected faces from all selected meshes.'),\
865         ('Init from view', USER_VIEW_INIT, 'The first projection will be from the view vector.'),\
866         ('Area Weight', USER_AREA_WEIGHT, 'Weight projections vector by face area.'),\
867         '',\
868         '',\
869         '',\
870         'UV Layout',\
871         ('Share Tex Space', USER_SHARE_SPACE, 'Objects Share texture space, map all objects into 1 uvmap.'),\
872         ('Stretch to bounds', USER_STRETCH_ASPECT, 'Stretch the final output to texture bounds.'),\
873         ('Island Margin:', USER_ISLAND_MARGIN, 0.0, 0.25, 'Margin to reduce bleed from adjacent islands.'),\
874         'Fill in empty areas',\
875         ('Fill Holes', USER_FILL_HOLES, 'Fill in empty areas reduced texture waistage (slow).'),\
876         ('Fill Quality:', USER_FILL_HOLES_QUALITY, 1, 100, 'Depends on fill holes, how tightly to fill UV holes, (higher is slower)'),\
877         ]
878         
879         # Reuse variable
880         if len(obList) == 1:
881                 ob = "Unwrap %i Selected Mesh"
882         else:
883                 ob = "Unwrap %i Selected Meshes"
884         
885         # HACK, loop until mouse is lifted.
886         '''
887         while Window.GetMouseButtons() != 0:
888                 sys.sleep(10)
889         '''
890         
891         if not Draw.PupBlock(ob % len(obList), pup_block):
892                 return
893         del ob
894         
895         # Convert from being button types
896         USER_PROJECTION_LIMIT = USER_PROJECTION_LIMIT.val
897         USER_ONLY_SELECTED_FACES = USER_ONLY_SELECTED_FACES.val
898         USER_SHARE_SPACE = USER_SHARE_SPACE.val
899         USER_STRETCH_ASPECT = USER_STRETCH_ASPECT.val
900         USER_ISLAND_MARGIN = USER_ISLAND_MARGIN.val
901         USER_FILL_HOLES = USER_FILL_HOLES.val
902         USER_FILL_HOLES_QUALITY = USER_FILL_HOLES_QUALITY.val
903         USER_VIEW_INIT = USER_VIEW_INIT.val
904         USER_AREA_WEIGHT = USER_AREA_WEIGHT.val
905         
906         USER_PROJECTION_LIMIT_CONVERTED = cos(USER_PROJECTION_LIMIT * DEG_TO_RAD)
907         USER_PROJECTION_LIMIT_HALF_CONVERTED = cos((USER_PROJECTION_LIMIT/2) * DEG_TO_RAD)
908         
909         
910         # Toggle Edit mode
911         is_editmode = Window.EditMode()
912         if is_editmode:
913                 Window.EditMode(0)
914         # Assume face select mode! an annoying hack to toggle face select mode because Mesh dosent like faceSelectMode.
915         
916         if USER_SHARE_SPACE:
917                 # Sort by data name so we get consistant results
918                 try:    obList.sort(key = lambda ob: ob.getData(name_only=1))
919                 except: obList.sort(lambda ob1, ob2: cmp( ob1.getData(name_only=1), ob2.getData(name_only=1) ))
920                 
921                 collected_islandList= []
922         
923         Window.WaitCursor(1)
924         
925         time1 = sys.time()
926         
927         # Tag as False se we dont operate on teh same mesh twice.
928         bpy.data.meshes.tag = False 
929         
930         for ob in obList:
931                 me = ob.getData(mesh=1)
932                 
933                 if me.tag or me.lib:
934                         continue
935                 
936                 # Tag as used
937                 me.tag = True
938                 
939                 if not me.faceUV: # Mesh has no UV Coords, dont bother.
940                         me.faceUV= True
941                 
942                 if USER_ONLY_SELECTED_FACES:
943                         meshFaces = [thickface(f) for f in me.faces if f.sel]
944                 else:
945                         meshFaces = map(thickface, me.faces)
946                 
947                 if not meshFaces:
948                         continue
949                 
950                 Window.DrawProgressBar(0.1, 'SmartProj UV Unwrapper, mapping "%s", %i faces.' % (me.name, len(meshFaces)))
951                 
952                 # =======
953                 # Generate a projection list from face normals, this is ment to be smart :)
954                 
955                 # make a list of face props that are in sync with meshFaces             
956                 # Make a Face List that is sorted by area.
957                 # meshFaces = []
958                 
959                 # meshFaces.sort( lambda a, b: cmp(b.area , a.area) ) # Biggest first.
960                 try:    meshFaces.sort( key = lambda a: -a.area ) 
961                 except: meshFaces.sort( lambda a, b: cmp(b.area , a.area) )
962                         
963                 # remove all zero area faces
964                 while meshFaces and meshFaces[-1].area <= SMALL_NUM:
965                         # Set their UV's to 0,0
966                         for uv in meshFaces[-1].uv:
967                                 uv.zero()
968                         meshFaces.pop()
969                 
970                 # Smallest first is slightly more efficient, but if the user cancels early then its better we work on the larger data.
971                 
972                 # Generate Projection Vecs
973                 # 0d is   1.0
974                 # 180 IS -0.59846
975                 
976                 
977                 # Initialize projectVecs
978                 if USER_VIEW_INIT:
979                         # Generate Projection
980                         projectVecs = [Vector(Window.GetViewVector()) * ob.matrixWorld.copy().invert().rotationPart()] # We add to this allong the way
981                 else:
982                         projectVecs = []
983                 
984                 newProjectVec = meshFaces[0].no
985                 newProjectMeshFaces = []        # Popping stuffs it up.
986                 
987                 
988                 # Predent that the most unique angke is ages away to start the loop off
989                 mostUniqueAngle = -1.0
990                 
991                 # This is popped
992                 tempMeshFaces = meshFaces[:]
993                 
994                 
995                 
996                 # This while only gathers projection vecs, faces are assigned later on.
997                 while 1:
998                         # If theres none there then start with the largest face
999                         
1000                         # add all the faces that are close.
1001                         for fIdx in xrange(len(tempMeshFaces)-1, -1, -1):
1002                                 # Use half the angle limit so we dont overweight faces towards this
1003                                 # normal and hog all the faces.
1004                                 if DotVecs(newProjectVec, tempMeshFaces[fIdx].no) > USER_PROJECTION_LIMIT_HALF_CONVERTED:
1005                                         newProjectMeshFaces.append(tempMeshFaces.pop(fIdx))
1006                         
1007                         # Add the average of all these faces normals as a projectionVec
1008                         averageVec = Vector(0,0,0)
1009                         if USER_AREA_WEIGHT:
1010                                 for fprop in newProjectMeshFaces:
1011                                         averageVec += (fprop.no * fprop.area)
1012                         else:
1013                                 for fprop in newProjectMeshFaces:
1014                                         averageVec += fprop.no
1015                                         
1016                         if averageVec.x != 0 or averageVec.y != 0 or averageVec.z != 0: # Avoid NAN
1017                                 projectVecs.append(averageVec.normalize())
1018                         
1019                         
1020                         # Get the next vec!
1021                         # Pick the face thats most different to all existing angles :)
1022                         mostUniqueAngle = 1.0 # 1.0 is 0d. no difference.
1023                         mostUniqueIndex = 0 # dummy
1024                         
1025                         for fIdx in xrange(len(tempMeshFaces)-1, -1, -1):
1026                                 angleDifference = -1.0 # 180d difference.
1027                                 
1028                                 # Get the closest vec angle we are to.
1029                                 for p in projectVecs:
1030                                         temp_angle_diff= DotVecs(p, tempMeshFaces[fIdx].no)
1031                                         
1032                                         if angleDifference < temp_angle_diff:
1033                                                 angleDifference= temp_angle_diff
1034                                 
1035                                 if angleDifference < mostUniqueAngle:
1036                                         # We have a new most different angle
1037                                         mostUniqueIndex = fIdx
1038                                         mostUniqueAngle = angleDifference
1039                         
1040                         if mostUniqueAngle < USER_PROJECTION_LIMIT_CONVERTED:
1041                                 #print 'adding', mostUniqueAngle, USER_PROJECTION_LIMIT, len(newProjectMeshFaces)
1042                                 # Now weight the vector to all its faces, will give a more direct projection
1043                                 # if the face its self was not representive of the normal from surrounding faces.
1044                                 
1045                                 newProjectVec = tempMeshFaces[mostUniqueIndex].no
1046                                 newProjectMeshFaces = [tempMeshFaces.pop(mostUniqueIndex)]
1047                                 
1048                         
1049                         else:
1050                                 if len(projectVecs) >= 1: # Must have at least 2 projections
1051                                         break
1052                 
1053                 
1054                 # If there are only zero area faces then its possible
1055                 # there are no projectionVecs
1056                 if not len(projectVecs):
1057                         Draw.PupMenu('error, no projection vecs where generated, 0 area faces can cause this.')
1058                         return
1059                 
1060                 faceProjectionGroupList =[[] for i in xrange(len(projectVecs)) ]
1061                 
1062                 # MAP and Arrange # We know there are 3 or 4 faces here 
1063                 
1064                 for fIdx in xrange(len(meshFaces)-1, -1, -1):
1065                         fvec = meshFaces[fIdx].no
1066                         i = len(projectVecs)
1067                         
1068                         # Initialize first
1069                         bestAng = DotVecs(fvec, projectVecs[0])
1070                         bestAngIdx = 0
1071                         
1072                         # Cycle through the remaining, first alredy done
1073                         while i-1:
1074                                 i-=1
1075                                 
1076                                 newAng = DotVecs(fvec, projectVecs[i])
1077                                 if newAng > bestAng: # Reverse logic for dotvecs
1078                                         bestAng = newAng
1079                                         bestAngIdx = i
1080                         
1081                         # Store the area for later use.
1082                         faceProjectionGroupList[bestAngIdx].append(meshFaces[fIdx])
1083                 
1084                 # Cull faceProjectionGroupList,
1085                 
1086                 
1087                 # Now faceProjectionGroupList is full of faces that face match the project Vecs list
1088                 for i in xrange(len(projectVecs)):
1089                         # Account for projectVecs having no faces.
1090                         if not faceProjectionGroupList[i]:
1091                                 continue
1092                         
1093                         # Make a projection matrix from a unit length vector.
1094                         MatProj = VectoMat(projectVecs[i])
1095                         
1096                         # Get the faces UV's from the projected vertex.
1097                         for f in faceProjectionGroupList[i]:
1098                                 f_uv = f.uv
1099                                 for j, v in enumerate(f.v):
1100                                         f_uv[j][:] = (MatProj * v.co)[:2]
1101                 
1102                 
1103                 if USER_SHARE_SPACE:
1104                         # Should we collect and pack later?
1105                         islandList = getUvIslands(faceProjectionGroupList, me)
1106                         collected_islandList.extend(islandList)
1107                         
1108                 else:
1109                         # Should we pack the islands for this 1 object?
1110                         islandList = getUvIslands(faceProjectionGroupList, me)
1111                         packIslands(islandList)
1112                 
1113                 
1114                 # update the mesh here if we need to.
1115         
1116         # We want to pack all in 1 go, so pack now
1117         if USER_SHARE_SPACE:
1118                 Window.DrawProgressBar(0.9, "Box Packing for all objects...")
1119                 packIslands(collected_islandList)
1120         
1121         print "Smart Projection time: %.2f" % (sys.time() - time1)
1122         # Window.DrawProgressBar(0.9, "Smart Projections done, time: %.2f sec." % (sys.time() - time1))
1123         
1124         if is_editmode:
1125                 Window.EditMode(1)
1126         
1127         Window.DrawProgressBar(1.0, "")
1128         Window.WaitCursor(0)
1129         Window.RedrawAll()
1130
1131 if __name__ == '__main__':
1132         main()