Highly efficient computer oriented octree data structure and neighbors search in 3D GIS spatial
Three Dimensional (3D) have given new perspective in various field such as urban planning, hydrology, infrastructure modeling, geology etc due to its capability of handling real world object in more realistic manners, rather than two-dimensional (2D) approach. However, implementation of 3D spatial a...
Saved in:
Main Authors: | , , , |
---|---|
Format: | Conference or Workshop Item |
Language: | English |
Published: |
2015
|
Subjects: | |
Online Access: | http://eprints.utm.my/id/eprint/63375/1/MuhamadUznirUjang2015_HighlyEfficientComputerOrientedOctreeData.pdf http://eprints.utm.my/id/eprint/63375/ http://www.geoinfo.utm.my/jointgeoinfo2015/ |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Universiti Teknologi Malaysia |
Language: | English |
id |
my.utm.63375 |
---|---|
record_format |
eprints |
spelling |
my.utm.633752017-05-30T03:10:51Z http://eprints.utm.my/id/eprint/63375/ Highly efficient computer oriented octree data structure and neighbors search in 3D GIS spatial Keling, Noraidah Mohamad Yusoff, Izham Ujang, Uznir Lateh, Habibah G109.5 Global Positioning System Three Dimensional (3D) have given new perspective in various field such as urban planning, hydrology, infrastructure modeling, geology etc due to its capability of handling real world object in more realistic manners, rather than two-dimensional (2D) approach. However, implementation of 3D spatial analysis in the real world has proven difficult due to the complexity of algorithm, computational power and time consuming. Existing GIS system enables 2D and two-and-a-half dimensional (2.5D) spatial datasets, but less capable of supporting 3D data structures. Recent development in Octree see more effort to improve weakness of octree in finding neighbor node by using various address encoding scheme with specific rule to eliminate the need of tree traversal. This paper proposed a new method to speed up neighbor searching and eliminating the needs of complex operation to extract spatial information from octree by preserving 3D spatial information directly from Octree data structure. This new method able to achieve O(1) complexity and utilizing Bit Manipulation Instruction 2 (BMI2) to speedup address encoding, extraction and voxel search 700% compared with generic implementation. 2015 Conference or Workshop Item PeerReviewed application/pdf en http://eprints.utm.my/id/eprint/63375/1/MuhamadUznirUjang2015_HighlyEfficientComputerOrientedOctreeData.pdf Keling, Noraidah and Mohamad Yusoff, Izham and Ujang, Uznir and Lateh, Habibah (2015) Highly efficient computer oriented octree data structure and neighbors search in 3D GIS spatial. In: first 3D Geoinfo, 28-30 Oct,2015, Kuala Lumpur, Malaysia. http://www.geoinfo.utm.my/jointgeoinfo2015/ |
institution |
Universiti Teknologi Malaysia |
building |
UTM Library |
collection |
Institutional Repository |
continent |
Asia |
country |
Malaysia |
content_provider |
Universiti Teknologi Malaysia |
content_source |
UTM Institutional Repository |
url_provider |
http://eprints.utm.my/ |
language |
English |
topic |
G109.5 Global Positioning System |
spellingShingle |
G109.5 Global Positioning System Keling, Noraidah Mohamad Yusoff, Izham Ujang, Uznir Lateh, Habibah Highly efficient computer oriented octree data structure and neighbors search in 3D GIS spatial |
description |
Three Dimensional (3D) have given new perspective in various field such as urban planning, hydrology, infrastructure modeling, geology etc due to its capability of handling real world object in more realistic manners, rather than two-dimensional (2D) approach. However, implementation of 3D spatial analysis in the real world has proven difficult due to the complexity of algorithm, computational power and time consuming. Existing GIS system enables 2D and two-and-a-half dimensional (2.5D) spatial datasets, but less capable of supporting 3D data structures. Recent development in Octree see more effort to improve weakness of octree in finding neighbor node by using various address encoding scheme with specific rule to eliminate the need of tree traversal. This paper proposed a new method to speed up neighbor searching and eliminating the needs of complex operation to extract spatial information from octree by preserving 3D spatial information directly from Octree data structure. This new method able to achieve O(1) complexity and utilizing Bit Manipulation Instruction 2 (BMI2) to speedup address encoding, extraction and voxel search 700% compared with generic implementation. |
format |
Conference or Workshop Item |
author |
Keling, Noraidah Mohamad Yusoff, Izham Ujang, Uznir Lateh, Habibah |
author_facet |
Keling, Noraidah Mohamad Yusoff, Izham Ujang, Uznir Lateh, Habibah |
author_sort |
Keling, Noraidah |
title |
Highly efficient computer oriented octree data structure and neighbors search in 3D GIS spatial |
title_short |
Highly efficient computer oriented octree data structure and neighbors search in 3D GIS spatial |
title_full |
Highly efficient computer oriented octree data structure and neighbors search in 3D GIS spatial |
title_fullStr |
Highly efficient computer oriented octree data structure and neighbors search in 3D GIS spatial |
title_full_unstemmed |
Highly efficient computer oriented octree data structure and neighbors search in 3D GIS spatial |
title_sort |
highly efficient computer oriented octree data structure and neighbors search in 3d gis spatial |
publishDate |
2015 |
url |
http://eprints.utm.my/id/eprint/63375/1/MuhamadUznirUjang2015_HighlyEfficientComputerOrientedOctreeData.pdf http://eprints.utm.my/id/eprint/63375/ http://www.geoinfo.utm.my/jointgeoinfo2015/ |
_version_ |
1643655698411683840 |