One of my favorite SDF techniques is domain repetition:
(def eye-center [35 82 62])
(def eyes (ball 39 | move eye-center | mirror x :r 10))
(def eye-angle [0 0 0])
(defn pupils [target]
(def left-pupil
(ball 15 | shade black | move [39 0 0]
| align x target
| move eye-center
))
(def right-pupil
(ball 15 | shade black | move [39 0 0]
| align x target
| move [-1 1 1 * eye-center]
))
(union left-pupil right-pupil))
(defn get-target [seed i]
(hash3 seed i | remap- + [0 0 2] | normalize))
(defn eye-target [seed]
(def base (t + hash 30 seed * hash 20 seed))
(def frame (floor base + 100))
(mix
(get-target seed frame)
(get-target seed (frame + 1))
(ss (fract base) 0.49 0.51)))
(def anim (osc t 7 | ss 0.2 0.8))
(union :r 50
(ball [100 150 100] | move [0 7 3])
| shade sky
| union (expand eyes 20 | move [0 1 -43]) :r 10
| subtract :r 10 eyes
| union
(eyes | shade white | union-color (pupils (eye-target $i)))
| union (box :r 17 [(ss p.y -44 44 17 33) 44 17]
| morph (ball [29 44 17])
| rotate x 2.92
| move [0 12 100]
| shade orange)
| tile: $i [(anim * 400) (anim * 500) (anim * 500)] :limit [(anim * 10000) 8 (anim * 10000)]
| union (ground -150 | shade white)
| scale 0.25
| scale (ss anim 0 1 1 0.2)
| rotate y 0.45 x -0.33 z 0.08)
It’s a great party trick that lets you render an infinite number of shapes in real-time, with soft shadows and ambient occlusion and all the other nice things that SDFs give you. It seemed like magic to me when I first saw it, and I suppose it still does – albeit in a different way.
The trick that makes this possible is that you aren’t evaluating “an infinite number of shapes.” As each ray marches through the scene, it only evaluates one shape at a time.
Let’s look at a 2D slice of that scene:
(def eye-center [35 82 62])
(def eyes (ball 39 | move eye-center | mirror x :r 10))
(def eye-angle [0 0 0])
(defn pupils [target]
(def left-pupil
(ball 15 | color black | move [39 0 0]
| align x target
| move eye-center
))
(def right-pupil
(ball 15 | color black | move [39 0 0]
| align x target
| move [-1 1 1 * eye-center]
))
(union left-pupil right-pupil))
(defn get-target [seed i]
(hash3 seed i | remap- + [0 0 2] | normalize))
(defn eye-target [seed]
(def base (t + hash 30 seed * hash 20 seed))
(def frame (floor base + 100))
(mix
(get-target seed frame)
(get-target seed (frame + 1))
(ss (fract base) 0.49 0.51)))
(def zed (osc t 5 10 25))
(union :r 50
(ball [100 150 100] | move [0 7 3])
| color sky
| union (expand eyes 20 | move [0 1 -43]) :r 10
| subtract :r 10 eyes
| union
(eyes | color white | union-color (pupils (eye-target $i)))
| union (box :r 17 [(ss p.y -44 44 17 33) 44 17]
| morph (ball [29 44 17])
| rotate x 2.92
| move [0 12 100]
| color orange)
| tile: $i [300 300 300]
| scale 0.25
| slice z zed)
Actually, that’s freaking me out. Let’s look at a simpler 2D scene, and you can trust me that this generalizes to more complex shapes:
(star 20 10 :r 1
| color (hsv (hash $i) 0.5 1)
| tile: $i [80 80])
Pretend that that’s a 2D slice of a 3D scene. Like, imagine that we’re actually trying to render this:
(star 20 10 :r 1
| shade (hsv (hash $i) 0.5 1)
| tile: $i [80 80]
| extrude z 20)
In order to render a 3D scene, we shoot rays out from the camera at different angles until they hit something. It’s just much easier to visualize this process in 2D:
(def scene
(star 20 10 :r 1
| color (hsv (hash $i) 0.5 1)
| tile: $i [80 80]))
(def line-start [-200 28])
(def line-end [68 64])
(def progress (t / 3 | fract | ss 0 0.5))
(def indicator (union
(line line-start (mix line-start line-end progress) 2)
(circle (mix -5 5 (ss progress 0.95 1)) | move line-end)))
(union
scene
(indicator | expand 1 | color black)
(indicator | color white))
But when we’re rendering SDFs, we don’t cast rays continuously like this – they don’t smoothly advance until they hit a shape. Since we know the distance field at every point, we use that information to decide how far to advance. Actual ray marching looks more like this:
(def scene
(star 20 10 :r 1
| color (hsv (hash $i) 0.5 1)
| tile: $i [80 80] :limit 5))
(def direction [1 0.13 | normalize])
(def line-start [-200 28])
(gl/defn :vec3 march [:int iterations]
(var at line-start)
(var dist 0)
(for (var i 0:s) (<= i iterations) (++ i)
(+= at (dist * direction))
(set dist ,(gl/with [q at]
(shape/distance scene))))
(return [dist at]))
(def iterations 15)
(def line-end (. (march (int iterations)) yz))
(def frame-base (fract (t / 15) * iterations))
(def frame (frame-base | floor | int))
(def inframe (frame-base | fract | ss 0.5 0.6))
(gl/def highlight-circle (march frame))
(def i-dist highlight-circle.x)
(def i-progress highlight-circle.yz)
(defn ray-point [progress]
(line-end - line-start * progress + line-start))
(def next-point (i-dist * direction + i-progress))
(def indicator (union
(line line-start (mix i-progress next-point inframe) 2)
(circle i-dist | shell 2 | move i-progress)
))
(union
scene
(indicator | expand 1 | color black)
(indicator | color white))
…except, you know, faster.
The radius of that circle is the value of the distance field at each point of the ray’s journey. The distance value means “what’s the distance to the nearest shape,” and during ray marching you can interpret that as “how far can I move in any direction before I hit something.” When you’re ray marching in 3D, it gives you the radius of the largest empty sphere of space around the current position of the ray.
The trick that makes domain repetition possible is that, in order to compute the distance field of an infinite number of shapes, you actually only look at one shape at a time. It’s not actually “the distance to the nearest shape.” It’s “the distance to the shape in the same ‘cell’ as me.”
That is, when we repeat this, we’re really breaking it up into cells, and only checking “the current cell:”
(def scene
(star 20 10 :r 1
| color (hsv (hash $i) 0.5 1)
| tile: $i [80 80] :limit 5))
(def direction [1 0.13 | normalize])
(def line-start [-200 28])
(gl/defn :vec3 march [:int iterations]
(var at line-start)
(var dist 0)
(for (var i 0:s) (<= i iterations) (++ i)
(+= at (dist * direction))
(set dist ,(gl/with [q at]
(shape/distance scene))))
(return [dist at]))
(def iterations 15)
(def line-end (. (march (int iterations)) yz))
(def frame-base (fract (t / 15) * iterations))
(def frame (frame-base | floor | int))
(def inframe (frame-base | fract | ss 0.5 0.6))
(gl/def highlight-circle (march frame))
(def dist highlight-circle.x)
(def ray-at highlight-circle.yz)
(defn ray-point [progress]
(line-end - line-start * progress + line-start))
(def next-point (dist * direction + ray-at))
(def indicator (union
(line line-start (mix ray-at next-point inframe) 2)
(circle dist | shell 2 | move ray-at)
))
(def ray-cell (ray-at / 80 | round))
(def scene
(star 20 10 :r 1
| color (hsv (hash $i) 0.5 (gl/if (= ray-cell $i) 1 0.25))
| tile: $i [80 80] :limit 5))
(union
(rect 40 | shell 1 | color white | tile: $i [80 80] :limit 5)
scene
(indicator | expand 1 | color black)
(indicator | color white))
And this works. For fairly regular, symmetric shapes, this works.
But part of the fun of domain repetition is that you don’t have to use regular shapes. You can do this with arbitrarily asymmetric shapes, or shapes that vary depending on the cell they’re in.
In fact I’ve been doing that in all of these examples: the stars are colored differently based on their cell coordinates. But we can vary their shape as well:
(defn make-scene [f]
(star r (r / 2) :r 1
| gl/let [r (10 * hash $i 10 + 10)] _
| rotate (hash $i 130 | remap-)
| move (hash2 $i 140 | remap- * 20)
| f $i
| tile: $i [80 80] :limit 5))
(def scene (make-scene (fn [$ $i] $)))
(def direction [1 0.13 | normalize])
(def line-start [-200 28])
(gl/defn :vec3 march [:int iterations]
(var at line-start)
(var dist 0)
(for (var i 0:s) (<= i iterations) (++ i)
(+= at (dist * direction))
(set dist ,(gl/with [q at]
(shape/distance scene))))
(return [dist at]))
(def iterations 15)
(def line-end (. (march (int iterations)) yz))
(def frame-base (fract (t / 15) * iterations))
(def frame (frame-base | floor | int))
(def inframe (frame-base | fract | ss 0.5 0.6))
(gl/def highlight-circle (march frame))
(def dist highlight-circle.x)
(def ray-at highlight-circle.yz)
(defn ray-point [progress]
(line-end - line-start * progress + line-start))
(def next-point (dist * direction + ray-at))
(def indicator (union
(line line-start (mix ray-at next-point inframe) 2)
(circle (abs dist) | shell 2 | move ray-at)
))
(def ray-cell (ray-at / 80 | round))
(def scene (make-scene (fn [$ $i]
($ | color (hsv (hash $i) 0.5 (gl/if (= ray-cell $i) 1 0.25))))))
(union
(rect 40 | shell 1 | color white | tile: $i [80 80] :limit 5)
scene
(indicator | expand 1 | color black)
(indicator | color white))
Hey look! We have a problem. If you watch that march to its completion, you’ll see that the ray actually overshoots, and winds up in the middle of a star. Thanks to the power of signed distance functions, it’s able to realize that it’s inside a shape (the distance field is negative) and the ray marcher backs out until it finds the edge.
This demonstrates a neat fact about signed distance functions, but the real point is that our magical approximation of infinite distance isn’t so magical after all. We won’t always be able to back out like this: with a little worse luck, a bad distance field could cause us to overshoot completely.
We’ll get obvious visual artifacts when we use this technique to render a 3D scene:
(star 20 10 :r 1 | extrude z 3
| rotate (hash3 $i 10 | normalize) t
| move (hash3 $i 20 | remap- * 10)
| shade (hsv (hash $i) 0.6 1)
| tile: $i [50 50 50] :limit 5)
As only some pixels overshoot their destinations.
And we can mitigate this by evaluating not just the current cell, but the current cell and its immediate neighbors. Your distance function gets more expensive – you’re evaluating your shape N times for each march now – but it’s a small price to pay for infinity.
Here’s the exact same scene, but sampling the eight nearest shapes instead of the nearest one:
(star 20 10 :r 1 | extrude z 3
| rotate (hash3 $i 10 | normalize) t
| move (hash3 $i 20 | remap- * 10)
| shade (hsv (hash $i) 0.6 1)
| tile: $i [50 50 50] :limit 5 :oversample true)
The artifacts are gone, but my laptop is hot now.
Okay. So this is classic domain repetition: it’s a discrete operation. There is a concept of a discrete “cell” or “tile,” with integer coordinates, and evaluation is based around multiple instances of these discrete cells.
Great.
Background information: explained.
Now we can start the blog post.
Periodic Spaces
Here’s a star:
(star 50 25 :r 3 | rotate (t / 2) | color sky)
There is only one star there. It is a normal star.
Here is a plot of the x coordinate of our input (on the x axis) versus the x coordinate that we render at (on the y axis).
(union
(star 50 25 :r 3 | rotate (t / 2) | color sky)
(circle 1 | move [q.x q.x] | color yellow))
It is the identity function, because we aren’t doing anything weird yet.
Let’s do something weird.
For each pixel we’re rendering, instead of using the color of the star at that point, we can use the color of the star at a different point. A trivial example is to just scale the x coordinate:
(defn with-x [expr]
(gl/with [q [expr q.y]]
(union
(star 50 25 :r 3 | rotate (t / 2) | color sky)
(circle 1 | move [q.x q.x] | color yellow))))
(with-x (q.x / 2))
The effect that we see is a stretching effect: it looks like we scaled the star. But we didn’t really: we scaled the image of the star that we rendered. This is like if we put a star on a scanner and slid it across the glass as it scanned. We would get an image that appeared stretched – just like this.
Many SDF combinators work this way. If you want to move the star ten pixels to the right, you actually evaluate the star at a point ten pixels to the left.
(defn with-x [expr]
(gl/with [q [expr q.y]]
(union
(star 50 25 :r 3 | rotate (t / 2) | color sky)
(circle 1 | move [q.x q.x] | color yellow))))
(with-x (q.x + oss t 5 -50 50))
But notice: we can do anything we want to the input. It’s just an expression, and we can write whatever expression we want.
We could evaluate at a random x coordinate:
(defn with-x [expr]
(gl/with [q [expr q.y]]
(union
(star 50 25 :r 3 | rotate (t / 2) | color sky)
(circle 1 | move [q.x q.x] | color yellow))))
(with-x (q.x | hash | remap- * 100))
We could evaluate with a smoothly-varying, semi-random offset:
(defn with-x [expr]
(gl/with [q [expr q.y]]
(union
(star 50 25 :r 3 | rotate (t / 2) | color sky)
(circle 1 | move [q.x q.x] | color yellow))))
(with-x (perlin [q.x 0] 20 * 20 + q.x))
We can even go nuts and make x a function of x and y:
(defn with-x [expr]
(gl/with [q [expr q.y]]
(union
(star 50 25 :r 3 | rotate (t / 2) | color sky)
(circle 1 | move [q.x q.x] | color yellow))))
(with-x (perlin q [30 100] * 100))
Or we could get back to the point of this blog post, and evaluate x with a periodic function. What happens if we take x % 100?
(defn with-x [expr]
(gl/with [q [expr q.y]]
(union
(star 50 25 :r 3 | rotate (t / 2) | color sky)
(circle 1 | move [q.x q.x] | color yellow))))
(with-x (mod q.x 100))
Er, right. That doesn’t look very good, because the star is centered at zero. Let’s try a variant of modulo that centers its output around zero:
(defn with-x [expr]
(gl/with [q [expr q.y]]
(union
(star 50 25 :r 3 | rotate (t / 2) | color sky)
(circle 1 | move [q.x q.x] | color yellow))))
(defn mod- [a b] (a + (b / 2) | mod b - (b / 2)))
(with-x (mod- q.x 100))
Aha! We have re-created the tile function that we were using to repeat space at the beginning of this blog post. And the plot of our x coordinate now looks like a sawtooth wave. It’s discontinuous – as soon as we reach the end of one period, we jump right back to the next period.
This sharp discontinuity doesn’t matter in 2D. But let’s take a look at this exact same scene extruded into 3D:
(defn with-x [expr]
(gl/with [q [expr q.y]]
(star 50 25 :r 3 | rotate (t / 2) | shade sky)))
(defn mod- [a b] (a + (b / 2) | mod b - (b / 2)))
(with-x (mod- q.x 100) | extrude z 3)
There are visual artifacts around the tips of the stars: sometimes the ray overshoots, because this repetition does not produce a correct distance field. (You can also click the magnet icon in the top right of the image for an alternate visualization that will make these artifacts stand out more clearly.)
We can see that the distance field is not very good by looking at the gradient of the distance field for this scene:
(defn with-x [expr]
(gl/with [q [expr q.y]]
(union
(star 50 25 :r 3 | rotate (t / 2)))))
(defn mod- [a b] (a + (b / 2) | mod b - (b / 2)))
(with-x (mod- q.x 100))
Notice how, at the sharp lines dividing each period of the wave, the contour lines don’t match up (it’s easier to see if you click to pause the rotation). If we use Bauble’s built-in multisampled repetition operator, we can see what the distance field should look like:
(star 50 25 :r 3 | rotate (t / 2) | tile [100 0] :oversample true)
But our sawtooth-wave modulo-repetition doesn’t look like that. We don’t see the complex distance field between two stars, because we never evaluate two stars. We just evaluate our one lonely star at different coordinates.
So this sawtooth wave is not great – although this is an interesting way to interpret the (naive) tiling operator.
Let’s try another periodic function. What if we use a triangle wave?
(defn with-x [expr]
(gl/with [q [expr q.y]]
(union
(star 50 25 :r 3 | rotate (t / 2) | color sky)
(circle 1 | move [q.x q.x] | color yellow))))
(gl/defn :float triangle-wave [:float x :float period]
(var section (x / period))
(var dir (round section | mod 2 | remap- | -))
(return (fract (section + 0.5) - 0.5 * period * dir)))
(with-x (triangle-wave q.x 100))
An intuitive explanation of this is: when you reach the end of the scanner, instead of starting over, reverse and scan backwards. So we “scan” left and right over the star, and the effect is that every other star is mirrored.
And, surprisingly to me, this actually does produce a correct distance field:
(defn with-x [expr]
(gl/with [q [expr q.y]]
(star 50 25 :r 3 | rotate (t / 2))))
(gl/defn :float triangle-wave [:float x :float period]
(var section (x / period))
(var dir (round section | mod 2 | remap- | -))
(return (fract (section + 0.5) - 0.5 * period * dir)))
(with-x (triangle-wave q.x 100))
Notice how, whenever the period changes, the contour lines perfectly match up. This means that we really can ray march this perfectly in 3D, with no visual artifacts and no extra evaluation:
(defn with-x [expr]
(gl/with [q [expr q.y]]
(star 50 25 :r 3 | rotate (t / 2) | shade sky)))
(gl/defn :float triangle-wave [:float x :float period]
(var section (x / period))
(var dir (round section | mod 2 | remap- | -))
(return (fract (section + 0.5) - 0.5 * period * dir)))
(with-x (triangle-wave q.x 100) | extrude z 3)
Of course it’s not the same scene that we were rendering before – half the stars are flipped – but still. If you’re tiling in all three dimensions, this is an 8x speedup over multisampled evaluation.
Now, this effect is well-known, and you can apply this to classic instanced repetition as well. If you want to repeat an asymmetric shape, you can make it the whole distance field symmetric by mirroring every other instance. But it didn’t really click for me until I saw it as a periodic function of space like this.
What about a sine wave?
(defn with-x [expr]
(gl/with [q [expr q.y]]
(union
(star 50 25 :r 3 | rotate (t / 2) | color sky)
(circle 1 | move [q.x q.x] | color yellow))))
(gl/defn :float sine-wave [:float x :float period]
(return (sin (x * pi / period) * 0.5 * period)))
(with-x (sine-wave q.x 100))
This one is pretty weird. It’s not a correct distance field: the contour lines are not equal distances apart, because space is stretched nonlinearly near the edges of each tile.
(defn with-x [expr]
(gl/with [q [expr q.y]]
(star 50 25 :r 3 | rotate (t / 2))))
(gl/defn :float sine-wave [:float x :float period]
(return (sin (x * pi / period) * 0.5 * period)))
(with-x (sine-wave q.x 100))
Still, we can ray march it with minimal artifacts:
(defn with-x [expr]
(gl/with [q [expr q.y]]
(star 50 25 :r 3 | rotate (t / 2) | shade sky)))
(gl/defn :float sine-wave [:float x :float period]
(return (sin (x * pi / period) * 0.5 * period)))
(with-x (sine-wave q.x 100) | extrude z 3)
It’s nice to be able to achieve a “smooth tiling” effect like this. As we vary the period, the shapes smoothly join together instead of just getting chopped off:
(defn with-x [expr]
(gl/with [q [expr q.y]]
(star 50 25 :r 3 | rotate (t / 2) | shade sky)))
(gl/defn :float sine-wave [:float x :float period]
(return (sin (x * pi / period) * 0.5 * period)))
(with-x (sine-wave q.x (osc t 5 100 50)) | extrude z 3)
It’s a neat effect in full 3D, too:
(defn with-point [expr]
(gl/with [p expr]
(box 25 | rotate x (t / 2) z (t / 3) y (t / 5) | shade sky)))
(gl/defn :float sine-wave [:float x :float period]
(return (sin (x * pi / period) * 0.5 * period)))
(defn limit [f x period instances]
(gl/if (> (abs x) (period * instances))
(x - (period * instances * sign x))
(f x period)
))
(with-point
[(limit sine-wave p.x (osc t 3 50 75) 2)
(limit sine-wave p.y (osc t 3 50 75) 2)
(limit sine-wave p.z (osc t 3 50 75) 2)])
You can also use this trick with radial symmetry. Bauble’s built-in radial symmetry operation uses the same discrete approach as its tile operation:
(octahedron 100 :r 5
| rotate x (t / 2) z (t / 3)
| radial y 12 80
| shade sky)
Artifact city, and sharp lines at the edge of each period.
But if we write our own radial symmetry, we can swap that sawtooth for a sine wave:
(gl/defn :float sine-wave [:float x :float period]
(return (sin (x * pi / period) * 0.5 * period)))
(gl/def angle (sine-wave (atan2+ p.xz) (tau / 12)))
(gl/def dist (length p.xz))
(octahedron 100 :r 5
| rotate x (t / 2) z (t / 3)
| move x 80
| gl/with [p [(cos angle * dist) p.y (sin angle * dist)]] _
| shade sky)
Kind of interesting.
This is a useful spatial distortion, and it’s fun to explore periodic spaces like this. I think there’s some value especially in a cheap approximation of smoothly merged repeated surfaces: that’s another effect that you can achieve with multisampled repetition – you don’t have to take the min of all adjacent cells; you can apply a smooth union operation – but the speedup you get by just throwing a sine wave at it is significant.
But this technique is less powerful than classic instanced domain repetition. For one thing, we’re always repeating the same shape. And while we could invent our own notion of “cell coordinates” based on which period we’re in, and still vary the shape as we scanned it with a triangle wave, by doing so we would lose the symmetry that made the triangle wave appealing in the first place.
There’s another limitation that hasn’t mattered in any of our examples yet: using classic instanced repetition, you have the choice to sample more than just the immediately adjacent cells. This allows you to repeat shapes that aren’t bounded by a single cell.
For example, here’s a triangle radially tiled around the origin:
(triangle [25 100]
| color (hsv (hash $i) 0.5 1)
| rotate (-pi/2 + t)
| radial: $i 10 50)
Because we’re only evaluating one “slice” of space, the triangle is clipped where it crosses the boundary between two cells. By evaluating the nearest adjacent slice as well, we can improve this:
(triangle [25 100]
| color (hsv (hash $i) 0.5 1)
| rotate (-pi/2 + t)
| radial: $i 10 50 :oversample true
:sample-from 0
:sample-to 1)
But it’s still clipped. Let’s evaluate both adjacent slices:
(triangle [25 100]
| color (hsv (hash $i) 0.5 1)
| rotate (-pi/2 + t)
| radial: $i 10 50 :oversample true
:sample-from -1
:sample-to 1)
Better! But still not perfect. Let’s evaluate both adjacent slices, and the adjacent slices next to them:
(triangle [25 100]
| color (hsv (hash $i) 0.5 1)
| rotate (-pi/2 + t)
| radial: $i 10 50 :oversample true
:sample-from -2
:sample-to 2)
That’s not something you can do with a pure periodic function of space: there’s no way to have a slice that contains five different triangles.
But even so… what other periodic functions should we try?