Sign in to follow this  

collissions

This topic is 4203 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 were thinking how to make not expensive (i mean CPU usage) 3D collission detection. I want to check collisions betwen blocks (really more than two). I came up with idea to check only that edges are in other blocks (which are rotated in all vectors). I was writing the code but i realized - the blocks can go trough others if they are like this:
    .____.
    |    |
.___|____|___.
|   |    |   |
.___|____|___.
    |    |
    .____.
(dots are the edges) Can any one help to not let 'em do that? Thanks anyway!

Share this post


Link to post
Share on other sites
I suposed it wount be clear... Well I wanted to show that the edges can pass trough outside other block but blocks are collided but my engine does not calculate it. Thats where i need help.

Share this post


Link to post
Share on other sites
well anyhow...
you said 3D
but then you also want to collide by checking edges to edges only.
That doesnt work.... for 2d edge checks are ok, for 3d you need to start thinking about colliding faces(triangles generally) to each other

the most obvious problem with edges only i can think of is a tiny box vs a large box. the tiny one can fall thru the middle of one of the big one's sides, without actually touching any edges...

if your objects are always boxes
and are always axis aligned (no rotations)
then you might be able to hack something together with edges only by checking one dimension at a time (flatten the situation into 3 separate 2d problems)

but otherwise you need to start thinking about face/polygon based collisions

Share this post


Link to post
Share on other sites
Quote:
Original post by TransistoR
I were thinking how to make not expensive (i mean CPU usage) 3D collission detection. I want to check collisions betwen blocks (really more than two). I came up with idea to check only that edges are in other blocks (which are rotated in all vectors). I was writing the code but i realized - the blocks can go trough others if they are like this:

.____.
| |
.___|____|___.
| | | |
.___|____|___.
| |
.____.

(dots are the edges)

Can any one help to not let 'em do that?

Thanks anyway!
What you show here is the classic problem with point-inclusion intersection tests. Fortunately, it's not necessary to perform multiple edge-face tests or what have you to work around this - there are better and more efficient algorithms. Of these, the separating axis theorem is probably the most well documented and easiest to implement. Just ask if you need further info on that.

Share this post


Link to post
Share on other sites
Quote:
Original post by TransistoR
Oh I get it now. I need face to face (ouch!) calculations. Can anyone give me a hint how to do that.
No, you don't need to perform face-face intersections, edge-face intersections, or anything like that; that's the whole point. Did you see my post on the separating axis theorem above? If you're not sure what it is, just ask, and I or someone else can point you toward some links or references.

Share this post


Link to post
Share on other sites
http://www.harveycartel.org/metanet/tutorials/tutorialA.html#section1
Separating Axis Theorem

it lets you quickly decide if two boxes are Not Colliding so you don't have to do any expensive math.
If SAT says that they Are Colliding though, depending on what your game does you might need to do face/face checks at that point.

Share this post


Link to post
Share on other sites
Quote:
Original post by haphazardlynamed
If SAT says that they Are Colliding though, depending on what your game does you might need to do face/face checks at that point.
Usually not though; the SAT can be extended to return collision points (or manifold) for both static and swept intersection tests.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
Original post by haphazardlynamed
If SAT says that they Are Colliding though, depending on what your game does you might need to do face/face checks at that point.
Usually not though; the SAT can be extended to return collision points (or manifold) for both static and swept intersection tests.


I'd be interested to see how this is done, think you could provide a link to a paper? At the moment I have minimum penetration axis and depth calculations embedded into my SAT tests which allows me to seperate objects so that they're only just touching with the minimum displacement. From here its possible to use the calculated min penetration axis to determine which features are touching so you can jump straight to the correct clipping test to determine the collision points. I've never seen a way its possible to get collision points fall directly out of the SAT test though.

Share this post


Link to post
Share on other sites
Quote:
Original post by Motorherp
I'd be interested to see how this is done, think you could provide a link to a paper? At the moment I have minimum penetration axis and depth calculations embedded into my SAT tests which allows me to seperate objects so that they're only just touching with the minimum displacement. From here its possible to use the calculated min penetration axis to determine which features are touching so you can jump straight to the correct clipping test to determine the collision points. I've never seen a way its possible to get collision points fall directly out of the SAT test though.
Yeah, I was just referring to the support feature clipping method you describe. I suppose it doesn't fall 'directly' out of the SAT test, but I think it could be considered an extension thereof.

My point to the OP still stands though; in most cases, per-feature clipping or intersection testing is not required, and if you only need a boolean result or first time of intersection, it's definitely not required.

Share this post


Link to post
Share on other sites

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