Archived

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

3D Pong Collision

This topic is 5111 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi guys, I hope this post does not seen too simple, but ive been stuck for weeks and its stopping my development in games. Im trying to make a nice 3D pong game, so far its awesome. Ive got a nice sphere mapped ball, reflective patterns and it all looks so slick. My problem is how to make the ball rebound off the paddle. Ive researched Sphere to Box collsion (get nearest point in box etc..) but i don''t know how to calculate the rebound (new velocity values upon hit)! Also, what if the ball has gone ''inside'' the box upon collision, just setting the inverse of the velocity of the ball, the ball would repeatedly rebound every frame. Im confused, since there are 4 sides on the paddle the ball can bounce off, so far all i have is a IsCollided() function. Thanks anyone who can help. - MeshMan

Share this post


Link to post
Share on other sites
Simple 2D pong never needed distance between a 2D rectangle and a circle. Your 3D version shouldn't either.

Treat your paddles as rectangles in a plane. When the ball touches (about to go through it) that plane (Ball.Z + Ball.Radius == Paddle.Z), check whether there is a paddle there (2D check), and if there is, then the simplest thing you could do is keep the X and Y velocities the same (X and Y being both perpendicular to the paddle), and invert Z velocity (Ball.Velocity.Z = -Ball.Velocity.Z). That would be basically the ball bouncing off. If there is no paddle, the player's missed, so do nothing (reset ball position, increment appropriate scores, etc.)

I've made a 3D pong in VB for my computers class once. If you're interested in seeing it (with the source), I'll see if I can find it. It's quite messy though, but should give you a basic idea on how to do simple physics.

---
shurcooL`

[edited by - shurcooL on December 12, 2003 4:56:19 PM]

Share this post


Link to post
Share on other sites
Woops, i was a little vague and not clear on exactly what im doing.

My version of pong isnt exactly 2 paddles that just reflect the ball when they hit one axis. I have two paddles situated in a snooker table type arena, like so:

--------------------
| |
| ---- |
| |
| o |
| |
| ---- |
| |
--------------------

The paddles are a little away from the edge of the boards sides so the ball can rebound from the sides of the board but also get behind the paddles and rebound off the paddle that way (kinda like own goals). The score is calculated by hitting the ball on your opponents back-board, first to 10 wins. So the ball needs to check collision from all sides of the paddles (3d paddles and 3D ball).

Is this clear? Or would you like me to upload a screenie.

- MeshMan

Share this post


Link to post
Share on other sites
Man, thats way over my head, i cant understand a word of that math article besides the normal vector to a plane. *shrugs* All i have is 2 bounding rect''s that say *yeah, we collide*, my math sux so that doesnt help, thanks anyways.

Share this post


Link to post
Share on other sites

//-------------------------------------------------------

// dot product

// d = A . B

//-------------------------------------------------------

float Dot(const Vector& A, const Vector& B)
{
return A.x*B.x + A.y*B.y + A.z*B.z;
}

//-------------------------------------------------------

// multiplication

// B = A * k

//-------------------------------------------------------

Vector Mul(float k, const Vecor& A)
{
return Vector(A.x * k, A.y * k, A.z * k);
}

//-------------------------------------------------------

// substraction

// C = A - B

//-------------------------------------------------------

Vector Sub(const Vector& A, const Vector& B)
{
return Vector(A.x-B.x, A.y-B.y, A.z-B.z);
}
//-------------------------------------------------------

// reflect a vector off a plane

// V -= 2.0f * (V . N) * N

// if normal not normalised,

// V -= 2.0f * [(V . N) / (N . N)] * N

//-------------------------------------------------------

bool Reflect(Vector& V, Vector& N)
{
float VdotN = Dot(V, N); // V . N

float NdotN = Dot(N, N);

if (VdotN > 0.0f) // ball moving away from plane, don;t reflect

return false;

if (NdotN < 0.0001f) // normal too small.

return false;

float k = 2.0f * (VdotN / NdotN); // the reflexion amount


Vector Vn = Mul(k, N); // the reflexion vector


V = Sub(V, Vn); // the new velocity, reflected off the plane


return true;
}

//-------------------------------------

// process collision of a ball and a paddle

//-------------------------------------

void ProcessCollision(const Vector& PointOnBall, const Vector& PointOnPaddle, Vector& BallVelocity)
{
Vector N = Sub(PointOnPaddle, PointOnBall);

Reflect(BallVelocity, N);
}

Share this post


Link to post
Share on other sites
I still dont know where to go with that code, since i need a closest point for the sphere and the paddle bounding box but to get the closest point of a bounding rect / sphere i need a relative point from.

For example, to get closest point on paddle box i would need the closest point from the ball, but to get the closest point on the ball, i would need the closest point on box.
And also to add to the ultimate confusion im in, what about if the ball hits a paddle and intersects the paddle and goes inside it, since it will ''never'' collide exactly on the pixels of the sides of the box.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Its 3d but collision is 2D since nothing moves on Y axis.

Share this post


Link to post
Share on other sites
quote:
Original post by MeshMan
I still dont know where to go with that code, since i need a closest point for the sphere and the paddle bounding box but to get the closest point of a bounding rect / sphere i need a relative point from.

For example, to get closest point on paddle box i would need the closest point from the ball, but to get the closest point on the ball, i would need the closest point on box.
And also to add to the ultimate confusion im in, what about if the ball hits a paddle and intersects the paddle and goes inside it, since it will ''never'' collide exactly on the pixels of the sides of the box.



I don''t use operators, because ... I don;t know! I wasn''t sure if he''d understand it.

anyhow. The closest point on a box to a sphere would be the closest point on the box to the centre of the sphere. That should be simple enough.

Then the closest point on the sphere to the box is the closest point on the sphere to the cloest point on the box.


Vector FindClosestPointOnBox(const CBox& Box, const Vector& P);
Vector FindClosestPointOnSphere(const CSphere& Sphere, const Vector& P);

Vector Pbox, Psphere;
Pbox = FindClosestPointOnBox (Box, Sphere.Centre);
Psphere = FindClosestPointOnSphere(Sphere, Pbox);


Vector FindClosestPointOnSphere(const CSphere& Sphere, const Vector& P)
{
Vector Pdiff = P - Sphere.Centre;
Pdiff.Normalise();

return Sphere.Centre + Pdiff * Sphere.Radius;
}

Vector FindClosestPointOnBox(const CBox& Box, const Vector& P)
{
/// Later!!!!! have to go to work :))

}

Share this post


Link to post
Share on other sites
Thanks! I understand it now, i had a rough idea that i should use the center of the sphere, but for future reference, would this apply to all objects? Would i use the center of mass on for example, a player model?

Anyhow, i understand it now, you dont have to complete your code for me to understand, i can easily enough implement it (and yes i will use operators ), thanks very much!

So, i hope you don''t mind me mentioning the last little detail. What if the sphere intersects the box, and how will i know which sides it has hit, and would i have to move the sphere to barley touching the box so that on next frame its not going to say its collided again?

Everyones help is much appreciated.

- MeshMan

Share this post


Link to post
Share on other sites
with the collision impulse calculations, the sphere will only *reflect* on the collision plane if the sphere moves towards the plane of collision. If the sphere intersects the box but moves away from the paddle, the velocity will not be changed.

The collision detection *relies* on the sphere intersecting the paddle. There is no prediction (like calculations involving the sphere velocity).

Then you need to separate the sphere and the box. For that, it is equivalent to have the two closest points touching. So you need to displace the sphere by vector

D = Pbox - Psphere;

you can also displace the paddle the other way, in this case

fRatio = 0.5f; // displace the paddle and the sphere by the same amount
Sphere.Position += D * fRatio;
Paddle.Position -= D * (1.0f - fRatio);

that will put the sphere on the surface of the box, and push the box out of the way as well. For a pong game, if the box is stuck between the paddle and the wall, you need to push the paddle as well as the ball (or you''ll squash the ball). The paddle and the ball will maybe jitter a few frames. you can reduce the amount of total displacement to smooth it out, but it could make the sphere slowly sink into the paddle and walls if you keep trying to squash the ball in a corner.

fRatio = 0.5f; // displace the paddle and the sphere by the same amount
fRigidness = 0.5f;
Sphere.Position += D * fRatio * fRigidness;
Paddle.Position -= D * (1.0f - fRatio) * fRigidness;


if the sphere centre is in the box, the closest point will be on one face of the box, and the algorithm still applies. Although in that case, which is an extreme case, you may want to pull the sphere back a little to make sure the sphere intersects the paddle, but only slightly (to get a better approximation of the collision). That can happen if the paddle moves fast towards the sphere and the sphere moves fast towards the paddle, and the paddle is very thin. If your game is set right, and updated at a decent speed, that should not happen, and you need so more clever stuff to avoid that case (swept volumes).

about the algorithm taking the closest point from one volume to another, I don''t think it would work for some of the other types of volume, like meshes and convex hulls. The algortihm would brake if the angle between two planes is > 90 degrees. It should still work for sphere-sphere, sphere-cylinfer, sphere-AABox, Sphere-Oriented box.

for a swept volume collision detection, you need to consider the sphere velocity, and find the time of collision where the centre of the sphere intersects the volume composed of the box, and surrounded by a shell of size = radius of the sphere. It''s hard to explain, but it would look like a box with rounded corners.

The other advantage of the swept test, is that you can also consider the paddle velocity, for extra precision.

One way, is to find the point of collision between the swept sphere and the edges, the corners and the planes. Then take the one with the minimum time of collision.

As you can see, it is more complicated. But you can try the simpler overlap method discussed here, and then move on to the swept test, which gives more accurate results.

Share this post


Link to post
Share on other sites
Ooooh, thats quite alot to take in, i guess this isnt the 10 minute coding job i thought it would be.

Oh well, im going to ''try'' and absorb what you''ve said, even though it seems a little hazy, im not quite sure what your telling me about how the ball knows which side of the paddle its hit, for example.
The paddle has four planes for each of its side, and your collision algo tests one plane, so which planes do i test first (top+bottom / left+right?), because im sure that the sphere at some point can collide on say the top and right side planes of the paddle.

Share this post


Link to post
Share on other sites
quote:
Original post by MeshMan
Ooooh, thats quite alot to take in, i guess this isnt the 10 minute coding job i thought it would be.

Oh well, im going to ''try'' and absorb what you''ve said, even though it seems a little hazy, im not quite sure what your telling me about how the ball knows which side of the paddle its hit, for example.
The paddle has four planes for each of its side, and your collision algo tests one plane, so which planes do i test first (top+bottom / left+right?), because im sure that the sphere at some point can collide on say the top and right side planes of the paddle.


no dude

the point of finding the closest point on the box automatically gives you a vertex sphere / edge sphere / plane sphere collision. The plane I refer to is a generalisation. Not a plane of the box, but a plane made of a normal vector, and possibly a position vector (which is not required here).

All the collision response needs is the normal of the plane. That''s quite general, but the collision response does not need to know what feature it collided with.

the closest points automatically give you the plane of collision, where you reflect the ball.

here is the overall algo.




bool Collide(CSphere Sphere, CBox Box)
{
//------------------------------------------------------

// find closest features

//------------------------------------------------------

Vector Pbox = FindClosestPointOnBox (Box, Sphere.Centre);
Vector Psphere = FindClosestPointOnSphere(Sphere, Pbox);

//------------------------------------------------------

// calculate plane normal.

//------------------------------------------------------

Vector N = Pbox - Psphere; // normal of collision plane

float n2 = N * N; // normal length squared


//------------------------------------------------------

// the sphere is too far away

//------------------------------------------------------

if (n2 > Sphere.Radius * Sphere.Radius)
return false;

//------------------------------------------------------

// Separate the sphere and the box, because they are

// overlapping

//------------------------------------------------------

Vector D = N;
float fRigidness = 0.8f;
float fRatio = 0.5f;
Sphere.Position += D * (fRatio * fRigidness);
Box .Position -= D * ((1.0f - fRatio) * fRigidness);

//------------------------------------------------------

// reflect the sphere off the collision plane

//------------------------------------------------------

Vector V = Sphere.Velocity;
float vn = V * N; // speed along the normal of collision


//------------------------------------------------------

// the sphere is moving away from the collision plane

//------------------------------------------------------

if (vn > 0.0f)
return true;

float fCoR = 1.0f; // coefficient of restitution (bounce)

float fCoF = 0.0f; // coefficient of friction (no friciton)


Vector Vn = N * (vn / n2); // velocity along the normal of plane

Vector Vt = V - Vn; // velocity along the plane


Sphere.Velocity = Vn * (-CoR) + Vt * (1.0f - fCoF);

return true;
}


10 minutes work

you can have some fun with the coefficient of restitution. make it greater than 1.0f (not too much though), the ball will accelerate everytime it hits the paddle. You may want to clanp the velocity to a minimum and maximum speed though. You can also add a spin effect, using the paddle velocity and generating a greater or lower tangencial velocity.



//....

//....

//....

Sphere.Velocity = Vn * (-CoR) + Vt * (1.0f - fCoF);

//--------------------------------------------------

// Add an extra spin effect and thrust, using the paddle

// velocity across the plane of collision and along

// the normal of collision

//--------------------------------------------------

V = Box.Velocity;
vn = V * N;
Vn = N * (vn / n2);
Vt = V - Vn;

float fSpinAmount = 0.1f;
float fThrustAmount = 0.1f;

Sphere.Velocity += Vt * fSpinAmount + Vn * fThrustAmount;
}

Share this post


Link to post
Share on other sites
quote:
Original post by MeshMan
Could you elaborate on the above? I think thats just for reflecting off a wall right? If so, that looks too much for the effect of a wall rebound.


and on his post, the first line is the same as the rest of the other lines. The first line is using vectors, as the other lines are the same thing but decomposing it into float maths.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I have a pretty good idea who you are Mr. AP. Knock it off.

[edited by - The Senshi on December 15, 2003 11:06:59 PM]

Share this post


Link to post
Share on other sites
as you can see, you can reuse the algorithm for collisions against the walls as well. The only difference is in the closestpoint() calculations. That''s all. Actually, the collision function should be split into 2 functions, one that calcualtes the closest points, and see if the objects overlap, one that do the collision response.

Same with sphere against spheres. So you can have a multiball mode very easily. And put obstacles very easily too. All rely on the closest point calculations.

Also, the coefficients of elasticity ect can be changed depending on the material the ball collides with, ect... Physics is fun

here are the closest point calculations for different objects



Vector ClosestPoint(CPlane Plane, Vector Point)
{
//-------------------------------------------------------

// square length of normal of the plane, in case not

// normalised already

//-------------------------------------------------------

Vector n2 = Plane.Normal * Plane.Normal;

//-------------------------------------------------------

// project the point on the plane.

//-------------------------------------------------------

Vector pn = (Point - Plane.Vertex) * Plane.Normal;

return (Point - Plane.Normal * (pn / n2));
}

Vector ClosestPoint(CSphere Sphere, Vector Point)
{
//-------------------------------------------------------

// project the point on the sphere surface

//-------------------------------------------------------

Vector N = (Point - Sphere.Position);
float n = N.Magnitude();

return Sphere.Position + N * (Sphere.Radius / n);
}

//-----------------------------------------------------

// Box made of a centre position and an extent vector

//-----------------------------------------------------

Vector ClosestPoint(CAABox Box, Vector Point)
{
Vector D = Point - Box.Centre;

Vector P(0, 0, 0);

bool bx = (fabs(D.x) > Box.HalfSize.x);
bool by = (fabs(D.y) > Box.HalfSize.z);
bool bz = (fabs(D.z) > Box.HalfSize.x);

//---------------------------------------------------------

// see if point is facing planes of the box

//---------------------------------------------------------

if (bx)
P.x = Box.HalfSize.x * sgn(D.x);

if (by)
P.y = Box.HalfSize.y * sgn(D.y);

if (bz)
P.z = Box.HalfSize.z * sgn(D.z);

//---------------------------------------------------------

// point inside the cube, return the closest plane to the

// point

//---------------------------------------------------------

if (!(bx | by | bz))
{
float min = abs(D.x);
P = Vector(Box.HalfSize.x * sgn(D.x), 0, 0);

if (abs(D.y) < min)
{
min = abs(D.y);
P = Vector(0, Box.HalfSize.y * sgn(D.y), 0);
}
if (abs(D.z) < min)
P = Vector(0, 0, Box.HalfSize.z * sgn(D.z));
}

P += Box.Centre;
}

Share this post


Link to post
Share on other sites
Man, youve answered everything!!!

Thanks so much, this helps with everything, i think i actually get what you mean by the plane being the closest point but really i dont see how ONE point can define a plance, i thought planes were defined with 3 points...so not quite sure where you get ur plane from the 1 point.

I was thinking of making the paddle go forward and backward too like air hockey, i guess i can do that now!!

Thanks so much dude! I can finally do my first real physics and 3d collision detection algo. (i promise i wont just Ctrl+C Ctrl+V it all )

Cheers

Share this post


Link to post
Share on other sites
Make it work then buy me a beer (or something)

the so called plane is not defined by one vector, it''s only the normal of the plane, which is defined by the difference of two closest point vectors. The plane itself is not useful, we only need the normal of collision

For the actual plane of collision, since the overlap method only gives an approximation, the point on the plane would be half way between the two closest points.

There are many ways to generate a plane. Use a normal and any point belonging to the plane (like a triangle normal and any of the verices define a true plane), use three vertices (three points in space, granted that they are nort colinear, define a plane), and probably lots of some other ones I can''t remember.

Check the closest points algorithms, I''ve done them from the top of my head. The sphere and plane closest points should be fine. The box, well, I don''t see anthing wrong, but since it''s a little bit more complex...

BTW, I already spotted a bug


//------------------------------------------------------

// calculate plane normal.

//------------------------------------------------------

Vector N = Pbox - Psphere; // normal of collision plane

float n2 = N * N; // normal length squared


//------------------------------------------------------

// the sphere is too far away

//------------------------------------------------------

Vector D = Pbox - Sphere.Position;
float d2 = D * D;

if (d2 > Sphere.Radius * Sphere.Radius)
return false;

Share this post


Link to post
Share on other sites
Was a little busy tonight, had a national powercut (reason unknown) so ive got little done, just trying to get UV''s fixed (or is it my TGA / BMP loaders...), so tommorow ill try all this and hopefully it will work, but im guessing it won''t, MeshMen + Math = BadThings; heh.

I''ll let you know...

(MSN Messenger - mblore_@hotmail.com)
(IRC EFNet #gamedev MeshMan)

Thanks again.

Share this post


Link to post
Share on other sites
Ive been doing it for a few days now and i can''t get the ball to reflect! Ive got debug points being drawing that shows a poing in the paddle closest to the sphere that works perfectly, and a point on the sphere that is closest to the paddle point. Thats it....I don''t know what your trying to tell me, ive gone over it like 20 times, what the hell is the general normal of what plane at what collision, arg...im going mad....what is what?!

Share this post


Link to post
Share on other sites