2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The sdTriangles comes from I. Quilez's other article: iquilezles.org/www/articles/triangledistance/…. In that article his algorithm provides an unsigned distance (udTriangle). To convert the unsigned distance to signed distance, add some non-trivial thickness to each triangle. sdf=udf-thickness. Ray marchers require signed distance functions. This distance function will work similarly to Blender's solidify modifier. The mesh will become like a thick shell, and the interior of the mesh will be airspace, just like the exterior. $\endgroup$ Aug 21 at 0:11
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Hi, Michael, it's great that you've made this tool and are willing to share it. Unfortunately, it seems that this isn't exactly what the Question was asking for. The question is asking about how to do this so OP can write code for it. So, it would make this a much better answer if you edit to add some explanation about the algorithm and the inputs and output. Then the fact that you've already written the program becomes an extra bonus. $\endgroup$
    – luser droog
    Aug 15 at 0:15
  • 1
    $\begingroup$ Sure. You are right about that. Unfortunately, my algorithm is nothing special. It is simply brute force, made faster by the gpu. I have one small innovation though, which I can share in this answer. I'll add it. $\endgroup$ Aug 16 at 5:44
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Is this citeseerx.ist.psu.edu/viewdoc/… what you mean by "voxelize/binarize a shape and compute the SDF of the binary image instead"? $\endgroup$
    – Sirius 5
    Apr 20 at 15:01
  • $\begingroup$ Here's an implementation in VTK library vtk.org/doc/nightly/html/classvtkImageEuclideanDistance.html which cites "New algorithms for Euclidean distance transformations of an n-dimensional digitised picture with applications" It's possible there are some faster CUDA implementations. $\endgroup$ Apr 20 at 18:30
  • $\begingroup$ This will fail if your mesh has any holes. The "interior" may leak and cause raymarching issues. Closing a mesh is a separate, non-trivial problem. I personally like to add non-trivial thickness to each triangle, like Blender's solidify modifier. sdf=abs(sdf)-thickness $\endgroup$ Aug 21 at 0:12
  • $\begingroup$ The thickness produces edge cases for which the sign is incorrect. For many meshes, it may not be a problem though. Also with the angle-weighted normal for an open edge as the triangle face normal, it "intuitively" closes the hole. $\endgroup$ Aug 23 at 1:55
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.