Regularity-Preserving Terrain Simplification For Faster Line-of-Sight
Date
2014-04-28
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Three-dimensional terrain models play a key role in many applications. Line-of-sight queries, which are important operations in some applications (e.g. battlefield simulations), test whether or not two entities can see each other over the terrain. Given enough entities and a large enough terrain, computing these queries can be expensive. Terrain simplification can be used to speed up the queries, with a penalty to accuracy. To take advantage of the especially fast algorithms that exist for regular terrain models, we introduce regularity-preserving terrain simplification methods based on reverse subdivision and examine their effect on query accuracy. Furthermore, we develop a novel feature preserving reverse subdivision scheme that attempts to improve query accuracy over the pre-existing methods.
Additionally, we have examined the problem of where entities should be located after terrain simplification to maximize accuracy. Using iterative methods that attempt to maximize accuracy, we show that room for improvement exists over the standard projection method. Then, we develop practical relocation methods designed to maximize accuracy over regular simplified terrain models, the first taking a hybrid approach between projection and no relocation and the second using residual vectors to map entities onto the simplified terrain. Accuracy improvements over these basic methods can be achieved by making use of the iterative methods in a pseudo-optimization pre-processing step.
Finally, we introduce a practical line-of-sight algorithm based on hierarchies of simplified terrains that is both fast and accurate. Our approach combines two existing algorithms, using each of their strengths to achieve highly efficient line-of-sight queries in local areas.
Description
Keywords
Computer Science
Citation
Alderson, T. (2014). Regularity-Preserving Terrain Simplification For Faster Line-of-Sight (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/27578