quadtree search question

Engines, Libraries and Tools Java 3D
#1

Hi all,
I am working on terrain code and using quadtree for frustrum culling. Was wandering what might be the best way to search quadtree to eliminate nodes which will not be rendered. One way might be to have just plain array and assign nodes to it as there are being recurcively created and then search through that array - or maybe more(or less) efficient might be to search recurcively tree along the edges. Does anybody have any input on this?
Later.

#2

I’m not sure what you mean, but the whole point of using quadtrees for frustum culling is to cut away nodes that will not be renderes asap. When rendering a quadtree test if the root node is in the view frustum (nearly always of course). If it is recurse on the 4 root children, checking all 4 nodes in turn. That way, nodes and their subtrees not in the view will be discarded as soon as possible.

  • elias
#3

thanks for reply - I guess I was not making myself clear - it is the actaull method for searching a node I am concerned with. Once the tree is built and I am to find node which is to be rendered. SO my question is what is the most efficient way of finding a node in quatree. I saw some c++ based code and and the way they were searching for a node was to have array which was storing reference of each newly constructed node - and then they basically go through that array and search for node. I was thinking storing that reference might be a waste - search function can be done recursively … which way then is more efficient then …I hope I am making more sense now :slight_smile:

#4

Why would you search for a node? I’m guessing the C code was really storing the tree in an array, but that makes no difference to the algorithm for traversing and rendering the tree.

  • elias
#5

why would I be searching for a node? …I create quadtree and it it loaded into memory … then when it comes to finding which leaf node (being Shape3D - having its own BranchGroup and reference to patch holding geometry and texture ) is to be included I am going through tree find them and those are then attached to a main BrachGroup …it is already working - I was just wandering if there is a better way for a search … basically my question is more about manipulation of data structures then graphics …

#6

if you mean “to be rendered this frame” when you say “included” there is a better way, namely the recursive way to traverse a quadtree. How is your quad tree built, data structure wise?

  • elias
#7

I use a rescricted fixed-lenght quadtree … it is actually quite primitive to construct such a structure and I imagine there are better ways to attack this problem but the reason I decided for this approach is I have easy (maybe only for me) way of handling heightmaps…see I am using for some portion of terrain more then 2 heightmaps being referenced by one leaf node - reason is I am trying to have a tunnel through mountain - that part is not done yet I am trying to figure out tringulation of such a geometry … later on I wanna move from static tree to something like CLOD described by Roettger http://wwwvis.informatik.uni-stuttgart.de/~roettger/