CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA

ÇAVUŞOĞLU, Abdullah; GÖRGÜNOĞLU, SALİH; Ozcan, Caner; ŞEN, BAHA

CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA

Abdullah ÇAVUŞOĞLU, (Yildirim Beyazit University)

Baha ŞEN, (Yildirim Beyazit University)

Caner ÖZCAN, (Karabuk University)

Salih GÖRGÜNOĞLU (Karabuk University)

Mathematical and Computational Applications

1 0

Yıl: 2013 Cilt: 18 Sayı: 3 Sayfa Aralığı: 301 - 312 Metin Dili: İngilizce İndeks Tarihi: 29-07-2022

CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA

Öz:

In this study, surfaces of solid objects are coloured with Cropped Quad-Tree method utilizing GPU computing optimization. There are numerous methods used in solid object colouring. When the studies carried out in different fields are taken into consideration, it is seen that quad-tree method displays a prominent position in terms of speed and performance. Cropped quad-tree is obtained as a result of the developments seen with the frequent use of this method in the field of computer sciences. Two different versions of algorithm which operate recursively on CPU and at the same time which use GPU computing optimization are used in this study. Besides, OpenGL is used for graphics drawing process. Within the setting of the study, results are obtained via CPU and GPU's, at first using Quad-Tree method and then Cropped Quad-Tree method. It is observed that GPU computing is obviously faster than CPU computing and Cropped Quad-Tree method produces rapid results compared to Quad-Tree method as a result of performance. GPU computing method boosted approximately performance by up to 20 times compared to only CPU usage; furthermore, cropped quad-tree method boosted approximately performance of algorithm by up to 25 times on average dependent on screen and object size.

Anahtar Kelime:

Konular: Matematik

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

1. J. Sanders, E. Kandrot, CUDA by Example: An Introduction to General-Purpose GPU Programming, Addison-Wesley, 2011
2. M. Garland, S. L. Grand, J. Nickolls, J. Anderson, J. Hardwick, S. Morton, E.
Phillips, Y. Zhang and V. Volkov, Parallel computing experiences with CUDA, IEEE Micro 28 (4), 13-27, 2008.
3. Z. Yang, Y. Zhu and Y. Pu, Parallel Image Processing Based on CUDA, Proceedings of the 2008 International Conference on Computer Science and Software Engineering, 198-201, 2008.
4. M. Akçay, B. Şen, İ. M. Orak andA. Çelik, Paralel Hesaplama ve CUDA, 6. International Advanced Technologies Symposium, 2011.
5. H. Samet, Region representation: quad-trees from binary arrays, Computer Graphics & Image Processing 13 (1), 88-93, 1980.
6. G. M. Hunter and K. Steiglitz, Operations on images using quad trees, IEEE Transactions on Pattern Analysis and Machine Intelligence, 145-153, 1979.
7. F. Wang, Relational-Linear Quad-tree Approach for Two-Dimensional Spatial Representation and Manipulation, IEEE Transactions on Knowledge and Data Engineering 3 (1), 118-122, 1991.
8. H. Samet, An algorithm for converting rasters to quadtrees, IEEE Trans. Pattern Analysis and Machine Intelligence 3(1), 93-95, 1981.
9. M. Kelly andA. Breslow, Quad-tree Construction on the GPU: A Hybrid CPU-GPU Approach, Retrieved September 13, 2012 from the World Wide Web:http://www.sccs.swarthmore.edu/users/10/mkelly1/quad-trees.pdf.
10. I. K. Park, N. Singhal, M. H. Lee,S. Cho and C.W. Kim, Design and Performance Evaluation of Image Processing Algorithms on GPUs, IEEE Transactions on Parallel and Distributed Systems 22 (1), 91-104, 2011.
11. C. Özcan and B. Şen, Investigation of the performance of LU decomposition method using CUDA, World Conference on Innovation and Computer SciencesProcedia Technology 1, 50-54, 2011.
12. B. Şen, C. Özcan and N. A. Atasoy, An Implementation for Quad-Tree Based Solid Object Coloring Using CUDA, AWER Procedia Information Technology and Computer Science 1, 2012.
13. R. A. Finkel and J. L. Bentley, Quad Trees: A data Structure for Retrieval on Composite Keys, Acta Informatica 4 (1), 1-9, 1974.
14. R. Sinha, S. Samaddar, D. Bhattacharyya and T.Kim, A Tutorial on Spatial Data Handling, International Journal of Database Theory and Application 3(1), 2010.
15. H. Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys 16(2), 187-260, 1984.
16. Quad-tree, Retrieved September 5, 2012 from the World Wide Web: http://en.wikipedia.org/wiki/Quadtree
17. G. J. Sullivan and R. L. Baker, Efficient quad-tree coding of images and video, IEEE Trans. on Image Processing 3, 327-331, 1994.
18. NVIDIA CUDA C Programming Guide, Version 4.0 available as http://developer.nvidia.com/nvidia-gpu-computing-documentation.
19. J. Nickolls and W.J. Dally, The GPU computing era, IEEE Micro 30, 56-69, 2010.
20. NVIDIA CUDA, Retrieved October 23, 2012 from the World Wide Web: http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html

APA	ÇAVUŞOĞLU A, ŞEN B, Ozcan C, GÖRGÜNOĞLU S (2013). CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA. , 301 - 312.
Chicago	ÇAVUŞOĞLU Abdullah,ŞEN BAHA,Ozcan Caner,GÖRGÜNOĞLU SALİH CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA. (2013): 301 - 312.
MLA	ÇAVUŞOĞLU Abdullah,ŞEN BAHA,Ozcan Caner,GÖRGÜNOĞLU SALİH CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA. , 2013, ss.301 - 312.
AMA	ÇAVUŞOĞLU A,ŞEN B,Ozcan C,GÖRGÜNOĞLU S CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA. . 2013; 301 - 312.
Vancouver	ÇAVUŞOĞLU A,ŞEN B,Ozcan C,GÖRGÜNOĞLU S CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA. . 2013; 301 - 312.
IEEE	ÇAVUŞOĞLU A,ŞEN B,Ozcan C,GÖRGÜNOĞLU S "CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA." , ss.301 - 312, 2013.
ISNAD	ÇAVUŞOĞLU, Abdullah vd. "CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA". (2013), 301-312.

APA	ÇAVUŞOĞLU A, ŞEN B, Ozcan C, GÖRGÜNOĞLU S (2013). CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA. Mathematical and Computational Applications, 18(3), 301 - 312.
Chicago	ÇAVUŞOĞLU Abdullah,ŞEN BAHA,Ozcan Caner,GÖRGÜNOĞLU SALİH CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA. Mathematical and Computational Applications 18, no.3 (2013): 301 - 312.
MLA	ÇAVUŞOĞLU Abdullah,ŞEN BAHA,Ozcan Caner,GÖRGÜNOĞLU SALİH CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA. Mathematical and Computational Applications, vol.18, no.3, 2013, ss.301 - 312.
AMA	ÇAVUŞOĞLU A,ŞEN B,Ozcan C,GÖRGÜNOĞLU S CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA. Mathematical and Computational Applications. 2013; 18(3): 301 - 312.
Vancouver	ÇAVUŞOĞLU A,ŞEN B,Ozcan C,GÖRGÜNOĞLU S CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA. Mathematical and Computational Applications. 2013; 18(3): 301 - 312.
IEEE	ÇAVUŞOĞLU A,ŞEN B,Ozcan C,GÖRGÜNOĞLU S "CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA." Mathematical and Computational Applications, 18, ss.301 - 312, 2013.
ISNAD	ÇAVUŞOĞLU, Abdullah vd. "CROPPED QUAD-TREE BASED SOLID OBJECT COLOURING WITH CUDA". Mathematical and Computational Applications 18/3 (2013), 301-312.