Local Painting and Deformation of Meshes on the GPU

We present a novel method to adaptively apply modifications to scene data stored in GPU memory. Such modifications may include interactive painting and sculpting operations in an authoring tool, or deformations resulting from collisions between scene objects detected by a physics engine. We only allocate GPU memory for the faces affected by these modifications to store fine‐scale colour or displacement values. This requires dynamic GPU memory management in order to assign and adaptively apply edits to individual faces at runtime. We present such a memory management technique based on a scan‐operation that is efficiently parallelizable. Since our approach runs entirely on the GPU, we avoid costly CPU–GPU memory transfer and eliminate typical bandwidth limitations. This minimizes runtime overhead to under a millisecond and makes our method ideally suited to many real‐time applications such as video games and interactive authoring tools. In addition, our algorithm significantly reduces storage requirements and allows for much higher resolution content compared to traditional global texturing approaches. Our technique can be applied to various mesh representations, including Catmull–Clark subdivision surfaces, as well as standard triangle and quad meshes. In this paper, we demonstrate several scenarios for these mesh types where our algorithm enables adaptive mesh refinement, local surface deformations and interactive on‐mesh painting and sculpting.     

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.     

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.     

Motorcycle Graphs: Canonical Quad Mesh Partitioning

We describe algorithms for canonically partitioning semi‐regular quadrilateral meshes into structured submeshes, using an adaptation of the geometric motorcycle graph of Eppstein and Erickson to quad meshes. Our partitions may be used to efficiently find isomorphisms between quad meshes. In addition, they may be used as a highly compressed representation of the original mesh. These partitions can be constructed in sublinear time from a list of the extraordinary vertices in a mesh. We also study the problem of further reducing the number of submeshes in our partitions—we prove that optimizing this number is NP‐hard, but it can be efficiently approximated.     

Approximate on‐Surface Distance Computation using Quasi‐Developable Charts

There is a vast number of applications that require distance field computation over triangular meshes. State‐of‐the‐art algorithms have quadratic or sub‐quadratic worst‐case complexity, making them impractical for interactive applications. While most of the research on this subject has been focused on reducing the computation complexity of the algorithms, in this work we propose an approximate algorithm that achieves similar results working in lower resolutions of the input meshes. The creation of lower resolution meshes is the essence of our proposal. The idea is to identify regions on the input mesh that can be unfolded into planar regions with minimal area distortion (i.e. quasi‐developable charts). Once charts are computed, their interior is re‐triangulated to reduce the number of triangles, which results in a collection of simplified charts that we call a base mesh. Due to the properties of quasi‐developable regions, we are able to compute distance fields over the base mesh instead of over the input mesh. This reduces the memory footprint and data processed for distance computations, which is the bottleneck of these algorithms. We present results that are one order of magnitude faster than current exact solutions, with low approximation errors.     

B‐Mesh: A Modeling System for Base Meshes of 3D Articulated Shapes

This paper presents a novel modeling system, called B‐Mesh, for generating base meshes of 3D articulated shapes. The user only needs to draw a one‐dimensional skeleton and to specify key balls at the skeletal nodes. The system then automatically generates a quad dominant initial mesh. Further subdivision and evolution are performed to refine the initial mesh and generate a quad mesh which has good edge flow along the skeleton directions. The user can also modify and manipulate the shape by editing the skeleton and the key balls and can easily compose new shapes by cutting and pasting existing models in our system. The mesh models generated in our system greatly benefit the sculpting operators for sculpting modeling and skeleton‐based animation.     

Practical quad mesh simplification

In this paper we present an innovative approach to incremental quad mesh simplification, i.e. the task of producing a low complexity quad mesh starting from a high complexity one. The process is based on a novel set of strictly local operations which preserve quad structure. We show how good tessellation quality (e.g. in terms of vertex valencies) can be achieved by pursuing uniform length and canonical proportions of edges and diagonals. The decimation process is interleaved with smoothing in tangent space. The latter strongly contributes to identify a suitable sequence of local modification operations. The method is naturally extended to manage preservation of feature lines (e.g. creases) and varying (e.g. adaptive) tessellation densities. We also present an original Triangle‐to‐Quad conversion algorithm that behaves well in terms of geometrical complexity and tessellation quality, which we use to obtain the initial quad mesh from a given triangle mesh.     

Ternary Sparse Matrix Representation for Volumetric Mesh Subdivision and Processing on GPUs

In this paper, we present a novel volumetric mesh representation suited for parallel computing on modern GPU architectures. The data structure is based on a compact, ternary sparse matrix storage of boundary operators. Boundary operators correspond to the first‐order top‐down relations of k‐faces to their (k ? 1)‐face facets. The compact, ternary matrix storage format is based on compressed sparse row matrices with signed indices and allows for efficient parallel computation of indirect and bottom‐up relations. This representation is then used in the implementation of several parallel volumetric mesh algorithms including Laplacian smoothing and volumetric Catmull‐Clark subdivision. We compare these algorithms with their counterparts based on OpenVolumeMesh and achieve speedups from 3× to 531×, for sufficiently large meshes, while reducing memory consumption by up to 36%.     

Context‐Based Coding of Adaptive Multiresolution Meshes

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.     

A Colour Interpolation Scheme for Topologically Unrestricted Gradient Meshes

Gradient meshes are a 2D vector graphics primitive where colour is interpolated between mesh vertices. The current implementations of gradient meshes are restricted to rectangular mesh topology. Our new interpolation method relaxes this restriction by supporting arbitrary manifold topology of the input gradient mesh. Our method is based on the Catmull‐Clark subdivision scheme, which is well‐known to support arbitrary mesh topology in 3D. We adapt this scheme to support gradient mesh colour interpolation, adding extensions to handle interpolation of colours of the control points, interpolation only inside the given colour space and emulation of gradient constraints seen in related closed‐form solutions. These extensions make subdivision a viable option for interpolating arbitrary‐topology gradient meshes for 2D vector graphics.     

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.     

CPH: A Compact Representation for Hierarchical Meshes Generated by Primal Refinement

We present CPH (Compact Primal Hierarchy): a compact representation of the hierarchical connectivity of surface and volume manifold meshes generated through primal subdivision refinements. CPH is consistently defined in several dimensions and supports multiple kinds of tessellations and refinements, whether regular or adaptive. The basic idea is to store only the finest mesh, encoded in a classical monoresolution structure that is enriched with a minimal set of labels. These labels allow traversal of any intermediate level of the mesh concurrently without having to extract it in an additional structure. Our structure allows attributes to be stored on the cells not only on the finest level, but also on any intermediate level. We study the trade‐off between the memory cost of this compact representation and the time complexity of mesh traversals at any resolution level.     

Tetrahedral Embedded Boundary Methods for Accurate and Flexible Adaptive Fluids

When simulating fluids, tetrahedral methods provide flexibility and ease of adaptivity that Cartesian grids find difficult to match. However, this approach has so far been limited by two conflicting requirements. First, accurate simulation requires quality Delaunay meshes and the use of circumcentric pressures. Second, meshes must align with potentially complex moving surfaces and boundaries, necessitating continuous remeshing. Unfortunately, sacrificing mesh quality in favour of speed yields inaccurate velocities and simulation artifacts. We describe how to eliminate the boundary‐matching constraint by adapting recent embedded boundary techniques to tetrahedra, so that neither air nor solid boundaries need to align with mesh geometry. This enables the use of high quality, arbitrarily graded, non‐conforming Delaunay meshes, which are simpler and faster to generate. Temporal coherence can also be exploited by reusing meshes over adjacent timesteps to further reduce meshing costs. Lastly, our free surface boundary condition eliminates the spurious currents that previous methods exhibited for slow or static scenarios. We provide several examples demonstrating that our efficient tetrahedral embedded boundary method can substantially increase the flexibility and accuracy of adaptive Eulerian fluid simulation.     

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.     

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.     

Volume Preservation of Multiresolution Meshes

Geometric constraints have proved to be efficient for enhancing the realism of shape animation. The present paper addresses the computation and the preservation of the volume enclosed by multiresolution meshes. A wavelet based representation allows the mesh to be handled at any level of resolution. The key contribution is the calculation of the volume as a trilinear form with respect to the multiresolution coefficients. Efficiency is reached thanks to the pre-processing of a sparse 3D data structure involving the transposition of the filters while represented as a lifting scheme. A versatile and interactive method for preserving the volume during a deformation process is then proposed. It is based on a quadratic minimization subject to a linearization of the volume constraint. A closed form of the solution is derived.     

A Parallel Approach to Compression and Decompression of Triangle Meshes using the GPU

Most state‐of‐the‐art compression algorithms use complex connectivity traversal and prediction schemes, which are not efficient enough for online compression of large meshes. In this paper we propose a scalable massively parallel approach for compression and decompression of large triangle meshes using the GPU. Our method traverses the input mesh in a parallel breadth‐first manner and encodes the connectivity data similarly to the well known cut‐border machine. Geometry data is compressed using a local prediction strategy. In contrast to the original cut‐border machine, we can additionally handle triangle meshes with inconsistently oriented faces. Our approach is more than one order of magnitude faster than currently used methods and achieves competitive compression rates.     

Generalized As‐Similar‐As‐Possible Warping with Applications in Digital Photography

Discrete conformal mappings of planar triangle meshes, also known as the As‐Similar‐As‐Possible (ASAP) mapping, involve the minimization of a quadratic energy function, thus are very easy to generate and are popular in image warping scenarios. We generalize this classical mapping to the case of quad meshes, taking into account the mapping of the interior of the quad, and analyze in detail the most common case ‐ the unit grid mesh. We show that the generalization, when combined with barycentric coordinate mappings between the source and target polygons, spawns an entire family of new mappings governed by quadratic energy functions, which allow to control quite precisely various effects of the mapping. This approach is quite general and applies also to arbitrary planar polygon meshes. As an application of generalized ASAP mappings of the unit grid mesh, we demonstrate how they can be used to warp digital photographs to achieve a variety of effects. One such effect is modifying the perspective of the camera that took a given photograph (without moving the camera). A related, but more challenging, effect is re‐photography ‐ warping a contemporary photograph in order to reproduce the camera view present in a vintage photograph of the same scene ‐ taken many years before with a different camera from a different viewpoint. We apply the generalized ASAP mapping to these images, discretized to a unit grid. Using a quad mesh (as opposed to a triangle mesh) permits biasing towards affine maps of the unit squares. This allows the introduction of an As‐Affine‐As‐Possible (AAAP) mapping for a good approximation of the homographies present in these warps, achieving quite accurate results. We demonstrate the advantages of the AAAP mapping on a variety of synthetic and real‐world examples.     

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.     

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.