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