Has been a bit since my last post. This will be about distancefields. I did a few posts showing pictures of fractals and other stuff rendered using a distancefield raytracer. Distancefields are quite versatile in their usage. Applications range from fonts, through 3D surfaces to physics. We will start nice and simple with 2D, though the extension to 3D is pretty much just adding a coordinate. A code example to play around with in your browser and more below the fold :)
First of all, what's a distancefield? Well, first imagine some object on the plane, say a single point. Then the distancefield will tell you for every point on the plane how far it is from the chosen point. That implies, that it is zero at the point itself. Let's say our point is called \( \bf p \). The distance from any other point \( \bf x \)to \( \bf p \) is just the length of the difference vector. \[ \operatorname{d}_{\text{point}} (\bf x ) = \lVert \bf p - \bf x \rVert \] This looks like the following:
A point isn't very interesting though. For now we will add two new objects: Circles and lines. Circles have a centerpoint \( \bf c \) and a radius \( r \). To find the distance we just draw a line between \(\bf x \) and \( \bf c \). From that line we remove the inside part, which has length \( r \). So together that is \[ \operatorname{d}_{\text{circle}} (\bf x) = \lVert \bf c - \bf x \rVert - r \] One thing of note is, that this function will be negative on the inside. That is actually pretty useful, since we can now easily tell if we are inside or outside of the object. This kind of distancefield is called a signed distancefield, though we will usually assume all distancefields to be signed, since it has some other nice properties, like being differentiable at the surface. The result is the following, with color coding for inside and outside:
For a line, you can use the same formula which you maybe learned in school for planes. If you need a reminder: https://en.wikipedia.org/wiki/Hesse_normal_form . We use a normalized normal vector (a vector perpendicular to the line) \( \bf n \) and a point \( \bf p \) on the plane. The distance is then
\[ \operatorname{d}_{\text{line}} (\bf x) = \bf n \cdot \bf x - \bf n \cdot \bf p \]
This will split the plane into a positive and negative half, so we could also call this halfspace. Overall, not that exciting though. We can do two simple operations to display our objects: Fill and stroke. Filling an object consists of painting every pixel with one color if the distance is zero or negative and with another color otherwise. Stroking is slightly more difficult. A simple version is checking whether the absolute distance in pixels is less than our linewidth (or half of that). Below are the results:
While this is something, it's not really that interesting. Luckily, distancefield are pretty cool. To start off, we will define three different operations. The first is union. This takes two objects \(A\), \(B\) and combines them into one. To figure out the distancefunction, we will think about three cases.
Point is outside of both objects: Since the union contains both objects, we need the distance the closest point on one of the objects. So, given the distance of both, we choose the nearest one.
Point is inside of both objects: The union object's closest point is the one on \(A\) or \(B\), which is furthest away from the current point. If we would choose the closer one, then our new object would not extend to the furthest point, thus not containing both objects. Since on the inside, both distance values are negative, the minimum of those is the furthest one.
Point is in \(A\) but not in \(B\): Obviously, we choose the one negative distance, since we are inside one of the objects. Once again, the minimum of the two values Putting this all together yields
\[ \operatorname{d}_{A\cup B} (\bf x) = \min(\operatorname{d}_A(\bf x), \operatorname{d}_B(\bf x) )\]
We can more or less argue the same way for the next operation: Intersection. That is, our new object will contain all points which are both in \(A\) and \(B\). The distancefunction is:
\[ \operatorname{d}_{A\cap B} (\bf x) = \max(\operatorname{d}_A(\bf x), \operatorname{d}_B(\bf x) ) \]
The last operation is complement. So we take one object \(A\) and flip it, such that the inside becomes the outside and vice versa. This can be simply done by flipping the sign!
\[ \operatorname{d}_{A^C} (\bf x) = -\operatorname{d}_A(\bf x) \]
(Just as a sidenote, this is not the real complement, since this complement contains the border, but that's not that important here).
With intersection and complement, we can actually define an extra combined operator: Subtraction. So we will remove one object \(B\) from another one \(A\). That is the same, as the intersection with the complement of \(B\)! So we have
\[ \operatorname{d}_{A\backslash B} (\bf x) = \max(\operatorname{d}_A(\bf x), -\operatorname{d}_B(\bf x)) \]
With this we can create really complex and interesting forms already, like rectangles, which can be created as the intersection of four lines (halfspaces) :) If you like, you can play around with the code in the link to create different forms or multi color forms and so on. That concludes this introduction to distancefields. Next time, probably some quadratic splines, interpolation and fonts :)
(If the embedding doesn’t work, use the following link: https://www.shadertoy.com/view/ldKSRy)