 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
OK, so here's a question.
I have a particle system that implements RK4 integration. It works
great. However... for each step, it involves computing the force acting
on a particle several times. That's fine if the force is an invariant
function of the particle's position and/or velocity (and possibly time).
But what do you do if the forces acting on a particle depend on the
positions of the other particles? o_O
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> But what do you do if the forces acting on a particle depend on the
> positions of the other particles? o_O
The fact that you are even asking that question makes me think you are
implementing RK4 incorrectly. The whole point of RK4 is that it gives more
accurate results when the forces depend on positions of other particles (eg
springs, collisions etc).
I suspect you are trying to apply the whole RK4 algorithm to one particle,
then the next, etc. This is wrong.
You need to store the positions and velocities of all the particles together
in one "state" object. Then you apply each step of RK4 on the whole state
at once. If you need the positions of other particles when calculating the
force, then of course you have all the position and velocity information
available in the state local to the current RK4 step.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> The fact that you are even asking that question makes me think you are
> implementing RK4 incorrectly.
Well, considering I have no clue why RK4 even works in the first place,
that's hardly surprising. ;-)
> The whole point of RK4 is that it gives
> more accurate results when the forces depend on positions of other
> particles (eg springs, collisions etc).
Really? I was under the impression that RK4 works just like other
methods, but just gives superior numerical accuracy.
> I suspect you are trying to apply the whole RK4 algorithm to one
> particle, then the next, etc. This is wrong.
It works fine if you only *have* one particle. ;-)
Actually, the simulation I'm about to run only consists of one particle.
But in future I'd like to handle more.
Currently my code is structured the way you indicate. (Heck, you can go
*read* it if you like... it's in the other NG.) But that doesn't allow
more complex systems.
> You need to store the positions and velocities of all the particles
> together in one "state" object. Then you apply each step of RK4 on the
> whole state at once. If you need the positions of other particles when
> calculating the force, then of course you have all the position and
> velocity information available in the state local to the current RK4 step.
Right. So just make all functions apply to the entire system at once. I
think I can do that...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> OK, so here's a question.
>
> I have a particle system that implements RK4 integration. It works
> great. However... for each step, it involves computing the force acting
> on a particle several times. That's fine if the force is an invariant
> function of the particle's position and/or velocity (and possibly time).
> But what do you do if the forces acting on a particle depend on the
> positions of the other particles? o_O
If you have a natural fear of O(N^2) problems, then I have some bad news
for you.
To accurately calculate the current force on each particle in a system,
you have to match up every possible pair of particles, all (n^2-n)/2 of
such pairs, and calculate the force that each of the particles in the
pair exerts on the other (generally equal and opposite, according to Mr.
Newton, so there is only one force calculation for each pair).
Try to get n as low as possible.
Regards,
John
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
John VanSickle wrote:
> If you have a natural fear of O(N^2) problems, then I have some bad news
> for you.
>
> Try to get n as low as possible.
I was thinking maybe 8 or so?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
John VanSickle <evi### [at] hotmail com> wrote:
> If you have a natural fear of O(N^2) problems, then I have some bad news
> for you.
>
> To accurately calculate the current force on each particle in a system,
> you have to match up every possible pair of particles, all (n^2-n)/2 of
> such pairs, and calculate the force that each of the particles in the
> pair exerts on the other (generally equal and opposite, according to Mr.
> Newton, so there is only one force calculation for each pair).
In all fairness, there are better methods. Think of dividing all the particles
up into an octree. A whole group of particles at a distance can be lumped into
one mass. I guess O(N logN) algorithms like this are as revolutionary as the
FFT. Of course I'm just regurgitating what's on Wikipedia and haven't actually
done any of this, but it's interesting to think about--and fascinating to watch.
(See links below)
- Ricky
http://en.wikipedia.org/wiki/Barnes-Hut_simulation
http://en.wikipedia.org/wiki/Fast_Multipole_Method
http://www.astro.ex.ac.uk/people/mbate/Animations/
http://www.cita.utoronto.ca/~dubinski/nbody/
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
triple_r <nomail@nomail> wrote:
> In all fairness, there are better methods. Think of dividing all the particles
> up into an octree. A whole group of particles at a distance can be lumped into
> one mass.
But you have to calculate the center of mass of the whole group, and
since each element of the group can change independently of the others,
that would mean you have to re-calculate this center of mass each time
anything changes.
Also another problem is that groups don't stay the same. If a particle
not belonging to the group enters the "inside" of the group, it cannot
be calculated anymore against that group as if it was just one single
mass located at the center of mass of the group.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> But you have to calculate the center of mass of the whole group, and
> since each element of the group can change independently of the others,
> that would mean you have to re-calculate this center of mass each time
> anything changes.
That's true. I think you're probably still saving yourself work though.
Compute that center of mass once and use it many times, verses computer
many object-object interactions many times over.
It depends on what you're simulating of course, but I would think there
are probably also situations were you can just disregard really distant
particles.
> Also another problem is that groups don't stay the same. If a particle
> not belonging to the group enters the "inside" of the group, it cannot
> be calculated anymore against that group as if it was just one single
> mass located at the center of mass of the group.
Isn't this just the "normal" problem of performing space partitioning
with moving objects?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> Isn't this just the "normal" problem of performing space partitioning
> with moving objects?
Which is a very hard problem. Why do you think scenery is always static
in all games?
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Isn't this just the "normal" problem of performing space partitioning
>> with moving objects?
>
> Which is a very hard problem. Why do you think scenery is always static
> in all games?
Oh, OK. I had assumed that this was a "solved" problem, since it occurs
any time you want to animate multiple moving objects...
I also assumed that scenery is always static in games so that you can
precompute light maps, occlusion data, and other stuff that makes it
possible to draw a landscape made up of a trillian polygons without
slowing everything to a crawl... As you probably know, I don't "do" this
for a living. ;-)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> I also assumed that scenery is always static in games so that you can
> precompute light maps
Actually nowadays games tend to use less and less precomputed light maps
and more real-time lighting. (This means that many games do not have anymore
that "radiosity" look to them, but that's usually compensated by having
fill lights and other techniques.)
But certainly at least some modern games still use them.
> occlusion data, and other stuff that makes it
> possible to draw a landscape made up of a trillian polygons without
> slowing everything to a crawl...
One feature which requires spatial partitioning is also the physics
engine. (After all, you only have less than 16 ms per frame to calculate
the physics of the entire level.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp <war### [at] tagpovrayorg> wrote:
> But you have to calculate the center of mass of the whole group, and
> since each element of the group can change independently of the others,
> that would mean you have to re-calculate this center of mass each time
> anything changes.
That is certainly the case, but even 100*(n log n) is still much smaller than
n^2 for large n. And can't you just do this hierarchically anyway? At each
step calculate the tree structure, calculate the center of masses
hierarchically, sum forces, and integrate? Those steps all sound like O(n log
n), but that's still pretty good. Of course you'd update everything together
so you wouldn't have to recalculate more than once per time step.
> Also another problem is that groups don't stay the same. If a particle
> not belonging to the group enters the "inside" of the group, it cannot
> be calculated anymore against that group as if it was just one single
> mass located at the center of mass of the group.
That is very true, so you'd have to recalculate the tree for each step. Even if
it's slightly outside though, the center of mass approximation is not exact. I
guess the fast multipole method takes this a step further and you can get the
correct answer down to machine precision, but that's beyond me.
This page has a pretty good introduction:
http://www.cs.berkeley.edu/~demmel/cs267/lecture26/lecture26.html
- Ricky
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> I also assumed that scenery is always static in games so that you can
>> precompute light maps
>
> Actually nowadays games tend to use less and less precomputed light maps
> and more real-time lighting.
How is it possible to do that?
(I'm not denying that games do it - they obviously do - I'm curios as to
how it's possible to do this given that the GPU only knows about
polygons and texture mapping.)
>> occlusion data, and other stuff that makes it
>> possible to draw a landscape made up of a trillian polygons without
>> slowing everything to a crawl...
>
> One feature which requires spatial partitioning is also the physics
> engine.
...which is more or less what I'm trying to use RK4 for! :-}
(I imagine a game physics engine uses something a tad more sophisticated
than just moddling a few points and allowing arbitrary interactions though.)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
triple_r wrote:
> In all fairness, there are better methods. Think of dividing all the particles
> up into an octree. A whole group of particles at a distance can be lumped into
> one mass.
I was thinking, that sounds more like figuring out how galaxies
interact, given where all the stars are. Then I went to
> http://www.astro.ex.ac.uk/people/mbate/Animations/
The octree of which stars are in which galaxies can be presumed fairly
static, I think. Might not be appropriate where every object is moving
everywhere in the scene.
--
Darren New / San Diego, CA, USA (PST)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> >> I also assumed that scenery is always static in games so that you can
> >> precompute light maps
> >
> > Actually nowadays games tend to use less and less precomputed light maps
> > and more real-time lighting.
> How is it possible to do that?
> (I'm not denying that games do it - they obviously do - I'm curios as to
> how it's possible to do this given that the GPU only knows about
> polygons and texture mapping.)
The GPU also knows about vertex normals and can interpolate them and
calculate the lighting of the surface according to the normal. In a similar
way as POV-Ray does.
Nowadays you can even write a shader which calculates the lighting from
the normal vector and positions of light sources in special ways, if you
want.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> triple_r <nomail@nomail> wrote:
>> In all fairness, there are better methods. Think of dividing all the particles
>> up into an octree. A whole group of particles at a distance can be lumped into
>> one mass.
>
> But you have to calculate the center of mass of the whole group, and
> since each element of the group can change independently of the others,
> that would mean you have to re-calculate this center of mass each time
> anything changes.
>
> Also another problem is that groups don't stay the same. If a particle
> not belonging to the group enters the "inside" of the group, it cannot
> be calculated anymore against that group as if it was just one single
> mass located at the center of mass of the group.
The point that accuracy requires the O(n^2) solution was rather blithely
ignored, too.
If the forces involved follow the 1/(d^2) rule (such strange forces as,
oh, gravity), then the non-linearity causes the averaging to yield a
different total force than the sum of the forces exerted by the
different masses. For instance, if particle A is at distance x_a
(relative to the affected point), and particle B is at distance x_b
(likewise relative), then using an average yields a force of:
2/(x_a/2 + x_b/2)^2, whereas the actual force is
1/(x_a^2) + 1/(x_b^2) = (x_b*x_b)+(x_a*x_a))/(x_a^2 * x_b^2)
If x_a = 1 and x_b = 1.01, then the forces are:
2/( 1.005^2) = 2/1.010025 = 1.9801490062127175069924011781887
whereas the other sum is
2.0201/1.0201 = 1.9802960494069208901088128614842
and this is an application where an error of this magnitude most
certainly does make a difference.
Unless you just want to make pretty pictures.
Regards,
John
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> How is it possible to do that?
>
>> (I'm not denying that games do it - they obviously do - I'm curios as to
>> how it's possible to do this given that the GPU only knows about
>> polygons and texture mapping.)
>
> The GPU also knows about vertex normals and can interpolate them and
> calculate the lighting of the surface according to the normal. In a similar
> way as POV-Ray does.
>
> Nowadays you can even write a shader which calculates the lighting from
> the normal vector and positions of light sources in special ways, if you
> want.
I was more puzzled as to how you compute shadows.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> I was more puzzled as to how you compute shadows.
That's actually one of the limitation of lightmaps: You can create superb
shadows for *static* scenery, but you can't use them to calculate shadows
for moving objects. This ends up in the situation with most older 3D games
(and many of the modern ones as well) where you have great-looking shadows
for everything except moving objects.
There are two techniques to calculate shadows: Shadow volumes, which are
based on shadow polygons (used, for example, by Doom3 and games using the
same engine) and shadow mapping (used, for example, in the Splinter Cell
games).
Both have their advantages and disadvantages, which is why neither one
is overwhelmingly popular (although shadow mapping might be a bit more
popular because it's a bit easier to implement and has its own advantages).
http://en.wikipedia.org/wiki/Shadow_volume
http://en.wikipedia.org/wiki/Shadow_mapping
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> That's actually one of the limitation of lightmaps: You can create superb
> shadows for *static* scenery, but you can't use them to calculate shadows
> for moving objects.
Yep, it's true.
(Well, if you have an "almost" static scene, you could perhaps include
extra data for, say, when a door opens or something. I doubt it would be
very accurate.)
> There are two techniques to calculate shadows: Shadow volumes, which are
> based on shadow polygons (used, for example, by Doom3 and games using the
> same engine) and shadow mapping (used, for example, in the Splinter Cell
> games).
>
> Both have their advantages and disadvantages, which is why neither one
> is overwhelmingly popular (although shadow mapping might be a bit more
> popular because it's a bit easier to implement and has its own advantages).
>
> http://en.wikipedia.org/wiki/Shadow_volume
> http://en.wikipedia.org/wiki/Shadow_mapping
Mmm, interesting.
I'm surprised shadow volumes didn't occur to me before. The intro to HL1
features what I guess you could call a "light volume": a door opens and
a semitransparent object representing the light flooding in is revealed.
(This illusion is then nicely shattered by driving a truck through it
without altering the geometry! But hey, it probably required no
alteration to the Quake engine...)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> That's actually one of the limitation of lightmaps:
I thought it was pretty cool that (as I understand it), the Thief 3 game
actually forces you to mind your shadows. If you're hiding around a
corner and your shadow sticks out, the guard will notice you. At least,
that's my understanding. I don't have a machine equiped properly to play
it here.
--
Darren New / San Diego, CA, USA (PST)
Ever notice how people in a zombie movie never already know how to
kill zombies? Ask 100 random people in America how to kill someone
who has reanimated from the dead in a secret viral weapons lab,
and how many do you think already know you need a head-shot?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> > That's actually one of the limitation of lightmaps:
> I thought it was pretty cool that (as I understand it), the Thief 3 game
> actually forces you to mind your shadows. If you're hiding around a
> corner and your shadow sticks out, the guard will notice you. At least,
> that's my understanding. I don't have a machine equiped properly to play
> it here.
That's one problem I have noticed with new gaming technologies: Most of
them are put into games just for looks, but very seldom actually used
for gameplay.
For example Doom3 supports accurate shadows for all the objects. However,
it's a purely visual element and plays absolutely no role in the actual
gameplay.
I don't know if Thief3 uses shadows in the way you describe, but it would
be a rare exception.
(OTOH, one could argue that something which is rather heavy to calculate
and which can be turned off with a rendering quality settings shouldn't be
a relevant gameplay feature because when it's turned off then it makes
little sense.)
Another example is physics simulation: Most modern games use Havoc or
some other physics engine, and once again purely for visuals only. There
really aren't many games where the physics engine would actually be a
relevant part of the gameplay. For example, The Elder Scrolls 4: Oblivion
uses Havoc, but the physics engine is not used for *anything* related to
gameplay. It's a purely visual element.
Half-Life 2 and its sequels are somewhat of a borderline case. It does
use the physics engine for gameplay. However, most of the situations where
it's used could IMO very well be implemented without the physics engine.
For example, at some points you need to use the gravity gun to pull a
plug (in order to shut down a barrier). The physics engine is used for
this, but it could well be done without it (just move the plug towards
the gravity gun when the user aims properly and fires). So while the
physics engine is used, it's not used for anything that couldn't be done
without one.
At another point you need to balance a plank to the other side by
putting weights on that side (so that you can then run accross the
plank and jump over the wall). While the physics engine is also used
here, it could still very conceivably be done without one.
(HL2:Episode 2 has some impressively massive physics simulations at
some points, such as a collapsing bridge. However, these could also be
simply precalculated motion paths, and a physics engine would not really
be needed.)
OTOH, the physics engine *does* contribute visually a lot, so games
really are better with one. For example throwing a grenade near a pile
of boxes can be visually quite fun. Also ragdoll physics make falling
enemies more realistic in all kinds of terrain, something which is very
difficult to do with precalculated motion paths.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> That's one problem I have noticed with new gaming technologies: Most of
> them are put into games just for looks, but very seldom actually used
> for gameplay.
Yeah. Eyecandy seems to be the way to go these days.
> I don't know if Thief3 uses shadows in the way you describe, but it would
> be a rare exception.
Farcry uses (what appears to me to be) a fairly sophisticated foliage
rendering system, and sure enough much of the game revolves around
sneaking through the undergrowth trying to avoid being seen. (I have no
idea to what extent the enemeis "see" like a human does.)
> (OTOH, one could argue that something which is rather heavy to calculate
> and which can be turned off with a rendering quality settings shouldn't be
> a relevant gameplay feature because when it's turned off then it makes
> little sense.)
When I played in one CSS match, the server operator demanded that all
players have their game set to DirectX 9 only, to avoid things like
people not being "properly blinded" by flash grenades. (At least, that
was their excuse. I'm not sure if it's really true...)
> (HL2:Episode 2 has some impressively massive physics simulations at
> some points, such as a collapsing bridge. However, these could also be
> simply precalculated motion paths, and a physics engine would not really
> be needed.)
I was under the impression that those really big scenes *are*
precalculated...
> OTOH, the physics engine *does* contribute visually a lot, so games
> really are better with one. For example throwing a grenade near a pile
> of boxes can be visually quite fun. Also ragdoll physics make falling
> enemies more realistic in all kinds of terrain, something which is very
> difficult to do with precalculated motion paths.
I guess you're probably the best person to ask about this Warp... How
"hard" is it to build a working game physics engine? I mean, how easy is
it to get good framerates? What other problems are involved?
(One thing I notice about all the Steam-powered games is that
slow-moving objects resting on surfaces sometimes seem to pathologically
jiggle around apparently without dissapating energy. Which, obviously,
looks a little weird...)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> I don't know if Thief3 uses shadows in the way you describe, but it would
> be a rare exception.
Given it's a sneaker, and given that doing things like leaving doors
open behind you can get you caught, and making too much noise can get
you caught, it seems reasonable they'd put that much effort into it. I
wouldn't think it would be all that much more difficult to have the NPCs
react to seeing shadows than to the player himself. Especially since
they only seem to react to the player in the other games. (I.e., make a
noise, get caught, even if you're standing near others arguing loudly
next to a pneumatic hammer.)
> (OTOH, one could argue that something which is rather heavy to calculate
> and which can be turned off with a rendering quality settings shouldn't be
> a relevant gameplay feature because when it's turned off then it makes
> little sense.)
I don't think you can turn it off. The game needs "pixel shader 3" and
won't run on my "pixel shader 1" cards. Not sure (don't really care)
what the differences are.
> For example, at some points you need to use the gravity gun to pull a
Altho if you watch the speed-runs, it's clear the use of the physics
engines make it possible to do things you wouldn't expect otherwise.
Like shoot the lever in the tower that holds up the giant logs that
break the doors down. Or maybe he's shooting the rope. (Took me a couple
viewings to figure out what he was doing there.)
One of the things in Black&White was the desire to make the physics good
enough that anything you could do for real you could do in the game. You
could, in theory, create a ball of water, use it to focus the sun on
some trees, light them on fire, set a boulder in the fire until it's
hot, and throw the bolder into another forest to light *that* on fire.
> Also ragdoll physics make falling
> enemies more realistic in all kinds of terrain,
But nowhere near as fun as watching Jumpman bounce on the way down. ;-)
--
Darren New / San Diego, CA, USA (PST)
Ever notice how people in a zombie movie never already know how to
kill zombies? Ask 100 random people in America how to kill someone
who has reanimated from the dead in a secret viral weapons lab,
and how many do you think already know you need a head-shot?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Mon, 04 Aug 2008 18:45:51 +0200, Warp <war### [at] tagpovrayorg> wrote:
> (OTOH, one could argue that something which is rather heavy to
> calculate and which can be turned off with a rendering quality
> settings shouldn't be a relevant gameplay feature because when
> it's turned off then it makes little sense.)
I remember that in X-Wing the trench run became a lot easier if you
lowered the detail setting, thus removing most of the obstacles in the
trench.
--
FE
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
