Abstract
The voxelization process is an essential stage in three dimensional (3D) graphics pipeline. Its implementation should precede displaying objects in the pipeline. In this paper, different Voxelization algorithms are modified and parallelized to accelerate the operation of this stage. The 3D Digital Differential Analyzer (DDA) algorithm is used for line voxelization. This algorithm is utilized in triangle filling using the scan-line and the edge-function algorithms. The first one is designed to produce lines in parallel while the second can produce voxels. All these algorithms are parallelized using CUDA architecture and implemented on GPU processor. The actual implementation of these algorithms is examined and optimized according to the occupancy and block size metrics. The experimental results show that the acceleration amount of 3D DDA was about 4352x max compared to the OpenGL implementation, and the edge function implementation has been executed at a higher speed than the scan-line for object triangles voxelization
Keywords
GPU; CUDA; Edge-function; Parallel implementation; voxelization.
Abstract
تعتبر عملية تجسيم الاشكال من المراحل المهمة في خط نقل الرسومات الثلاثية الابعاد,تُنفذ هذه المرحلة قبل عرض الاشكال في خط النقل الخاص
بوحدة المعالجة الرسومية ) GPU (.في هذا البحث ، تم تصميم الخوارزميات الخاصة بتوليد النقاط وذلك بأستخدام التنفيذ المتوازي لتسريع العمل. تم استخدام
خوارزمية المحلل التفاضلي الرقمي ثلاثي الأبعاد ) DDA (. واُستغلت هذه الخوارزمية في ملء المثلث الذي يعتبر العنصر الاساسي للعمل في الانظمة
الصورية, وذلك باستخدام طريقتين اساسيتين: خط المسح و دالة الحافة. تم تصميم الطريقة الاولى بحيث يتم توليد خطوط المسح بصورة متوازية. اما في
الطريقة الثانية فتم توزيع العمل بحيث ان كل خيط يولد نقطة صورية واحدة. جميع هذه الخوارزميات صُممت ونُفذت بنااءاًعلى معمارية CUDA
وبأستخدامالمعالج GPU . اظهرت النتائج التجريبية أن مقدار التسارع لخوارزمية 3D DDA كان حوالي 2534 x كحد أقصى مقارنةً بتنفيذ ال OpenGL ،
اما خوارزمية دالة الحافة فكانت افضل من خط المسح وذلك بسرعة توليد 2.3 مليار نقطة في الثانية الواحدة
بوحدة المعالجة الرسومية ) GPU (.في هذا البحث ، تم تصميم الخوارزميات الخاصة بتوليد النقاط وذلك بأستخدام التنفيذ المتوازي لتسريع العمل. تم استخدام
خوارزمية المحلل التفاضلي الرقمي ثلاثي الأبعاد ) DDA (. واُستغلت هذه الخوارزمية في ملء المثلث الذي يعتبر العنصر الاساسي للعمل في الانظمة
الصورية, وذلك باستخدام طريقتين اساسيتين: خط المسح و دالة الحافة. تم تصميم الطريقة الاولى بحيث يتم توليد خطوط المسح بصورة متوازية. اما في
الطريقة الثانية فتم توزيع العمل بحيث ان كل خيط يولد نقطة صورية واحدة. جميع هذه الخوارزميات صُممت ونُفذت بنااءاًعلى معمارية CUDA
وبأستخدامالمعالج GPU . اظهرت النتائج التجريبية أن مقدار التسارع لخوارزمية 3D DDA كان حوالي 2534 x كحد أقصى مقارنةً بتنفيذ ال OpenGL ،
اما خوارزمية دالة الحافة فكانت افضل من خط المسح وذلك بسرعة توليد 2.3 مليار نقطة في الثانية الواحدة
Keywords
وحدة المعالجة الرسومية ،معمارية كودا ، دالة الحافة ، التنفيذ المتوازي،تجسيم الاشكال