if node is leaf:
for all primitives in this leaf:
if ray intersects primitive:
return true
return false
for eight child nodes:
if child node and ray intersects child node's AABB:
if ray intersects child node:
return true
return false
Octree traversal for raytracing
Author
Hello,
I am currently trying to use my octree for some ray tracing. The traversal of the octree requires an unexpected amount of time, taking up to 5 seconds for 2500 rays :-( The number of primitives per leaf is limited to max. 10.
The intersection algorithm, called recursively starting at root node:
Quote:
if node is leaf:
for all primitives:
if ray intersects primitive:
return true
return false
for eight child nodes:
if child node and ray intersects child node's AABB:
if ray intersects child node:
return true
return false
First, it seems to me you are checking for ray/node collision twice, once against AABB and then against the node (presuming transformed BB). My opinion is you should keep the octree axis aligned and transform the ray instead (with the transformation inverse to that with which you'd transform the AABB). But maybe I got you wrong.
Also, I assume you mean "for all primitives in that leaf".
also, you might want to see this thread
http://www.gamedev.net/community/forums/topic.asp?topic_id=298074
I had had improved my kd-tree (kind of an octree, but you don't divide in halves, but instead where you think it's going to help the most) by a huge factor thanks to those guys. Ie it really matters (in such a tight loop) where you position ifs, etc. Don't have the code anymore though
http://www.gamedev.net/community/forums/topic.asp?topic_id=298074
I had had improved my kd-tree (kind of an octree, but you don't divide in halves, but instead where you think it's going to help the most) by a huge factor thanks to those guys. Ie it really matters (in such a tight loop) where you position ifs, etc. Don't have the code anymore though
If the kd-tree compiler is the problem, you may try mine (updated today):
http://ompf.org/forum/viewtopic.php?t=438
It emits the tree for an obj file in text format. After that, you can use Wald's paper to get the traversal up and running.
http://ompf.org/forum/viewtopic.php?t=438
It emits the tree for an obj file in text format. After that, you can use Wald's paper to get the traversal up and running.
Author
Quote:Original post by phantomus
If the kd-tree compiler is the problem, you may try mine (updated today):
http://ompf.org/forum/viewtopic.php?t=438
It emits the tree for an obj file in text format. After that, you can use Wald's paper to get the traversal up and running.
oh, Windows only :-(
I need something working on Windows, Mac OS X (PPC CPU) and Linux :-|
Yann, thanks for the paper, I am reading it right now :)
Maybe a bottom up method could be faster:
Search node for the ray origin; compute ray - node exit point; use it as entry point to find the next node...
This avoids recursion. Node searching is fast when using integer coords and bit math. Parent pointers or caching node history can improve search time further.
However - this is more difficult to impl. and discussion what is faster (bottom up or top down) is old, and without a clear answer.
Search node for the ray origin; compute ray - node exit point; use it as entry point to find the next node...
This avoids recursion. Node searching is fast when using integer coords and bit math. Parent pointers or caching node history can improve search time further.
However - this is more difficult to impl. and discussion what is faster (bottom up or top down) is old, and without a clear answer.
Quote:Original post by JoeJ
Maybe a bottom up method could be faster:
Search node for the ray origin; compute ray - node exit point; use it as entry point to find the next node...
That's exactly what the algorithm presented in the paper I linked to above does.
Quote:Original post by Yann LQuote:Original post by JoeJ
Maybe a bottom up method could be faster:
Search node for the ray origin; compute ray - node exit point; use it as entry point to find the next node...
That's exactly what the algorithm presented in the paper I linked to above does.
No, the paper is about top-down but describes both methods shortly:
"Bottom-Up Methods: Traversing starts at the first terminal
node intersected by the ray. A process called
neighbour finding is used to obtain the next terminal
node from the current one [Glass84, Samet89,
Samet90].
Top-Down Methods: These methods start from the
root voxel (that is, from the one covering all others).
Then a recursive procedure is used. From the
current node, its direct descendants hit by the ray
are obtained, and the process is (recursively) repeated
for each of them, until terminal voxels are reached
[Agate91, Cohen93, Endl94, Janse85, Garga93].
In this paper we introduce a new top-down algorithm..."
I've implemented both methods and for my case bottom up is faster (running on 100MHz ARM cpu).
I found alot papers about top down, but none about bottom up.
Author
Quote:Original post by Yann L
See this paper.
I have tried to implement this, but somehow the first step does not work:
My test scene has a AABB from (-2.5, -2.5, 0) to (2.5, 2.5, 2.5). The original ray has its origin at (-1, -1, 2.5) and points down in direction (-0.4, -0.4, -0.8). The paper says for negative directions the ray needs to be processed (section 3.4 in the paper). This results in an origin of (6.0, 6.0, -0.001) and a new direction of (0.4, 0.4, 0.8).
Calculating t1x, t1y and t1z as first step:
t1x = (2.5 - 6.0) / 0.4 = -8.75
The algorithm checks first if t1x is less than zero. This is the case and it exits. However, when using my previous slow version or a kd-tree the hit gets calculated correctly.
I am sure there must be an error in my implementation, but I don't see what might be wrong. I can't believe this algorithm has an error...
BBox &box = _rootNode->bbox;static const float SizeX = box.maxPoint.x - box.minPoint.x;static const float SizeY = box.maxPoint.y - box.minPoint.y;static const float SizeZ = box.maxPoint.z - box.minPoint.z;if(myRay.direction.x < 0.0){ myRay.origin.x = SizeX - myRay.origin.x; myRay.direction.x = -myRay.direction.x; a |= 4;}if(myRay.direction.y < 0.0){ myRay.origin.y = SizeY - myRay.origin.y; myRay.direction.y = -myRay.direction.y; a |= 2;}if(myRay.direction.z < 0.0){ myRay.origin.z = SizeZ - myRay.origin.z; myRay.direction.z = -myRay.direction.z; a |= 1;} float t0x = (box.minPoint.x - myRay.origin.x) / myRay.direction.x;float t1x = (box.maxPoint.x - myRay.origin.x) / myRay.direction.x;float t0y = (box.minPoint.y - myRay.origin.y) / myRay.direction.y;float t1y = (box.maxPoint.y - myRay.origin.y) / myRay.direction.y;float t0z = (box.minPoint.z - myRay.origin.z) / myRay.direction.z;float t1z = (box.maxPoint.z - myRay.origin.z) / myRay.direction.z;This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
