abstract
- Real-time simulation of haptic interaction with deformable objects is computationally demanding. In particular in finite-element (FE) based analysis of such interactions, a large system of equations must be solved at an update rate of 100-1,000 Hz for simulation fidelity and stability. A new hardware-based parallel implementation of a Preconditioned Conjugate Gradient (PCG) algorithm is proposed for solving the linear systems of equations arising from FE-based deformation models. Concurrent utilization of a large number of fixed-point computing units on a Field-Programmable Gate Array (FPGA) device yields a very fast solution to these equations. Quantization and overflow errors in the fixed-point implementation of the iterative solver are minimized through dynamic scaling and preconditioning. Numerical accuracy of the solution, the architecture design, and issues pertaining to the degree of parallelism and scalability of the architecture are discussed in detail. The implementation of the solver on an Altera EP3SE110 FPGA device has enabled real-time simulation of three-dimensional linear elastic deformation models with 1,500 nodes at an update rate of up to 2,500 Hz.