Smoothed Constructive Solid Geometry

Many complex shapes can be described as combinations (e.g. unions, intersections, ... ) of simpler shapes. For example, say we have two overlapping capsule shapes:

and we'd like to find a representation of the union of those shapes. One way to characterize the union of two shapes, $C_1,C_2$$C_1, C_2$ is in terms of an implicit region defined by the inequality

where $s_i(x,y)$$s_i(x,y)$ is the signed distance from $(x,y)$$(x,y)$ to the $i^{th}$$i^{th}$ shape. As we might expect, this produces the following region

In https://iquilezles.org/articles/smin/, there are many examples of applications where defining the geometry using "smooth" boolean operations is preferable. Luckily, this can be accomplished by making a small change to our region definition, to use a smooth minimum instead of the "hard" minimum

Although there are many different smooth min functions, in this document we'll assume smin refers to the "exponential smooth min" described in the linked document above.

Then, the resulting geometry includes fillet-like features (where the radius is controllable by a parameter) where the primitive shapes are close to each other.

While this process works well for the simple example above, there are some important cases where naively joining primitives by smoothed operations can result in undesirable geometry.

Problems with Overlapping Endpoints

Now, let's consider a slightly more interesting example with 6 capsule shapes

the implicit region defined by the "hard" minimum gives us the union shape we expect

But, what if we wanted a geometry with rounded fillets instead of sharp corners where the primitives intersect? In the first example, we showed that can be accomplished by using a smooth minimum, let's give that a try

Well, it certainly has the fillets at the intersections, but it also has (probably undesirable) bulbous features too. Additionally, although the region produced by the "hard" minimum has mirror symmetry about the vertical axis, the region defined by the smooth minimum doesn't.

Where did those swollen features come from?

Smooth min functions don't behave exactly like the actual min function. For example the actual min function satisfies

but the smooth min doesn't

This means that, even though the left tip of the horizontal blue cylinder from this example satisfies

The smooth min returns a slightly negative value $\text{smin}(s_{\text{blue}},s_{\text{yellow}},\cdots )<0$$\text{smin}(s_{\text{blue}}, s_{\text{yellow}}, \cdots) < 0$​, which makes that point seem slightly inside, rather than on the boundary. As a result, the actual boundary appears to moves outward slightly, leading to the bulbous features.

The "swelling" on the right side of the region is more pronounced than it is on the left, because there are 3 coincident shapes on the right, so there's a larger discrepancy between the smooth min and actual min.

A Potential Fix

So, what can we do about it?

The problem is related to the counterintuitive property of the smooth min function described above

However, the smooth min does still satisfy $a=\text{smin}(a)$$a = \text{smin}(a)$​, so if we can manage to remove unnecessarily duplicated arguments fed into the smooth min, then there's hope that we might be able to fix the issue. In other words, when the endpoints of capsules overlap with each other, the areas near the overlap get counted too many times, and that causes the swelling.

So, the idea behind the fix is to redefine the smooth min function to accept two kinds of arguments:

where $a_i$$a_i$ contribute to the inner sum with positive weight, and $b_i$$b_i$ contribute with negative weight. This way, we can cancel out some of the $a_i$$a_i$ contributions if we need to. Note, this canceling-out can also be achieved by allowing the arguments to be complex-valued

With this in mind, we can now preprocess the geometry and look for places where the endpoints might be counted too many times:

From left to right, the dark circular regions are effectively counted 2x, 3x, and 3x, instead of once. But now that we have the ability to negate contributions in the smin calculation, we can go back and add in spherical SDF contributions with weights -1x, -2x, and -2x to bring the multiplicity for those regions back to 1.

This geometry looks much better than the initial smooth min version, but it still has a few notable downsides over using the true minimum:

1. The exponential function is more expensive to evaluate.

2. The exponential smooth min hurts the locality of the calculation. This means that to calculate the smooth SDF of at a point, one needs to evaluate SDFs to all shapes within a distance of $\approx 5r$$\approx5r$ from the point, which makes this approach even more expensive.

3. It requires some additional preprocessing to identify overlapping endpoints and their multiplicity.

4. It slightly dilates the geometry everywhere.