I was wondering if there are any techniques for calculating the intersection point/s between two or more distance fields.
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ Numerical root finders. Analytically you cannot hope for much for anything more complex than very simple objects. $\endgroup$– lightxbulbCommented Sep 17, 2019 at 9:24
-
$\begingroup$ 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. $\endgroup$– Alexandros MourtziapisCommented Sep 17, 2019 at 9:57
-
1$\begingroup$ 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. $\endgroup$– lightxbulbCommented Sep 17, 2019 at 10:05
-
$\begingroup$ 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 $\endgroup$– Alexandros MourtziapisCommented Sep 17, 2019 at 10:25
-
$\begingroup$ 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. $\endgroup$– lightxbulbCommented Sep 17, 2019 at 10:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
