Neighbor Feature Extended Kd-tree And Searching Algorithm

Calculating distance between a huge amount of objects in scene to determine interactions is a main computing task of the interest management in game system. The kd-tree being a type of nearest neighbor finding tools has been applied to game scene partitioning, and keeps the efficiency of interest management in a certain extent. But the current applications of kd-tree just use the feature that the sub-space is divided into two, the searching needs to begin from the standing node and goes upward recursively to a non-leaf node which encompasses the AOI, then goes downward recursively to find all leaf nodes which intersect the AOI. When the searching is among multiple deep tree nodes, the efficiency decreases evidently due to the long searching path.Noticing that the AOI intersecting leaf nodes are adjacent to standing node in space, it's possible to find a shorter linking path, and the size of smallest sub-divided space is larger than AOI, the concept of neighbor feature is proposed. The neighbor feature represents many space-adjacent features between nodes, these features can make the searching path to surrounding spaces shorter based on the position-relation between AOI and standing node, it alleviates the problem that searching hierarchical recursively makes an excessive long path. The traditional structure of kd-tree is extended using neighbor feature, the split dimension is used to represent the neighbor feature, the space adjacent relations between nodes are added upon the hierarchical relations, and a new searching algorithm which goes from standing node to surrounding spaces is devised. The analysis and simulation showed that the new algorithm improves the performance by about 40% and is more stable than the traditional one.