Optimizing line-of-sight using simplified regular terrains

Abstract

In this work, we explore a set of techniques for speeding up line-of-sight queries whilst attempting to maintain accuracy. Line-of-sight queries, which test if two entities can see each other over a 3D terrain model, are an important operation in several applications. Given enough entities and a large enough terrain, computing these queries can be expensive. We apply reverse subdivision methods to simplify the terrain model and speed up the queries, including a novel feature-aware reverse subdivision scheme. To counteract the loss of accuracy due to simplification, we also examine the problem of where entities should be placed after terrain simplification to increase accuracy. Using iterative methods that attempt to maximize accuracy, we show that room for improvement exists over the standard projection method. Then, using residual multiresolution vectors, we develop a relocation method designed to …