Given:
-
Bullet's current point: x1, y1, and z1
-
A point the Bullet is moving toward: x2, y2, and z2
-
Sphere's center point: sx, sy, and sz
-
Sphere's radius: r
-
And speed of Bullet is in units/frame: n
Frame is define as the time increment between updates.
Asked to Write Code for following:
-
Will the projectile intersect the sphere?
-
If so, where in xyz space will the collision take place?
-
At what angle will the projectile ricochet off the sphere?
-
Give the new velocity vector.
Assumptions:
-
Bullet's current point is its starting point. It is assumed before this point it doesn't matter.
-
Bullet can't move backwards along its path unless it hits something maybe.
-
Bullet can't start inside sphere. Wouldn't make sense to test for hit when inside.
-
Bullet is a point with no mass, so no momentum is not factored in.
-
Ricochet angle (in radians) is to the tangent plain's surface
at hit point, not to the normal of the plain.
-
Frame or how many frames (time) to hit, or distance to hit point was not wanted but I provide.
-
Structure for the answer was not set so had to create one.
-
With use of floats there is some error due to imprecision
in values of floats. See Considerations
Steps to Solve:
-
Find unit vector of bullet
-
Get line equations for X, Y, & Z using
ds as distance along line from point 1.
-
Get distance equation from any point on
line to center of sphere.
-
Solve for D and take derivative with respect
to ds.
-
Solve for ds by setting D/ds equal to zero.
-
Test if ds >= 0 then continue, if ds is neg.
means bullet has to go backwards to hit sphere.
-
Put ds back into distance equations and
get smallest distance form line to sphere.
-
Test if D <= R then continue Hit happen,
were D is distance squared & R is radius squared.
-
Use distance equation again with D = R and
solve for ds, ds will have two solutions.
-
The correct ds is the smallest non negative
answer.
-
Put this ds into line equations for X,
Y, & Z to get point were bullet hits the sphere.
-
Find unit vector form point on sphere to
center.
-
Use dot product with lines unit vector
to find angle between lines vector and sphere vector.
-
Take 90 - angle found to get ricochet
angle.
-
Calculate the two vectors normal to and
parallel to tangent plain on sphere though hit point.
-
Reverse normal vector and add to parallel
vector to get ne ricochet vector of bullet.
-
Multiply by speed of bullet to get new
velocity vector.
-
Done.
(JavaScript example )
-
Good points about this method
-
Considerations
-
What if Sphere is moving
-
CODE
Some Notes:
I found out about this contest on Sept. 6th on comp.games.development.programming.algorithms news group.
I thought cool I never really though about 3d collision before, I'm an ex-game modeler/programmer but 3D code was done by others.
I started out on Sept. 9 with idea of testing each frame for a hit.
This was going good when I ran into the problem of finding the angle of ricochet after four days of a couple hours each.
On Sept. 13, it occur to me to use my vast knowledge from five years of Collage (with a BS in Aerospace Engineering),
and math classes from Calculus I to Adv. Engineering math, over 21 credit hours of math.
It then boiled down to a couple of unit vectors, the distance formula between two points in 3D,
a derivative and some sin and cos stuff of a right triangle. This solution lets you check if there will ever be a hit and find out
were the hit happens all with out having to check each frame. You can find out when easily but that wasn't a requirement to find.
This took me about 6 hours of time mostly used for looking up and checking that every thing check math wise.
Had a lot of time because Hurricane Floyd shut down the plant were I work for 2 and a half days.
It took me about 4 hours to code, about 2 hours to document plus another 4 to pretty it up and stuff.
All said about 3 days worth of work. Finished on Sept. 16. Veified it using javascript on Sept. 17, and on Sept. 19th
I put it in nice table/form layout in javascript and put some checks in for input values another 4 hours.
On Sept. 20th I did some through testing and found some test to check for.
Had to add test before acos in java because I was getting a number 1.000000004 which acos (inverse cos) doesn't like, set to 1.
Complied and test and it work fine on sept 21st. Did some minor clean up of explanation on the 27th.
Not Bad I think.
I think I could even crank out a moving constant speed sphere solution in about 4 to
6 hours maybe.
Well it took me a little longer about 8 hours over Sept. 19th & 20th.
Take a look, I added out put for other data along the way.
(Javascript example )
Bullets unit vector.
bullet's unit vector is used to define the bullet's path at any point along it.
U = Ux + Uy + Uz
Find distances form point 1 to point 2 in X, Y, & Z directions.
X = x2 - x1
Y = y2 - y1
Z = z2 - z1
Find distance between to points.
D = (X^2 + Y^2 + Z^2)^.5
Find Unit Vector by dividing each component by D.
Ux = X/D
Uy = Y/D
Uz = Z/D
Get line equations for X, Y, &
Z using ds as distance along line from point 1.
Xt = x1 + Ux*ds
Yt = y1 + Uy*ds
Zt = z1 + Uz*ds
Get distance equation from any
point on line to center of sphere.
Distance equation is D = (X^2 + Y^2 + Z^2)^.5, but it can be kept in the form of D^2 = X^2 + Y^2 + Z^2
because we can compare to R^2 which is radius of sphere squared.
X = sx - Xt = sx - (x1 + Ux*ds)
Y = sy - Yt = sy - (y1 + Uy*ds)
Z = sz - Zt = sz - (z1 + Uz*ds)
D^2 = (sx - x1 - Ux*ds)^2 + (sy - y1 - Uy*ds)^2 + (sz - z1 - Uz*ds)^2
Expand out squares:
For X:
(sx - x1 - Ux*ds)^2 = sx^2 - 2sx*x1 + x1^2 - 2(sxUx - x1Ux)ds + Ux^2*ds^2
let C1 = sx^2 - 2sx*x1 + x1^2
and C2 = sxUx - x1Ux
(sx - x1 - Ux*ds)^2 = C1 - 2C2*ds +
For Y:
(sy - y1 - Uy*ds)^2 = sy^2 - 2sy*y1 + y1^2 - 2(syUy - y1Uy)ds + Uy^2*ds^2
let C3 = sy^2 - 2sy*y1 + y1^2
and C4 = syUy - y1Uy
(sy - y1 - Uy*ds)^2 = C3 - 2*C4*ds + Uy^2*ds^2
For Z:
(sz - z1 - Uz*ds)^2 = sz^2 - 2sz*z1 + z1^2 - 2(szUz - z1Uz)ds + Uz^2*ds^2
let C5 = sz^2 - 2sz*z1 + z1^2
and C6 = szUz - z1Uz
(sz - z1 - Uz*ds)^2 = C5 - 2*C6*ds + Uz^2*ds^2
So
D^2 = C1 + C3 + C5 - 2(C2 + C4 + C6)*ds + (Ux^2 + Uy^2 + Uz^2)*ds^2
Note: Ux^2 + Uy^2 + Uz^2 = 1 because U is a unit vector.
D^2 = C1 + C3 + C5 - 2(C2 + C4 + C6)*ds + ds^2
Solve for D and take derivative
with respect to ds.
D = (C1 + C3 + C5 - 2(C2 + C4 + C6)*ds + ds^2)^.5
dD = (.5(C1 + C3 + C5 - 2(C2 + C4 + C6)*ds + ds^2)^-.5)*(- 2(C2 + C4 + C6) + 2ds)
dD = (-(C2 + C4 + C6) + ds) / ((C1 + C3 + C5 - 2(C2 + C4 + C6)*ds + ds^2)^.5)
Solve for ds by setting dD equal
to zero.
We set dD to zero because that is were the distance form line to Sphere's center is smallest
and the only way dD can be zero is if -(C2 + C4 + C6) + ds = 0
So ds = (C2 + C4 + C6)
Test if ds >= 0 then continue, if
ds is neg. means bullet has to go backwards to hit sphere.
ds could be negative which would mean the line is closest behind point
1.
Since the bullet starts at point 1 and moves to pt 2 there can be no
hit.
Put ds back into distance equations
and get smallest distance form line to sphere.
Put ds back into D2 = C1 + C3 + C5 - 2(C2 + C4 + C6)*ds + ds^2
D2 = C1 + C3 + C5 - 2(C2 + C4 + C6)(C2 + C4 + C6) + (C2 + C4 + C6)(C2
+ C4 + C6)
So
D2 = C1 + C3 + C5 - (C2 + C4 + C6)(C2 + C4 + C6)
Test if D <= R then continue
Hit happen, were D is distance squared & R is radius squared.
So if D2 which is distance squared (D^2) form center to closest point
on line is less than R2 = r^2 then we must have hit the Sphere.
Use distance equation again with
D = R and solve for ds, ds will have two solutions.
Now set D2 the value of R2 and solve for the two ds's that will solve
the equitation.
Use the aX^2 + bX + c = 0 solution of
X = (-2b - (b^2 + 4ac)^.5)/2a
X = (-2b + (b^2 + 4ac)^.5)/2a
Set a variable sq to (b^2 + 4ac)^.5
sq = (4(C2 + C4 + C6)(C2 + C4 + C6) + 4(C1 + C3 + C5 - R2))^.5
Solve or two ds's
ds = (-4*(C2 + C4 + C6) - sq )/2
or
ds = (-4*(C2 + C4 + C6) + sq)/2
The correct ds is the smallest non
negative answer.
This is for a check just in case point one might have been in Sphere to begin
with.
Put this ds into line equations
for X, Y, & Z to get point were bullet hits the sphere.
Xt = x1 + Ux*ds
Yt = y1 + Uy*ds
Zt = z1 + Uz*ds
So hit point is (Xt, Yt, Zt)
Find unit vector form point on
sphere to center.
Now we need to find the angle the bullet has to the tangent plain of
the sphere at the hit point.
First we need the normal to this tangent plain which is the unit vector
form hit point to center.
T = Tx + Ty + Tz
X = sx - Xt
Y = sy - Yt
Z = sz - Zt
D = (X^2 + Y^2 + Z^2)^.5
Tx = X/D
Ty = Y/D
Tz = Z/D
Use Dot product with lines unit
vector to find angle between lines vector and sphere vector.
Now that we have unit vector of tangent plain we can get the angle
between the bullet unit vector and plains.
This is done by use of the Dot product.
cos(theta) = (U dot T)/(|U||T|)
since U and T are unit vectors |U| = 1 and |T| = 1
So cos(theta) = U dot V solve for theta
and U dot T = Ux*Tx + Uy*Ty + Uz*Tz
theta = acos(Ux*Tx + Uy*Ty + Uz*Tz) might be different depending on complier.
Take 90 - angle found to get
ricochet angle.
The theta found is the angle from bullet's path to the normal to tangent plain.
The ricochet angle is pi_half - theta.
theta is given in terms of radians and pi_half = 1.570796326795.
ricochet angle = pi_half - theta in radians.
Calculate the two vectors normal
to and parallel to tangent plain on sphere though hit point.
Now we need the two components perpendicular and parallel to the tangent
plain.
Uprep = U sin(ricochet angle)
Upara = U - Uperp
Reverse normal vector and add
to parallel vector to get new ricochet vector of bullet.
Bullet's Upara will stay the same but its Uperp will point in opposite
direction which means we take the negative of it.
Then add the two unit vectors back together to get new unit vector in
direction of ricochet.
U = Upara - Uperp
Multiply by speed of bullet
to get new velocity vector.
Take this new U and multiply by n the speed of bullet to get new velocity vector.
Done (JavaScript example )
You now know if the Bullet hit the stationary Sphere.
Were in 3D space it hit the Sphere.
The angle of ricochet of the Bullet to tangent plain surface
and the velocity vector of Bullet's new path.
Good points about this method
This is a good way to test for a hit because you don't need to check each frame for a hit and you
can easily find out what frame the hit occurs by take distance form point 1 to sphere (ds) divid by speed
of bullet (n). and added to your current frame.
Considerations
Some things to consider about this are:
With the use of floats there is some error due to floats not being
precise ie( 0 could be 1.453e-23).
Hit could happen between frames.
This could be change for cylinder and/or box test also.
What if Sphere is moving (JavaScript example )
If Sphere moves along a straight line at a constant velocity some added
parameters are needed but it should still
be possible to find if a hit would occur and were on the sphere, and still with
out having to test every time or frame.
CODE
Code uses:
3 square root calls
1 acos (arccos) call
1 sin call
Every thing else is adds, subtractions, multiplies and divides.
At every possible chance test for possible hit is done and if not possible
return FALSE.
Code is in C and all variables are global for speed with two structs created
for 3d points and the answer.
|