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$

Generally it boils down to finding the nearest element. Computing distance to it. Checking the normal to tell if inside or out. There are a number of edge cases. Also you usually compute the "angle weighted psuedonormal" as its called.

Here's the usual reference "Signed Distance Computation using the Angle Weighted Pseudo-normal" by J. Bærentzen.

There are many such libraries with the implementation if you don't want to write it yourself. I personally use ImplicitPolyDataDistance function in VTK. Also a fan of LibIGLs. But there are many lighter weight ones to do it as well, https://github.com/Magnus2/MeshSdf.

It's also worth mentioning that you can compute SDFs in other less accurate ways for more performance. Namely, another popular approach is to voxelize/binarize a shape and compute the SDF of the binary image instead. The distances at the boundary of the shape won't be exact but it is a good estimate and often faster.

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$
2
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.