Search

We introduce a novel adaptive eigenvalue filtering strategy to stabilize and accelerate the optimization of Neo-Hookean energy and its variants under the Projected Newton framework. For the first time, we show that Newton's method, Projected Newton with eigenvalue clamping and Projected Newton with absolute eigenvalue filtering can be unified using ideas from the generalized trust region method. Based on the trust-region fit, our model adaptively chooses the correct eigenvalue filtering strategy to apply during the optimization. Our method is simple but effective, requiring only two lines of code change in the existing Projected Newton framework. We validate our model outperforms stand-alone variants across a number of experiments on quasistatic simulation of deformable solids over a large dataset., Comment: SIGGRAPH Asia 2024 (Conference track). Project page: https://www.cs.columbia.edu/cg/trust-region/

Given function values on a domain $D_0$, possibly with noise, we examine the possibility of extending the function to a larger domain $D$, $D_0\subset D$. In addition to smoothness at the boundary of $D_0$, the extension on $D\setminus D_0$ should also inherit behavioral trends of the function on $D_0$, such as growth and decay or even oscillations. The approach chosen here is based upon the framework of linear models, univariate or bivariate, with constant or varying coefficients., Comment: 22 pages, 19 figures A revised version of the published paper: Levin, David. "Behavior preserving extension of univariate and bivariate functions." Advances in Quantum Chemistry. Vol. 68. Academic Press, 2014. 19-42

We present an elastic simulator for domains defined as evolving implicit functions, which is efficient, robust, and differentiable with respect to both shape and material. This simulator is motivated by applications in 3D reconstruction: it is increasingly effective to recover geometry from observed images as implicit functions, but physical applications require accurately simulating and optimizing-for the behavior of such shapes under deformation, which has remained challenging. Our key technical innovation is to train a small neural network to fit quadrature points for robust numerical integration on implicit grid cells. When coupled with a Mixed Finite Element formulation, this yields a smooth, fully differentiable simulation model connecting the evolution of the underlying implicit surface to its elastic response. We demonstrate the efficacy of our approach on forward simulation of implicits, direct simulation of 3D shapes during editing, and novel physics-based shape and topology optimizations in conjunction with differentiable rendering., Comment: 16 pages, 21 figures

We present a general method for computing local parameterizations rooted at a point on a surface, where the surface is described only through a signed implicit function and a corresponding projection function. Using a two-stage process, we compute several points radially emanating from the map origin, and interpolate between them with a spline surface. The narrow interface of our method allows it to support several kinds of geometry such as signed distance functions, general analytic implicit functions, triangle meshes, neural implicits, and point clouds. We demonstrate the high quality of our generated parameterizations on a variety of examples, and show applications in local texturing and surface curve drawing., Comment: 12 pages, 14 figures

We present a novel, physically-based morphing technique for elastic shapes, leveraging the differentiable material point method (MPM) with space-time control through per-particle deformation gradients to accommodate complex topology changes. This approach, grounded in MPM's natural handling of dynamic topologies, is enhanced by a chained iterative optimization technique, allowing for the creation of both succinct and extended morphing sequences that maintain coherence over time. Demonstrated across various challenging scenarios, our method is able to produce detailed elastic deformation and topology transitions, all grounded within our physics-based simulation framework., Comment: 14 pages, 9 figures

In this work, we show that exploiting additional variables in a mixed finite element formulation of deformation leads to an efficient physics-based character skinning algorithm. Taking as input, a user-defined rig, we show how to efficiently compute deformations of the character mesh which respect artist-supplied handle positions and orientations, but without requiring complicated constraints on the physics solver, which can cause poor performance. Rather we demonstrate an efficient, user controllable skinning pipeline that can generate compelling character deformations, using a variety of physics material models.

The proliferation of 3D representations, from explicit meshes to implicit neural fields and more, motivates the need for simulators agnostic to representation. We present a data-, mesh-, and grid-free solution for elastic simulation for any object in any geometric representation undergoing large, nonlinear deformations. We note that every standard geometric representation can be reduced to an occupancy function queried at any point in space, and we define a simulator atop this common interface. For each object, we fit a small implicit neural network encoding spatially varying weights that act as a reduced deformation basis. These weights are trained to learn physically significant motions in the object via random perturbations. Our loss ensures we find a weight-space basis that best minimizes deformation energy by stochastically evaluating elastic energies through Monte Carlo sampling of the deformation volume. At runtime, we simulate in the reduced basis and sample the deformations back to the original domain. Our experiments demonstrate the versatility, accuracy, and speed of this approach on data including signed distance functions, point clouds, neural primitives, tomography scans, radiance fields, Gaussian splats, surface meshes, and volume meshes, as well as showing a variety of material energies, contact models, and time integration schemes.

Volume-preserving hyperelastic materials are widely used to model near-incompressible materials such as rubber and soft tissues. However, the numerical simulation of volume-preserving hyperelastic materials is notoriously challenging within this regime due to the non-convexity of the energy function. In this work, we identify the pitfalls of the popular eigenvalue clamping strategy for projecting Hessian matrices to positive semi-definiteness during Newton's method. We introduce a novel eigenvalue filtering strategy for projected Newton's method to stabilize the optimization of Neo-Hookean energy and other volume-preserving variants under high Poisson's ratio (near 0.5) and large initial volume change. Our method only requires a single line of code change in the existing projected Newton framework, while achieving significant improvement in both stability and convergence speed. We demonstrate the effectiveness and efficiency of our eigenvalue projection scheme on a variety of challenging examples and over different deformations on a large dataset., Comment: SIGGRAPH 2024 (Conference track). Project page: https://www.cs.columbia.edu/cg/abs-psd/

We propose a reduced space mixed finite element method (MFEM) built on a Skinning Eigenmode subspace and material-aware cubature scheme. Our solver is well-suited for simulating scenes with large material and geometric heterogeneities in real-time. This mammoth geometry is composed of 98,175 vertices and 531,565 tetrahedral elements and with a heterogenous composition of widely varying materials of muscles ($E= 5\times10^5$ Pa), joints ($E=1\times10^5$ Pa), and bone ($E=1\times10^{10}$ Pa). The resulting simulation runs at 120 frames per second (FPS)., Comment: 10 pages, 15 figures

This paper demonstrates that the space of piecewise smooth functions can be well approximated by the space of functions defined by a set of simple (non-linear) operations on smooth uniform splines. The examples include bivariate functions with jump discontinuities or normal discontinuities across curves, and even across more involved geometries such as a 3-corner. The given data may be uniform or non-uniform, and noisy, and the approximation procedure involves non-linear least-squares minimization. Also included is a basic approximation theorem for functions with jump discontinuity across a smooth curve.

This paper introduces a novel graph-based filter method for automatic feature selection (abbreviated as GB-AFS) for multi-class classification tasks. The method determines the minimum combination of features required to sustain prediction performance while maintaining complementary discriminating abilities between different classes. It does not require any user-defined parameters such as the number of features to select. The methodology employs the Jeffries-Matusita (JM) distance in conjunction with t-distributed Stochastic Neighbor Embedding (t-SNE) to generate a low-dimensional space reflecting how effectively each feature can differentiate between each pair of classes. The minimum number of features is selected using our newly developed Mean Simplified Silhouette (abbreviated as MSS) index, designed to evaluate the clustering results for the feature selection task. Experimental results on public data sets demonstrate the superior performance of the proposed GB-AFS over other filter-based techniques and automatic feature selection approaches. Moreover, the proposed algorithm maintained the accuracy achieved when utilizing all features, while using only $7\%$ to $30\%$ of the features. Consequently, this resulted in a reduction of the time needed for classifications, from $15\%$ to $70\%$., Comment: 8 pages, 4 figures

In this work we present a new WENO b-spline based quasi-interpolation algorithm. The novelty of this construction resides in the application of the WENO weights to the b-spline functions, that are a partition of unity, instead to the coefficients that multiply the b-spline functions of the spline. The result obtained conserves the smoothness of the original spline and presents adaption to discontinuities in the function. Another new idea that we introduce in this work is the use of different base weight functions from those proposed in classical WENO algorithms. Apart from introducing the construction of the new algorithms, we present theoretical results regarding the order of accuracy obtained at smooth zones and close to the discontinuity, as well as theoretical considerations about how to design the new weight functions. Through a tensor product strategy, we extend our results to several dimensions. In order to check the theoretical results obtained, we present an extended battery of numerical experiments in one, two and tree dimensions that support our conclussions.

Physical systems ranging from elastic bodies to kinematic linkages are defined on high-dimensional configuration spaces, yet their typical low-energy configurations are concentrated on much lower-dimensional subspaces. This work addresses the challenge of identifying such subspaces automatically: given as input an energy function for a high-dimensional system, we produce a low-dimensional map whose image parameterizes a diverse yet low-energy submanifold of configurations. The only additional input needed is a single seed configuration for the system to initialize our procedure; no dataset of trajectories is required. We represent subspaces as neural networks that map a low-dimensional latent vector to the full configuration space, and propose a training scheme to fit network parameters to any system of interest. This formulation is effective across a very general range of physical systems; our experiments demonstrate not only nonlinear and very low-dimensional elastic body and cloth subspaces, but also more general systems like colliding rigid bodies and linkages. We briefly explore applications built on this formulation, including manipulation, latent interpolation, and sampling., Comment: SIGGRAPH 2023

Given a finite number of samples of a continuous set-valued function F, mapping an interval to compact subsets of the real line, we develop good approximations of F, which can be computed efficiently.

By starting with the assumption that motion is fundamentally a decision making problem, we use the world-line concept from Special Relativity as the inspiration for a novel multi-agent path planning method. We have identified a particular set of problems that have so far been overlooked by previous works. We present our solution for the global path planning problem for each agent and ensure smooth local collision avoidance for each pair of agents in the scene. We accomplish this by modeling the trajectories of the agents through 2D space and time as curves in 3D. Global path planning is solved using a modified Djikstra's algorithm to ensure that initial trajectories for agents do not intersect. We then solve for smooth local trajectories using a quasi-Newton interior point solver, providing the trajectory curves with a radius to turn them into rods. Subsequently, resolving collision of the rods ensures that no two agents are in the same spatial position at the same time. This space-time formulation allows us to simulate previously ignored phenomena such as highly asymmetric interactions in very constrained environments. It also provides a solution for scenes with unnaturally symmetric agent alignments without the need for jittering agent positions or velocities.

We propose a neural network-based approach for collision detection with deformable objects. Unlike previous approaches based on bounding volume hierarchies, our neural approach does not require an update of the spatial data structure when the object deforms. Our network is trained on the reduced degrees of freedom of the object, so that we can use the same network to query for collisions even when the object deforms. Our approach is simple to use and implement, and it can readily be employed on the GPU. We demonstrate our approach with two concrete examples: a haptics application with a finite element mesh, and cloth simulation with a skinned character.

We propose and explore a new, general-purpose method for the implicit time integration of elastica. Key to our approach is the use of a mixed variational principle. In turn its finite element discretization leads to an efficient alternating projections solver with a superset of the desirable properties of many previous fast solution strategies. This framework fits a range of elastic constitutive models and remains stable across a wide span of timestep sizes, material parameters (including problems that are quasi-static and approximately rigid). It is efficient to evaluate and easily applicable to volume, surface, and rods models. We demonstrate the efficacy of our approach on a number of simulated examples across all three codomains.

Given cell-average data values of a piecewise smooth bivariate function $f$ within a domain $\Omega$, we look for a piecewise adaptive approximation to $f$. We are interested in an explicit and global (smooth) approach. Bivariate approximation techniques, as trigonometric or splines approximations, achieve reduced approximation orders near the boundary of the domain and near curves of jump singularities of the function or its derivatives. Whereas the boundary of $\Omega$ is assumed to be known, the subdivision of $\Omega$ to subdomains on which $f$ is smooth is unknown. The first challenge of the proposed approximation algorithm would be to find a good approximation to the curves separating the smooth subdomains of $f$. In the second stage, we simultaneously look for approximations to the different smooth segments of $f$, where on each segment we approximate the function by a linear combination of basis functions $\{p_i\}_{i=1}^M$, considering the corresponding cell-averages. A discrete Laplacian operator applied to the given cell-average data intensifies the structure of the singularity of the data across the curves separating the smooth subdomains of $f$. We refer to these derived values as the signature of the data, and we use it for both approximating the singularity curves separating the different smooth regions of $f$. The main contributions here are improved convergence rates to both the approximation of the singularity curves and the approximation of $f$, an explicit and global formula, and, in particular, the derivation of a piecewise smooth high order approximation to the function.

Given gridded cell-average data of a smooth multivariate function, we present a constructive explicit procedure for generating a high-order global approximation of the function. One contribution is the derivation of high order approximations to point-values of the function directly from the cell-average data. The second contribution is the development of univariate B-spline based high order quasi-interpolation operators using cell-average data. Multivariate spline quasi-interpolation approximation operators are obtained by tensor products of the univariate operators.

We present a Markov chain on the $n$-dimensional hypercube $\{0,1\}^n$ which satisfies $t_{{\rm mix}}(\epsilon) = n[1 + o(1)]$. This Markov chain alternates between random and deterministic moves and we prove that the chain has cut-off with a window of size at most $O(n^{0.5+\delta})$ where $\delta>0$. The deterministic moves correspond to a linear shift register., Comment: 17 pages. Revised Sections 1 and 2, added additional references. Proof of Lemma 5 expanded

Active structures have the ability to change their shape, properties, and functionality as a response to changing operational conditions, which makes them more versatile than their static counterparts. However, most active structures currently lack the capability to achieve multiple, different target states with a single input actuation or require a tedious material programming step. Furthermore, the systematic design and fabrication of active structures is still a challenge as many structures are designed by hand in a trial and error process and thus are limited by engineers' knowledge and experience. In this work, a computational design and fabrication framework is proposed to generate structures with multiple target states for one input actuation that don't require a separate training step. A material dithering scheme based on multi-material 3D printing is combined with locally applied copper coil heating elements and sequential heating patterns to control the thermo-mechanical properties of the structures and switch between the different deformation modes. A novel topology optimization approach based on power diagrams is used to encode the different target states in the structure while ensuring the fabricability of the structures and the compatibility with the drop-in heating elements. The versatility of the proposed framework is demonstrated for four different example structures from engineering and computer graphics. The numerical and experimental results show that the optimization framework can produce structures that show the desired motion, but experimental accuracy is limited by current fabrication methods. The generality of the proposed method makes it suitable for the development of structures for applications in many different fields from aerospace to robotics to animated fabrication in computer graphics.

We present a new method for computing a smooth minimum distance function based on the LogSumExp function for point clouds, edge meshes, triangle meshes, and combinations of all three. We derive blending weights and a modified Barnes-Hut acceleration approach that ensure our method approximates the true distance, and is conservative (points outside the zero isosurface are guaranteed to be outside the surface) and efficient to evaluate for all the above data types. This, in combination with its ability to smooth sparsely sampled and noisy data, like point clouds, shortens the gap between data acquisition and simulation, and thereby enables new applications such as direct, co-dimensional rigid body simulation using unprocessed lidar data., Comment: 17 pages, 23 figures