Re: PVS generation

Bernd Kreimeier (Bernd.Kreimeier@NeRo.Uni-Bonn.DE)
Mon, 17 Jun 1996 11:23:52 +0200 (MET DST)

Date: Mon, 17 Jun 1996 11:23:52 +0200 (MET DST)
From: Bernd Kreimeier <Bernd.Kreimeier@NeRo.Uni-Bonn.DE>
Message-Id: <>
Subject: Re: PVS generation

Troy Stephens wrote:
>> beam tree suggestion
> I think the detail that I'm
> missing, though, is how the origin(s) for the beam
> tree(s) through a portal is/are selected.

Disclaimer: this is entirely my guess, it doesn't look
like Teller have tried something like this, and
we have to wait for "vis" to check what John Carmack
came up with.

A beam-tree like approach could work like this:

for each leaf ( == cell in Teller's description)
for each portal to adjacent leafs
for each portal in the adjacent leaf
create an intial view frustrum from both portals
while (beam tree not solid)
next leaf from BSP traversal
for each portal within leaf
if portal intersects beam tree
update beam tree
put leaf in PVS

The BSP traversal will of course clip subtrees against
the beam tree or the intial frustrum. The processing
is aborted as soon as the beam tree is solid. The
disadvantage of beam trees Abrash mentioned is that
performance is not level enough for realtime - this is
no problem here. I do not dare think about complexity,
though - depends on the relation between N_leafs and
N_portals in the adjacency graph, i.e. bounds on the
degree of the nodes, I guess.

To answer the question: "create an intial view frustrum"
could be anything. You might take each vertex of the
first portal, and two adjacent vertices in the portal
of the adjacent leaf, and create a clipping plane. Or
you might determine the center of both portals, which
will give you the overall direction, and use some bounding
rectangles that will enclose the minimal beam tree.

A side note: all this plane clipping stuff makes me wonder
how PVS calculation on a hardware accelerator like the
PowerVR might work... too bad that 3D accels aren't really
coprocessors that could be queried conveniently.

hope this helps