Collision Detection Woes

[dstaudigel]

Is it just me or are hit/collision/intersection tests the biggest @$$pain in the world? I'm having troubles after troubles. I won't even bother posting my code at this point. Anyhow, i found ColDet library, which is good for intersection, but how do i do moving sphere/model and another (maybe moving?) sphere/model? Are there any stand-alone libs like ColDet?

Daniel

[Dr. Light]

I don't know if you can manipulate matrixes in C++ just like BASIC, (although I'm pretty sure you can) but here is something simple you can do that also works pretty fast. First, take your x and y screen sizes and divide it by the size of the area you would like to check (xblocks=640/50, yblocks=480/50 - which makes each "block" 50 pixels), this is the initial size of your matrix. Next, take your sprite's position and put it into a "block" in you matrix at these positions ( sprite_x/50 sprite_y/50 - make sure to round these to the nearest whole number). Then do the same for the sprite that might collide with it, just see if it has the same matrix position. You can make it a higher resolution by making the "blocks" smaller, and putting more of them down in specific locations



matrix example1:

*=hit
1=sprite1
2=sprite2

frame 1:
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000001000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000000002000000000000
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000


frame 2:
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000010000000000000000
00000000000000000000000000
00000000000020000000000000
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000

frame 3:
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
0000000000*000000000000000
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000



Matrix example 2:

frame 1:
00000000000000000000000000
00000000000000000000000000
00000001100000000000000000
00000011110000000000000000
00000001100000000000000000
00000000000000000000000000
00000000000002000000000000
00000000000002000000000000
00000000000222220000000000
00000000002202022000000000
00000000000000000000000000
00000000000000000000000000


frame 2:
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000110000000000000000
00000001111000000000000000
00000000110000000000000000
00000000000200000000000000
00000000000200000000000000
00000000022222000000000000
00000000220202200000000000
00000000000000000000000000
00000000000000000000000000

frame 3:
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000000000000000000000
00000000000110000000000000
00000000001*1100000000000
00000000000*10000000000000
00000000022222000000000000
00000000220202200000000000
00000000000000000000000000
00000000000000000000000000

[dstaudigel]

Helpful, but in the wrong dimention. 3d coldet is what i'm talkin 'bout.

[phydeaux]

I've had pretty good luck with libSOLID:
http://www.win.tue.nl/~gino/solid/

LGPL, so you can freely distribute it. SOLID supports boxes, spheres, cylinders, cones, polygon soup, simple polytopes.

I haven't tried any physics engines, though. I tend to use my own simplistic physics.

[dstaudigel]

Just one question... This solid thing will calculate hits between frame 1 and frame 2 right?

Say I have a sphere (me) falling from a great height, and i am going really fast. In normal hit testing, my sphere would never coincide with the level model, and i just pass right through it. Does SOLID test for intersections between frames? i couldn't tell from the manual.

Daniel

[kainsin]

This is probably one of the most asked questions about 3D out there without as much useful documentation that is needed.

If you know some Linear Algebra then this isn't too difficult. Basically, just find the vector that describes the object's direction and see if it passes through the plane of at least one face of the other objects.

[Dr. Light]

Just add a third dimension to the matrix and calculate that too silly :D . matrix(x,y,z). Its not meant to be super accurate though, just quick and lean, so it still may not help you out any. Just trying to be helpful though.

[KittyMac]

Originally posted by dstaudigel
Just one question... This solid thing will calculate hits between frame 1 and frame 2 right?

Say I have a sphere (me) falling from a great height, and i am going really fast. In normal hit testing, my sphere would never coincide with the level model, and i just pass right through it. Does SOLID test for intersections between frames? i couldn't tell from the manual.

Daniel

Perhaps an easier method (although admittedly more costly CPU wise) is to increase the number of updates per screen refresh. So, for instance instead of having the ball fall a far distance per update, have it fall a shorter distance over multiple updates in the same amount of time. I tend to use code which update 200 times per seconds and allows the renderer to draw as fast as it can. This gives good enough results for me.

Doing this can clear up most case of collision detection to just hit detection. If not, you may need to do is find the intersection between two lines.



typedef struct{
float x, y, z;
}fPoint;

int intersectLineSegments( fPoint p0,
fPoint p1,
fPoint p2,
fPoint p3,
fPoint * loc,
float * distance)
/* Finds the intersection between two line segments defined by {p0, p1} and {p2, p3}
* Point of intersection is returned in loc
* function returns 1 if hit, 0 if miss
* Note: This is only for 2D collision detection, but with a little research you can extend
* to the third
*/
{
fPoint s1 = {p1.x - p0.x, p1.y - p0.y};
fPoint s2 = {p3.x - p2.x, p3.y - p2.y};
float s, t, d;

d = ( (-s2.x) * s1.y + s1.x * s2.y );

// Line Segments Are Parallel
if(d == 0.0){
float d1, d2;
int col = 0;

if(p0.x == p2.x){
// Parallel Vertical Lines
if(p3.y > p2.y){
if(p0.y <= p3.y && p0.y >= p2.y)
col = 1;
if(p1.y <= p3.y && p1.y >= p2.y)
col = 1;
}else{
if(p0.y <= p2.y && p0.y >= p3.y)
col = 1;
if(p1.y <= p2.y && p1.y >= p3.y)
col = 1;
}
}else{
// Parallel Horizontal Lines
if(p3.x > p2.x){
if(p0.x <= p3.x && p0.x >= p2.x)
col = 1;
if(p1.x <= p3.x && p1.x >= p2.x)
col = 1;
}else{
if(p0.x <= p2.x && p0.x >= p3.x)
col = 1;
if(p1.x <= p2.x && p1.x >= p3.x)
col = 1;
}
}

if(col){
d1 = (p0.x - p2.x) * (p0.x - p2.x) + (p0.y - p2.y) * (p0.y - p2.y);
d2 = (p0.x - p3.x) * (p0.x - p3.x) + (p0.y - p3.y) * (p0.y - p3.y);

if(d1 <= d2){
*distance = d1;
*loc = p2;
}else{
*distance = d2;
*loc = p3;
}
//return 1;
}

return 0;
}

s = ( (-s1.y) * (p0.x - p2.x) ) + (s1.x * (p0.y - p2.y) );

t = (s2.x * (p0.y - p2.y)) - (s2.y * (p0.x - p2.x) );

s /= d;
t /= d;

if(s >= 0.0 && s <= 1.0){
if(t >= 0.0 && t <= 1.0){
t -= 0.01;
loc->x = p0.x + t * s1.x;
loc->y = p0.y + t * s1.y;

*distance = (p0.x - loc->x) * (p0.x - loc->x) + (p0.y - loc->y) * (p0.y - loc->y);

return 1;
}
}

return 0;
}




Cheers,
Rocco