# 2d collision detection with triangles

This topic is 4898 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
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 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 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 on other sites
Quote:
 Original post by oliiiconfusing stuffThat, 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 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 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 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 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 pointdef __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 foundd = self.pos - body.pos		# get the difference between bodysif d.dot(p) < 0.0:			# p is the normal of collision	p = Vector([0,0])-p		# i didnt make a negative operatorfa = 1.0				# this code seperates the bodys (whats the correct way to do this?)fb = 1.0if self.invmass == 0:	fa = 0.0if body.invmass == 0:	fb = 0.0self.pos += p*fabody.pos -= p*fbta = Triangle(self.tris[cp[0]])		# make a copy of the colliding triangle on this bodytb = Triangle(body.tris[cp[1]])		# make a copy of the colliding triangle on the other bodyif 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			# translatetb += body.poscp = self.__findCP(ta,tb,p)		# finds the colliding pointpa = self.pos-cp			# difference of cp and center of this objectpa = Vector([-pa.y,pa.x])		# make it perpendicularpb = body.pos-cp			# same as above but for other objectpb = Vector([-pb.y,pb.x])pa1 = pa.dot(p)			# used in impulse calculationpb1 = pb.dot(p)# impulsej = -(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 velocityself.dpos = self.dpos + j*self.invmass*pbody.dpos = body.dpos - j*body.invmass*pself.dr = self.dr + pa.dot(-j*p)*self.invinertiabody.dr = body.dr + pb.dot(j*p)*body.invinertia

##### 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.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 11
• 11
• 15
• 11
• 11
• ### Forum Statistics

• Total Topics
634149
• Total Posts
3015834
×