A Framework for Synchronized Editing of Multiple Curve Representations

Editing curves and surfaces is difficult in part because their mathematical representations rarely correspond to most people's idea of a curve or surface. The implementation (and hence, behavior) of most manipulation tools is intertwined with a particular curve or surface representation; this can make reimplementing the tool with a different representation problematic. A system using a single representation must therefore either limit the types of tools available or convert existing tools to work on the system's representation.
In this paper we present a framework for editing curves or surfaces which supports multiple representations and ensures that they stay synchronized. As a proof of concept, we have created a curve editor which contains several tools each of which manipulate one of three different curve representations: polylines, NURBs, and multi-resolution B-splines.     

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.     

Para-Graph: Graph-Based Parameterization of Triangle Meshes with Arbitrary Genus

This paper describes a novel approach to the parameterization of triangle meshes representing 2‐manifolds with an arbitrary genus. A topology‐based decomposition of the shape is computed and used to segment the shape into primitives, which define a chart decomposition of the mesh. Then, each chart is parameterized using an extension of the barycentric coordinates method. The charts are all 0‐genus and can be of three types only, depending on the number of boundary components. The chart decomposition and the parameterization are used to define a shape graph where each node represents one primitive and the arcs code the adjacency relationships between the primitives. Conical and cylindrical primitives are coded together with their skeletal lines that are computed from and aligned with their parameterization. The application of the parameterization approach to remeshing guarantees that extraordinary vertices are localized only where two patches share a boundary and they are not scattered on the whole surface.     

Object Completion using k‐Sparse Optimization

We present a new method for the completion of partial globally‐symmetric 3D objects, based on the detection of partial and approximate symmetries in the incomplete input dataset. In our approach, symmetry detection is formulated as a constrained sparsity maximization problem, which is solved efficiently using a robust RANSAC‐based optimizer. The detected partial symmetries are then reused iteratively, in order to complete the missing parts of the object. A global error relaxation method minimizes the accumulated alignment errors and a non‐rigid registration approach applies local deformations in order to properly handle approximate symmetry. Unlike previous approaches, our method does not rely on the computation of features, it uniformly handles translational, rotational and reflectional symmetries and can provide plausible object completion results, even on challenging cases, where more than half of the target object is missing. We demonstrate our algorithm in the completion of 3D scans with varying levels of partiality and we show the applicability of our approach in the repair and completion of heavily eroded or incomplete cultural heritage objects.     

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.     

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.     

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.     

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.     

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.     

A Biorthogonal Wavelet Approach based on Dual Subdivision

In this paper a biorthogonal wavelet approach based on Doo‐Sabin subdivision is presented. In the dual subdivision like Doo‐Sabin scheme, all the old control vertices disappear after one subdivision step, which is a big challenge to the biorthogonal wavelet construction. In our approach, the barycenters of the V‐faces corresponding to the old vertices are selected as the vertices associated with the scaling functions to construct the scaling space. The lifting scheme is used to guarantee the fitting quality of the wavelet transform, and a local orthogonalization is introduced with a discrete inner product operation to improve the computation efficiency. Sharp feature modeling based on extended Doo‐Sabin subdivision rules is also discussed in the framework of our wavelet construction. The presented wavelet construction is proven to be stable and effective by the experimental results.     

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.     

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.     

Global Structure Optimization of Quadrilateral Meshes

We introduce a fully automatic algorithm which optimizes the high‐level structure of a given quadrilateral mesh to achieve a coarser quadrangular base complex. Such a topological optimization is highly desirable, since state‐of‐the‐art quadrangulation techniques lead to meshes which have an appropriate singularity distribution and an anisotropic element alignment, but usually they are still far away from the high‐level structure which is typical for carefully designed meshes manually created by specialists and used e.g. in animation or simulation. In this paper we show that the quality of the high‐level structure is negatively affected by helical configurations within the quadrilateral mesh. Consequently we present an algorithm which detects helices and is able to remove most of them by applying a novel grid preserving simplification operator (GP‐operator) which is guaranteed to maintain an all‐quadrilateral mesh. Additionally it preserves the given singularity distribution and in particular does not introduce new singularities. For each helix we construct a directed graph in which cycles through the start vertex encode operations to remove the corresponding helix. Therefore a simple graph search algorithm can be performed iteratively to remove as many helices as possible and thus improve the high‐level structure in a greedy fashion. We demonstrate the usefulness of our automatic structure optimization technique by showing several examples with varying complexity.     

Implicit Fitting Using Radial Basis Functions with Ellipsoid Constraint

Implicit planar curve and surface fitting to a set of scattered points plays an important role in solving a wide variety of problems occurring in computer graphics modelling, computer graphics animation, and computer assisted surgery. The fitted implicit surfaces can be either algebraic or non‐algebraic. The main problem with most algebraic surface fitting algorithms is that the surface fitted to a given data set is often unbounded, multiple sheeted, and disconnected when a high degree polynomial is used, whereas a low degree polynomial is too simple to represent general shapes. Recently, there has been increasing interest in non‐algebraic implicit surface fitting. In these techniques, one popular way of representing an implicit surface has been the use of radial basis functions. This type of implicit surface can represent various shapes to a high level of accuracy. In this paper, we present an implicit surface fitting algorithm using radial basis functions with an ellipsoid constraint. This method does not need to build interior and exterior layers for the given data set or to use information on surface normal but still can fit the data accurately. Furthermore, the fitted shape can still capture the main features of the object when the data sets are extremely sparse. The algorithm involves solving a simple general eigen‐system and a computation of the inverse or psedo‐inverse of a matrix, which is straightforward to implement.     

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.     

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.     

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.