Acceleration of line of sight analysis algorithms with parallel programming

Date

2017-11-23

Author

Yılmaz, Gökhan
Sürer, Elif
Temizel, Alptekin

Metadata

Show full item record

Item Usage Stats

168
views

0
downloads

Line of sight (LOS) analysis is a set of methods and algorithms to determine the visible points in a terrain with reference to a specific observer point. This analysis is used in simulations, Geographic Information System (GIS) applications and games. For this reason, it is important to have a capability to get results quickly and facilitate analysis in such a way that the interaction with the changing reference points is possible. Van Kreveld, R2 and R3 are the most frequently used algorithms in line of sight analysis. The purpose of this research is to develop parallel adaptations of these particular algorithms by making use of the capabilities of a modern Graphics Processing Unit (GPU) and to evaluate these adaptations in terms of performance and memory usage. By analyzing which algorithm is more suitable to be implemented on the GPU, the algorithm that will provide the most appropriate and quick solution to the probing problem can be determined. In this research, Van Kreveld's algorithm, which is basically a sequential algorithm, was developed partly in parallel, and the speed-up was 1.5x compared to the sequential version of the algorithm. Speed-up rates increase up to 10.5x for R2 and 160x for R3 algorithms, respectively. The results can be used to combine CPU / GPU approaches in order to perform hybrid or full parallelization of Van Kreveld’s Algorithm on the GPU. The results presented in the paper will serve as a guide for the selection of the appropriate algorithm by evaluating the strengths and weaknesses of different algorithms.

Subject Keywords

Geographic information systems, vVewshed, Parallel programming, Line of sight analysis, GPGPU

URI

https://hdl.handle.net/11511/83463

Conference Name

7. Ulusal Savunma Uygulamaları Modelleme ve Simülasyon Konferansı ( 21 - 23 Kasım 2017)

Collections

Graduate School of Informatics, Conference / Seminar

Suggestions

OpenMETU
Core

Accelerating of line of sight analysis algorithms with parallel programming Yılmaz, Gökhan; Temizel, Alptekin; Sürer, Elif; Department of Modeling and Simulation (2017) Line of sight (LOS) analysis is a set of methods and algorithms to determine the visible points in a terrain with reference to a specific observer point. This analysis is used in simulations, Geographic Information System (GIS) applications and games. For this reason, it is important to have a capability to get results quickly and facilitate analysis in such a way that the interaction with the changing reference points is possible. Van Kreveld, R2 and R3 are the most frequently used algorithms in line of si...
Tracking of ground targets with interacting multiple model estimator Acar, Duygu; Baykal, Buyurman; Department of Electrical and Electronics Engineering (2011) Interacting Multiple Model (IMM) estimator is used extensively to estimate trajectories of maneuvering targets in cluttered environment. In the standard tracking methods, it is assumed that movement of target is applicable to a certain model and the target could be monitored via the usage of status predictions of that model. However, targets can make different maneuvering movements. At that time, expression of target dynamic model with only one model can be insufficient. In IMM approach, target dynamic mode...
Development of free/libre and open source spatial data analysis system fully coupled with geographic information system Kepoğlu, Volkan Osman; Düzgün, H. Şebnem; Department of Geodetic and Geographical Information Technologies (2011) Spatial Data Analysis (SDA) is relatively narrower and constitutes one of the areas of Spatial Analysis. Geographic Information System (GIS) offers a potentially valuable platform for supporting SDA techniques. Integration of SDA with GIS helps SDA to benefit from the data input, storage, retrieval, data manipulation and display capabilities of GIS. Also, GIS can benefit from SDA techniques in which the integration of these techniques can increase the analysis capabilities of GIS. This integration serves fo...
Classification of remotely sensed data by using 2D local discriminant bases Tekinay, Çağrı; Çetin, Yasemin; Department of Information Systems (2009) In this thesis, 2D Local Discriminant Bases (LDB) algorithm is used to 2D search structure to classify remotely sensed data. 2D Linear Discriminant Analysis (LDA) method is converted into an M-ary classifier by combining majority voting principle and linear distance parameters. The feature extraction algorithm extracts the relevant features by removing the irrelevant ones and/or combining the ones which do not represent supplemental information on their own. The algorithm is implemented on a remotely sensed...
Modeling of the nonlinear behavior of steel framed structures with semi rigid connections Sarıtaş, Afşin; Özel, Halil Fırat (null; 2015-07-21) A mixed formulation frame finite element with internal semi-rigid connections is presented for the nonlinear analysis of steel structures. Proposed element provides accurate responses for spread of inelasticity along element length by monitoring the nonlinear responses of several crosssections, where spread of inelasticity over each section is captured with fiber discretization. Each material point on the section considers inelastic coupling between normal stress and shear stress. The formulation of the ele...

Citation Formats

G. Yılmaz, E. Sürer, and A. Temizel, “Acceleration of line of sight analysis algorithms with parallel programming,” presented at the 7. Ulusal Savunma Uygulamaları Modelleme ve Simülasyon Konferansı ( 21 - 23 Kasım 2017), Ankara, Türkiye, 2017, Accessed: 00, 2021. [Online]. Available: https://hdl.handle.net/11511/83463.