Re: PVS generation

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

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

Steve Larsen explained:
>full portal based adjacency graph

A side note: this beastie is valuable for all those
considering writing a Bot. Precompute it, and use an
A*-like shortest path, or your Bot will not find its way
out of the bathroom with both hands and a ... map :-).

> simplified portal stabbing line

A stabbing line is a sightline intersecting all portals
in a sequence. I have yet to think my way through this.
Could you elaborate on the possible simplifications?

> a O(n*log(n)) method for portals comprised of isothetic
> rectangles

You are talking about the algorithm referenced on pp. 55-58
in the thesis? Or the TH92 reference? Hmm, my dictionaries
do not tell me what isothetic means... axial?

> this is great as long as all your doors are axial rectangles

Far out idea: approximate an arbitrarily oriented and shaped
portal by a bounding box of six axial portals. This will
increase the PVS in pathological cases, and increase the
number of portals, but if O(n^4) is the alternative...

> PVS-aware Lightmap generator

A radiosity based approach might well not be worth the
trouble of making it fit to NAT-grids, but at least it'd
be something John Carmack hasn't done (yet). Is "light"
actually a PVS aware raycaster? Sounds like a good idea,
but for PC editing you will want a raycaster that does
not require a PVS :-(.

I wonder if John Carmack is actually using a stabbing line
approach. The work log mentions portals, but no stabbing,
and no adjacency graph (hah - finally put this stuff to
some use, with good ol' grep). His Info(7) described a portal
graph used for Sealing. Info (5) mentions not retaining the
portal chain information. Hmmm.