• API
• FAQ
• Tools
• Archive
SHARE
TWEET  UV Unwrap KD-Tree, NNS, A* Vertex/Edge Selection DrGravitas  Dec 10th, 2015 3 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. '''
2.         WIP: 15_1206
3.         Script By: Dr. Gravitas
4.
5.         Imports a pickled representation of edges and their vertices, representing the
6.         borders of UV Shells. This tries to replicate the actions taken to create a
7.         UV based on the nearest edge/vertex of the selected model. It sews together
8.         all of the UVs and then cuts those nearest edges and finally unwraps it.
9.
10. '''
11. import pymel.core as pm
12. from maya import OpenMaya as om
13. import os
14. import fileinput
15. import pickle
16. import heapq
17. from collections import namedtuple
18. from operator import itemgetter
19. from pprint import pformat
20.
21.
22. '''
23.         Given a vector and a KDTree Node, look up the vertex corresponding with the node's location and
24.         determine the distance in worldspace between it and the vector's point.
25. '''
26. def compareVectorDistanceFromNode(vector, node):
27.         if node is not None:
28.                 vertex = v2PDict[node.location]
29.                 return vector.distanceTo( pm.datatypes.Vector( vertex.getPosition(space='world') ) )
30.         # When the node is none, return infinite distance
31.         return float('inf')
32.
33.
34. def compareVectorDistance(vertex, vector):
35.         return vector.distanceTo( pm.datatypes.Vector( vertex.getPosition(space='world') ) )
36.
37. class PathNode:
38.         cost, node, edge, parentNode = (None,None,None,None)
39.
40.         def __init__(self, cost=None,node=None,edge=None,parentNode=None):
41.                 self.cost = cost
42.                 self.node = node
43.                 self.edge = edge
44.                 self.parentNode = parentNode
45.
46. def getConnectedVertsAndEdges( vertex ):
47.         connectedPathNodes = []
48.         edges = vertex.connectedEdges()
49.
50.         for edge in edges:
51.                 verts = edge.connectedVertices()
52.                 vert = verts[(verts.index(vertex) -1)*-1]
53.                 #Uninitialized cost is infinite, parent is none
54.                 connectedPathNode = PathNode( node=vert, edge=edge )
55.                 connectedPathNodes.append( connectedPathNode )
56.
57.         return connectedPathNodes
58.
59. def retracePath( pathNode ):
60.         path = [pathNode.edge]
61.         while pathNode.parentNode is not None:
62.                 pathNode = pathNode.parentNode
63.                 path.append(pathNode.edge)
64.         path.reverse()
65.         return path
66.
67. def aStar( startPathNode, end, expandNodeMethod, comparisonMethod ):
68.         openSet = set()
69.         openHeap = []
70.         closedSet = set()
71.
73.         openHeap.append(startPathNode)
74.
75.         while openSet:
76.                 currentPathNode = heapq.heappop(openHeap)
77.                 if comparisonMethod(currentPathNode.node, end) == 0:
78.                         return retracePath(currentPathNode)
79.
80.                 openSet.remove(currentPathNode.node)
82.
83.                 for connectedNode in expandNodeMethod( currentPathNode.node ):
84.                         if connectedNode.node not in closedSet:
85.                                 # Estimated distance to the end
86.                                 dist = comparisonMethod( connectedNode.node, end )
87.                                 if connectedNode.node not in openSet:
89.                                         connectedNode.cost = dist
90.                                         heapq.heappush(openHeap, connectedNode)
91.                                 connectedNode.parentNode = currentPathNode
92.         return None
93.
94. '''
95.         Get minimum edges necessary to connect the two vertices
96. '''
97. def pathBetweenVertices( startVertex, goalVertex ):
98.         edges = []
99.
100.         if startVertex.index() == goalVertex.index():
101.                 pm.error('Identical Vertices provided for pathfinding!' + str(startVertex) + ' and ' + str(goalVertex) )
102.         if not startVertex.isConnectedTo( goalVertex ):
103.                 #For when the two vertices are not directly connected
104.                 startNode = PathNode( cost = 0,  node = startVertex)
105.                 goalAsVector = pm.datatypes.Vector( goalVertex.getPosition(space='world') )
106.                 edges = aStar( startNode, goalAsVector, getConnectedVertsAndEdges, compareVectorDistance )
107.                 if edges is None:
108.                         pm.warning('A* failed to connect the two vertices: ' + str(startVertex) + ' and ' + str(goalVertex) )
109.                         edges = []
110.         else:
111.                 possibleEdges = startVertex.connectedEdges()
112.                 for possibleEdge in possibleEdges:
113.                         if goalVertex in possibleEdge.connectedVertices():
114.                                 edges.extend( possibleEdge )
115.
116.         return edges
117.
118.
119.
120. class BestChoice(namedtuple('BestChoice', 'node distanceToIdeal')):
121.         def __repr__(self):
122.                 return pformat(tuple(self))
123.
124. def recursive_search( idealPoint, illegalPoints, currentNode, bestNode, comparisonMethod ):
125.         if currentNode is None:
126.                 return bestNode
127.
128.         # Do not allow the vertices that are listed to be selected as the best point.
129.         if currentNode.location not in illegalPoints:
130.                 distance = comparisonMethod( idealPoint, currentNode )
131.                 if distance < bestNode.distanceToIdeal:
132.                         #print distance, bestNode.distanceToIdeal, currentNode.location
133.                         bestNode = BestChoice( currentNode, distance )
134.
135.         # Determine axis (X, Y, Z) of the current node (depth mod number of dimensions)
136.         axis = currentNode.axis
137.         # Get the difference between the idealPoint and the current Node's position at the chosen axis
138.         #  and determine whether to travel down the left or right branch
139.         diff = idealPoint[axis] - currentNode.location[axis]
140.
141.         close, away = (currentNode.left_child, currentNode.right_child) if diff <= 0 else (currentNode.right_child, currentNode.left_child)
142.
143.         bestNode = recursive_search( idealPoint, illegalPoints, close, bestNode, comparisonMethod )
144.         if diff ** 2 < bestNode.distanceToIdeal:
145.                 bestNode = recursive_search(idealPoint, illegalPoints, away, bestNode, comparisonMethod )
146.
147.         return bestNode
148.
149.
150. def searchKDTree( idealPoint, illegalPoints, comparisonMethod ):
151.         #Execute the search at the root node of the tree
152.         distance = comparisonMethod( idealPoint, tree )
153.         bestNode = BestChoice( tree, distance )
154.         bestNode = recursive_search( idealPoint, illegalPoints, tree, bestNode, comparisonMethod )
155.         return bestNode.node
156.
157. '''
158.         Worst Case: We have no idea where this edge begins or ends.
159.
160.         Given an edgeDef, find the edge or edges that best fits that definition.
161. '''
162. def searchForEdge(edgeDef):
163.         actualEdges = []
164.         verts = edgeDef
165.         actualVerts = []
166.         illegalPoints = []
167.
168.         for vertDef in verts:
169.                 vertPoint = vertDef
170.                 vector = pm.datatypes.Vector( vertPoint )
171.                 # Begin KDTree navigation - identified vertices are illegal to reselect for subsequent vertices of the edge
172.                 bestNode = searchKDTree( vertPoint, illegalPoints, compareVectorDistanceFromNode )
173.                 #print bestNode.tree_level
174.                 bestVert = v2PDict[bestNode.location]
175.                 actualVerts.extend( bestVert )
176.                 illegalPoints.append( bestNode.location )
177.                 #print vertDef
178.                 #print '[' + str(bestVert) + ', ' + str(bestVert.getPosition())
179.
180.         #With best cases for Verts, get edges between first and all others. Should only be one other!
181.         start = actualVerts
182.         for end in actualVerts[1:]:
183.                 actualEdges.extend( pathBetweenVertices( start, end ) )
184.
185.
186.         return actualEdges
187.
188. '''
189.         Identifies MeshEdges for each of the edges definied in the edgeDefList
190.         and cuts the UV along them.
191. '''
192. def getActualEdges(edges):
193.         actualEdges = []
194.
195.         for edge in edges:
196.                 #actualEdge = findActualEdge( edge )
197.                 #actualEdges.extend( actualEdge )
198.                 actualEdges.extend( searchForEdge( edge ) )
199.
200.         return actualEdges
201.
202. '''
203.         Attempts to reconstruct UVs based on list of edges/vertices
204. '''
205. def reconstructUVOps(selected):
206.         pm.polyMapSew( selected )
207.         edges = importUVEdgeDefs()
208.         actualEdges = getActualEdges( edges )
209.         pm.select( clear=True )
210.         pm.polyMapCut( actualEdges )
211.         pm.select( target.map[0:] )
212.         pm.mel.eval('Unfold3D -u -ite 3 -p 1 -bi 1 -tf 1 -ms 4096 -rs 3;')
213.         pm.select( actualEdges )
214.         pm.refresh(f=True)
215.
216. '''
217.         Attempts to read in from a file and unpickle the data into a Python data structure
218. '''
220.         commands = None
221.         try:
222.                 with open(inputFile, 'r') as inFile:
223.                         commands = pickle.load( inFile )
224.         except IOError:
225.                 pm.error("Error: File does not appear to exist.")
226.         return commands
227.
228.
229. def buildTreeAndHash( target ):
230.         for vertex in target.verts:
231.                 vPoint = vertex.getPosition( space='world' )
232.                 pos = ( vPoint.x, vPoint.y, vPoint.z )
233.
234.                 v2PDict[pos] = vertex
235.
236.         tree = kdtree( v2PDict.keys() )
237.         return tree
238.
239. class Node(namedtuple('Node', 'location tree_level axis left_child right_child')):
240.         def __repr__(self):
241.                 return pformat(tuple(self))
242.
243. def kdtree( point_list, depth=0 ):
244.         try:
245.                 k = len( point_list ) # assumes all points have the same dimension
246.         except IndexError as e: # if not point_list:
247.                 return None
248.         # Select axis based on depth so that axis cycles through all valid values
249.         axis = depth % k
250.
251.         # Sort point list and choose median as pivot element
252.         point_list = sorted( point_list, key=itemgetter(axis))
253.         median = len( point_list ) // 2 # choose median
254.
255.         # Create node and construct subtrees
256.         return Node(
257.                 location = point_list[median],
258.                 tree_level = depth,
259.                 axis = axis,
260.                 left_child = kdtree(point_list[:median], depth + 1),
261.                 right_child = kdtree(point_list[median + 1:], depth + 1)
262.         )
263.
264. '''
265.         Imports Edges from a file location into Python Data structures
266.
267.         TODO: Turn this into a dialog box that lets you configure this but auto-populates
268.         with most recent file in default location
269.
270. '''
271. def importUVEdgeDefs():
272.         dirPath = os.path.dirname( 'C:\\[Insert Path to Project Scripts Here]\\Scripts\\StoredData\\UV Cut Edges\\' )
273.         filename = '15_1206_UVCutEdges' # Name of the exported edges definition
274.         inputFile = os.path.abspath( os.path.join( dirPath, filename ) )
275.
277.
278.
279. '''
280.         Main Body
281. '''
282. start_time = pm.date()
283. print '\n\n\n'
284. print '******************************************************************'
285. print '\t\t\t' + start_time
286. print '******************************************************************'
287. target = (pm.selected()).getShape()
288. #pm.select( clear=True )
289. tree = ()
290. v2PDict = {}
291. tree = buildTreeAndHash( target )
292. reconstructUVOps( target )
293. tree = None
294. v2PDict = None
295. end_time = pm.date()
296. print '******************************************************************'
297. print '\t\t\t' + start_time
298. print '\t\t\t' + end_time
299. print '******************************************************************'
300. #pm.error('Success!')
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top