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