Jump to content
  • Advertisement
Sign in to follow this  
mike25025

2d collision detection with triangles

This topic is 4827 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 programing a physics engine and have run into a problem. I don't know how to separate two objects and find the point of collision. My objects are stored as triangles and the triangles can be arranged in any way (not connected, overlapping etc.). I have SAT implemented for detecting a collision but I don't know what to do next. If I have to I will implement a different method but I don't know what other algorithms there are. Could someone help me or tell me where I can find a tutorial?

Share this post


Link to post
Share on other sites
Advertisement
Check here: http://uk.geocities.com/olivier_rebellion/
And specifically this demo (includes lots of usefull documentation): http://uk.geocities.com/olivier_rebellion/Polycolly.zip

Of course, do not forget to google for it. I'm sure you'll find planty of other tutorials over the net.

Share this post


Link to post
Share on other sites
Ive read Olis tutorials (I have the polycolly docs open in my browser right now).
Unfortunately he only uses polygons and doesn't describe how to use groups of triangles which is what I need.

Share this post


Link to post
Share on other sites
that problem is difficult. The SAT works well for convex geometry, but for polygon soups, it's a lot more complicated usually, due to the number of contacts it can generate (if you do a per-poly calculation).

The thing with per-triangle tests, there is no notion of volume. It's just a bunch of triangles colliding.

You need to analyse the intersections and turn them into meaningful data.

I never really tried to solve those problems, maybe subconsciously trying to avoid the nightmares they generate, but here's a thought.

...I don't think there is a full-proof design on how to extract informations from intersections, but if you store the intersections between triangles (will gives segments), those segments should give you closed contour lines.

Now what to do with those lines... Well, they should roughly follow a plane, and then you can guess where this is going. You need to extract orientation information from those contours (like, use a covariance matrix, and eigen vectors to form a basis, and take the smallest of the vector deviation as your plane normal).

With non-convex geometry, you will get several contours. Each of them will produce a contact point (the 'centre' of the countour) and a normal (the normal of the plane that best fits the contour points).

That's for intersections.

For collisions, where triangles naturally collide after a given time, then you just need a bit of sorting and merging the contact points that are close together to avoid redundancies (and over the top responses).

That, or order your model into convex pieces and use the SAT / GJK / whatever.

my 2 cents.

Share this post


Link to post
Share on other sites
Quote:
Original post by oliii
confusing stuff

That, or order your model into convex pieces and use the SAT / GJK / whatever.


I think Ill do the latter.

But theres still the problem of how to represent the static geometry of the world (which will have concave shapes). How does one handle this?

Share this post


Link to post
Share on other sites
triangles, that you collide with simple shapes, like boxes and sphere, and some fudge to make it work.

Here is an example of a method I used.

It's not particularly good nor clever, and the collision system it was used for was only dealing with intersecting geometry. My main problem was hitting edges of triangles, which will provide a hard collision, even if the surface appears smooth. This was mainly a problem with bxes, spheres would bump a bit, but nothing major, but it was still a problem.

A way I dealt with was to generate normals at vertices. then when I got a edge-edge collision between a triangle and a box, I'd find teh point on the triangle edge that was in contact. On that point, I'd interpolate the normal from the two edge vertices. That normal was then used for the collision impulse, not the intersection direction. That way, for flat surfaces, the normal on vertices would point up, and so was the interpolated normal on the edge.

That produced a smooth collision impulse.

There was also the matter of cleaning up the contacts (avoid duplications and redundancies), sorting them (along the velocity), and the small matter of dealing with reducing intersections, ect... It worked OK in the end, but not perfect by any means. Again, one way to reduce those problems is deal with swept tests.

So, lots of fudge.

demos.
- keys : F1->F8 for various demos, AWSD, mouse.
- docs included for the swept SAT.

Share this post


Link to post
Share on other sites
I cant get it to work. [sad] Somethings wrong with the impulse or collision point but I cant figure it out. I dont know what to do.

Share this post


Link to post
Share on other sites
if you don't tell us what you are doing, we can't help you.

BTW, I missed the "2d" part in the OP. but anyway, show us what you are doing.

Share this post


Link to post
Share on other sites
I know that the SAT is working so it must be something in this code.

Sorry for the bad variable names. This is in Python but I'm not too worried about performance yet.

# finds the collision point
def __findCP(self,ta,tb,n): # ta is a triangle from object a and tb is from object b. n is the collision normal
ma = 1000000.0
mb = -1000000.0

# find the minimum and maximum points on the triangles
for p in ta:
t = p.dot(n)
if t < ma:
ma = t

for p in tb:
t = p.dot(n)
if t > mb:
mb = t

na = 0
nb = 0

cpa = None
cpb = None

# count the points on the axis
for p in ta:
t = p.dot(n)
if math.fabs(t-ma) <= 0.001:
na += 1
cpa = p

for p in tb:
t = p.dot(n)
if math.fabs(t-mb) <= 0.001:
nb += 1
cpb = p

if na > 1:
return cpb
return cpa

##############################

# this is after a collision has been found

d = self.pos - body.pos # get the difference between bodys
if d.dot(p) < 0.0: # p is the normal of collision
p = Vector([0,0])-p # i didnt make a negative operator

fa = 1.0 # this code seperates the bodys (whats the correct way to do this?)
fb = 1.0
if self.invmass == 0:
fa = 0.0
if body.invmass == 0:
fb = 0.0

self.pos += p*fa
body.pos -= p*fb

ta = Triangle(self.tris[cp[0]]) # make a copy of the colliding triangle on this body
tb = Triangle(body.tris[cp[1]]) # make a copy of the colliding triangle on the other body

if math.fabs(self.r) > 0.0001: # rotate
ta.rotate(self.r)
if math.fabs(body.r) > 0.0001:
tb.rotate(body.r)

ta += self.pos # translate
tb += body.pos

cp = self.__findCP(ta,tb,p) # finds the colliding point

pa = self.pos-cp # difference of cp and center of this object
pa = Vector([-pa.y,pa.x]) # make it perpendicular

pb = body.pos-cp # same as above but for other object
pb = Vector([-pb.y,pb.x])

pa1 = pa.dot(p) # used in impulse calculation
pb1 = pb.dot(p)

# impulse
j = -(1.0+1.0)*((self.dpos-body.dpos).dot(p)) / (p.dot(p)*(self.invmass+body.invmass) + pa1*pa1*self.invinertia + pb1*pb1*body.invinertia)

# change the velocity and rotational velocity
self.dpos = self.dpos + j*self.invmass*p
body.dpos = body.dpos - j*body.invmass*p

self.dr = self.dr + pa.dot(-j*p)*self.invinertia
body.dr = body.dr + pb.dot(j*p)*body.invinertia

Share this post


Link to post
Share on other sites
If your problem is: search for collisions in a set of triangles the algorithm is really simple!

First you need a data structure to store your triangles.
In 2D you can use quadtree or, best, an hash matrix (voxel).
The idea is to divide your space in a grid of cells.
In each cell you store a list of the triangles intersecting the cell.
As insertion key you can use, conservatively, the bounding rect of the triangle.
The hash map (quadtree, matrix, ...) is very important if you have a lot of triangles!
In fact if you compare each triangles with the entire set you will get O(N^2); by using an hash matrix you can reduce considerably the work.
Obviously a trick is to compare
T1 with T2,T3,...,Tn then
T2 with T3,..,Tn (T1 and T2 already compared)
Ti with Ti+1,...,Tn
So you have the half of comparisons.

Instead with an hash map, given a triangle, you can find a set of possible intersections.

Given two triangles the algorithm is the edge-edge test. If you find an edge of triangle A that intersects an edge of triangle B you have found an intersection.
So in the worst case you have to perform 6 tests.
Tip: you can avoid the intersection test if the bounding rectangles have no intersection. This test is fast.

In 3D it's more complicate but not so much; in this case you can use a frustum cull.
This solution applied to 2D is interesting because if the clipping is not empty you have also the intersection area (in the form of a convex polygon).

So your problem is reduced to implement an hash map and to compute segment-segment intersection.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!