Invisible wrote:
>>> Before anybody else asks... is there a good article somewhere that 
>>> explains what BSP is, and why it's good?
>> 
>> 
>> http://en.wikipedia.org/wiki/Binary_space_partition_tree
> 
> Just says that BSP involves recursively subdividing space and storing 
> the chunks in a binary tree. Doesn't really explain why this would be 
> useful for the purpose of raytracing.

put simply it's a fast way of finding what objects occupy a given region of
3d space irregardless of the origin and direction of the ray being shot. each
leaf node of a tree represents a particular (possibly overlapping) volume and
contains a list of all objects that potentially occupy that volume (in terms
of their bounding boxes).

so, if we have a start and end point of a ray, and then determine which nodes
the ray crosses through, we have available a list of all objects that it can
possibly intersect. as a general rule, the fewer objects per node the better,
though there would be a point where the time taken to iterate a deep tree may
exceed the time taken to test the bounds of each of the objects in a higher-
level node with multiple objects.

in the ray-tracing community there has for some time been some argument over
the various merits of the BVH (our standard bounding method) vs BSP, with
some folks being strongly pro-BSP, and others usually in the middle (there
don't seem to be a lot of anti-BSP'ers out there:). There's little doubt that
BSP is a very useful technique, but IMO BVH (bounding volume hierarchy) isn't
as bad as some folks seem to think - POV-Ray has done quite well with it for
a long time and it's quite memory-efficient.

-- Chris

Post a reply to this message