Archived

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

Gammastrahler

Collision Detection Problem

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 this post


Link to post
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 end

Vector displacement = end - start;

// set the movement along the plane normal to 0, thus making the movement ''slide'' on the plane

displacement -= collider->_plane.Normal * (displacement.Dot(collider->_plane.Normal));

// ''slide'' the target position on the plane

currentPos = 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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 collisions

float 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 this post


Link to post
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 this post


Link to post
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]

Share this post


Link to post
Share on other sites
For climbing sharp inclines, it all depends on the aspect ratio (on how much downforce it''s got) of your original velocity vector. It will dictate the limit the ellipsoid can climb up.



/
/
/
A /
* /
\/
/\
End / \
*. \
/ . \
/ * B
/
/

// here, the veloctiy is too vertical, thus making the object

// slide down the slope





/
/
/
/
End *.
/ .
/ .
A *--------------* B
/
/
/
/
/

// here, the velocity has no vertical components, thus making the object climb up the slope.




so either, increase the gravity vector, or decrease the speed along the (x, z) planes.




As you use ellipsoids, I''m sure you''ve checked out this doc already. If not, you gotta have to have a look at it.


ftp://ftp.fluidstudios.com/pub/FluidStudios/CollisionDetection/Fluid_Studios_Generic_Collision_Detection_for_Games_Using_Ellipsoids.pdf


It should solve all your problems. The source code is also included, with a demo, but it''s a bit messy as far the collision ssytem is concerned.

For climbing stairs, the collision is done in two steps. First step, the collison test is performed without adding the gravity to the movement. This makes the sphere/ellipsoid climb stairs easily. The second step, you use the remaining displacememtn vector found in your first collision pass, and add gravity, and run the collision test with that vector. This makes the ellipse stop climbing sharp slopes.

It''s all explained better in the doc.

Share this post


Link to post
Share on other sites