Tree of 3d bounding boxes
Moritz Moeller
libkdtree at virtualritz.com
Tue Sep 30 13:22:47 UTC 2008
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
More information about the libkdtree-devel
mailing list