Sign in to follow this  

Need help undertsanding Sweep Test Math.

Recommended Posts

Im reading Kasper Fauerby's article on ellipsoid collision detection. I understand most of it, however the only part that gets me is the math behind the vertex and edge sweep test. What i dont get is how he turns ( C(T) - P ) * ( C(T) - P ) Where C(T) = basePoint + (Velocity * T) into the form At^2 + Bt + C Where A = Velocity * Velocity B = 2 * Velocity * (basePoint - Vertex) C = || basePoint - Vertex ||^2 -1 I get how quadratic equations can be solved, and how they can have two answers and such. I get what a root is, im finishing college algerbra this semester with a "B", so i do have some math knowledge under my belt. Besides the edge test which is next, i get the whole article. But for now i just want to focus on the sweep test against a vertex, which is the simpler of the two. Of course i could just copy and paste someone elses pre-made code into my project, however for learning purposes i want to know how to do it myself so in time i wont have to copy and paste and i can just refer to most of it off the top of my head.

Share this post

Link to post
Share on other sites
I'll try :

for vertex collisions, a point P is on sphere [C, r] if (P - C)^2 = r^2

the point P is also on the ray [O, D], so it satisfies the parametric equation P(t) = O + D * t, where t is the unknown

So in the first equation you replace P by P(t) and you get

((O - C) + D * t)^2 - r^2 = 0 (eq 1)

(eq 1) is in the form (A + B * t)^2 - C = 0, so expanding you get...
[(B.B)]*t^2 + [2*(B.A)]*t + [(A.A)-C] = 0

so, when you develop (eq 1), you get...

[(D)^2] * t^2 + [2 * (O - C) . (D)] * t + [(O - C)^2 - r^2] = 0

that's where the form [a]*t^2 + [b]*t + [c] = 0, comes from, where...

a = [D^2] = [D . D]
b = [2 * (O - C) . (D)]
c = [(O - C)^2 - r^2] = [(O - C) . (O - C) - r^2]

for edge collision (which is equivalent to a cylinder - ray intersection test), it's almost identical, the equation to satisfy is :

((P - C) x H)^2 = r^2 * (H.H)

where H is the direction of the cylinder (not normalised), r the radius, C a point on the cylinder centre. Using a segment [A, B], you would get...

((P - A) x (B - A))^2 = r^2 * ((B - A).(B - A))

the equation solves the same way. replace P by O + D * t, and you will get...

let AOxAB = (O - A) x (B - A)
let DxAB = D x (B - A)
let AB2 = (B - A) . (B - A)

a = (DxAB . DxAB)
b = 2 * (DxAB . AOxAB)
c = (AOxAB . AOxAB) - r*r * ((B - A) . (B - A))

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this