Development of an algorithm for the elimination of surface sorting in the stage of hidden surface removal in displaying constructive solid geometry (CSG) volumes and surfaces

Abstract

ÖZET YAPISAL KATI GEOMETRİ (CSG) HACİM ve YÜZEYLERİNİ GÖRÜNTÜLEMEDE GÖRÜNMEZ YÜZEYLERİN TEMİZLİĞİ AŞAMASINDA OLUŞAN YÜZEY SIRALAMASININ ORTADAN KALDIRILMASI İÇİN BİR ALGORİTMANIN GELİŞTİRİLMESİ KOÇ, Sema Yüksek Lisans Tezi, Elektrik ve Elektronik Mühendisliği Bölümü Tez Yöneticisi: Assist. Prof. Dr. Ulus ÇEVİK Karşılıklı etkileşimli sistemlerde bilgisayar grafiği kullanarak görüntü oluşturulurken, çizgi-tabanlı modellemelerde görüntünün doğru algılanamaması nedeniyle katı modellemelere ihtiyaç duyulmaktadır. Katı cisimlerin modellemesinde kullanılan en popüler metotlardan birisi de CSG'dir. Sonsuz düzlemler uzayı yarı-uzaylara böler. Ve bu yarı-uzayların kesişimlerinden daha karmaşık cisimler, konveks katılar ya da çukurlar, elde edilir. Daha karmaşık yapıya sahip hacimler bu konveks birimlerin birleşimleri ile oluşturabilir. Bir cisimde bakış noktasından dışarıya doğru yönelen düzlem yarı- uzayları `ön yüzey`, bakış noktasına doğru yönelenler ise `arka yüzey` olarak adlandırılırlar. CSG metodu bilgisayar oyunları, uçak simulatörleri, ve bilgisayar yardımlı projeler gibi bir çok alanlarda kullanılmaktadır. Bu uygulamalarda gerçek zamanlı etkileşime ulaşabilmek için verilerin hızlı bir şekilde işlenmesi gerekmektedir. Daha önce yapılan çalışmalarda, cismin görüntüsünü doğru bir şekilde oluşturabilmek için tüm ön yüzeylerin arka yüzeylerden önce işlenmesigerekmekteydi. Ve görünmez yüzeylerin eliminasyonu sırasında, yüzeylerin sıralanması gereği(ön yüzeyler önce, arka yüzeyler sonra) gecikmelere sebep olmaktadır. Bu çalışmada kullanılan CSG görüntü tekniği, yüzeylerin sıralanması gereğini hem konveks hem de konkav cisimler için ortadan kaldırmaktadır. Bu algoritma görüntü verilerini paralel bir şekilde işlemek için, her bir piksel üzerinde, o pikselin görünürlüğünün ve renginin belirleneceği özdeş işlemciler kullanılarak gerçekleştirilebilir. Anahtar Kelimeler. CSG, Yüzeylerin sıralanması, bilgisayar grafiği. vı

ABSTRACT DEVELOPMENT OF AN ALGORITHM FOR THE ELIMINATION OF SURFACE SORTING IN THE STAGE OF HIDDEN SURFACE REMOVAL IN DISPLAYING CONSTRUCTIVE SOLID GEOMETRY (CSG) VOLUMES AND SURFACES KOÇ, Sema M. Sc. In Electrical and Electronics Engineering Supervisor: Assist. Prof. Dr. Ulus ÇEVİK June 1999, 122 Pages The idea of using computer graphics in interactive systems has led to the need for solid-shaded images rather than line-based, or wire-frame pictures as they cause ambiguity in recognising the objects, being displayed. One of the most popular methods to model solid objects or volumes is CSG. Unbounded planes divide space into half-spaces. With this half spaces higher level intersection objects can be defined as convex solids or as their complements, which are convex holes or voids. More complex shaped volumes can be constructed from the union of collection of these convex units. In such an object, plane half-spaces oriented away from the viewpoint are called 'front surfaces' and oriented towards the viewpoint are called 'back surfaces'. The CSG scheme is used widely in many interactive computer graphics applications such as in computer games, flight simulators, and CAD tools. These applications require fast processing of data to machieve real-time interaction. In previous studies to obtain a correct image all the front surfaces of an object should have been processed before the back surfaces. The necessity of surface sorting (front surfaces first, back surfaces last) in the hidden surface removal stage may introduce significant delays. The CSG display technique that is used in this study, achieves the elimination of surface sorting for both convex and concave objects. This algorithm can be implemented in identical processors at each pixel, in which the visibility and colour of each pixel is determined, for parallel processing of image data. Keywords: CSG, Surface sorting, Computer graphics, Rendering IV