[deleted]
A fast 3D collision detection algorithm
11–20 of 34 posts
Re: A fast 3D collision detection algorithm
#12This is novel indeed! What about non-spherical shapes? Do we assume a spherical bounds and just eat the cost? Either way, narrow phase gets extremely unwieldy when down to the triangle level. Easy for simple shapes but if you throw 1M vertices at it vs 1M vertices you’re going to have a bad time. Any optimization to cut down on ray tests or clip is going to be a win.
Usually you have a render model and a physical model which is a degenerate version of the viewed object, with some objects tailored for picking up, or allowing objects to pass through a curved handle, etc.
I would assume using this algorithm wouldn't necessarily change that creation pipeline.
Re: A fast 3D collision detection algorithm
#13I'm trying to work through the math here, and I don't understand why these two propositions are equivalent: 1) min_{x,y} |x-y|^2 x ∈ A y ∈ B 2) = min_{x,y} d d ≥ |x-y|^2 x ∈ A y ∈ B What is 'd'? If d is much greater than |x-y|^2 at the actual (x, y) with minimal distance, and equal to |x-y|^2 at some other (x', y'), couldn't (2) yield a different, wrong solution? Is it implied that 'd' is a measure or something, such…
I can't read substack on my phone, so I can't see the article, but the correct statement that is closest to what you have written is just that d is any real number satisfying this inequality. We define a subset U of AxBxR by
U={(a,b,x):x>|a-b|^2}
and then were looking for the infimum of (the image of) U under the third coordinate function
d(a,b,x)=x
Re: A fast 3D collision detection algorithm
#14Nice. It's definitely an optimization problem. But you have to look at numerical error.
I had to do a lot of work on GJK convex hull distance back in the late 1990s. It's a optimization problem with special cases.
Closest points are vertex vs vertex, vertex vs edge, vertex vs face, edge vs edge, edge vs face, and face vs face. The last three can have non-unique solutions. Finding the closest vertices is easy but not sufficient. When you use this in a physics engine, objects settle into contact, usually into the non-unique solution space. Consider a cube on a cube. Or a small cube sitting on a big cube. That will settle into face vs face, with no unique closest points.
A second problem is what to do about flat polygon surfaces. If you tesselate, a rectangular face becomes two coplanar triangles. This can make GJK loop. If you don't tesselate, no polygon in floating point is truly flat. This can make GJK loop. Polyhedra with a minimum break angle between faces, something most convex hullers can generate, are needed.
Running unit tests of random complex polyhedra will not often hit the hard cases. A physics engine will. The late Prof. Steven Cameron at Oxford figured out solutions to this in the 1990s.[1] I'd discovered that his approach would occasionally loop. A safe termination condition on this is tough. He eventually came up with one. I had a brute force approach that detected a loop.
There's been some recent work on approximate convex decomposition, where some overlap is allowed between the convex hulls whose union represents the original solid. True convex decomposition tends to generate annoying geometry around smaller concave features, like doors and windows. Approximate convex decomposition produces cleaner geometry.[2] But you have to start with clean watertight geometry (a "simplex") or this algorithm runs into trouble.
Re: A fast 3D collision detection algorithm
#15I’m getting sick of the number of links submitted to HN blasting me with cookie spam bullshit.
Re: A fast 3D collision detection algorithm
#16I'm trying to work through the math here, and I don't understand why these two propositions are equivalent: 1) min_{x,y} |x-y|^2 x ∈ A y ∈ B 2) = min_{x,y} d d ≥ |x-y|^2 x ∈ A y ∈ B What is 'd'? If d is much greater than |x-y|^2 at the actual (x, y) with minimal distance, and equal to |x-y|^2 at some other (x', y'), couldn't (2) yield a different, wrong solution? Is it implied that 'd' is a measure or something, such…
But why would d be much greater. The problem asks to minimise d, and so it cannot be greater than the smallest |x-y|^2.
Re: A fast 3D collision detection algorithm
#17This is novel indeed! What about non-spherical shapes? Do we assume a spherical bounds and just eat the cost? Either way, narrow phase gets extremely unwieldy when down to the triangle level. Easy for simple shapes but if you throw 1M vertices at it vs 1M vertices you’re going to have a bad time. Any optimization to cut down on ray tests or clip is going to be a win.
> Do we assume a spherical bounds and just eat the cost?
We pick the bounding volume that is most suitable to the use case. The cost of non-spherical bounding volumes is often not that severe when compared to purely spherical ones.
https://docs.bepuphysics.com/PerformanceTips.html#shape-opti...
Edit: I just noticed the doc references this issue:
https://github.com/bepu/bepuphysics2/issues/63
Seems related to the article.
Re: A fast 3D collision detection algorithm
#18I'm trying to work through the math here, and I don't understand why these two propositions are equivalent: 1) min_{x,y} |x-y|^2 x ∈ A y ∈ B 2) = min_{x,y} d d ≥ |x-y|^2 x ∈ A y ∈ B What is 'd'? If d is much greater than |x-y|^2 at the actual (x, y) with minimal distance, and equal to |x-y|^2 at some other (x', y'), couldn't (2) yield a different, wrong solution? Is it implied that 'd' is a measure or something, such…
This is the epigraph form of the problem. You try to find the point with the lowest height in the epigraph.
Re: A fast 3D collision detection algorithm
#19Nice to see this! I was writing about this topic 25 years ago: https://www.flipcode.com/archives/Theory_Practice-Issue_01_C...
And part two: https://www.flipcode.com/archives/Theory_Practice-Issue_02_C...
Re: A fast 3D collision detection algorithm
#20Nice. It's definitely an optimization problem. But you have to look at numerical error. I had to do a lot of work on GJK convex hull distance back in the late 1990s. It's a optimization problem with special cases. Closest points are vertex vs vertex, vertex vs edge, vertex vs face, edge vs edge, edge vs face, and face vs face. The last three can have non-unique solutions. Finding the closest vertices is easy but not…
> But you have to look at numerical error.
Yeah I agree, the error analysis could be many blogs in and of itself. I kinda got tired by the end of this blog. I would like to write a post about this in the future. For global solvers and iterative.
> Finding the closest vertices is easy but not sufficient.
As I'm sure you are aware, most GJK implementations find the closest features and then a one shot contact manifold can be generated by clipping the features against each other. When GJK finds a simplex of the CSO, each vertex of the simplex keeps track of the corresponding points from A and B.
> A second problem is what to do about flat polygon surfaces
Modern physics engines and the demo I uploaded do face clipping which handle this. For GJK you normally ensure the points in your hull are linearly independent.