I've been writing some code for efficient traversal in voxel spaces recently. Here's a visual comparison between the Bresenham line algorithm, and the Amanatides-Woo "Fast Voxel Traversal Algorithm". #gamedev #solodev #indiedev #customengine

At first I used it too, but unfortunately it’s too slow for big volumes and too rigid / expensive when it comes to skipping larger steps (like skipping 128/64/32 voxels etc), so only left it for small chunks where it works perfectly, and higher level is a traced tree

Good point. Indeed, per-cell traversal is an insufficient approach for sparse/big volumes. But I will address that with a multi-resolution grid and a lo-hi precalculation of the contents of each cell.

If you have an option to make mipmaps like Teardown did then HDDA can make sense, yes

I dunno what you're building there, but in any case, this might help 🤔

Thanks! This is part of a larger system I am building for terrain rendering.

Is there any difference between Amanatides-Woo and the DDA(Digital Differential Analyzer) Algorithm?

Somebody correct me if I'm wrong. My understanding is that DDA is any algorithm that incrementally steps through a line in a grid. Bresenham is a 2D, integer-only version. Amanatides–Woo traverses the 2D/3D cells pierced by the line segment between two floating-point endpoints.

I looked the termup and found a paper titled "A Fast Voxel Traversal Algorithm for Ray Tracing" it appears to be a variant of DDA

I was messing around doing a line of sight/lighting map and came up with a worse way of doing this but I thought it was interesting. Find the normal of the ray cast. Each voxel step, add the normal which is only 2 floating point adds with no branching.

The Bresenham line algorithm is so clean. Understanding how it works teaches you so much about efficiency

Oh i had the pleasure of doing 3D DDA recently too. Nothing fancy tho, just the basics...

Looks like line rasterizing 😅

That's what it is!