Regularity-Preserving Terrain Simplification For Faster Line-of-Sight

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.

Name thesis:degree_name

Master of Science (MSc)

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher.institution

Graduate Studies

Year dc:date.issued

2014

Author dc:creator

• Alderson, Troy

Advisor dc:contributor.advisor

• Samavati, Faramarz

• Computer Science

Statement dc:rights

• University of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.

Language dc:language.iso

eng

DOI

http://dx.doi.org/10.11575/PRISM/27578

OAI identifier oai:identifier

oai:ucalgary.scholaris.ca:11023/1438