How can I get a signed distance (SDF) from a mesh?

Question

I am trying to use constructive solid geometry (CSG) and boolean operators to combine various shapes and get the outer (possibly concave) hull. This seems to work okay when using primitive shapes like cubes and spheres but I cannot figure out how to use other shapes.

Can I get a signed distance to a mesh? How would I calculate it?

I found https://www.iquilezles.org/www/articles/sdfbounding/sdfbounding.htm which seems like it might be what I want, specifically the section where they use an sdMesh method, but I do not understand where the sdTriangles method comes from. The only sdTriangle method that I found is on the 2D Distance Functions page. Do I use that somehow? Will that give a negative number if the point is "behind" the triangle in 3D space (i.e. inside the mesh)?

I am working in Unity / C#, but can translate from other languages.

Answer 1

EDIT I was able to get a simple algorithm working for this purpose, though it's not highly optimized.

In my implementation, I use sheer brute force, accelerated by GPU. By this, I mean that I get the signed distance function for each triangle to a given point in 3D space, and just take the minimum of those values. I use the unsigned distance function by Inigo Quilez, https://www.iquilezles.org/www/articles/triangledistance/triangledistance.htm MAKE SURE TO ADD NON-TRIVIAL THICKNESS to your triangle sdf function (thus creating a signed distance function instead of an unsigned one). sdf=abs(udf)-thickness. Otherwise, it will end up near-useless for ray-marching.

However, I implement one simple culling trick to make the algorithm a bit faster. Lets say, I have some sample point I want the signed distance value for. Start with an extremely large initial value, for instance, 2048.0 units (call this Dcurrent). Then, for each triangle, before calculating the signed distance, calculate the triangle's centroid, and the maximum distance from each vertex of the triangle to the centroid. Call that distance Dcentroid. Next, calculate the distance from the centroid of the triangle to the point in question, call this Dpoint. If Dcurrent<(Dpoint-Dcentroid), then skip the triangle entirely. This will save you on costly cross-product calculations.

Why it works: The current estimate for the SDF (for a given point P) represents a "sphere of relevance" around a P. The centroid and Dcentroid represent the "sphere of relevance" of a given triangle. If the spheres do not overlap, then that triangle will have no influence on the SDF for point P.

Answer 2

What you want is a Distance Transform algorithm which can be computed very fast using JFA, the steps are basically:

• Define where you want your seeds (I guess points that make up your mesh.

• At each log iteration find wether or not the current position is better than the last one, if it is add it to a texture (3d in this case).

Not sure of the details but in this video Ryan Brucks shows the Distance Field of a mesh computed by JFA using (a compute shader I guess?) on UE4.

Also check this link by Alan Wolfe.

Answer 3

Foolproof Accurate Way:

Find the nearest element (vertex, edge, or face). Compute distance to it. Check the angle-weighted psuedonormal to tell if inside or out.

Brute Force:

given a point X inside a mesh
for every feature of mesh
    compute closest point on feature y
    compute angle-weighted normal at y.
    project (y-x) onto the normal for sign

You can speed this up with a spatial accelerator (octrees, etc).

Why the angle-weighted pseudonormal? What is the angle-weighted pseudonormal? There's a whole proof for it: "Signed Distance Computation using the Angle Weighted Pseudo-normal" by J. Bærentzen.

Forewarning, there are many approximations to it, as mentioned in the paper, one of the other approaches listed as an answer works for one triangle but suffers edge cases for many triangles.

There are many such libraries with the implementation if you don't want to write it yourself. VTK has this ImplicitPolyDataDistance. LibIGL as well LibIGLs. But there are many light-weight ones to do it as well.

Faster but often less accurate:

Scan conversion methods are also very popular and a number of methods fall under this category. Nvidia has a brief for it in GPU Gems here. Particularly outlining a method to do it fast on the GPU. A similar method exists for Euclidean distance transforms of a voxelized/binarized shape.

EDIT: Also worth mentioning narrow bands and hierarchical SDFs. Those are very popular as well. Instead of computing SDF values for every element. Say in an image. We can compute SDF values only near the boundary of the shape. With an octree you can compute it at each vertex and interpolate to get inbetween estimates. There are special methods for computing these as well and libraries such as OpenVDB.