←back to thread

A fast 3D collision detection algorithm

(cairno.substack.com)
269 points OlympicMarmoto | 1 comments | 09 Jul 25 14:12 UTC | HN request time: 0.21s | source

I discovered this collision detection algorithm during COVID and finally got around to writing about it.

github repo: https://github.com/cairnc/sat_blog

Show context
msteffen ◴[09 Jul 25 17:28 UTC] No.44512706[source]▶
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?
replies(4): >>44512964 #>>44513600 #>>44514056 #>>44515013 #
1. mathgradthrow ◴[09 Jul 25 17:53 UTC] No.44512964[source]▶
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