# Collision Detection

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

## Recommended Posts

Hey guys, I am working on a research problem where I have moving triangular surface grid. So I have triangles (defined by points and the connectivity info). So there could be multiple collision s. What I have done is: a) For each triangle-point combination, I try to compute the time t when this point lies on the plane formed by the triangle. I do this by getting the equation of a plane as function of time, the location of the point as a function of time. I get this cubic equation in time which I proceed to solve. Since nonlinear equations are a pain to solve, I am looking at alternate algorithms. I have looked at bunch of papers, but all seemed to talk about collision between a moving and a stationary object. In my case, every point is moving. So can anyone point to a paper which talks about collision detection between multiple moving bodies? Thanks!

##### Share on other sites
Couple of questions. By 'triangular surface grid', do you mean a triangle mesh? If so, is the mesh convex or concave?

Also, when you say 'triangle-point combination', what are the points in question?

Most collision detection algorithms work with one moving object and one stationary object, with the understanding that most problems involving two moving objects can be reconfigured so that one is stationary.

The cubic equation bit doesn't sound right, but I don't want to say any more without having a better idea of what you're doing.

##### Share on other sites
Quote:
 Original post by jykCouple of questions. By 'triangular surface grid', do you mean a triangle mesh? If so, is the mesh convex or concave?Also, when you say 'triangle-point combination', what are the points in question?Most collision detection algorithms work with one moving object and one stationary object, with the understanding that most problems involving two moving objects can be reconfigured so that one is stationary.The cubic equation bit doesn't sound right, but I don't want to say any more without having a better idea of what you're doing.

Yes, it is a triangular mesh. I am not sure how it matters if the mesh is convex or concave. It could be any kind of surface.

Basically, I am trying to find if any of the points of the mesh would collide with a face of the mesh. Each of the points has some velocity vector, so each triangle of the mesh is also moving (because the points forming the triangle are moving).

So the triangles of the mesh are not rigid, they also deform as they move in time due to the motion of the points. So that is why the equation of the plane of this triangle is quadratic in time. So taking the location of any other point, which is linear in time (not the 3 points forming a triangle), and plugging into this plane eqn, one ends up with a cubic equation.

So what do you suggest?

##### Share on other sites
Comments, and a couple more questions...
Quote:
 Yes, it is a triangular mesh. I am not sure how it matters if the mesh is convex or concave. It could be any kind of surface.
For collision detection, it is of great significance whether the object is convex or concave, in that most commonly used collision detection algorithms operate only on convex objects. It sounds though like you're trying to do per-triangle collision detection, in which case it's not as relevant.
Quote:
 Basically, I am trying to find if any of the points of the mesh would collide with a face of the mesh. Each of the points has some velocity vector, so each triangle of the mesh is also moving (because the points forming the triangle are moving).
I don't think per-vertex will work, as two triangles can collide without any of their vertices colliding with the face of the other. For this and other reasons, tri-tri intersection is usually handled using other methods.
Quote:
 So the triangles of the mesh are not rigid, they also deform as they move in time due to the motion of the points.
When I think 'deform' I think of the mesh actually changing shape. But it sounds like you just mean the mesh as a whole is undergoing linear motion. Can you clarify?

##### Share on other sites
Quote:
Original post by jyk
Comments, and a couple more questions...
Quote:
 Yes, it is a triangular mesh. I am not sure how it matters if the mesh is convex or concave. It could be any kind of surface.
For collision detection, it is of great significance whether the object is convex or concave, in that most commonly used collision detection algorithms operate only on convex objects. It sounds though like you're trying to do per-triangle collision detection, in which case it's not as relevant.
Quote:
 Basically, I am trying to find if any of the points of the mesh would collide with a face of the mesh. Each of the points has some velocity vector, so each triangle of the mesh is also moving (because the points forming the triangle are moving).
I don't think per-vertex will work, as two triangles can collide without any of their vertices colliding with the face of the other. For this and other reasons, tri-tri intersection is usually handled using other methods.
Quote:
 So the triangles of the mesh are not rigid, they also deform as they move in time due to the motion of the points.
When I think 'deform' I think of the mesh actually changing shape. But it sounds like you just mean the mesh as a whole is undergoing linear motion. Can you clarify?

well see, as such there has to be a) triangle vertex collision
b) edge edge collision. If two triangles already intersect at some time t, that means either :
a) a vertex of one triangle has collided with the other triangle
b) an edge of one triangle should have collided with one edge of the other triangle
before that time t( say t-deltaT). I am assuming that the triangle is "solid".

Well yes the whole mesh is moving. So the geometry of the mesh is changing, along with the shapes of the triangles too. Look at it this way, if each vertex has moved for time t, so if you form the triangles using the same connectivity as before, you get different shaped triangles. I hope I am making sense. It's just that during this motion, there are collisions. So I am trying to detect those.

##### Share on other sites
Well, I probably can't help much, because I'm a bit confused :-| An object does not necessarily change shape simply because it's moving, so I still don't know what you mean by 'the geometry of the mesh is changing'. Its position and orientation may change, but unless you are actively deforming the mesh, the 'shape' should not change.

If you're really talking about collision detection between moving, deforming meshes, that's a complex problem. If you're talking about two rigid bodies undergoing angular and linear motion, that's a complex problem. If you're talking about two rigid bodies undergoing linear motion only, with angular motion assumed to be constant over the time step, that can still be difficult but is well-researched and there are many standard algorithms that address it. The last case is the way collision detection is done in the vast majority of games today.

Anyway, sorry if I'm not getting what you're trying to communicate...

##### Share on other sites
hey sorry if I am not clear. But from the understanding you have of my problem, can you recommend any papers? I am not sure which one to start reading.

Thanks!

##### Share on other sites
I'm sure there are papers on mesh-mesh collision, but I can't think of particular ones off the top of my head. There are several good articles on intersection in the documentation section at geometrictools.com. If you can get your hands on a book or two, Eberly's "3D Game Engine Design", Christer Ericson's book, and Gino van den Bergen's book are all good places to look.

##### Share on other sites
You seem to know your math, so I recomend Gino van den Bergen papers on GJK, in particular "A Fast and Robust GJK Implementation for Collision Detection of Convex Objects" and "Ray Casting against General Convex Objects with Application to Continuous Collision Detection.".

GJK is a collision detection algorithm for convex shapes, in your case, you could use each separate triangle of a concave mesh as a distinct "convex object", that will probably tax performance, but you could just group triangles that form convex shapes, and do the tests on said groups.

The hard part of the GJK algorithm is lies in the Johnson distance algorithm, and look out for floating point error.

1. 1
Rutin
42
2. 2
3. 3
4. 4
5. 5

• 9
• 27
• 20
• 14
• 14
• ### Forum Statistics

• Total Topics
633387
• Total Posts
3011607
• ### Who's Online (See full list)

There are no registered users currently online

×