23838588f43992d7235c38fa2ff00ba64bff8af8
[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 is not 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     # Create the variables.
817     USER_PROJECTION_LIMIT = projection_limit
818     USER_ONLY_SELECTED_FACES = True
819     USER_SHARE_SPACE = 1 # Only for hole filling.
820     USER_STRETCH_ASPECT = 1 # Only for hole filling.
821     USER_ISLAND_MARGIN = island_margin # Only for hole filling.
822     USER_FILL_HOLES = 0
823     USER_FILL_HOLES_QUALITY = 50 # Only for hole filling.
824     USER_VIEW_INIT = 0 # Only for hole filling.
825     
826     is_editmode = (context.active_object.mode == 'EDIT')
827     if is_editmode:
828         obList =  [ob for ob in [context.active_object] if ob and ob.type == 'MESH']
829     else:
830         obList =  [ob for ob in context.selected_editable_objects if ob and ob.type == 'MESH']
831         USER_ONLY_SELECTED_FACES = False
832
833     if not obList:
834         raise('error, no selected mesh objects')
835
836     # Reuse variable
837     if len(obList) == 1:
838         ob = "Unwrap %i Selected Mesh"
839     else:
840         ob = "Unwrap %i Selected Meshes"
841
842     # HACK, loop until mouse is lifted.
843     '''
844     while Window.GetMouseButtons() != 0:
845         time.sleep(10)
846     '''
847
848 #XXX    if not Draw.PupBlock(ob % len(obList), pup_block):
849 #XXX            return
850 #XXX    del ob
851
852     # Convert from being button types
853
854     USER_PROJECTION_LIMIT_CONVERTED = cos(USER_PROJECTION_LIMIT * DEG_TO_RAD)
855     USER_PROJECTION_LIMIT_HALF_CONVERTED = cos((USER_PROJECTION_LIMIT/2) * DEG_TO_RAD)
856
857
858     # Toggle Edit mode
859     is_editmode = (context.active_object.mode == 'EDIT')
860     if is_editmode:
861         bpy.ops.object.mode_set(mode='OBJECT')
862     # Assume face select mode! an annoying hack to toggle face select mode because Mesh dosent like faceSelectMode.
863
864     if USER_SHARE_SPACE:
865         # Sort by data name so we get consistant results
866         obList.sort(key = lambda ob: ob.data.name)
867         collected_islandList= []
868
869 #XXX    Window.WaitCursor(1)
870
871     time1 = time.time()
872
873     # Tag as False se we dont operate on the same mesh twice.
874 #XXX    bpy.data.meshes.tag = False
875     for me in bpy.data.meshes:
876         me.tag = False
877
878
879     for ob in obList:
880         me = ob.data
881
882         if me.tag or me.library:
883             continue
884
885         # Tag as used
886         me.tag = True
887
888         if not me.uv_textures: # Mesh has no UV Coords, dont bother.
889             me.uv_textures.new()
890
891         uv_layer = me.uv_textures.active.data
892         me_verts = list(me.vertices)
893
894         if USER_ONLY_SELECTED_FACES:
895             meshFaces = [thickface(f, uv_layer[i], me_verts) for i, f in enumerate(me.faces) if f.select]
896         else:
897                 meshFaces = [thickface(f, uv_layer[i], me_verts) for i, f in enumerate(me.faces)]
898
899         if not meshFaces:
900             continue
901
902 #XXX            Window.DrawProgressBar(0.1, 'SmartProj UV Unwrapper, mapping "%s", %i faces.' % (me.name, len(meshFaces)))
903
904         # =======
905         # Generate a projection list from face normals, this is ment to be smart :)
906
907         # make a list of face props that are in sync with meshFaces
908         # Make a Face List that is sorted by area.
909         # meshFaces = []
910
911         # meshFaces.sort( lambda a, b: cmp(b.area , a.area) ) # Biggest first.
912         meshFaces.sort(key=lambda a: -a.area)
913
914         # remove all zero area faces
915         while meshFaces and meshFaces[-1].area <= SMALL_NUM:
916             # Set their UV's to 0,0
917             for uv in meshFaces[-1].uv:
918                 uv.zero()
919             meshFaces.pop()
920
921         # Smallest first is slightly more efficient, but if the user cancels early then its better we work on the larger data.
922
923         # Generate Projection Vecs
924         # 0d is   1.0
925         # 180 IS -0.59846
926
927
928         # Initialize projectVecs
929         if USER_VIEW_INIT:
930             # Generate Projection
931             projectVecs = [Vector(Window.GetViewVector()) * ob.matrix_world.inverted().to_3x3()] # We add to this allong the way
932         else:
933             projectVecs = []
934
935         newProjectVec = meshFaces[0].no
936         newProjectMeshFaces = []        # Popping stuffs it up.
937
938
939         # Predent that the most unique angke is ages away to start the loop off
940         mostUniqueAngle = -1.0
941
942         # This is popped
943         tempMeshFaces = meshFaces[:]
944
945
946
947         # This while only gathers projection vecs, faces are assigned later on.
948         while 1:
949             # If theres none there then start with the largest face
950
951             # add all the faces that are close.
952             for fIdx in range(len(tempMeshFaces)-1, -1, -1):
953                 # Use half the angle limit so we dont overweight faces towards this
954                 # normal and hog all the faces.
955                 if newProjectVec.dot(tempMeshFaces[fIdx].no) > USER_PROJECTION_LIMIT_HALF_CONVERTED:
956                     newProjectMeshFaces.append(tempMeshFaces.pop(fIdx))
957
958             # Add the average of all these faces normals as a projectionVec
959             averageVec = Vector((0.0, 0.0, 0.0))
960             if user_area_weight == 0.0:
961                 for fprop in newProjectMeshFaces:
962                     averageVec += fprop.no
963             elif user_area_weight == 1.0:
964                 for fprop in newProjectMeshFaces:
965                     averageVec += fprop.no * fprop.area
966             else:
967                 for fprop in newProjectMeshFaces:
968                     averageVec += fprop.no * ((fprop.area * user_area_weight) + (1.0 - user_area_weight))
969
970             if averageVec.x != 0 or averageVec.y != 0 or averageVec.z != 0: # Avoid NAN
971                 projectVecs.append(averageVec.normalized())
972
973
974             # Get the next vec!
975             # Pick the face thats most different to all existing angles :)
976             mostUniqueAngle = 1.0 # 1.0 is 0d. no difference.
977             mostUniqueIndex = 0 # dummy
978
979             for fIdx in range(len(tempMeshFaces)-1, -1, -1):
980                 angleDifference = -1.0 # 180d difference.
981
982                 # Get the closest vec angle we are to.
983                 for p in projectVecs:
984                     temp_angle_diff= p.dot(tempMeshFaces[fIdx].no)
985
986                     if angleDifference < temp_angle_diff:
987                         angleDifference= temp_angle_diff
988
989                 if angleDifference < mostUniqueAngle:
990                     # We have a new most different angle
991                     mostUniqueIndex = fIdx
992                     mostUniqueAngle = angleDifference
993
994             if mostUniqueAngle < USER_PROJECTION_LIMIT_CONVERTED:
995                 #print 'adding', mostUniqueAngle, USER_PROJECTION_LIMIT, len(newProjectMeshFaces)
996                 # Now weight the vector to all its faces, will give a more direct projection
997                 # if the face its self was not representive of the normal from surrounding faces.
998
999                 newProjectVec = tempMeshFaces[mostUniqueIndex].no
1000                 newProjectMeshFaces = [tempMeshFaces.pop(mostUniqueIndex)]
1001
1002
1003             else:
1004                 if len(projectVecs) >= 1: # Must have at least 2 projections
1005                     break
1006
1007
1008         # If there are only zero area faces then its possible
1009         # there are no projectionVecs
1010         if not len(projectVecs):
1011             Draw.PupMenu('error, no projection vecs where generated, 0 area faces can cause this.')
1012             return
1013
1014         faceProjectionGroupList =[[] for i in range(len(projectVecs)) ]
1015
1016         # MAP and Arrange # We know there are 3 or 4 faces here
1017
1018         for fIdx in range(len(meshFaces)-1, -1, -1):
1019             fvec = meshFaces[fIdx].no
1020             i = len(projectVecs)
1021
1022             # Initialize first
1023             bestAng = fvec.dot(projectVecs[0])
1024             bestAngIdx = 0
1025
1026             # Cycle through the remaining, first already done
1027             while i-1:
1028                 i-=1
1029
1030                 newAng = fvec.dot(projectVecs[i])
1031                 if newAng > bestAng: # Reverse logic for dotvecs
1032                     bestAng = newAng
1033                     bestAngIdx = i
1034
1035             # Store the area for later use.
1036             faceProjectionGroupList[bestAngIdx].append(meshFaces[fIdx])
1037
1038         # Cull faceProjectionGroupList,
1039
1040
1041         # Now faceProjectionGroupList is full of faces that face match the project Vecs list
1042         for i in range(len(projectVecs)):
1043             # Account for projectVecs having no faces.
1044             if not faceProjectionGroupList[i]:
1045                 continue
1046
1047             # Make a projection matrix from a unit length vector.
1048             MatQuat = VectoQuat(projectVecs[i])
1049
1050             # Get the faces UV's from the projected vertex.
1051             for f in faceProjectionGroupList[i]:
1052                 f_uv = f.uv
1053                 for j, v in enumerate(f.v):
1054                     # XXX - note, between mathutils in 2.4 and 2.5 the order changed.
1055                     f_uv[j][:] = (MatQuat * v.co).xy
1056
1057
1058         if USER_SHARE_SPACE:
1059             # Should we collect and pack later?
1060             islandList = getUvIslands(faceProjectionGroupList, me)
1061             collected_islandList.extend(islandList)
1062
1063         else:
1064             # Should we pack the islands for this 1 object?
1065             islandList = getUvIslands(faceProjectionGroupList, me)
1066             packIslands(islandList)
1067
1068
1069         # update the mesh here if we need to.
1070
1071     # We want to pack all in 1 go, so pack now
1072     if USER_SHARE_SPACE:
1073 #XXX            Window.DrawProgressBar(0.9, "Box Packing for all objects...")
1074         packIslands(collected_islandList)
1075
1076     print("Smart Projection time: %.2f" % (time.time() - time1))
1077     # Window.DrawProgressBar(0.9, "Smart Projections done, time: %.2f sec." % (time.time() - time1))
1078
1079     if is_editmode:
1080         bpy.ops.object.mode_set(mode='EDIT')
1081
1082     dict_matrix.clear()
1083
1084 #XXX    Window.DrawProgressBar(1.0, "")
1085 #XXX    Window.WaitCursor(0)
1086 #XXX    Window.RedrawAll()
1087
1088 """
1089     pup_block = [\
1090     'Projection',\
1091     ('Selected Faces Only', USER_ONLY_SELECTED_FACES, 'Use only selected faces from all selected meshes.'),\
1092     ('Init from view', USER_VIEW_INIT, 'The first projection will be from the view vector.'),\
1093     '',\
1094     'UV Layout',\
1095     ('Share Tex Space', USER_SHARE_SPACE, 'Objects Share texture space, map all objects into 1 uvmap.'),\
1096     ('Stretch to bounds', USER_STRETCH_ASPECT, 'Stretch the final output to texture bounds.'),\
1097 *       ('Island Margin:', USER_ISLAND_MARGIN, 0.0, 0.5, ''),\
1098     'Fill in empty areas',\
1099     ('Fill Holes', USER_FILL_HOLES, 'Fill in empty areas reduced texture waistage (slow).'),\
1100     ('Fill Quality:', USER_FILL_HOLES_QUALITY, 1, 100, 'Depends on fill holes, how tightly to fill UV holes, (higher is slower)'),\
1101     ]
1102 """
1103
1104 from bpy.props import FloatProperty
1105
1106
1107 class SmartProject(Operator):
1108     '''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.'''
1109     bl_idname = "uv.smart_project"
1110     bl_label = "Smart UV Project"
1111     bl_options = {'REGISTER', 'UNDO'}
1112
1113     angle_limit = FloatProperty(
1114             name="Angle Limit",
1115             description="lower for more projection groups, higher for less distortion",
1116             min=1.0, max=89.0,
1117             default=66.0,
1118             )
1119     island_margin = FloatProperty(
1120             name="Island Margin",
1121             description="Margin to reduce bleed from adjacent islands",
1122             min=0.0, max=1.0,
1123             default=0.0,
1124             )
1125     user_area_weight = FloatProperty(
1126             name="Area Weight",
1127             description="Weight projections vector by faces with larger areas",
1128             min=0.0, max=1.0,
1129             default=0.0,
1130             )
1131
1132     @classmethod
1133     def poll(cls, context):
1134         return context.active_object is not None
1135
1136     def execute(self, context):
1137         main(context,
1138              self.island_margin,
1139              self.angle_limit,
1140              self.user_area_weight,
1141              )
1142         return {'FINISHED'}
1143
1144     def invoke(self, context, event):
1145         wm = context.window_manager
1146         return wm.invoke_props_dialog(self)