Octrees for raytracing

I think this paper might be worth a look (can''t quite remember if it''s the right one, it sounds like it but could be wrong).

Solution to case 2: test both spaces.

The to octtree node encompasses all of your scene. Traverse it recursively. If a ray passes through a box of the octtree, evaluate it (ie is a ray pases through its children, evaluate them etc...). If you reach the bottom, test for ray collisions.

The intersection closest to the origin of the ray is "the" intersection. If you are evaluating a node further away than your current closest intersection, skip it.

I think that solves all of your problems.

---

[ Galactic Conquest | Bananas | My dead site | www.sgi.com | Goegel ]

Hi Xori.

While I cannot help you directly with the octree, I can suggest something else. I used a uniform voxel grid as acceleration for my ray tracer. The uniform grid uses exactly the same idea as the octree, except all the regions of space are the same size. Because of that, you can use something like the bresenham line drawing algorithm to very quickly determine which voxels the ray will pass through. This makes the traversal extremely fast (you don''t need to
advance a tiny amount and perform 3d intersection tests to check which neighbour was entered, as you are suggesting for the octree).

I can post more details if you are interested.

By the way, the uniform grid is extremely fast. My render times went from > 1 hour to < 1 minute.

shadow

Thank you all for your replies.

shadow_bobble: I would indeed be interested in extra details. I have heard of a method I believe is similar to yours (referred to as SEADS - spatially enumerated auxiliary data structure). I was thinking of octrees because uhm... I like tree data structures (yes I'm sure that sounds silly)... but if SEADS works as well as you say it does, I would enjoy giving that a try. I have seen reports on the performance of SEADS from the late '80s and early '90s which describe the memory requirements of SEADS as "prodigious" but I'm sure that can be kept at reasonable levels especially given the low expense of memory. If you don't want to post everything/anything here, my email address is in my profile.

EDIT: The server my email is on is going to be down until Jan 1... sorry :-/

[edited by - Xori on December 30, 2003 5:41:18 PM]

Hi Xori. I don''t mind posting info here. :-)

Ok. So I didn''t actually make a voxel class or anything. My "voxel grid" data structure was an array of pointers to STL sets. I index into this array with i,j,k essentially treating
it as a 3D structure. Each set contains pointers to polygons
that are in the region of space (a small cube or voxel) corresponding to position i,j,k.

As pre-processing, you need to bin the polygons into these sets. This is just a bunch of cube/polygon intersection tests for the cube centered at i,j,k. Graphics gems has code for
the cube/polygon test (i think book 3). If you can''t get it,
just let me know and I can help.

You don''t need to test a polygon against every voxel. Just test against voxels that overlap with the polygons bounding box (the indices for these voxels correspond to min_i..k and max_i..k in pseudo-code below).

So I have a loop that goes:

for(each polygon in scene) {
 find bounding box of polygon;
 find min_i,min_j,min_k,max_i,max_j,max_k;
 for all voxels between (min_i,min_j,min_k) and 
 (max_i,max_j,max_k) {
    perform cube/polygon intersection;
    if (intersection) add polygon pointer to set (i,j,k);
}

}

Let me know if you understand all that Xori, then i''ll post the next piece about firing rays quickly through this structure. I know it''s a lot to digest. :-)

shadow

No problem understanding - lay it on me.
Only difference is that in my system (in addition to models) I have renderable solid objects for easy CSG operations (spheres, torii, cylinders, solid convex polyhedra). It''s not as efficient with this objects as it is with small-polygon based objects, but nonetheless, I use a similar method - build a bounding box with faces orthogonal to the CCS axes and use these bounds to test where they will be placed in my SEADS structure.

Please continue...

Ok great!

So next step is firing rays. This part is maybe a little harder to understand, so ask any questions if you need to.

Let's assume the ray origin is inside your voxel grid. To understand this part, it is better to think of the voxel grid as a series of equally spaced axis aligned planes the ray will be crossing. What we need to do is find the t value for the first 2 ray/plane intersections for each axis.

In the diagram below, assume there is a ray moving from R0 to the right and slightly down. I tried to draw it below but it isn't very good. Anyway, first do the X axis. Find the t values for the ray intersecting planes Px1 and Px2. Subtract the first t value from the second. The answer you get is a floating point constant for the X axis for this ray. it is the ray-space distance from one voxel to the next down the X axis.

Do the same to get one constant each for the Y axis and the Z axis. diagram:

         Px1       Px2
---------------------
| R0 --__ |         |
|         |         |
|         |         |
|---------|---------| Py1
|         |         |    
|         |         |
|         |         |
|---------|---------| Py2

So when you go to move from one voxel to the next you use these numbers to check which direction to move. It's easier to understand if I just use some numbers for the 2D example.

In the diagram above, let's say the ray crosses plane:

Px1 at t = 1.2
Px2 at t = 2.8
Py1 at t = 3.2
Py2 at t = 7.0

so the x axis value is 2.8 - 1.2 = 1.6
and the y axis value is 7.0 - 3.2 = 3.8

Ok so let's say you've checked the current voxel and you didn't find an intersection.

First move
----------

You want to move to the next voxel. The ray-space distance to the first X crossing is 1.2, and to the first Y crossing is 3.2, so of course we move to the next voxel on the X axis.
Since we chose to move on X, we reset the X axis value to 1.6.

Second move
-----------

Let's say we didn't find anything in this voxel either, so we need to move again. We know it is 1.6 units to the next X crossing, and (3.2 - 1.2) = 2.0 units to the next Y crossing. Why minus 1.2? Because that's how far we moved down the ray when we made our first move. So since 1.6 is closer, we move down X again.

Third move
----------

Didn't find anything in this voxel either, so we need to move again. We know that once again it is 1.6 units to the next X crossing, and (2.0 - 1.2) = 0.8 units to the next Y crossing, so we're going to move down Y axis this time since it is closer.
Since we moved down Y, we reset the Y axis value to 3.8.

Then on the next move we'll choose X again at 1.6, etc.

Do you get it? It's EXTREMELY fast since you're just doing subtractions and MIN operations to decide which way to move.

let me know if anything isn't clear (or if anything *is* clear. hehe :-)

shadow





[edited by - shadow_bobble on December 30, 2003 11:10:12 PM]