Quick quad tree Q | GameDev.net

ZealousEngine · 2006-05-25T12:47:42+00:00

Im trying to cull a 1kmx1km area into 16x16 sub sectors. I dont have a quad tree class, but rather I was hoping this could be done with some clever looping and a simple 2d array (16x16). I tryed to write it out, but ended up coding each 'layer', resulting in a HUGE block of code. Is there no way to do a simple, elegenat 'quad tree' cull without a complex class? ie just a simple loop that determines if …

Yes. You could easily represent a fixed-size & fixed-depth quadtree with an array. But you'll still have methods associated with the quadtree for insertions, search, traversing, so you'll probably want to wrap it into a class. The total number of nodes in the tree are: 1^4 + 2^4 + .. + (depth-1)^4, if you want to access node n:s children you do: 4*n + i (i = 1, 2, 3, 4). Culling is done as usual by starting at root n = 0, checking if it is intersecting the frustum, if so check recursivly the children else stop traversing that branch, and so on.

Topic Locked