Abstract: In rendering large models, it is important to efficiently identify the subset of primitives which are visible from a given viewpoint. One approach that can be applied in the case of static models consists of partitioning the viewpoint space into viewpoint cells, and then precomputing a visibility table that explicitly records the list of potentially-visible primitives for each viewpoint cell. We propose a method of compressing such visibility tables in order to produce compact and natural descriptions of potentially-visible sets. The algorithms are tested on three types of scenes which have very different structures: a terrain model, an architectural model, and a world consisting of curved tunnels. The results show that the the salient structure in each type of scene can be automatically detected and exploited in order to achieve a compact representation of potentially visible sets.