How to Learn Amanatides–Woo Fast Voxel Traversal: 3D DDA, tMax/tDelta, Grid Crossings and Robust Ray Marching

Wait, What?

A ray can cross a million-unit scene without taking a million tiny steps.

The Amanatides–Woo fast voxel traversal algorithm solves a deceptively practical problem: given a ray moving through a regular 2D or 3D grid, which cells does it cross, and in what order? A naïve ray marcher repeatedly advances by a small distance and asks which cell it is in. That can miss thin cells, do redundant work, or force you to choose an arbitrary step size. Amanatides–Woo instead jumps exactly from one grid boundary to the next.

For students, it is a beautiful bridge from coordinate geometry to production graphics. For professionals, it is a lesson in turning continuous motion into a discrete event sequence with a tiny, stable inner loop.

Quick Answer

Learn it through ray parameterisation → grid indexing → step signs → first boundary distances → tDelta → tMax → repeated boundary selection → tie handling → bounds and termination → floating-point robustness → production testing. The central invariant is simple: tMaxX, tMaxY and tMaxZ always tell you the ray parameter at which the next boundary in each axis will be crossed.

1. Start with the job the algorithm actually owns

Amanatides–Woo is a traversal algorithm for a uniform spatial grid. It does not test ray–triangle intersection, decide which surface is visible, or perform arbitrary path planning. Its job is narrower and therefore extremely useful: enumerate the grid cells intersected by a ray in front-to-back order.

That distinction prevents collision with the existing Möller–Trumbore article, which owns ray–triangle intersection, and with pathfinding material such as A*, D* Lite, Theta* and Jump Point Search. A voxel traversal is not searching for a cheapest route. It is following one already-defined geometric ray through a regular lattice.

2. Rebuild the continuous ray first

Represent a ray as:

p(t) = origin + t * direction

where t ≥ 0. If the grid cell width is one unit, the current cell is obtained from the floor of each coordinate. For non-unit voxels, transform into grid coordinates first or divide by cell size consistently.

Before touching the fast traversal, practice with a 2D ray. Draw an origin at (1.2, 2.4), choose direction (0.8, 0.3), and mark every vertical and horizontal grid line it eventually crosses. The algorithm is nothing more than an efficient way of predicting which of those crossing events comes next.

3. The three pieces of state

For each axis, the algorithm needs three values.

• step: +1 if the ray moves toward larger cell indices, −1 if it moves toward smaller indices, and 0 if it never moves on that axis.
• tDelta: how much the ray parameter t increases between successive crossings of parallel grid planes on that axis.
• tMax: the t value of the next boundary crossing on that axis.

If voxel size is 1 and the x component of the ray direction is dx, then:

tDeltaX = abs(1 / dx)

and similarly for y and z. If an axis direction is zero, its next crossing is effectively infinity because that boundary will never be crossed.

4. Why tMax is the real insight

Suppose the ray is currently inside voxel x = 3 and travelling in the positive x direction. The next vertical boundary is x = 4. Solve the ray equation for the t at which the ray reaches that boundary. That is tMaxX.

Do the same for y and z. Whichever tMax is smallest identifies the first boundary encountered. If x wins, increment the x voxel index by stepX, then add tDeltaX to tMaxX. The next x-plane crossing has now been scheduled.

while voxel is inside grid:
    visit(voxel)

    if tMaxX < tMaxY and tMaxX < tMaxZ:
        voxel.x += stepX
        tMaxX += tDeltaX
    elif tMaxY < tMaxZ:
        voxel.y += stepY
        tMaxY += tDeltaY
    else:
        voxel.z += stepZ
        tMaxZ += tDeltaZ

The original 1987 paper highlights how small the inner loop can become: moving from one voxel to its neighbour requires only a couple of comparisons and one addition for the chosen axis.

5. Work one ray by hand

Use a 2D grid first. Let origin = (0.25, 0.40) and direction = (1.0, 0.5). The starting cell is (0, 0). The next x boundary is x = 1, so tMaxX = 0.75. The next y boundary is y = 1, so 0.40 + 0.5t = 1, giving tMaxY = 1.2. Because x wins, the next cell is (1, 0). Now add tDeltaX = 1.0, making the next x event 1.75. The y event remains 1.2, so y wins next and the ray enters (1, 1).

Trace six or seven cells this way before coding. If a learner cannot predict the next winning tMax on paper, a 3D implementation will feel like unexplained arithmetic.

6. Handle negative directions deliberately

The first boundary depends on direction. For positive x movement, the next boundary is the right edge of the current cell. For negative movement, it is the left edge. That sounds trivial until an origin lies exactly on a boundary and a floor operation places it in a neighbouring cell that does not match your intended half-open interval convention.

Write down the convention before implementation. A common choice is to treat voxel cells as half-open intervals. Then test positive and negative directions from points just below, exactly on, and just above a boundary.

7. Entry into the grid is a separate problem

If the ray origin is outside the voxel volume, first intersect the ray with the grid’s axis-aligned bounding box. Start traversal at the entry point. Do not scatter special cases throughout the DDA loop. Separating ray-box clipping from grid traversal keeps the algorithm easier to reason about and test.

8. Ties are not a footnote

A ray can hit a grid edge or corner, meaning two or three tMax values are equal. A strict if/else chain may step along only one axis and then visit a cell the ray touches only at a boundary, or may produce application-dependent omissions. There is no universal tie policy because the correct answer depends on what “intersects a voxel” means for the application.

Professional implementations choose and document one of several contracts: step every tied axis simultaneously; emit all supercover cells touched by the ray; or use a deterministic half-open convention that assigns boundary contacts to one side. Test diagonal rays such as (1,1,0) and (1,1,1) explicitly.

9. Zero components and infinities

If dx = 0, the ray never crosses an x plane. Setting tDeltaX and tMaxX to positive infinity is often cleaner than branching inside every loop iteration. But avoid creating NaNs through expressions such as 0 * infinity. Initialise zero-direction axes separately.

10. Complexity is output-sensitive

The traversal performs constant work per crossed voxel, so the runtime is O(K), where K is the number of visited cells. That is the right complexity to teach. Saying “it is O(N)” is ambiguous because N might mean total voxels in the world, ray length, or number of objects. The algorithm does not inspect untouched cells.

11. Numerical robustness changes the production version

Floating-point arithmetic introduces several edge cases:

• origins exactly on voxel planes;
• very small direction components that create enormous tDelta values;
• ties that are mathematically equal but differ by one ulp;
• large world coordinates where grid indexing loses precision;
• termination at the grid boundary or at a finite ray length;
• negative zero and sign handling.

Do not “solve” all of these by adding a random epsilon everywhere. Epsilons can move a ray into the wrong cell. Prefer explicit coordinate conventions, careful entry-point computation, well-defined tie rules and targeted tolerance only where the contract requires it.

12. From beginner implementation to professional engine code

A good development sequence is:

• Stage 1: 2D grid, positive direction only.
• Stage 2: arbitrary signs and zero components.
• Stage 3: 3D traversal and a finite grid bounding box.
• Stage 4: tie/corner policy and deterministic tests.
• Stage 5: per-voxel occupancy tests, early termination and duplicate-object suppression.
• Stage 6: SIMD/GPU-friendly data layout, branch behaviour and cache profiling.

Notice that optimization comes after the traversal contract is proven. Fast wrong cell enumeration is not a graphics optimization.

13. A testing matrix professionals should actually run

• axis-aligned rays in all six 3D directions;
• 45° diagonals and exact corner hits;
• origins inside and outside the grid;
• origins exactly on every type of boundary;
• very shallow angles;
• zero-length and nearly zero-length directions;
• finite segments that stop inside a voxel;
• random rays compared against an independent geometric reference;
• large coordinate offsets;
• deterministic traversal order across platforms where required.

14. How to learn it efficiently

For novice programmers, start with a prediction task rather than a blank editor. Give a small grid and ask which cell comes next. Then run a reference trace. Investigate the three tMax values. Modify one direction component. Only after that should the learner build the loop. This follows the PRIMM pattern: Predict, Run, Investigate, Modify, Make.

Use subgoal labels such as Locate current cell → Schedule next boundary on each axis → Select earliest event → Advance one or more axes → Reschedule crossed boundaries → Check termination. Research on subgoal-labelled worked examples shows that explicit procedural subgoals can improve programming problem solving. Fade the hints as competence grows, and include deliberate debugging tasks because a 2024 meta-analysis found a meaningful overall effect for debugging interventions in computational-thinking education.

Common failure states

• Using fixed-distance ray marching and calling it voxel traversal.
• Computing tDelta correctly but initializing tMax to the wrong boundary.
• Forgetting that negative directions cross the opposite cell face first.
• Dividing by zero without a defined infinity policy.
• Ignoring edge/corner ties.
• Starting outside the grid without a ray-box entry calculation.
• Stopping on voxel count rather than a geometric exit condition.
• Adding epsilons until tests pass instead of defining boundary ownership.
• Comparing performance without counting how many voxels each method actually visits.

Practice ladder

• Beginner: trace ten cells by hand in 2D.
• Foundation: implement 2D traversal for all direction signs.
• Intermediate: extend to 3D, outside-grid origins and finite segments.
• Advanced: specify and test edge/corner tie semantics and compare with a brute geometric oracle.
• Professional: integrate traversal into a sparse voxel renderer or occupancy system, profile branches/cache behaviour, and test determinism across CPU and GPU implementations.

Learning Hall boundary

This article owns uniform-grid ray traversal with Amanatides–Woo / 3D DDA logic. It builds on geometry fundamentals but does not replace Möller–Trumbore ray–triangle intersection, Bresenham rasterization, pathfinding, spatial-index design or general ray-tracing architecture.

Evidence and further reading

• John Amanatides and Andrew Woo, “A Fast Voxel Traversal Algorithm for Ray Tracing,” Eurographics 1987. The original paper describes the grid traversal and its very small per-voxel update cost.
• For programming pedagogy, see PRIMM, subgoal-labelled worked examples, and the 2024 meta-analysis of debugging interventions.

Professional rule: you understand Amanatides–Woo when you can derive tMax and tDelta from the ray equation, state your boundary/tie contract, and prove that every emitted cell is reached in nondecreasing ray parameter order.