POV-Ray : Newsgroups : povray.binaries.animations : An old one. Filling a container. Server Time
19 Jul 2024 21:29:01 EDT (-0400)
  An old one. Filling a container. (Message 6 to 15 of 15)  
<<< Previous 5 Messages Goto Initial 10 Messages
From: Slime
Subject: Re: An old one. Filling a container.
Date: 21 Jul 2002 18:46:38
Message: <3d3b39ce@news.povray.org>
> 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

From: JRG
Subject: Re: An old one. Filling a container.
Date: 21 Jul 2002 19:25:21
Message: <3d3b42e1$1@news.povray.org>
"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

From: Slime
Subject: Re: An old one. Filling a container.
Date: 21 Jul 2002 21:27:17
Message: <3d3b5f75@news.povray.org>
> 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

From: Christoph Hormann
Subject: Re: An old one. Filling a container.
Date: 22 Jul 2002 03:36:16
Message: <3D3BB5F0.71E35DBC@gmx.de>
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

From: JRG
Subject: Re: An old one. Filling a container.
Date: 22 Jul 2002 15:15:34
Message: <3d3c59d6@news.povray.org>
"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

From: Christoph Hormann
Subject: Re: An old one. Filling a container.
Date: 22 Jul 2002 15:39:15
Message: <3D3C5F62.28B7461@gmx.de>
JRG wrote:
> 
> 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... :-)
> 
> [...]
> 
> 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.

Well actually an acceleration is force divided by mass.

Numerical calculus will surely be very useful (i heard a lecture on that
matter last term too), but it won't help without some mechanics of course.
;-)

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

From: JRG
Subject: Re: An old one. Filling a container.
Date: 22 Jul 2002 16:31:20
Message: <3d3c6b98@news.povray.org>
"Christoph Hormann" wrote:
>
>
> JRG wrote:
> >
> > 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... :-)
> >
> > [...]
> >
> > 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.
>
> Well actually an acceleration is force divided by mass.

Of course :) I just meant the only force I took into account is weight.

> Numerical calculus will surely be very useful (i heard a lecture on that
> matter last term too), but it won't help without some mechanics of course.
> ;-)

Hehe, that's for sure. Fortunately I don't lack physics notions, just quite a bit of
programming experience.


--
Jonathan.


Post a reply to this message

From: JRG
Subject: Re: An old one. Filling a container.
Date: 22 Jul 2002 16:33:36
Message: <3d3c6c20$1@news.povray.org>
"Slime" wrote:
> 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?

Sure it did. It sounds very interesting.


> 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.)

Hehe, must be real fun... :-)

--
Jonathan.


Post a reply to this message

From: Apache
Subject: Re: An old one. Filling a container.
Date: 22 Jul 2002 19:09:20
Message: <3d3c90a0$1@news.povray.org>
> 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... :-)

You don't need an exam Just surf the web looking for 'Runge Kutta' pdf
files, and in a few days you'll have it implemented nicely :)


Post a reply to this message

From: Apache
Subject: Re: An old one. Filling a container.
Date: 22 Jul 2002 19:10:55
Message: <3d3c90ff@news.povray.org>
If you divide the space where the total of the balls are in smaller parts
you'll be able to increase the speed drastically. That way you'll be able to
do the same thing with 100.000 balls at a very nice speed!


Post a reply to this message

<<< Previous 5 Messages Goto Initial 10 Messages

Copyright 2003-2023 Persistence of Vision Raytracer Pty. Ltd.