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