#### Archived

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

# Collision Detection Problem

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

## Recommended Posts

Hi, i have just begun to write my first collision detection class, it is currently only for sphere-to plane collisions. the problem is, this code prevents the player always from moving! it´s as if the player is sticked on the ground! for example, i start at the center of a cube room, and movement is not possible! i would be very happy if someone could help me! if i set the velocity´s Y-coordinate to zero, then it works.... here is some code:

bool CCollision::sphere_plane_collision(const CVector3 &start,
const CVector3 &end, const CPlane &plane,
float radius, CVector3 &result)
{
float t0 = plane.point_distance(start);

float t1 = plane.point_distance(end);

if (t0 >= radius && t1 >= radius) return false;

result = start;

return true;
}

bool CCollision::collide_with_world(const CVector3 &start, const CVector3 &end,
CVector3 &result)
{
std::vector<CPolygon>::iterator collider = _colliders.begin();

for ( ; collider != _colliders.end(); ++collider)
{

if (sphere_plane_collision(start, end, collider->_plane, 3.2f, result))
return true;
}

return false;
}

void CPlayer::move()
{
velocity._x = 0.14 * (ux);
velocity._y = gravity.y  // negative;

velocity._z = 0.14 * (uz);

CVector3 targetPos = currentPos + velocity;

if (!CCollision::collide_with_world(currentPos, targetPos,   result)))
{
currentPos = targetPos;
}
else
{
currentPos = result;
}
}

thanks Gammastrahler!

##### Share on other sites
if you are on the ground already when doing the test, the line will intersect at near 0.0f on the line. Therefore, ''result'' will be very very very very close to your start position, hence you keep reseting the position of the player to it''s start position (or very near to it).

Instead of just setting "currentPos = targetPos;", also constrain the velocity of the player to the plane, and slide the player onto the plane.

// the movement from start to endVector displacement = end - start;// set the movement along the plane normal to 0, thus making the movement ''slide'' on the planedisplacement -= collider->_plane.Normal * (displacement.Dot(collider->_plane.Normal));// ''slide'' the target position on the planecurrentPos = targetPos + displacement;

you might run into some problems like that (like going though walls), but at least, it''s a start.

to fix most of these, once you found the fist plane intersected, do another test with the targetPos and the constrained displacement. Here is the code, with sliding motion added.

CPlane* CCollision::collide_with_world(const CVector3 &start, const CVector3 &end, CVector3 &result){	CPlane* pNearestCollidedPlane = NULL;	// go through all the polygons, and find the first intersected	Vector3 end2 = end;   	for (std::vector<CPolygon>::iterator collider = _colliders.begin() ; collider != _colliders.end(); ++collider)	{			if (sphere_plane_collision(start, end2, collider->_plane, result))		{			// the intersection distance is shorter thean the previous one found,			// as save it as the potentially closest collision plane			end2 = result;			pNearestCollidedPlane = collider->_plane;		}	}	// return the first intersection found	result = end2;	return pNearestCollidedPlane;}void CPlayer::move(){	// do the velocity stuff	velocity._x = 0.14 * (ux);	velocity._y = gravity.y // negative;	velocity._z = 0.14 * (uz);	// make sure we will catch even the tiniest of collisions	float threshold = 0.00001f;	currentPos -= velocity * threshold;	// prepare the collison test	CVector3 end   = currentPos + velocity;	CVector3 result;	// a bit of friciton when colliding	float friction = 0.1f;	float bounce = 0.0f; // no bouncing	// as long as we find a plane to slide on to...	while (CCollision::collide_with_world(currentPos, end, result) != NULL)	{		// get the nearest intersection parameters, and put the sphere there		currentPos = result;		CVector3 displacement = end - currentPos;				// the ''slide'' vector (components of the movement along the plane normal is removed.		// even add some bounce if you want.		displacement -= collider->_plane.Normal * displacement.Dot(collider->_plane.Normal) * (1.0f + bounce);		// see how far we can slide, add some simple friction :)		end = currentPos + displacement * friction;		// test the world again to see if we can find another plane to slide onto	}	// right, all collisons are done, set the position for the next frame	currentPos = end;}

that should get you going

##### Share on other sites
@ oliii

thanks for your code
i have implemented it, but there is now another problem:
as i get too close to a collider, i bounce off....

##### Share on other sites
in what way? you should not bounce off. You should just slide off the walls. bounce is set to 0.0f.

BTW, in
// see how far we can slide, add some simple friction
end = currentPos + displacement * friction;

replace it by
end = currentPos + displacement * (1.0f - friction);

to make sure you understand the algo

1st step
---------

                                                     . wall2                                                    .                         start                     .                           x                      .                            \                    .                             \                  .                              \                .                               \              .                                \            .  wall1                            \          .   ..................................+--------.----+............                            result \      .     | new end                                    \    .      |                                     \          |                                      \         |                                       \        |                                        \       |                                         \      |                                          \     |                                           \    |                                            \   |                                             \  |                                              \ |                                               \|                                                * end

Step 2
------

                                                     . wall2                                                    .                                                   .                                                  .                                                 .                                                .                                               .                                               *. new end                                              /   .wall1                                 result/      . ..................................*--------+--------*..........                                start     .          end                                         .                                               .

it''s quite simple really. You just project the end point on the wall surface, and do another test, until no collision is found or the ray is very very small.

the bounce and friction are only extra stuff thrown in. If they bother you, set them to 0.0f

Try with only one wall, just a floor. You should just skid along the plane.

in another words, you can do

void CPlayer::move(){	// do the velocity stuff	velocity._x = CVector3(0.14 * (ux), gravity.y, 0.14 * (uz));	// prepare the collison test	CVector3 end = currentPos + velocity;	// find a plane to slide on to	CVector3 result;	CPlane* pCollidedPlane = CCollision::collide_with_world(currentPos, end, result);	// as long as we find a plane to slide on to...	while (pCollidedPlane != NULL)	{		// get the nearest intersection parameters, and put the sphere there		currentPos = result;		// Move the end point on the surface of the plane 		// watch out, you might need to invert the sign of Dparam, depending on what it represents in your plane equation.		end += pCollidedPlane->Normal * (pCollidedPlane->Dparam - end.Dot(pCollidedPlane->Normal));		// test the world again to see if we can find another plane to slide onto		pCollidedPlane = CCollision::collide_with_world(currentPos, end, result);	}	// right, all collisons are done, set the position for the next frame	currentPos = end;}

##### Share on other sites
now its working many thank for your help!!!

##### Share on other sites
hehehe... My work is done...

##### Share on other sites
There is still one strange problem ....

i have tested with a solid, big cube.... i walk on top of the cube, that´s no problem. but when i get to the boundarys, i can´t move through just as if the plane´s normals would point to the inside....

so i have included the following test:

if (collider->_plane.is_behind(start)){    // skip this collider}const bool CPlane::is_behind(const CVector3 &p) const{ return (p.Dot(_normal) + _d) < 0.0f; }

and this results in an endless loop for my collision code!!

do you have some suggestions / any hint for me??

maybe oliii ??

thanks
Gammastrahler

##### Share on other sites
on the box example, it looks like the player''s feet get stuck on the edge. It''s a typical collison problem

yeah, culling back facing polys should help. Also, check if the velocity of the player is going ''towards'' the normal of the polygon. if the player is actually moving away from the poly, skip the polygon.

also, remove that threshold bit in the code.
// make sure we will catch even the tiniest of collisionsfloat threshold = 0.00001f;// currentPos -= velocity * threshold; // maybe not such a good idea

However, you have to be careful with culling the backfacing polygons, if you only do ray-polygon tests, as the start position could be slightly underneath the polygon, but should still be colliding with it, and then the test would fail due to numerical innacuracies.

try this

if (collider->_plane.is_behind(start) ||     collider->_plane.is_moving_towards(end-start)){    // skip this collider}const bool CPlane::is_behind(const CVector3 &p) const{   return (p.Dot(_normal) + _d) < -0.0001f;}const bool CPlane::is_moving_towards(const CVector3 &dir) const{   return (p.Dot(dir) < 0.0001f);}

you can see that I don''t do tests with 0.0f, but instead use very small values. Now, I am not sure if these exact values will help you or not, it depends on your system. But try with very small values, either above or below 0.0f. You have to think about it beforehand, as the sign is quite important. It will either make your player more prone to stumble on polygons, or go through it. Or it might work perfectly

dynamic collisions are very sensitive to thresholds. this is a pain, but it''s unavoidable, due to the numerical innacuracies. Using double precision arithmetic won''t solve the problem totally, it will just make it happening less often.

a way to do it, is to move the ray, not on the result position, but a litle bit before the result position, or a little bit away from the real point of intersection, like

	if (sphere_plane_collision(start, end2, collider->_plane, result))		{			// the intersection distance is shorter thean the previous one found,			// as save it as the potentially closest collision plane			end2 = result + collider->_plane.Normal * 0.001f; // one milimeter above the polygon			pNearestCollidedPlane = collider->_plane;		}

this will make the player jitter very slightly, but it should help for the infinite collision loop.

if it works, great, otherwise, you have to play around with thresholds, and think on where they could be useful.
a way to debug your collision system, is to put rather large thresholds (like replace 0.001f by 0.05f in the code above), see if the player gets stuck, or goes through stuff. It it works fine, reduce the threshold step by step, and find a value where the player doesn''t jump all other the place, nor does get stuck on geometry.

Also, you may want to stop the collision tests if the velocity is close to 0.0f, but it could make stuff go through triangles. Not sure about that one.

hard work, innit?

##### Share on other sites
@ oliii

many thanks again.... now, with your great help i have the basics running

although there are still problems. i implemented friction, so that i can smoothly climb up stairs. but the problem is, i have tested with different sphere radii, and if the radius is too big, i´m no longer able to climb up stairs, the friction pushes me back!!! if i remove friction then it works again but no longer smooth.... also, friction causes the player to slightly bounce of my walls which is also not desired.
i tried to make the friction a function of the length of the velocity vector, but the results were not satisfying....

now, i have tried to implement ellipsoids.... but it doesnt work!!! i have a scale vector:

scaleVector = 1.0 / radiusVector.

Then, i scale my start and end position, as well as my polygon set, recalculating planes, and rescale it on end.

My sphere plane collisions now check for unit sphere intersection (distance to plane <= 1.0), but it doesnt work.

here is my complete code (currently i have no edge collision detection)
void CCollision::collide_with_world(const CVector3 &start, const CVector3 &end,CVector3 &result, std::vector<CPolygon> &_colliders){	    CVector3 rStart = start;    CVector3 target = end;    CVector3 scaleVector = radiusVector;    scaleVector = 1.0 / radiusVector;    rStart.Multiply(scaleVector);    target.Multiply(scaleVector);    std::vector<CPolygon>::iterator collider = _colliders.begin();    for ( ; collider != _colliders.end(); ++collider)    {	for (int i = 0; i < collider->_nVerts; i++)	    collider->_verts[i].Multiply(scaleVector);	collider->calc_plane();    }    bool foundCollision;    while (true)    {	foundCollision = false;	CVector3 velocity = target - rStart;	//if (velocity.Length() < -EPSILON) break;	for ( collider = _colliders.begin(); collider != _colliders.end(); ++collider)	{	    CPlane plane = collider->_plane;	    //float u = plane._normal.Dot(rStart) + plane._d;	    //if (u < -EPSILON) continue;	    //if (velocity.Dot(plane._normal) + plane._d < -EPSILON)	    //	continue;	    float v = plane._normal.Dot(target) + plane._d;	    if (v <= 1.0)  // scaled to unit sphere	    {	        CVector3 planeIntersectionPoint = target - plane._normal * v;	        if (InsidePolygon(planeIntersection, *collider))		{		    CVector3 offset = plane._normal * (1.0 - v);		    target = target + offset;// friction commented out * (18 * CFrameRate::Instance()->GetTimeDelta());		    velocity = target - rStart;							    foundCollision = true;	        }	    }        }        if (!foundCollision) break;    }       // rescale world    scaleVector = radiusVector;    for ( collider = _colliders.begin(); collider != _colliders.end(); ++collider)    {	for (int i = 0; i < collider->_nVerts; i++)	    collider->_verts[i].Multiply(scaleVector);	collider->calc_plane();    }            result = target;    // rescale result    result.Multiply(scaleVector);}

i hope you could give me some hint

thanks
Gammastrahler

[edited by - Gammastrahler on July 12, 2003 10:04:12 AM]

##### Share on other sites
ok... i have solved the ellipsoid problem but with ellipsoid collision, now i´m able to climb inclining planes which have a high angle, this is very unnatural.... how can i avoid this?

and there is still the problem with friction

if i have only walls, floors, and ceilings... no problem

[edited by - Gammastrahler on July 12, 2003 10:22:42 AM]

1. 1
2. 2
3. 3
Rutin
14
4. 4
5. 5

• 10
• 11
• 9
• 14
• 10
• ### Forum Statistics

• Total Topics
632652
• Total Posts
3007661
• ### Who's Online (See full list)

There are no registered users currently online

×