{"id":{"repo_id":"calgary","oai_identifier":"oai:ucalgary.scholaris.ca:11023/1438"},"canonical_url":"https://search.dev.ndltd.org/etd/calgary/oai:ucalgary.scholaris.ca:11023/1438","repository":{"repo_id":"calgary","name":"University of Calgary","base_url":"https://ucalgary.scholaris.ca/server/oai/request"},"display":{"title":"Regularity-Preserving Terrain Simplification For Faster Line-of-Sight","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Alderson, Troy"],"institution":"Graduate Studies","degree_name":"Master of Science (MSc)","degree_level":null,"degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Samavati, Faramarz"],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-04-28","date_published":"2014-04-28","updated_at":"2026-07-24T01:30:25Z","subjects":["Computer Science"],"languages":["eng"],"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."],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["http://dx.doi.org/10.11575/PRISM/27578"],"render_values":[{"text":"http://dx.doi.org/10.11575/PRISM/27578","href":"http://dx.doi.org/10.11575/PRISM/27578","code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/11023/1438","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Samavati, Faramarz"]},{"key":"dc:creator","label":"Author","values":["Alderson, Troy"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-04-28T22:27:41Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-06-16T07:00:34Z"]},{"key":"dc:date.issued","label":"Date","values":["2014-04-28"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Calgary"]},{"key":"dc:type","label":"Dc Type","values":["master thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MSc)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Calgary"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["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."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["http://dx.doi.org/10.11575/PRISM/27578"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11023/1438"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Regularity-Preserving Terrain Simplification For Faster Line-of-Sight"]}]}],"canonical_facts":{"dc:contributor.advisor":["Samavati, Faramarz"],"dc:creator":["Alderson, Troy"],"dc:date.accessioned":["2014-04-28T22:27:41Z"],"dc:date.available":["2014-06-16T07:00:34Z"],"dc:date.issued":["2014-04-28"],"dc:description.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."],"dc:identifier.doi":["http://dx.doi.org/10.11575/PRISM/27578"],"dc:identifier.uri":["http://hdl.handle.net/11023/1438"],"dc:language.iso":["eng"],"dc:publisher.institution":["University of Calgary"],"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."],"dc:subject":["Computer Science"],"dc:title":["Regularity-Preserving Terrain Simplification For Faster Line-of-Sight"],"dc:type":["master thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_name":["Master of Science (MSc)"],"thesis:institution_name":["University of Calgary"]},"updated_at":"2026-07-24T01:30:25Z"}