# How does an average Collision detection work?

This topic is 4907 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 think I have understood the basic difference between my probs and the way most collision detection algos work. In my case, assuming I have a collision between a triangle and a point, the triangle is getting deformed due to the motion. Hence there are additional constraint here. I think most of the collision detection algos assume that the triangle is moving with a velocity V, has the same shape, and collides with another triangle or point or some body moving with a different velocity. Am I correct in saying this? Can people just give the basic intro? Thanks!

##### Share on other sites
Hi,
your question is too general to be answered in one sentence. What is usually meant by "Collision Detection" is detecting whether or not an object "runs into" another object while moving in your world. So if your object is about to move from point A in space to point B, you search and test the vicinity of point B for objects you might have collided with. If so your object can't move from point A to B! If there's no collision detected you may move the object to B. The algorithm you use depends on what you want to achieve. You may consider your moving object as a sphere and test it against all object in the neighbourhood of your destination point (say boxes or other geometric objects). There are number of algorithms you can use, more or less precise..
But from what you're desciribing I thing you're tallking about deformation due to speed of your object. This has actually little to do with collison detection. First you must deform your object and then test for collision.
But you should give better explanation what you're after, because this is really too general question :)

Hope this help a little ;)
Cheers
Y.

##### Share on other sites
We were discussing this recently in your other thread. I think the problem may be that people are unsure of what you're trying to do. Building on yanco's post, I'll describe some different types of collision detection, and perhaps you can tell us which you're trying to implement.

1. Static

Given two objects and their current states (position and orientation), the objects are tested to see if they're intersecting. The test may be boolean only, or information about the intersection, such as penetration depth and direction, may be returned. This is very common.

2. Swept, linear only

The objects have a constant linear velocity over the timestep, and angular velocity is ignored. The objects are tested to see if they intersect during the timestep. Usually the first time of intersection, and perhaps contact information, is returned. Also very common.

3. Swept, linear and angular velocity

Like 2, except that angular velocity is considered. This is an area of research and up until recently at least has not commonly been implemented in games.

4. Deforming

All of the previous assume that the objects are rigid and do not change shape over the timestep. Finding the intersection of moving, deforming objects is a whole other subject and as far as I know is not at all common in typical game environments.
Quote:
 In my case, assuming I have a collision between a triangle and a point, the triangle is getting deformed due to the motion. Hence there are additional constraint here. I think most of the collision detection algos assume that the triangle is moving with a velocity V, has the same shape, and collides with another triangle or point or some body moving with a different velocity. Am I correct in saying this?
From this it sounds like your objects are deforming. The thing that throws me though is 'deformed due to the motion'. Perhaps you could explain exactly what you mean by that.

##### Share on other sites
hey guys,

Sorry if I was not clear. I think you are right. My kind of collision does not exist in gaming/has not been tried.

However, I have managed to get a few papers in which people are simulating cloth movement. The cloth is defined by a mesh of triangles and they collide with each other. Each of the triangle is deformable (the velocity is assigned to the vertices). And the equations I derived does match with theirs. They solve a cubic equation in time for the instant when the collision occurs. So I am fine there. But a new problem is how to solve the cubic equation in a robust manner. I have implemented the analytical solution using the cubic formula on math world, but it doesn't seem to be very robust (for some specific coefficients). Anyone have any ideas to solve that?

Oh Also, I need an efficient to do the search. I think the search can be similar to the ones used in gaming. Can anyone point to a simple and efficient search method. Right now I have implemented uniform subdivision in space. Was very easy to implement, not sure how effective.

Thanks!

##### Share on other sites
Ah, cloth - why didn't you say so! :-) What you've been saying becomes clear in that context.

I've only done static collision with cloth (verlet-style), so I don't have much to offer regarding your problem. You might consider retitling the thread, though, as the mention of cloth simulation might catch the attention of people with experience in that area.

• ### What is your GameDev Story?

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

• 13
• 9
• 9
• 34
• 16
• ### Forum Statistics

• Total Topics
634124
• Total Posts
3015659
×