[Bf-extensions-cvs] SVN commit: /data/svn/bf-extensions [1085] branches/ivygen/KdTree.py: == IVY ==
Florian Meyer
florianfelix at web.de
Sun Sep 26 20:03:03 CEST 2010
Revision: 1085
http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-extensions&revision=1085
Author: testscreenings
Date: 2010-09-26 20:03:02 +0200 (Sun, 26 Sep 2010)
Log Message:
-----------
== IVY ==
- preliminary implementation of KDTree for further study
Added Paths:
-----------
branches/ivygen/KdTree.py
Added: branches/ivygen/KdTree.py
===================================================================
--- branches/ivygen/KdTree.py (rev 0)
+++ branches/ivygen/KdTree.py 2010-09-26 18:03:02 UTC (rev 1085)
@@ -0,0 +1,188 @@
+'''
+preliminary implementation of KDTree,
+with nearest neighbour search
+
+places an empty at the closest vert of the selected object.
+
+The plan is to rewrite this to either get the tree as a property of meshobjects
+and to use vertices as the values and not only the locations,
+will propably yield better usability in the future
+
+'''
+
+
+
+
+import bpy
+from bpy.props import *
+import mathutils
+
+'''
+#Can be replaced with mathutils functions
+
+def square_distance(pointA, pointB):
+ # squared euclidean distance
+ distance = 0
+ dimensions = len(pointA) # assumes both points have the same dimensions
+ for dimension in range(dimensions):
+ distance += (pointA[dimension] - pointB[dimension])**2
+ return distance
+'''
+
+class KDTreeNeighbours():
+ """ Internal structure used in nearest-neighbours search.
+ """
+ def __init__(self, query_point, t):
+ self.query_point = query_point
+ self.t = t # neighbours wanted
+ self.largest_distance = 0 # squared
+ self.current_best = []
+
+ def calculate_largest(self):
+ if self.t >= len(self.current_best):
+ self.largest_distance = self.current_best[-1][1]
+ else:
+ self.largest_distance = self.current_best[self.t-1][1]
+
+ def add(self, point):
+ #sd = square_distance(point, self.query_point)
+ sd = (point-self.query_point).length
+ # run through current_best, try to find appropriate place
+ for i, e in enumerate(self.current_best):
+ if i == self.t:
+ return # enough neighbours, this one is farther, let's forget it
+ if e[1] > sd:
+ self.current_best.insert(i, [point, sd])
+ self.calculate_largest()
+ return
+ # append it to the end otherwise
+ self.current_best.append([point, sd])
+ self.calculate_largest()
+
+ def get_best(self):
+ return [element[0] for element in self.current_best[:self.t]]
+
+
+class KdTreeNode():
+ def __init__(self, vert, left, right, depth):
+ self.vert = vert
+ self.left = left
+ self.right = right
+ self.depth = depth
+
+ def is_leaf(self):
+ return (self.left == None and self.right == None)
+
+
+class KdTree():
+ def __init__(self, verts=[], ob_matrix=None, mode='Unbalanced'):
+
+ def build_balanced_tree(verts, depth=0):
+ if not verts: return None
+
+ split_axis = depth % 3 # only 3dimensional verts
+
+ verts.sort(key=lambda vert: vert[split_axis])
+ middle_vert = int(len(verts)/2)
+
+ node = KdTreeNode(vert = verts[middle_vert],
+ left = build_balanced_tree(verts[0:middle_vert], depth+1),
+ right = build_balanced_tree(verts[middle_vert+1:], depth+1),
+ depth = depth)
+
+ return node
+
+ self.root_node = build_balanced_tree(verts, depth=0)
+
+ '''
+ @staticmethod
+ def construct_from_data(data):
+ tree = KdTree(data)
+ return tree
+ '''
+ def query(self, query_point, t=1):
+ statistics = {'nodes_visited': 0, 'far_search': 0, 'leafs_reached': 0}
+
+ def nn_search(node, query_point, t, depth, best_neighbours):
+ if node == None:
+ return
+
+ #statistics['nodes_visited'] += 1
+
+ # if we have reached a leaf, let's add to current best neighbours,
+ # (if it's better than the worst one or if there is not enough neighbours)
+ if node.is_leaf():
+ #statistics['leafs_reached'] += 1
+ best_neighbours.add(node.vert)
+ return
+
+ # this node is no leaf
+
+ # select dimension for comparison (based on current depth)
+ axis = depth % len(query_point)
+
+ # figure out which subtree to search
+ near_subtree = None # near subtree
+ far_subtree = None # far subtree (perhaps we'll have to traverse it as well)
+
+ # compare query_point and point of current node in selected dimension
+ # and figure out which subtree is farther than the other
+ if query_point[axis] < node.vert[axis]:
+ near_subtree = node.left
+ far_subtree = node.right
+ else:
+ near_subtree = node.right
+ far_subtree = node.left
+
+ # recursively search through the tree until a leaf is found
+ nn_search(near_subtree, query_point, t, depth+1, best_neighbours)
+
+ # while unwinding the recursion, check if the current node
+ # is closer to query point than the current best,
+ # also, until t points have been found, search radius is infinity
+ best_neighbours.add(node.vert)
+
+ # check whether there could be any points on the other side of the
+ # splitting plane that are closer to the query point than the current best
+ if (node.vert[axis] - query_point[axis])**2 < best_neighbours.largest_distance:
+ #statistics['far_search'] += 1
+ nn_search(far_subtree, query_point, t, depth+1, best_neighbours)
+
+ return
+
+ # if there's no tree, there's no neighbors
+ if self.root_node != None:
+ neighbours = KDTreeNeighbours(query_point, t)
+ nn_search(self.root_node, query_point, t, depth=0, best_neighbours=neighbours)
+ result = neighbours.get_best()
+ else:
+ result = []
+
+ #print statistics
+ return result
+
+
+
+print('______START_______')
+C = bpy.context
+
+cursor = C.scene.cursor_location
+ob = C.active_object
+verts = C.active_object.data.vertices.values()
+vertices = [vert.co for vert in C.active_object.data.vertices]
+mat = ob.matrix_world.copy()
+
+Tree = KdTree(vertices)
+
+close = Tree.query(cursor*mat)[0]
+
+close = mat*close
+#close = close*mat
+print('closest:', close)
+em = bpy.ops.object.add('INVOKE_DEFAULT', type='EMPTY', location=close)
+#C.active_object.location = close[0]
+
+print (Tree.root_node.left.depth)
+
+
+#print(verts)
\ No newline at end of file
More information about the Bf-extensions-cvs
mailing list