Collision Detection Woes

dstaudigel
Unregistered
 
Post: #1
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
Quote this message in a reply
Member
Posts: 114
Joined: 2002.08
Post: #2
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

"Most nutritionists say that Twinkies are bad. But they're not, they're very very good."
Quote this message in a reply
dstaudigel
Unregistered
 
Post: #3
Helpful, but in the wrong dimention. 3d coldet is what i'm talkin 'bout.
Quote this message in a reply
Member
Posts: 184
Joined: 2004.07
Post: #4
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.
Quote this message in a reply
dstaudigel
Unregistered
 
Post: #5
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
Quote this message in a reply
kainsin
Unregistered
 
Post: #6
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.
Quote this message in a reply
Member
Posts: 114
Joined: 2002.08
Post: #7
Just add a third dimension to the matrix and calculate that too silly Grin . 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 this message in a reply
Member
Posts: 204
Joined: 2002.09
Post: #8
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
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Optimize the collision detection alaslipknot 1 2,801 May 12, 2013 08:02 PM
Last Post: SethWillits
  Collision detection tutorial ThemsAllTook 7 22,830 Nov 5, 2011 05:20 PM
Last Post: SethWillits
  Help with Collision Detection..(i'm almost there) carmine 1 4,694 Jun 29, 2011 12:33 PM
Last Post: ThemsAllTook
  Time Delta, collision detection mk12 19 15,647 Sep 8, 2010 06:40 PM
Last Post: AnotherJake
  Collision detection for pinball game johncmurphy 0 4,804 Sep 6, 2009 02:46 PM
Last Post: johncmurphy