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 = centerpoint1-centerpoint2 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 non-ending 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.
Have you tried the ‘distance’ function? and check for distance closer then X?
it check in a “spherical” manner.
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.
what is an original animation of objects in the scene? why and how do they move? what’s control their animation?
If you want something like physics sim then add something friction-like – decrease speed after collision. And you can add some random deviation to your vectors (small).
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 off-line. Change paths where you need, slow down – speed up some objects. This is not a real-time task. If it needs a minute do it a minute, or half-hour… who cares?
The problem is that in every frame some of them overlap. So I have no frame where nothing overlaps.
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?
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?
Yes they are. And the problem is that even in the first frame they collide.
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