Collision Detection Woes
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 standalone libs like ColDet?
Daniel
Daniel
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
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
"Most nutritionists say that Twinkies are bad. But they're not, they're very very good."
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.
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.
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
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
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.
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.
Just add a third dimension to the matrix and calculate that too silly . 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.
"Most nutritionists say that Twinkies are bad. But they're not, they're very very good."
Quote: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.
Code:
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
Virus Out
Big Bang Board Games
Adventures on Pirate Isle
Solace  Strategy, War, and Glory!
The Belt
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
Optimize the collision detection  alaslipknot  1  4,385 
May 12, 2013 08:02 PM Last Post: SethWillits 

Collision detection tutorial  ThemsAllTook  7  24,860 
Nov 5, 2011 05:20 PM Last Post: SethWillits 

Help with Collision Detection..(i'm almost there)  carmine  1  5,440 
Jun 29, 2011 12:33 PM Last Post: ThemsAllTook 

Time Delta, collision detection  mk12  19  18,261 
Sep 8, 2010 06:40 PM Last Post: AnotherJake 

Collision detection for pinball game  johncmurphy  0  5,371 
Sep 6, 2009 02:46 PM Last Post: johncmurphy 