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.     

Pseudo‐Spline Subdivision Surfaces

Pseudo‐splines provide a rich family of subdivision schemes with a wide range of choices that meet various demands for balancing the approximation power, the length of the support, and the regularity of the limit functions. Special cases of pseudo‐splines include uniform odd‐degree B‐splines and the interpolatory 2n‐point subdivision schemes, and the other pseudo‐splines fill the gap between these two families. In this paper we show how the refinement step of a pseudo‐spline subdivision scheme can be implemented efficiently using repeated local operations, which require only the data in the direct neighbourhood of each vertex, and how to generalize this concept to quadrilateral meshes with arbitrary topology. The resulting pseudo‐spline surfaces can be arbitrarily smooth in regular mesh regions and C¹ at extraordinary vertices as our numerical analysis reveals.     

A Local/Global Approach to Mesh Parameterization

We present a novel approach to parameterize a mesh with disk topology to the plane in a shape‐preserving manner. Our key contribution is a local/global algorithm, which combines a local mapping of each 3D triangle to the plane, using transformations taken from a restricted set, with a global “stitch” operation of all triangles, involving a sparse linear system. The local transformations can be taken from a variety of families, e.g. similarities or rotations, generating different types of parameterizations. In the first case, the parameterization tries to force each 2D triangle to be an as‐similar‐as‐possible version of its 3D counterpart. This is shown to yield results identical to those of the LSCM algorithm. In the second case, the parameterization tries to force each 2D triangle to be an as‐rigid‐as‐possible version of its 3D counterpart. This approach preserves shape as much as possible. It is simple, effective, and fast, due to pre‐factoring of the linear system involved in the global phase. Experimental results show that our approach provides almost isometric parameterizations and obtains more shape‐preserving results than other state‐of‐the‐art approaches. We present also a more general “hybrid” parameterization model which provides a continuous spectrum of possibilities, controlled by a single parameter. The two cases described above lie at the two ends of the spectrum. We generalize our local/global algorithm to compute these parameterizations. The local phase may also be accelerated by parallelizing the independent computations per triangle.     

Accurate Simplification of Multi‐Chart Textured Models

Scanning and acquisition methods produce highly detailed surface meshes that need multi‐chart parameterizations to reduce stretching and distortion. From these complex shape surfaces, high‐quality approximations are automatically generated by using surface simplification techniques. Multi‐chart textures hinder the quality of the simplification of these techniques for two reasons: either the chart boundaries cannot be simplified leading to a lack of geometric fidelity; or texture distortions and artefacts appear near the simplified boundaries. In this paper, we present an edge‐collapse based simplification method that provides an accurate, low‐resolution approximation from a multi‐chart textured model. For each collapse, the model is reparameterized by local bijective mappings to avoid texture distortions and chart boundary artefacts on the simplified mesh due to the geometry changes. To better apply the appearance attributes and to guarantee geometric fidelity, we drive the simplification process with the quadric error metrics weighted by a local area distortion measure.     

A Flexible Kernel for Adaptive Mesh Refinement on GPU

We present a flexible GPU kernel for adaptive on‐the‐fly refinement of meshes with arbitrary topology. By simply reserving a small amount of GPU memory to store a set of adaptive refinement patterns, on‐the‐fly refinement is performed by the GPU, without any preprocessing nor additional topology data structure. The level of adaptive refinement can be controlled by specifying a per‐vertex depth‐tag, in addition to usual position, normal, color and texture coordinates. This depth‐tag is used by the kernel to instanciate the correct refinement pattern, which will map a refined connectivity on the input coarse polygon. Finally, the refined patch produced for each triangle can be displaced by the vertex shader, using any kind of geometric refinement, such as Bezier patch smoothing, scalar valued displacement, procedural geometry synthesis or subdivision surfaces. This refinement engine does neither require multipass rendering nor any use of fragment processing nor special preprocess of the input mesh structure. It can be implemented on any GPU with vertex shading capabilities.     

Simplification of Articulated Meshes

We present a method for simplifying a polygonal character with an associated skeletal deformation such that the simplified character approximates the original shape well when deformed. As input, we require a set of example poses that are representative of the types of deformations the character undergoes and we produce a multi-resolution hierarchy for the simplified character where all simplified vertices also have associated skin weights. We create this hierarchy by minimizing an error metric for a simplified set of vertices and their skin weights, and we show that this quartic error metric can be effectively minimized using alternating quadratic minimization for the vertices and weights separately. To enable efficient GPU accelerated deformations of the simplified character, we also provide a method that guarantees the maximum number of bone weights per simplified vertex is less than a user specified threshold at all levels of the hierarchy.     

A New QEM for Parametrization of Raster Images

We present an image processing method that converts a raster image to a simplical two‐complex which has only a small number of vertices (base mesh) plus a parametrization that maps each pixel in the original image to a combination of the barycentric coordinates of the triangle it is finally mapped into. Such a conversion of a raster image into a base mesh plus parametrization can be useful for many applications such as segmentation, image retargeting, multi‐resolution editing with arbitrary topologies, edge preserving smoothing, compression, etc. The goal of the algorithm is to produce a base mesh such that it has a small colour distortion as well as high shape fairness, and a parametrization that is globally continuous visually and numerically. Inspired by multi‐resolution adaptive parametrization of surfaces and quadric error metric, the algorithm converts pixels in the image to a dense triangle mesh and performs error‐bounded simplification jointly considering geometry and colour. The eliminated vertices are projected to an existing face. The implementation is iterative and stops when it reaches a prescribed error threshold. The algorithm is feature‐sensitive, i.e. salient feature edges in the images are preserved where possible and it takes colour into account thereby producing a better quality triangulation.     

Feature Preserving Mesh Generation from 3D Point Clouds

We address the problem of generating quality surface triangle meshes from 3D point clouds sampled on piecewise smooth surfaces. Using a feature detection process based on the covariance matrices of Voronoi cells, we first extract from the point cloud a set of sharp features. Our algorithm also runs on the input point cloud a reconstruction process, such as Poisson reconstruction, providing an implicit surface. A feature preserving variant of a Delaunay refinement process is then used to generate a mesh approximating the implicit surface and containing a faithful representation of the extracted sharp edges. Such a mesh provides an enhanced trade‐off between accuracy and mesh complexity. The whole process is robust to noise and made versatile through a small set of parameters which govern the mesh sizing, approximation error and shape of the elements. We demonstrate the effectiveness of our method on a variety of models including laser scanned datasets ranging from indoor to outdoor scenes.     

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.     

Fast Parallel Construction of Smooth Surfaces from Meshes with Tri/Quad/Pent Facets

Polyhedral meshes consisting of triangles, quads, and pentagons and polar configurations cover all major sampling and modeling scenarios. We give an algorithm for efficient local, parallel conversion of such meshes to an everywhere smooth surface consisting of low‐degree polynomial pieces. Quadrilateral facets with 4‐valent vertices are ‘regular’ and are mapped to bi‐cubic patches so that adjacent bi‐cubics join C² as for cubic tensor‐product splines. The algorithm can be implemented in the vertex and geometry shaders of the GPU pipeline and does not use the fragment shader. Its implementation in DirectX 10 achieves conversion plus rendering at 659 frames per second with 42.5 million triangles per second on input of a model of 1300 facets of which 60% are not regular.     

Skeleton-based Variational Mesh Deformations

In this paper, a new free-form shape deformation approach is proposed. We combine a skeleton-based mesh deformation technique with discrete differential coordinates in order to create natural-looking global shape deformations. Given a triangle mesh, we first extract a skeletal mesh, a two-sided Voronoibased approximation of the medial axis. Next the skeletal mesh is modified by free-form deformations. Then a desired global shape deformation is obtained by reconstructing the shape corresponding to the deformed skeletal mesh. The reconstruction is based on using discrete differential coordinates. Our method preserves fine geometric details and original shape thickness because of using discrete differential coordinates and skeleton-based deformations. We also develop a new mesh evolution technique which allow us to eliminate possible global and local self-intersections of the deformed mesh while preserving fine geometric details. Finally, we present a multi-resolution version of our approach in order to simplify and accelerate the deformation process. In addition, interesting links between the proposed free-form shape deformation technique and classical and modern results in the differential geometry of sphere congruences are established and discussed.     

Dependency‐Free Parallel Progressive Meshes

The constantly increasing complexity of polygonal models in interactive applications poses two major problems. First, the number of primitives that can be rendered at real‐time frame rates is currently limited to a few million. Secondly, less than 45 million triangles—with vertices and normal—can be stored per gigabyte. Although the rendering time can be reduced using level‐of‐detail (LOD) algorithms, representing a model at different complexity levels, these often even increase memory consumption. Out‐of‐core algorithms solve this problem by transferring the data currently required for rendering from external devices. Compression techniques are commonly used because of the limited bandwidth. The main problem of compression and decompression algorithms is the only coarse‐grained random access. A similar problem occurs in view‐dependent LOD techniques. Because of the interdependency of split operations, the adaption rate is reduced leading to visible popping artefacts during fast movements. In this paper, we propose a novel algorithm for real‐time view‐dependent rendering of gigabyte‐sized models. It is based on a neighbourhood dependency‐free progressive mesh data structure. Using a per operation compression method, it is suitable for parallel random‐access decompression and out‐of‐core memory management without storing decompressed data.     

Multi‐Scale Geometry Interpolation

Interpolating vertex positions among triangle meshes with identical vertex‐edge graphs is a fundamental part of many geometric modelling systems. Linear vertex interpolation is robust but fails to preserve local shape. Most recent approaches identify local affine transformations for parts of the mesh, model desired interpolations of the affine transformations, and then optimize vertex positions to conform with the desired transformations. However, the local interpolation of the rotational part is non‐trivial for more than two input configurations and ambiguous if the meshes are deformed significantly. We propose a solution to the vertex interpolation problem that starts from interpolating the local metric (edge lengths) and mean curvature (dihedral angles) and makes consistent choices of local affine transformations using shape matching applied to successively larger parts of the mesh. The local interpolation can be applied to any number of input vertex configurations and due to the hierarchical scheme for generating consolidated vertex positions, the approach is fast and can be applied to very large meshes.     

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.     

Shape Decomposition using Modal Analysis

We introduce a novel algorithm that decomposes a deformable shape into meaningful parts requiring only a single input pose. Using modal analysis, we are able to identify parts of the shape that tend to move rigidly. We define a deformation energy on the shape, enabling modal analysis to find the typical deformations of the shape. We then find a decomposition of the shape such that the typical deformations can be well approximated with deformation fields that are rigid in each part of the decomposition. We optimize for the best decomposition, which captures how the shape deforms. A hierarchical refinement scheme makes it possible to compute more detailed decompositions for some parts of the shape.
Although our algorithm does not require user intervention, it is possible to control the process by directly changing the deformation energy, or interactively refining the decomposition as necessary. Due to the construction of the energy function and the properties of modal analysis, the computed decompositions are robust to changes in pose as well as meshing, noise, and even imperfections such as small holes in the surface.     

Two Simple Methods for Improving a Triangle Mesh Surface

We present two simple and efficient local methods that reposition vertices of a triangle mesh surface with the goal of producing good triangle shapes while preserving the enclosed volume and sharp features. The methods involve minimizing a quadratic energy functional with respect to variations in a tangent plane (or in the direction of a crease) at each free vertex. One of the methods is aimed at producing uniform angles, while the other method is designed to produce uniform triangle areas, or more generally, to force relative triangle areas to conform to curvature estimates or estimates of local feature size so that vertex density is low in flat spots and relatively high in regions of large curvature. Test results demonstrate the effectiveness of both methods, especially when combined.     

Fitting Sharp Features with Loop Subdivision Surfaces

Various methods have been proposed for fitting subdivision surfaces to different forms of shape data (e.g., dense meshes or point clouds), but none of these methods effectively deals with shapes with sharp features, that is, creases, darts and corners. We present an effective method for fitting a Loop subdivision surface to a dense triangle mesh with sharp features. Our contribution is a new exact evaluation scheme for the Loop subdivision with all types of sharp features, which enables us to compute a fitting Loop subdivision surface for shapes with sharp features in an optimization framework. With an initial control mesh obtained from simplifying the input dense mesh using QEM, our fitting algorithm employs an iterative method to solve a nonlinear least squares problem based on the squared distances from the input mesh vertices to the fitting subdivision surface. This optimization framework depends critically on the ability to express these distances as quadratic functions of control mesh vertices using our exact evaluation scheme near sharp features. Experimental results are presented to demonstrate the effectiveness of the method.     

Creating and Animating Subject‐Specific Anatomical Models

Creating and animating subject‐specific anatomical models is traditionally a difficult process involving medical image segmentation, geometric corrections and the manual definition of kinematic parameters. In this paper, we introduce a novel template morphing algorithm that facilitates three‐dimensional modelling and parameterization of skeletons. Target data can be either medical images or surfaces of the whole skeleton. We incorporate prior knowledge about bone shape, the feasible skeleton pose and the morphological variability in the population. This allows for noise reduction, bone separation and the transfer, from the template, of anatomical and kinematical information not present in the input data. Our approach treats both local and global deformations in successive regularization steps: smooth elastic deformations are represented by an as‐rigid‐as‐possible displacement field between the reference and current configuration of the template, whereas global and discontinuous displacements are estimated through a projection onto a statistical shape model and a new joint pose optimization scheme with joint limits.     

Streaming Surface Reconstruction Using Wavelets

We present a streaming method for reconstructing surfaces from large data sets generated by a laser range scanner using wavelets. Wavelets provide a localized, multiresolution representation of functions and this makes them ideal candidates for streaming surface reconstruction algorithms. We show how wavelets can be used to reconstruct the indicator function of a shape from a cloud of points with associated normals. Our method proceeds in several steps. We first compute a low‐resolution approximation of the indicator function using an octree followed by a second pass that incrementally adds fine resolution details. The indicator function is then smoothed using a modified octree convolution step and contoured to produce the final surface. Due to the local, multiresolution nature of wavelets, our approach results in an algorithm over 10 times faster than previous methods and can process extremely large data sets in the order of several hundred million points in only an hour.     

A Viewpoint-Dependent Approach to Ray Trace Free-Form Surfaces

For convincing realistic scenes objects with free‐form surfaces are essential. Especially for photorealistic rendering pure polygonal models are often not sufficient. We present a new kind of algorithm to render free‐form surfaces in a rendering system based on ray tracing. We describe a triangular patch as usual by its three points and normal vectors, but base the intersection calculation as well on the viewpoint of the camera (or, in general, on the ray itself). Hence, the shape of the object depends to some extent on the sampling rays. However, the resulting differences of, for instance, the shape of the silhouette to the shape of the corresponding shadow is usually not perceived by the observer of the rendered image. Because we perform a direct computation without a tessellation process, the resulting surface, its shadows, and its reflections appear smooth independent of the distance to the camera. Furthermore, the memory consumption depends only linearly on the number of input triangles. Special features like creases, T‐vertices, and darts are also well supported. The computed uv‐coordinates provide a direct means for texture mapping whose visual appearance improves significantly compared to triangle meshes of the same resolution.