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