This page runs from a web server, not from a file: in the repository run python3 -m http.server 8000 and open http://localhost:8000/tutorial/.

Part I · Seeing with rays · Chapter 2

Shapes as distances

A ray has to find where it meets a shape. ShadyTracer's shapes are not made of triangles; each one is a formula that answers a single question: how far is it from here to the nearest surface? That answer turns out to be all a ray needs.

1A distance for every point

Take a circle with its middle at c and radius r. How far is a point p from it? Measure the distance to the middle, and take away the radius. That is one subtraction. Drag the probe: the circle drawn around it is as large as it can be while still only touching the shape. Nothing at all is inside that circle.

Now drag the probe inside. The distance becomes negative: it says how deep the point is. Positive outside, zero exactly on the surface, negative inside. A formula like this is a signed distance field, SDF for short. The thin lines are places with the same distance, like the height lines on a map; the bold one is the surface itself.

Two shapes together? Ask each one and keep the smaller answer: the nearest surface is the nearer of the two. Drag the circle and the box by the circled crosses in their middles and watch the lines rearrange. That is a union, and it is one comparison. Cutting one shape out of another, or keeping only where two overlap, are just as short (Building and bending shapes).

Or melt them together: a smooth blend takes a little off the smaller distance wherever the two are close, and a fillet, a rounded web of material, fills the corner between them. Move the blend slider to widen it, and drag the shapes: pull them apart and the fillet stretches, then lets go. It adds a little material wherever the two shapes are close, not only in the corner: look under the box, where it bulges slightly towards the circle. This is the very formula ShadyTracer uses, in its flat form.

The mathsA circle, a union, a blend

d_circle(p) = |p − c| − r

d_union = min(d₁, d₂)

h = max(k − |d₁ − d₂|, 0), d_blend = min(d₁, d₂) − h²4k

|p − c|: the length of the line from the middle to the point, by Pythagoras
|d₁ − d₂|: the same bars around a single number mean its size without its sign: |−3| = 3
k: the blend slider: how far the blend reaches. Where the two distances differ by more than k, h is 0 and nothing changes
h² / 4k: how much is taken off: nothing where h is 0, most (k/4) where the two distances are equal, and in between a curve chosen so the surface bends smoothly from one shape into the other, with no crease

In 3D the circle becomes a sphere and nothing else changes: |p − c| is then the length in three dimensions. A box takes a few more lines, shown in section 6.

A distance field. Drag the probe: the circle around it reaches the nearest surface, and no surface crosses it. Inside a shape it is drawn red and dashed: there the distance is negative.

2Sphere tracing

Here is the trick. A ray (one per pixel, as in chapter 1) starts at the eye and wants to know where it first hits anything. Ask the field for the distance at the start. Nothing is closer than that, in any direction, so the ray can safely move that far along its own direction. At the new point, ask again, move again. Each circle in the figure is one question, and the ray hops from the middle of one most of the way to its edge (0.9 of the way: section 3 is why). Near a surface the distances shrink, the hops get shorter, and the ray creeps up to it.

This is sphere tracing (in 3D the circles are spheres). It needs nothing from a shape but its distance. Drag start, and aim, which only sets the ray's direction, and move the ball, the block and the wall by their circled crosses.

A ray aimed straight at a surface needs only a handful of steps. The expensive ones pass close to a surface without hitting it: every distance is small, so every step is small. This ray slips just past the corner of the block: count its steps.

A ray marched through a small scene. Each circle is one distance asked; the ray moves 0.9 of the way to its edge (the step scale) and asks again.

3Close enough, and not too far

Why does the ray creep up to a surface and never quite land on it? Head-on at a flat wall, one step of the whole distance would land exactly on it. But the nearest surface is usually not straight ahead: it is off to one side, or curved away, so each step covers only part of the way to where the ray will meet it. And each step is 0.9 of the distance, which leaves a tenth behind every time. Either way, the distances shrink step by step without reaching zero.

So the march stops when the distance's size (leaving out its sign) is below a small number, the surface tolerance. Make it large and rays stop early: a ray that passes close to an edge counts as a hit, so edges grow fat and thin gaps close up. At a tolerance of 0.1, the grazing ray from before stops at the corner of the block, which it really passes. Make it tiny and rays need more steps to arrive. ShadyTracer chooses it from the scene's size, and never smaller than the computer's numbers can tell apart at that point (Numbers have grain).

Why move only 0.9 of the distance, the step scale, and not all of it? With a perfect formula, the whole distance is safe. But some formulas are a little too large in places (section 5), and the computer's numbers are slightly off too, so 0.9 leaves a margin, paid for with a few more steps. Set the step scale above 1 and the margin turns into an overshoot: here the first long step carries the ray over the thin wall, and after that every step lands a little inside whatever it approaches. Inside, the distance is negative, and the march goes by its size, as it must to march through glass (chapter 10): so a ray that has stepped inside does not stop there, it marches on, out of the far side. This one goes through the ball as well and out of the scene. The pixel shows the sky where it should show the wall, and nothing in the result looks broken.

And when there is nothing to hit? A ray that is outside the scene's radius, a circle around everything in the scene, and moving away from its middle can never come back, so the march stops and the ray is given the sky. ShadyTracer asks where the ray is, not how far it has gone (a ray that bounced around inside for a long way has not left). That is called an escape. The scene's middle is the point (0, 0, 0), so the test is two sums: the ray's distance from it, squared, is x² + y² + z²; and the ray points away from it when its position and its direction, multiplied part by part and added up, give more than 0 (the dot product of the two arrows).

The same march. A large tolerance counts a near miss as a hit; a step scale above 1 jumps the thin wall and the ball; a ray past the scene's radius, heading out, escapes.

4In 3D: where the steps go

The same march in three dimensions makes a real picture: one ray per pixel, sphere traced into a small scene of a floor, a ball, a box and a ring, and lit by the sun, with a shadow ray from each hit towards the sun to see whether anything is in the way. The blue at the top is the sky, above the horizon; everything below it is the floor. This is the march as ShadyTracer does it, written out in JavaScript and run on your computer's processor instead of the graphics card, so it is small and blocky. Drag it to turn the scene.

Now show Steps per pixel: each pixel coloured by how many steps its ray took, pale for few, through blue, to red for many. Rays that go straight at a surface need only a few. The dark outlines round every shape are rays that pass just beside it: every distance they ask is small, so every step is small. The reddest band of all is the far floor just below the horizon, where the rays run almost parallel to it, and the sky just above it costs more than the sky higher up, for the same reason. Where a picture spends its time is decided by its edges and its grazing angles, not by how big things are. (Normals colours each pixel by which way its surface faces; chapter 4 is about those.)

With a step scale of 1.6, steps are longer than the distance says is safe. Look at the picture: the ball is nearly gone, only a rim left where rays meet it at a glancing angle, because every ray that meets it head-on steps inside and marches on until it comes out the far side; along the bottom, rays go through the floor in the same way and find a strip of sky beneath it. Back at 0.9 the picture is right again. Compare the readouts: being right costs nearly twice the steps.

A small scene sphere traced in 3D, a ray a pixel. Picture: lit by the sun. Steps per pixel: how many steps each ray needed. Normals: the direction out of each surface, shown as a colour (its x, y and z as red, green and blue). Drag to turn.

5The one rule: never too large

A true distance can never change faster than you move. Walk one step away from a wall and you are at most one step further from it; walk one step along it and you are no further at all. That is the whole reason sphere tracing works: the distance at a point is a promise about every point around it. And it ties the two halves of this section together: a formula that is zero on the surface and grows by at most one for each unit you move can never be more than the true distance, because the true distance is how far you have to move to reach that zero.

So if a formula ever says the nearest surface is further than it really is, the ray can step through it. Here is an easy way to get that wrong: take the circle's formula and squeeze it sideways, by half, to make an ellipse. The shape looks right. But moving one unit across now changes the formula by two: it grows twice as fast as any distance can, and claims twice the room. The red circles claim to be empty and are not, and the very first step lands inside the shape. Squeeze it harder and the ray steps right over it.

The fix is to know how much faster than a real distance the formula can change (here: two, one over the squeeze) and divide by it. The steps get shorter, the ray takes one more, and every circle is truly empty: it stops at the surface. (Its last steps are tiny, right at the surface. This figure steps the whole distance, a step scale of 1, to show the formula on its own.) A promise that a formula never changes faster than a true distance is a Lipschitz bound. A formula that keeps it is called safe, or a bound; one that equals the true distance is exact.

The mathsDividing by the slope

The squeezed formula is the circle's with x replaced by x / s, for a squeeze s (here ½):

f(x, y) = √( (x/s)² + y² ) − r

Along the line y = 0, outside the shape, this is f = |x|/s − r. Move a step a along x, and f changes by a/s, which is 2a when s = ½. A true distance changes by at most a. So f can be up to 1/s times too large. Multiplied by s, it never is:

f_safe = s · f

The number you divide by (here 1/s) is the formula's steepest slope, its Lipschitz constant. Dividing by more than you need is safe but slow; dividing by less is fast and wrong.

ShadyTracer holds every shape to this rule, and says in the code which kind each one is:

It is also why ShadyTracer's scene builder only scales a shape by the same amount in every direction (): a shape stretched more one way than another is this ellipse. And it is why shapes that bend space, like a twist, shrink their steps to stay safe (Building and bending shapes).

A circle squeezed into an ellipse. Its raw formula claims too much empty space (red circles), and the ray lands inside; divided by its steepest slope, every circle is truly empty.

6How ShadyTracer does it

The figures above use the help's own 2D distance functions, which are written to match the renderer's 3D ones in sdf.js:

In the renderer, sphere tracing is the march kernel, written in WGSL, the language of programs for the graphics card. The GPU runs it for thousands of rays at once, each on one of its workers (a thread), and each runs this loop. sceneAt asks the whole scene for its distance and which surface it is; the distance is hit.s.w. marchTol is the tolerance at this point; UB.stepscale is the 0.9.

Two details matter for later chapters:

The march takes at most 32 steps a round (). A ray that needs more is put back on the list and continued in the next round, so that all the GPU's workers stay busy with rays that still have work. That is the idea of wavefront path tracing. The comment's "32 of them per march iteration" is this same 32: one distance asked a step. (maxiter, the limit on all the rounds together, is a different number.)
It uses the absolute distance, abs(hit.s.w), the distance without its sign. A ray inside glass is inside a shape, where the distance is negative, and it marches to the far side the same way (Glass).

7Tricks and trade-offs

Each is stamped with how it is known; point at a stamp to see what it means.

Leaving the scene is a test, not a shape. Every scene used to contain a huge sphere around everything, the sky dome, so that a ray going nowhere would still hit something. That sphere was part of every distance the scene computed, at every step of every ray. Now the march checks, once a step, whether the ray is outside the scene's radius and pointing away from its middle: a few multiplications (two dot products, in the code). The comment in the excerpt above calls it "strictly cheaper".

Steps of 0.9. The step scale defaults to 0.9 (): a small margin against a formula that is very slightly too large, paid for with somewhat more steps. In the march figure, compare the step count at 0.9 and at 1.0 for the same ray.

Longer steps, taken back when wrong. Over-relaxed sphere tracing steps 1.2 to 1.6 times the distance, and checks each time whether the new point's empty circle still overlaps the last one; if not, the step was too long, and it goes back and takes a normal one. ShadyTracer does not do this; its performance notes list it as an idea whose gain "is not known" here. It would cut steps in open space; what it costs near surfaces in these scenes has not been measured.

Normals for free. The same shapes that give a distance also give the direction out of the surface, so a hit needs no extra questions to find which way the surface faces. Without that, the renderer asks the scene three more times per hit, once for each direction (Which way is up).

8What went wrong before

The sky dome. Described above: a sphere in every scene, costing a little at every step of every ray, replaced by a two-line test.
Two well-known formulas that broke the rule. Both came from Inigo Quilez's list, the one this chapter recommends. His pyramid gave distances too large inside the pyramid, by up to half its base, in 15 to 46% of the solid. His parabola's sign flipped near the curve in the GPU's 32-bit numbers (f32), so the whole axis read as surface. Both were found by measuring every shape against an independent reference, and replaced. That is no reason to read his list less: it is where ShadyTracer's shapes come from. It is a reason to measure every formula you take, from anyone.
sign(0) is 0. The GPU's sign function returns 0 for 0, not ±1. A normal is an arrow meant to be exactly one unit long, and that made normals of the wrong length on an axis. ShadyTracer's shapes use a comparison instead. Small, and the kind of thing only a test finds.

9Try it

In the march figure, aim the ray straight at the ball and count the steps. Then aim it so it just misses the top of the ball. Why so many more?
Set the step scale to 1.0 and to 0.5 for the same ray. How does the count change? Then find a ray where 1.0 and 1.8 hit different surfaces.
In the last figure, find the strongest squeeze (the smallest number) for which the raw formula still works for a ray through the middle. Then move the ray's start up or down. Is it still safe?
In ShadyTracer's Help, the page on signed distance functions has the same field to play with, with more shapes.