# Octree traversal for raytracing

This topic is 4152 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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:
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

I can not see anything wrong with this algorithm, however it requires to this high amount of time. Is there anything faster running and easy to implement? I know I could use a kd-tree, but time is limited ;-) Thanks, Enrico [Edited by - Enrico on May 21, 2007 11:47:36 AM]

##### Share on other sites
Quote:
 if node is leaf: for all primitives: if ray intersects primitive: return true return falsefor eight child nodes: if child node and ray intersects child node's AABB: if ray intersects child node: return truereturn 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".

##### Share on other sites
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

See this paper.

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by phantomusIf the kd-tree compiler is the problem, you may try mine (updated today):http://ompf.org/forum/viewtopic.php?t=438It 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 :)

##### Share on other sites
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.

##### Share on other sites
Quote:
 Original post by JoeJMaybe 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.

##### Share on other sites
Quote:
Original post by Yann L
Quote:
 Original post by JoeJMaybe 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.

##### Share on other sites
Quote:
 Original post by Yann LSee 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;

1. 1
2. 2
Rutin
18
3. 3
4. 4
5. 5

• 9
• 14
• 9
• 9
• 9
• ### Forum Statistics

• Total Topics
632922
• Total Posts
3009216
• ### Who's Online (See full list)

There are no registered users currently online

×