Tunnelling, how to stop it?
Started by ggs, Jun 21 2001 01:21 PM
9 replies to this topic
#1 Members  Reputation: 166
Posted 21 June 2001  01:21 PM
How do you stop tunnelling, I''m aware it occurs on the subatomic/atomic level but I dont want it to occur at the macro level. ie I dont want it occuring in my game
I know this is primarily a collision detection issue, but all the collision detection tutorials I''ve looked at dont even deal tiwht this issue. For learning purposes I''m keeping to 2D, and have been writting a demo(in delphi) to implement what I''ve learnt so far. Any ideas?
PS
I havent covered rotation yet, but I plan to after I have some idea how to approch to tunnelling issue.
#3 Members  Reputation: 122
Posted 22 June 2001  05:37 AM
To answer you, Omegasyphon, tunneling is when a particle (like an electron) passes through a large object (like a wall).
ggs, you can stop "tunneling" by implementing what is commonly called collision detection. a common way to do this is by using bounding boxes or bounding spheres, depending on your object.
say you have 2 tennis balls moving toward each other. it makes sense that if the distance between the centers of each is greater than the radius of both added together, they haven''t hit yet, have they?
in psuedo mathcode it would look something like this:
hope that helps you a bit
Hyren
"Back to the code mines... kachink... kachink..."
vidgamez.iwarp.com
ggs, you can stop "tunneling" by implementing what is commonly called collision detection. a common way to do this is by using bounding boxes or bounding spheres, depending on your object.
say you have 2 tennis balls moving toward each other. it makes sense that if the distance between the centers of each is greater than the radius of both added together, they haven''t hit yet, have they?
in psuedo mathcode it would look something like this:

hope that helps you a bit
Hyren
"Back to the code mines... kachink... kachink..."
vidgamez.iwarp.com
#4 Members  Reputation: 122
Posted 22 June 2001  05:45 AM
Tunneling, in a quantum physics sense, is when some things, like electrons, particles of light, or just Really Small Stuff, passes straight through a solid object without really acknowledging that it's there.
In the game sense that ggs is talking about, I think he means what happens if you just check the position of an object against another frame by frame for collision detection. The problem is, if the objects move far enough during a frame, they may pass straight through each other because they hopped far enough if that frame that the collision tests fail. What you have to do is find a way to check your collisions in a way that takes into account movement, instead of just static checks.
Ways of doing that include tracing lines from the edges of the objects you're testing collisions for to see if they intersect, or possibly interpolating from one position to the next and testing at each step along the way, but that gets expensive and still might miss from time to time.
For all that talk, I really haven't done it myself, so I'm kinda talking out of my rear. But here's some links to help you get started:
http://www.gamasutra.com/features/20000330/bobic_01.htm
http://www.peroxide.dk/tutorials/tut10/pxdtut10.html
Jonathan
P.S.  Damn I hate it when I reply at the same time as someone else.
Edited by  Jonathan on June 22, 2001 12:46:51 PM
In the game sense that ggs is talking about, I think he means what happens if you just check the position of an object against another frame by frame for collision detection. The problem is, if the objects move far enough during a frame, they may pass straight through each other because they hopped far enough if that frame that the collision tests fail. What you have to do is find a way to check your collisions in a way that takes into account movement, instead of just static checks.
Ways of doing that include tracing lines from the edges of the objects you're testing collisions for to see if they intersect, or possibly interpolating from one position to the next and testing at each step along the way, but that gets expensive and still might miss from time to time.
For all that talk, I really haven't done it myself, so I'm kinda talking out of my rear. But here's some links to help you get started:
http://www.gamasutra.com/features/20000330/bobic_01.htm
http://www.peroxide.dk/tutorials/tut10/pxdtut10.html
Jonathan
P.S.  Damn I hate it when I reply at the same time as someone else.
Edited by  Jonathan on June 22, 2001 12:46:51 PM
#5 Members  Reputation: 180
Posted 23 June 2001  04:20 PM
Hi
Well I was doing a physics simulation an I experiment "tunneling" too, so here is a method wich I learn from the Urls which I add here:
www.d6.com/users/checker
www.gamasutra.com and look for jeff lander articles.
Well first for the collision detection I use pointto plane intersection in the following form:
so to know if a point (your particle center of mass) you need to compute the distance from your point to the plane, so if this distance is lower than a treshold value very near to 0 (0.001f), your particle has penetred the plane so you must back one time your simulation and test again until you got a impact, here add some code
1. Point To Plane Collision.
//
// Get distance from your particle to plane
float const depthEpsilon = 0.001f;
float dot = _Dot(Particlepos, &N) + Plane.D
//
// Check if the particle has penetrated the plane
if (dot < depthEpsilon)
return penetrating
else
if (dot < depthEpsilon)
{
// See if the particle has collided with plane
float vel = _Dot(ParticleVel, &N);
if (vel < 0.0f) return collide;
then in your simulation main loop check as follows
if state = penetrating
TargetTime = (CurrentTime + TargetTime) * (RwReal)0.5f;
so if is penetrating move your time back and try again.
In the code N = collision plane''s normal
Plane.D is the planes distance calculated from planes equation
Ax+By+Cy+D = 0
D = (Ax+By+Cz) where (A,B,C) = Planes Normal
and (x,y,z) = point in plane, so any triangle''s vertex works.
and you see that Ax+By+Cz = N dot Vertex
Hope it helps you.
Oscar
Well I was doing a physics simulation an I experiment "tunneling" too, so here is a method wich I learn from the Urls which I add here:
www.d6.com/users/checker
www.gamasutra.com and look for jeff lander articles.
Well first for the collision detection I use pointto plane intersection in the following form:
so to know if a point (your particle center of mass) you need to compute the distance from your point to the plane, so if this distance is lower than a treshold value very near to 0 (0.001f), your particle has penetred the plane so you must back one time your simulation and test again until you got a impact, here add some code
1. Point To Plane Collision.
//
// Get distance from your particle to plane
float const depthEpsilon = 0.001f;
float dot = _Dot(Particlepos, &N) + Plane.D
//
// Check if the particle has penetrated the plane
if (dot < depthEpsilon)
return penetrating
else
if (dot < depthEpsilon)
{
// See if the particle has collided with plane
float vel = _Dot(ParticleVel, &N);
if (vel < 0.0f) return collide;
then in your simulation main loop check as follows
if state = penetrating
TargetTime = (CurrentTime + TargetTime) * (RwReal)0.5f;
so if is penetrating move your time back and try again.
In the code N = collision plane''s normal
Plane.D is the planes distance calculated from planes equation
Ax+By+Cy+D = 0
D = (Ax+By+Cz) where (A,B,C) = Planes Normal
and (x,y,z) = point in plane, so any triangle''s vertex works.
and you see that Ax+By+Cz = N dot Vertex
Hope it helps you.
Oscar
#6 Members  Reputation: 166
Posted 23 June 2001  06:12 PM
quote:
... just check the position of an object against another frame by frame for collision detection. The problem is, if the objects move far enough during a frame, they may pass straight through each other because they hopped far enough if that frame that the collision tests fail...
Yup, thats what I ment. I''ll try those sugestions when I fix a bug.Sorry about the confusion about my 1st post.
#7 Members  Reputation: 109
Posted 24 June 2001  08:02 AM
Just some thoughts: I haven''t actually done this...
Assume that an object''s path is either an arc or set of arcs, or more trivially, a straight line. Assume that an object has a maximum radius relative to the path it is traveling. An example: A bus 8 feet wide and 12 feet high traveling a straight line would have a maximum radius of 6 feet.
Ok, any arc has a maximum distance that it gets from a line segment connecting its two end points. For example, a half circle has a maximum distance from the line segment connecting its endpoints equivalent to the radius of the half circle. Any object traversing this path would approximately be at most a maximum distance from the connecting line segment equal to the maximum arc''s distance plus the objects maximum radius.
Using the simplified line segments plus the radius as defined above in place of the arcs, we essentially have a cylinder. If we have two possibly intersecting paths, we have two potentially intersecting cylinders. All that aside, there is an equation to compute the closest distance two line segments are from each other.
If this closest distance is less than the radius as described above, then subdivide the line segments to create a better approximation of the arcs they represent. Recursively repeat until it is either determined that no intersection occurs or an intersection does occur.
Assume that an object''s path is either an arc or set of arcs, or more trivially, a straight line. Assume that an object has a maximum radius relative to the path it is traveling. An example: A bus 8 feet wide and 12 feet high traveling a straight line would have a maximum radius of 6 feet.
Ok, any arc has a maximum distance that it gets from a line segment connecting its two end points. For example, a half circle has a maximum distance from the line segment connecting its endpoints equivalent to the radius of the half circle. Any object traversing this path would approximately be at most a maximum distance from the connecting line segment equal to the maximum arc''s distance plus the objects maximum radius.
Using the simplified line segments plus the radius as defined above in place of the arcs, we essentially have a cylinder. If we have two possibly intersecting paths, we have two potentially intersecting cylinders. All that aside, there is an equation to compute the closest distance two line segments are from each other.
If this closest distance is less than the radius as described above, then subdivide the line segments to create a better approximation of the arcs they represent. Recursively repeat until it is either determined that no intersection occurs or an intersection does occur.
#8 Members  Reputation: 166
Posted 24 June 2001  11:33 PM
I've ended up attempting to use Point To Plane Collision.
How ever how to you generate the normal??, I'm looking around gamedev now but any help would be appreciated.
Edit : Didn't really supply enough info.
Here is the code I've used so far in my collision detection responce algo.
As you can see I haven't worked out the collision normal, and I've put it as a param. Is this about right?
Edited by  ggs on June 25, 2001 7:02:04 AM
How ever how to you generate the normal??, I'm looking around gamedev now but any help would be appreciated.
Edit : Didn't really supply enough info.
Here is the code I've used so far in my collision detection responce algo.
Procedure TParticle.CollisionWith(Particle : TParticle;const CollisionPlane : TPlane2D);
var
VelocityAB,ScaledVector : TVector;
Impulse : FloatPoint;
CollisionValue,normDot : FloatPoint;
begin
// generate data about the collisions
SubtractVector(Particle.Velocity,Velocity{subtracted},VelocityAB{out});
// check to see what type of collision has occured
CollisionValue := DotProductf(VelocityAB,CollisionPlane.normal);
// if > 0 then, the points are leaving
// if = 0 then, contact is achieved, ignore if a collision occurs then it will be caught later
// if < 0 then, a collision has occured!
if (CollisionValue >= 0) then
exit;
// calculate the Impulse of the collision
normDot := DotProductf(CollisionPlane.normal, CollisionPlane.normal);
Impulse := ((1 + CollisionConstant) * CollisionValue) /
(normDot * (oneOverMass + Particle.oneOverMass));
// now actually use the impulse value
ScaleVector(CollisionPlane.normal{in},ScaledVector{out},Impulse * oneOverMass);
AddVector(Velocity,ScaledVector{added});
end; {CollisionWith}
As you can see I haven't worked out the collision normal, and I've put it as a param. Is this about right?
Edited by  ggs on June 25, 2001 7:02:04 AM
#9 Members  Reputation: 180
Posted 25 June 2001  04:30 PM
Hi, here I post how to compute a plane normal:
supouse you got a triangle defined by 3 vertex (v1, v2, v3), so to computes its normal, you need to make to coplanar vectors from this triangle''s vertex and then computes the cross product between this two coplanar vectors, so the Cross product will be the triangle''s normal
Example: vertex3D v1, v2, v3;
Vector3D u, v, n;
// First coplanar vector u
u = v2  v1;
// Secon coplanar vector v
v = v3  v1;
// get triangle normal
n = CrossProduct(&v, &u);
// Normalize it
Normalize(&n)
Hope it helps you.
Oscar
supouse you got a triangle defined by 3 vertex (v1, v2, v3), so to computes its normal, you need to make to coplanar vectors from this triangle''s vertex and then computes the cross product between this two coplanar vectors, so the Cross product will be the triangle''s normal
Example: vertex3D v1, v2, v3;
Vector3D u, v, n;
// First coplanar vector u
u = v2  v1;
// Secon coplanar vector v
v = v3  v1;
// get triangle normal
n = CrossProduct(&v, &u);
// Normalize it
Normalize(&n)
Hope it helps you.
Oscar
#10 Anonymous Poster_Anonymous Poster_* Guests  Reputation:
Posted 25 June 2001  05:12 PM
hers a generic way to do it
how about this say u have a maximum speed limit
and a minumum object radius => the maximum movement of a object
the maximum speed any partical or object can move is say 2.0
now make the minimum size of any objects radius 2.1
anytime a objects center point moves in a frame it will never be able to simply pass through if u check center points against the radius of another object that is if the minimum of the radius of any object is more than the maximum possible movement of a object in any frame of course
lightwave