Search

A method for concise, faithful approximation of complex 3D datasets is key to reducing the computational cost of graphics applications. Despite numerous applications ranging from geometry compression to reverse engineering, efficiently capturing the geometry of a surface remains a tedious task. In this paper, we present both theoretical and practical contributions that result in a novel and versatile framework for geometric approximation of surfaces. We depart from the usual strategy by casting shape approximation as a variational geometric partitioning problem. Using the concept of geometric proxies, we drive the distortion error down through repeated clustering of faces into best-fitting regions. Our approach is entirely discrete and error-driven, and does not require parameterization or local estimations of differential quantities. We also introduce a new metric based on normal deviation, and demonstrate its superior behavior at capturing anisotropy. [ABSTRACT FROM AUTHOR]

A haptic interface lets the user touch, explore, paint, and manipulate virtual three-dimensional (3D) models in a natural way using a haptic display device. However, one can roughly classify haptic rendering algorithms according to the surface representation they use, geometric haptic algorithms for surface data, and volumetric haptic algorithms based on volumetric data including implicit surface representation. This article presents a haptic rendering technique based on a hybrid surface representation, a combination of a geometric and an implicit surface model. This representation addresses many limitations in haptic displays and achieves fast, accurate, and stable simulation of surface properties including friction, stiffness, and textures. Based on the hybrid representation, the authors present techniques for decorating and editing a model using a haptic interface. Their prototype sculpting system allows the user to paint directly on the 3D model and edit local surface properties. This representation can be potentially applied to various applications, such as digital art and medical training. INSET: Related Work..

Despite their cinematic appeal, turbulent flows involving fluid-solid coupling remain a computational challenge in animation. At the root of this current limitation is the numerical dispersion from which most accurate Navier-Stokes solvers suffer: proper coupling between fluid and solid often generates artificial dispersion in the form of local, parasitic trains of velocity oscillations, eventually leading to numerical instability. While successive improvements over the years have led to conservative and detail-preserving fluid integrators, the dispersive nature of these solvers is rarely discussed despite its dramatic impact on fluid-structure interaction. In this paper, we introduce a novel low-dissipation and low-dispersion fluid solver that can simulate two-way coupling in an efficient and scalable manner, even for turbulent flows. In sharp contrast with most current CG approaches, we construct our solver from a kinetic formulation of the flow derived from statistical mechanics. Unlike existing lattice Boltzmann solvers, our approach leverages high-order moment relaxations as a key to controlling both dissipation and dispersion of the resulting scheme. Moreover, we combine our new fluid solver with the immersed boundary method to easily handle fluid-solid coupling through time adaptive simulations. Our kinetic solver is highly parallelizable by nature, making it ideally suited for implementation on single- or multi-GPU computing platforms. Extensive comparisons with existing solvers on synthetic tests and real-life experiments are used to highlight the multiple advantages of our work over traditional and more recent approaches, in terms of accuracy, scalability, and efficiency. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a numerical technique to generate sample distributions in arbitrary dimension for improved accuracy of Monte Carlo integration. We point out that optimal transport offers theoretical bounds on Monte Carlo integration error, and that the recently-introduced numerical framework of sliced optimal transport (SOT) allows us to formulate a novel and efficient approach to generating well-distributed high-dimensional pointsets. The resulting sliced optimal transport sampling, solely involving repeated 1D solves, is particularly simple and efficient for the common case of a uniform density over a d-dimensional ball. We also construct a volume-preserving map from a d-ball to a d-cube (generalizing the Shirley-Chiu mapping to arbitrary dimensions) to offer fast SOT sampling over d-cubes. We provide ample numerical evidence of the improvement in Monte Carlo integration accuracy that SOT sampling brings compared to existing QMC techniques, and derive a projective variant for rendering which rivals, and at times outperforms, current sampling strategies using low-discrepancy sequences or optimized samples. [ABSTRACT FROM AUTHOR]

Geometry processing of surface meshes relies heavily on the discretization of differential operators such as gradient, Laplacian, and covariant derivative. While a variety of discrete operators over triangulated meshes have been developed and used for decades, a similar construction over polygonal meshes remains far less explored despite the prevalence of non-simplicial surfaces in geometric design and engineering applications. This paper introduces a principled construction of discrete differential operators on surface meshes formed by (possibly non-flat and non-convex) polygonal faces. Our approach is based on a novel mimetic discretization of the gradient operator that is linear-precise on arbitrary polygons. Equipped with this discrete gradient, we draw upon ideas from the Virtual Element Method in order to derive a series of discrete operators commonly used in graphics that are now valid over polygonal surfaces. We demonstrate the accuracy and robustness of our resulting operators through various numerical examples, before incorporating them into existing geometry processing algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we construct higher-order variational integrators for a class of degenerate systems described by Lagrangians that are linear in velocities. We analyze the geometry underlying such systems and develop the appropriate theory for variational integration. Our main observation is that the evolution takes place on the primary constraint and the "Hamiltonian" equations of motion can be formulated as an index-1 differential-algebraic system. We also construct variational Runge–Kutta methods and analyze their properties. The general properties of Runge–Kutta methods depend on the "velocity" part of the Lagrangian. If the "velocity" part is also linear in the position coordinate, then we show that non-partitioned variational Runge–Kutta methods are equivalent to integration of the corresponding first-order Euler–Lagrange equations, which have the form of a Poisson system with a constant structure matrix, and the classical properties of the Runge–Kutta method are retained. If the "velocity" part is nonlinear in the position coordinate, we observe a reduction of the order of convergence, which is typical of numerical integration of DAEs. We verified our results through numerical experiments for various dynamical systems. [ABSTRACT FROM AUTHOR]

Moving mesh methods (also called r-adaptive methods) are space-adaptive strategies used for the numerical simulation of time-dependent partial differential equations. These methods keep the total number of mesh points fixed during the simulation but redistribute them over time to follow the areas where a higher mesh point density is required. There are a very limited number of moving mesh methods designed for solving field-theoretic partial differential equations, and the numerical analysis of the resulting schemes is challenging. In this paper, we present two ways to construct r-adaptive variational and multisymplectic integrators for (1+1)-dimensional Lagrangian field theories. The first method uses a variational discretization of the physical equations, and the mesh equations are then coupled in a way typical of the existing r-adaptive schemes. The second method treats the mesh points as pseudo-particles and incorporates their dynamics directly into the variational principle. A user-specified adaptation strategy is then enforced through Lagrange multipliers as a constraint on the dynamics of both the physical field and the mesh points. We discuss the advantages and limitations of our methods. Numerical results for the Sine–Gordon equation are also presented. [ABSTRACT FROM AUTHOR]

In this paper, we provide a numerical tool to study a material's coherence from a set of 2D Lagrangian trajectories sampling a dynamical system, i.e., from the motion of passive tracers. We show that eigenvectors of the Burau representation of a topological braid derived from the trajectories have levelsets corresponding to components of the Nielsen–Thurston decomposition of the dynamical system. One can thus detect and identify clusters of space–time trajectories corresponding to coherent regions of the dynamical system by solving an eigenvalue problem. Unlike previous methods, the scalable computational complexity of our braid-based approach allows the analysis of large amounts of trajectories. [ABSTRACT FROM AUTHOR]

Fig. 1 A one-form (vector field) given as edge values on a 128 × 128 grid is decomposed into a coarse one-form component u 1 (on a 2 × 2 grid) and a series of wavelet coefficients for a six-level hierarchy adapted to the one-form Laplace operator; the relative (Dirichlet) energy content of each level is indicated as well. Fig. 1 • We propose the first construction of operator-adapted wavelets for finite-element differential forms. • The core of our construction relies on refinable and subdivision-based high-order bases of arbitrary differential forms. • Since our approach applies to arbitrary differential forms, we can derive scalar-valued as well as vector-valued wavelets. • The resulting wavelets are scale-orthogonal wrt a linear operator L , leading to a Galerkin discretization that is block-diagonal, with well-conditioned blocks. • Our construction accommodates linear differential constraints such as divergence-freeness, and has direct applications such as coarse-graining and model reduction of PDEs. We introduce in this paper an operator-adapted multiresolution analysis for finite-element differential forms. From a given continuous, linear, bijective, and self-adjoint positive-definite operator L , a hierarchy of basis functions and associated wavelets for discrete differential forms is constructed in a fine-to-coarse fashion and in quasilinear time. The resulting wavelets are L -orthogonal across all scales, and can be used to derive a Galerkin discretization of the operator such that its stiffness matrix becomes block-diagonal, with uniformly well-conditioned and sparse blocks. Because our approach applies to arbitrary differential p -forms, we can derive both scalar-valued and vector-valued wavelets block-diagonalizing a prescribed operator. We also discuss the generality of the construction by pointing out that it applies to various types of computational grids, offers arbitrary smoothness orders of basis functions and wavelets, and can accommodate linear differential constraints such as divergence-freeness. Finally, we demonstrate the benefits of the corresponding operator-adapted multiresolution decomposition for coarse-graining and model reduction of linear and non-linear partial differential equations. [ABSTRACT FROM AUTHOR]

We present a structure preserving numerical algorithm for the collision of elastic bodies. Our integrator is derived from a discrete version of the field-theoretic (multisymplectic) variational description of nonsmooth Lagrangian continuum mechanics, combined with generalized Lagrange multipliers to handle inequality constraints. We test the resulting explicit integrator for the longitudinal impact of two elastic linear bar models, and for the collision of a nonlinear geometrically exact beam model with a rigid plane. Numerical simulations for various physical parameters are presented to illustrate the behavior and performance of our approach. [ABSTRACT FROM AUTHOR]

Denoising is a common, yet critical operation in geometry processing aiming at recovering high‐fidelity models of piecewise‐smooth objects from noise‐corrupted pointsets. Despite a sizable literature on the topic, there is a dearth of approaches capable of processing very noisy and outlier‐ridden input pointsets for which no normal estimates and no assumptions on the underlying geometric features or noise type are provided. In this paper, we propose a new robust‐statistics approach to denoising pointsets based on line processes to offer robustness to noise and outliers while preserving sharp features possibly present in the data. While the use of robust statistics in denoising is hardly new, most approaches rely on prescribed filtering using data‐independent blending expressions based on the spatial and normal closeness of samples. Instead, our approach deduces a geometric denoising strategy through robust and regularized tangent plane fitting of the initial pointset, obtained numerically via alternating minimizations for efficiency and reliability. Key to our variational approach is the use of line processes to identify inliers vs. outliers, as well as the presence of sharp features. We demonstrate that our method can denoise sampled piecewise‐smooth surfaces for levels of noise and outliers at which previous works fall short. [ABSTRACT FROM AUTHOR]

Geometry has been extensively studied for centuries, almost exclusively from a differential point of view. However, with the advent of the digital age, the interest directed to smooth surfaces has now partially shifted due to the growing importance of discrete geometry. From 3D surfaces in graphics to higher dimensional manifolds in mechanics, computational sciences must deal with sampled geometric data on a daily basis-hence our interest in Applied Geometry. In this talk we cover different aspects of Applied Geometry. First, we discuss the problem of Shape Approximation, where an initial surface is accurately discretized (i.e., remeshed) using anisotropic elements through error minimization. Second, once we have a discrete geometry to work with, we briefly show how to develop a full- blown discrete calculus on such discrete manifolds, allowing us to manipulate functions, vector fields, or even tensors while preserving the fundamental structures and invariants of the differential case. We will emphasize the applicability of our discrete variational approach to geometry by showing results on surface parameterization, smoothing, and remeshing, as well as virtual actors and thin-shell simulation. Joint work with: Pierre Alliez (INRIA), David Cohen-Steiner (Duke U.), Eitan Grinspun (NYU), Anil Hirani (Caltech), Jerrold E. Marsden (Caltech), Mark Meyer (Pixar), Fred Pighin (USC), Peter Schröder (Caltech), Yiying Tong (USC). [ABSTRACT FROM AUTHOR]

In this paper, we formulate an automatic approach to the detection of partial, local, and global symmetries and orbits in arbitrary 3D datasets. We improve upon existing voting-based symmetry detection techniques by leveraging the Lie group structure of geometric transformations. In particular, we introduce a logarithmic mapping that ensures that orbits are mapped to linear subspaces, hence unifying and extending many existing mappings in a single Lie-algebra voting formulation. Compared to previous work, our resulting method offers significantly improved robustness as it guarantees that our symmetry detection of an input model is frame, scale, and reflection invariant. As a consequence, we demonstrate that our approach efficiently and reliably discovers symmetries and orbits of geometric datasets without requiring heavy parameter tuning. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we present finite-dimensional particle-based models for fluids which respect a number of geometric properties of the Euler equations of motion. Specifically, we use Lagrange–Poincaré reduction to understand the coupling between a fluid and a set of Lagrangian particles that are supposed to simulate it. We substitute the use of principal connections in Cendra et al. (2001) [13] with vector field valued interpolations from particle velocity data. The consequence of writing evolution equations in terms of interpolation is two-fold. First, it provides estimates on the error incurred when interpolation is used to derive the evolution of the system. Second, this form of the equations of motion can inspire a family of particle and hybrid particle–spectral methods, where the error analysis is “built in”. We also discuss the influence of other parameters attached to the particles, such as shape, orientation, or higher-order deformations, and how they can help us achieve a particle-centric version of Kelvin’s circulation theorem. [Copyright &y& Elsevier]

In this paper, we introduce a hybrid LBM-FVM solver for two-phase fluid flow simulations in which interface dynamics is modeled by a conservative phase-field equation. Integrating fluid equations over time is achieved through a velocity-based lattice Boltzmann solver which is improved by a central-moment multiple-relaxation-time collision model to reach higher accuracy. For interface evolution, we propose a finite-volume-based numerical treatment for the integration of the phase-field equation: we show that the second-order isotropic centered stencils for diffusive and separation fluxes combined with the WENO-5 stencils for advective fluxes achieve similar and sometimes even higher accuracy than the state-of-the-art double-distribution-function LBM methods as well as the DUGKS-based method, while requiring less computations and a smaller amount of memory. Benchmark tests (such as the 2D diagonal translation of a circular interface), along with quantitative evaluations on more complex tests (such as the rising bubble and Rayleigh-Taylor instability simulations) allowing comparisons with prior numerical methods and/or experimental data, are presented to validate the advantage of our hybrid solver. Moreover, 3D simulations (including a dam break simulation) are also compared to the time-lapse photography of physical experiments in order to allow for more qualitative evaluations. • This paper proposes a new hybrid LBM-FVM solver to simulate two-phase flows which reduces memory consumption and improves computational accuracy and efficiency. • The momentum equation is solved by a set of lattice Boltzmann equations with a velocity-based high-order CM-MRT model, while the phase-field equation is solved by a WENO-based finite-volume approach. • Our solver is validated through benchmark tests, comparisons, and validation examples, both quantitatively and qualitatively. • Our massively-parallel implementation on GPU offers efficient simulation of two-phase flows for a low memory footprint. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we introduce the concept of an exoskeleton as a new abstraction of arbitrary shapes that succinctly conveys both the perceptual and the geometric structure of a 3D model. We extract exoskeletons via a principled framework that combines segmentation and shape approximation. Our method starts from a segmentation of the shape into perceptually relevant parts and then constructs the exoskeleton using a novel extension of the Variational Shape Approximation method. Benefits of the exoskeleton abstraction to graphics applications such as simplification and chartification are presented. [Copyright &y& Elsevier]

In this paper, we propose a controllable embedding method for high- and low-dimensional geometry processing through sparse matrix eigenanalysis. Our approach is equally suitable to perform non-linear dimensionality reduction on big data, or to offer non-linear shape editing of 3D meshes and pointsets. At the core of our approach is the construction of a multi-Laplacian quadratic form that is assembled from local operators whose kernels only contain locally-affine functions. Minimizing this quadratic form provides an embedding that best preserves all relative coordinates of points within their local neighborhoods. We demonstrate the improvements that our approach brings over existing nonlinear dimensionality reduction methods on a number of datasets, and formulate the first eigen-based as-rigid-as-possible shape deformation technique by applying our affine-kernel embedding approach to 3D data augmented with user-imposed constraints on select vertices. [ABSTRACT FROM AUTHOR]

Semi-supervised learning (SSL) is fundamentally a geometric task: in order to classify high-dimensional point sets when only a small fraction of data points are labeled, the geometry of the unlabeled data points is exploited to gain better classifying accuracy. A number of state-of-the-art SSL techniques rely on label propagation through graph-based diffusion, with edge weights that are evaluated either analytically from the data or through compute-intensive training based on nonlinear and nonconvex optimization. In this paper, we bring discrete differential geometry to bear on this problem by introducing a graph-based SSL approach where label diffusion uses a Laplacian operator learned from the geometry of the input data. From a data-dependent graph of the input, we formulate a biconvex loss function in terms of graph edge weights and inferred labels. Its minimization is achieved through alternating rounds of optimization of the Laplacian and diffusion-based inference of labels. The resulting optimized Laplacian diffusion directionally adapts to the intrinsic geometric structure of the data which often concentrates in clusters or around low-dimensional manifolds within the high-dimensional representation space. We show on a range of classical datasets that our variational classification is more accurate than current graph-based SSL techniques. The algorithmic simplicity and efficiency of our discrete differential geometric approach (limited to basic linear algebra operations) also make it attractive, despite the seemingly complex task of optimizing all the edge weights of a graph. [ABSTRACT FROM AUTHOR]

Multiphase flows exhibit a large realm of complex behaviors such as bubbling, glugging, wetting, and splashing which emerge from air-water and water-solid interactions. Current fluid solvers in graphics have demonstrated remarkable success in reproducing each of these visual effects, but none have offered a model general enough to capture all of them concurrently. In contrast, computational fluid dynamics have developed very general approaches to multiphase flows, typically based on kinetic models. Yet, in both communities, there is dearth of methods that can simulate density ratios and Reynolds numbers required for the type of challenging real-life simulations that movie productions strive to digitally create, such as air-water flows. In this article, we propose a kinetic model of the coupling of the Navier-Stokes equations with a conservative phase-field equation, and provide a series of numerical improvements over existing kinetic-based approaches to offer a general multiphase flow solver. The resulting algorithm is embarrassingly parallel, conservative, far more stable than current solvers even for real-life conditions, and general enough to capture the typical multiphase flow behaviors. Various simulation results are presented, including comparisons to both previous work and real footage, to highlight the advantages of our new method.

In this paper, we introduce an interactive approach to generate physically based shape interpolation between poses. We extend linear modal analysis to offer an efficient and robust numerical technique to generate physically-plausible dynamics even for very large deformation. Our method also provides a rich set of intuitive editing tools with real-time feedback, including control over vibration frequencies, amplitudes, and damping of the resulting interpolation sequence. We demonstrate the versatility of our approach through a series of complex dynamic shape interpolations.