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

1–10 of 34 posts

Re: A fast 3D collision detection algorithm

#3

Post by reactordev »

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.

Re: A fast 3D collision detection algorithm

#4

Post by bruce343434 »

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.

Most likely this can be preceded by testing branches of some spatial hierarchy datastructure, 1 million squared is a lot to compute no matter the algorithm

Re: A fast 3D collision detection algorithm

#5

Post by [deleted] »

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.

[deleted]

Re: A fast 3D collision detection algorithm

#6

Post by reactordev »

bruce343434 wrote: post #4
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.

Most likely this can be preceded by testing branches of some spatial hierarchy datastructure, 1 million squared is a lot to compute no matter the algorithm

Without optimizations of the vertices buffer, correct, it’s a 1T loop. But we can work on faces and normals so that reduces it by a factor of 3. We can octree it further as well spatially but…

There’s a really clever trick Unreal does with their decimation algorithm to produce collision shapes if you need to. I believe it requires a bake step (pre-compute offline).

I’d be fine with a bake step for this.

Re: A fast 3D collision detection algorithm

#7

Post by OlympicMarmoto »

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 you mean non-convex shapes? You can do a convex decomposition and then test all pairs. Usually games accelerate this with a BVH.

Re: A fast 3D collision detection algorithm

#9

Post by msteffen »

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 that it's somehow constrained or bounded to prevent this?

Re: A fast 3D collision detection algorithm

#10

Post by leoqa »

Aside: I learned the Sep Axis Theorem in school and often use it for interviews when asked about interesting algorithms. It's simple enough that you can explain it to non-technical folks. "If I have a flashlight and two objects, I can tell you if they're intersected by shining the light on it". Then you can explain the dot product of the faces, early-exit behavior and MTV.
Post reply on HN