Eagle::KDTree< N, T > Class Template Reference

A multidimensional KDTree data structure rewritten from c-code by John Tsiombikas (http://code.google.com/p/kdtree/). More...

#include <elementary/aerie/KDTree.hpp>

Inheritance diagram for Eagle::KDTree< N, T >:

Public Member Functions
template<class Container >
bool	getEuclideanRange (const FixedArray< double, N > &pos, const double range, Container &res)
	Query the tree at a certain position with a certain range (distance).
void	insert (const FixedArray< double, N > &pos, const T &data)
	Insert a data element at a certain position into the KDTree.
void	speak ()
	Print the tree content into stdout.
Public Member Functions inherited from MemCore::ReferenceBase< KDTree< N, T > >
auto	getObjectCountID () const noexcept
	Get a unique ID for this object in the given domain.
bool	isIdentical (const WeakPtr< KDTree< N, T >, KDTree< N, T > > &PossibleSelf) const noexcept
	Check if this object is identical to the one used by the given pointer.
void	mkAutoDestructive ()
	Marks this object as being automatically destructed, e.g.
refcount_t	refcount () const noexcept
	The strong reference count.
	ReferenceBase (KDTree< N, T > *that) noexcept
	Constructor, initializes reference counter to zero.
const auto &	self () const
	Return weak pointer to the object self.
refcount_t	wrefcount () const noexcept
	The weak reference count.

Additional Inherited Members
Public Types inherited from MemCore::ReferenceBase< KDTree< N, T > >
using	reference_domain_t = KDTree< N, T >
	The type of the base class.
using	SelfPtr_t = WeakPtr< KDTree< N, T >, KDTree< N, T > >
	Type for a pointer to this object itself.
Protected Member Functions inherited from MemCore::ReferenceBase< KDTree< N, T > >
virtual void	extremeUnction ()
	A virtual function that will be called just before the object is destroyed.
ReferenceBase &	operator= (const ReferenceBase &R)
	Protected assignment operator (should not be called).
void	suicide ()
	Delete this.
virtual	~ReferenceBase ()
	Virtual destructor.

Detailed Description

template<int N, class T>
class Eagle::KDTree< N, T >

A multidimensional KDTree data structure rewritten from c-code by John Tsiombikas (http://code.google.com/p/kdtree/).

For a general information on what a kdtree is: http://en.wikipedia.org/wiki/Kd-tree Template Parameters are N for the dimension of the tree, T the data type of the data stored in the tree The tree can fill a container of any kind with results. Specializations for returning an unsorted std::vector<T>, an unsorted std::list<T> ,a sorted std::map<double,T> and std::multimap<double, T>, with 'double' being the squared distance to the query position, are provided. Usage:

using namespace Eagle;
using namespace std;
 
RefPtr<KDTree<4, int>>tree = new KDTree<4,int>();    //create 4-dimensional tree storing int's
assert(tree);
 
FixedArray<double, 4> pos1, pos2;                    //use FixedArrays<double,N> for defining positions
    pos1 = 0.0,  0.0,  0.0,  0.0; 
    pos2 = 0.5,  0.0,  0.0,  0.1; 
 
    tree->insert(pos1, 1);                           //insert data (int) at positions into the tree
    tree->insert(pos2, 2);
 
 vector<int>res;                                     //create a result container
     tree->nearest_range( pos3, 0.5, res );          //query tree at position with range providing the result container

Todo:

Implement Back to Front order traversal http://www.flipcode.com/archives/Thoughts_On_Visibility_Determination-In_Dynamic_Semi-Static_and_Static_Scenes.shtml

Rendering The Tree

A kd-tree (or an octree, kd-tree assumed from here on) can be traversed front-to-back relatively easily. Traversing is performed using a recursive function that determines at which side of a splitting plane the camera is located; these splitting planes are generated when the octree or kd-tree is compiled - a kd-tree contains a single splitting plane per node, the octree contains three splitting planes.

For octree traversal, check each of the three planes in turn to find the correct order to process the child nodes. The 'camera side' of each plane is processed first, then the opposite side. This way, we quickly find the kd-tree node that contains the camera. This is obviously the closest node, so we process this node first. This node also has no child nodes, so the recursive function returns, and the opposite side of the last encountered splitting plane is processed. This way we find the next closest node. Repeating this process, we visit every node, in the correct order. Note that to traverse the trees in back-to-front order, we simply pick the side of the plane that the camera is NOT in: Now the node with the camera will be the last node that is visited. This might be usefull in some cases (but not in the two algorithms that I discuss below).

Also note that neither the kd-tree nor the octree provide us with any kind of visibility information; they only provide us with the nodes sorted by depth. This even doesn't mean that the polygons are sorted: The polygons in the nodes still need some processing if we want them perfectly sorted.

http://en.wikipedia.org/wiki/BSP_tree

traverse_tree(bsp_tree* tree,point eye)
{
  location = tree->find_location(eye);
 
  if(tree->empty())
    return;
 
 
  if(location > 0)      // if eye in front of location
  {
    traverse_tree(tree->back,eye);
    display(tree->polygon_list);
    traverse_tree(tree->front,eye);
  }
  else if(location < 0) // eye behind location
  {
    traverse_tree(tree->front,eye);
    display(tree->polygon_list);
    traverse_tree(tree->back,eye);
  }
  else                  // eye coincidental with partition hyperplane
  {
    traverse_tree(tree->front,eye);
    traverse_tree(tree->back,eye);
  }
}

Author

Copyright (C) 2007 John Tsiombikas nucle.nosp@m.ar@s.nosp@m.iggra.nosp@m.ph.o.nosp@m.rg

Marcel Ritter 2009

Member Function Documentation

getEuclideanRange()

template<int N, class T >

template<class Container >

bool Eagle::KDTree< N, T >::getEuclideanRange ( const FixedArray< double, N > &  pos, const double  range, Container &  res  )

inline

Query the tree at a certain position with a certain range (distance).

The template argument Container is used to return different container types. Containers may contain just the elements, or elements AND distances. Support for vector<T>, map<double,T> and list<T> is already provided via the template specializations of KDTreeResult<class Container, Class T>. To add support for another container you have provide a template partial specialisation of struct KDTreeResult holding a reference to the container and providing the insert function, like it's done for the map:

template<class T>
struct KDTreeResult<map<double,T>, T >
{
    map<double,T>&result;
 
    KDTreeResult(map<double,T>&r)
    :result(r)
    {}
 
    void insert(const double dist_sq, const T&data)
    {
        result.insert( pair<double,T>(dist_sq, data) ); 
    }
};

A tree can then be queried like in this example (map):

KDTree<4, int> tree;
 
//... fill in some data ...
 
map<double, int>res_map; 
 
    tree.nearest_range( pos3, 0.5, res_map ); 
 
    cout << "result as map, elements with distances, sorted" << endl;
    for(map<double, int>::iterator it = res_map.begin(); it != res_map.end(); it++ )
        cout << it->first << "\t" << it->second <<endl; 

Here some additional code example snaps for querying all supported container types so far:

//vector
vector<int>res;
tree->nearest_range( pos3, 0.5, res ); 
 
//map
map<double, int>res_map; 
tree->nearest_range( pos3, 0.5, res_map ); 
 
//list
list<int>res_list;
tree->nearest_range( pos3, 0.5, res_list ); 

speak()

template<int N, class T >

void Eagle::KDTree< N, T >::speak ( )

inline

Print the tree content into stdout.

For printing the data element cout is used. So ensure, that the ostream operator << is provided for your data element types.