Sign in to follow this  

Falling through map, discrete collision detection

This topic is 1931 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

I have a Quake 3 BSP map and I test for discrete collisions with triangle against the AABB. I have stepping but I don't have sliding along walls. When the player goes up to the side of a staircase and pushes against it and jiggles around a bit he falls through the map. Any ideas?

Share this post


Link to post
Share on other sites
[code]#include <math.h>
/* this version of SIGN3 shows some numerical instability, and is improved
* by using the uncommented macro that follows, and a different test with it */
#ifdef OLD_TEST
#define SIGN3( A ) (((A).x<0)?4:0 | ((A).y<0)?2:0 | ((A).z<0)?1:0)
#else
#define EPS 10e-5
#define SIGN3( A ) \
(((A).x < EPS) ? 4 : 0 | ((A).x > -EPS) ? 32 : 0 | \
((A).y < EPS) ? 2 : 0 | ((A).y > -EPS) ? 16 : 0 | \
((A).z < EPS) ? 1 : 0 | ((A).z > -EPS) ? 8 : 0)
#endif
#define CROSS( A, B, C ) { \
(C).x = (A).y * (B).z - (A).z * (B).y; \
(C).y = -(A).x * (B).z + (A).z * (B).x; \
(C).z = (A).x * (B).y - (A).y * (B).x; \
}
#define SUB( A, B, C ) { \
(C).x = (A).x - (B).x; \
(C).y = (A).y - (B).y; \
(C).z = (A).z - (B).z; \
}
#define LERP( A, B, C) ((B)+(A)*((C)-(B)))
#define MIN3(a,b,c) ((((a)<(b))&&((a)<(c))) ? (a) : (((b)<(c)) ? (b) : (c)))
#define MAX3(a,b,c) ((((a)>(b))&&((a)>(c))) ? (a) : (((b)>(c)) ? (b) : (c)))
#define INSIDE 0
#define OUTSIDE 1
typedef struct{
CVector3 a; /* Vertex1 */
CVector3 b; /* Vertex2 */
CVector3 c; /* Vertex3 */
} Triangle3;

/*___________________________________________________________________________*/
/* Which of the six face-plane(s) is point P outside of? */
long face_plane(CVector3 p)
{
long outcode;
outcode = 0;
if (p.x > .5) outcode |= 0x01;
if (p.x < -.5) outcode |= 0x02;
if (p.y > .5) outcode |= 0x04;
if (p.y < -.5) outcode |= 0x08;
if (p.z > .5) outcode |= 0x10;
if (p.z < -.5) outcode |= 0x20;
return(outcode);
}
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */
/* Which of the twelve edge plane(s) is point P outside of? */
long bevel_2d(CVector3 p)
{
long outcode;
outcode = 0;
if ( p.x + p.y > 1.0) outcode |= 0x001;
if ( p.x - p.y > 1.0) outcode |= 0x002;
if (-p.x + p.y > 1.0) outcode |= 0x004;
if (-p.x - p.y > 1.0) outcode |= 0x008;
if ( p.x + p.z > 1.0) outcode |= 0x010;
if ( p.x - p.z > 1.0) outcode |= 0x020;
if (-p.x + p.z > 1.0) outcode |= 0x040;
if (-p.x - p.z > 1.0) outcode |= 0x080;
if ( p.y + p.z > 1.0) outcode |= 0x100;
if ( p.y - p.z > 1.0) outcode |= 0x200;
if (-p.y + p.z > 1.0) outcode |= 0x400;
if (-p.y - p.z > 1.0) outcode |= 0x800;
return(outcode);
}
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */
/* Which of the eight corner plane(s) is point P outside of? */
long bevel_3d(CVector3 p)
{
long outcode;
outcode = 0;
if (( p.x + p.y + p.z) > 1.5) outcode |= 0x01;
if (( p.x + p.y - p.z) > 1.5) outcode |= 0x02;
if (( p.x - p.y + p.z) > 1.5) outcode |= 0x04;
if (( p.x - p.y - p.z) > 1.5) outcode |= 0x08;
if ((-p.x + p.y + p.z) > 1.5) outcode |= 0x10;
if ((-p.x + p.y - p.z) > 1.5) outcode |= 0x20;
if ((-p.x - p.y + p.z) > 1.5) outcode |= 0x40;
if ((-p.x - p.y - p.z) > 1.5) outcode |= 0x80;
return(outcode);
}
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */
/* Test the point "alpha" of the way from P1 to P2 */
/* See if it is on a face of the cube */
/* Consider only faces in "mask" */
long check_point(CVector3 p1, CVector3 p2, float alpha, long mask)
{
CVector3 plane_point;
plane_point.x = LERP(alpha, p1.x, p2.x);
plane_point.y = LERP(alpha, p1.y, p2.y);
plane_point.z = LERP(alpha, p1.z, p2.z);
return(face_plane(plane_point) & mask);
}
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */
/* Compute intersection of P1 --> P2 line segment with face planes */
/* Then test intersection point to see if it is on cube face */
/* Consider only face planes in "outcode_diff" */
/* Note: Zero bits in "outcode_diff" means face line is outside of */
long check_line(CVector3 p1, CVector3 p2, long outcode_diff)
{
if ((0x01 & outcode_diff) != 0)
if (check_point(p1,p2,( .5-p1.x)/(p2.x-p1.x),0x3e) == INSIDE) return(INSIDE);
if ((0x02 & outcode_diff) != 0)
if (check_point(p1,p2,(-.5-p1.x)/(p2.x-p1.x),0x3d) == INSIDE) return(INSIDE);
if ((0x04 & outcode_diff) != 0)
if (check_point(p1,p2,( .5-p1.y)/(p2.y-p1.y),0x3b) == INSIDE) return(INSIDE);
if ((0x08 & outcode_diff) != 0)
if (check_point(p1,p2,(-.5-p1.y)/(p2.y-p1.y),0x37) == INSIDE) return(INSIDE);
if ((0x10 & outcode_diff) != 0)
if (check_point(p1,p2,( .5-p1.z)/(p2.z-p1.z),0x2f) == INSIDE) return(INSIDE);
if ((0x20 & outcode_diff) != 0)
if (check_point(p1,p2,(-.5-p1.z)/(p2.z-p1.z),0x1f) == INSIDE) return(INSIDE);
return(OUTSIDE);
}
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */
/* Test if 3D point is inside 3D triangle */
long point_triangle_intersection(CVector3 p, Triangle3 t)
{
long sign12,sign23,sign31;
CVector3 vect12,vect23,vect31,vect1h,vect2h,vect3h;
CVector3 cross12_1p,cross23_2p,cross31_3p;
/* First, a quick bounding-box test: */
/* If P is outside triangle bbox, there cannot be an intersection. */
if (p.x > MAX3(t.a.x, t.b.x, t.c.x)) return(OUTSIDE);
if (p.y > MAX3(t.a.y, t.b.y, t.c.y)) return(OUTSIDE);
if (p.z > MAX3(t.a.z, t.b.z, t.c.z)) return(OUTSIDE);
if (p.x < MIN3(t.a.x, t.b.x, t.c.x)) return(OUTSIDE);
if (p.y < MIN3(t.a.y, t.b.y, t.c.y)) return(OUTSIDE);
if (p.z < MIN3(t.a.z, t.b.z, t.c.z)) return(OUTSIDE);
/* For each triangle side, make a vector out of it by subtracting vertexes; */
/* make another vector from one vertex to point P. */
/* The crossproduct of these two vectors is orthogonal to both and the */
/* signs of its X,Y,Z components indicate whether P was to the inside or */
/* to the outside of this triangle side. */
SUB(t.a, t.b, vect12)
SUB(t.a, p, vect1h);
CROSS(vect12, vect1h, cross12_1p)
sign12 = SIGN3(cross12_1p); /* Extract X,Y,Z signs as 0..7 or 0...63 integer */
SUB(t.b, t.c, vect23)
SUB(t.b, p, vect2h);
CROSS(vect23, vect2h, cross23_2p)
sign23 = SIGN3(cross23_2p);
SUB(t.c, t.a, vect31)
SUB(t.c, p, vect3h);
CROSS(vect31, vect3h, cross31_3p)
sign31 = SIGN3(cross31_3p);
/* If all three crossproduct vectors agree in their component signs, */
/* then the point must be inside all three. */
/* P cannot be OUTSIDE all three sides simultaneously. */
/* this is the old test; with the revised SIGN3() macro, the test
* needs to be revised. */
#ifdef OLD_TEST
if ((sign12 == sign23) && (sign23 == sign31))
return(INSIDE);
else
return(OUTSIDE);
#else
return ((sign12 & sign23 & sign31) == 0) ? OUTSIDE : INSIDE;
#endif
}
/*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . */
/**********************************************/
/* This is the main algorithm procedure. */
/* Triangle t is compared with a unit cube, */
/* centered on the origin. */
/* It returns INSIDE (0) or OUTSIDE(1) if t */
/* intersects or does not intersect the cube. */
/**********************************************/
long t_c_intersection(Triangle3 t)
{
long v1_test,v2_test,v3_test;
float d, denom;
CVector3 vect12,vect13,norm;
CVector3 hitpp,hitpn,hitnp,hitnn;
/* First compare all three vertexes with all six face-planes */
/* If any vertex is inside the cube, return immediately! */
if ((v1_test = face_plane(t.a)) == INSIDE) return(INSIDE);
if ((v2_test = face_plane(t.b)) == INSIDE) return(INSIDE);
if ((v3_test = face_plane(t.c)) == INSIDE) return(INSIDE);
/* If all three vertexes were outside of one or more face-planes, */
/* return immediately with a trivial rejection! */
if ((v1_test & v2_test & v3_test) != 0) return(OUTSIDE);
/* Now do the same trivial rejection test for the 12 edge planes */
v1_test |= bevel_2d(t.a) << 8;
v2_test |= bevel_2d(t.b) << 8;
v3_test |= bevel_2d(t.c) << 8;
if ((v1_test & v2_test & v3_test) != 0) return(OUTSIDE);
/* Now do the same trivial rejection test for the 8 corner planes */
v1_test |= bevel_3d(t.a) << 24;
v2_test |= bevel_3d(t.b) << 24;
v3_test |= bevel_3d(t.c) << 24;
if ((v1_test & v2_test & v3_test) != 0) return(OUTSIDE);
/* If vertex 1 and 2, as a pair, cannot be trivially rejected */
/* by the above tests, then see if the v1-->v2 triangle edge */
/* intersects the cube. Do the same for v1-->v3 and v2-->v3. */
/* Pass to the intersection algorithm the "OR" of the outcode */
/* bits, so that only those cube faces which are spanned by */
/* each triangle edge need be tested. */
if ((v1_test & v2_test) == 0)
if (check_line(t.a,t.b,v1_test|v2_test) == INSIDE) return(INSIDE);
if ((v1_test & v3_test) == 0)
if (check_line(t.a,t.c,v1_test|v3_test) == INSIDE) return(INSIDE);
if ((v2_test & v3_test) == 0)
if (check_line(t.b,t.c,v2_test|v3_test) == INSIDE) return(INSIDE);
/* By now, we know that the triangle is not off to any side, */
/* and that its sides do not penetrate the cube. We must now */
/* test for the cube intersecting the interior of the triangle. */
/* We do this by looking for intersections between the cube */
/* diagonals and the triangle...first finding the intersection */
/* of the four diagonals with the plane of the triangle, and */
/* then if that intersection is inside the cube, pursuing */
/* whether the intersection point is inside the triangle itself. */
/* To find plane of the triangle, first perform crossproduct on */
/* two triangle side vectors to compute the normal vector. */

SUB(t.a,t.b,vect12);
SUB(t.a,t.c,vect13);
CROSS(vect12,vect13,norm)
/* The normal vector "norm" X,Y,Z components are the coefficients */
/* of the triangles AX + BY + CZ + D = 0 plane equation. If we */
/* solve the plane equation for X=Y=Z (a diagonal), we get */
/* -D/(A+B+C) as a metric of the distance from cube center to the */
/* diagonal/plane intersection. If this is between -0.5 and 0.5, */
/* the intersection is inside the cube. If so, we continue by */
/* doing a point/triangle intersection. */
/* Do this for all four diagonals. */
d = norm.x * t.a.x + norm.y * t.a.y + norm.z * t.a.z;
/* if one of the diagonals is parallel to the plane, the other will intersect the plane */
if(fabs(denom=(norm.x + norm.y + norm.z))>EPS)
/* skip parallel diagonals to the plane; division by 0 can occur */
{
hitpp.x = hitpp.y = hitpp.z = d / denom;
if (fabs(hitpp.x) <= 0.5)
if (point_triangle_intersection(hitpp,t) == INSIDE) return(INSIDE);
}
if(fabs(denom=(norm.x + norm.y - norm.z))>EPS)
{
hitpn.z = -(hitpn.x = hitpn.y = d / denom);
if (fabs(hitpn.x) <= 0.5)
if (point_triangle_intersection(hitpn,t) == INSIDE) return(INSIDE);
}
if(fabs(denom=(norm.x - norm.y + norm.z))>EPS)
{
hitnp.y = -(hitnp.x = hitnp.z = d / denom);
if (fabs(hitnp.x) <= 0.5)
if (point_triangle_intersection(hitnp,t) == INSIDE) return(INSIDE);
}
if(fabs(denom=(norm.x - norm.y - norm.z))>EPS)
{
hitnn.y = hitnn.z = -(hitnn.x = d / denom);
if (fabs(hitnn.x) <= 0.5)
if (point_triangle_intersection(hitnn,t) == INSIDE) return(INSIDE);
}

/* No edge touched the cube; no cube diagonal touched the triangle. */
/* We're done...there was no intersection. */
return(OUTSIDE);
}[/code]

[code]
bool TriBoxOverlap(CVector3 vPos, CVector3 vMin, CVector3 vMax, CVector3* vTri)
{
float center[3];
center[0] = vPos.x+vMax.x+vMin.x;
center[1] = vPos.y+vMax.y+vMin.y;
center[2] = vPos.z+vMax.z+vMin.z;
float halfsize[3];
halfsize[0] = (vMax.x-vMin.x)/2.0f;
halfsize[1] = (vMax.y-vMin.y)/2.0f;
halfsize[2] = (vMax.z-vMin.z)/2.0f;
float scaledown[3];
scaledown[0] = 1.0f / halfsize[0];
scaledown[1] = 1.0f / halfsize[1];
scaledown[2] = 1.0f / halfsize[2];
Triangle3 tri;
tri.a = (vTri[0] - center) * scaledown[0];
tri.b = (vTri[1] - center) * scaledown[1];
tri.c = (vTri[2] - center) * scaledown[2];
if(t_c_intersection(tri) == INSIDE)
return true;
return false;
}
[/code]

Share this post


Link to post
Share on other sites

This topic is 1931 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this