<p>Ive been thinking about the same problem. I suppose rather than finding the level sets, it might be more useful to think of it as finding the local maxima  of the sum of the squares of the positive/internal part of the SDF; which should behave somewhat like the hypothetical point of contact assuming both bodies were elastic and yielding equally.</p>
<p>That function should have maxima; though not particularly unique ones, if you take the case of a box lying on a plane; thered be a square-shaped maximum.</p>
<p>Of course there can be multiple local maxima too, in case of a banana-shaped or concave object.</p>
<p>Either way we should be able to find such maxima using some type of descent. But I dont know if itd be efficient. And then there is the question of how to create the seed-points. One might take the extrema, or vertices of a convex hull, say, as seed points to start doing descent on other SDFs. But you can already see where that might go wrong in case of two cubes hitting edgewise.</p>
<p>You can put more sampling points on the edge, but without edge-specific logic, you are going to be stuck with the resolution of the sampling of that edge; though maybe it would work fine in practice with a rather coarse sampling, and just a fixed few descent steps? Perhaps caching of points from the previous frame would make for really decent average-case performance? Hard to tell without giving it a spin, and I am not aware of any prior work doing so.</p>

CC BY-SA 4.0
2021-11-27T15:45:37.080Z
2021-11-27T15:45:37.080Z
Eelco Hoogendoorn
<p>I was wondering if there are any techniques for calculating the intersection point/s between two or more distance fields.</p>

CC BY-SA 4.0
2019-09-17T09:24:06.567Z
Numerical root finders. Analytically you cannot hope for much for anything more complex than very simple objects.
lightxbulb
CC BY-SA 4.0
2019-09-17T09:57:04.660Z
thanks for the reply @lightxbulb. I was hoping for some kind of smart raymarching algorithm for finding the roots probably using some kind of gradient descent for realtime applications.
Alexandros Mourtziapis
CC BY-SA 4.0
2019-09-17T10:05:06.160Z
An intersection point of two surfaces described by sdfs $f$ and $g$ is simply $x : f(x) = g(x) = 0$. Provided that $f$ and $g$ are not simplistic, then the roots of that system of equations cannot be found analytically, that is why I mentioned numerical root finding. Under additional constraints you can use gradient or subgradient descent, since then you can try to minimize an energy of the form: $\alpha|f(x)|^p + \beta|g(x)|^q$, which is minimized for $f(x) = g(x) = 0$. If the surfaces do not intersect, it will still be a closest point in some sense.
lightxbulb
CC BY-SA 4.0
2019-09-17T10:25:52.333Z
I want to ask one more thing. What would you say about precalculating and storing offline a set of points X1n & X2n where f(X1n)=0 g(X2n)=0 respectively and then using that information and I guess some kind of acceleration structure find at least some kind of approximation of the intersection points? Would it work? Could it be done in a better more efficient way? Thanks
Alexandros Mourtziapis
CC BY-SA 4.0
2019-09-17T10:35:30.333Z
A lot of things may be done. Storing points is not ideal however, since all the points you pick may turn out to not correspond to the intersection. One possibility is to discretize your sdf, and then check all voxels within some threshold, and extract voxels for which both sdfs are close to 0. Another possibility is triangulating the surface and then intersecting the triangles from both surfaces. There are many possible solutions beyond these two examples too.
lightxbulb
<mathematics><signed-distance-field>
SDF collision detection
Alexandros Mourtziapis
# SDF collision detection

(Asked by: username_0 on 2019-09-17)

I was wondering if there are any techniques for calculating the intersection point/s between two or more distance fields.

**Tags:** mathematics, signed-distance-field

> **Comments:**
> **username_1**: Numerical root finders. Analytically you cannot hope for much for anything more complex than very simple objects.  
> **username_0**: thanks for the reply @username_1. I was hoping for some kind of smart raymarching algorithm for finding the roots probably using some kind of gradient descent for realtime applications.  
> **username_1**: An intersection point of two surfaces described by sdfs $f$ and $g$ is simply $x : f(x) = g(x) = 0$. Provided that $f$ and $g$ are not simplistic, then the roots of that system of equations cannot be found analytically, that is why I mentioned numerical root finding. Under additional constraints you can use gradient or subgradient descent, since then you can try to minimize an energy of the form: $\alpha|f(x)|^p + \beta|g(x)|^q$, which is minimized for $f(x) = g(x) = 0$. If the surfaces do not intersect, it will still be a closest point in some sense.  
> **username_0**: I want to ask one more thing. What would you say about precalculating and storing offline a set of points X1n & X2n where f(X1n)=0 g(X2n)=0 respectively and then using that information and I guess some kind of acceleration structure find at least some kind of approximation of the intersection points? Would it work? Could it be done in a better more efficient way? Thanks  
> **username_1**: A lot of things may be done. Storing points is not ideal however, since all the points you pick may turn out to not correspond to the intersection. One possibility is to discretize your sdf, and then check all voxels within some threshold, and extract voxels for which both sdfs are close to 0. Another possibility is triangulating the surface and then intersecting the triangles from both surfaces. There are many possible solutions beyond these two examples too.  

---

## 1 answers

### Answer by username_2 on 2021-11-27. Score: 1

Ive been thinking about the same problem. I suppose rather than finding the level sets, it might be more useful to think of it as finding the local maxima of the sum of the squares of the positive/internal part of the SDF; which should behave somewhat like the hypothetical point of contact assuming both bodies were elastic and yielding equally.

That function should have maxima; though not particularly unique ones, if you take the case of a box lying on a plane; thered be a square-shaped maximum.

Of course there can be multiple local maxima too, in case of a banana-shaped or concave object.

Either way we should be able to find such maxima using some type of descent. But I dont know if itd be efficient. And then there is the question of how to create the seed-points. One might take the extrema, or vertices of a convex hull, say, as seed points to start doing descent on other SDFs. But you can already see where that might go wrong in case of two cubes hitting edgewise.

You can put more sampling points on the edge, but without edge-specific logic, you are going to be stuck with the resolution of the sampling of that edge; though maybe it would work fine in practice with a rather coarse sampling, and just a fixed few descent steps? Perhaps caching of points from the previous frame would make for really decent average-case performance? Hard to tell without giving it a spin, and I am not aware of any prior work doing so.


---

