|
VISH
0.2
|
A multidimensional KDTree data structure rewritten from c-code by John Tsiombikas (http://code.google.com/p/kdtree/). More...
#include </home/werner/origo/vish/ocean/aerie/KDTree.hpp>
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
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);
}
}
ComputeGridStreamLines.cpp, and ComputeMultiStreamLines.cpp.
| bool Eagle::KDTree::nearest_range | ( | 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 );
| void Eagle::KDTree::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.
1.7.5