I just revisited the *balls filling a container* simulation to test my new
programming skill (hehe just passed my C exam).
While it's not perfect (some balls clearly intersect) it does the job. The program
took ~20 min to calculate 800 frames (30 iterations per frame, 400 balls and ~10
millions collisions). Then each frame took about 9 sec to render with POV.

http://digilander.libero.it/jrgpov/anim/palline.avi (2.7 MB divx 5).

--
Jonathan.

Post a reply to this message

JRG wrote:
> 
> I just revisited the *balls filling a container* simulation to test my new
> programming skill (hehe just passed my C exam).
> While it's not perfect (some balls clearly intersect) it does the job. The program
> took ~20 min to calculate 800 frames (30 iterations per frame, 400 balls and ~10
> millions collisions). Then each frame took about 9 sec to render with POV.

Nice, could you have a few more words on the algorithm used? How do you
handle multiple simultaneous collisions of one ball?

Christoph

-- 
POV-Ray tutorials, IsoWood include,                 
TransSkin and more: http://www.tu-bs.de/~y0013390/  
Last updated 15 Jul. 2002 _____./\/^>_*_<^\/\.______

Post a reply to this message

I've done this before, without intersections, but 20 minutes for 800 frames
* 30 iterations is very impressive. My algorithm takes about 30 seconds per
frame with *one* iteration, though that iteration catches every intersection
and handles it correctly.

 - Slime
[ http://www.slimeland.com/ ]

Post a reply to this message

"Christoph Hormann" wrote:
> Nice, could you have a few more words on the algorithm used? How do you
> handle multiple simultaneous collisions of one ball?

I have to say that the real fun was to handle the vector structs and functions... the
algorithm itself (which I shamelessly copied from my previous POV coded version) is
rather banal. A simple and not too optimised O(N^2) algorithm:

1) For frame = 1 to final_frame.
1.1) For iteration = 1 to num_of_iterations.
1.1.1) For ball = 1 to balls (frame).
1.1.1.1) Update positions and velocities.
1.1.1.2) Check collisions with walls and floor.
1.1.1.3) For other_ball = ball +1 to balls (frame)
1.1.1.3.1) Check collision with other_ball.

That's it. As you can see, I do not handle simutaneous collisions at all. One ball
can collide with another one. After that (point 1.1.1.3.1) its velocity gets updated.
Then it can collide with another ball during the same iteration. The new collision is
treated just as the other one, but with the updated velocity vector.

The main problem is to handle the balls staying one on each other. They rather tend
to *sink*, because the top balls tend to go down for the gravity acceleration while
those on the bottom of the container cannot sink anymore. I've used some trick to
avoid this: for example after a collision loop I save the mean of the distances (a
vector) between the ball considered and those which it collided with, and do not
consider the component of the acceleration along that vector during the next
iteration. This trick helped a lot but it's still not enough.
Any idea? I can post any code you want, but it's pretty ugly :)


--
Jonathan.

Post a reply to this message

"Slime" wrote:
> I've done this before, without intersections, but 20 minutes for 800 frames
> * 30 iterations is very impressive. My algorithm takes about 30 seconds per
> frame with *one* iteration, though that iteration catches every intersection
> and handles it correctly.

Ouch... the 10 iterations version (which looked pretty much the same...) took 409
sec... (debug not optimised version compiled with Visual Studio) so about half a
second per frame (actually the first hundreds frames get calculated in a
*phhheeeww*).
Anyway my algorithm cannot prevent *every* intersection right now, so it would be
great if you could give me some tips about the one you used. BTW I couldn't enjoy
your anim... just  a single still boring frame...who knows why.


--
Jonathan.

Post a reply to this message

> Ouch... the 10 iterations version (which looked pretty much the same...)
took 409
> sec... (debug not optimised version compiled with Visual Studio) so about
half a
> second per frame (actually the first hundreds frames get calculated in a
> *phhheeeww*).
> Anyway my algorithm cannot prevent *every* intersection right now, so it
would be
> great if you could give me some tips about the one you used. BTW I
couldn't enjoy
> your anim... just  a single still boring frame...who knows why.

Ooooh, you wrote this in C++? No wonder it's so fast. Mine's in POV-SDL =)
mainly so I can use the trace() function.

The algorithm basically works like this, for each iteration:

1. find every possible collision that will occur during this iteration
2. take the first collision and react to it, advancing all the balls the
amount of time that has passed
3. repeat until there are no more collisions during this iteration

Now, it doesn't work exactly like that; if it did, it'd be about 10 times as
slow. I've optimized it in various ways, but that's the gist of it. (the
main optimization is only checking for collisions involving balls that have
had collisions earlier during the current iteration, or which *will* have a
collision sometime during the iteration. That is, if a ball is found to have
no collisions during the iteration, ignore it in subsequent loops until the
next iteration.) Hard to explain, as you can see.

 - Slime
[ http://www.slimeland.com/ ]

Post a reply to this message

"Slime" wrote:
> Ooooh, you wrote this in C++? No wonder it's so fast. Mine's in POV-SDL =)
> mainly so I can use the trace() function.

Yeah, no in C, but hey I told you that :). The POV version was basically the same
thing and, according to my previous post, the last frames took about 9 sec to parse
(200 balls, 10 iterations per frame).

> The algorithm basically works like this, for each iteration:
>
> 1. find every possible collision that will occur during this iteration
> 2. take the first collision and react to it, advancing all the balls the
> amount of time that has passed
> 3. repeat until there are no more collisions during this iteration
>
> Now, it doesn't work exactly like that; if it did, it'd be about 10 times as
> slow. I've optimized it in various ways, but that's the gist of it. (the
> main optimization is only checking for collisions involving balls that have
> had collisions earlier during the current iteration, or which *will* have a
> collision sometime during the iteration. That is, if a ball is found to have
> no collisions during the iteration, ignore it in subsequent loops until the
> next iteration.) Hard to explain, as you can see.

I see. What I don't understand is how this prevents any intersection to happen. I
mean: a collision happens when the distance between two balls (their centres) is
smaller than the diameter of the balls. Now what I do is to update their velocity
vectors accordingly, but their positions don't get touched. That's why intersection
is still possible in very specific cases. Now, do you *fix* the position after a
collision has been detected?

I would like to see your algorithm used to fill up a container just like this, for
comparison :-)


--
Jonathan.

Post a reply to this message

> I see. What I don't understand is how this prevents any intersection to
happen. I
> mean: a collision happens when the distance between two balls (their
centres) is
> smaller than the diameter of the balls. Now what I do is to update their
velocity
> vectors accordingly, but their positions don't get touched. That's why
intersection
> is still possible in very specific cases. Now, do you *fix* the position
after a
> collision has been detected?

Yes. Let's say I have a system with two balls. Imagine this now: One ball is
at (0,0) and is heading towards (1,1). The other ball is at (1,0) and
heading towards (0,1). Assume their radii are extremely close to zero.

They're going to bounce off each other at time=0.5 (assuming time=1 is the
end of the iteration, when they reach their destinations).

I detect the collision at t=.5. I then figure out their new velocities. (In
this case, their velocities will simply be swapped, I believe. Or something
like that. Let's say for simplicity that they swap their velocities.)

Then I place the balls at (their current starting position) + (.5*(their old
velocity)) - (.5*(their new velocity))

Their new position is at (1,0) and (0,0), respectively. In this example,
they happen to have swapped starting positions.

Now that I've taken care of that intersection, I ignore any intersections
that occur at t <= 0.5. That way I won't detect their collision again. And
at the end of the iteration, I just add each balls' velocity to it's
position, so the first ball ends up at (0,1) and the second at (1,1).

Did that make sense?

Before long, I'll work on the code and make a new example for you. But not
now... Warcraft III takes priority =) (two levels left! I think.)

 - Slime
[ http://www.slimeland.com/ ]

Post a reply to this message

JRG wrote:
> 
> [...]
> 
> That's it. As you can see, I do not handle simutaneous collisions at all. One ball
> can collide with another one. After that (point 1.1.1.3.1) its velocity gets
updated.
> Then it can collide with another ball during the same iteration. The new collision
is
> treated just as the other one, but with the updated velocity vector.

I see.  By updating velocities you probably mean mirroring the velocities
at the normal vector (minus damping factor). 

> 
> The main problem is to handle the balls staying one on each other. They rather tend
> to *sink*, because the top balls tend to go down for the gravity acceleration while
> those on the bottom of the container cannot sink anymore. I've used some trick to
> avoid this: for example after a collision loop I save the mean of the distances (a
> vector) between the ball considered and those which it collided with, and do not
> consider the component of the acceleration along that vector during the next
> iteration. This trick helped a lot but it's still not enough.
> Any idea? I can post any code you want, but it's pretty ugly :)

You probably should have a look at some literature about numerical
integration.  Totally avoiding balls overlapping isn't possible with most
methods, but it is not necessary.  You just have to make sure that when
balls overlap there is a force driving them away from each other.

Christoph

-- 
POV-Ray tutorials, IsoWood include,                 
TransSkin and more: http://www.tu-bs.de/~y0013390/  
Last updated 15 Jul. 2002 _____./\/^>_*_<^\/\.______

Post a reply to this message

"Christoph Hormann" wrote:
>
>
> JRG wrote:
> >
> > [...]
> >
> > That's it. As you can see, I do not handle simutaneous collisions at all. One
ball
> > can collide with another one. After that (point 1.1.1.3.1) its velocity gets
updated.
> > Then it can collide with another ball during the same iteration. The new
collision is
> > treated just as the other one, but with the updated velocity vector.
>
> I see.  By updating velocities you probably mean mirroring the velocities
> at the normal vector (minus damping factor).

Exactly.

> >
> > The main problem is to handle the balls staying one on each other. They rather
tend
> > to *sink*, because the top balls tend to go down for the gravity acceleration
while
> > those on the bottom of the container cannot sink anymore. I've used some trick to
> > avoid this: for example after a collision loop I save the mean of the distances
(a
> > vector) between the ball considered and those which it collided with, and do not
> > consider the component of the acceleration along that vector during the next
> > iteration. This trick helped a lot but it's still not enough.
> > Any idea? I can post any code you want, but it's pretty ugly :)
>
> You probably should have a look at some literature about numerical
> integration.

Actually I've just studied numerical calculus at University... but didn't take the
exam yet (I'll probably do it in september) so I still have to read through my papers
before doing something useful with the new notions I have... :-)

> Totally avoiding balls overlapping isn't possible with most
> methods, but it is not necessary.  You just have to make sure that when
> balls overlap there is a force driving them away from each other.

Yeah, that's the other way round :) I didn't take into account *forces*, just gravity
acceleration and collisions. Anyway I'll look into it deeplier as soon as I have my
calculus exam done.

Cheers,

--
Jonathan.

Post a reply to this message