Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A fast 3D collision detection algorithm

cairno.substack.com

Post reply on HN
Print view View original

21–30 of 34 posts

Re: A fast 3D collision detection algorithm

#21

Post by CamperBob2 »

Animats wrote: post #14

Nice. 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…

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.

I wonder if it would be smart to restate the problem in just those terms -- managing bounding-volume overlap rather than interpenetration at the geometric level.

If everything is surrounded by bounding spheres, then obviously collision detection in the majority of cases is trivial. When two bounding spheres do intersect, they will do so at a particular distance and at a unique angle. There would then be a single relevant quantity -- the acceptable overlap depth -- that would depend on the angle between the BV centers, the orientation of the two enclosed objects, and nothing else. Seems like something that would be amenable to offline precomputing... almost like various lighting hacks.

Ultimately I guess you have to deal with concavity, though, and then the problem gets a lot nastier.

Re: A fast 3D collision detection algorithm

#22

Post by reactordev »

andrewmcwatters wrote: post #12
reactordev wrote: post #3

This 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.

I’m trying to find a way to NOT have hull models included in my games. Saving players potentially GBs of disk space.

Constructing Bvh’s on the fly from the high fidelity models we use. Without incurring a performance penalty like we are. So we can improve collision detection instead of clipping due to low res hull models.

The OP’s source code builds a Bvh but it still does so in a way that we’re able to clog it with 34M vertices. Sadly, we’re still going to have to explode geometry and rebuild a hierarchy in order to iterate over collisions fast. I do like the approach OP took but we both suffer from the same issues.

Re: A fast 3D collision detection algorithm

#23

Post by reactordev »

bob1029 wrote: post #17
reactordev wrote: post #3

This 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 arti…

Yeah triangle-triangle is really dependent on number of triangles.

I noticed that issue is 6 years old, what’s the current state?

Re: A fast 3D collision detection algorithm

#24

Post by [deleted] »

reactordev wrote: post #22
andrewmcwatters wrote: post #12

Earlier quoted context omitted.

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.

I’m trying to find a way to NOT have hull models included in my games. Saving players potentially GBs of disk space. Constructing Bvh’s on the fly from the high fidelity models we use. Without incurring a performance penalty like we are. So we can improve collision detection instead of clipping due to low res hull models. The OP’s source code builds a Bvh but it still does so in a way that we’re able to clog it with…

[deleted]

Re: A fast 3D collision detection algorithm

#26

Post by markisus »

msteffen wrote: post #9

I'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 think you are missing that d, x, and y are variables that get optimized over. Any choice of d lower than the the solution to 1) is infeasible. Any d higher than the solution to 1) is suboptimal.

edit: I see now that the problem 2) is missing d in the subscript of optimization variables. I think this is a typo.

Re: A fast 3D collision detection algorithm

#28

Post by oasisaimlessly »

CamperBob2 wrote: post #21
Animats wrote: post #14

Nice. 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…

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. I wonder if it would be smart to restate the problem in just those terms -- managing bounding-volume overlap rather than interpenetration at the geometric level. If everything is surrounded by bounding spheres, then obviously collision detection in the ma…

Most physics engines do indeed do this and call it something like "collision margin"[1].

[1]: https://gamedev.stackexchange.com/questions/113774/why-do-ph...

Re: A fast 3D collision detection algorithm

#29

Post by msteffen »

OlympicMarmoto wrote: post #18
msteffen wrote: post #9

I'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. https://en.wikipedia.org/wiki/Epigraph_(mathematics)

Ah, got it, thanks!!

Re: A fast 3D collision detection algorithm

#30

Post by contingencies »

Animats wrote: post #14

Nice. 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…

I am consistently amazed at your depth of knowledge. Can we have a meal? My shout. I'm crossing the US a lot for fundraising right now, probably nearby someplace. Email in profile.
Post reply on HN