Comparison of image space subdivision algorithms for parallel volume rendering

Abstract

ÖZET EKRAN UZAYINDA BÖLME YÖNTEMLERİNİN PARALEL HACİM GÖRÜNTÜLEME AMACIYLA KARŞILAŞTIRMALI İNCELENMESİ Egemen Tanin Bilgisayar ve Enformatik Mühendisliği, Yüksek Lisans Danışman: Doç. Dr. Cevdet Aykanat Temmuz, 1995 Birçok mühendislik uygulamalarında, elde edilen sonuçlar yapısal olmayan hacimsel veri kümeleri olarak saklanmaktadır. Doğrudan Hacim Görüntüleme (DUG) yöntemleri bu amaçla kullanılan en etkin görüntüleme tekniklerinden biridir. Ancak bu yöntemler oldukça yoğun işlemler sonucunda istenilen görüntüyü elde edebilmekte ve dolayısıyla animasyon ve benzeri uygulamalar için oldukça yavaş yöntemler olarak kabul edilmektedirler. Ayrıca hacim sel veriler çok büyük bilgisayar bellekleri kullanılarak saklanabilmekte ve bu açıdanda görüntüleme işlemini oldukça zorlaştırmaktadırlar. Bunlara ek olarak uygulamaların çoğunluğu çok işlemcili dağıtık hafızalı bilgisayarlarda yapılmaktadır. Dolayısıyla büyük veri kümelerinin görüntüleme amaçlı bil gisayarlara taşınması büyük sorunlar doğurabilmektedir, işte bütün bu ne denlerden dolayıdır ki Paralel-DHG (P-DHG) önemli bir araştırma konusu olmuştur. Fakat DHG yöntemlerinin yapısal olmayan hacimlerde uygulan ması nokta yeri tespiti ve bakış açısı sıralaması adı verilen iki problemin çözümünü gerektirmektedir. Bu tezde standart poligon boyama yöntemleri kullanılarak bu problemlere çözüm aranmış ve paralelleştirmek amacıyla üç yöntem ileri sürülmüştür. Önerilen ana paralel algoritma Işın Düşürme yönteminin kullanılması yoluyla görüntüleme yapılması esasını kullanmakta ve ileri sürülen bu üç yöntem gibi ekran uzayını baz olarak almaktadır. Dolayısıyla iş bölümü ekran uzayının daha küçük ekran parçacıklarına bölünmesi ile gerçekleştirilmektedir. İş dağılımı herbir paralel işlemci başına tek bir ekranVI bölümü düşecek şekilde statik dağılım yapılarak gerçekleştirilmiştir. Kullanılan poligon boyama yönteminin ana bölümleri göz önüne alınarak bir ekran bölümündeki iş hesaplanmış ve mümkün olduğunca işlemcilere eşit iş dağılımı yapılmaya çalışılmıştır. Geliştirilen programlar her türlü sistem ve veri kümesi kullanabilecek şekilde genelleştirilmiş ve bu şekilde gerçekleştirilmişlerdir. Yatay, dikdörtgene, ve özyineli adı verilen bölme yöntemlerinin IBM-SP2 sis teminde karşılaştırmalı incelenmesi yapılmış ve bu tezle birlikte sunulmuştur. Anahtar Sözcükler: Doğrudan hacim görüntüleme, bilgisayar grafikleri, paralel algoritmalar, dağıtık hafızalı çok işlemcili bilgisayarlar.

ABSTRACT COMPARISON OF IMAGE SRACE SUBDIVISION ALGORITHMS FOR PARALLEL VOLUME RENDERING Egemen Tanin M.S. in Computer Engineering and Information Science Advisor: Assoc. Prof. Cevdet Aykanat July, 1995 In many scientific applications, results are presented as unstructured volumet ric data sets. Direct Volume Rendering (DVR) is a powerful way of visualizing these volumetric data sets. However, it involves intensive computations. In addition, most of the volumetric data sets also require huge memories. Hence, DVR is a good candidate for parallelization on distributed memory multicom puter. Also most of the engineering simulations are done on multicomputers. Therefore, visualization of these results on the same architectures where simu lations are done avoids the overhead of transporting large amount of data. In order to visualize unstructured volumetric data sets, the underlying algorithms should resolve the point location and the view sort problems of the 3D grid points. In this thesis, these problems are solved by using the well-known Scan- line Z-Buffer algorithm. Three image space subdivision algorithms, namely horizontal, rectangular, and recursive subdivisions, are utilized to distribute the computations evenly among the processors in the rendering phase. The main parallel algorithm uses Raycasting approach of DVR to visualize the data sets, which is also an image space method. Therefore, the divisions are made in order to obtain a set of sub-images. Static task decomposition is used where each processor is assigned to a single sub-image. The load balance among the processors is achieved by defining the overall work load with in a sub-image by using the milestone operations done in the Scanline Z-Buffer algorithm. The algorithms are developed in a way that they can handle any kind of polygonal, volumetric, and etc. data set where the underlying architecture is also kept iiiIV flexible in many aspects for the sake of generality and portability. The exper imental performance evaluation of the horizontal, rectangular, and recursive subdivision algorithms on an IBM-SP2 system are presented and discussed in a comparative way. Keywords: Direct volume rendering, computer graphics, parallel algorithms, distributed memory multicomputer.