[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