10 Finite Element Algorithms for Computational Biomechanics of the Brain
259
structures of the segmented neuroimages are typically discretised using triangles,
the skull surface can be treated as a triangular mesh. We refer to each triangle surface
as a ‘face’, to the vertices, ‘nodes’, and to the triangle sides – ‘edges’. Using this
terminology, the basic brain–skull contact algorithm is described as follows:
– For each slave node P:
• Find the closest master node C (global search).
• Check the faces and edges surrounding C for penetration (local search).
• Check additional faces and edges that might be penetrated by P (identified in the
master surface analysis stage – because the master surface is rigid, this analysis
can be done pre-operatively).
Following [56, 59], further improvement of efficiency of the penetration detection algorithm and computation speed is done by implementing bucket sort in the
global search phase.
10.7 Real-Time Computations Without Supercomputers:
Increasing Computation Speed Through Algorithm
Implementation on Graphics Processing Unit (GPU)
The algorithms for surgery simulation and image-guided surgery discussed in
this Chapter facilitate efficient and robust computations. For instance, they make
it possible to compute deformation field within the brain for image registration
problem in under 40 s on a standard personal computer for non-linear finite element
models consisting of around 30,000 elements. However, predicting the time history
of force between the soft tissue and surgical tool at frequency of 500 Hz required
for haptic feedback poses a challenge even for very efficient non-linear algorithms
deployed on a personal computer.
For hardware-based increase of computation speed, we advocate the implementation of the algorithms on graphics processing units (GPUs) by using a GPU as a
coprocessor for the computer central processing unit (CPU) for executing sections
of the code that can run in parallel. GPUs have a highly parallel, multithreaded,
multicore processor architecture, and its cost (under US$ 3000 for most general
purpose GPUs) is orders of magnitude smaller than that of a supercomputer with a
comparable number of parallel threads. GPU architecture is well suited for problems
that can be expressed as data-parallel computations with high arithmetic intensity,
where the same programme is executed on many data elements in parallel.
Before the introduction of NVIDIA’s Compute Unified Device Architecture
(CUDA) [62] and Open Computing Language (OpenCL) [63], general-purpose
computations on GPUs were done by recasting the computations in graphic
terms and using the graphics pipeline. Therefore, a scientific or general-purpose
computation often required a concerted effort by experts in both computer graphics
and in the particular scientific or engineering domain. With the introduction of
259
structures of the segmented neuroimages are typically discretised using triangles,
the skull surface can be treated as a triangular mesh. We refer to each triangle surface
as a ‘face’, to the vertices, ‘nodes’, and to the triangle sides – ‘edges’. Using this
terminology, the basic brain–skull contact algorithm is described as follows:
– For each slave node P:
• Find the closest master node C (global search).
• Check the faces and edges surrounding C for penetration (local search).
• Check additional faces and edges that might be penetrated by P (identified in the
master surface analysis stage – because the master surface is rigid, this analysis
can be done pre-operatively).
Following [56, 59], further improvement of efficiency of the penetration detection algorithm and computation speed is done by implementing bucket sort in the
global search phase.
10.7 Real-Time Computations Without Supercomputers:
Increasing Computation Speed Through Algorithm
Implementation on Graphics Processing Unit (GPU)
The algorithms for surgery simulation and image-guided surgery discussed in
this Chapter facilitate efficient and robust computations. For instance, they make
it possible to compute deformation field within the brain for image registration
problem in under 40 s on a standard personal computer for non-linear finite element
models consisting of around 30,000 elements. However, predicting the time history
of force between the soft tissue and surgical tool at frequency of 500 Hz required
for haptic feedback poses a challenge even for very efficient non-linear algorithms
deployed on a personal computer.
For hardware-based increase of computation speed, we advocate the implementation of the algorithms on graphics processing units (GPUs) by using a GPU as a
coprocessor for the computer central processing unit (CPU) for executing sections
of the code that can run in parallel. GPUs have a highly parallel, multithreaded,
multicore processor architecture, and its cost (under US$ 3000 for most general
purpose GPUs) is orders of magnitude smaller than that of a supercomputer with a
comparable number of parallel threads. GPU architecture is well suited for problems
that can be expressed as data-parallel computations with high arithmetic intensity,
where the same programme is executed on many data elements in parallel.
Before the introduction of NVIDIA’s Compute Unified Device Architecture
(CUDA) [62] and Open Computing Language (OpenCL) [63], general-purpose
computations on GPUs were done by recasting the computations in graphic
terms and using the graphics pipeline. Therefore, a scientific or general-purpose
computation often required a concerted effort by experts in both computer graphics
and in the particular scientific or engineering domain. With the introduction of