Sampling-sensitive multiresolution hierarchy for irregular meshes

Previous approaches of constructing multiresolution hierarchy for irregular meshes investigated how to overcome the connectivity and topology constraints during the decomposition, but did not consider the effects of sampling information on editing and signal processing operations. We propose a sampling-sensitive downsampling strategy and design a decomposition framework that produces a hierarchy of meshes with decreasing maximum sampling rates and increasingly regular vertex support sizes. The resulting mesh hierarchy has good quality triangles and enables more stable editing. The detail vectors better approximate the frequency spectrum of the mesh, thus making signal filtering more accurate.     

Multiresolution analysis on irregular surface meshes

Wavelet-based methods have proven their efficiency for visualization at different levels of detail, progressive transmission, and compression of large data sets. The required core of all wavelet-based methods is a hierarchy of meshes that satisfies subdivision-connectivity. This hierarchy has to be the result of a subdivision process starting from a base mesh. Examples include quadtree uniform 2D meshes, octree uniform 3D meshes, or 4-to-1 split triangular meshes. In particular, the necessity of subdivision-connectivity prevents the application of wavelet-based methods on irregular triangular meshes. In this paper, a “wavelet-like” decomposition is introduced that works on piecewise constant data sets over irregular triangular surface meshes. The decomposition/reconstruction algorithms are based on an extension of wavelet-theory allowing hierarchical meshes without property. Among others, this approach has the following features: it allows exact reconstruction of the data set, even for nonregular triangulations, and it extends previous results on Haar-wavelets over 4-to-1 split triangulations     

A process for surface fairing in irregular meshes

This paper describes a stepwise, automatic fairing process to construct a smooth surface by optimizing suitably chosen quantitative fairness measures. The input consists of given point and/or curve data, each designated to be interpolated or approximated. These data may stem from digitizing drawings or mockup models or from prior individual curve fairing. The data are arranged in an arbitrary irregular mesh topology. The irregular, n-sided mesh cells are converted by midpoint subdivision into aggregates of quadrilateral patches (Peters, 1994), for which a biquartic Bézier surface representation is chosen everywhere. The resulting C¹ surface minimizes the fairness measure, which is selected from a variety of geometrically relevant quadratic forms, including second and higher order derivative norms. This variational formulation of the fairing problem is of Quadratic Programming type and has a unique solution. Two algorithms are described, one for global, simultaneous and another for local, iterative solution of the corresponding large linear system of equations. This surface fairing technique will be illustrated by two main examples, viz., a car hood and a twisted tripod, demonstrating the performance of the fairing algorithms and the effects of the chosen fairness measures on the character of the resulting shapes.     

Smooth spline surface generation over meshes of irregular topology

An efficient method for generating a smooth spline surface over an irregular mesh is presented in this paper. Similar to the methods proposed by [1, 2, 3, 4], this method generates a generalised bi-quadratic B-spline surface and achieves C ¹ smoothness. However, the rules to construct the control points for the proposed spline surfaces are much simpler and easier to follow. The construction process consists of two steps: subdividing the initial mesh once using the Catmull–Clark [5] subdivision rules and generating a collection of smoothly connected surface patches using the resultant mesh. As most of the final mesh is quadrilateral apart from the neighbourhood of the extraordinary points, most of the surface patches are regular quadratic B-splines. The neighbourhood of the extraordinary points is covered by quadratic Zheng–Ball patches [6].     

Making Doo-Sabin surface interpolation always work over irregular meshes

This paper presents a reliable method for constructing a control mesh whose Doo-Sabin subdivision surface interpolates the vertices of a given mesh with arbitrary topology. The method improves on existing techniques in two respects: (1) it is guaranteed to always work for meshes of arbitrary topological type; (2) there is no need to solve a system of linear equations to obtain the control points. Extensions to include normal vector interpolation and/or shape adjustment are also discussed.     

A multiresolution representation for massive meshes

We present a new external memory multiresolution surface representation for massive polygonal meshes. Previous methods for building such data structures have relied on resampled surface data or employed memory intensive construction algorithms that do not scale well. Our proposed representation combines efficient access to sampled surface data with access to the original surface. The construction algorithm for the surface representation exhibits memory requirements that are insensitive to the size of the input mesh, allowing it to process meshes containing hundreds of millions of polygons. The multiresolution nature of the surface representation has allowed us to develop efficient algorithms for view-dependent rendering, approximate collision detection, and adaptive simplification of massive meshes. The empirical performance of these algorithms demonstrates that the underlying data structure is a powerful and flexible tool for operating on massive geometric data.     

Teaching meshes, subdivision and multiresolution techniques

In recent years, geometry processing algorithms that directly operate on polygonal meshes have become an indispensable tool in computer graphics, CAD/CAM applications, numerical simulations, and medical imaging. Because the demand for people that are specialized in these techniques increases steadily the topic is finding its way into the standard curricula of related lectures on computer graphics and geometric modeling and is often the subject of seminars and presentations. In this article we suggest a toolbox to educators who are planning to set up a lecture or talk about geometry processing for a specific audience. For this we propose a set of teaching blocks, each of which covers a specific subtopic. These teaching blocks can be assembled so as to fit different occasions like lectures, courses, seminars and talks and different audiences like students and industrial practitioners. We also provide examples that can be used to deepen the subject matter and give references to the most relevant work.     

Volume visualization of sparse irregular meshes

An algorithm that was designed for the data typically found in reservoir simulation and structural analysis is presented. Designed for general applicability and high efficiency, it can be used to visualize scalar volumes of irregular computational meshes. The algorithm accepts as input virtually any 3-D mesh used in computer simulations. Pictures of practical value can be drawn interactively     

Wavelet-based multiresolution analysis for data cleaning and its application to water quality management systems

Data cleaning techniques are useful for extracting desirable knowledge or interesting patterns from existing databases in engineering applications. The major problems of conventional techniques (e.g., Fourier Transformation Technique) are that they are (1) more appropriate in linear systems than nonlinear systems, and (2) stringently depend on state space functions. In this study a wavelet-based multiresolution analysis technique (WMAT) is proposed for reducing noises induced by complex uncertainty. The approach is applied to a river water quality simulation system for showing its practicability in data cleaning and parameter estimation. Clean data are prepared through running a Thomas’ river water quality model and polluted data are synthesized by mixing clean data with white Gaussian noises. The results show that WMAT will not distort the clean data, and can effectively reduce the noise in the polluted data. The data denoised by WMAT are furthermore used for estimating the modeling parameters. It is also indicated that the parameters estimated with the denoised data through WMAT are much closer to real values than those (1) with polluted data through WMAT and (2) with data through Fourier analysis technique. It is thus recommended that the prepared data be used for estimating the modeling parameters until being cleaned with WMAT.     

View-dependent refinement of multiresolution meshes using programmable graphics hardware

View-dependent multiresolution rendering places a heavy load on CPU. This paper presents a new method on view-dependent refinement of multiresolution meshes by using the computation power of modern programmable graphics hardware (GPU). Two rendering passes using this method are included. During the first pass, the level of detail selection is performed in the fragment shaders. The resultant buffer from the first pass is taken as the input texture to the second rendering pass by vertex texturing, and then the node culling and triangulation can be performed in the vertex shaders. Our approach can generate adaptive meshes in real-time, and can be fully implemented on GPU. The method improves the efficiency of mesh simplification, and significantly alleviates the computing load on CPU.     

n-Dimensional multiresolution representation of subdivision meshes with arbitrary topology

We present a new model for the representation of n-dimensional multiresolution meshes. It provides a robust topological representation of arbitrary meshes that are combined in closely interlinked levels of resolution. The proposed combinatorial model is formalized through the mathematical model of combinatorial maps allowing us to give a general formulation, in any dimensions, of the topological subdivision process that is a key issue to robustly and soundly define mesh hierarchies. It fully supports multiresolution edition what allows the implementation of most mesh processing algorithms – like filtering or compression – for n-dimensional meshes with arbitrary topologies.We illustrate this model, in dimension 3, with an new truly multiresolution representation of subdivision volumes. It allows us to extend classical subdivision schemes to arbitrary polyhedrons and to handle adaptive subdivision with an elegant solution to compliance issues. We propose an implementation of this model as an effective and relatively inexpensive data structure.     

Wavelet-based progressive compression scheme for triangle meshes: wavemesh

We propose a new lossy to lossless progressive compression scheme for triangular meshes, based on a wavelet multiresolution theory for irregular 3D meshes. Although remeshing techniques obtain better compression ratios for geometric compression, this approach can be very effective when one wants to keep the connectivity and geometry of the processed mesh completely unchanged. The simplification is based on the solving of an inverse problem. Optimization of both the connectivity and geometry of the processed mesh improves the approximation quality and the compression ratio of the scheme at each resolution level. We show why this algorithm provides an efficient means of compression for both connectivity and geometry of 3D meshes and it is illustrated by experimental results on various sets of reference meshes, where our algorithm performs better than previously published approaches for both lossless and progressive compression.     

Bayesian AD coder: Mesh-aware valence coding for multiresolution meshes

The Alliez Desbrun (AD) coder has accomplished the best compression ratios for multiresolution 2-manifold meshes in the last decade. This paper presents a Bayesian AD coder which has better compression ratios in connectivity coding than the original coder, based on a mesh-aware valence coding scheme for multiresolution meshes. In contrast to the original AD coder, which directly encodes a valence for each decimated vertex, our coder indirectly encodes the valence according to its rank in a sorted list with respect to the mesh-aware scores of the possible valences. Experimental results show that the Bayesian AD coder shows an improvement of 8.5-36.2% in connectivity coding compared to the original AD coder despite of the fact that a simple coarse-to-fine step of the mesh-aware valence coding is plugged into the original algorithm.     

Biquartic C-surface splines over irregular meshes

C¹-surface splines define tangent continuous surfaces from control points in the manner of tensor-product (B-)splines, but allow a wider class of control meshes capable of outlining arbitrary free-form surfaces with or without boundary. In particular, irregular meshes with non-quadrilateral cells and more or fewer than four cells meeting at a point can be input and are treated in the same conceptual frame work as tensor-product B-splines; that is, the mesh points serve as control points of a smooth piecewise polynomial surface representation that is local and evaluates by averaging. Biquartic surface splines extend and complement the definition of C¹-surface splines in a previous paper (Peters, J SLAM J. Numer. Anal. Vol 32 No 2 (1993) 645–666) improving continuity and shape properties in the case where the user chooses to model entirely with four-sided patches. While tangent continuity is guaranteed, it is shown that no polynomial, symmetry-preserving construction with adjustable blends can guarantee its surfaces to lie in the local convex hull of the control mesh for very sharp blends where three patches join. Biquartic C¹-surface splines do as well as possible by guaranteeing the property whenever more than three patches join and whenever the blend exceeds a certain small threshold.     

Convex multiresolution analysis

A standard wavelet multiresolution analysis can be defined via a sequence of projectors onto a monotone sequence of closed vector subspaces possessing certain properties. We propose a nonlinear extension of this framework in which the vector subspaces are replaced by convex subsets. These sets are chosen so as to provide a recursive, monotone approximation scheme that allows for various signal and image features to be investigated. Several classes of convex multiresolution analyses are discussed and numerical applications to signal and image-processing problems are demonstrated     

Implicit meshes for surface reconstruction

Deformable 3D models can be represented either as traditional explicit surfaces, such as triangulated meshes, or as implicit surfaces. Explicit surfaces are widely accepted because they are simple to deform and render, but fitting them involves minimizing a nondifferentiable distance function. By contrast, implicit surfaces allow fitting by minimizing a differentiate algebraic distance, but are harder to meaningfully deform and render. Here, we propose a method that combines the strength of both approaches. It relies on a technique that can turn a completely arbitrary triangulated mesh, such as one taken from the Web, into an implicit surface that closely approximates it and can deform in tandem with it. This allows both automated algorithms to take advantage of the attractive properties of implicit surfaces for fitting purposes and people to use standard deformation tools they feel comfortable for interaction and animation purposes. We demonstrate the applicability of our technique to modeling the human upper-body, including face, neck, shoulders, and ears, from noisy stereo and silhouette data.     

Refinement and coarsening of surface meshes

This paper presents an adaptation scheme for surface meshes. Both refinement and coarsening tools are based upon local retriangulation. They can maintain the geometric features of the given surface mesh and its quality as well. A mesh gradation tool to smooth out large size differences between neighboring (in space) mesh faces and a procedure to detect and resolve self-intersections in the mesh are also presented. Both are driven by an octree structure and make use of the presented refinement tool.     

Simplification of composite parametric surface meshes

This paper concerns the simplification of composite parametric surface meshes which conform to the boundary of each constituting patch. The goal is to eliminate the small edges which result from this boundary patch preserving constraint, provided that these small edges belong to an almost flat area. To this end, two tolerance areas with respect to the initial reference mesh are introduced to keep close to the surface. The reference mesh is then simplified and optimized (in terms of shape quality) so that the resulting mesh belongs to these tolerance areas. Several examples of surface meshes are provided in order to assess the efficiency of the simplification method.