See what's going on with flipcode!

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.

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved. Please read our Terms, Conditions, and Privacy information.