 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] dev null> 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
|
|
| |
| |
|
|
|
|
| |
