Abstract:

  We propose an implementation for quad-tree based solid object coloring using Compute Unified Device Architecture (CUDA). There are numerous different techniques in use for solid object coloring. One commonly used technique is the quad-tree, which has evolved from work in different fields. A quad-tree is a tree data structure in which each internal node has exactly four children. The quad-tree somewhat follows the tree data structure commonly used in computer science. The normal tree data structure looks like an upside down tree, where a parent node at the top of the tree has one or more children nodes connected to it. The aim of this study is coloring of a solid object using screen splitting method. The screen is divided into squares via this method and whether one or more points of the object are available in the separated parts is searched. According to the existing points, algorithm is applied and the object coloring is provided by reducing pixel size. We implemented our algorithm using the Graphics Processing Unit (GPU) computing and compared their performance with a CPU implementation. Nvidia CUDA library has been used for the GPU computing. CUDA gives developers access to the virtual instruction set and memory of the parallel computational elements in CUDA GPUs. We have tried our study on different systems that have different GPUs and CPUs. The computation studies were also evaluated for different solid objects. When we compared the results obtained from both systems, a better performance was obtained with GPU computing. According to results, GPU computation approximately worked 20 times faster than the CPU computation. 

Keywords: