DOI: 10.1145/1063723.1063732We describe a simple and efficient dynamic occlusion- culling algorithm for computing potentially visible sets (PVS) in densely occluded virtual environments. Our method is an optimization of a widely used technique in which a 3D environment is divided into cells and portals. Our algorithm computes the PVS in approximately half the time of previous portal methods at the expense of producing a slightly relaxed PVS. In addition, our algorithm enables fast culling of objects within cells using inexpensive object-space methods by using a lookup table to compute the diminished object-space view frustum. The algorithm takes advantage of temporal coherence, is easy to implement, and is particularly well suited for applications that need to compute a PVS for use in non-rendering tasks such as AI.