RE: Visibility lists

Bernd Kreimeier (Bernd.Kreimeier@NeRo.Uni-Bonn.DE)
Tue, 23 Apr 1996 10:16:08 +0200 (MET DST)

From: Bernd Kreimeier <Bernd.Kreimeier@NeRo.Uni-Bonn.DE>
Date: Tue, 23 Apr 1996 10:16:08 +0200 (MET DST)
Message-Id: <>
Subject: RE: Visibility lists

>From: Mike Ruete <>

> I (with my limited understanding of BSPs) would guess that you would
>probably *not* see a linear relationship between leaves and vislist entries.
>I would think the vislist would get a lot bigger a lot faster as you got
>more leaves...

Let's do some guesstimates: the worst case is that every leaf is
potentially visible to every other leave, thus O( sqr(N) ).

Average case: To get a level framerate, any coder could only hope the
level designers take into consideration requirements like: the average
number of polygons to be clipped per frame should not vary too much.
As Abrash wrote: no matter how fast the hardware, or how sophisticated
the renderer, they will just add more polys and create more complex

Assume some not too much varying average of polys/leaf (any cube is
fine, any fine-grained approximation of a sphere like some 320-hedron
of course contradicts this assumption, but let's stick with euclidian
geometry for convenience sake). To get constant average polys/frame,
both polys/leaf and visible leafs/frame have to be approx. constant
(of course, a level designer could always trade less complex leafs
to get a larger range of view - prime example will be outdoor areas).

In conclusion, the average case could indeed be a linear relationship
between number of vislist entries and number of leafs, assuming that
RLE encoding will be able to compress all the zero flags to some
constant overhead. Anybody care to comment on RLE performance?

However, the average case looks pretty much like being the best as
well. So Mike is probably right: we will face something that is worse
than linear, but luckily not as bad as quadratic.