Tree of 3d bounding boxes

[Moritz Moeller]

Sylvain,

thanks heaps for the quick answer!

>> Could I e.g. just treat 3d bounding boxes as 6-dimensional points?
> 
> Yes! You can!
> 
> However range searches have to be treated very carefully. You need to
> swap the ranges coordinates to perform a search of bounding box.
> However you will not be able to find intersecting bounding boxes
> without modifying a bit the algorithm of range search. So you have to
> tell me what kind of operation you wanna do with the KD-tree.

Basically I'm populating a city- and landscape with buildings & flora 
(mostly trees).
If you care, this is for a movie. The whole thing is a photorealistic CG 
shot, offline rendered with a RenderMan-compliant renderer. The setting, 
is in ancient Japan (ca. 700 BC) and this is a big city (for that time 
anyway), surrounded by rice fields, mountains and dense woodlands.

To be able to render this, I can't send the data all at once (I estimate 
it around half a terabyte). I need to be able to render this on machines 
with <=4 GB of RAM. :)

The common solution is to send a bounding hierarchy (aka the KD tree). 
The leaves are the bounding boxes of the the buildings, the flora, etc.

So I do need to send the tree's cells and subcells as bounding boxes 
themselves.
The renderer will then call me back for them as it starts rendering a 
part of the image that intersects one of these bounding boxes.

So my thinking was along these lines:
1 Preparation
   1.1 Send the KD tree all the bounding boxes for the houses, flora &c
   1.2 Call optimize()
   1.3 Serialize the tree to disk

2 Rendering a frame
   2.1 Load "root" cells of tree from disk and send to renderer
   2.2 Renderer cracks open cell and calls me back
     2.2.1 send sub-cells of that cell to renderer
     2.2.2 go to 2.2

Serializing the tree in a way that allows me to read is level by level 
is another problem I have to solve, maybe the lib already has an access 
point for this?

I basically need to be able to traverse the tree from the root myself.
I need to get the bounds for each cell of the 1st level of the tree. 
Then feed these to the renderer. Then I need to get the sub-cells (not 
bounding boxes themselves), stored in that cell once the renderer cracks 
the cells open that I sent it first.

I only need the leaf level (i.e. the actual bounding boxes), when the 
renderer asks me to give it the data with a granularity higher than the 
size of the smallest cell (farthest branches) in the tree.

As far as I understand, most people use KD trees to find something 
quickly (implicitly). I need to do the opposite and explicitly feed the 
whole tree, cell-by-cell to the renderer, as it asks for it.
Only when it cracks open the last level of cells that actually store the 
bounding boxes, I need to send it the data (e.g. some 3D model of a 
building or some tree [as in: wood, not KD!] or bush that is stored on 
disk).
Of course this is still faster than sending all data but the main point 
here is keeping memory use well bounded.

This is why I said I was unsure if this lib was the right tool for the task.

Hope that all makes sense.


Cheers,

Moritz