Polygonal Approximation Algorithms for Multiresolution Modeling


In this project, we investigate different techniques for multiresolution modeling of complex graphical models. We especially investigate dynamic view-dependent visualization of complex graphical models containing millions of polygons. The models are architectural models, terrain models where walkthrough applications make sense. We also investigate stereoscopic visualization techniques for these models.

View Dependent Refinement of Polygonal Meshes

We implement a framework for view-dependent refinement of progressive meshes. We use a similar approach to Hoppe’s progressive mesh (PM) representation (ACM Comput. Graphics, Proceedings of SIGGRAPH’97, August 1997, pp. 189–198) for view-dependent refinement with a different algorithm for constructing PM representation. Our method is simple to implement and fast enough to achieve interactive frame rates for moderately complex models (models containing hundreds of thousands of polygons) on a machine with polygon rendering hardware. Moreover, our implementation allows changes to topology and achieves a simpler and sometimes more realistic refinements. We use the original mesh and perform edge collapses so that the detail level is adjusted to the desired level. Detail level is dictated by the view frustum, surface orientation and screen space error. For example, the portions of the mesh outside the viewing frustum (see Figure 1) or the parts that look away from you are refined to a lower detail level (see Figure 2). The refinement step also takes the screen space error into account; i.e., distant parts are fined more, flat areas refined more whereas silhouettes are refined less (see Figure 3). Our implementation allows changes to topology and achieves a simpler and sometimes more realistic refinements. For example, during the refinement, unconnected parts of the mesh can merge together (this depends on the underlying edge decimator. We used Garland's Simplification by Quadric Error Metrics).


Figure 1: Effect of viewing frustum culling in view-dependent refinement.


Figure 2: Effect of surface orientation in view-dependent refinement.


Figure 3: Effect of screen space error tolerance in view-dependent refinement

Below, you can see some animated view-dependent refinement examples. Green lines describes the viewing frustum according to a phantom camera, to demonstrate the view dependent refinement process. If the user does not spawn a phantom camera, the refinement process is done with respect to the normal camera whose image plane is the whole window.

Movies of Various Visualizations using View-dependent Refinement (in gzipped .mov and .mpg format)

Stereoscopic View-Dependent Visualization of Terrain Height Fields

We developed a framework for the stereoscopic view-dependent visualization of large scale terrain models. We use a quadtree-based multiresolution representation for the terrain data (see Figure 4). This structure is queried to obtain the view-dependent approximations of the terrain model at different levels of detail. In order not to lose depth information, which is crucial for the stereoscopic visualization, we make use of a different simplification criterion, namely, distance-based angular error threshold (see Figure 5). We also present an algorithm for the construction of stereo pairs in order to speed up the view-dependent stereoscopic visualization. The approach we use is the simultaneous generation of the triangles for two stereo images using a single draw-list so that the view frustum culling and vertex activation is done only once for each frame. The cracking problem is solved using the dependency information stored for each vertex. We eliminate the popping artifacts that can occur while switching between different resolutions of the data using morphing. Still frames from a monoscopic walkthrough over Grand Canyon is given in Figure 6.


Figure 4: The process flow diagram of the proposed framework for stereoscopic visualization. This diagram shows the invocation order of the presented algorithms. The data worked on by the processes in the dashed blocks are 1) the whole quad-tree, 2) the view-frustum culled data, 3) the activated blocks, and 4) the draw-list transferred.


Figure 5: Angular error threshold representation for vertex removal.


Figure 6: Still frames from a monoscopic walkthrough over Grand Canyon.

Project Publications

Journal Articles

  • Uğur Güdükbay and Türker Yılmaz, "Stereoscopic View-dependent Visualization of Terrain Height Fields," IEEE Transactions on Visualization and Computer Graphics, Vol. 8, No. 4, pp. 330-345, 2002. (pdf).

  • Uğur Güdükbay, Okan Arıkan, and Bülent Özgüç, "Visualizer: A Mesh Visualization System using View-dependent Refinement", Computers & Graphics, Vol. 26, No. 3, pp. 491-503, 2002. (pdf copy).

Conference Publications

  • Okan Arıkan and Uğur Güdükbay, "An Algorithm for Progressive Raytracing," in Lecture Notes in Computer Science (LNCS), Vol. 1909, Advances in Information Sciences (ADVIS'00), Edited by Tatyana Yakhno, pp. 248-256, Springer-Verlag, Berlin, 2000. (pdf copy).

  • Muhammet Mustafa Özdal, Uğur Güdükbay, and Bülent Özgüç, "Poligonal Model Optimizasyonu Üzerinde İyileştirmeler", 9. Sinyal İşleme ve Uygulamaları Kurultayı (SİU'01), Cilt I, pp. 348-353, Gazimagusa, TRNC, April 2001. (pdf copy).

  • Muhammet Mustafa Özdal and Uğur Güdükbay, "Improvements for Mesh Optimization Algorithm," in Proceedings of the Fifteenth International Symposium On Computer and Information Sciences, 43-51, Istanbul, Turkey, 11-13 October 2000. (pdf copy).

  • Okan Arıkan and Uğur Güdükbay, "Görüntüleyici: Bakış Açısına göre Basitleştirme Yapan bir Model Görüntüleme Sistemi" (in Turkish), Sinyal İşleme ve Uygulamaları Kurultayı (IEEE SİU'00), 506-511, June 2000. (pdf copy).

People:

  • Faculty
    • Uğur Güdükbay (Principal investigator)
  • Researchers
    • Turker Yilmaz (M.S. student)
    • Muhammet Mustafa Ozdal (M.S. student)
    • Okan Arikan (B.S. student)

Duration:

February 1999 - February 2001

Sponsor:

TUBITAK - Scientific and Technical Research Council of Turkey (Grant no: 198E018)

Budget:

~US$20,000)