Florian Hecht, Yeon Jin Lee, Jonathan R. Shewchuk, and James F. O'Brien,
Updated Sparse Cholesky Factors for Corotational Elastodynamics,
ACM Transactions on Graphics 31(5):123.1–123.13, October 2012.
PDF (color, 24,436k, 13 pages).
We introduce warp-canceling corotation,
a nonlinear finite element formulation for elastodynamic simulation that
achieves fast performance by making only partial or
delayed changes to the simulation's linearized system matrices.
This formulation combines the widely used corotational finite element method
with stiffness warping so that changes in the per-element rotations are
initially approximated by inexpensive per-node rotations.
When the errors of this approximation grow too large,
the per-element rotations are selectively corrected by updating parts of
the matrix chosen according to locally measured errors.
These changes to the system matrix are propagated to
its sparse Cholesky factor by incremental updates that are
much faster than refactoring the matrix from scratch.
A nested dissection ordering of the system matrix gives rise to
a hierarchical factorization in which changes to the system matrix cause
limited, well-structured changes to the Cholesky factor.
Because our method requires computing only partial updates of
the Cholesky factor, it is substantially faster than
full refactorization and outperforms widely used iterative methods such as
preconditioned conjugate gradients, but
it realizes the stability and scalability of a sparse direct method.
Unlike iterative methods, our method's performance does not slow for
stiffer materials; rather, it improves.
Nuttapong Chentanez, Ron Alterovitz, Daniel Ritchie, Lita Cho, Kris K. Hauser,
Ken Goldberg, Jonathan R. Shewchuk, and James F. O'Brien,
Interactive Simulation of Surgical Needle Insertion and Steering,
ACM Transactions on Graphics 28(3):88.1–88.10, August 2009.
Special issue on Proceedings of SIGGRAPH 2009.
PDF (color, 6,580k, 10 pages).
Clinical procedures such as biopsies, injections, and neurosurgery involve
inserting a needle into tissue; here we focus on
brachytherapy cancer treatment with a steerable needle,
in which radioactive seeds are injected
into a prostate gland to locally irradiate tumors.
Needle insertion deforms body tissues, making it difficult to
accurately place the needle tip while avoiding vulnerable vessels and nerves.
We describe an interactive, real-time simulator of needle insertion that
might lead to software for training surgeons and planning surgeries based on
medical images from patients.
The simulator models the coupling between a steerable needle and
deformable tissue as a linear complementarity problem.
A key part of our simulator is
a novel algorithm for dynamic local remeshing that quickly enforces
the conformity of a tetrahedral tissue mesh to a curvilinear needle path,
enabling accurate computation of contact forces.
Because a one-dimensional needle intersects the tissue mesh in simple ways,
we can use a simple and fast dynamic meshing algorithm that
keeps the quality of the modified tetrahedra high in practice.