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