I've updated the BSP tree patch with several performance tweaks and
support for meshes.  It also has a much better defined API for adding
support for other object types.  Also I've run it though a significant
number of scene files to collect performance statistics.

The patch and statistics are now available on a web page:
http://povplace.addr.com/bsptree/

Andrew

Post a reply to this message

"Andrew Clinton" <ajc### [at] uwaterlooca> wrote in 
news:pan### [at] uwaterlooca:

> I've updated the BSP tree patch with several performance tweaks and
> support for meshes.  It also has a much better defined API for adding
> support for other object types.  Also I've run it though a significant
> number of scene files to collect performance statistics.

I found your page very interesting, complete and I really appreciated the 
torough comparison. Definitely well done.

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.

I hope your patch will be considered for inclusion in the MegaPOV 
experimental version and, why not, in a future POV version.

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

Alessandro Falappa

Post a reply to this message

> 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

"Andrew Clinton" <ajc### [at] uwaterlooca> wrote in
news:pan### [at] uwaterlooca: 

> 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.

If I were you I would change the naming just to make sure to avoid 
confusion when looking for algorithms and insights in the literature.
I noticed that you have also a "competitor" ;-), and that you've already 
discussed a bit on your respective implementations, any thought of 
"merging your results taking the best from both"?

> 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). 

Thanks.
That's why it's better to leave to the user the option to tune some 
parameters of the spatial data structure and to choose the old one.

--
Alessandro Falappa

Post a reply to this message

>
> > 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.
>
> If I were you I would change the naming just to make sure to avoid
> confusion when looking for algorithms and insights in the literature.

Well, its not always referred to as a KD tree in the literature, for
example:
http://www.acm.org/jgt/papers/HavranKopalBittnerZara97/

The algorithms in Mental Ray do indeed use a KD tree (at least according to
a reference in the paper: http://www.cgg.cvut.cz/~havran/phdthesis.html) but
they refer to it as a BSP tree nonetheless.  I remember seeing other
references to raytracers using orthogonal or axis-aligned BSP trees but
don't have them on hand.

> I noticed that you have also a "competitor" ;-), and that you've already
> discussed a bit on your respective implementations, any thought of
> "merging your results taking the best from both"?
>

That would be an interesting idea, though I'm not sure how practical.  Since
we both seemed to implement from the same paper there is much overlap in the
implementations.  IMHO, my current implementation at least has a more
modular and flexible interface.  His patch has a more efficient construction
phase but allocates larger arrays.  My previous testing also seemed to show
that my patch has better rendering time performance, though we really need
an impartial judge to do the comparison and analysis :)

Post a reply to this message

> <dsf> wrote in message ...

Sorry, that would be me (Andrew Clinton) - the reader settings are screwed
up :)

Post a reply to this message

<dsf> wrote in news:40b0fc9f$1@news.povray.org:

> 
>>
>> If I were you I would change the naming just to make sure to avoid
>> confusion when looking for algorithms and insights in the literature.
> 
> Well, its not always referred to as a KD tree in the literature, for
> example:
> http://www.acm.org/jgt/papers/HavranKopalBittnerZara97/

I see. They call it an "orthogonal BSP tree".
Could you kindly send me, if you have it, an electronic version of that 
paper (PS, PDF, any format...) or point me to a place where I can download 
it? In the former case my address is alessandro(at)falappa(dot)net.

> That would be an interesting idea, though I'm not sure how practical. 
> Since we both seemed to implement from the same paper there is much
> overlap in the implementations.  IMHO, my current implementation at
> least has a more modular and flexible interface.  His patch has a more
> efficient construction phase but allocates larger arrays.  My previous
> testing also seemed to show that my patch has better rendering time
> performance, though we really need an impartial judge to do the
> comparison and analysis :) 

Well I meant you could try to merge your codebases, make a unified 
interface: I believe that two developers working together are more 
powerful than one (as teached by the Extreme Programming techniques)!

Cheers.

Alessandro Falappa

Post a reply to this message

>> 
>> Well, its not always referred to as a KD tree in the literature, for
>> example:
>> http://www.acm.org/jgt/papers/HavranKopalBittnerZara97/
> 
> I see. They call it an "orthogonal BSP tree".
> Could you kindly send me, if you have it, an electronic version of that 
> paper (PS, PDF, any format...) or point me to a place where I can download 
> it? In the former case my address is alessandro(at)falappa(dot)net.
> 

You can download a copy at the top of the page:
http://citeseer.ist.psu.edu/havran98fast.html

Post a reply to this message