Tree of 3d bounding boxes

Sylvain Bougerel sylvain.bougerel.devel at gmail.com
Tue Sep 30 14:29:05 UTC 2008


On Tue, Sep 30, 2008 at 9:22 PM, Moritz Moeller
<libkdtree at virtualritz.com> wrote:
> 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.

When I was doing gaming programming classes I learnt about compressed
AABB tree. There's book that talks about it, or it's "Game Programing
Gems 2". (from the top of my head)

Anyway, what you're describing sounds a lot like managing an AABB
tree. This kind of structure has the double adventage to be compact
and easy to write. It seems to have all the kind of operations you
need.

Regrettably, the KDtree won't be able to do the job for you. That
because *the children Bounding Box can be outside of the parent
Bounding box*, in a kd-tree. I'm sorry I didn't really understand that
requirement at first, that's why it's contradictory with what I have
said before.

I wrote an AABB tree myself, but it's been a long time, and I'm not
sure where I put the code. I'm going on holiday tomorrow, so I wont be
able to check, but if you're ready to wait until next week. I can try
to dig up my back up CD. I might not have it anymore.

So, in the end, I don't think you should use a KD-tree here.


>
> Hope that all makes sense.
>
>
> Cheers,
>
> Moritz
>



More information about the libkdtree-devel mailing list