Point clouds and polygonal meshes are widely used when modeling real-world scenarios. Here, point clouds arise, for instance, from acquisition processes applied in various surroundings, such as reverse engineering, rapid prototyping, or cultural preservation. Based on these raw data, polygonal meshes are created to, for example, run various simulations. For such applications, the utilized meshes must be of high quality. This paper presents an algorithm to derive triangle meshes from unstructured point clouds. The occurring edges have a close to uniform length and their lengths are bounded from below. Theoretical results guarantee the output to be manifold, provided suitable input and parameter choices. Further, the paper presents several experiments establishing that the algorithms can compete with widely used competitors in terms of quality of the output and timing and the output is stable under moderate levels of noise. Additionally, we expand the algorithm to detect and respect features on point clouds as well as to remesh polyhedral surfaces, possibly with features. Supplementary material, an extended preprint, a link to a previously published version of the article, utilized models, and implementation details are made available online .

This paper presents a simple and effective two-stage mesh denoising algorithm, where in the first stage, face normal filtering is done by using bilateral normal filtering in a robust statistics framework. Tukey's bi-weight function is used as similarity function in the bilateral weighting, which is a robust estimator and stops the diffusion at sharp edges to retain features and removes noise from flat regions effectively. In the second stage, an edge-weighted Laplace operator is introduced to compute a differential coordinate. This differential coordinate helps the algorithm to produce a high-quality mesh without any face normal flips and makes the method robust against high-intensity noise.

This paper presents a two-stage mesh denoising algorithm. Unlike other traditional averaging approaches, our approach uses an element-based normal voting tensor to compute smooth surfaces. By introducing a binary optimization on the proposed tensor together with a local binary neighborhood concept, our algorithm better retains sharp features and produces smoother umbilical regions than previous approaches. On top of that, we provide a stochastic analysis on the different kinds of noise based on the average edge length. The quantitative results demonstrate that the performance of our method is better compared to state-of-the-art smoothing approaches.

Abstract This paper introduces a new approach to automatically generate pure quadrilateral patch layouts on manifold meshes. The algorithm is based on a careful construction of a singularity graph of a given input frame field or a given periodic global parameterization. A pure quadrilateral patch layout is then derived as a constrained minimum weight perfect matching of that graph. The resulting layout is optimal relative to a balance between coarseness and geometric feature alignment. We formulate the problem of finding pure quadrilateral patch layouts as a global optimization problem related to a well‐known concept in graph theory. The main advantage of the new method is its simplicity and its computation speed. Patch layouts generated by the present algorithm are high quality and are very competitive compared to current state of the art.

Creating motions of objects or characters that are physically plausible and follow an animator's intent is a key task in computer animation. The spacetime constraints paradigm is a valuable approach to this problem, but it suffers from high computational costs. Based on spacetime constraints, we propose a framework for controlling the motion of deformable objects that offers interactive response times. This is achieved by a model reduction of the underlying variational problem, which combines dimension reduction, multipoint linearization, and decoupling of ODEs. After a preprocess, the cost for creating or editing a motion is reduced to solving a number of one-dimensional spacetime problems, whose solutions are the wiggly splines introduced by Kass and Anderson [2008]. We achieve interactive response times through a new fast and robust numerical scheme for solving the one-dimensional problems that is based on a closed-form representation of the wiggly splines.

We present a new method for modeling discrete constant mean curvature (CMC) surfaces, which arise frequently in nature and are highly demanded in architecture and other engineering applications. Our method is based on a novel use of the CVT ( centroidal Voronoi tessellation ) optimization framework. We devise a CVT-CMC energy function defined as a combination of an extended CVT energy and a volume functional. We show that minimizing the CVT-CMC energy is asymptotically equivalent to minimizing mesh surface area with a fixed volume, thus defining a discrete CMC surface. The CVT term in the energy function ensures high mesh quality throughout the evolution of a CMC surface in an interactive design process for form finding. Our method is capable of modeling CMC surfaces with fixed or free boundaries and is robust with respect to input mesh quality and topology changes. Experiments show that the new method generates discrete CMC surfaces of improved mesh quality over existing methods.

We introduce hexagonal global parameterization, a new type of surface parameterization in which parameter lines respect sixfold rotational symmetries (6-RoSy). Such parameterizations enable the tiling of surfaces with nearly regular hexagonal or triangular patterns, and can be used for triangular remeshing. Our framework to construct a hexagonal parameterization, referred to as HEXCOVER, extends the QUADCOVER algorithm and formulates necessary conditions for hexagonal parameterization. We also provide an algorithm to automatically generate a 6-RoSy field that respects directional and singularity features in the surface. We demonstrate the usefulness of our geometry-aware global parameterization with applications such as surface tiling with nearly regular textures and geometry patterns, as well as triangular and hexagonal remeshing.

Abstract Discrete Laplace–Beltrami operators on polyhedral surfaces play an important role for various applications in geometry processing and related areas like physical simulation or computer graphics. While discretizations of the weak Laplace–Beltrami operator are well‐studied, less is known about the strong form. We present a principle for constructing strongly consistent discrete Laplace–Beltrami operators based on the cotan weights. The consistency order we obtain, improves previous results reported for the mesh Laplacian. Furthermore, we prove consistency of the discrete Willmore energies corresponding to the discrete Laplace–Beltrami operators.

Abstract Despite the success of quad‐based 2D surface parameterization methods, effective parameterization algorithms for 3D volumes with cubes, i.e. hexahedral elements, are still missing. C ube C over is a first approach for generating a hexahedral tessellation of a given volume with boundary aligned cubes which are guided by a frame field. The input of C ube C over is a tetrahedral volume mesh. First, a frame field is designed with manual input from the designer. It guides the interior and boundary layout of the parameterization. Then, the parameterization and the hexahedral mesh are computed so as to align with the given frame field. C ube C over has similarities to the Q uad C over algorithm and extends it from 2D surfaces to 3D volumes. The paper also provides theoretical results for 3D hexahedral parameterizations and analyses topological properties of the appropriate function space.

Abstract Multiresolution meshes provide an efficient and structured representation of geometric objects. To increase the mesh resolution only at vital parts of the object, adaptive refinement is widely used. We propose a lossless compression scheme for these adaptive structures that exploits the parent–child relationships inherent to the mesh hierarchy. We use the rules that correspond to the adaptive refinement scheme and store bits only where some freedom of choice is left, leading to compact codes that are free of redundancy. Moreover, we extend the coder to sequences of meshes with varying refinement. The connectivity compression ratio of our method exceeds that of state‐of‐the‐art coders by a factor of 2–7. For efficient compression of vertex positions we adapt popular wavelet‐based coding schemes to the adaptive triangular and quadrangular cases to demonstrate the compatibility with our method. Akin to state‐of‐the‐art coders, we use a zerotree to encode the resulting coefficients. Using improved context modelling we enhanced the zerotree compression, cutting the overall geometry data rate by 7% below those of the successful Progressive Geometry Compression. More importantly, by exploiting the existing refinement structure we achieve compression factors that are four times greater than those of coders which can handle irregular meshes.

We propose a framework for deformation-based surface modeling that is interactive, robust, and intuitive to use. The deformations are described by a nonlinear optimization problem that models static states of elastic shapes under external forces which implement the user input. Interactive response is achieved by a combination of model reduction, a robust energy approximation, and an efficient quasi-Newton solver. Motivated by the observation that a typical modeling session requires only a fraction of the full shape space of the underlying model, we use second and third derivatives of a deformation energy to construct a low-dimensional shape space that forms the feasible set for the optimization. Based on mesh coarsening, we propose an energy approximation scheme with adjustable approximation quality. The quasi-Newton solver guarantees superlinear convergence without the need of costly Hessian evaluations during modeling. We demonstrate the effectiveness of the approach on different examples including the test suite introduced in Sorkine [2008].

This sketch introduces hexagonal global parameterization, a new type of periodic global parameterization that is ideal for tiling surfaces with patterns of six-fold rotational symmetries, i.e., 6-RoSy's [Palacios and Zhang 2007]. Being one of the two most fundamental rotational symmetries that are compatible with translational symmetries in the plane, 6-RoSy's appear in many places in nature, such as honeycombs, insect eyes, corals and crystals, as well as man-made objects such as Islamic patterns [Kaplan and Salesin 2004] and tri-axial weaving [Akleman et al. 2009]. Such symmetries can also provide optimal circle packing, which naturally have applications in architectural design [Schiftner et al. 2009]. A hexagonal global parameterization facilitates all of these applications. See Figure 1 for some examples. Furthermore, parameter lines in a hexagonal global parameterization intersect at an angle of π/3, which enables triangular remeshing of a mesh surface with close to ideal aspect ratios in the triangles. The dual mesh of such a triangulation provides a hexagon-dominant tiling of the surface.

We study discrete curvatures computed from nets of curvature lines on a given smooth surface and prove their uniform convergence to smooth principal curvatures. We provide explicit error bounds, with constants depending only on properties of the smooth limit surface and the shape regularity of the discrete net.

Abstract Complex‐valued functions are fundamental objects in complex analysis, algebra, differential geometry and in many other areas such as numerical mathematics and physics. Visualizing complex functions is a non‐trivial task since maps between two‐dimensional spaces are involved whose graph would be an unhandy submanifold in four‐dimensional space. The present paper improves the technique of “domain coloring” in several aspects: First, we lift domain coloring from the complex plane to branched Riemann surfaces, which are essentially the correct domain for most complex functions. Second, we extend domain coloring to the visualization of general 2‐valued maps on surfaces. As an application of such general maps we visualize the Gauss map of surfaces as domain colored plots and establish a link to current surface parametrization techniques and texture maps. Third, we adjust the color pattern in domain and in image space to produce higher quality domain colorings. The new color schemes specifically enhance the display of singularities, symmetries and path integrals, and give better qualitative measures of the complex map.

Mesh parameterization is a powerful geometry processing tool with numerous computer graphics applications, from texture mapping to animation transfer. This course outlines its mathematical foundations, describes recent methods for parameterizing meshes over various domains, discusses emerging tools like global parameterization and inter-surface mapping, and demonstrates a variety of parameterization applications.

We present a method for parametric reconstruction of a piecewise defined pipe surface, consisting of cylinder and torus segments, from an unorganized point set. Our main contributions are reconstruction of the spine curve of a pipe surface from surface samples, and approximation of the spine curve by G^1 continuous circular arcs and line segments. Our algorithm accurately outputs the parametric data required for bending machines to create the reconstructed tube.

Abstract We introduce an algorithm for the automatic computation of global parameterizations on arbitrary simplicial 2‐manifolds, whose parameter lines are guided by a given frame field, for example, by principal curvature frames. The parameter lines are globally continuous and allow a remeshing of the surface into quadrilaterals. The algorithm converts a given frame field into a single vector field on a branched covering of the 2‐manifold and generates an integrable vector field by a Hodge decomposition on the covering space. Except for an optional smoothing and alignment of the initial frame field, the algorithm is fully automatic and generates high quality quadrilateral meshes.

We present a new algorithm for fairing of space curves with respect spatial constraints based on a vector valued curvature function. Smoothing with the vector valued curvature function is superior to standard Frenet techniques since the individual scalar components can be modeled similar to curvature-based curve smoothing techniques in 2D. This paper describes a curve smoothing flow that satisfies strict spatial constraints and allows simultaneous control of both curvature functions.

We introduce FreeLence, a novel and simple single-rate compression coder for triangle manifold meshes. Our method uses free valences and exploits geometric information for connectivity encoding. Furthermore, we introduce a novel linear prediction scheme for geometry compression of 3D meshes. Together, these approaches yield a significant entropy reduction for mesh encoding with an average of 20-30 % over leading single-rate regiongrowing coders, both for connectivity and geometry.

Abstract A new method for noise removal of arbitrary surfaces meshes is presented which focuses on the preservation and sharpening of non‐linear geometric features such as curved surface regions and feature lines. Our method uses a prescribed mean curvature flow (PMC) for simplicial surfaces which is based on three new contributions: 1. the definition and efficient calculation of a discrete shape operator and principal curvature properties on simplicial surfaces that is fully consistent with the well‐known discrete mean curvature formula, 2. an anisotropic discrete mean curvature vector that combines the advantages of the mean curvature normal with the special anisotropic behaviour along feature lines of a surface, and 3. an anisotropic prescribed mean curvature flow which converges to surfaces with an estimated mean curvature distribution and with preserved non‐linear features. Additionally, the PMC flow prevents boundary shrinkage at constrained and free boundary segments.

WELCOME to the special section on Mathematics and Visualization. Mathematics is becoming an increasingly important tool in visualization, aiding the development and analysis of efficient algorithms and data structures. As visualization is beginning to evolve into a mature science and the underlying technology is becoming increasingly complex, the need for a rigorous framework is becoming obvious. Formal mathematical language provides a solid ground which allows us to embed visualization problems within an abstract setting and thereby to make well-established analytical tools applicable. For example, convergence issues and the numerical stability of visualization algorithms are essential for effective and reliable results in visualization. The editors of this special section have actively supported the convergence of mathematics and visualization as organizers of the international conference series Visualization and Mathematics since 1995, the film festival VideoMath at the International Congress of Mathematicians ICM 1998, as well as at various international workshops and summer schools. These activities helped to establish a small but worldwide community of researchers who perform work in this border area; they also gave rise to the new book series Mathematics + Visualization and the videoseries VideoMATH published by Springer Verlag. In particular, the international conference series Visualization and Mathematics in Berlin intensified the interaction of mathematicians and scientists from computer graphics and visualization. The current special section is comprised of a set of five carefully selected articles which are elaborated publications of the latest conference in 2002. In order to emphasize the interdisciplinary character of the young scientific field of mathematical visualization, the articles in this special section were selected to cover a broad range of topics from theory to praxis. The papers include topics from discrete and differential geometry, combinatorial and differential topology, graph theory, vector field analysis, geometry compression, image processing, signal processing, feature detection, image segmentation, numerical methods, and partial differential equations. The articles were selected by the editors of this special section and each carefully reviewed by at least three referees. In the following, we summarize the articles. “Applications of Forman’s Discrete Morse Theory to Topology Visualization and Mesh Compression” by Thomas Lewiner, Heio Lopes and Geovan Tavares: Many advances in science arise from the combination of different fields. Lewiner et al. relate Forman’s discrete geometry, a purely mathematical construction, with popular mesh compression schemes, such as Edgebreaker. This link unveils a new topological view on compression algorithms. The introduction of Forman’s discrete Morse theory and vector fields provides a new tool for topology visualization and the understanding of visualization algorithms. “Visualizing a Sphere Eversion” by George Francis and John M. Sullivan: Finding a process to turn a sphere inside out has been an active research area for geometers and topologists for more than 50 years. Mathematical visualization—using computer graphics tools, numerical algorithms, and geometric invention—provides an adequate collection of techniques to calculate and visualize the complex deformations of the eversion process. Here, mathematical visualization provides insight into abstract constructions and explains mathematics to a broader audience. The paper by Francis and Sullivan provides a glimpse of the exciting history of the sphere eversion problem and presents the underlying techniques of the author’s awarded computer graphics animation “Optiverse.” “Robust Feature Detection and Local Classification for Surfaces Based on Moment Analysis” by Ulrich Clarenz, Martin Rumpf, and Alex Telea: Geometry analysis and processing has become a major topic in computer graphics, as well as feature detection in visualization. The authors present a surface classification method for triangulated surfaces, with applications in surface fairing, mesh decimation, surface segmentation, and surface matching. The method uses local zero and first order moments as an alternative to curvature and utilizes structure tensor-like concepts. The method is well-founded, explained in detail, and shows convincing performance under various conditions. It provides an indicator for the smoothness of a given discrete surface and comes together with a built-in multiscale. Interesting aspects are the difference between the computation of moments in the smooth and nonsmooth surface as well as the analysis of how the moments scale with the scale parameter for smooth and nonsmooth areas. “Fast Evolution of Image Manifolds and Application to Filtering and Segmentation in 3D Medical Images” by Thomas Deschamps, Ravi Malladi, and Igor Ravve: Image analysis techniques are interesting in visualization as they represent “feature detection” methods for one major data type, namely, images. Additionally, many of IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, VOL. 10, NO. 5, SEPTEMBER/OCTOBER 2004 497

No abstract available.

We consider interpolation between keyframe hierarchies. We impose a set of weak constraints that allows smooth interpolation between two keyframe hierarchies in an animation or, more generally, allows the interpolation in an n-parameter family of hierarchies. We use hierarchical triangulations obtained by the Rivara element bisection algorithm (M. Rivara, 1984) and impose a weak compatibility constraint on the set of root elements of all keyframe hierarchies. We show that the introduced constraints are rather weak. The strength of our approach is that the interpolation works in the class of conforming triangulations and simplifies the task of finding the intermediate hierarchy, which is the union of the two (or more) keyframe hierarchies involved in the interpolation process. This allows for an efficient generation of the intermediate connectivity and additionally ensures that the intermediate hierarchy is again a conforming hierarchy satisfying the same constraints.