Re: PVS generation

Steve Larsen (
Mon, 17 Jun 1996 12:49:52 -0600

Message-Id: <>
From: (Steve Larsen)
Subject: Re: PVS generation
Date: Mon, 17 Jun 1996 12:49:52 -0600

> > 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?

One of the methods Teller's thesis discusses regarding portal traversal is
using groups of constrained stabbing lines to derive the antipenumbra of a
line/surface light source. By intersecting these stabbing lines with other
surfaces that contain portals, you can define a "visible area" on that
surface. If a portal (or part of one) is contained in that area, you can
add that portal to the sequence. However, finding these stabbing lines is
not a trivial process.

Now, I was thinking, what if you found stabbing lines that over-approximate
the antipenumbra, but were easier to determine. Or a single stabbing line
and then approximate the anti-penumbra using some heuristic. To be
blatantly honest with you, I have really thought about it too much. It
just seems like you could come up with a few ideas to try.

> > 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?

Yes: isothetic rectangle == rectangle with edges parallel to principal axes.

"Stabbing isothetic rectangles and boxes in O(n lg n) time"
M. Hohmeyer and S. Teller
Computational Geometry Theory and Applications 4 (1992) pp. 201-207

> > 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...

Yeah, I was thinking about this myself. Create an isothetic surface
on the "wall" that contains the actual portal. The only drawback that
I saw at a glance is that this exaggeration could potentially cause
a large increase in the PVS. But to be fair, which of these approximations
couldn't? Definitely worth some consideration.

> > 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 am not sure how "light" works. The lightmap generator I made will
consider the PVS before building a lightmap for a surface. Working with
the NATs was really not that big a deal, tho I must admit that I haven't
tried it yet on a slanted surface, so it might be broke as hell in that
case. ;)

> 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.

I don't think he is using stabbing lines in the strictest sense of the
word, but I'm sure he's using a very similar concept. It will be
interesting to see what he has done, if he releases the source.