Frontier Sets: A Partitioning Scheme to Enable Scalable Virtual Environments

Abstract

We present a new spatial partitioning scheme called frontier sets. Frontier sets build on the notion of a potentially visible set (PVS) [ARB90, TS91]. In a PVS a world is sub-divided into cells and for each cell all the other cells that can be seen are computed. Frontier sets represent regions of mutual invisibility. One frontier in a frontier set considers pairs of cells, A and B. It lists two sets of cells, FAB and FBA. From no cell in FAB is any cell in FBA visible and vice-versa. We have used frontier sets to investigate peer-to-peer networking schemes for networked virtual environments. Preliminary investigation of simulations within the Quake II game engine shows that frontiers have significant promise and may allow a new class of scalable peer-to-peer game infrastructures to emerge.