Manipulation of Implicit Functions (With an Eye on CAD)

Most people are familiar with the equation for a circle, :

I prefer to think of it as the curve where is zero — the locations where the Euclidean distance from is one.

This curve is called an implicit function, and when we look at it as the curve on which a function of two variables is zero, a lot of possibilities open up for manipulating it. Clearly we can translate it by adding or subtracting from and :

We can also scale them by like so: .   I’m intentionally preserving unit distance here, you will see why this is useful later.

Beyond that, we can change our notion of distance to produce different shapes, by changing the powers used above. For example, :

Or, :

These notions of distance correspond to the -norms. As you increase the power, these tend to the unit ball of the super norm, :

Now, consider what and would look like:

is the intersection. Maximum intersects things. Conversely, minimum unions things.

Two things need to be clarified: what and why.

What are we unioning or intersecting? After all, we’re working with functions, not objects. However, we can look at the functions as a way of representing objects — we already have been, we just haven’t discussed it. The boundary is the , negative regions are the interior and positive regions are the exterior. We can think of the function as representing the “outwardness” of the object.

Now why does it work? Sometimes, the best way to answer such a question is to look at a simple example. Let’s consider unioning and intersecting two simple one dimensional objects, line segments. We can look at the corresponding “outwardness” functions not as a colored background but height on the y-axis.

(Technical comment, disregard unless you’re a very big nitpick: The ‘outwardness’ functions aren’t the normal ‘outwardness’ functions of line segments — they’re slices of a square — but they avoid certain questions I don’t want to deal with here.)

In short, if one of the functions is negative, the minimum will be negative and thus inside — being inside one means you’re inside the union. Similarly, if one of them is positive, the maximum will be positive — if you’re outside one, you’re outside the intersection.

One thing that would be really interesting to do is to make a rounded union or intersection. Consider the following union of two squares.

The sharp right-angle transition in the curve corresponds to the interface between the two unioned objects.

If we could round the transition, we would get nice round unions. So we construct a rounded minimum function, replacing that corner with a quarter of a circle.

If we use this to union the squares, we get:

(NB. This particular formation of rounded unions is a little bit naive. If you union and the sides aren’t orthogonal, this version will make a bump, which is not the expected behavior. This can be corrected for quite easily by looking at the dot product of the discrete gradients.)

Another neat thing we can do is make shells of the object. By this I mean that we create a new object that is a certain width from the edge of our original object. For example, this is the shell of width 0.2 of a square:

We do this by taking the absolute value and then subtracting half the desired width. Taking the absolute value makes the interior into exterior and then subtracting ‘pushes out’ the boundary.

Again, we consider a one dimensional example. It is very similar to what happens to a slice down of the above shell of square example.

We can do this to a more complicated example, our earlier rounded union:

It’s important to notice that the rounded unions (and other CSG operations) and shells only work because the magnitudes of the values are the distance from the boundary.

It’s also important to note that everything we’ve done can be done in arbitrary dimensions!

Another neat thing we can do is use the output of one of these functions as the input for another. For example, if we feed , the outwardness of a circle on the -plane, into a new circle which we can think of as being on the -plane, , we get a torus.

That is, results in:

Exercise: Can you make formulae for the following?

Other (Silly?) Tricks

There are other ways to do unions that don’t involve anything more than multiplication and subtraction — I used them a lot when I was younger (for example, making an equation for a 3-torus). The first trick is to realize that multiplying the functions for your implicit functions together unions the graphs of the implicit functions because when either of the functions is zero, the product of the two is zero.

This doesn’t union the objects, it unions the edges. The “bubble” inside is positive and one can get rid of it by subtracting the right amount, which has the side effect of smoothing the interface (consider: has a sharp corner but does not).

Subtracting a bit more will get rid of the bubble entirely:

These techniques are, however, substantially harder to use to make precise objects than the min/max based unions I mentioned earlier. The choice of the right value to subtract can be quite finicky as well.

Rendering Implementation Tricks

As you’ve probably noticed, we’re manipulating something much more specific than implicit functions — we’re manipulating objects represented by functions where the boundary can be considered an implicit function, the interior is negative, the exterior is positive, and magnitude is the distance from the boundary. Or at least we’d like to try and keep things in that format, since we can do lots of cool things that way, as you’ve already seen!

You may also have guessed, given my interest in CAD, that this post isn’t just me presenting the fun tricks I played around with to make pretty graphs on lunch break at high school. I’m working on a programmatic CAD tool based on it.

When deciding how to render such objects, I started by reading the discussion that occurred when sage decided to implement implicit plotting — a cool advantage of open projects is public discussion of how to approach problems. A little bit of further reading led me to the Marching Squares/Cubes algorithm.

Now, there’s a lot of improvements to be made on the plain old Marching Squares/Cubes algorithm. For example, Wikipedia’s Marching Squares page outlines the natural linear interpolation modification — this works particularly well for the type of functions I’m applying it to. But what’s really interesting is that there are modifications we can make that only work if we have the guarantee that the magnitude is at most the distance from the boundary (or, in mathematical terms, that we have Lipschitz Continuity with c=1 and the functions is zero at the boundary of the object it describes). In particular, if we see a big magnitude, we can throw away the whole region! This allows us to bring Marching Cube’s complexity from , where is the number of steps on each side, to where is the Hausdorff dimension of the boundary of , the object being rendered. Normally (ie, for non-fractal objects) this means !

Relation to the Hausdorff Pseudometric

Mathematicians may have been reminded of Hausdorff distance. It is very closely related to my outwardness function. In the development of Hausdorff distance, one defines the distance between a set and a point as — the minimum distance between the point and a member of the set. From here we can define the outwardness function of as:

Relation to the Level Set Method

The Level Set Method is the most similar thing I’ve been able to find in Computer Graphics to my technique. What I’m working with is basically a more restricted version of the level set technique (the magnitude restriction) that gives one some advantages. That said, I have not researched existing techniques in any great degree of detail — it’s entirely possible that everything I’ve spoken about in this essay is well known.

ImplicitCAD

In any case, the programmatic CAD tool I wrote based on this method, ImplicitCAD, is on GitHub. It’s ready for beta testers! Have a look!

I’m very excited about it for a number of reasons, but the main one is that I’m hoping it will allow one to easily create new operations to use on objects. If you can describe the effect in terms of what should happen to points at varying degrees of outwardness, you should be able to implement it. Hopefully this essay has explained enough that you can go and do just that!

Advertisement

Tags: CAD, math