The wrong way to use a signed distance function (sdf)

Dis­claimer: there’s noth­ing wrong with using a sdf this way.

Recent­ly, my good friend Mike Brond­b­jerg post­ed this on Twit­ter:

You can fol­low along and see how this idea is evolv­ing into the beau­ti­ful, ele­gant line draw­ings that are the hall­mark of his style.

Spheres

Mike’s post gave me an idea, a way to intro­duce a con­cept I like to use in some of my work: signed dis­tance func­tions. Sdfs are more com­mon­ly asso­ci­at­ed with ray­trac­ing and shaders, and by far the best source to learn about them in that con­text is Ini­go Quilez, of Shader­toy fame: https://​iquile​zles​.org/.

But there is a delight­ful­ly wrong way to use a sdf. Their pri­ma­ry use in ray­trac­ing and shaders is to define mesh­less geom­e­try. For exam­ple, a way to draw smooth spheres with­out gen­er­at­ing a ton of tri­an­gles. The use I’m show­ing here is the exact oppo­site: to gen­er­ate geom­e­try, point clouds in fact. Geom­e­try that then needs to be processed in a con­ven­tion­al way before it can be ren­dered on the screen.

Let’s imag­ine we want to tack­le some­thing sim­i­lar to the tweet: par­ti­cles col­lid­ing with a sphere. One way to do this is by cal­cu­lat­ing the dis­tance of the par­ti­cle to the cen­ter of the sphere, let’s keep it at the ori­gin. For a par­ti­cle \vec{p} at posi­tion (x,y,z) , this dis­tance is giv­en by: {d( \vec{p} )=\sqrt{x.x+y.y+z.z}}. If that dis­tance d is larg­er than the radius r of the sphere, the par­ti­cle is out­side the sphere, if it’s small­er then it is inside, if it’s exact­ly the same then it is on the sur­face.

\begin{cases} d( \vec{p} )<r, & \text{if } \vec{p}\text{ is inside} \\ d( \vec{p} )=r , & \text{if } \vec{p}\text{ is on sphere}\\ d( \vec{p} )>r, & \text{if } \vec{p}\text{ is out­side} \end{cases}

Using this, we can check the par­ti­cles every step. As long as their dis­tance to the sphere is larg­er than the radius, they’re fine. If a par­ti­cle takes a step and its dis­tance becomes small­er or equal, it has hit the sphere.

Particles on a sphere
A grid of par­ti­cles fly­ing into a sphere. Some have col­lid­ed with the sphere, the rest is zoom­ing off into infin­i­ty.

If the sphere is not in the ori­gin but cen­tered in a point \vec{c} (cx,cy,cz) the dis­tance func­tion becomes {d( \vec{p} , \vec{c} )=\sqrt{(x‑cx).(x‑cx)+(y‑cy).(y‑cy)+(z‑cz).(z‑cz)}}. Typ­i­cal­ly, this is explained as the length of the vec­tor going from \vec{p} to \vec{c} . Anoth­er way to see it, that will serve us well fur­ther on, is to imag­ine that we shift the sphere to the ori­gin, \vec{c}\to\vec{0} , and the entire space moves with it . Our par­ti­cle is then moved \vec{p}\to\vec{p}-\vec{c} . Check­ing a par­ti­cle at \vec{p} against a sphere in cen­ter \vec{c} is the same as doing it for a par­ti­cle at \vec{p}-\vec{c} against a sphere in the ori­gin.

Since we can put the sphere wher­ev­er we want, we can add mul­ti­ple spheres. Each par­ti­cle is then test­ed against the dif­fer­ent spheres one by one.

Particles on a bunch of spheres
A grid of par­ti­cles fly­ing into a bunch of spheres.

Distance Fields

In cre­ative cod­ing, it is often use­ful to have sev­er­al per­spec­tives to look at things. The equa­tions above can be refac­tored:

\begin{cases} d( \vec{p} )-r<0, & \text{if } \vec{p}\text{ is inside} \\ d( \vec{p} )-r=0 , & \text{if } \vec{p}\text{ is on sphere}\\ d( \vec{p} )-r>0, & \text{if } \vec{p}\text{ is out­side} \end{cases}

Noth­ing has real­ly changed, the equa­tions are still the same. But what they describe is a func­tion {d( \vec{p} )-r} that sep­a­rates space in three regions: one region out­side the sphere, with pos­i­tive val­ues; one region inside the sphere, with neg­a­tive val­ues; and the sur­face of the sphere itself, where the func­tion equals zero. This is the signed dis­tance func­tion of a sphere in the ori­gin, with radius r .

Test­ing the par­ti­cles at each step is essen­tial­ly the same eval­u­a­tion: cal­cu­late the func­tion at \vec{p} and see how it clas­si­fies. The advan­tage of see­ing it this way is that the signed dis­tance func­tion can be eas­i­ly replaced, and sud­den­ly we’re check­ing col­li­sions with a box, a torus, or any of the many shapes that have a well-defined sdf, like the list Ini­go keeps.

A grid of par­ti­cles fly­ing into a bunch of box­es.

In itself, there’s noth­ing stop­ping us from using the first approach to cal­cu­late the dis­tance of a point to some spe­cif­ic geom­e­try. But I find sdfs make it more intu­itive, espe­cial­ly when we start mod­i­fy­ing and com­bin­ing them.

Not every func­tion is a signed dis­tance func­tion, there are cer­tain require­ments. I’m not going into the rig­or­ous math details, main­ly because I’m not qual­i­fied enough to pull that off. In essence, its rate of change has to cor­re­spond to what you expect for a dis­tance. If we fol­low the slope of the func­tion down­wards, we expect to end up at the sur­face. If we take small steps towards it, the dis­tance should decrease with small steps, not sud­den­ly change slope or start increas­ing.

As a cre­ative coder, one of the first things we think of is “add noise”, which is not a math­e­mat­i­cal­ly valid dis­tance func­tion. Adding noise to the sdf of a sphere does­n’t give us the sdf of a noisy sphere. For­tu­nate­ly, as cre­ative coders, we can choose to forego the rig­or and let the may­hem sur­prise us.

Noise might not be a valid dis­tance func­tion, but it’s still fun to use.

Tracer classes

Although a lot of infor­ma­tion and func­tions are avail­able online, it might not be imme­di­ate­ly clear how to use any of it in Pro­cess­ing. Typ­i­cal­ly, code is giv­en in OpenGL Shad­ing Lan­guage (GLSL) and the used func­tions aren’t always obvi­ous. GLSL is cre­at­ed to deal with num­bers and vec­tors in a uni­fied way. A func­tion like max(v,0.0) looks famil­iar but in GLSL can also work com­po­nent-wise on vec­tors, some­thing that Pro­cess­ing does­n’t han­dle. Tran­scrib­ing sdf func­tions can be con­fus­ing when unfa­mil­iar with GLSL.

In this sec­tion, we’ll be cre­at­ing the code used for the images above. In the end, we will have a rudi­men­ta­ry frame­work to build on for more com­plex pieces. Let’s start with some con­ve­nience class­es, Point and Vec­tor.

Both are just con­tain­ers for coor­di­nates. There is no real rea­son why we can’t use Pro­cess­ing PVec­tor for this, or why we have both Point and Vector. But for this tuto­r­i­al, it is eas­i­er to talk about points and vec­tors with as lit­tle abstrac­tion as pos­si­ble.

Anoth­er class that will come in handy is Ray, a half-line start­ing at a Point origin, the direc­tion is giv­en by the Vector direction. On cre­ation, direction is nor­mal­ized, its length is rescaled to 1.0. The func­tion get(t) will return a new Point on the ray, a dis­tance t from its ori­gin.

For our mini-frame­work, we need signed dis­tance func­tions. We could hard­wire the func­tions into a sdf(Point p) func­tion and change that code every time. But, a bit of struc­ture goes a long way to help explo­ration. First, we need to tell Processing/​JAVA what a signed dis­tance func­tion is:

Don’t wor­ry if the details on what an interface is aren’t clear. We can con­sid­er it a promise to Pro­cess­ing: every­thing we iden­ti­fy as a SDF will have this func­tion signedDistance(Point p) that returns a float. It does­n’t mat­ter what class it is pre­cise­ly, how we cre­ate objects of that class, how the object cal­cu­lates the dis­tance, as long as we tell Pro­cess­ing it’s an SDF, it will be able to call that func­tion. An interface can be used to define vari­ables, to pass objects to func­tions, pret­ty much every­where we can use a class. What we can’t do, is cre­ate a new object with new SDF().

We already encoun­tered one signed dis­tance func­tion, that of a sphere at the ori­gin with radius r, {d( \vec{p} )-r}. We can now imple­ment a class that encap­su­lates this.

We tell Pro­cess­ing that this class imple­ments SDF. In return, we need to ful­fill our promise and imple­ment signedDistance(Point p) . Every­where Pro­cess­ing expects a SDF we can now pass a SphereSDF and it will work.

Sim­i­lar­ly, we can define the sdf of a box at the ori­gin of size X, Y, and Z.

One piece miss­ing, the par­ti­cles. We’re going to shoot par­ti­cles, Trac­ers, into the scene along straight paths. When they hit some­thing, they stop. Oth­er­wise, they come to a stop after a cer­tain dis­tance. If our col­li­sion geom­e­try would be defined by mesh­es, we could try to inter­sect the ray of the par­ti­cles with the faces of the geom­e­try. How­ev­er, in this case, the whole point of this tuto­r­i­al after all, we define the geom­e­try by signed dis­tance func­tions. So, we will be using anoth­er tech­nique of find­ing col­li­sions: sphere trac­ing.

Imag­ine we have an arbi­trary col­li­sion geom­e­try defined by a sdf and assume we have some par­ti­cles start­ing out­side this geom­e­try. We know that in every point in space we can cal­cu­late the signed dis­tance {sdf( \vec{p} )} . That dis­tance, let’s call it d , tells us how close the geom­e­try is to the point, but it does­n’t give us a direc­tion. The only thing we can say is that the par­ti­cle can safe­ly move in any direc­tion over a dis­tance d . In oth­er words, we know that at that point we can put a sphere of radius d and know for sure that the geom­e­try isn’t in that sphere. In the extreme case, if the par­ti­cle is mov­ing straight towards the geom­e­try, it might end up direct­ly on the sur­face, but it will nev­er cross it or go inside.

Take the fig­ure below. We start at P_{0} and the cho­sen direc­tion is along the blue line. The black tri­an­gle and rec­tan­gle are our col­li­sion geom­e­try. sdf( P_{0}) tells us it that it is safe to move any­where in the green cir­cle cen­tered on P_{0} .

If we take a big step, the max­i­mum safe dis­tance, along the blue line, we end up in P_{1} . sdf( P_{1}) isn’t zero. Our direc­tion of move­ment was­n’t the short­est path to the sur­face. We move on, this time a step of size sdf( P_{1}) and the par­ti­cle ends up in P_{2} . We can repeat this until the returned dis­tance is close to zero, or if we nev­er hit the sur­face, after we reach a cut­off dis­tance. In the fig­ure, the fourth step takes us to P_{4} , on the sur­face.

The nice thing about this tech­nique is that we don’t have to guess step sizes. There is no risk of tak­ing too many small steps and wast­ing time, or of tak­ing too large steps and over­shoot a col­li­sion. The sdf auto­mat­i­cal­ly takes care of this by dynam­i­cal­ly adapt­ing the step size.

Our Trac­er par­ti­cle class looks like this:

Each Tracer starts in a Point origin, along a Vector direction. Since our par­ti­cles only move in a straight line, we store them as a Ray. We also need to define when we stop trac­ing the par­ti­cles. Numer­i­cal round­off makes it unlike­ly we’ll get exact­ly 0.0 dis­tance, so instead, we check if the dis­tance becomes small­er than some val­ue precison. If the trac­er does­n’t hit, we want to stop after a cer­tain dis­tance, called cutoff. Just to be safe, we lim­it the max­i­mum num­ber of steps our trac­er can take, MAXSTEPS.

The cur­rent state of a Tracer is held in 4 vari­ables:

  • t: the cur­rent dis­tance trav­eled along ray
  • closestDistance: the clos­est the par­ti­cle has come to the sur­face so far
  • steps: the num­ber of steps tak­en so far
  • p: the cur­rent posi­tion of the par­ti­cle along the ray

At every step, the signed dis­tance func­tion is checked, and the par­ti­cle is moved that dis­tance for­ward along the ray. The trac­ing is stopped once one of three con­di­tions is met:

  • closestDistance < precision: the par­ti­cle has come clos­er to the sur­face than our pre­ci­sion thresh­old: col­li­sion.
  • t>=cutoff: The dis­tance trav­eled along the ray exceeds the cut­off dis­tance: no col­li­sion.
  • steps>=MAXSTEPS: The num­ber of steps tak­en exceeds the max­i­mum num­ber allowed. This should only occur when we’ve made a mis­take in the code.

In any case, at the end of the trace, the par­ti­cle is either on the sur­face or beyond our region of inter­est.

Putting it all together

To repro­duce this image, we need to cre­ate a sdf, cre­ate some par­ti­cles, and run the traces. The script, includ­ing the class­es can be found here.

To set­up the trac­ers, we cre­ate an emit­ter, a reg­u­lar 600*600 square grid of 50x50 points. This emit­ter is posi­tioned some­where “above” the ori­gin — to the right in the image above. Each point defines a Trac­er aimed along the neg­a­tive Z‑axis. The sdf in this exam­ple is a sin­gle sphere at the ori­gin. To show the trac­ers miss­ing the sphere, we draw a lim­it­ing plane at the cut­off dis­tance.

Beyond

This is just the start. In the next part, we will explore how we can extend the code to manip­u­late and com­bine signed dis­tance func­tions.

In 2017, I cre­ate a series of images using dif­fer­ent com­bi­na­tions of trac­ers, sdfs and shad­er effects, that shows just some of the pos­si­bil­i­ties.