Ben Jones

Synthesis of Rigorous Floating-Point Predicates

A floating-point predicate is a routine that returns a boolean value based on a result of a floating-point computation. For example, in computational geometry floating-point predicates determine whether 3 points are collinear or which side of a line a point lies on. Due to floating-point round-off errors, implementing such predicates correctly, while maintaining good performance, requires both domain knowledge and deep understanding of the floating-point standard. Hence, it is usually done by experts that carefully craft them by relying on the floating-point round-off error model and complex mathematical derivations. This paper presents our automatic floating-point predicates synthesis method. Given an input predicate specified over reals, our method synthesizes the corresponding rigorous floating-point predicate by automatically deriving the expression that calculates the round-off error-bound of the input computation. We minimize the number of operations in the error-bound calculation, which is critical to maintain good performance, by judiciously reusing intermediate results, applying absolute-value inequalities, adjusting polynomial coefficients, and performing meta-heuristic grouping. We implemented the method in a prototype tool FPSyn. We evaluated FPSyn on 8 floating-point predicates, and showed that it synthesizes predicates whose performance is on par with optimized manually crafted implementations, while they outperform the straightforward interval arithmetic implementations.

Show BibTex

    @article {Nguyen:2022:FPSyn,
    title = {{Synthesis of Rigorous Floating-Point Predicates}},
    author = {Thanh Son Nguyen and Zvonimir Rakamaric and Ben Jones},
    journal = {Proceedings of 28th International Symposium on Model Checking of Software (SPIN)}
    year = {2022},
    volume = {1},
    number = {1}
    }
    

Energized Rigid Body Fracture

Paper
Video

Compelling animation of fracture is a vital challenge for computer graphics. Methods based on continuum mechanics are physically accurate, but computationally expensive since they require computing elastic deformation. In many applications, this elastic deformation is imperceptible, so simulation methods based on rigid body dynamic with breakable constraints are popular in practice. Simply deleting constraints when thresholds on force or displacement are reached ignores the elastic energy that is stored just before fracture, which is captured by continuum mechanics based methods. Our approach computes the energy stored in these constraints when they are broken, and reintroduces it to the system as kinetic energy. As a result, our method is able to animate energetic fracture scenarios with results comparable to continuum mechanics approaches, but with the computational efficiency of rigid body simulation.

Show BibTex

    @article {Li:2018:ERBF,
    title = {{Energized Rigid Body Fracture}},
    author = {Li, Xiaokai and Andrews, Sheldon and Jones, Ben and Bargteil, Adam},
    journal = {Proceedings of the ACM on Computer Graphics and Interactive Techniques (PACM CGIT)},
    year = {2018},
    volume = {1},
    number = {1}
    }
    

Efficient Collision Detection for Example-Based Deformable Bodies

Paper
Video

We introduce a new collision proxy for example-based deformable bodies. Specifically, we approximate the deforming geometry as a union of spheres. During pre-computation we perform a sphere packing on the input, undeformed geometry. Then, for each example pose, we move and resize the spheres to approximate the example. During runtime we blend together these positions and radii, using the same skinning weights we use for the geometry. We demonstrate the method on a car crash example, where we achieve an overall speedup of 5-20 times, depending on the resolution of the collision proxy geometry.

Show BibTex

  @inproceedings{Jones:2017:ECD,
  author = {Ben Jones and Joshua A. Levine and Tamar Shinar and Adam W. Bargteil}
  title = {Efficient Collision Detection for Example-Based Deformable Bodies}
  booktitle = {Proceedings of the ACM SIGGRAPH Conference on Motion in Games},
  series = {MIG '17},
  year = {2017},
  month = {Nov},
  location= {Barcelona}
  }   

Reclustering for Large Plastisticity in Clustered Shape Matching

Paper
Video

In this paper, we revisit the problem online reclustering in clustered shape matching simulations and propose an approach that employs two nonlinear optimizations to create new clusters. The first optimization finds the embedding of particles and clusters into three-dimensional space that minimizes elastic energy. The second finds the optimal location for the new cluster, working in this embedded space. The result is an approach that is more robust in the presence of elastic deformation. We also experimentally verify that our clustered shape matching approach converges as the number of clusters increases, suggesting that our reclustering approach does not change the underlying material properties. Further, we demonstrate that particle resampling is not strictly necessary in our framework allowing us to trivially conserve volume. Finally, we highlight an error in estimating rotations in the original shape-matching work [Muüller et al. 2005] that has been repeated in much of the follow up work.

Show BibTex

  @inproceedings{Falkenstein:2017:RLP,
  author = {Michael Falkenstein and Ben Jones and Joshua A. Levine and Tamar Shinar and Adam W. Bargteil}
  title = {Reclustering for Large Plasticity in Clustered Shape Matching}
  booktitle = {Proceedings of the ACM SIGGRAPH Conference on Motion in Games},
  series = {MIG '17},
  year = {2017},
  month = {Nov},
  location= {Barcelona}
  }   

Example-Based Plastic Deformation of Rigid Bodies

Project Page

Physics-based animation is often used to animate scenes containing destruction of near-rigid, man-made materials. For these applications, the most important visual features are plastic deformation and fracture. Methods based on continuum mechanics model these materials as elastoplastic, and must perform expensive elasticity computations even though elastic deformations are imperceptibly small for rigid materials. We introduce an example-based plasticity model based on linear blend skinning that allows artists to author simulation objects using familiar tools. Dynamics are computed using an unmodified rigid body simulator, making our method computationally efficient and easy to integrate into existing pipelines. We introduce a flexible technique for mapping impulses computed by the rigid body solver to local, example-based deformations. For completeness, our method also supports prescoring based fracture. We demonstrate the practicality of our method by animating a variety of destructive scenes.

Show BibTex

@article{Jones:2016:EPD,
author = {Ben Jones and Nils Thuerey and Tamar Shinar and Adam W. Bargteil},
title = {Example-based Plastic Deformation of Rigid Bodies}
journal = {ACM Trans. Graph.},
year = {2016},
month = {July},
number = {4},
volume = {35}
}   

Ductile Fracture for Clustered Shape Matching

Project Page

In this paper, we incorporate ductile fracture into the clustered shape matching simulation framework for deformable bodies, thus filling a gap in the shape matching literature. Our plasticity and fracture models are inspired by the finite element literature on deformable bodies, but are adapted to the clustered shape matching framework. The resulting approach is fast, versatile, and simple to implement.

Show BibTex

  @inproceedings{Jones:2016:DFC,
  author = {Ben Jones and April Martin and Joshua A. Levine and Tamar Shinar and Adam W. Bargteil},
  title = {Ductile Fracture for Clustered Shape Matching}
  booktitle = {Proceedings of the 2016 symposium on Interactive 3D graphics and games},
  year = {2016},
  month = {Feb},
  location = {Redmond, WA}
  }
  

Clustering and Collision Detection for Clustered Shape Matching

Project Page

In this paper, we address clustering and collision detection in the clustered shape matching simulation framework for deformable bodies. Our clustering algorithm is “fuzzy,” meaning that it gives particles weighted membership in clusters. These weights are a significant extension to the basic clustered shape matching framework as they are used to divide particle mass among the clusters. We explore several weighting schemes and demonstrate that the choice of weighting scheme gives artists additional control over material behavior. Furthermore, by design our clustering algorithm yields spherical clusters, which not only results in sparse weight vectors, but also exceptionally efficient collision geometry. We further enhance this simple collision proxy by intersecting with half-spaces to allow for even better, yet still simple and computationally efficient, collision proxies. The resulting approach is fast, versatile, and simple to implement.

Show BibTex

  @inproceedings{Jones:2015:CCD,
  author = {Ben Jones and April Martin and Joshua A. Levine and Tamar Shinar and Adam W. Bargteil},
  title = {Clustering and Collision Detection for Clustered Shape Matching}
  booktitle = {Proceedings of the ACM SIGGRAPH Conference on Motion in Games},
  series = {MIG '15},
  year = {2015},
  month = {Nov},
  location = {Paris}
  }
  

Strain Limiting for Clustered Shape Matching

Winner Best Presentation Award

Project Page

In this paper, we advocate explicit symplectic Euler integration and strain limiting in a shape matching simulation framework. The resulting approach resembles not only previous work on shape matching and strain limiting, but also the recently popular position-based dynamics. However, unlike this previous work, our approach reduces to explicit integration under small strains, but remains stable in the presence of non-linearities.

Show BibTex

  @inproceedings{Bargteil:2014:SLF,
  author = {Adam Bargteil and Ben Jones},
  title = {Strain Limiting for Clustered Shape Matching}
  booktitle = {Proceedings of the ACM SIGGRAPH Conference
  on Motion in Games},
  series = {MIG '14},
  year = {2014},
  month = {Nov},
  location = {Los Angeles}
  }
  

Deformation Embedding for Point-Based Elastoplastic Simulation

Project Page

We present a straightforward, easy-to-implement, point-based approach for animating elastoplastic materials. The core idea of our approach is the introduction of embedded space, the least-squares best fit of the material's rest state into three dimensions. Nearest neighbor queries in the embedded space efficiently update particle neighborhoods to account for plastic flow. These queries are simpler and more efficient than remeshing strategies employed in mesh-based finite element methods. We also introduce a new estimate for the volume of a particle, allowing particle masses to vary spatially and temporally with fixed density. Our approach can handle simultaneous extreme elastic and plastic deformations. We demonstrate our approach on a variety of examples that exhibit a wide range of material behaviors.

Show BibTex

  @article{Jones:2014:DEF,
  author = {Ben Jones and Stephen Ward and Ashok Jallepalli and
  Joseph Perenia and Adam Bargteil},
  title = {Deformation Embedding for Point-Based Elastoplastic Simulation}
  journal = {ACM Trans. Graph.},
  year = {2014},
  month = {March},
  volume = {33},
  number = {2}
  
  }
  

Dynamic Sprites

Winner Best Student Paper Award

Project Page

Traditional methods for creating dynamic objects and characters from static drawings involve careful tweaking of animation curves and/or simulation parameters. Sprite sheets offer a more drawing-centric solution, but they do not encode timing information or the logic that determines how objects should transition between poses and cannot generalize outside the given drawings. We present an approach for creating dynamic sprites that leverages sprite sheets while addressing these limitations. In our system, artists create a drawing, deform it to specify a small number of example poses, and indicate which poses can be interpolated. To make the object move, we design a procedural simulation to navigate the pose manifold in response to external or user-controlled forces. Powerful artistic control is achieved by allowing the artist to specify both the pose manifold and how it is navigated, while physics is leveraged to provide timing and generality. We used our method to create sprites with a range of different dynamic properties.

Show BibTex

  @inproceedings{Jones:2013:DS,
  author = {Ben Jones and Jovan Popovi{\'{c}} and
  James McCann and Wilmot Li and Adam Bargteil},
  title = {Dynamic Sprites},
  booktitle = {Proceedings of the ACM SIGGRAPH Conference
  on Motion in Games},
  year = {2013},
  month = {Nov},
  location = {Dublin,Ireland}
  }
  @article{jones2014dynamic,
  title={Dynamic sprites: artistic authoring of interactive animations},
  author={Jones, Ben and Popovic, Jovan and McCann, James and Li, Wilmot and Bargteil, Adam},
  journal={Computer Animation and Virtual Worlds},
  year={2014},
  publisher={Wiley Online Library}
}

Automatic Construction of Coarse, High-Quality Tetrahedralizations that Enclose and Approximate Surfaces for Animation

Project Page

Embedding high-resolution surface geometry in coarse control meshes is a standard approach to achieving high-quality computer animation at low computational expense. In this paper we present an effective, automatic method for generating such control meshes. The resulting high-quality, tetrahedral meshes enclose and approximate an input surface mesh, avoiding extrapolation artifacts and ensuring that the resulting coarse volumetric meshes are adequate collision proxies. Our approach comprises three steps: we begin with a tetrahedral mesh built from the body-centered cubic lattice that tessellates the bounding box of the input surface; we then perform a sculpting phase that carefully removes elements from the lattice; and finally a variational vertex adjustment phase iteratively adjusts vertex positions to more closely approximate the surface geometry. Our approach provides explicit trade-offs between mesh quality, resolution, and surface approximation. Our experiments demonstrate the technique can be used to build high-quality meshes appropriate for simulations within games.

Show BibTex

  @inproceedings{Stuart:2013:ACC,
  author = {David Stuart and Joshua Levine and
  Ben Jones and Adam Bargteil},
  title = {Automatic Construction of Coarse, High-Quality
  Tetrahedralizations that Enclose and Approximate
  Surfaces for Animation},
  booktitle = {Proceedings of the ACM SIGGRAPH Conference
  on Motion in Games},
  year = {2013},
  month = {Nov},
  location = {Dublin,Ireland}
  }
  

Locomotion Skills for Simulated Quadrupeds

Project webpage (featuring Windows binary demo)

We develop an integrated set of gaits and skills for a physics-based simulation of a quadruped. The motion repertoire for our simulated dog includes walk, trot, pace, canter, transverse gallop, rotary gallop, leaps capable of jumping on-and-off platforms and over obstacles, sitting, lying down, standing up, and getting up from a fall. The controllers use a representation based on gait graphs, a dual leg frame model, a flexible spine model, and the extensive use of internal virtual forces applied via the Jacobian transpose. Optimizations are applied to these control abstractions in order to achieve robust gaits and leaps with desired motion styles. The resulting gaits are evaluated for robustness with respect to push disturbances and the traversal of variable terrain. The simulated motions are also compared to motion data captured from a filmed dog.

Show BibTex

@article{Coros:2011:LSS:2010324.1964954,
author = {Coros, Stelian and Karpathy, Andrej and
Jones, Ben and Reveret, Lionel and
van de Panne, Michiel},
title = {Locomotion skills for simulated quadrupeds},
journal = {ACM Trans. Graph.},
issue_date = {July 2011},
volume = {30},
number = {4},
month = jul,
year = {2011},
issn = {0730-0301},
pages = {59:1--59:12},
articleno = {59},
numpages = {12},
url = {http://doi.acm.org/10.1145/2010324.1964954},
doi = {10.1145/2010324.1964954},
} 

Masters Thesis:
Rising Motion Controllers for Physically Simulated Characters

PDF

The control of physics-based simulated characters is an important open problem with potential applications in film, games, robotics, and biomechanics. While many methods have been developed for locomotion and quiescent stance, the problem of returning to a standing posture from a sitting or fallen posture has received much less attention. In this thesis, we develop controllers for biped sit-to-stand, quadruped getting-up, and biped prone-to-stand motions. These controllers are created from a shared set of simple components including pose-tracking, root orientation correction, and virtual force based control. We also develop an optimization strategy that generates fast, dynamic rising motions from an initial statically stable motion. This stragety is also used to generalize controllers to sloped terrain and characters of varying size.

Show BibTex

  @MASTERSTHESIS{
  jonesThesis2011,
  author = {Ben Jones},
  title = {Rising Motion Controllers for 
  Physically Simulated Characters},
  school = {University of British Columbia},
  year = {2011}
  }