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.     

Localized Quadrilateral Coarsening

In this paper we introduce a coarsening algorithm for quadrilateral meshes that generates quality, quad-only connectivity during level-of- coarsening creation. A novel aspect of this work is development and implementation of a localized adaptation of the polychord collapse operator to better control and preserve important surface components. We describe a novel weighting scheme for automatic deletion selection that considers surface attributes, as well as localized queue updates that allow for improved data structures and computational performance opportunities over previous techniques. Additionally, this work supports optional and intuitive user controls for tailored simplification results.     

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.     

Semi-regular Quadrilateral-only Remeshing from Simplified Base Domains

Semi-regular meshes describe surface models that exhibit a structural regularity that facilitates many geometric processing algorithms. We introduce a technique to construct semi-regular, quad-only meshes from input surface meshes of arbitrary polygonal type and genus. The algorithm generates a quad-only model through subdivision of the input polygons, then simplifies to a base domain that is homeomorphic to the original mesh. During the simplification, a novel hierarchical mapping method, keyframe mapping , stores specific levels-of-detail to guide the mapping of the original vertices to the base domain. The algorithm implements a scheme for refinement with adaptive resampling of the base domain and backward projects to the original surface. As a byproduct of the remeshing scheme, a surface parameterization is associated with the remesh vertices to facilitate subsequent geometric processing, i.e. texture mapping, subdivision surfaces and spline-based modeling.     

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.     

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.     

Animation‐Aware Quadrangulation

Geometric meshes that model animated characters must be designed while taking into account the deformations that the shape will undergo during animation. We analyze an input sequence of meshes with point‐to‐point correspondence, and we automatically produce a quadrangular mesh that fits well the input animation. We first analyze the local deformation that the surface undergoes at each point, and we initialize a cross field that remains as aligned as possible to the principal directions of deformation throughout the sequence. We then smooth this cross field based on an energy that uses a weighted combination of the initial field and the local amount of stretch. Finally, we compute a field‐aligned quadrangulation with an off‐the‐shelf method. Our technique is fast and very simple to implement, and it significantly improves the quality of the output quad mesh and its suitability for character animation, compared to creating the quad mesh based on a single pose. We present experimental results and comparisons with a state‐of‐the‐art quadrangulation method, on both sequences from 3D scanning and synthetic sequences obtained by a rough animation of a triangulated model.     

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.     

Contouring Discrete Indicator Functions

We present a method for calculating the boundary of objects from Discrete Indicator Functions that store 2‐material volume fractions with a high degree of accuracy. Although Marching Cubes and its derivatives are effective methods for calculating contours of functions sampled over discrete grids, these methods perform poorly when contouring non‐smooth functions such as Discrete Indicator Functions. In particular, Marching Cubes will generate surfaces that exhibit aliasing and oscillations around the exact surface. We derive a simple solution to remove these problems by using a new function to calculate the positions of vertices along cell edges that is efficient, easy to implement, and does not require any optimization or iteration. Finally, we provide empirical evidence that the error introduced by our contouring method is significantly less than is introduced by Marching Cubes.     

Discrete Critical Values: a General Framework for Silhouettes Computation

Many shapes resulting from important geometric operations in industrial applications such as Minkowski sums or volume swept by a moving object can be seen as the projection of higher dimensional objects. When such a higher dimensional object is a smooth manifold, the boundary of the projected shape can be computed from the critical points of the projection. In this paper, using the notion of polyhedral chains introduced by Whitney, we introduce a new general framework to define an analogous of the set of critical points of piecewise linear maps defined over discrete objects that can be easily computed. We illustrate our results by showing how they can be used to compute Minkowski sums of polyhedra and volumes swept by moving polyhedra.     

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.     

Variational Surface Approximation and Model Selection

We consider the problem of approximating an arbitrary generic surface with a given set of simple surface primitives. In contrast to previous approaches based on variational surface approximation, which are primarily concerned with finding an optimal partitioning of the input geometry, we propose to integrate a model selection step into the algorithm in order to also optimize the type of primitive for each proxy. Our method is a joint global optimization of both the partitioning of the input surface as well as the types and number of used shape proxies. Thus, our method performs an automatic trade‐off between representation complexity and approximation error without relying on a user supplied predetermined number of shape proxies. This way concise surface representations are found that better exploit the full approximative power of the employed primitive types.     

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.     

Particle Level Set Advection for the Interactive Visualization of Unsteady 3D Flow

Typically, flow volumes are visualized by defining their boundary as iso‐surface of a level set function. Grid‐based level sets offer a good global representation but suffer from numerical diffusion of surface detail, whereas particle‐based methods preserve details more accurately but introduce the problem of unequal global representation. The particle level set (PLS) method combines the advantages of both approaches by interchanging the information between the grid and the particles. Our work demonstrates that the PLS technique can be adapted to volumetric dye advection via streak volumes, and to the visualization by time surfaces and path volumes. We achieve this with a modified and extended PLS, including a model for dye injection. A new algorithmic interpretation of PLS is introduced to exploit the efficiency of the GPU, leading to interactive visualization. Finally, we demonstrate the high quality and usefulness of PLS flow visualization by providing quantitative results on volume preservation and by discussing typical applications of 3D flow visualization.