Spatial subdivision for parallel ray casting/tracing

Abstract

Özet PARALEL IŞIN DUŞURME/IZLEME İÇİN UZAYSAL BÖLÜMLEME Veysi İşler Bilgisayar ve Enformatik Mühendisliği Doktora Tez Yöneticileri: Prof. Dr. Bülent Özgüç ve Doç. Dr. Cevdet Aykanat Şubat 1995 Bu çalışma uzaysal bölme yönteminin paralel bir bilgisayarda gerçeğe uygun görüntü üretmek için kullanılması üzerinde yoğunlaşmaktadır. Işm izleme çok yararlı olmasına karşın oldukça fazla işlem gerektiren bir yöntemdir. Bu nedenle bir çok araştırıcı, bu yöntemin sorunlarına çözüm bulmak için çalışmaktadır. Bu çalışmalar sonucunda ortaya çıkan parallel ışın izleme yöntemlerinin sınıflandırılması bu tezde yapılmakta, önemli paralel ışın izleme yöntemleri yine bu tezde tartışılmakta ve eleştirilmektedir. Uzaysal bölümleme yöntemi, bir işlemcinin yerel belleğine sığamayan üç-boyutlu karmaşık sahnelerin ayrıştırılmasına dayanan paralel ışm izleme algoritmasına uygu lanmıştır. Geliştirilen ayrıştırma yöntemi, sahnedeki nesnelerin işlemcilere eşit bir şekilde dağıtılmasını sağlamakla birlikte grafiksel tutarlılığın (coherence) kullanılmasına da olanak sağlamaktadır. Uzaysal bölümlemeyi kullanan ayrıştırma yöntemi, ayıran düzlemleri etkin veri yapıları ile oldukça kısa sürede bulmaktadır. Ayrıca, ortaya mçıkan hacimlere bağlı nesnelerin işlemcilere, işlemciler arasındaki iletişimi azaltacak şekilde eşlenmesi de ayrıştırma yöntemi ile eşzamanlı olarak kısa sürede yapılmaktadır. Ayrıca, önişlemde harcanan zamanı azaltmak için, önerilen ayrıştırma ve eşleme işleri de paralelleştirilmişt ir. Son olarak, işlemcilere ait yerel belleklerin tamamını kullanmaya olanak sağlayan yeni bir ayırma düzlemi (çıkıntılı ayırma düzlemi) önerilmektedir. Önerilen çıkıntılı ayırma düzlemi paylaşılan nesnelerin birden fazla işlemcinin yerel belleğinde bulunmasına izin vermeyerek paralel bilgisayarın verimli kullanılmasını sağlar. Önerilen paralel algoritmalar Intel iPSC/2 hiperküp bilgisayarında gerçekleştirilmiştir. Anahtar Sözcükler: Işın Düşürme, Işın İzleme, Uzaysal Bölümleme, İkili Uzaysal Bölümleme, Ayırma Düzlemi, Hiperküp Topolojisi, Paralel İşleme. iv

Abstract SPATIAL SUBDIVISION FOR PARALLEL RAY CASTING/TRACING Veysi İşler Ph.D. in Computer Engineering and Information Science Supervisors: Prof. Bülent Özgüç and Assoc. Prof. Cevdet Aykanat February 1995 Ray casting/tracing has been extensively studied for a long time, since it is an elegant way of producing realistic images. However, it is a computationally intensive algorithm. In this study, a taxonomy of parallel ray casting/tracing algorithms is presented and the primary parallel ray casting/tracing systems are discussed and criticized. This work mainly focuses on the utilization of spatial subdivision technique for ray casting/tracing on a distributed-memory MIMD parallel computer. In this research, the reason for the use of parallel computers is not only the processing power but also the large memory space provided by them. The spatial subdivision technique has been adapted to parallel ray casting/tracing to decompose a three-dimensional complex scene that may not fit into the local memory of a single processor. The decomposition method achieves an even distribution of scene objects while allowing to exploit graphical coherence. Additionally, the decomposition method produces three-dimensional volumes which are mapped inexpensively to the processors so that the objects within adjacent volumes are stored in the local memories of close processors to decrease interprocessor communication cost. Then, the developeddecomposition and mapping methods have been parallelized efficiently to reduce the preprocessing overhead. Finally, a splitting plane concept (called `jaggy splitting plane`) has been proposed to accomplish full utilization of the memory space of processors. Jaggy splitting plane avoids the shared objects which are the major sources of inefficient utilization of both memory and processing power. The proposed parallel algorithms have been implemented on the Intel iPSC/2 hypercube multicomputer (distributed- memory MIMD). Keywords: Ray Casting, Ray Tracing, Spatial Subdivision, Binary Spatial Partition ing (BSP), Splitting Plane, Hypercube Topology, Parallel Processing. u