Re: [Algorithms] portal engines in outdoor environments

[Angel P. <ju...@bi...>]

> .. is a hopeless proposition, I think.  I'd just like you
> guys to check my reasoning before I give up.  Consider,
> for example, a building placed on a landscape.  The goal
> is to construct portals so that when you stand on one
> side of the building, you can't see the other.  If the
> player is constrained to stay on the ground, this is
> easy enough, it's really a 2d occlusion problem, and you
> need 8 portals (two * 4 faces of a square in 2d; two portals
> cuz you need one on each side of a face of the square,
> parrallel to that face) which splits the universe into 9
> zones (8 outside and one inside the occluding cube).
> 
> However, if we have a plain cube in 3d and the player can
> go anywhere around it, we need 48 portals !! (8 for each of
> the 6 faces on the cube).  Now if you have two cubes near
> eachother, you need massive numbers of portals, and they
> must all not intersect with eachother or other geometry.
> This quickly becomes unworkable.

Actually these will be just 12 portals - 4 on the ground plane,
4 on the roof plane and 4 vertical ones. And 6 cells.

The main problem with portalized outdoors is that a portal may be split
into many tiny pieces while it is traversed through the other portals.

Look at the first screenshot at
http://thegeleto.tripod.com/sshots/
and you'll see what I mean.

Consider this picture:
   __________________
  |                  |
  |   Portal A       |
  |                  x1__________________
  |                  |                  |
  |                  |   Portal B       |
  |   _______________|_____________     |
  |  |               |             |    |
  |  |           Portal C          |    |
  |  |               |             |    |
  |  |     Ca        |     Cb      |    |
  |  |               |             |    |
  |  |_______________|_____________|    |
  |                  |                  |
  |__________________x2_________________|

Portals A and B are two adjacent coplanar portals sharing same
edge (x1-x2). Portal C is behind these 2 portals and is split in 2
pieces - Ca and Cb.

The ordinary portal traversal algho will work like this:

-- Create the frustum for portal A.
-- Clip C to this frustum , crete a new frustum from the clipped portal
-- Recurse further through the new frustum
-- Create the frustum for portal B.
-- Clip C to this frustum , crete a new frustum
-- Recurse further through the new frustum

The key to fixing the problem with the many splits is an algho that will work
like this:
-- Create the frustum for portal A : Fa
-- Store the portal edge x1-x2 with the frustum Fa
-- Clip C to this frustum (Fa) , crete a new frustum from the clipped portal :Fac
-- Clip the stored in Fa edge x1-x2 to the new frustum (Fac) and store it in that
frustum. (when clipping the case when x1-x2 lies on a plane will be considered
as if it is in front of the plane )
-- DONT recurse further through the new frustum but rather store it
  inside C
-- Create the frustum for portal B : Fb
-- Store the portal edge x2-x1 with the frustum Fb
-- Clip C to this frustum (Fb) , crete a new frustum from the clipped portal :Fbc
 -- Clip the stored in Fb edge x2-x1 to the new frustum (Fbc) and store it in that
frustum. (when clipping the case when x2-x1 lies on a plane will be considered
as if it is in front of the plane )
-- Clip all edges stored in Fac(currently stored inside C) to Fbc and all edges
stored in Fbc to Fac (when clipping the case when an edge lies on a plane will
be considered as if it is BEHIND the plane!!! )
-- If there are no edges stored in Fac and Fbc (as is in this case because they
were clipped ) - try to merge Fac and Fbc (succesfully in this case) in one
frustum - Fc
-- Recurse further through Fc

While this algho is a lot more complicated it will decrease the portal splitting
in portalized outdoors quite a lot.
I have not tried it yet, and there probably will be many gotchas.

> I think something like a "real-time" occcluder (shadow volumes,
> etc.) is the only hope for outdoors.

You can use a structure of cells connected with occulders instead of portals.
As you traverse the cells you can put these occulders in a beam tree after
clipping them to that tree. To make things faster you can put inside the
beam tree only edges shared by 2 polygons one of which is backface culled
and the other isn't. At each cell the beam tree will be used to determine the
visible polygons. The process ends when there are no edges left in the beam
tree. It's a good optimization the remove the beam tree nodes that contain no
edges (after the clipping to a new occulder these edges were removed) when
possible (this will not be possible when both node->front and node->back
are not NULL). So if this optimization is used - the process will end when the
beam tree collapses (e.g. all nodes are deleted). This beam-tree approach
can be easily combined with conventional portals.
But this sounds too complicated to me and probably it won't be faster than the
above portal approach.

With both alghos you will have to deal with too many portals/occulders.


> --------------------------------------
> Charles Bloom           www.cbloom.com
> 
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list