Archived

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

Collision detection problem: been plaguing me for weeks :(

This topic is 5130 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''m working on writing a game with a ball and a bunch of walls in C++ using OpenGL. I''m having problems with collision detection at corners. Some stuff about my problem is available at this page I put up. Each wall is represented as four line segments, forming a quadrilateral. In the example on that page, there are four walls (represented by the Wall class), making for a total of sixteen line segments. At every frame, the program checks for collision in every wall. I have a function written for a point-to-line-segment collision. It takes a position and a velocity, both represented as vectors. It creates a vector D going from the center of the line segment to the position, and a vector Dprime from the center of the line segment to the objects position+velocity, in other words, where the point is "about to be". The vector W goes from the line segment''s center to one endpoint, and N is perpendicular to W. It then compares the dot product N·D to N·Dprime. If their signs are different, (one is positive and the other is negative) that means that D and Dprime are on opposite sides of the line segment, in other words, that the point is about to cross the line segment. If this is true and Dprime isn''t too far away from the center of the line segment, a collision is registered. The Wall class handles collision detection by checking each of its four line segments (represented by the Barrier class) for a collision given the ball''s position and its velocity. The Barrier''s collision detection returns either 0 (no collision) or a float representing the distance from the ball to the barrier in question. After all the wall''s have been checked for a collision, a function call returns a unit vector that is perpendicular to the closest Barrier that registered a collision. Then, if that vector isn''t NULL, the ball''s velocity vector is reflected about it. I am sure that the reflection is done correctly. Any ideas on this topic would be very greatly appreciated. Thank you in advance for any help you might be able to give me, and not in advance for having read this topic.

Share this post


Link to post
Share on other sites
yeah, queue up your collisions, from nearest to farthest, process them one by one. I sort them by order of time, and I also store overlaps in the list, with a time value negative, and the value being the overlap depth. That way, all my overlaps are staisfied first.

I might change this system later on, it seems a bit extreme

Share this post


Link to post
Share on other sites
I''m not sure queueing the collisions would work with the particular model i''m using. If two collisions are registered, the farthest one will usually be on the opposite side of the wall that registered the nearest. Like so:


/
+-2-----
|/
1
/|
/ |
/ |
o |


If I bounce the ball for the first collision, then the second one won''t matter anymore:


\
\ +-2-----
\|
1
/|
/ |
/ |
o |


Now (2) is no longer on the path of the ball.

Share this post


Link to post
Share on other sites
quote:
Original post by Tokage
I''m not sure queueing the collisions would work with the particular model i''m using. If two collisions are registered, the farthest one will usually be on the opposite side of the wall that registered the nearest. Like so:


/
+-2-----
|/
1
/|
/ |
/ |
o |


If I bounce the ball for the first collision, then the second one won''t matter anymore:


\
\ +-2-----
\|
1
/|
/ |
/ |
o |


Now (2) is no longer on the path of the ball.



that''s right.
When you process a collision, you need to remove all collisions involving mobile objects (objects that will change path from it) from the queue, and if those collisions involve other mobile objects, you need to re-process collisions for those objects as well.

Basically, all you need to keep is the first collision happening to each mobiles in the world. You do not need to store later collisions for each of them. So each objects has one collision report, and all those reports are sorted by overlap then time. Also, it can happen that two objects share the same collision report, obviously.

say you have objects
A
B
C
D
E
F

and the static geometry S

and when you detect collisions you found that

A (A, S, -0.1f)
B (B, E, 0.1f)
C (C, D, -0.05f)
D (D, C, -0.05f)
E (E, A, -0.01f)
F (F, S, 0.5f)

A overlaps the static geometry with depth of 10 cm, B collides with E at time 0.1 sec, C overlaps with D with a depth of 5cm, F collides with static geometry at time 0.5 sec. Each object has its own collision report. Each report stores the indices of both objects, and the time/overlap amount.

you sort the collision reports and you get

(A, S, -0.1f)
(C, D, -0.05f)
(D, C, -0.05f)
(E, A, -0.01f)
(B, E, 0.1f)
(F, S, 0.5f)


so you process first report. A collide with S, which does not move after the collision is processed (static geometry). A on the other hand will react, so you must remove all collision reports that involve A, and store a list of objects that need to be retested for collision.

the list become

(C, D, -0.05f)
(D, C, -0.05f)
(B, E, 0.1f)
(F, S, 0.5f)

and objects to test again are A, E.

you found that E then collide with A at time 0.3f
then you have.

A (A, E, 0.3f)
E (E, A, 0.3f)

you insert those two in the list and you have

(C, D, -0.05f)
(D, C, -0.05f)
(B, E, 0.1f)
(A, E, 0.3f)
(E, A, 0.3f)
(F, S, 0.5f)

Now you process the (C, D), you need to test only C and D again (they are mobiles). You found that neither C or D collide after the collision is processed. The list becomes

(B, E, 0.1f)
(A, E, 0.3f)
(E, A, 0.3f)
(F, S, 0.5f)


so you work your way up until the list is empty.

Now, I''m not sure if this system works if you are using time scales. I tried it with displacement vectors and it works fine. Displacement vectors have the advantage that they do not rely on all the objects having the same timeframe, Like you would have to do (move ALL objects to the time of collisoin, test all objects again).

so, basically, the system I use works with distance to intersection, which works for both overlap and impacts, and objects closest (or deeply embedded) to each other are processed first.

Share this post


Link to post
Share on other sites