Periodic Spaces

One of my favorite SDF techniques is domain repetition:

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:

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:

Pretend that that’s a 2D slice of a 3D scene. Like, imagine that we’re actually trying to render this:

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:

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:

…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:”

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:

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:

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:

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:

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).

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:

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.

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:

We could evaluate with a smoothly-varying, semi-random offset:

We can even go nuts and make x a function of x and y:

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?

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:

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:

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:

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:

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?

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:

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:

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?

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.

Still, we can ray march it with minimal artifacts:

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:

It’s a neat effect in full 3D, too:

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:

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:

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:

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:

But it’s still clipped. Let’s evaluate both adjacent slices:

Better! But still not perfect. Let’s evaluate both adjacent slices, and the adjacent slices next to them:

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?