View Full Version : Collision Detection Algorithm
cgneuling 04202012, 11:08 AM Hi! I have implemented a Collision Detection in Algorithm like the following principle: Every object got a sphere as bounding box and the bounding boxes are saved with the center point and radius. For every time stemp I want to look if there are any collisions and if so I will move the animation path so that they do not collide. So for every sphere I look if there is a collision and if so I translate it with the vector v = centerpoint1centerpoint2 and multiply it with the length so that they do not collide. This works for about 30 spheres really good, but I want to make it for 1000 spheres per time step, but there are situations whrere this simple algorithm do not comes to an end, because when I repeat the algorithm so long till there are no more collisions. But I am in a nonending loop. Are there any algorithm that translate sphere bounding boxes so that no one of them collides? If so are there program examples or are there any papers for it? In my situation there are collisions in every time step. So I have to move the spheres so that they do not collide any more. My actual algorithm works like that:
for every sphere: look for every sphere that is not the actual sphere if it collides with it> if so move it...at the end of this two loops look if there are still collisions > if so start the algorithm again.


stigatle
04202012, 12:00 PM
Have you tried the 'distance' function? and check for distance closer then X?
it check in a "spherical" manner.
cgneuling
04202012, 12:08 PM
When I am looking for collisions than I calculate the vector between the two center points of the two spheres and then I look if the length of this vector is smaller than the sum of their two radius. Do you mean that? And after that I move one sphere like this:
new_center_point = old_center_point + vector * new_length
whereas the new_length = (radius1 + radius2)  length;
but the problem is when they are for example in a line that one sphere will be moved left and right and left and right and so on. So I have a never ending loop.
If you want something like physics sim then add something frictionlike  decrease speed after collision. And you can add some random deviation to your vectors (small).
denisT
04202012, 12:52 PM
When I am looking for collisions than I calculate the vector between the two center points of the two spheres and then ...
what is an original animation of objects in the scene? why and how do they move? what's control their animation?
cgneuling
04202012, 01:17 PM
Their move is only controlled by the animation path...the position of the object center per time frame. So I want to make the collision detection per frame only on their current position. And then for the next frame so that their original object position is kind of an helper point.
cgneuling
04202012, 01:31 PM
The problem is that in every frame some of them overlap. So I have no frame where nothing overlaps.
denisT
04202012, 02:07 PM
Their move is only controlled by the animation path...the position of the object center per time frame. So I want to make the collision detection per frame only on their current position. And then for the next frame so that their original object position is kind of an helper point.
that means you have predefined animation and you can control (setup) it offline. Change paths where you need, slow down  speed up some objects. This is not a realtime task. If it needs a minute do it a minute, or halfhour... who cares? :)
cgneuling
04202012, 03:04 PM
yes but the problem is I don't know how to get away all collisions .
When I have a scene at just one time step, where 100 of my 1000 bounding boxes collide. How can I write an algorithm that get away all collisions?
Because it doesn't work if I look for every sphere if it collides with another and if so translate it in the direction of the vector between the two center points and so on. Because when I have for example 5 in a line. And 2 collides with 3. When I then move 3 away from 2 in the direction of the vector than it will collide with 4. and then if 4 collides with 3 than its possible that it is translated so that it collides again with 2 and then I am in an never ending loop. What can I do to fix that problem?
denisT
04202012, 03:32 PM
i don't think you have to move your objects from path. just speed them up or slow down along their paths to make them pass the point of possible intersection sooner or later to avoid a collision.
what is generating the paths of animation? are they splines?
cgneuling
04202012, 03:45 PM
Yes they are. And the problem is that even in the first frame they collide.
denisT
04202012, 03:47 PM
Yes they are. And the problem is that even in the first frame they collide.
do all objects have to start at the same time?
spider853
04202012, 04:54 PM
Try to instead moving the spheres at the boundings of the collision limit the movement to half or lower. (don't use percentage as you will never get to the boundings)
Iterate T times or untill there is no collision.
for example
r = 25.0
for i = 1 to selection.count do
(
for j = i+1 to selection.count do
(
Dif = selection[i].pos  selection[j].pos
if length(Dif) < r*2 then
(
DifVec = Normalize (selection[i].pos  selection[j].pos)
CenterVec = (selection[i].pos + selection[j].pos)/2.0
MoveBy = (r*2  length(Dif) )/2.0 + 0.01
if MoveBy > r/5 then
MoveBy = r/5
selection[i].pos += DifVec * MoveBy
selection[j].pos = DifVec * MoveBy
)
)
)
)
Something like this.. didn't try
this way the spheres inside will push slowly the spheres outside
or/and use a temporary holder for positions, and apply them after collision iteration
cgneuling
04202012, 05:49 PM
ok, but where should I start with this algorithm? Should I calculate the center of the scene and start with the sphere, which is nearest to the center or does it not matter where I start?
spider853
04202012, 06:00 PM
for this example doesn't matter
btw I made a test and for
r/2 I get 52 iteration and with r/1 58
if you want to use the density calculate the density of the sphere by suming the distance between spheres closer than r*2 for example.
then sort the sphere by 1/density descendent or just by density ascendent
and when you will collide the sorted spheres it will move from center out,
but here you see that you need 2 n*n passes
you can also use somehow density information to get the substeps... so where the density is higher you will want to go slower so you will not get jumpy movement forward and backward
...
you can also use grids with r*2 width, for quicker collision find
cgneuling
04222012, 02:50 PM
Hi!
It doesn't work. It doesn't comes to an end :(
My code is the following:
int Collision_Function_cf2(int t, const int object_number, int* object_field, , Point3 **animation_frames, float *radius)
{
int remember = 0;
Point3 current_vector;
Point3 current_vector1;
float vector_length;
Point3 vector_difference;
int current_index;
int index2;
for(int i = 0; i < object_number; i++)
{
current_index = object_field[i];
for(int j = i; j < object_number; j++)
{
index2 = object_field[j];
if(current_index != index2)
{
current_vector = animation_frames[index2][t]  animation_frames[current_index][t];
vector_length = sqrt((current_vector.x * current_vector.x) + (current_vector.y * current_vector.y) + (current_vector.z * current_vector.z));
if(vector_length < (radius[index2] + radius[current_index]))
{
current_vector1 = current_vector / vector_length;
current_vector = current_vector1;
vector_length = radius[index2] + radius[current_index]  vector_length;
//vector_length = vector_length + (0.05 * vector_length);
vector_length = (vector_length / 2) + 0.01;
if(vector_length > (radius[current_index] / 5))
{
vector_length = radius[current_index]/5;
}
animation_frames[current_index][t] = animation_frames[current_index][t] + (current_vector * vector_length);
animation_frames[index2][t] = animation_frames[index2][t] + (current_vector1* vector_length);
control_array[current_index][t] = 1;
control_array[index2][t] = 1;
}
}
}
}
for(int i = 0; i < object_number; i++)
{
current_index = object_field[i];
for(int k = i; k < object_anzahl; k++)
{
index2 = object_number[k];
if(index2 != current_index)
{
if(vector_length < (radius[index2] + radius[current_index]))
{
remember = 1;
}
}
}
}
return remember;
}
and then in my main program I call this function again if remember = 1.
CGTalk Moderation
04222012, 02:50 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.
vBulletin v3.0.5, Copyright ©20002015, Jelsoft Enterprises Ltd.