|
Octree Traversal Question submitted by (31 August 1999)  |
Return to The Archives |
 |
 |
|
| I've been playing around with some realtime voxel ray-tracing stuff, and I ran into a problem: given a ray and an octree level (8 ajacent equal-sized cubes), what is the fastest way to find an in-order traversal of the cubes that the ray passes through (you can assume that the cubes are in some convenient place, say from -1 to 1 in all axes, since I can perform a transform on the ray to get the cubes in place)? I tried an algorithm that was optimized for large a*b*c voxel sets, but I only want 2*2*2. I'm thinking there's a way to do it with a lookup table of some sort, but I haven't been able to figure it out yet. Thanks for your help. | ||
 |
 |
 |
|
|
|
I've done this with a simple line-drawing algorithm, tuned for a
3-dimensional line. Each cube is then your "3D pixel" (voxel) and you step
from voxel to voxel at the cost of only a few adds. You'll need to be careful when writing this code, to maintain full precision (think sub-pixel accuracy in voxel-space.) Response provided by Paul Nettle |
||
|
|
|
This article was originally an entry in flipCode's Fountain of Knowledge, an open Question and Answer column that no longer exists. |