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.  
  72.         openSet.add(startPathNode.node)
  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)
  81.                 closedSet.add(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:
  88.                                         openSet.add(connectedNode.node)
  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[1]
  165.         actualVerts = []
  166.         illegalPoints = []
  167.        
  168.         for vertDef in verts:
  169.                 vertPoint = vertDef[1]
  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[0]
  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. '''
  219. def readFile(inputFile):
  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[0] ) # 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.        
  276.         return readFile( inputFile )
  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())[0].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. OK, I Understand
 
Top