bsp or kd-tree

A BSP tree is a type of KD-Tree isn''t it?

You have to remember that you''re unique, just like everybody else.

Out of curiosity, what do you need a BSP Tree or KD-Tree for with a ray tracer? As soon as a ray hits an object it stops (Unless the object is suppose to be transparent) so all the back faces are removed and it''s depth sorted. Are you using it just to disregard objects that are not in the frustum? If thats the case and it''s not real time, couldn''t you just use a bounding box or bounding sphere to see if the object lies in the frustum?

-UltimaX-
Ariel Productions
|Designing A Screen Shot System|

"You wished for a white christmas... Now go shovel your wishes!"

I need BSP or KD tree to store objects on my scene. Currently i use
simpler recursive algorithm with a scen object list.

lekki

Hi,

i must say, i agree with python_regious. i even think they are the same.

Both are binary trees, and both get build up almost the same way (Except KD-trees get split right trough the points)

But i'd still say BSP trees are easier to implement Simply because there is more information on the internet



You can get a pretty high speed boost with BSP-trees in Ray-tracers. With ray-tracing without a BSP tree, you would check collision of the ray with every polygon in the scene, until you found the nearest one, normally. With BSP-trees, you could speed this up, since it would work similar to Hidden surface removal. Bounding boxes work fine too, but the experience i made, was always that BSP was faster.

good luck

[edited by - m1o1d1 on April 3, 2004 11:51:39 AM]

[edited by - m1o1d1 on April 3, 2004 11:52:14 AM]

Hi
Please give me a hint how to build tree from list of my objects.
ive got binary tree implementation


lekki

Cut space in half. Is object Right or Left?
Cut it in half again. Ask same question
Work that down to object level and thats a BST( I think.)

At least, if its not a BST, it should speed it up some.

lekki, use Google and search for BSP Tree FAQ, it should answer your questions and gives pseudo-c code to show basic implementation.

Yes, a Binary Space Partition (BSP) and a k-d tree are essentially the same beasts... however, in typical representations, the BSP splits each axis in a given order (e.g., x,y,z,x,y,z,x,...) and typcially along the midline of the region being split. A k-d tree makes no such assurance and usually splits the axis with the largest variance before splitting any other axis. The partition value is chosen so as to minimise some function of the variances of the two new regions. Of course, you can still just split axes in a given order in a k-d tree, and/or along the midline... but then you have a BSP.

Timkin

Here is an excellent review of several spatial partitioning data structures:
http://www.mpi-sb.mpg.de/~havran/DISSVH/phdthesis.html

In particular, the implementation of kd trees has some very useful pseudocode, which I stole for my ray tracer.

"Math is hard" -Barbie