Re: [Algorithms] Re: Portal VS BSP

[Alen L. <ale...@cr...>]

We used portal-walking based on a modified sorted edge rasterizer, called that
"advancing" sorted edge rasterizer. The idea is that if you do this (just for
example purposes):

1) add viewer's zone to list of current zones
2) for each zone in current zones add all occluders and portals to list of
active polygons
3) render all active occluders to z-buffer
4) check each of active portals against the z-buffer to see which would pass,
and whichever did pass, add their adjoining zone(s) to list of current zones
5) if there are new zones in list of current zones, go to (2).

Once you are finished with this, all the zones that were ever active should be
rendered.

Now, of course you don't want to do that with z-buffer for real. So we used a
sorted edge rasterizer (SER) and modified it so that it processed occluders
and portals together and automatically added adjoining zones when a visibile
portal is encountered, continuing where it stopped. Main characteristic of SER
is that its complexity is not dependent on Width x Height x Overdraw, as
z-buffer is, but roughly on NumOfEdges x AverageEdgeHeight x EdgeOverlap. And
it has high coherence so that the EdgeOverlap term can usually be ignored.
This way you do the calculations in image space, so you don't have the high
complexity you would get by clipping portals against each other, and you still
have much less workload than a naive z-buffer approach would have.

At the time we developed this, nice additional property was that you can even
calculate per-polygon visibility, not only per-zone. But as GPUs got faster,
it was not really used much.

Most obvious improvements that we couldn't really do at the time, due to our
visibility geometry being coupled with rendering geometry, would be to: a) use
lower resolution than screen and b) use simpler geometry for visibility than
for rendering.

Alen

----- Original Message -----
From: "Joe Ante" <jo...@li...>
To: <gda...@li...>
Sent: Monday, December 15, 2003 01:27
Subject: Re: [Algorithms] Re: Portal VS BSP


> Hi Alen,
>
> >True, true, it really does depend on your targets. PS2 is the border area -
> >we used dynamic visibility on Xbox without any problems.
> What kind of dynamic visibility testing algorithm are you using?
>
> Joe Ante
>
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: SF.net Giveback Program.
> Does SourceForge.net help you be more productive?  Does it
> help you create better code?  SHARE THE LOVE, and help us help
> YOU!  Click Here: http://sourceforge.net/donate/
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>