Sign in to follow this  
Penguins

concave 2d polygon collision

Recommended Posts

sorry if this topic is a repeat. I am looking for a method to deal with the collision of two concave polygons. I am well aware of the point in polygon algorithms, however as my prgram is set up now, the toy is just moved backed to it's last position when a collision is detected. Clearly, this is not sufficient for my game. I've looked at several articles about collision however all of them describe ways of dealing with _convex_ polygons. Has anyone dealt with or know of a way of dealing with concave polygons?

Share this post


Link to post
Share on other sites
While it's conceivable that there might be an algorithm for intersecting concave polygons, I suggest that you simply tesselate them into convex polygons and check each pair. How concave are we talking about, anyway?

Share this post


Link to post
Share on other sites
Presumably there are two things you want to do - (1) see if the objects are intersecting and (2) if they are work out the minimum delta that's required to separate them (works as both a collision normal and a penetration depth/direction) .

Since it's 2D, you might be able to get away with a rather brute-force approach:

1. For intersection, just test all the edges of one polygon against the edges of the other (can speed this up using a tree-structure if your objects are moderately/very complicated), and vice-versa.

2. For the penetration bit:

2.1 Pre-process each object (before you start the simulation) to set up a grid of points that just covers it, in object space. At each point record (a) if it's inside or outside the polygon and (b) the direction and distance to the nearest edge. Then make a function that will take any position in world space and, using interpolation, indicate if that world position is inside/outside, and if the former, the direction/distance to the nearest edge.

2.2 During your collision detection, walk around the edge of the first polygon (let's say you start at a point that is outside the second polygon). When you reach an intersection point from step 1 above, start sampling the second polygon to find the maximum penetration depth/direction. When you leave the second polygon record the maximum depth that you found. At the end of this (and when you process the second polygon against the first) you'll have got a list of contact points/directions/depths.

So long as objects don't move too far compared to their "feature size", you should get sensible results from this. I did something similar in 3D and it worked OK, but it was a bit slow and used a lot of memory - in 2D these problems won't be so bad.

Share this post


Link to post
Share on other sites
Mr. Rowl, the brute force solution you describe seems rather limited and unflexible,(what if i want to rotate or move in object? i would have to rotate every precalculated point). Is the problem of concave collision so rare? I thought it would be relatively common, such as terrain for a 2d game like soldat. but perhaps tesselating is the best solution, thanks for your help.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
google search "Point-In-Polygon Algorithm — Determining Whether A Point Is Inside A Complex Polygon"

Share this post


Link to post
Share on other sites

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