Visibility Lists Revisited

David Etherton (etherton@megatek.com)
Wed, 20 Mar 1996 12:10:25 +0800

Date: Wed, 20 Mar 1996 12:10:25 +0800
From: etherton@megatek.com (David Etherton)
Message-Id: <9603202010.AA22152@fuzz.megatek>
To: quake-editing@nvg.unit.no
Subject: Visibility Lists Revisited

[Olivier has probably already figured this out and written it up in
the specs, but just in case...]

It looks like the visibility lists are RLE compressed. The encoding
is very simple: if a byte is nonzero, it contains the visibility data
for the next eight leaves. If it is zero, the next byte contains
a skip count. This skip count (probably) means that the next (count<<3)
leaves are not visible. I guess that it means they're *not* visible
because I see lots of (consecutive) 0xFF's in the visibility lists of
test1.bsp.

It seems like RLE compressing 0xFF's as well as 0x00's would work
well, but who am I to question to id gods? :)

I'm reasonably sure that I'm on the right track, because every visibility
list in test1.bsp "unpacks" to 57 bytes, or 456 leaves. While there
are 494 leaves on test1.bsp, leaves 452 and onward all have a visibility
offset of -1. Not sure whether that means "all visible" or "none
visible" yet. [Note floor((452+7)>>3)==57]

[I also just ran test2.bsp through, and it sees them all as 118 bytes
long, and the first leaf with a visoffs of -1 is 941]

I'm still not sure whether the bit test for testing individual unpacked
visibility bytes is (1<<(offset&7)) or (128>>(offset&7)); my usual
sanity check of "any leaf should be able to see itself" still
doesn't work consistently for either method.

I hope this furthers the Great Hacking Effort...

-dce