Stream Surface Parametrization by Flow‐Orthogonal Front Lines

The generation of discrete stream surfaces is an important and challenging task in scientific visualization, which can be considered a particular instance of geometric modeling. The quality of numerically integrated stream surfaces depends on a number of parameters that can be controlled locally, such as time step or distance of adjacent vertices on the front line. In addition there is a parameter that cannot be controlled locally: stream surface meshes tend to show high quality, well‐shaped elements only if the current front line is “globally” approximately perpendicular to the flow direction. We analyze the impact of this geometric property and present a novel solution – a stream surface integrator that forces the front line to be perpendicular to the flow and that generates quad‐dominant meshes with well‐shaped and well‐aligned elements. It is based on the integration of a scaled version of the flow field, and requires repeated minimization of an error functional along the current front line. We show that this leads to computing the 1‐dimensional kernel of a bidiagonal matrix: a linear problem that can be solved efficiently. We compare our method with existing stream surface integrators and apply it to a number of synthetic and real world data sets.     

SD Models: Super‐Deformed Character Models

Super‐deformed, SD, is a specific artistic style for Japanese manga and anime which exaggerates characters in the goal of appearing cute and funny. The SD style characters are widely used, and can be seen in many anime, CG movies, or games. However, to create an SD model often requires professional skills and considerable time and effort. In this paper, we present a novel technique to generate an SD style counterpart of a normal 3D character model. Our approach uses an optimization guided by a number of constraints that can capture the properties of the SD style. Users can also customize the results by specifying a small set of parameters related to the body proportions and the emphasis of the signature characteristics. With our technique, even a novel user can generate visually pleasing SD models in seconds.     

Polygonal mesh watermarking using Laplacian coordinates

We propose a watermarking algorithm for polygonal meshes based on the modification of the Laplacian coordinates. More specifically, we first compute the Laplacian coordinates (x,y,z) of the mesh vertices, then construct the histogram of the lengths of the (x,y,z) vectors, and finally, insert the watermark by altering the shape of that histogram. The watermark extraction is carried out blindly, with no reference to the host model. The proposed method is more robust than several existing high capacity watermarking algorithms. In particular, it is able to resist attacks such as translations, rotations, uniform scaling and vertex reordering, due to the invariance of the histogram of the Laplacian vector lengths under such transformations. Compared to the existing robust watermarking methods, our experiments show that the proposed method can better resist common mesh editing attacks, due to the good behaviour of the Laplacian coordinates under such operations.     

Persistent Heat Signature for Pose‐oblivious Matching of Incomplete Models

Although understanding of shape features in the context of shape matching and retrieval has made considerable progress in recent years, the case for partial and incomplete models in presence of pose variations still begs a robust and efficient solution. A signature that encodes features at multi‐scales in a pose invariant manner is more appropriate for this case. The Heat Kernel Signature function from spectral theory exhibits this multi‐scale property. We show how this concept can be merged with the persistent homology to design a novel efficient pose‐oblivious matching algorithm for all models, be they partial, incomplete, or complete. We make the algorithm scalable so that it can handle large data sets. Several test results show the robustness of our approach.     

Dirichlet Harmonic Shape Compression with Feature Preservation for Parameterized Surfaces

With the rapid advancement of 3D scanning devices, large and complicated 3D shapes are becoming ubiquitous, and require large amount of resources to store and transmit them efficiently. This makes shape compression a demanding technique in order for the user to reduce the data transmission latency. Existing shape compression methods could achieve very low bit‐rates by sacrificing shape quality. But none of them guarantees the preservation of salient feature lines that users care. In addition, many 3D shapes come with parametric information for texture mapping purposes. In this paper we describe a spectral method to compress the geometric shapes equipped with arbitrary valid parametric information. It guarantees to preserve user‐specified feature lines while achieving a high compression ratio. By applying the spectral shape analysis – Dirichlet Manifold Harmonics, in the 2D parametric domain, this method provides a progressive compression mechanism to trade‐off between bit‐rate and shape quality. Experiments show that this method provides very low bit‐rate with high shape‐quality and still guarantees the preservation of user‐specified feature lines.     

Least Squares Subdivision Surfaces

The usual approach to design subdivision schemes for curves and surfaces basically consists in combining proper rules for regular configurations, with some specific heuristics to handle extraordinary vertices. In this paper, we introduce an alternative approach, called Least Squares Subdivision Surfaces (LS), where the key idea is to iteratively project each vertex onto a local approximation of the current polygonal mesh. While the resulting procedure haves the same complexity as simpler subdivision schemes, our method offers much higher visual quality, especially in the vicinity of extraordinary vertices. Moreover, we show it can be easily generalized to support boundaries and creases. The fitting procedure allows for a local control of the surface from the normals, making LS³ very well suited for interactive freeform modeling applications. We demonstrate our approach on diadic triangular and quadrangular refinement schemes, though it can be applied to any splitting strategies.     

Isosurfaces Over Simplicial Partitions of Multiresolution Grids

We provide a simple method that extracts an isosurface that is manifold and intersection‐free from a function over an arbitrary octree. Our method samples the function dual to minimal edges, faces, and cells, and we show how to position those samples to reconstruct sharp and thin features of the surface. Moreover, we describe an error metric designed to guide octree expansion such that flat regions of the function are tiled with fewer polygons than curved regions to create an adaptive polygonalization of the isosurface. We then show how to improve the quality of the triangulation by moving dual vertices to the isosurface and provide a topological test that guarantees we maintain the topology of the surface. While we describe our algorithm in terms of extracting surfaces from volumetric functions, we also show that our algorithm extends to generating manifold level sets of co‐dimension 1 of functions of arbitrary dimension.     

Localized Delaunay Refinement for Sampling and Meshing

The technique of Delaunay refinement has been recognized as a versatile tool to generate Delaunay meshes of a variety of geometries. Despite its usefulness, it suffers from one lacuna that limits its application. It does not scale well with the mesh size. As the sample point set grows, the Delaunay triangulation starts stressing the available memory space which ultimately stalls any effective progress. A natural solution to the problem is to maintain the point set in clusters and run the refinement on each individual cluster. However, this needs a careful point insertion strategy and a balanced coordination among the neighboring clusters to ensure consistency across individual meshes. We design an octtree based localized Delaunay refinement method for meshing surfaces in three dimensions which meets these goals. We prove that the algorithm terminates and provide guarantees about structural properties of the output mesh. Experimental results show that the method can avoid memory thrashing while computing large meshes and thus scales much better than the standard Delaunay refinement method.     

Improving the Parameterization of Approximate Subdivision Surfaces

We provide a method for improving the parameterization of patching schemes that approximate Catmull‐Clark subdivision surfaces, such that the new parameterization conforms better to that of the original subdivision surface. We create this reparameterization in real‐time using a method that only depends on the topology of the surface and is independent of the surface's geometry. Our method can handle patches with more than one extraordinary vertex and avoids the combinatorial increase in both complexity and storage associated with multiple extraordinary vertices. Moreover, the reparameterization function is easy to implement and fast.     

Scales and Scale‐like Structures

We present a method for generating scales and scale‐like structures on a polygonal mesh through surface replacement. As input, we require a triangular mesh that will be covered with scales and one or more proxy‐models to be used as the scale's shape. A user begins scale generation by drawing a lateral line on the model to control the distribution and orientation of scales on the surface. We then create a vector field over the surface to control an anisotropic Voronoi tessellation, which represents the region occupied by each scale. Next we replace these regions by cutting the proxy model to match the boundary of the Voronoi region and deform the cut model onto the surface. The result is a fully connected 2‐manifold that is suitable for subsequent post‐processing applications like surface subdivision.     

Noise‐Adaptive Shape Reconstruction from Raw Point Sets

We propose a noise‐adaptive shape reconstruction method specialized to smooth, closed shapes. Our algorithm takes as input a defect‐laden point set with variable noise and outliers, and comprises three main steps. First, we compute a novel noise‐adaptive distance function to the inferred shape, which relies on the assumption that the inferred shape is a smooth submanifold of known dimension. Second, we estimate the sign and confidence of the function at a set of seed points, through minimizing a quadratic energy expressed on the edges of a uniform random graph. Third, we compute a signed implicit function through a random walker approach with soft constraints chosen as the most confident seed points computed in previous step.     

Smooth Shape‐Aware Functions with Controlled Extrema

Functions that optimize Laplacian‐based energies have become popular in geometry processing, e.g. for shape deformation, smoothing, multiscale kernel construction and interpolation. Minimizers of Dirichlet energies, or solutions of Laplace equations, are harmonic functions that enjoy the maximum principle, ensuring no spurious local extrema in the interior of the solved domain occur. However, these functions are only C⁰ at the constrained points, which often causes smoothness problems. For this reason, many applications optimize higher‐order Laplacian energies such as biharmonic or triharmonic. Their minimizers exhibit increasing orders of continuity but lose the maximum principle and show oscillations. In this work, we identify characteristic artifacts caused by spurious local extrema, and provide a framework for minimizing quadratic energies on manifolds while constraining the solution to obey the maximum principle in the solved region. Our framework allows the user to specify locations and values of desired local maxima and minima, while preventing any other local extrema. We demonstrate our method on the smoothness energies corresponding to popular polyharmonic functions and show its usefulness for fast handle‐based shape deformation, controllable color diffusion, and topologically‐constrained data smoothing.     

Boundary Detection in Particle‐based Fluids

This paper presents a novel method to detect free‐surfaces on particle‐based volume representation. In contrast to most particle‐based free‐surface detection methods, which perform the surface identification based on physical and geometrical properties derived from the underlying fluid flow simulation, the proposed approach only demands the spatial location of the particles to properly recognize surface particles, avoiding even the use of kernels. Boundary particles are identified through a Hidden Point Removal (HPR) operator used for visibility test. Our method is very simple, fast, easy to implement and robust to changes in the distribution of particles, even when facing large deformation of the free‐surface. A set of comparisons against state‐of‐the‐art boundary detection methods show the effectiveness of our approach. The good performance of our method is also attested in the context of fluid flow simulation involving free‐surface, mainly when using level‐sets for rendering purposes.     

Designing Quad‐dominant Meshes with Planar Faces

We study the combined problem of approximating a surface by a quad mesh (or quad‐dominant mesh) which on the one hand has planar faces, and which on the other hand is aesthetically pleasing and has evenly spaced vertices. This work is motivated by applications in freeform architecture and leads to a discussion of fields of conjugate directions in surfaces, their singularities and indices, their optimization and their interactive modeling. The actual meshing is performed by means of a level set method which is capable of handling combinatorial singularities, and which can deal with planarity, smoothness, and spacing issues.     

Polar NURBS Surface with Curvature Continuity

Polar NURBS surface is a kind of periodic NURBS surface, one boundary of which shrinks to a degenerate polar point. The specific topology of its control‐point mesh offers the ability to represent a cap‐like surface, which is common in geometric modeling. However, there is a critical and challenging problem that hinders its application: curvature continuity at the extraordinary singular pole. We first propose a sufficient and necessary condition of curvature continuity at the pole. Then, we present constructive methods for the two key problems respectively: how to construct a polar NURBS surface with curvature continuity and how to reform an ordinary polar NURBS surface to curvature continuous. The algorithms only depend on the symbolic representation and operations of NURBS, and they introduce no restrictions on the degree or the knot vectors. Examples and comparisons demonstrate the applications of the curvature‐continuous polar NURBS surface in hole‐filling and free‐shape modeling.     

Structure‐Aware Mesh Decimation

We present a novel approach for the decimation of triangle surface meshes. Our algorithm takes as input a triangle surface mesh and a set of planar proxies detected in a pre‐processing analysis step, and structured via an adjacency graph. It then performs greedy mesh decimation through a series of edge collapse, designed to approximate the local mesh geometry as well as the geometry and structure of proxies. Such structure‐preserving approach is well suited to planar abstraction, i.e. extreme decimation approximating well the planar parts while filtering out the others. Our experiments on a variety of inputs illustrate the potential of our approach in terms of improved accuracy and preservation of structure.     

Large‐Scale Integer Linear Programming for Orientation Preserving 3D Shape Matching

We study an algorithmic framework for computing an elastic orientation‐preserving matching of non‐rigid 3D shapes. We outline an Integer Linear Programming formulation whose relaxed version can be minimized globally in polynomial time. Because of the high number of optimization variables, the key algorithmic challenge lies in efficiently solving the linear program. We present a performance analysis of several Linear Programming algorithms on our problem. Furthermore, we introduce a multiresolution strategy which allows the matching of higher resolution models.     

3D Skeletons: A State‐of‐the‐Art Report

Given a shape, a skeleton is a thin centered structure which jointly describes the topology and the geometry of the shape. Skeletons provide an alternative to classical boundary or volumetric representations, which is especially effective for applications where one needs to reason about, and manipulate, the structure of a shape. These skeleton properties make them powerful tools for many types of shape analysis and processing tasks. For a given shape, several skeleton types can be defined, each having its own properties, advantages, and drawbacks. Similarly, a large number of methods exist to compute a given skeleton type, each having its own requirements, advantages, and limitations. While using skeletons for two‐dimensional (2D) shapes is a relatively well covered area, developments in the skeletonization of three‐dimensional (3D) shapes make these tasks challenging for both researchers and practitioners. This survey presents an overview of 3D shape skeletonization. We start by presenting the definition and properties of various types of 3D skeletons. We propose a taxonomy of 3D skeletons which allows us to further analyze and compare them with respect to their properties. We next overview methods and techniques used to compute all described 3D skeleton types, and discuss their assumptions, advantages, and limitations. Finally, we describe several applications of 3D skeletons, which illustrate their added value for different shape analysis and processing tasks.