Splitting triangles/multiple references in KDtrees back
(L) [2007/07/25] [Zakalwe] [Splitting triangles/multiple references in KDtrees] Wayback!Hi guys, I'm writing a small literature review on Ray Tracing Acceleration Data Structures. One of the questions my supervisor has asked me based on my initial draft is "why do people not split the triangles on the splitting planes rather than reference them in both nodes subtrees". The answer is quite obvious in terms of build time because of the overhead of the splitting and the creation of new object due to the splitting. Unfortunately a literature review is not somewhere you can make statements without backup. Does anyone know of a paper presenting empirical results? Even Havran's comprehensive review doesn't touch this.
(L) [2007/07/25] [Phantom] [Splitting triangles/multiple references in KDtrees] Wayback!Well there simply isn't any reason for performing the actual split, is there? The only use for split triangles is during construction itself.
_________________
--------------------------------------------------------------
Whatever
(L) [2007/07/25] [Zakalwe] [Splitting triangles/multiple references in KDtrees] Wayback!I'm not arguing there is. It's merely a question that was asked of me. The answer is obvious but saying "it is obvious that..." in such a review is frowned upon.
(L) [2007/07/26] [toxie] [Splitting triangles/multiple references in KDtrees] Wayback!i don't think that there is a paper or phd that describes this (because it's trivial).
but there are basically some good reasons not to split them:
a) memory: 4/8bytes (index) vs. 36 (full triangles)
b) numerical precision: splitting them may have rays slipping "between" the newly created triangles (whereas before you just had one single triangle) AND between these and the neighbouring triangles (as they will not necessarily share vertices anymore)
c) cache pollution during traversal: you will fetch more triangles during traversal and you cannot do mailboxing tricks (if anyone still uses them) for large triangles
_________________
That's the trouble with computers, always think in black and white. No aquamarines, no blues, no imagination.
(L) [2007/07/26] [Zakalwe] [Splitting triangles/multiple references in KDtrees] Wayback!Do you think this can count as personal communication with two respected member of the RTRT community?
@misc{BikkerWachter:2007:Personal,
author = {Jacco Bikker and Carsten W{\"a}chter},
howpublished = {Personal communication},
year = {2007},
}
(L) [2007/07/26] [toxie] [Splitting triangles/multiple references in KDtrees] Wayback!why not.. if this supervisor of yours is THAT picky, feel free to cite me.
_________________
That's the trouble with computers, always think in black and white. No aquamarines, no blues, no imagination.
(L) [2007/07/26] [greenhybrid] [Splitting triangles/multiple references in KDtrees] Wayback![SMILEY Applause]
_________________
[LINK http://xitrace.org/ xitrace.org] | [LINK http://greenhybrid.net/ greenhybrid.net]
I love the smell of freshly cooked images in the morning....Yummy.
(L) [2007/08/06] [toxie] [Splitting triangles/multiple references in KDtrees] Wayback!while writing my phd (which is no fun btw ;)) i just thought about that issue again..
why not actually split the triangles for real -only- for the construction as jacco already mentioned?
it would be much easier to
a) sort the triangles left and right
b) find out if some empty volume could be cut away, which in turn can be precisely determined (otherwise must be "guessed" as intersecting all triangles with the node bbox to find the borders is clearly too costly) and "thrown away" if necessary
c) determine the -real- surface area of the triangles inside a node
after the construction throw away the duplicated tris and use an inverse reference list to get the original triangle back instead (so only references have to be stored in the leafs as usual!).
_________________
That's the trouble with computers, always think in black and white. No aquamarines, no blues, no imagination.
(L) [2007/08/06] [Lynx] [Splitting triangles/multiple references in KDtrees] Wayback!Isn't that rather common to clip triangles on kd-tree construction? [SMILEY confused]
Note that it doesn't necessarily stay a triangle if you cut it with a plane...you can end up with a polygon of <insert correct number> of edges after several cuts...(i forgot the number...)
Of course you could tesselate to triangles again...but they still belong to the same original triangle so what would be the point of that...
(L) [2007/08/07] [Stereo] [Splitting triangles/multiple references in KDtrees] Wayback!This is exactly what I am doing in my kd-tree builder. After each subdivision step I clip triangles that straddle the splitting plane and use them in the next recursion step instead of the original tris. In case clipping yields polygons they are tesselated to triangles to keep everything homogenous.
An important thing is that only the original triangles will be included in the final kd-tree, which can easily be achieved by looking at the ids stored in the triangles. Using clipped triangles would of course not make any sense, as it would only increase the triangle count.
This clipping-on-the-go can be seen as an optimization of triangle clipping as it is described for example in Wald's O(N log N) paper. You don't have to clip triangles to all sides of the current node's bounding box, but clip them to the splitting planes as you build the tree.
- Stephan
back