Understanding Signed Distance Functions

In this post, I will digress a bit from CNC machining to introduce a very smart mathematical concept that helped me solve the problem of tool crash detection in my [∞] CNC web application. I was introduced to this technique a few years ago but found it so cool that I wanted to share an introduction to it with you in this post :) I therefore hope that you will enjoy this aparté! I uploaded a ZIP file for Premium members with all the Matlab programs used in this post for the Premium members [∞] here.

Tool crash detection is an important topic in CNC machining because a small mistake can often lead to the irremediable destruction of an expensive piece of equipment, not even to mention scrapping up your part completely. A typical mistake is to drive a threading mill – a very delicate type of mill used to machine threads – into a hole that wasn’t drilled yet! The consequence of such mistakes is usually the loss of a 200€ tool in addition to lots of wasted time. Similar observations can be made with t-slot cutters, round endmill, chamfer mills etc.

The fundamentals of tool crash detection is relatively straightforward: detect if a tool plunges or moves laterally into unmachined stock when it shouldn’t. The main issue, however, is that we do not want to test for tool contact at the tip, or center, of the tool but on the complete tool diameter (or shaft diameter). The question is therefore whether the machining coordinates approaches stock by some distance D_min.

Tool crash of a thread mill is illustrated in Figure 1 for my [∞] lens mount part. Various crashes can occur here: plunging too deep, moving too much laterally, swapping the operations order (e.g. machining the thread before pocketing the part) etc. Our tool crash detection must handle all of these.

This problem can efficiently be solved by turning to signed distance functions (SDFs) which makes the body of this post.

The SDF is a function that gives, for each (x, y) coordinate pair, the distance to the nearest edge when looking at the part from above:

Furthermore, we define the function as being negative inside the represented object and positive outside. The function is zero on the edge of the object.

The object shape is therefore defined as

The condition for tool crash becomes

or, put differently, when the tool approaches the object edge by less than a distance R_min, with the tool still being inside the object.

The challenge is how to construct this function in a robust way.

The most straightforward approach is to construct a binary map from the CNC primitives (pocket disk, pocket rect, path slot etc.) and to apply a bushfire algorithm to the resulting image or any distance map generation algorithm. In the bushfire algorithm, we assign all values that are ‘1’ in the binary mask to the distance 0 and add all other points to a waiting list. We then propagate the distance from all the pixels that have distance 0 to the pixels within the waiting list by assigning neighboring pixels the distance value 1. We continue this process until there is no pixel left in the waiting list. The resulting SDF is shown in Figure 2.

Although this may work fine in controlled environments, this method pose a risk in terms of memory usage when opened to external users. Since we would like to probe for a distance R_min, we need to have a resolution of at least R_min/2 on the distance map. Most tools are usually larger than 1 mm but we don’t control the size of the input binary map which is a function of how large the stock being machined is! Unless you restrict the maximum stock dimension, you run the risk of using a lot of memory. For instance, a stock of 400×300 mm with a resolution of 0.5 mm represents already at least 1 Mb of data. Larger stock, and, more importantly, finer resolutions, will quickly saturate your memory – especially if you allow multiple users to run tasks in parallel.

A more elegant solution is to generate the distance value on the fly, based exclusively on a mathematical approach of the problem. This is exactly what I did here.

The solution I present is heavily based on the work of [∞] Inigo Quilez who did an incredible job presenting SDFs to the non-expert public. I strongly recommend that you check his website. Since there is no way I can compete with the literacy he is showing on the subject, I will focus here on the aspects that are of importance for tool crash detection implementation. I will also present things along a different angle, hoping that this article can shed some more light onto the topic.

The most basic distance function I can think of is the distance to a point located at (0, 0) which is shown in Figure 3 and has expression f(x,y)=√(x²+y²). You can see a 3D plot of this distance function on the left, a top view at the center and a binarized version on the right showing only values that are inside the shape (f(x,y) ≤ 0). Note that a point don’t really have an interior, but I deliberately represented it as a single dot in the binary image here.

The function of Figure 3 has radial symmetry and can be used to generate many more SDFs. For instance, subtracting an offset from this function yields a disk as shown in Figure 4. This change comes from the fact that we defined the object as being all the points where the function is lower than or equal to zero. The effect of the offset is better seen on the 3D plot where you can compare the intersection with the zero plane.

This result can be generalized by noting that we can grow or shrink any object by some distance r to the distance value. If the initial SDF of the object is f, then the grown object, f’, is

Use negative distance to shrink the object instead of growing it.

Another easy modification that we can do is shift the function to some location (x_c,y_c) using

We can also rotate the coordinates using

In fact, we can apply any coordinate change at one exception: scaling. Scaling (x,y) will change the metric of the system and therefore the returned distance. To accommodate for this change we need to scale back the returned distance by the inverse amount:

An indirect consequence is that only isometric scaling is supported by SDFs; you can’t scale x and y differently. It also makes using non-orthonormal transformations matrix complicated.

Side note, we have been using cartesian coordinates here but in some applications other coordinates systems might be better suited. For instance, polar coordinates system can be expressed as

or, more usefully,

which leads to a very simple expression for the SDF of a point:

Last but not least, you can also flip an object inside-out by inverting its SDF as shown in Figure 5 (recall that the interior of an object has been defined as f(x,y)≤0 so flipping the sign makes the interior becomes the exterior).

So far, we have everything necessary to represent disk inner and outer pocketing operations. This may seem restrictive at first but remember that (a) lathes inherently generate radially symmetric objects hence representable by a series of disk pockets operations, and, (b) SDFs exist for many other shapes including lines, rounded rectangles, hexagons, starts, arcs, pie shapes etc. [∞] Inigo Quilez website presents many different SDFs that you can have a look at. Here, I will focus on aspects that are specific to CNC machining and won’t dig further into SDFs primitives. That being said, tool crash detection is limited to shapes for which you have an exact SDF solution, and some are not always easy to derive.

Now that the basis has been set, let’s dig into the fun stuff :)

Pockets, while they represent the final cut shape, are however not representative of the CNC machining process. In CNC machining, our tools describes paths into the stock where the tool leaves a cut of diameter D around that path. To machine a pocket, we would typically machine a few concentric circles that overlap by an amount chosen during the CNC program creation (in most cases lower than D/2). It is the junctions of all these circular paths that creates what we see as a disk pocket once the part is done. This is illustrated in Figure 6.

Fortunately, we can turn our disk SDF into a circle SDF using the absolute value of the disk function:

This function has no more “inside” but only an outside as all values are positive. We still have an edge however represented by f’=0, leading to a circle shape instead of a disk shape.

But we can now grow this new object by the diameter of the tool using the grow/shrink function:

This new function is shown in Figure 6 and can be generalized to any SDF functions (square, lines, polygons etc.). I’m calling it the toolpath SDF transform operator.

Last but not least, if you read my post on [∞] CNC Programming, you know that it is possible to configure your CNC machine to follow a path that is either centered on the given coordinates, inside the given coordinates or outside them via the radius compensation flag. We could emulate this by altering the diameter of our disk function, f, i.e. make the disk diameter smaller or larger, but we can also do better! Instead, we can modify the SDF path function as

where k=0 for centered path, k=-1 for inside paths, and k=+1 for outside paths.

In my CNC web application, I generate SDF for each tool path using the here-above formula and a set of SDF primitives. It is from these SDFs tool paths that I can test for tool crashes.

The problem is that we now have many SDF functions and need some way to combine them. That’s where the SDF method falls short unfortunately… There is no simple way to generate a true SDF combination using separate SDFs, only an approximation to that function. By “true” I mean an SDF that will effectively tell you, for each coordinate pair (x,y) how far away you are from the edge of the final, merged, object.

We know how far we are from any given tool paths edges on the other hand; so we can approximate the total SDF as a worst-case scenario such that we are at best distant by f_i from an edge by taking the minimum of all toolpaths SDFs:

Here, the ^ remind us that this is an approximation only. I’m also using a capital F to indicate that it is a merged SDF from multiple primitive SDFs.

Such combination of multiple SDFs is a union or merge operator. There exists other operators, such as the intersection between multiple SDFs or the subtraction of different SDFs. For instance, you have the intersection operator defined as

and the subtraction between two shapes can be seen as the intersection between the first shape with the inverse of the second shape, or,

The approximation made for Boolean operations (merge, intersection, subtraction etc.) is very problematic in the context of CNC machining. While it poses not much problem for raytracing where you are basically searching for the object edge, F=0, it is not sufficient as-is for tool crash detection where we need to answer the question “is this a safe place to move our tool to”.

Let’s illustrate this with an example.

Imagine you have a series of concentric rings machined with a tool of diameter D₁, making a pocket of diameter D > D₁ as shown in Figure 8 We now want to know if we can insert a tool of diameter D₂ into the center of that pocket. If D₂<D that should succeed but, since we are testing for the minimum of D₂ against all toolpaths of width D₁, the test will systematically fail when D₁<D₂ and will sometimes fail/pass when D₁>D₂.

We therefore need to patch our test function such that it can handle spurious failures like this one. Note that if the test succeeds (i.e. if F>-D₂/2) we are sure that all toolpath edges are farther than D₂ and that the tool can be inserted safely. We only need to patch the case where the test fails when it shouldn’t have.

To figure out how to patch the test function, recall that our goal is to answer the question “is this a safe place to move our tool to” which can be rephrased as “is the stock edge farther away than distance D₂/2 from this position?”. If our initial test fails, we then need to check if that was a spurious failure by checking if we can actually find a stock edge within a radius of D₂/2.

To check for edges within a radius of D₂/2 (plus some safety margin), we can throw rays in all directions from the test point (x,y) and test if we find the condition F=0 within some radius D₂/2. We can use the ray-marching algorithm here to trace the rays to edges. The algorithm is relatively straightforward: we sample the worst-case, approximated, distance to an edge at the current point location and moves forward by that amount. If the function was correct, we should land closer to an edge, and we can continue the process until we reach |F|<ε. If the function was not correct, we get another worst-case distance to try and so on. The algorithm should quickly converge and we can safely skip testing once we have already travelled by more than D₂/2.

This leaves the question of how many rays to trace; more rays leading to more accurate results but being also more CPU intensive. Here I opted to check every D₂/2 arc segments on a circle of diameter D₂. Since this circle has perimeter πD₂, having segments of maximum D₂/2 requires N>2π rays. I chose N=8 as it aligns with the principal axis of my systems and its diagonal. Note that this approach is by no means compulsory and you can choose the number of rays cast you want.

This process is illustrated in Figure 9. Each dot represent an intermediate position in the raytracing and intersection with the shape edge are shown as small red circles. In Figure 9, the tool would contact the edge of the object – indicating a true collision.

That’s about everything concerning the tool crash detection itself. But before I close this post, I would like to show another problem that I solved using SDF functions – enhancing how versatile this mathematical tool is.

So far, I divided the pocket operation as a series of cutting toolpaths but I did not mention how I’m generating these toolpaths. For simple shapes, like disks, slots and rectangles, you can just shrink the size of the shape by the overlapping ratio you want for the toolpaths. For instance, an 8 mm disk pocket can be divided into circular toolpaths of 8 mm diameter, 7 mm, 6 mm, 5 mm etc. For more complex shapes, like polygons, or cutting the outside of multiple shapes (e.g. cutting around a box and a disk at the same time over a plane), things are not so simple.

To solve this problem, I generated a bounding box around the shape(s) such that we know that all points outside of the bounding box cannot be, by definition, inside the shape. I then generated a set of points inside this box and kept only those for which the SDF was smaller than -D/2, where D is the diameter of the tool used for the pocketing operation. The points are then connected forming one or multiple continuous tool paths. To finish the pocketing operation, the edge path is traced in either inner or outer radius compensation mode.

This algorithm used to generate the inner points inside an SDF is illustrated in Figure 7 where the inner points are marked in blue and the outer points in red. Note how the inner points are offset from the shape edge to account for tool diameter during the pocketing operation.

For simple convex shapes, I also implemented a different approach for outer pocket (contour) operations. Here, I move the tool horizontally until I intersect the SDF expanded by radius D/2 (plus some margin), before backing up and moving to the next horizontal movement. As the tool reaches the bottom of the bounding box, I then perform the same operation but on the right face of the shape. Again, the outer edge path is traced for a clean finish of the shape.

This second algorithm is illustrated in Figure 8. Note on the figure how the tool stops on slanted lines – something that would have been very difficult to implement using standard line intersections algorithms!

Note also that the algorithm of Figure 7, despite being generic, requires storing points positions leading to similar memory footprint problems as those we already discussed – although less problematic because we would typically use coarser point resolution here. The algorithm of Figure 8 is much simpler to implement and don’t have the same memory footprint issue but is limited to simple convex shapes. That being said, the algorithm could be modified for more complex shapes, a task that I did not pursue because I was already satisfied with the algorithm of Figure 7.

None of these could have been implemented so easily without the use of SDFs! I clearly cannot emphasize more on how powerful this mathematical tool is to solve computer problems :)

Do not hesitate to share your thoughts on the [∞] community board to let me know if you enjoyed this post! To promote a little bit the usage of the [∞] Premium membership, I also uploaded the complete Matlab code used to create the figure in this post and let you experiment with SDF functions yourself :)

I would like to give a big thanks to Sebastian, Alex, Stephen, Lilith, James, Jesse, Jon, Kausban, Karel, Michael, Sivaraman, Zach, Samy, Shaun, Onur, Sunanda, Themulticaster, Tayyab, Benjamin, Marcel, Dennis, M, Natan and RottenSpinach who have supported this post through [∞] Patreon. I also take the occasion to invite you to donate through Patreon, even as little as $1. I cannot stress it more, you can really help me to post more content and make more experiments!