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