Görünmez çizgi ve görünmez yüzey algoritmalarının incelenmesi

Hidden line and hidden surface algorithms

Tez No: 66712
Yazar: TANSEL BOLAT
Danışmanlar: YRD. DOÇ. DR. HİKMET KOCABAŞ
Tez Türü: Yüksek Lisans
Konular: Makine Mühendisliği, Mechanical Engineering
Anahtar Kelimeler: Belirtilmemiş.
Yıl: 1997
Dil: Türkçe
Üniversite: İstanbul Teknik Üniversitesi
Enstitü: Fen Bilimleri Enstitüsü
Ana Bilim Dalı: Konstrüksiyon Ana Bilim Dalı
Bilim Dalı: Belirtilmemiş.
Sayfa Sayısı: 86

Özet

ÖZET CAD/CAM sistemlerinin kullanıcıya sunduğu en büyük avantajlarından biri görselliktir. Böylece CAD sadece bilgisayar yardımıyla çizim çizme olmayıp ürünlerin tüm tasarımını, otomasyonu, parametrik tasarımı, sonlu elemanlar yöntemleri gibi işlemleri sağlayan bir sistem olmaktadır. Bilgisayar grafiklerindeki en temel problem hayatta ele aldığımız herşey üç boyutlu olmasına karşılık iki boyutlu ekranda nasıl görüntüleneceğidir. Çok karışık tasarımlar üzerinde çalışılırken resim üzerinde birbirinin içinden geçen pek çok çizginin bulunması tasarım üzerinde çalışılmasını zorlaştırır. Görünmez çizgi ve yüzey algoritmaları üç boyutlu model görüntülerinin üzerindeki belirsizliği kaldırır. Görünmez çizgilerin silinmesi için kullanılan yöntemler esnasında hesaplamalar için çok fazla bir süre harcanır. Her bir çizgi veya yüzeyin konumu diğerlerinin hepsiyle karşılaştırılmak zorundadır. Bu yüzden algoritmaların çalışmaları ve aralarındaki ortak prensibi bulmak için girişimler sürdürülmektedir. Görünmez çizgi eliminasyon teknikleri nihai resmi meydana çıkarmak için iki çeşit yöntem ortaya koymaktadırlar. Birincisinde, ele alman kısımların herhangi bir yüzey tarafından örtülmediğinin hesaplanabilmesi için üç boyutlu sahnedeki her çizginin incelenmesinin gerekli olduğu fikrini ele almaktadır. Her çizgi her yüzeye karşı test edilir. Test sonucuna göre çizgi bölümleri görüntülenir. İkinci yöntemde ekranın değişik alanları çeşitli karar mekanizmalarıyla görünmez çizgi problemi çözülür. Her alan bir pencere olarak isimlendirilir. Pencerede hiçbir nesne yoksa pencere boş gözükür. Roberts tarafından geliştirilen algoritmada her kenar konveks çokyüzlünün bir parçası olmasını gerektirmektedir. İlk önce arkadaki yüzlerin aradan seçilmesiyle arka yüzdeki çokgenlerin bütün kenarları silinir. Sonra kalan kenarların herbirisi bir birlerini örtebileceklerinden herbir çokyüzlü ile karşılaştırılır. Diğer bir algoritma türü olan z-buffer'da her bir piksel için sınıflandırılmış z değerlerine gereksinim duyulur. Yenilenen buffer arka plan için piksel değerlerini başlatırken z-buffer en küçük z değerlerini başlangıç durumuna getirir. Yenilenen ve z-bufferların her ikisi de (x, y) piksel koordinatlarında gösterilir. Warnock algoritmasında problemin çözümü için pencere görüntüleri altbölünmelere bölünür. Pencerede tek çokgen bulunması gibi durumlar basitçe çözülebilir. Çokgenler kısmen birbirlerini kapsadıkları zaman çokgenler arasındaki ilişki analiz edilir. Eğer algoritma karar veremiyorsa pencere dört küçük pencereye bölünür ve aynı çözüm tekniği her pencereye uygulanır. Eğer bu bölünmüş pencerelerden biri hala karmaşık bulunuyorsa yine dört küçük pencereye bölünür. Bu tekrarlama problem çözülene veya pencerenin ekranda görüntülenemeyecek kadar küçük bir piksel noktasına düşünceye kadar sürer. Çokgenin pencereyle ilgili konumlan da karar vermede etkilidir. Çokgen pencerenin tamamen içinde, tamamen dışında, pencereyle kesişen veya pencereyi çevreleyen şeklinde olabilir. Pencerenin tamamen dışında yani ayrı konumunda bulunan çokgenler elenir. Diğer durumlarda konumlarına göre ele alınırlar. viii

Özet (Çeviri)

SUMMARY HIDDEN LINE AND HIDDEN SURFACE ALGORITHMS Since the early development of computer graphics, there is always a demand for images (of objects) enhanced by removing the hidden parts that would not be seen if objects were constructed from opaque material in real life. Edges and surfaces of a given object may be bidden (invisible) or visible in a given image depending on the viewing direction. The determination of hidden edges and surfaces is considered one of the most challenging problems in computer graphics. Its solution typically demands large amounts of computer time and memory space. Three-dimensional wire frame graphics becomes extremely difficult to interpret when the number of line segments involved grows large. There is ambiguity with even a small number of line segments as for instance in determining which panels of a wire frame cube are at the front of the cube and which are at the back side of it. Solid geometry can be produced in computer graphics by the process of hidden line removal. Figure 1 shows the difference between the wire frame display of a cube and the solid geometry view using a hidden-line algorithm. How does a hidden-line algorithm work? In the example in Figure 1, there are 12 line segments in the displayed object and no more than 9 of these should be displayed at any time. Three lines must be 'hidden', that is, not draw in the graphics rendition. This example of a cube has a particularly simple solution to the hidden line problem. It will be noted that three lines to be removed all emanate from one vertex of the cube: the most distant vertex from the viewer. The algorithm has therefore only to determine which of the eight vertexes is most distant from the eye position, that is, for which: (x-eye.x)2+(y-eye.y)2+(z-eye.z)2 has maximum value, and then not draw those lines that have this vertex as one of their end points. Figure 1 A wireframe cube versus a solid panel cubeThis method can be generalized to many convex volumes. The algorithm first determines which points are hidden and then the line segment connections to these points are depend on the orientation of the object for viewing. In this case the simple criterion for whether a point is hidden, that is, a search for the n most distant points (n being the number of points always hidden) is not applicable. The algorithms that eliminate the hidden parts for the line drawings are called hidden-line removal algorithms, and the algorithms that eliminate the hidden parts for area filled scenes are generally referred to as hidden-surface removal algorithms. Hidden-surface removal algorithms can produce the effects of hidden-line removal algorithms when they are restricted to monochrome graphics, and are therefore more general. The direct or brute force approach to hidden line/surface/solid removal requires large amounts of computing times. The position of each line or surface has to be compared with that of all the others, leading to a square-law combinatorial explosion. Therefore, extensive studies of existing algorithms have been pursued in an attempt to find the common underlying principles among these algorithms. Two main general principles can be identified. These are coherence and sorting. Objects and their related geometric models are more than a set of random discontinuities. They have some consistency both over the area of the image and over the time, from one frame to the next. Thus using this coherence between various frames can improve the efficiency of visualization algorithms. The solution to the of removing hidden edges and surfaces draws on various concepts from computing, mainly sorting, and geometric modeling, mainly projection and intersection. This problem can also be viewed as a visibility problem. Therefore, a clear understanding of it and its solution is useful and can be extended to solve relevant engineering problems. Consider, for example, the vision and path planning problems in robotics applications. In the vision problem, the camera location and orientation provide the viewing direction which, in turn, can be used to determine the hidden edges and surfaces of objects encountered in the robot working environment. In the path planning problem, the knowledge of when a given surface changes from visible to hidden (via finding silhouette edges and curves) can be utilized to find the minimum path of the robot and effector. Points on the surface where its status changes from visible to invisible or vice versa can be considered as critical points which the path planning algorithm can use as an input. Another example is the display of finite element meshes where the hidden elements removed. In this case, each element is treated as a planar polygon and the collection of elements that forms the meshed object, from a finite element point of view, forms a polyhedron from a computer graphics viewpoint. The earliest visible-line algorithm was developed by Roberts. It requires that each edge be part of the face of a convex polyhedron. First, back face culling is used to remove all edges shared by a pair of a polyhedron's back-facing polygons. Next, each remaining edge is compared with each polyhedron that might obscure it. Many polyhedra can be trivially eliminated from the comparison through extent testing: the XIextents of their projections may fail to overlap in x or y, or one object's extent may be farther back in z than is the other. Those polyhedra that are tested are compared in sequence with the edge. Because the polyhedra are convex, there is at most one contiguous group of points on any line that is blocked from the observer by any polyhedron. Thus, each polyhedron either obscures the edge totally or causes one or two pieces to remain. Any remaining pieces of the edge are compared with the next polyhedron. Roberts's visibility test is performed with a parametric version of the projector from the eye to a point on the edge being tested. He uses linear- programming approach to solve for those values of the line equation that cause projector to pass through a polyhedron, resulting in the invisibility of the endpoint. The projector passes through a polyhedron if it contains some point that is inside all the polyhedron's front faces. The z-Buffer Algorithm is also known as the depth-buffer algorithm. In addition to the frame (refresh) buffer, this algorithm requires a z buffer in which z values can be sorted for each pixel. The z buffer is initialized to the smallest z value, while the frame buffer is initialized to the background pixel value. Both the frame and z buffers are indexed by pixel coordinates (x, y). These coordinates are actually screen coordinates. The z-buffer algorithm works as follows. For each polygon in the scene, find all the pixels (x, y) that lie inside or on the boundaries of the polygon when projected onto the screen. For each of these pixels, calculate the depth z of the polygon at (x, y). If z > depth (x, y), the polygon is closer to the viewing eye than others already stored in the pixel. In this case, the z buffer is updated by setting the depth (x, y) to z. Similarly, the intensity of the frame buffer location corresponding to the pixel is updated to the intensity of the polygon at (x, y). After all the polygons have been processed, the frame buffer contains the solution. Warnock's algorithm is one of the first area-coherence algorithms. Essentially, this algorithm solves the hidden surface problem by recursively subdividing the image into subimages. It first attempts to solve the problem for a window that covers the entire image. Simple cases such as one polygon in the window or none at all are easily solved. If polygons overlap, the algorithm tries to analyze the relationship between the polygons and generates the display for the window. If the algorithm cannot decide easily, it subdivides the window into four smaller windows and applies the same solution technique to every window. If one of the four windows is still complex, it is further subdivided into four smaller windows. The recursion terminates if the hidden surface problem can be solved for all the windows or if the window becomes as small as a single pixel on the screen. In this, case, the intensity of the pixel is chosen equal to the polygon visible in the pixel. The subdivision process results in a window tree. Figure 2 shows the application of Warnock's algorithm. One would devise a rule that any window is recursively subdivided unless it contains two polygons. In Xllsuch a case, comparing the z depth of the polygons determines which one hides the other. Figure 2 Warnock's algorithm While the subdivision of the original window is governed by the complexity of the scene in Fig.2, the subdivision of any window into four equal windows makes the algorithm inefficient. A more efficient way would be to subdivide a window according to the complexity of the scene in the window. This is equivalent to subdividing a window into four unequal subwindows. The area-subdivision algorithms all follow the 'divide and conquer' strategy seen earlier in the line and polygon clipping algorithms. An area of the projection plane image is examined. If it is 'easy' to decide which polygon or polygons are visible in the area, the appropriate polygons are displayed. Otherwise the area is subdivided into smaller areas and the decision logic is recursively applied to each of the smaller areas. As the areas become smaller, fewer and fewer polygons will overlap each area, and ultimately a decision will be possible. This is clearly an image space approach. It exploits area coherence, the tendency for at least small areas of an image to be contained in at most a single polygon. At each stage in the recursive subdivision process, the projection of each polygon has one of four relationships to the area of interest (see Fig. 3): a) Surrounding polygons completely contain the (shaded) area of interest; b) Intersecting polygons intersect the area; xiuc) Contained polygons are completely inside the area; d) Disjoint polygons are completely outside the area. (a) Surrounding (b) Intersecting (c) Contained (d) Disjoint Figure 3 Four relations of polygon projections to an area element Disjoint polygons clearly have no influence on the area. The part of intersecting polygon that is outside the area is also irrelevant, while the part of an intersecting polygon that is interior to the area is the same as a contained polygon and can be treated as such. There are four cases in which a decision about an area can be made easily so it need not be further divided to be conquered. They are: 1. All of the polygons are disjoint from the area, so the background pixel value can be displayed in the area. 2. There is either only one intersecting or only one contained polygon. The area is first filled with the background pixel value and then the polygon is scan- converted. (On many displays it is more convenient to initially set the entire refresh buffer to the background.) If the polygon is intersecting, only the contained part is scan-converted. 3. There is a single surrounding polygon, but no intersecting or contained polygons. The area is filled with the pixel value of the surrounding polygon. 4. More than one polygon is intersecting, contained in, or surrounding the area, and at least one of them is a surrounding polygon. In this case we use a simple test to determine whether one of the surrounding polygon is in front of all the other polygons: the z coordinates of the planes of all surrounding, intersecting, and contained polygons are computed at the four corners of the area; if there is a surrounding polygon whose four such z-coordinates are smaller (closer to the viewpoint) than any of the other z-coordinates, then the entire area can be filled with the pixel value of this surrounding polygon. Algorithm always subdivides the area to simplify the problem. After subdivision, only contained and intersecting polygons need to be examined: surrounding and disjoint polygons of the original area remain surrounding and disjoint polygons of each subdivided area. Subdivision normally ends when the resolution of the display device has been reached: on a 512x512 raster display, at XIVmost nine subdivisions would be made. If after this maximum number of subdivisions none of cases 1 to 4 has occurred, then the depth of all relevant polygon is computed at the center of this pixel-sized indivisible area. The polygon with the smallest z-coordinate defines the shading of the area. Alternatively, for antialiasing, several further levels of subdivision could be used to determine the composite pixel value which blends together all polygons visible in the area. XV

Benzer Tezler

Tez No
84019
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
Yapısal katı geometri (CSG) hacim ve yüzeylerini görüntülemede görünmez yüzeylerin temizliği aşamasında oluşan yüzey sıralamasının ortadan kaldırılması için bir algoritmanın geliştirilmesi
SEMA KOÇ
Yüksek Lisans
İngilizce
1999
Elektrik ve Elektronik Mühendisliği Gaziantep Üniversitesi
Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ULUS ÇEVİK
Tez No
539817
Satellite based passive radar system
Uydu tabanlı pası̇f radar sı̇stemı̇
NİHAT MERT ÜNAL
Yüksek Lisans
İngilizce
2019
Elektrik ve Elektronik Mühendisliği Çankaya Üniversitesi
Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
Prof. Dr. YUSUF ZİYA UMUL
Tez No
230930
Görsel sanat etkinlikleriyle bütünleştirilmiş ilköğretim fen ve teknoloji öğretimi
Teaching science and technology subject with integration of science and visual art activities at primary schools
SUAT TÜRKOĞUZ
Doktora
Türkçe
2008
Eğitim ve Öğretim Dokuz Eylül Üniversitesi
İlköğretim Ana Bilim Dalı
PROF. DR. ZELİHA YAYLA
Tez No
736979
Çizgi filmde hayvan temsilleri: 'Benim Hayvanlarım' uygulama filmi
Animal representation in cartoon films 'My Animals' animated film
MELİSA SARIALİOĞLU
Yüksek Lisans
Türkçe
2022
Güzel Sanatlar Anadolu Üniversitesi
Animasyon Ana Sanat Dalı
PROF. HİKMET SOFUOĞLU
Tez No
803285
Narrative act in an architectural design studio: Studio altı | üstü
Mimari tasarım stüdyosunda anlatı eylemi: Stüdyo altı | üstü
PELİN GÜR
Yüksek Lisans
İngilizce
2023
Mimarlık TOBB Ekonomi ve Teknoloji Üniversitesi
Mimarlık Ana Bilim Dalı
PROF. DR. TAYYİBE NUR ÇAĞLAR
DR. ÖĞR. ÜYESİ SELDA BANCI

Geri Dön