Quadrilateral and Tetrahedral Stripification

Finding a 2-factor of a generic graph is a difficult problem and there are randomized algorithms proposed to solve this problem in O(n3) complexity. We propose algorithms that find a 2-factor of a graph, if one exists, for a restricted class of graphs in which all vertices have degree four or less, in O(n2) complexity where n is the number of vertices of the graph. Such graphs are actually dual graphs of quadrilateral and tetrahedral meshes that are widely used in graphics and visualization applications. We use the 2-factor of these graphs to find linear ordering of the primitives in the form of strips. Applications like compression, access and rendering of such data benefits a lot from such linear ordering. We use the similarity between the dual graphs of the quadrilateral and tetrahedral meshes to introduce a novel, unified graph based algorithm to produce quad and tetrahedral strip representations respectively. Further, by introducing a few additional vertices, we can represent the entire quad-surface using a single quad-strip loop. We can use a similar technique to reduce the number of tetrahedral strips, to represent the entire tetrahedral mesh.

Fast Interactive Rendering usint Single-strips

Representing a triangulated two manifold using a single triangle strip is an NP-complete problem. By introducing a few Steiner vertices, recent works find such a single-strip and hence a linear ordering of edge-connected triangles of the entire triangulation. In this paper, we highlight and exploit this linear order in efficient triangle-strip management for high-performance rendering. We present new algorithms to generate weighted single-strip representations that respect different constraint-based clustering of triangles. These functional constraints can be application dependent; for example, normal-based constraints for efficient visibility culling or spatial constraints for highly coherent vertex-caching. We also present a hierarchical single-strip management strategy for high-performance interactive 3D rendering.

Contacts: M. Gopi (gopi @ ics.uci.edu), Renato Pajarola (renato @ acm.org), Pablo Diaz-Gutierrez (pablo @ ics.uci.edu)

Point Based Rendering

In this paper we present a novel point-based rendering approach based on object-space point interpolation of densely sampled surfaces. We introduce the concept of a transformation-invariant covariance matrix of a set of points which can efficiently be used to determine splat sizes in a multiresolution point hierarchy. We also analyze continuous point interpolation in object-space, and we define a new class of parametrized blending kernels as well as a normalization procedure to achieve smooth blending. Furthermore, we present a hardware accelerated rendering algorithm based on texture mapping and a-blending as well as programmable vertex- and pixel-shaders. Experimental results show the high quality and rendering efficiency that is achieved by our approach.

Contacts: Renato Pajarola (pajarola @ ics.uci.edu), Miguel Sainz (msainz @ ics.uci.edu)

Depth-Image Meshing and Warping

In this paper we present a novel and efficient depth-image representation and warping technique based on a piece-wise linear approximation of the depth-image as a textured and simplified triangle mesh. We describe the application of a hierarchical triangulation method to generate view-dependent triangulated depth-meshes efficiently from reference depth-images, and propose a new hardware accelerated depth-image rendering technique that supports per-pixel weighted blending of multiple depth-images in real-time. Applications of our technique include image-based object representations and the use of depth-images in large scale walk-through visualization systems.

Contacts: Renato Pajarola (pajarola @ ics.uci.edu), Miguel Sainz (msainz @ ics.uci.edu)

Quadtree Based Triangulation of Irregular Points

Interactive visualization of large digital elevation models is of continuing interest in scientific visualization, GIS, and virtual reality applications. Taking advantage of the regular structure of grid digital elevation models, efficient hierarchical multiresolution triangulation and adaptive level-of-detail (LOD) rendering algorithms have been developed for interactive terrain visualization. Despite the higher triangle count, these approaches generally outperform mesh simplification methods that produce irregular triangulated network (TIN) based LOD representations. In this project we combine the advantage of a TIN based mesh simplification preprocess with high-performance quadtree based LOD triangulation and rendering at run-time. This QuadTIN called approach generates an efficient quadtree triangulation hierarchy over any irregular point set that may originate from irregular terrain sampling or from reducing oversampling in high-resolution grid digital elevation models.

Contacts: Renato Pajarola (pajarola @ ics.uci.edu), Roberto Lario (rlario @ dacya.ucm.es)

Dynamic Triangle Strips

DStrips is a simple and efficient method to dynamically manage and generate triangle strips for real-time viewdependent multiresolution meshing and rendering. Progressive view-dependent triangle mesh simplification and rendering is an important concept for interactive visualization environments. To minimize the rendering cost, triangle meshes are simplified to the maximal tolerated perceptual error. A further savings can be gained by using hardware optimized rendering primitives such as triangle strips. However, triangle strips have been rarely used successfully in interactive multiresolution meshes due to the costs involved with maintaining the coherency of the strips in the changing mesh. This paper introduces a new dynamic triangle stripping data structure and algorithm, DStrips, that is practical for use with multiresolution meshes. DStrips is aimed at preserving pre-computed triangle strips through changes in the mesh and generating reasonably good triangle strips in real-time. Furthermore, this data structure and algorithm can be easily adapted to any multiresolution mesh which has a face-to-edge/edge-to-face mapping. The presented approach is implemented on top of a real-time view-dependent meshing and rendering framework based on a half-edge data structure using progressive edge collapses and vertex splits. Direct comparisons are made to previous methods in triangle stripification of dynamic and static meshes.

Contacts: Renato Pajarola (pajarola @ ics.uci.edu), Michael Shafae (mshafae @ ics.uci.edu)

Efficient View-dependent Mesh Simplification and Rendering

In this paper we present an optimized view-dependent meshing framework for adaptive and continuous level-of-detail (LOD) rendering in real-time. Multiresolution triangle mesh representations are an important tool for adapting triangle mesh complexity in real-time rendering environments. Ideally for interactive visualization, a triangle mesh is simplified to the maximal tolerated perceptual error, and thus mesh simplification is view-dependent. This paper introduces an efficient hierarchical multiresolution triangulation framework based on a half-edge triangle mesh data structure, and presents an optimized computation of several view-dependent error metrics within that framework providing conservative error bounds. The presented approach called FastMesh, is highly efficient both in space and time cost, and it spends only a fraction of the time required for rendering to perform the error calculations and dynamic mesh updates.

Contacts: Renato Pajarola (pajarola @ ics.uci.edu), Chris DeCoro (cdecoro @ uci.edu), Michael Shafae (mshafae @ ics.uci.edu)

Multiresolution Isosurface Extraction

Multiresolution methods are becoming increasingly important tools for the interactive visualization of very large data sets. Multireso-lution isosurface visualization allows the user to explore volume data using simplified and coarse representations of the isosurface for overview images, and finer resolution in areas of high interest or when zooming into the data. Ideally, a coarse isosurface should have the same topological structure as the original. The topological genus of the isosurface is one important property which is often ne-glected in multiresolution algorithms. This results in uncontrolled topological changes which can occur whenever the level-of-detail is changed. The scope of this paper is to propose an efficient tech-nique which allows preservation of topology as well as controlled topology simplification in multiresolution isosurface extraction.

Contacts: Thomas Gerstner (gerstner @ iam.uni-bonn.de), Renato Pajarola (pajarola @ ics.uci.edu)

Progressive Triangle Mesh Compression

Most systems that support the visual interaction with 3D models use shape representations based on triangle meshes. The size of these representations imposes limits on applications, for which complex 3D models must be accessed remotely. Techniques for simplifying and compressing 3D models reduce the transmission time. Multi-resolution formats provide quick access to a crude model and then refine it progressively. Unfortunately, compared to the best non-progressive compression methods, previously proposed progressive refinement techniques impose a significant overhead when the full resolution model must be downloaded. The CPM (Compressed Progressive Meshes) approach proposed here eliminates this overhead. It uses a new technique, which refines the topology of the mesh in batches, which each increase the number of vertices by up to 50%. Less than an amortized total of 4 bits per triangle encode where and how the topological refinements should be applied. We estimate the position of new vertices from the positions of their topological neighbors in the less refined mesh using a new estimator that leads to representations of vertex coordinates that are 50% more compact than previously reported progressive geometry compression techniques.

Contacts: Renato Pajarola (pajarola @ ics.uci.edu)

Progressive Tetrahedral Mesh Compression

Irregular tetrahedral meshes, which are popular in many engineering and scientific applications, often contain a large number of vertices. A mesh of V vertices and T tetrahedra requires 48áV bits or less to store the vertex coordinates, 4áTálog2(V) bits to store the tetrahedra-vertex incidence relations, also called connectivity information, and káV bits to store the k-bit value samples associated with the vertices. Given that T is 5 to 7 times larger than V and that V often exceeds 323, the storage space required for the connectivity is larger than 300áV bits and thus dominates the overall storage cost. Our Òimplants sprayÓ compression approach introduced in this paper reduces this cost to about 30áV bits or less Ð a 10:1 compression ratio. Furthermore, implant spray supports the progressive refinement of a crude model through a series of vertex-splits operations.

Contacts: Renato Pajarola (pajarola @ ics.uci.edu)

Interactive Large Scale Terrain Visualization

Real-time rendering of triangulated surfaces has attracted growing interest in the last few years. However, interactive visu-alization of very large scale grid digital elevation models is still a hard problem. The graphics load must be controlled by an adaptive surface triangulation and by taking advantage of dif-ferent levels of detail. Furthermore, the management of the visi-ble scene requires efficient access to the terrain database. We describe a all-in-one visualization system which integrates adaptive triangulation, dynamic scene management and spatial data handling. The triangulation model is based on the restricted quadtree triangulation. Furthermore, we present new algorithms of the restricted quadtree triangulation. These include among others exact error approximation, progressive meshing, performance enhancements and spatial access.

Contacts: Xiaohong Bao (xbao @ ics.uci.edu), Renato Pajarola (pajarola @ ics.uci.edu)