Fast direct volume rendering of unstructured grids

Abstract

ÖZET DÜZENSİZ IZGARALARIN HIZLI DİREK HACİM GÖRÜNTÜLENMESİ Hakan Berk. Bilgisayar ve Enformatik Mühendisliği. Yüksek Lisans Tez Yöneticisi: Doç. Dr. Cevdet Aykanat Eylül. 1997 Bilimsel Hesaplama her geçen gün gelişen teknoloji ile daha da önem kapan maktadır. Bilimsel uygulamalar tarafından üretilen çok miktardaki verilerin bilimadamlarınca işlenmesi ve daha kolay anlaşılabilmesi için yeni yöntemlere ihtiyaç duyulmaktadır. Üretilen verilerin yüksek miktarda olmasından dolayı bilimadamlarının bu verilerden anlamlı ve işe yarar bilgileri çıkarmaları zorlaşmaktadır. Bu yüzden bu sayısal verilerin görüntülenmesi bilimadamları için vazgeçilemez bir araçtır, ve bilgisayar grafiklerinin bu konuyla uğraşan dalma da Bilimsel Görüntüleme adı verilir. Amacı 3-boyutlu hacimsel verilerin görüntülenmesi olan Hacim Görüntüleme ise Bilimsel Görüntüleme'nin en önemli alt dallarından birisidir. Hacim Görüntüleme yöntemleri iki sınıfa ayırılabilir; Dolaylı ve Direk. Dolaylı yöntemler daha hızlıdır, fakat Direk yöntemler daha esnektir ve daha doğru sonuçlar verirler. Direk hacim görüntüleme yöntemleri de kendi içinde üçe ayrılırlar: ekran-uzayı (ışın izleme), cisim-uzayı ve karma yöntemler. Direk Hacim Görüntüleme (DHG) yöntemlerinin verimliliği daha çok noA-fa-veri tespiti ve görüntü-sıralama problemlerini ne şekilde çözdüğüne bağlıdır. Bu problemlerin çözümü düzenli ızgaralarda basit olmasına rağmen. düzensiz ızgaralarda daha zordur. Araştırmacılar düzensiz ızgaraların hacim görüntülenmesini özel grafik donanımı, yada paralel mimariler kullanarak hızlandırmaya çalışmaktadırlar, ama bu alanda yazılım çözümlerine her zaman ihtiyaç duyulacaktır. Bu tez düzensiz ızgaraların hacim görüntülenmesindeki problemlerin yazılım yöntemleri ile çözülmesi üzerinedir. Düzensiz ızgaraların hacim görüntülenmesi için olan üç ayrı kategorideki yöntemleri inceler. Tezin en önemli amaçlarından birisi değişik kategorilerdeki yöntemlerin avantaj ve dezavantajlarını saptamaktır. Bu konudaki önemli yöntemlerin tartışması.bunların dezavantajlarının ve avantajlarının belirtilmesi ile zenginleştirilmeye çalışılmıştır. Bu problemleri çözmeye yönelik üç yeni ve hızlı yöntem geliştirilmiş ve daha iyi bir karşılaştırma için olan bir yöntem detaylı bir şekilde incelenmiştir. Tezde öne sürülen tüm yöntemler doğru ve yüksek kalite resim üretmeyi amaç edinmişlerdir. Bunlardan iki tanesi tamamen ışın-izleme üzerine geliştirilmiş yöntemler olup, erken ışın sonlanmasını desteklemekte ve döngüsel ızgaraları görüntüleyebilmektedirler. Bu yöntemlerin göreceli performansları geniş bir veri kümesi üzerinde deneysel olarak ölçülmüş ve olan en iyi DHG yöntemlerinden daha hızlı oldukları sonucuna varılmıştır. Anahtar Kelimeler. Hacim Görüntüleme. Direk Hacim Görüntüleme. Düzensiz Izgara, Işın izleme.

Ill ABSTRACT FAST DIRECT VOLUME RENDERING OF UNSTRUCTURED GRIDS Hakan Berk M.S. in Computer Engineering and Information Science Supervisor: Assoc. Prof. Cevdet Ay kan at September, 1997 Scientific Computing has become more and more important with the evolv ing technology. The vast amount of data that the scientific computing applica tions produce need new ways to be processed and be interpreted by scientists. The large amount of data makes it very difficult for scientists to extract useful information from the data, and interpret it to reach a useful conclusion. Thus. visualization of such numerical data as an image, which is named as Scientific Visualization, is an indispensable tool for researchers. Volume Rendering is a very important branch of Scientific Visualization and makes it possible for scientists to visualize the 3-dimensional (3D) volumetric datasets. / olume Rendering algorithms can be classified into two categories: Indirect and Direct methods. Indirect methods are faster, but direct methods are more flexible, and accurate. Direct methods can be classified into three categories: image-space (ray-casting), object-space (projection) and hybrid. The efficiency of a direct volume rendering (DVR) algorithm is strongly related to the way that it solves the underlying point location and view sort problems. Although these problems are almost trivial ones to solve in structured grids, they be come more complex ones to deal with for unstructured grids. Researchers have tried to speed up the volume rendering of unstructured grids by using spe cial graphics hardware, and parallel architectures, but the need for software solutions to these problems will always exist. This thesis is involved in solv ing those problems in unstructured grids via software methods. It investigates three distinct categories, namely image-space methods, object-space methods and hybrid methods for fast direct volume rendering of unstructured grids.IV The main objective of the thesis is to identify the relative superiorities and inferiorities of the algorithms in these three categories. A survey of existing methods is enriched by a discussion of their merits and shortcomings. Three new and fast algorithms to overcome the existing inefficiencies are proposed, and one existing algorithm is investigated in detail for a better comparison. All of the proposed algorithms are aimed at producing correct, high quality images. Two of the proposed algorithms are pure ray-casting based solutions that support early ray termination and can handle cyclic grids. The relative performances of the proposed algorithms are experimented on a wide range of benchmark grids in a common framework for software methods and they are found to be faster than the existing best DVR algorithms. Key words: Volume Rendering, Direct Volume Rendering (DVR). Unstruc tured Grid, Volume Visualization. Ray Casting.