Message-Id: <199606111925.NAA00318@sal.cs.utah.edu>
From: larsen@sunset.cs.utah.edu (Steve Larsen)
To: quake-dev@gamers.org
Subject: Re: PVS generation
Date: Tue, 11 Jun 1996 13:25:50 -0600
>
>>How is it done
>
[snip, snip]
>Sampling on a grid is definitely not a good idea.
>Doing a simple raycasting from each center of
>a leaf might serve as a "fast vis" function.
>Clipping by distance is another idea that will not
>correctly determine a PVS, but will be fast. Any
>other ideas?
Agreed. A grid, and in particular choosing the "corners" or center of the
leaf, will fail very frequently. I have considered a few different
approaches, including (listed in order of complexity):
1. Above mentioned radial test.
2. Using full portal-based adjacency graph.
3. Using a distance constrained portal sequence. Step through the
portals adding only leaves within a certain radius from the
source leaf.
4. Using simplified portal stabbing line algorithm that over-
exagerates the PVS.
In addition, there are two additional possibilities I think are relevant.
Both correctly calculate the PVS, not approximate as above:
5. Seth Teller and Michael Hohmeyer have demonstrated a O(n*log(n)) method
for portals comprised of isothetic rectangles.
6. Many others (including Teller et al) have contributed algorithms to
compute stabbing lines for a collection of oriented polygons.
Most of these are in the O(n^4) range, but decrease as constraints
are applied.
(NOTE: n is number of edges in portal set for above).
Here is my take on these methods, YMMV.
1. This will work only in small, enclosed areas. Any large areas will be
rife with artifacts.
2. The full adjacency graph will probably wind up being near the entire
set of leaves for most levels. Very little would be gained over
the trivial accept method.
3. I believe this method has promise as a "quick and dirty" PVS process.
It will have artifacts as well as 1. However, since you are actually
following the portal graph, and hence rejecting many near but
non-visible leaves, you can extend the radius and decrease the
frequency of error. The calculations should be quite managable
on a PC, IMO.
4. Haven't really explored the possibilities here yet. This could work
pretty well, or could also wind up being close to 5, 6 in
complexity depending on what "simplified" methods could be
discovered.
5. This is great as long as all your doors are axial rectangles.
6. Full blown method. Will likely be VERY computationally expensive.
May not be feasible for use on a PC.
One nice thing about these PVS calculations is that they are perfectly
suited to parallelization. So, if you have access to an MP machine
you could greatly benefit.
My gut feeling is this for generating .bsp files:
BSP node generation: This will become a trivial step. Should be able
to get it down so that it is within 2-3 times as slow as
generating DOOM maps (which on any Pentium is most negligible,
so I guess it will be 1/2 to 1/3 negligible ;)
Lightmap generation: If you have a PVS set available (and a PVS aware
lightmap generator), you could probably do a pretty decent
lightmap in say twice as long as the BSP.
Visibility: Discussed above. I expect this to end up taking > 75%
of the time for full-blown level generations when all is said
and done.
These are my opinions/guesses, not fact. I could be way off on this.
I will not be responsible for lying to millions of people ;)
Steve