Mesh analysis using geodesic mean-shift

In this paper, we introduce a versatile and robust method for analyzing the feature space associated with a given mesh surface. The method is based on the mean-shift operator, which was shown to be successful in image and video processing. Its strength lies in the fact that it works in a single joint space of geometry and attributes called the feature-space. The mean-shift procedure works as a gradient ascend finding maxima of an estimated probability density function in feature-space. Our method for using the mean-shift technique on surfaces solves several difficulties. First, meshes as opposed to images do not present a regular and uniform sampling of domain. Second, on surface meshes the shifting procedure must be constrained to stay on the surface and preserve geodesic distances. We define a special local geodesic parameterization scheme, and use it to generalize the mean-shift procedure to unstructured surface meshes. Our method can support piecewise linear attribute definitions as well as piecewise constant attributes.     

Scribble-based gradient mesh recoloring

Previous gradient mesh recoloring methods usually have dependencies on an additional reference image and the rasterized gradient mesh. To circumvent such dependencies, we propose a user scribble-based recoloring method, in which users are allowed to annotate gradient meshes with a few color scribbles. Our approach builds an auxiliary mesh from gradient meshes, namely control net, by taking both colors and local color gradients at mesh points into account. We then develop an extended chrominance blending method to propagate the user specified colors over the control net. The recolored gradient mesh is finally reconstructed from the recolored control net. Experiments validate the effectiveness of our approach on multiple gradient meshes. Compared with various alternative solutions, our method has no color bleedings nor sampling artifacts, and can achieve fast performance.

     

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.     

Isometry‐Aware Preconditioning for Mesh Parameterization

This paper presents a new preconditioning technique for large‐scale geometric optimization problems, inspired by applications in mesh parameterization. Our positive (semi‐)definite preconditioner acts on the gradients of optimization problems whose variables are positions of the vertices of a triangle mesh in ?² or of a tetrahedral mesh in ?³, converting localized distortion gradients into the velocity of a globally near‐rigid motion via a linear solve. We pose our preconditioning tool in terms of the Killing energy of a deformation field and provide new efficient formulas for constructing Killing operators on triangle and tetrahedral meshes. We demonstrate that our method is competitive with state‐of‐the‐art algorithms for locally injective parameterization using a variety of optimization objectives and show applications to two‐ and three‐dimensional mesh deformation.     

Content‐Based Colour Transfer

This paper presents a novel content‐based method for transferring the colour patterns between images. Unlike previous methods that rely on image colour statistics, our method puts an emphasis on high‐level scene content analysis. We first automatically extract the foreground subject areas and background scene layout from the scene. The semantic correspondences of the regions between source and target images are established. In the second step, the source image is re‐coloured in a novel optimization framework, which incorporates the extracted content information and the spatial distributions of the target colour styles. A new progressive transfer scheme is proposed to integrate the advantages of both global and local transfer algorithms, as well as avoid the over‐segmentation artefact in the result. Experiments show that with a better understanding of the scene contents, our method well preserves the spatial layout, the colour distribution and the visual coherence in the transfer process. As an interesting extension, our method can also be used to re‐colour video clips with spatially‐varied colour effects.     

A log-barrier method for mesh quality improvement and untangling

The presence of a few inverted or poor-quality mesh elements can negatively affect the stability, convergence and efficiency of a finite element solver and the accuracy of the associated partial differential equation solution. We propose a mesh quality improvement and untangling method that untangles a mesh with inverted elements and improves its quality. Worst element mesh quality improvement and untangling can be formulated as a nonsmooth unconstrained optimization problem, which can be reformulated as a smooth constrained optimization problem. Our technique solves the latter problem using a log-barrier interior point method and uses the gradient of the objective function to efficiently converge to a stationary point. The method uses a logarithmic barrier function and performs global mesh quality improvement. We have also developed a smooth quality metric that takes both signed area and the shape of an element into account. This quality metric assigns a negative value to an inverted element. It is used with our algorithm to untangle a mesh by improving the quality of an inverted element to a positive value. Our method usually yields better quality meshes than existing methods for improvement of the worst quality elements, such as the active set, pattern search, and multidirectional search mesh quality improvement methods. Our method is faster and more robust than existing methods for mesh untangling, such as the iterative stiffening method.     

Space-Optimized Texture Maps

Texture mapping is a common operation to increase the realism of three‐dimensional meshes at low cost. We propose a new texture optimization algorithm based on the reduction of the physical space allotted to the texture image. Our algorithm optimizes the use of texture space by computing a warping function for the image and new texture coordinates. Neither the mesh geometry nor its connectivity are modified by the optimization. Our method uniformly distributes frequency content of the image in the spatial domain. In other words, the image is stretched in high frequency areas, whereas low frequency regions are shrunk. We also take into account distortions introduced by the mapping onto the model geometry in this process. The resulting image can be resampled at lower rate while preserving its original details. The unwarping is performed by the texture mapping function. Hence, the space‐optimized texture is stored as‐is in texture memory and is fully supported by current graphics hardware. We present several examples showing that our method significantly decreases texture memory usage without noticeable loss in visual quality.     

Field‐aligned Quadrangulation for Image Vectorization

Image vectorization is an important yet challenging problem, especially when the input image has rich content. In this paper, we develop a novel method for automatically vectorizing natural images with feature‐aligned quad‐dominant meshes. Inspired by the quadrangulation methods in 3D geometry processing, we propose a new directional field optimization technique by encoding the color gradients, sidestepping the explicit computing of salient image features. We further compute the anisotropic scales of the directional field by accommodating the distance among image features. Our method is fully automatic and efficient, which takes only a few seconds for a 400×400 image on a normal laptop. We demonstrate the effectiveness of the proposed method on various image editing applications.     

Gradient Outlier Removal for Gradient‐Domain Path Tracing

We present a new outlier removal technique for a gradient‐domain path tracing (G‐PT) that computes image gradients as well as colors. Our approach rejects gradient outliers whose estimated errors are much higher than those of the other gradients for improving reconstruction quality for the G‐PT. We formulate our outlier removal problem as a least trimmed squares optimization, which employs only a subset of gradients so that a final image can be reconstructed without including the gradient outliers. In addition, we design this outlier removal process so that the chosen subset of gradients maintains connectivity through gradients between pixels, preventing pixels from being isolated. Lastly, the optimal number of inlier gradients is estimated to minimize our reconstruction error. We have demonstrated that our reconstruction with robustly rejecting gradient outliers produces visually and numerically improved results, compared to the previous screened Poisson reconstruction that uses all the gradients.     

Geometric signal compression

Compression of mesh attributes becomes a challenging problem due to the great need for efficient storage and fast transmission. This paper presents a novel geometric signal compression framework for all mesh attributes, including position coordinates, normal, color, texture, etc. Within this framework, mesh attributes are regarded as geometric signals defined on mesh surfaces. A planar parameterization algorithm is first proposed to map 3D meshes to 2D parametric meshes. Geometric signals are then transformed into 2D signals, which are sampled into 2D regular signals using an adaptive sampling method. The JPEG2000 standard for still image compression is employed to effectively encode these regular signals into compact bit-streams with high rate/distortion ratios. Experimental results demonstrate the great application potentials of this framework.     

A local tangential lifting differential method for triangular meshes

In this note we present a local tangential lifting (LTL) algorithm to compute differential quantities for triangular meshes obtained from regular surfaces. First, we introduce a new notation of the local tangential polygon and lift functions and vector fields on a triangular mesh to the local tangential polygon. Then we use the centroid weights proposed by Chen and Wu [4] to define the discrete gradient of a function on a triangular mesh. We also use our new method to define the discrete Laplacian operator acting on functions on triangular meshes. Higher order differential operators can also be computed successively. Our approach is conceptually simple and easy to compute. Indeed, our LTL method also provides a unified algorithm to estimate the shape operator and curvatures of a triangular mesh and derivatives of functions and vector fields. We also compare three different methods : our method, the least square method and Akima’s method to compute the gradients of functions.     

Geometry completion and detail generation by texture synthesis

We present a novel method for patching holes in polygonal meshes and synthesizing surfaces with details based on existing geometry. The most novel feature of our proposed method is that we transform the 3D geometry synthesis problem into a 2D domain by parameterizing surfaces and solve this problem in that domain. We then derive local geometry gradient images that encode intrinsic local geometry properties, which are invariant to object translation and rotation. The 3D geometry of holes is then reconstructed from synthesized local gradient images. This method can be extended to execute other mesh editing operations such as geometry detail transfer or synthesis. The resulting major benefits of performing geometry synthesis in 2D are more flexible and robust control, better leveraging of the wealth of current 2D image completion methods, and greater efficiency.     

Rate-distortion optimization for progressive compression of 3D mesh with color attributes

We propose a new lossless progressive compression algorithm based on rate-distortion optimization for meshes with color attributes; the quantization precision of both the geometry and the color information is adapted to each intermediate mesh during the encoding/decoding process. This quantization precision can either be optimally determined with the use of a mesh distortion measure or quasi-optimally decided based on an analysis of the mesh complexity in order to reduce the calculation time. Furthermore, we propose a new metric which estimates the geometry and color importance of each vertex during the simplification in order to faithfully preserve the feature elements. Experimental results show that our method outperforms the state-of-the-art algorithm for colored meshes and competes with the most efficient algorithms for non-colored meshes.     

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.     

Spectral Gradient Sampling for Path Tracing

Spectral Monte‐Carlo methods are currently the most powerful techniques for simulating light transport with wavelength‐dependent phenomena (e.g., dispersion, colored particle scattering, or diffraction gratings). Compared to trichromatic rendering, sampling the spectral domain requires significantly more samples for noise‐free images. Inspired by gradient‐domain rendering, which estimates image gradients, we propose spectral gradient sampling to estimate the gradients of the spectral distribution inside a pixel. These gradients can be sampled with a significantly lower variance by carefully correlating the path samples of a pixel in the spectral domain, and we introduce a mapping function that shifts paths with wavelength‐dependent interactions. We compute the result of each pixel by integrating the estimated gradients over the spectral domain using a one‐dimensional screened Poisson reconstruction. Our method improves convergence and reduces chromatic noise from spectral sampling, as demonstrated by our implementation within a conventional path tracer.     

A local tangential lifting differential method for triangular meshes

In this note we present a local tangential lifting (LTL) algorithm to compute differential quantities for triangular meshes obtained from regular surfaces. First, we introduce a new notation of the local tangential polygon and lift functions and vector fields on a triangular mesh to the local tangential polygon. Then we use the centroid weights proposed by Chen and Wu [4] to define the discrete gradient of a function on a triangular mesh. We also use our new method to define the discrete Laplacian operator acting on functions on triangular meshes. Higher order differential operators can also be computed successively. Our approach is conceptually simple and easy to compute. Indeed, our LTL method also provides a unified algorithm to estimate the shape operator and curvatures of a triangular mesh and derivatives of functions and vector fields. We also compare three different methods : our method, the least square method and Akima’s method to compute the gradients of functions.     

Hexahedral mesh smoothing via local element regularization and global mesh optimization

The quality of finite element meshes is one of the key factors that affect the accuracy and reliability of finite element analysis results. In order to improve the quality of hexahedral meshes, we present a novel hexahedral mesh smoothing algorithm which combines a local regularization for each hexahedral mesh, using dual element based geometric transformation, with a global optimization operator for all hexahedral meshes. The global optimization operator is composed of three main terms, including the volumetric Laplacian operator of hexahedral meshes and the geometric constraints of surface meshes which keep the volumetric details and the surface details, and another is the transformed node displacements condition which maintains the regularity of all elements. The global optimization operator is formulated as a quadratic optimization problem, which is easily solved by solving a sparse linear system. Several experimental results are presented to demonstrate that our method obtains higher quality results than other state-of-the-art approaches.     

Mesh deformation using radial basis functions for gradient-based aerodynamic shape optimization

Gradient-based aerodynamic shape optimization using computational fluid dynamics (CFD), and time dependent problems in aeroelasticity, that is, coupled calculations between computational structural mechanics (CSM) and CFD, require repeated deformations of the CFD mesh.An interpolation scheme, based on radial basis functions (RBF), is devised in order to propagate the deformations from the boundaries to the interior of the CFD mesh. This method can lower the computational costs due to the deformation of the mesh, in comparison with the usual Laplace smoothing. Moreover, the algorithm is independent of the mesh connectivities. Therefore, structured and unstructured meshes are equally treated as well as hybrid meshes.The application of this interpolation scheme in problems of aerodynamic shape optimization is also carefully investigated. When the optimization is executed by a gradient-based algorithm the cost function is differentiated with respect to the design parameters in order to obtain the gradient. The gradient is most efficiently and accurately calculated by solving a certain adjoint equation derived from the discretized flow equations. The calculation of the gradient, which is detailed in this presentation, involves the Jacobian matrix of the mesh deformation.Finally, we present the results of an optimization of the ONERA M6 wing at transonic speed using the interpolation algorithm. The results are used for comparison with another technique of mesh deformation. The quality of the mesh obtained by the new algorithm, and the interpolation error, are analyzed with respect to the parameters of the interpolation scheme: the type of RBF, the RBF’s shape parameter, and the sets of control points.