daily pastebin goal
63%
SHARE
TWEET

Visualize K-D Tree on Mesh

DrGravitas Dec 10th, 2015 2 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. '''
  2.         WIP: 15_1207
  3.         Script By: Dr. Gravitas
  4.        
  5.         Visualize K-D Tree Spacial Partitioning of selected Mesh.
  6.  
  7. '''
  8. import pymel.core as pm
  9. from maya import OpenMaya as om
  10. import os
  11. import fileinput
  12. import pickle
  13. import heapq
  14. from collections import namedtuple
  15. from operator import itemgetter
  16. from pprint import pformat
  17.  
  18.  
  19. def buildTreeAndHash( target ):
  20.         for vertex in target.verts:
  21.                 vPoint = vertex.getPosition( space='world' )
  22.                 pos = ( vPoint.x, vPoint.y, vPoint.z )
  23.                
  24.                 v2PDict[pos] = vertex
  25.                
  26.         tree = kdtree( v2PDict.keys() )
  27.         return tree
  28.  
  29. class Node(namedtuple('Node', 'location tree_level axis left_child right_child')):
  30.         def __repr__(self):
  31.                 return pformat(tuple(self))
  32.  
  33. def kdtree( point_list, depth=0 ):
  34.         try:
  35.                 k = len( point_list[0] ) # assumes all points have the same dimension
  36.         except IndexError as e: # if not point_list:
  37.                 return None
  38.         # Select axis based on depth so that axis cycles through all valid values
  39.         axis = depth % k
  40.  
  41.         # Sort point list and choose median as pivot element
  42.         point_list = sorted( point_list, key=itemgetter(axis))
  43.         median = len( point_list ) // 2 # choose median
  44.  
  45.         # Create node and construct subtrees
  46.         return Node(
  47.                 location = point_list[median],
  48.                 tree_level = depth,
  49.                 axis = axis,
  50.                 left_child = kdtree(point_list[:median], depth + 1),
  51.                 right_child = kdtree(point_list[median + 1:], depth + 1)
  52.         )
  53.  
  54. def buildVertSelectGroups( node ):
  55.         currentGroup = []
  56.         allGroups = []
  57.         if node is not None:
  58.                 currentVert = v2PDict[node.location]
  59.                 currentGroup.extend( currentVert )
  60.                 leftGroup = buildVertSelectGroups( node.left_child )
  61.                 rightGroup = buildVertSelectGroups( node.right_child )
  62.                
  63.                 currentGroup.extend(leftGroup[0])
  64.                 currentGroup.extend(rightGroup[0])
  65.                 allGroups.append(currentGroup)
  66.                
  67.                 for vGroup in leftGroup[1]:
  68.                         allGroups.append( vGroup )
  69.                 for vGroup in rightGroup[1]:
  70.                         allGroups.append( vGroup )
  71.                
  72.        
  73.         return currentGroup, allGroups
  74.        
  75.        
  76. '''
  77.         Main Body
  78. '''
  79. start_time = pm.date()
  80. print '\n\n\n'
  81. print '******************************************************************'
  82. print '\t\t\t' + start_time
  83. print '******************************************************************'
  84. target = (pm.selected())[0].getShape()
  85. pm.select( clear=True )
  86. tree = ()
  87. v2PDict = {}
  88. tree = buildTreeAndHash( target )
  89. selectionGroups = buildVertSelectGroups( tree )
  90. selectionGroups[1].append( selectionGroups[0] )
  91. selectionGroups = selectionGroups[1]
  92.  
  93. selectionGroups.sort(key=len, reverse=True)
  94.  
  95. for selectionGroup in selectionGroups:
  96.         pm.select( selectionGroup )
  97.         pm.refresh(f=True)
  98. pm.select( clear=True )
  99. pm.refresh(f=True)
  100. tree = None
  101. v2PDict = None
  102. selectionGroups = None
  103. end_time = pm.date()
  104. print '******************************************************************'
  105. print '\t\t\t' + start_time
  106. print '\t\t\t' + end_time
  107. print '******************************************************************'
  108. #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