<p><strong>EDIT</strong>
I was able to get a simple algorithm working for this purpose, though it's not highly optimized.</p>
<p>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, <a href="https://www.iquilezles.org/www/articles/triangledistance/triangledistance.htm" rel="nofollow noreferrer">https://www.iquilezles.org/www/articles/triangledistance/triangledistance.htm</a>
MAKE SURE TO ADD NON-TRIVIAL THICKNESS to your triangle sdf function (thus creating a signed distance function instead of an unsigned one). <code>sdf=abs(udf)-thickness</code>. Otherwise, it will end up near-useless for ray-marching.</p>
<p>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 <code>Dcurrent</code>). 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 <code>Dcentroid</code>. Next, calculate the distance from the centroid of the triangle to the point in question, call this <code>Dpoint</code>. If <code>Dcurrent</code>&lt;(<code>Dpoint</code>-<code>Dcentroid</code>), then skip the triangle entirely. This will save you on costly cross-product calculations.</p>
<p>Why it works:
The current estimate for the SDF (for a given point <code>P</code>) represents a &quot;sphere of relevance&quot; around a <code>P</code>. The centroid and <code>Dcentroid</code> represent the &quot;sphere of relevance&quot; of a given triangle. If the spheres do not overlap, then that triangle will have no influence on the SDF for point <code>P</code>.</p>

CC BY-SA 4.0
2021-08-15T00:15:28.653Z
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.
luser droog
CC BY-SA 4.0
2021-08-16T05:44:38.737Z
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.
Michael Sohnen
CC BY-SA 4.0
2021-08-11T12:55:31.907Z
2021-08-16T06:00:32.970Z
2021-08-16T06:00:32.970Z
Michael Sohnen
<p>What you want is a Distance Transform algorithm which can be computed very fast using <a href="http://www.comp.nus.edu.sg/%7Etants/jfa/i3d06.pdf" rel="nofollow noreferrer">JFA</a>, the steps are basically:</p>
<ul>
<li><p>Define where you want your seeds (I guess points that make up your mesh.</p>
</li>
<li><p>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).</p>
</li>
</ul>
<p>Not sure of the details but in this video <a href="https://youtu.be/GvI7qt3kmz4" rel="nofollow noreferrer">Ryan Brucks</a> shows the Distance Field of a mesh computed by JFA using (a compute shader I guess?) on UE4.</p>
<p>Also check <a href="https://blog.demofox.org/2016/02/29/fast-voronoi-diagrams-and-distance-dield-textures-on-the-gpu-with-the-jump-flooding-algorithm/" rel="nofollow noreferrer">this link by Alan Wolfe</a>.</p>

CC BY-SA 4.0
2021-04-21T13:38:35.433Z
2021-04-21T13:38:35.433Z
Felipe Gutierrez
<p>Foolproof Accurate Way:</p>
<p>Find the nearest element (vertex, edge, or face). Compute distance to it. Check the angle-weighted psuedonormal to tell if inside or out.</p>
<p>Brute Force:</p>
<pre><code>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
</code></pre>
<p>You can speed this up with a spatial accelerator (octrees, etc).</p>
<p>Why the angle-weighted pseudonormal? What is the angle-weighted pseudonormal? There's a whole proof for it: &quot;Signed Distance Computation using the Angle
Weighted Pseudo-normal&quot; by J. Bærentzen.</p>
<p>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.</p>
<p>There are many such libraries with the implementation if you don't want to write it yourself. VTK has this <a href="https://vtk.org/doc/nightly/html/classvtkImplicitPolyDataDistance.html" rel="nofollow noreferrer">ImplicitPolyDataDistance</a>. LibIGL as well <a href="https://libigl.github.io/tutorial/#signed-distances" rel="nofollow noreferrer">LibIGLs</a>. But there are many light-weight ones to do it as well.</p>
<p>Faster but often less accurate:</p>
<p>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 <a href="https://developer.nvidia.com/gpugems/gpugems3/part-v-physics-simulation/chapter-34-signed-distance-fields-using-single-pass-gpu" rel="nofollow noreferrer">here</a>. Particularly outlining a method to do it fast on the GPU. A similar method exists for Euclidean distance transforms of a voxelized/binarized shape.</p>
<p>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.</p>

CC BY-SA 4.0
2021-04-20T15:01:36.817Z
Is this http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.7988&rep=rep1&type=pdf what you mean by "voxelize/binarize a shape and compute the SDF of the binary image instead"?
Sirius 5
CC BY-SA 4.0
2021-04-20T18:30:54.393Z
Here's an implementation in VTK library https://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.
Andrew Wilson
CC BY-SA 4.0
2021-08-21T00:12:42.433Z
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`
Michael Sohnen
CC BY-SA 4.0
2021-08-23T01:55:36.890Z
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.
Andrew Wilson
CC BY-SA 4.0
2021-04-19T18:55:26.427Z
2021-08-20T04:57:28.683Z
2021-08-20T04:57:28.683Z
Andrew Wilson
<p>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.</p>
<p>Can I get a signed distance to a mesh? How would I calculate it?</p>
<p>I found <a href="https://www.iquilezles.org/www/articles/sdfbounding/sdfbounding.htm" rel="nofollow noreferrer">https://www.iquilezles.org/www/articles/sdfbounding/sdfbounding.htm</a> which seems like it might be what I want, specifically the section where they use an <code>sdMesh</code> method, but I do not understand where the <code>sdTriangles</code> method comes from. The only <code>sdTriangle</code> 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 &quot;behind&quot; the triangle in 3D space (i.e. inside the mesh)?</p>
<p>I am working in Unity / C#, but can translate from other languages.</p>

CC BY-SA 4.0
2021-08-21T00:11:17.220Z
The sdTriangles comes from *I. Quilez's* other article: https://www.iquilezles.org/www/articles/triangledistance/triangledistance.htm. 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.
Michael Sohnen
<3d><algorithm><mesh><signed-distance-field>
How can I get a signed distance (SDF) from a mesh?
Sirius 5
# How can I get a signed distance (SDF) from a mesh?

(Asked by: username_0 on 2021-04-19)

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.

**Tags:** 3d, algorithm, mesh, signed-distance-field

> **Comments:**
> **username_1**: The sdTriangles comes from *I. Quilez's* other article: https://www.iquilezles.org/www/articles/triangledistance/triangledistance.htm. 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.  

---

## 3 answers

### Answer by username_1 on 2021-08-11. Score: 3

**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`.

> **Comments:**
> **username_2**: Hi, username_1, 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.  
> **username_1**: 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.  

---

### Answer by username_3 on 2021-04-21. Score: 1

What you want is a Distance Transform algorithm which can be computed very fast using [JFA](http://www.comp.nus.edu.sg/%7Etants/jfa/i3d06.pdf), 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](https://youtu.be/GvI7qt3kmz4) 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](https://blog.demofox.org/2016/02/29/fast-voronoi-diagrams-and-distance-dield-textures-on-the-gpu-with-the-jump-flooding-algorithm/).


---

### Answer by username_4 on 2021-04-19. Score: 1

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](https://vtk.org/doc/nightly/html/classvtkImplicitPolyDataDistance.html). LibIGL as well [LibIGLs](https://libigl.github.io/tutorial/#signed-distances). 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](https://developer.nvidia.com/gpugems/gpugems3/part-v-physics-simulation/chapter-34-signed-distance-fields-using-single-pass-gpu). 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.

> **Comments:**
> **username_0**: Is this http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.7988&rep=rep1&type=pdf what you mean by "voxelize/binarize a shape and compute the SDF of the binary image instead"?  
> **username_4**: Here's an implementation in VTK library https://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.  
> **username_1**: 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`  
> **username_4**: 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.  

---

