Archived

This topic is now archived and is closed to further replies.

s_cloudx

Hit Scan Colllsion

Recommended Posts

s_cloudx    162
How do I create hit scan (Like in Counter-strike, where all their weapons hit enemies kilometers away at the click of the mouse button) collisions in 3D?

Share this post


Link to post
Share on other sites
davepermen    1047
raytracing/raycasting..

think about it. the shoot follows a line. does that line intersect with the world? if so, you hit something. if not, you didn''t. if you hit something, find out what.

"take a look around" - limp bizkit
www.google.com

Share this post


Link to post
Share on other sites
drslush    122
Basically what you are looking for is an alogrithm for a ray-sphere intersection. Given the vector representing the direction the player is aiming, just find if there is an intersection with the given sphere (defining the bounds of the enemy).

If you want to find where the bullet hits a wall in a level, I suggest using a BSP tree to find the intersection.

Share this post


Link to post
Share on other sites
s_cloudx    162
Can you please explain a little more on raycasting please?

Im using an octree but since the octree only holds a limited number of game objects I''ve been looking for other techniques. Im planning to put some sniper weapon into the game, btw.

Share this post


Link to post
Share on other sites
oliii    2196
there are loads of docs on the net about ray-casting.

basically, you create a ray, using a start position vector and a direction (normalised), for a sphere/ray intersection, you solve a simple second order equation, it goes like this


  
bool Intersect(Vector RayPos, Vector RayDir, Vector SpherePos, float SphereRad, float &t, float tmax)
{
.........
.........
.........
}


- t is the distance of intersection, if it intersects
- tmax is the maximum distance allowed for intersection (this is useful to prioritise collisions. You can simply reset the maximum distance to the last intersection distance found, before testing more objects, which will automatically give you the first intersection in the end).


Ray equation
-------------
P on the ray = RayPos + RayDir * t

Sphere equation
----------------
P on the sphere verifies the equation (P - SpherePos)^2 = SpehreRad^2

so, for a point that is both on a ray and a sphere (i.e. the points of intersection), you replace P by the ray equation

--------------------------------------------------------------
| ((RayPos - SpherePos) + RayDir * t)^ 2 - SphereRad^2 = 0 |
--------------------------------------------------------------

so
[RayDir * RayDir] * t^2 +
[2 * (RayDir * (RayPos - SpherePos))] * t +
[((RayPos - SpherePos)^2 - SphereRad^2] = 0;

you need to solve an equation in the form equation
a.t^2 + b.t + c = 0, so


  
c = ((RayPos - SpherePos) * (RayPos - SpherePos)) - (SphereRad * SphereRad);
b = 2.0f * (RayDir * (RayPos - SpherePos));
a = (RayDir * RayDir);

d = b*b - 4*a*c

if (d < 0.0f)
return false;

if (a < 0.000001f) // this should never happen, but...

return false;

t0 = (-b - sqrt(d)) / (2*a);
t1 = (-b + sqrt(d)) / (2*a);



t1 will always be >= t0, because a is always > 0, and sqrt(d) is always > 0

therefore,

  
if (t1 < 0.0 || t0 > tmax)
return false;

else if (t0 > 0.0f)
t = t0;
else
t = t1;
[source]

and in the end, the point of collision on the sphere would be
P = RayPos + RayDir * t, if a collision is found

the same principle applies for triangles and boxes collisions. It''s the principle of ray casting. Fire a ray, calculate the intersection if any.

Share this post


Link to post
Share on other sites
oliii    2196
np.

Watchout for the accuracy of the algorithm. I did that on the top of my head. But you get the drift. Solve a simple 2nd order equation. Although 24 hours later, I can''t find anything wrong with what I gave you.

Share this post


Link to post
Share on other sites
s_cloudx    162
oliii, Something's wrong. I put your code into my game and I'm getting wrong values.

This is the code (off the top of my head. I don't have internet access at home):

Note: I assumed you meant t as a Vector.

      
bool Intersect(Vector RayPos, Vector RayDir, Vector SpherePos, float SphereRad, Vector &t, float tmax)
{
c = ((RayPos - SpherePos) * (RayPos - SpherePos)) - (SphereRad * SphereRad);
b = 2.0f * (RayDir * (RayPos - SpherePos));
a = (RayDir * RayDir);
d = b*b - 4*a*c;

if (d < 0.0f)
return false;

if (a < 0.000001f) // this should never happen, but...

return false;

t0 = (-b - sqrt(d)) / (2*a);
t1 = (-b + sqrt(d)) / (2*a);
if (t1 < 0.0 || t0 > tmax)
return false;
else if (t0 > 0.0f)
t = t0;
else t = t1;

if (SpherePos == RayPos + RayDir * t)
return true;
}


and I call it like so:


       
if (Intersect(Avatar->Position,
Normalize(Avatar->Camera->LookAt),
Target->Position,
Target->Spheresize,
t,
9999))
DoCollision(Avatar, Target);


btw, I don't understand how d was solved. Can you kindly explain? I appreciate any help.

[edited by - s_cloudx on May 7, 2003 12:47:54 AM]

Share this post


Link to post
Share on other sites
oliii    2196
you got your knickers in a twist...

t is a float, and is the distance from your avatar position to the intersection point.

this is what I would do


  
float t_hit = 10000.0f;

CTarget* pFirstHitTarget=NULL;

for(int i = 0; i < NumberOfTargets; i ++)
{
float t;

if (Intersect(Avatar->Position,
Normalize(Avatar->Camera->LookAt),
Target[i].Position,
Target[i].Spheresize,
t,
t_hit))
{
t_hit = t;
pFirstHitTarget = &Target[i];
}
}

if (pFirstHitTarget != NULL)
{
DoCollision(Avatar, pFirstHitTarget, t_hit);
}


you can use t_hit in the DoCollision() to apply damage. if t_hit is huge, apply less damage, if it is small (point blank range), apply the maximum damage.

Note, this algo will return the first target hit by the ray. If you want the ray to go through all the targets, you just move the DoCollision() into the if().

Share this post


Link to post
Share on other sites
oliii    2196
OK, as far as the equation is concerned, it''s a scond order equation, in the form

a.x^2 + b.x + c = 0

going back to secondary school, you solve a second order equation by calculating a number d, which is

d = b.b - 4.a.c

if d < 0, there is no solution to the equation (no intersection, the sphere is too far from the ray).

if d > 0, then you will have two possible solutions

x0 = (-b - sqrt(d)) / (2.a)
x1 = (-b + sqrt(d)) / (2.a)

as far as you''re concerned, you''re only interested in the first positive solution. if x0 < 0.0 and x1 < 0.0, then it means that the sphere is behind the avatar, hence no collision.

if x0 < 0.0 and x1 > 0.0, it means that the avatar is INSIde the sphere.

if x0 > 0.0 and x1 > 0.0, it means that the sphere is in front of the ray, and has been intersected in two points. So you take the minimum between the two x0 and x1, and you''ll find the distance of the avatar position to the closest intersection with the sphere.

Basically, take the minimum positive value, that will return the distance of the intersection point to the avatar position.


if you want the intersection point (to do a particle effect), you do

P = Avatar->Position + Normalize(Avatar->Camera->LookAt) * t_hit;

Share this post


Link to post
Share on other sites
s_cloudx    162
Okay, I understood how the second order is solved.

But, I''m still confused. I thought when a math involves a Vector, the result is a vector. Like so:

Vector RayPos;
Vector SpherPos;
float SphereRad;

wouldn''t the following create a vector?

c = ((RayPos - SpherePos) * (RayPos - SpherePos)) - (SphereRad * SphereRad);

like so,

c = ((Vector - Vector) * (Vector - Vector)) - (float * float)
c = (Vector * Vector) - float
c = Vector

thus, the result is a vector?

Or am I doing something terribly wrong here?

Share this post


Link to post
Share on other sites
vanillacoke    122
You can''t subtract a scalar from a vector, so that expression only makes sense if the * is a dot product, which gives you a scalar from two vectors.

Share this post


Link to post
Share on other sites
s_cloudx    162
So, it''s not correct to subtract a scalar value from a vector? I always thought that:

Vector - scalar = Vector(Vector.x - scalar, Vector.y - scalar, Vector.z - scalar)

So, what is the correct way to subtract scalar value from a vector?

Share this post


Link to post
Share on other sites
oliii    2196
you can substract vectors to vectors so you''d do

Vector V (V.x, V.y, V.z)
Vector S (scalar, scalar, scalar)

Vector W = V - S

would achieve what you want

Share this post


Link to post
Share on other sites
s_cloudx    162
But then, the result would be a vector and t would have to be a vector, too. Oh, dear.

EDIT: I sounded like a ninnynack, so I'll try to say it in another way. *AHEM*

Currently, this is what my code looks like:


Vector c = ((RayPos - SpherePos) * (RayPos - SpherePos)) - (SphereRad * SphereRad);
Vector b = 2.0f * (RayDir * (RayPos - SpherePos));
Vector a = (RayDir * RayDir);
Vector d = b*b - 4*a*c;


Later in the code, I have this:


t0 = (-b - sqrt(d)) / (2*a);
/*...*/
t = t0; //where t is a Vector



If I make t a float, I would have to decide if I should put in t0's x, y, or z value. But since you said t is the distance of how far an object is, I knew I made a mistake somewhere. I suspect that my Vector maths are wrong. Could someone please aid me here?

BTW, oliii, I really appreciate your help. Thank you!

[edited by - s_cloudx on June 4, 2003 8:45:34 PM]

Share this post


Link to post
Share on other sites
oliii    2196
quote:
Original post by s_cloudx
But then, the result would be a vector and t would have to be a vector, too. Oh, dear.

If I make t a float, I would have to decide if I should put in t0''s x, y, or z value. But since you said t is the distance of how far an object is, I knew I made a mistake somewhere. I suspect that my Vector maths are wrong. Could someone please aid me here?

BTW, oliii, I really appreciate your help. Thank you!






You got it all wrong

t is a float and CANNOT be equal to a vector. A vector length maybe, or a vector component (either x, y or z), or a dot product of 2 vectors, or any vector operations that return a float.

a, b, c are floats too. They are NOT vectors. Look into the equations for ''c'' for example.

(RayPos - SpherePos)*(RayPos - SpherePos) is a dot product of two vector substractions. the substractions produce a vector, but the dot products of the two substractions will turn the result into a scalar. (SphereRad * SphereRad) is a product of scalars, which return a scalar. so a = scalar + scalar = scalar.

a, b, c are lowercase names. This usually means they are either a float or a int. Basically a scalar.

t is a float and is the parametric component for the line equation

P = RayPos + t * RayDir;

Raypos is a vector, Raydir is a vector, (t * raydir) is also a vector (t * RayDir = Vector(RayDir.x*t, Raydir.y*t, RayDir.z*t)).

I use equations in parametric form, which applies into any dimensions (2D, 3D, whatever), and you solve the set of equations for a parameter which is a scalar, with no units attached to it. It''s like a percentage, it''s just a number.


OK, to clear things up, I''ll note the vectors as vVectorName and floats as fFloatName.



Vector vRelPos = vRayPos - vSpherePos;

float fC = (vRelPos * vRelPos) - (fSphereRad * fSphereRad);
float fB = 2.0f * (vRayDir * vRelPos);
float fA = (RayDir * RayDir);
float fD = fB*fB - 4*fA*fC;


float fT0 = (-fB - sqrt(fD)) / (2*fA);
float fT1 = (-fB + sqrt(fD)) / (2*fA);

if (fT1 < 0.0f && fT0 < 0.0f)
return false;

fT = MinimumButPositive(fT0, fT1);


vPointOfIntersection = vRayPos + (vRayDir * fT);

Share this post


Link to post
Share on other sites
oliii    2196
BTW, if you have any specific questions, you can email me. I won''t bite And you''ll get your answers quicker. This thread has been going on for more than a month now, and you''re still stuck

first thing though, if you want to make a FPS, I strongly suggest you get fluent in vector / matrix / quaternions / geometry. If you don''t get it, you won''t go anywhere :D

Share this post


Link to post
Share on other sites
oliii    2196
quote:
Original post by s_cloudx
So, it''s not correct to subtract a scalar value from a vector? I always thought that:

Vector - scalar = Vector(Vector.x - scalar, Vector.y - scalar, Vector.z - scalar)

So, what is the correct way to subtract scalar value from a vector?


well, you could implement an operator which would do this, but it''s really not recommended. at all.



class Vector
{
.......
.......
friend Vector operator-(float k, const Vector& V) { return Vector(V.x-k, V.y-k, V.z-k); }

Vector operator-(float k) { return Vector(x-k, y-k, z-k); }
};


this would be a perfectly valid operator, but it would be too confusing. Avoid stuff like that at all costs. C++ is great in the sense that it lets you do pretty much whatever you want with operators, but it can introduce confusion if you over-do it.

for the cross product, try


Vector operator ^ (const Vector^ V)
{
return Vector(y*V.z-z*V.y, z*V.x-x*V.z, x*V.y-y*V.x);
}


and you can do a cross product like this


Vector vCrossProduct = vFirstVector ^ vSecondVector;

Share this post


Link to post
Share on other sites