Part VII · Speed · Chapter 26
Fewer and cheaper steps
A ray's time on the graphics card is its steps, and a step's time is the scene's answer at one point: the distance to every object, of which the nearest is kept. This chapter is three ways ShadyTracer pays less for that. It skips the objects far from a ray, behind boxes, and the copies of a row or a ring far from it. It makes a costly surface cheap away from itself, inside a shell. And it steps without asking the scene at all, from a grid of remembered distances. Each comes with what it saved on the user's cards, what it cost, and what was taken out again.
1Every object at every step
Sphere tracing, from chapter 2 (the march): a ray steps by the distance to the nearest surface (times 0.9, the step scale), and stops when that distance is below its tolerance. To know the nearest surface, the scene's function, which ShadyTracer writes from the scene tree (chapter 24), asks every object for its distance and keeps the smallest. So every step pays for every object, near the ray or not. Here is a shelf in the flat world (this tutorial's two-dimensional scenes): a floor, two plain discs, a rounded block, and two discs with a relief (chapter 3), a rough fine one (granite, left) and a broad smooth one (marble, right). Their bumps are too small to see at this scale; section 3 shows one up close. 48 camera rays take 1,021 steps; each step asks all six objects, and each relief asks its noise, four layers of it. In this page's costs (one plain shape's distance is 1, a layer of noise 4: a model's numbers, the caption says why), the noise is 84% of the work. In the Noise library, one of the scenes that come with ShadyTracer, its six reliefs were 89% of the time a sample took on the user's card (chapter 25).
A culling box around each object: before asking the object, ask how far the box is, which is cheap and exact. Nothing inside the box can be nearer than the box itself, so while the box is farther than a margin (ten surface tolerances), the object is skipped and the box's distance stands in for it: the scene answers with the nearest of the objects it asked, or the nearest skipped box if that is nearer still. The floor, which has no end, has no box. The cost falls from 38,798 to 12,545, about a third. Every ray ends where it did without the boxes; on the card, every picture with them was the same as without. On the user's Ampere card the Noise library ran 3.9 times faster with its boxes (216.6 against 839.8 milliseconds a sample).
Two things a box costs. Its test: 4,730 here, one for every boxed object (five: the floor has none) at every step. And sometimes a step: where a box stands in, the ray may step only as far as the box, not as far as the object would have let it (387 of the 946 steps here). On the plain discs and the block, the box's test costs as much as the shape it guards, and its step is shorter; on a relief it is far cheaper than the noise, and its step longer (a relief's own distance is divided by its slope bound everywhere). So since 0.34.0, only the dear (costly) objects get a box: the reliefs, and every group (a group is several shapes, or code, joined: never one plain shape). 907 steps, cost 12,208. On the user's Pascal card (chapter 25's GTX 1080 Ti), boxes that never culled cost a third more time on scenes of plain shapes (the showcase, the demo, Surface materials: scenes that come with ShadyTracer); boxes on the dear ones only were 13 to 15% faster than every box on the showcase, level on the demo, and 6% slower on the Noise library, where they still saved 72% against none. The user chose dear only.
One more turn. The reliefs today have a shell (section 3, drawn dashed here): far from its surface a relief costs no more than a plain shape. Switch it on: without boxes the shelf costs 10,702, and with boxes on the dear ones 11,471, 7% more. In this model, once the reliefs are shelled, their boxes no longer pay. Whether that is so on a card is not known: every culling measurement in the documents was made on the benchmark's frozen Noise library, whose reliefs have no shell. It is an inference, and the row that would test it (the shelled reliefs with their boxes and without) has not been run.
kit/steps.js): a plain shape's distance 1, a
box test 1, a layer of noise 4, set so the reliefs dominate as they did in the Noise library. Choose the boxes
and the shell; point at a ray to see its steps.2Only at the root
The boxes guard only the scene's top-level objects and groups, where they are joined by the plainest join there is: the nearest wins, a union. What the code does with a skipped object: it leaves the union, and at the end the nearest skipped box's distance caps the answer (if it is nearer, it is the answer). Why that is safe there: the answer is the smallest of the objects' distances; leaving one out can only make the smallest larger, and the cap brings it back to no more than the box's distance, which is no more than that object's own. So the answer is never more than the true distance, and a step is never too long; and the cap is above the margin, so the march never takes a box for a surface. A group is boxed as a whole. Here two discs, A and B, joined into a lens (an intersection: where both are), boxed whole at the root: the rays find the lens. Drag P: the dashed circle is what the lens's own formula answers there; where the box is skipped, the scene answers with the box's distance instead. Above the lens's top tip, as P starts, that is more than the formula's answer, 0.900 against 0.820, and still not more than the true distance, 0.901. The formula, the larger of the two discs' distances, is only a safe estimate: there it measures to the farther disc's circle, while the nearest point of the lens is its tip.
Now box B on its own, inside the join, as ShadyTracer never does. Where B's box is far, B is skipped and leaves the join, and the lens is left as A alone: A's whole round surface, where the lens has none. The lens's formula is the larger of two distances; leaving one out makes it smaller, down to 0 on A's surface, and no cap can raise it. Every ray stops on that surface, 1.2 short of the lens. A subtraction (one shape carved out of another) is a larger-of-two too. The code's comment says it in one line: "in a subtraction, an intersection or a blend, a lower bound on a child is not a lower bound on the result".
A blend fails another way. Two discs a little apart, blended (chapter 3's smooth union): the blend builds a bridge between them, and the bridge lies outside B's own box. Skip B there, and the bridge is gone: two rays pass straight through where it stands, and a third (the second from the left) slips past its edge to stop on A, 0.04 lower. At P, just above the bridge, the scene now answers 0.150 where the bridge is 0.054 away: a ray from P aimed at the bridge's nearest point would step past its surface. This is also why a group's box is padded: a smooth union can reach beyond what it joins, by at most a quarter of the blend's size (its k, chapter 3) each time it joins, and the padding adds that much.
3A surface that costs less from afar
Chapter 3 built a relief: a disc whose distance has noise added, four layers of it, and then divided by a slope bound (a Lipschitz bound) so the march does not step through a bump. As the benchmark's frozen scene has it, every step pays for the noise and every step is divided, however far the ray is from the bumps. Fourteen rays at one relief: 318 steps, every one of them paying.
The division is the dearer half. The bound here is 1 + 0.17 × 17.2 ÷ 1.875, about 2.6: 0.17 is the bumps' height over their width. 17.2 is how steep the four layers of noise can be together: 4.3 for one layer (measured); each further layer half as tall and twice as fine, so just as steep; four of them at their steepest in one place, 4 × 4.3. And 1.875 is the four layers' strengths added, 1 + ½ + ¼ + ⅛: the relief's height is shared among the layers by strength, so the first layer's is the height ÷ 1.875, and the slope bound is that over the width, times 17.2. So far from the bumps, where the disc's own distance would do, every step is 2.6 times shorter than it could be: the circles here, one ray's steps, against the dashed one, the room its first step really had.
The shell: the noise moves the surface by at most 1.386 times
its amount (a bound proved in noise.js), so beyond twice that from the plain circle, the circle's own
distance less that reach is a safe distance, with no noise and no division. 243 steps, 211 of them paying, and a
cost a third lower. On the user's Ampere card the shell made the Noise library 22.9% faster (156.0 against 202.3, the scene
without it timed again beside it in that run, whose first timing of it had read 216.6
ms a sample); timed by kernel in the next run, the march 38% faster and the shadow rays 33%. The note written
before that run expected most of the reliefs' cost to go. About a third of it went. The notes after it offered a
reason, as a hypothesis: the boxes had already skipped the steps far from a relief, so the shell saved only the
steps between a box's edge and the band, and the steps inside the band pay as before. The next run found the
rest of the reliefs' time where that predicts, in the kernels that march, not in shading.
And a smaller bound. 17.2 assumes four layers all at their steepest in the same place. A
search of this four-layer noise itself found 8.9 at most in 14.4 million points; with a quarter to spare, 11.2.
Divided by that, the steps are longer: 202 here. Both are measurements, not proofs: the proved bound is four
times larger and would take four times the steps. A bound too small would let a step pass through a bump, so a
test searches the noise for anything steeper and fails within a quarter of the bound (noise.test.mjs).
The relief keeps 17.2 until the benchmark's row for 11.2 has been seen and timed by the user.
4Steps without asking
A step needs the distance at the ray's point. The step cache remembers distances instead: a grid of cells over the scene's box, each holding the scene's distance at its centre. That distance is a ball with no surface in it, so a ray anywhere inside the ball can move to where it leaves the ball, without asking the scene. The cells are filled by a pass of their own before the rays are traced (since 0.33.0; at first a cell was filled the first time a ray passed through it, section 7), and filled again only when the scene changes (a camera move keeps them: a ball does not care where the camera is). Here the shelf, boxed and shelled as today, with about 1,024 cells (57 × 19 = 1,083: the grid is rounded up to whole cells, as the engine's is): the darker a cell, the nearer a surface to its centre. A few of the balls are drawn.
Each step, the ray first looks at its own cell's ball. If the ball would carry it at least a cell further, it goes, to where it leaves the ball, times the step scale; otherwise it asks the scene, as ever. Not to the ball's nearest edge, as sphere tracing would: anywhere inside a ball, its exit along the ray is a safe step, however far the ray is from the ball's centre (one is drawn). And never on the last of a march pass's 32 steps (chapter 22: the march kernel gives each ray up to 32 steps a round), because the pass ends by handing on what the scene's own answer at that last step found. 794 steps, 116 of them from the cache, and a tenth off the cost; every ray ends where it did without it. Point at a step to see its ball.
The second mode looks at the two cells ahead along the ray as well, and takes the farthest exit of the three balls: 755 steps here. On the user's Pascal card the cache, filled once, made the optics bench (a scene of lenses on pillars) 27% faster, the same scene written as data 19%, OpticsBench2 and the showcase 10%; the material test (6% faster) and the demo (4% slower) moved by less than that run could tell apart. On the dichroics scene, on the Ampere card, it changed nothing measurable. It is a developer setting, off by default.
Until 0.33.0 the cells were filled from the copy of the scene the rays march, the one with the culling boxes. Outside a relief's box, that copy answers with the box's distance, so the balls there stopped at the box, not at the relief (marked here). The user saw it in the renderer's view of the cells, which shows them in orange: "I see orange glow around objects but also around their boundingboxes". Every ball was still safe, and most of those around the boxes smaller: 879 steps here, against 794. The fill now asks the copy made for picking (finding what is under the mouse), which has no boxes.
5How ShadyTracer does it
The box's distance, and the margin:
Why only at the root, as the code generator says it:
The code it writes around each boxed object, and at the end of the scene's function the one line that lets the nearest skipped box stand in:
The line, at the end of the scene's function: if (CULL < abs(C.s.w)) { C.s.w = CULL; }
():
C.s.w is the scene's answer, the nearest distance found.
The same skipping works inside an array: a group whose children are drawn again at a list of places, its copies. The copies are joined to each other as the root's children are, nearest wins, so a copy far from the point can be left out and a lower bound on its distance kept in its place, exactly as a box stands in for a top-level object. Every copy used to be asked at every step. The test scene is a floor under 256 copies of one small lamp: 16 rows of 16, the rows standing round a ring. On the user's Pascal card it took 281 ms of marching a sample, against 7 ms for the same floor under one lamp. Choosing which of the 256 lamps to aim at (chapter 14) cost nothing measurable; asking every lamp at every step cost all of it.
Now a row of copies, or a ring of them, is asked only in a window: the few copies around the one closest to the point. The closest is found without asking any: along a row it is the copy at the point's place along the row, round a ring the copy at the point's angle about the ring's axis. From there the copies are taken one at a time on each side, until on each side the next copy's bound is beyond the margin, and that copy's bound stands in for every copy past it ():
- A row: the distance to the next copy's box. The copies are one box moved the same distance at a time, and the distance to a box moved along a line only grows on each side of its smallest value, so no copy past the stopping one is nearer.
- A ring: the distance to the sphere round the next copy's box, which only grows as the copies turn away from the closest one. (A ring's copies are turned as well as moved, so their boxes do not line up the way a row's do; a sphere does not mind being turned.) But never less than the distance to the band every copy lies in: the ring of room at the copies' distance from the axis and at their height along it. Above or below a flat ring of lamps, each sphere bulges out of the lamps' thin layer and comes close, while the band is as thin as the lamps; the band is the farther of the two, so its distance is the longer step. Both are lower bounds on the distance to the same copies, so the larger of them is one too.
On the same card the 256 lamps now take 51 ms of marching a sample, against 270 ms with every copy asked in the same run (the 281 above was another run; on this card one build read up to a fifth apart from run to run). A row of 16 marches as fast as the same 16 lamps placed by hand. The first version was slower, not faster: section 7 says why.
A relief in its shell (the WGSL the relief group starts with, as text in JavaScript):
The step cache's step, and where the march takes it:
6Tricks and trade-offs
Each is stamped with how it is known; point at a stamp to see what it means.
Boxes: the Noise library 3.9 times faster, the plain scenes little either way. The fourth full
run, each culled row beside the same scene with its boxes off: the Noise library 216.6 against 839.8 ms a
sample, Surface materials −5.0%, the showcase −3.2%, the demo −13.2%, the Menger cubes −4.4%, materials +2.5%;
in GPU time in the fifth, the Noise library 3.95 times (the user's Ampere card, 2026-09-30,
docs/PERFORMANCE.md). The third run had read the other scenes 11 to 27% faster; the fourth found
those pairs inside the third's drift (chapter 25).
A box test costs about a plain shape. Boxes that never cull, against none: +31 to +37% GPU
time on Surface materials, the demo and the showcase in one run, +23 to +42% in the next two; the Noise library,
boxes measured, −74% (the user's Pascal card, Tests > boxcost, 0.33.5, 0.33.8 and 0.33.9,
roadmap/ARCHITECTURE.md).
One plain shape gets no box. An object whose code is one call of a closed-form shape (sixteen
of them: no loop, no noise) and whose material has no relief, or a light's face. Every group keeps its box.
Whether a lens or a frustum costs more than its box test is not measured: the benchmark's plain shapes are
spheres, rounded boxes and cylinders (codegen.js, ONLY THE DEAR ONES; plainshape.js).
The shell's edge is twice the reach out, and a little more. Twice, so a ray stepping from the
edge moves at least the reach and a grazing ray does not crawl; plus the surface tolerance times the slope bound
and one, so a hit and the points its normal is measured from never straddle the edge, where the distance jumps
(modifiers.js, the relief's comment). A material's relief has a shell too, written by the code
generator: beyond two amplitudes, the distance less the amplitude.
The step cache: filled once, a gain on the optics benches and the showcase. Against the cache
off: the optics bench −27%, the optics bench as data −19%, OpticsBench2 −10%, the showcase −10%, the material
test −6%, the demo +4%, differences under about 7% within what that run could tell apart (the user's Pascal card, Tests > stepcache,
0.33.1, roadmap/ARCHITECTURE.md); on the dichroics scene +1.4% (the user's Ampere card, 0.61.2,
docs/PERFORMANCE.md). A fill costs 0.2 to 3.3 ms on the scenes written as code, 26.1 ms on the optics bench
as data, paid again whenever anything but the camera changes.
Off means not there. With the cache off, its lookups, its uniform test and its binding are
not in the kernels at all; turning it on builds them again (wavefront.js, COMPILED IN ONLY WHEN
ON, 0.29.0). The user asked for exactly that: "make sure that all these different options, even when turned off,
dont impose an overhead".
A step that asks only the distance. Every step of the march asked the scene for its whole answer
(each shape's normal, turned into the world, the material, the solid the point is in) and read one number of it.
Since 0.79.0 the renderer's march is built against a second add_new and fold that keep the
nearest surface's distance and nothing else, and the surface kernel asks for the whole answer once, at the ray the
march stopped, on a trip of the loop it already had (scene_api.js, FOLD_DIST; wavefront.js,
THE HIT ITSELF). The distance is the same expression, so the steps are the same: on a software GPU every camera ray
ends in the same place, bit for bit, and so does every pixel of the whole picture
(builder/test/marchdist.gpu.mjs). The Optics page keeps the full march: its shading reads the march's
hit directly.
Shadow rays ask only the distance too. A shadow ray asks whether anything is in the way, which
is a distance, and since 0.79.0 the occlusion kernel is built against the same distance-only fold
(wavefront.js, prog_occlude's distOnly). One shadow ray asks more: one aimed at a glowing surface
takes the glow of whatever blocks it (chapter 16). That kernel cannot answer it, so it marks the ray where it was
blocked and leaves it in its slot in the queue; a small kernel holding the whole scene asks the material there
before the next round (prog_occlude_emit), and is sized to no work at all when nothing was marked.
On a software GPU every shadow ray's light is the full kernel's, bit for bit, and every round's queue the same
(builder/test/occludedist.gpu.mjs).
A step that asks only the distance: the march 8% to 79% faster, the sample 2% to 35%. GPU time a
sample, before against after, on the user's Pascal card (Tests > marchdist, 2026-10-25,
docs/PERFORMANCE.md): the march on the optics bench 49.3 against 10.2 ms, the showcase 17.3 against
8.8, dichroics 177.8 against 144.0, the Noise library 70.7 against 58.8. The surface kernel's one look more a hit
takes part of it back -- on dichroics 21 of the 34 ms -- so the whole sample fell 35.5% on the optics bench, 12.4% on the showcase, 2% to 4.5% on dichroics,
the Noise library and the Menger cubes, and not at all on the material test (+1%, within that run's drift).
Shadow rays on distance only: occlusion 8% to 83% faster on five scenes. GPU time a sample, the
occlusion kernel and its resolve together, before against after, on the user's Pascal card (Tests >
occludedist, 2026-10-25, docs/PERFORMANCE.md): the optics bench 29.3 against 4.9 ms, the Menger
cubes 22.6 against 17.7, the showcase 6.5 against 5.3, dichroics 34.6 against 32.0. The Noise library read 40.9
against 52.4, in a row where the march, which the change does not touch, was 21% slower too: not explained.
Boxes on shelled reliefs. In this page's model, a relief in its shell costs about its box test when the ray is far, so its box saves nothing and shortens steps. Not measured on a card: the culling rows all ran the frozen Noise library, whose reliefs are unshelled. What would test it: the benchmark's shell row with its boxes and without.
7What went wrong before
- A window that made it slower. Section 5's window, as it was first built, marched the 256
lamps in 1007 ms a sample on the user's Pascal card, against 281 ms with every copy asked. Two things were
wrong, and each was found by measuring, not by reasoning:
- Each step cost more. The loop fetched each copy's place through a
switchon its number, and in a window that number differs from pixel to pixel. A graphics card runs neighbouring pixels on one stream of instructions, so where their cases disagree it runs the cases one after another. A test that kept the switch but asked every copy marched 43% slower (twice, on that build) than the old loop over every copy, which used the same switch but had every pixel on the same copy at the same moment. Now a window's copy is worked out from the first copy: moved along the row, or turned round the ring. - The rays took more steps. The boxes are measured by asking the scene, at every point of a grid laid over it, which object's surface is nearest. Every object answers with its tag, a number naming it, and the points close to an object's surface make its box. But every copy of an object has the same tag. So an object inside an array was measured as all its copies at once: the 4 cm lamp came out 2.2 m across, and the sphere round "one copy" over 3 m across. A ray near that sphere could step only to its edge, so rays crept past it in short steps. Counted in a software copy of a graphics card: 47 steps a camera ray with the window, against 22 without. Now the scene also says which copy a surface belongs to, each point is put into its own copy, and the bounds are section 5's. Counted again: 30 steps against 21. (Without the window the count fell too, from 22 to 21. The array's own culling box is its copies' boxes put at every copy, and each of those had been all the copies already, so it came out more than twice the ring's size.) The window can only add steps, since a bound standing in is never longer than the true distance; it still takes more, 30 against 21, but each step asks a few copies, not 256.
- Each step cost more. The loop fetched each copy's place through a
- The orange shell. Section 4, as it happened: the step cache filled from the copy with the culling boxes, its balls stopping at the boxes. Safe, and slower than it needed to be; only the picture of the cells showed it ().
- A cache that never ran. The page's renderer wraps the engine in an outer layer, and that layer's way to set the cache's box replaced the engine's, then called itself until the stack ran out. In 0.23.0 and 0.24.0 the step cache never ran in the page at all, while every test passed, because every test drove the engine alone (). The repository's oldest failure: true for the only caller there was.
- A box that left out part of its group. The boxes are measured by sampling the scene on grids, a coarse one widened while something is missing, then finer ones. The widened search kept only its own findings, and the optics bench's thin cylinders, found by the first search, by none after: each lens pillar's box was measured without them, and a culled ray could step past them: "0.61 by the box where the surface was 0.23 away" (). Now a group whose part found no surface has no box at all.
- "Can't say" read as "none". The benchmark's view of the boxes could not say which parts had found no surface, and the code asked it in a way that took silence for "nothing missing": every object on the benchmark's lens-assembly rows was culled by boxes that might leave a part out. Now that question is refused unless it can be answered ().
- A relief's box was its plain shape. The box measurer credited the bumps to the group that makes them, not to the object, so a relief's box was its shape without them, up to the relief's amount too small: harmless in a drawing of the boxes, a clipped object once they culled ().
- The lazy fill. The cache's first version filled a cell the first time a ray passed through it, during the march; 0.33.0 added the fill of every cell before the trace, and the fill from the copy without boxes. Filled once before the trace was faster, by 6 to 22%, on every scene in both of the cache's ways of looking but one: one scene, in one of the two, by 2%, within the run's noise. (Until version 0.67.3 the comment said "on every scene"; this chapter found the run it cites saying otherwise, and the comment now says what the run does.) The lazy fill was no faster than no cache on four of six; it was taken out in 0.41.0 ().