Search

Many geometry processing techniques require the solution of partial differential equations (PDEs) on surfaces. Such surface PDEs often involve boundary conditions prescribed on the surface, at points or curves on its interior or along the geometric (exterior) boundary of an open surface. However, input surfaces can take many forms (e.g., meshes, parametric surfaces, point clouds, level sets, neural implicits). One must therefore generate a mesh to apply finite element-type techniques or derive specialized discretization procedures for each surface representation. We propose instead to address such problems through a novel extension of the closest point method (CPM) to handle interior boundary conditions specified at surface points or curves. CPM solves the surface PDE by solving a volumetric PDE defined over the Cartesian embedding space containing the surface; only a closest point function is required to represent the surface. As such, CPM supports surfaces that are open or closed, orientable or not, and of any codimension or even mixed-codimension. To enable support for interior boundary conditions, we develop a method to implicitly partition the embedding space across interior boundaries. CPM's finite difference and interpolation stencils are adapted to respect this partition while preserving second-order accuracy. Furthermore, an efficient sparse-grid implementation and numerical solver is developed that can scale to tens of millions of degrees of freedom, allowing PDEs to be solved on more complex surfaces. We demonstrate our method's convergence behaviour on selected model PDEs. Several geometry processing problems are explored: diffusion curves on surfaces, geodesic distance, tangent vector field design, and harmonic map construction. Our proposed approach thus offers a powerful and flexible new tool for a range of geometry processing tasks on general surface representations., 24 pages

Tensegrity robots, composed of rigid rods and flexible cables, exhibit high strength-to-weight ratios and significant deformations, which enable them to navigate unstructured terrains and survive harsh impacts. They are hard to control, however, due to high dimensionality, complex dynamics, and a coupled architecture. Physics-based simulation is a promising avenue for developing locomotion policies that can be transferred to real robots. Nevertheless, modeling tensegrity robots is a complex task due to a substantial sim2real gap. To address this issue, this paper describes a Real2Sim2Real (R2S2R) strategy for tensegrity robots. This strategy is based on a differentiable physics engine that can be trained given limited data from a real robot. These data include offline measurements of physical properties, such as mass and geometry for various robot components, and the observation of a trajectory using a random control policy. With the data from the real robot, the engine can be iteratively refined and used to discover locomotion policies that are directly transferable to the real robot. Beyond the R2S2R pipeline, key contributions of this work include computing non-zero gradients at contact points, a loss function for matching tensegrity locomotion gaits, and a trajectory segmentation technique that avoids conflicts in gradient evaluation during training. Multiple iterations of the R2S2R process are demonstrated and evaluated on a real 3-bar tensegrity robot., Comment: Submitted to IROS2023

This paper presents a novel method for generating a single polynomial approximation that produces correctly rounded results for all inputs of an elementary function for multiple representations. The generated polynomial approximation has the nice property that the first few lower degree terms produce correctly rounded results for specific representations of smaller bitwidths, which we call progressive performance. To generate such progressive polynomial approximations, we approximate the correctly rounded result and formulate the computation of correctly rounded polynomial approximations as a linear program similar to our prior work on the RLibm project. To enable the use of resulting polynomial approximations in mainstream libraries, we want to avoid piecewise polynomials with large lookup tables. We observe that the problem of computing polynomial approximations for elementary functions is a linear programming problem in low dimensions, i.e., with a small number of unknowns. We design a fast randomized algorithm for computing polynomial approximations with progressive performance. Our method produces correct and fast polynomials that require a small amount of storage. A few polynomial approximations from our prototype have already been incorporated into LLVM's math library., Comment: 14 pages

We present an arbitrary updated Lagrangian Material Point Method (A-ULMPM) to alleviate issues, such as the cell-crossing instability and numerical fracture, that plague state of the art Eulerian formulations of MPM, while still allowing for large deformations that arise in fluid simulations. Our proposed framework spans MPM discretizations from total Lagrangian formulations to Eulerian formulations. We design an easy-to-implement physics-based criterion that allows A-ULMPM to update the reference configuration adaptively for measuring physical states including stress, strain, interpolation kernels and their derivatives. For better efficiency and conservation of angular momentum, we further integrate the APIC[Jiang et al. 2015] and MLS-MPM[Hu et al. 2018] formulations in A-ULMPM by augmenting the accuracy of velocity rasterization using both the local velocity and its first-order derivatives. Our theoretical derivations use a nodal discretized Lagrangian, instead of the weak form discretization in MLS-MPM[Hu et al. 2018], and naturally lead to a "modified" MLS-MPM in A-ULMPM, which can recover MLS-MPM using a completely Eulerian formulation. A-ULMPM does not require significant changes to traditional Eulerian formulations of MPM, and is computationally more efficient since it only updates interpolation kernels and their derivatives when large topology changes occur. We present end-to-end 3D simulations of stretching and twisting hyperelastic solids, splashing liquids, and multi-material interactions with large deformations to demonstrate the efficacy of our novel A-ULMPM framework., Comment: First two authors share joint first authorship

We propose a novel differentiable physics engine for system identification of complex spring-rod assemblies. Unlike black-box data-driven methods for learning the evolution of a dynamical system \emph{and} its parameters, we modularize the design of our engine using a discrete form of the governing equations of motion, similar to a traditional physics engine. We further reduce the dimension from 3D to 1D for each module, which allows efficient learning of system parameters using linear regression. The regression parameters correspond to physical quantities, such as spring stiffness or the mass of the rod, making the pipeline explainable. The approach significantly reduces the amount of training data required, and also avoids iterative identification of data sampling and model training. We compare the performance of the proposed engine with previous solutions, and demonstrate its efficacy on tensegrity systems, such as NASA's icosahedron., Workshop on Differentiable Vision, Graphics, and Physics in Machine Learning at NeurIPS 2020. arXiv admin note: substantial text overlap with arXiv:2004.13859

We present the design of a low-cost wheeled mobile robot, and an analytical model for predicting its motion under the influence of motor torques and friction forces. Using our proposed model, we show how to analytically compute the gradient of an appropriate loss function, that measures the deviation between predicted motion trajectories and real-world trajectories, which are estimated using Apriltags and an overhead camera. These analytical gradients allow us to automatically infer the unknown friction coefficients, by minimizing the loss function using gradient descent. Motion trajectories that are predicted by the optimized model are in excellent agreement with their real-world counterparts. Experiments show that our proposed approach is computationally superior to existing black-box system identification methods and other data-driven techniques, and also requires very few real-world samples for accurate trajectory prediction. The proposed approach combines the data efficiency of analytical models based on first principles, with the flexibility of data-driven methods, which makes it appropriate for low-cost robots. Using the learned model and our gradient-based optimization approach, we show how to automatically compute motor control signals for driving the robot along pre-specified curves.

Given the importance of floating-point~(FP) performance in numerous domains, several new variants of FP and its alternatives have been proposed (e.g., Bfloat16, TensorFloat32, and Posits). These representations do not have correctly rounded math libraries. Further, the use of existing FP libraries for these new representations can produce incorrect results. This paper proposes a novel approach for generating polynomial approximations that can be used to implement correctly rounded math libraries. Existing methods generate polynomials that approximate the real value of an elementary function $f(x)$ and produce wrong results due to approximation errors and rounding errors in the implementation. In contrast, our approach generates polynomials that approximate the correctly rounded value of $f(x)$ (i.e., the value of $f(x)$ rounded to the target representation). It provides more margin to identify efficient polynomials that produce correctly rounded results for all inputs. We frame the problem of generating efficient polynomials that produce correctly rounded results as a linear programming problem. Our approach guarantees that we produce the correct result even with range reduction techniques. Using our approach, we have developed correctly rounded, yet faster, implementations of elementary functions for multiple target representations., 44 pages

We propose a novel differentiable physics engine for system identification of complex spring-rod assemblies. Unlike black-box data-driven methods for learning the evolution of a dynamical system and its parameters, we modularize the design of our engine using a discrete form of the governing equations of motion, similar to a traditional physics engine. We further reduce the dimension from 3D to 1D for each module, which allows efficient learning of system parameters using linear regression. As a side benefit, the regression parameters correspond to physical quantities, such as spring stiffness or the mass of the rod, making the pipeline explainable. The approach significantly reduces the amount of training data required, and also avoids iterative identification of data sampling and model training. We compare the performance of the proposed engine with previous solutions, and demonstrate its efficacy on tensegrity systems, such as NASA's icosahedron., Comment: accepted at 2020 Learning for Dynamics and Control (L4DC2020)

We consider the problem of computing a triangulation of the real projective plane P2, given a finite point set S={p1, p2,..., pn} as input. We prove that a triangulation of P2 always exists if at least six points in S are in general position, i.e., no three of them are collinear. We also design an algorithm for triangulating P2 if this necessary condition holds. As far as we know, this is the first computational result on the real projective plane.