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