Publications
GIPC: Fast and stable Gauss-Newton optimization of IPC barrier energy
Barrier functions are crucial for maintaining an intersection and inversion free simulation trajectory but existing methods which directly use distance can restrict implementation design and performance. We present an approach to rewriting the barrier function for arriving at an efficient and robust approximation of its Hessian. The key idea is to formulate a simplicial geometric measure of contact using mesh boundary elements, from which analytic eigensystems are derived and enhanced with filtering and stiffening terms that ensure robustness with respect to the convergence of a Project-Newton solver. A further advantage of our rewriting of the barrier function is that it naturally caters to the notorious case of nearly-parallel edge-edge contacts for which we also present a novel analytic eigensystem. Our approach is thus well suited for standard second order unconstrained optimization strategies for resolving contacts, minimizing nonlinear nonconvex functions where the Hessian may be indefinite. The efficiency of our eigensystems alone yields a 3 × speedup over the standard IPC barrier formulation. We further apply our analytic proxy eigensystems to produce an entirely GPU-based implementation of IPC with significant further acceleration.
Kemeng Huang, Floyd M. Chitalu, Huancheng Lin, and Taku Komura. 2024. GIPC: Fast and stable Gauss-Newton optimization of IPC barrier energy. ACM Trans. Graph. Just Accepted (January 2024). https://doi.org/10.1145/3643028
Related Project(s): https://ipc-sim.github.io/
Source code, video & supplementary document coming soon..
Isotropic ARAP energy using Cauchy-Green invariants
Isotropic As-Rigid-As-Possible (ARAP) energy has been popular for shape editing, mesh parametrisation and soft-body simulation for almost two decades. However, a formulation using Cauchy-Green (CG) invariants has always been unclear, due to a rotation-polluted trace term that cannot be directly expressed using these invariants. We show how this incongruent trace term can be understood via an implicit relationship to the CG invariants. Our analysis reveals this relationship to be a polynomial where the roots equate to the trace term, and where the derivatives also give rise to closed-form expressions of the Hessian to guarantee positive semi-definiteness for a fast and concise Newton-type implicit time integration. A consequence of this analysis is a novel approach to determine rotations and singular values of deformation-gradient tensors without explicit/numerical factorization which is significant, resulting in up-to 3.5× speedup and benefits energy function evaluation for reducing solver time. We validate our energy formulation by experiments and comparison, demonstrating that our resulting eigendecomposition using the CG invariants is equivalent to existing ARAP formulations. We thus reveal isotropic ARAP energy to be a member of the “Cauchy-Green club”, meaning that it can indeed be defined using CG invariants and therefore that the closed-form expressions of the resulting Hessian are shared with other energies written in their terms.
Huancheng Lin, Floyd M. Chitalu, and Taku Komura. 2022. Isotropic ARAP energy using Cauchy-Green invariants. ACM Transactions on Graphics, Volume 41, Issue 6, December 2022, Article No.: 275, pp 1–14, https://doi.org/10.1145/3550454.3555507
Simulating brittle fracture with material points
Large-scale topological changes play a key role in capturing the fine debris of fracturing virtual brittle material. Real-world, tough brittle fractures have dynamic branching behaviour but numerical simulation of this phenomena is notoriously challenging. In order to robustly capture these visual characteristics, we simulate brittle fracture by combining elastostatic continuum mechanical models with rigid-body methods: A continuum damage mechanics problem is solved, following rigid-body impact, to simulate crack propagation by tracking a damage field. We combine the result of this elastostatic continuum model with a novel technique to approximate cracks as a non-manifold mid-surface, which enables accurate and robust modelling of material fragment volumes to compliment fast-and-rigid shatter effects. For enhanced realism, we add fracture detail, incorporating particle damage-time to inform localised perturbation of the crack surface with artistic control. We evaluate our method with numerous examples and comparisons, showing that it produces a breadth of brittle material fracture effects and with low simulation resolution to require much less time compared to fully elastodynamic simulations.
Linxu Fan, Floyd M. Chitalu, and Taku Komura. 2022. Simulating Brittle Fracture with Material Points. ACM Transactions on Graphics, Volume 41, Issue 5, October 2022, Article No.: 177, pp 1–20, https://doi.org/10.1145/3522573
Binary Ostensibly-Implicit Trees for Fast Collision Detection
We present a simple, efficient and low-memory technique, targeting fast construction of bounding volume hierarchies (BVH)for broad-phase collision detection. To achieve this, we devise a novel representation of BVH trees in memory. We develop amapping of the implicit index representation to compact memory locations, based on simple bit-shifts, to then construct andevaluate bounding volume test trees (BVTT) during collision detection with real-time performance. We model the topology ofthe BVH tree implicitly as binary encodings which allows us to determine the nodes missing from a complete binary tree usingthe binary representation of the number of missing nodes. The simplicity of our technique allows for fast hierarchy constructionachieving over6×speedup over the state-of-the-art. Making use of these characteristics, we show that not only it is feasible torebuild the BVH at every frame, but that using our technique, it is actually faster than refitting and more memory efficient.
Chitalu, F.M., Dubach, C. and Komura, T. (2020), Binary Ostensibly-Implicit Trees for Fast Collision Detection. Computer Graphics Forum, 39: 509-521. https://doi.org/10.1111/cgf.13948
Displacement-Correlated XFEM for Simulating Brittle Fracture
We present a remeshing-free brittle fracture simulation method under the assumption of quasi-static linear elastic fracture mechanics (LEFM). To achieve this, we devise two algorithms. First, we develop an approximate volumetric simulation, based on the extended Finite Element Method (XFEM), to initialize and propagate Lagrangian crack-fronts. We model the geometry of fracture explicitly as a surface mesh, which allows us to generate high-resolution crack surfaces that are decoupled from the resolution of the deformation mesh. Our second contribution is a mesh cutting algorithm, which produces fragments of the input mesh using the fracture surface. We do this by directly operating on the half-edge data structures of two surface meshes, which enables us to cut general surface meshes including those of concave polyhedra and meshes with abutting concave polygons. Since we avoid triangulation for cutting, the connectivity of the resulting fragments is identical to the (uncut) input mesh except at edges introduced by the cut. We evaluate our simulation and cutting algorithms and show that they outperform state-of-the-art approaches both qualitatively and quantitatively.
Chitalu, F. M., Miao, Q., Subr, K. and Komura, T. (2020), Displacement-Correlated XFEM for Simulating Brittle Fracture. Computer Graphics Forum, 39: 569-583. https://doi.org/10.1111/cgf.13953
Bulk-synchronous parallel simultaneous BVH traversal for collision detection on GPUs
Simultaneous BVH traversal, as a dynamic task of pair-wise proximity tests, poses several challenges in terms of parallelization using GPUs. It is a highly dynamic and data-dependent problem which can induce control-flow divergence and inefficient data-access patterns. We present a simple solution using the bulk-synchronous parallel model to ensure a uniform mode of execution, and balanced workloads across GPU threads. The method is easy to implement, fast and operates entirely on the GPU by relying on a topology-centred work expansion scheme to ensure large concurrent workloads. We demonstrate speedups of upto 7.1x over the widely used "streams" model for GPU based parallel collision detection.
Floyd M. Chitalu, Christophe Dubach, and Taku Komura. 2018. Bulk-synchronous parallel simultaneous BVH traversal for collision detection on GPUs. In Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D '18). Association for Computing Machinery, New York, NY, USA, Article 4, 1–9. https://doi.org/10.1145/3190834.3190848
Method for Efficient CPU-GPU Streaming for Walkthrough of Full Motion Lightfield Video
Lightfield video, as a high-dimensional function, is very demanding in terms of storage. As such, lightfield video data, even in a compressed form, do not typically fit in GPU or main memory unless the capture area, resolution or duration is sufficiently small. Additionally, latency minimization--critical for viewer comfort in use-cases such as virtual reality--places further constraints in many compression schemes. In this paper, we propose a scalable method for streaming lightfield video, parameterized on viewer location and time, that efficiently handles RAM-to-GPU memory transfers of lightfield video in a compressed form, utilizing the GPU architecture for reduction of latency. We demonstrate the effectiveness of our method in a variety of compressed animated lightfield datasets.
Floyd M. Chitalu, Babis Koniaris, and Kenny Mitchell. 2017. Method for Efficient CPU-GPU Streaming for Walkthrough of Full Motion Lightfield Video. In Proceedings of the 14th European Conference on Visual Media Production (CVMP 2017) (CVMP 2017). Association for Computing Machinery, New York, NY, USA, Article 8, 1–9. https://doi.org/10.1145/3150165.3150173
PhD Thesis : Accelerating and Simulating Detected Physical Interactions
The aim of this doctoral thesis is to present a body of work aimed at improving performance and developing new methods for animating physical interactions using simulation in virtual environments. To this end we develop a number of novel parallel collision detection and fracture simulation algorithms. Methods for traversing and constructing bounding volume hierarchies (BVH) on graphics processing units (GPU) have had a wide success. In particular, they have been adopted widely in simulators, libraries and benchmarks as they allow applications to reach new heights in terms of performance. Even with such a development however, a thorough adoption of techniques has not occurred in commercial and practical applications. Due to this, parallel collision detection on GPUs remains a relatively niche problem and a wide number of applications could benefit from a significant boost in proclaimed performance gains. In fracture simulations, explicit surface tracking methods have a good track record of success. In particular they have been adopted thoroughly in 3D modelling and animation software like Houdini [124] as they allow accurate simulation of intricate fracture patterns with complex interactions, which are generated using physical laws. Even so, existing methods can pose restrictions on the geometries of simulated objects. Further, they often have tight dependencies on implicit surfaces (e.g. level sets) for representing cracks and performing cutting to produce rigid-body fragments. Due to these restrictions, catering to various geometries can be a challenge and the memory cost of using implicit surfaces can be detrimental and without guarantee on the preservation of sharp features. We present our work in four main chapters. We first tackle the problem in the accelerating collision detection on the GPU via BVH traversal - one of the most demanding components during collision detection. Secondly, we show the construction of a new representation of the BVH called the ostensibly implicit tree - a layout of nodes in memory which is encoded using the bitwise representation of the number of enclosed objects in the tree (e.g. polygons). Thirdly, we shift paradigm to the task of simulating breaking objects after collision: we show how traditional finite elements can be extended as a way to prevent frequent re-meshing during fracture evolution problems. Finally, we show how the fracture surface–represented as an explicit (e.g. triangulated) surface mesh–is used to generate rigid body fragments using a novel approach to mesh cutting.
Floyd M. Chitalu. Accelerating and Simulating Detected Physical Interactions. Doctoral Thesis. The University of Edinburgh (April 2020), 157 pages. http://dx.doi.org/10.7488/era/388