Archived

This topic is now archived and is closed to further replies.

lekki

bsp or kd-tree

Recommended Posts

Hello I write my own raytracer. Please tell me what is a easier data structure to implement BSP tree or KD - tree ? lekki

Share this post


Link to post
Share on other sites
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!"

Share this post


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

lekki

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
Hi
Please give me a hint how to build tree from list of my objects.
ive got binary tree implementation


lekki

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites