#distancefield

[sibaku]

I’m currently working a lot with distancefields. Distancefields can be described pretty easily. Given some kind of object, a distancefield () will tell you f...

Some more mathy stuff. Hopefully easy to understand proofs (with omssions for clarity) for some distancefield properties (without using implicit surfaces or differential equations)

[thegiallo-en]

Devember 2016 - day 17

Today I’ve moved into a function the linear stepping camera and coded a circular stepping one. I've also corrected the name of "rotation" function that was in reality performing an inverse rotation.

Then I’ve explored the smooth union and then read the IQ’s smooth min.

https://www.shadertoy.com/view/ltcSDl

      Uh, oh, i've also added a gradient visualization of the total numebr of iterations performed per fragment!

https://www.shadertoy.com/view/XtcXWl

[thegiallo-en]

Devember 2016 - day 09

Today cones for dinner! But not bound ones, I’m sorry. I’ve started calculating the distance from a bound cone but I didn’t find one formula without using a step function or conditionals. I’ve not studied the IQ one. We’ll see tomorrow.

https://www.shadertoy.com/view/ll3SDB

[sibaku]

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)

[sibaku]

I did a super simple proof of concept (terrible controls and stuff, so not sharing it right now) of a 3D sculpting tool like ZBrush or Sculptris using discrete distancefields. That horrible thing you see there has a resolution of 35^3 voxels, so not that much. Still, you can see a lot of details and round shapes. Thinking about doing a desktop or javascript version (currently shadertoy framework), so I have control over stuff. Had the idea this morning and it seems to be a good idea :)

[sibaku]

Transformation operation on an object rendered using a distancefield tracer.

The reddish rod in the middle is the base object. Using this as base, a non-linear transformation is applied, producing the green object.

Since this will distort the distancefield, a bound on the change of the transformation can be used to still get correct results. For this, I didn’t calculate the bounds directly. Instead I used optimization to find bounds on the norm of the jacobian (generated by automatic differentiation) for a simple hierarchical region. 

Works alright ^^

[sibaku]

Moar hypno toad stuff with fractals

[sibaku]

Made a small animation.

This shows a small animation of an increasing refinement of lines concentrating around a Mandelbrot set (lines separated by colors to better see them). They are roughly lines of equal distance, where the distance is approximated by log(|z_n|)|z_n|/(2|d/dc z_n|), the well known formula found for example in “The Science of Fractal Images” or “Hypercomplex Iterations”. The former also has some images as the ones in the video in it. Really liked them, so I made some yesterday. While stepping through, I thought it looks really nice, how the lines come together, so I made a small animation