> From a cg purist programmer point of view (and as you point out in the 
> introduction) I would not define your structure as a BSP-Tree but as a Kd-
> Tree because with BSP-Tree I mean a structure that can divide the space 
> along arbitrary planes (not only axis aligned) and that oblige to split 
> geometry that crosses those planes boundaries.
> 

You're right that it is more specifically defined as a KD-Tree.  It would
be a fair amount of work at this point to fix all the references so I've
left it as BSP-tree.  It seems that BSP trees also have a third definition
and that is that the splitting plane is axis-aligned AND it is put in the
center of the cell it is splitting.  If there is enough interest in the
patch I could correct the naming.

> 
> Could you please comment on why the shells7.pov scene is so badly managed 
> by the Kd-Tree structure?

The scene has very large numbers of overlapping objects (spheres).  The tree
degenerates a a small number of nodes with very long object lists.  The
slowdown is probably caused by the large number of object bounding boxes
that are intersected and then sorted before testing the contained objects for
intersection.  For scenes like this the BSP tree is not a very appropriate
data structure (although there are some improvements that could be made
but possibly at the expense of performance on more ordinary scenes).

Post a reply to this message