Computing point visibility on a terrain based on a nested horizon structure


In this paper, we define the concepts of horizons and shadows with respect to a fixed viewpoint. We introduce a model, called the in infuence map, for describing the visibility of a terrain from a viewpoint, based on a sequence of nested horizons. The influence map can be encoded as a balanced tree, called the influence tree, which has a spatial complexity of O ( n 2 log n ) for a polyhedral terrain with n vertices. We show that a point visibility query on such structure can be answered in O (log 2 n ) time.

Proceedings ACM Symposium on Applied Computing ‘94