Quote:Original post by _goat If I cand find the PDF by nVidia I will, but it basically said that Octrees were preferable because, due to their shallowness.
Shallowness is a fake issue. If you want a shallowness tree, use a single-cell tee ;)
What kind of KD-Tree exactly is considered to be the best please ?
Quote:Original post by Woodchuck What kind of KD-Tree exactly is considered to be the best please ?
I think it depends on the ray tracer implementation and the scene. In some cases you want to isolate the objects by surface area (to guarantee the number of tests is similiar between rays), in others you want to isolate empty spaces (to guarantee you are testing as few objects as possible). Hope this helps,
Quote:Original post by Woodchuck What kind of KD-Tree exactly is considered to be the best please ?
I think it depends on the ray tracer implementation and the scene. In some cases you want to isolate the objects by surface area (to guarantee the number of tests is similiar between rays), in others you want to isolate empty spaces (to guarantee you are testing as few objects as possible). Hope this helps,
Agreed: adaptive bounding volume hierarchies are the way to go for dynamic scenes.
Quote:Original post by jvff The point for spatial subdivision is to separate what is viewable and what can be ignored.
Well they are also useful in finding spatially neighboring regions for things like collision detection, etc. Thus it's nice to have a BVH that supports neighbor access without too much traversal (ex. octtrees can be bad for this as neighboring cells can require one to traverse ALL the way up and ALL the way down the whole tree...).
Kd-trees are considered the fastest ray casting structure for static geometry.
This link provides a PhD thesis with information on multiple structures for ray shooting with the different characteristics of the algorithms implemented. http://www.cgg.cvut.cz/~havran/phdthesis.html Like everything in Computer Science you might disagree with some of this results, but in reality the best way to deal with this is to implement different spatial partitioning algorithms yourself and get performance results.
There is very little literature on kd-trees, and it is hard to find good papers on them.
The main reasons why kd-trees are faster are because: 1. If built correctly they maximize the empty spaced traversed which reduces traversal time. 2. If designed correctly they can be VERY hardware friendly (The books "Graphics Programming Methods" and "Real-Time Collision Detection") have some details on how to do so.
Kd-trees can be very expensive to build but very cheap to traverse. The Siggraph 2005 notes on Real Time Ray Tracing have a good presentation on Kd-trees.
Note that Kd-trees can be succesfully used on games for ray casting on static geometry (not for rendering), and IMHO there is not a single spatial structure that works well with dynamic and static geometry.
It depends on so many factors that saying "the fastest" is pointless.
For a system where you can to trivial comparisons, AND can build an optimal BSP outside of your performance constratints, AND your lookups fit the BSP search model, then they can be optimal for search time.
For a system where you are examining zones or are working with dynamic data inside zones, AND you can generate kd trees outside your performance constraints, AND you can trivially compute the zone(s) that an object lies in with a simple formula, then a kd-tree can be optimal for search time.
kd tree has a benefit that you can directly compute the zone, no lookups required. There is a tradeoff of space, and some search operations are extremely difficult.
bsp trees have the benefit that they match binary trees and will give search results very quickly, consume relatively little memory, and work very well with static data.
The two trees can be searched in roughly the same way; the performance from each depends on how you use them.
Kd-trees ARE BSP-trees with partitioning constraints on axis aligned planes.
And the conditions in which kd-trees perform faster than other data structures are: - Static geometry (Geometry does not move or change shape) - Queries used are for ray shooting only - Implemented on some modern computer architectures with some kind of processor cache
This also assumes that: - You can build the tree offline - You are going to be spending lots of time casting rays against static geometry which makes the time spent building trees negligible
Like most spatial data structures you can come up with a scene that generates a horrible kd-tree and makes traversal very expensive. But this is true for every single spatial partitioning data structure.
I would not use Kd-trees (Or BSPs in general) for dynamic geometry, or for broad phase collision detection. For games I would use it as a paritioning data structure for the static geometry. More common is to use kd-trees on global illumination renderers that are based on ray shooting algorithms.
I have not seen a single cosmological simulation that used BSP trees.
Cosmological simulations use methods of approximating the result of N-Body integration on a system.. and generally with *extremely* large N.
As such they do not concern themselves at all with rendering issues, but instead with the much broader stroke of interactions and transitions between (in the case of tree's) volumes that are dynamically changing.
Only two notable cosmological algorithms use tree structures, and those two structures are KD-tree's and Oct-tree's.
