RE: [Algorithms] portal engines in outdoor environments

[John R. <jra...@ve...>]

>>What about RAM requirements for this pre-computed list?

Oh, it's not really that bad.  You just keep a bitstream, where each bit
represents a 'node'.  Each node has a 'node-id'.  When you go through your
rendering pipeline, each time you hit a node you just test the node_id bit.
Pretty much the same way Quake does it.  It's not that much memory really,
and you can always tweak your grid size.  What you are looking for is gross
culling anyway.  If you've got a big mountain in front of you, no sense in
drawing all the crap behind it.  That sort of thing.


>>And of course there is the inevitable question of how you compute what is
visible to what node.  I'd assume its done as a pre-process?

Yes.  In a previous engine what I did was stick a camera at a bunch of
places inside the grid that would represent "a guy standing here", and then
spun the camera around in all directions, rendering the entire world into a
span-buffer.  I then queried the span buffer for which *individual polygons*
could be seen.  For this new engine I have an insanely fast ray-tracer.
What I intend to due is just cast rays out from the camera position to the
vertex of every polygon inside the nodes I am testing against.  I'm pretty
sure this will work with no holes.  If I get some holes, I'll just do some
more samples until they go away.  I don't think this is going to take that
long to build either, because as soon as any ray hits, then that node is
visible.

My raytracer is extremely fast (because this is a massively multiplayer
online game which is supposed to fit hundreds of people in a single
environment firing weapons!).  I wrote a class I called 'cyclops' which
would generate 256 ray trace tasks every single frame out of the eyeballs of
a character I moved around the environment.  When the raytrace task would
complete I would highlight the polygon in the world that it hit and draw a
ray from his eyes to the hit location.  I set the raytracer up to 2
kilometers range on a terrain of about 100k polygons.  On this terrain I had
dozens of very high polygon density buildings, each in their own co-ordinate
space, including a two tiled polygon bridges each spanning about 500 meters.
It was able to compute the solution set with virtually no noticable
peformance hit.  The way my raytracer and all collision detection routines
work is by creating a circular cache of polygons which are being hit tested.
The faces in the cache have all kinds of pre-computed information to allow
for very high speed hit testing.

> And do you do
a full 3D solution with volumes, etc. or a 2.5D type of thing?

2 1/2 D.  My game does have some low flying aircraft, but once you are up in
the air you can pretty much see everything and LOD is your only hope there.

John