Visibility Lists

David Etherton (
Mon, 18 Mar 1996 09:11:28 +0800

Date: Mon, 18 Mar 1996 09:11:28 +0800
From: (David Etherton)
Message-Id: <9603181711.AA25455@fuzz.megatek>
Subject: Visibility Lists

When trying to determine which leaves are visible from a current
leaf, one looks at the vislist memory of the leaf data structure.
However, it's not clear to me which of the following two
formulas is correct:

int i; // leaf number to check
u_char *vp = start_of_vislist + leaf->vislist

if (vp[i>>3] & (1<<(i&7))) { puts("is visibile"); }

- or -

if (vp[i>>3] & (128>>(i&7))) { puts("is visibile"); }

My renderer isn't far enough along that I can readily tell;
the obvious solution would be to play with the bits and
run it through quake itself, but id didn't distribute a
Sparc version of quake yet :(.

My guess is that the first formula is correct, but I suspect
there's something weird with the visibility lists because
I had assumed (hoped) that for any leaf i, its own visibility
bit is set in its visbility list. This would seem to make
sense to me because (barring special effects), two adjacent
leaves may very well have the exact same visibility lists,
so they could share the list.

Unfortunately, while test1.bsp and test2.bsp both have
starting positions in leaves that can "see" themselves,
test3.bsp does not.

Any comments? Obviously my own implementation could be at
fault and I'm wondering if anybody else is having similar

On another topic [as a bonus if you've actually read this far :)],
I've found that augmenting the node structures with backpointers
to their parents (after reading in the map) might prove useful
for optimizing rendering. In order to render from a specific
position, I'm doing the following:

- Traverse the bsp tree to find which leaf the camera is in,
caching the result so that I can do a quick bbox check the
next time to see if I'm in the same leaf.
- See if the current leaf has the same visibility list (ie offset)
as our cached result.
- If it does not, scan the visibility list, and for each leaf
which is visible, mark the leaf as needing to be rendered,
then mark its parent node as needing to be visited, and
then mark *that* parent's node, and so on, until we either
hit the root of the tree or hit a node that's already marked
for visitation.
- Start traversing the tree at the top.
- If neither child node needs to be visited, stop.
- If only one child node needs to be visited, only visit that
- If both children need to be visited, then and only then test
the camera position against the node's split plane to see
which child needs to be visited first.

We can also project the bounding box of a node or leaf into the
view frustum to see if we can trivially reject the entire subtree
(off the side, or behind the viewer) before visiting it as well.

-David Etherton