In this thesis we investigate the benefits achieved by exploiting parallel algorithms on typical Computer Graphics problems. Given three different parallel architectures, the impact in term of performance on well known geometry tasks is examined. We start by considering simple SSE instructions for SIMD level parallelism using Intel SSE intrinsics. Then, shared-memory parallelism on multiprocessing machines and the dedicated OpenMP API are investigated. Finally, we consider General-Purpose computing on Graphics Processing Units together with NVIDIA CUDA technology. By exploiting these three types of parallelism, a Conjugate Gradient method for sparse linear systems derived by the harmonic parameterization is implemented. Further, a parallel Multigrid solver for finite element simulations based on hexahedral cells is developed. During the implementations of such methods, timings and speedups are measured, in order to find which parallel paradigm is best situated for each one of these problems.

[Dissertation]

The parameterization of a surface is a bijective (one-to-one) mapping from the surface to a suitable region. In general, the surface is embedded in R³ and the target region is a subset of R². A parameterization can be formulated to guarantee some properties of the parameterized surface, like no distortion in angles (conformal mapping) or no distortion in areas (equiareal mapping). One can show that if a mapping is conformal it is also harmonic. Harmonic mappings, however, have the big advantage over conformal mappings of being simpler to compute. Harmonic mapping can be approximated by using a finite element method based on linear elements. This approach leads to solve a large sparse system of linear equations where the associated coefficient matrix is symmetric and positive definite. A well known iterative solver for such kind of systems is the Conjugate Gradient (CG) method. Starting from an initial guess, the CG finds a sequence of approximations to the real solution. In this experiment, we captured each step of the CG for the harmonic parameterization problem. At each iteration, the solver converges to the solution and therefore the visual appearance of the textured surface becomes more plausible.

[Movie]

In contrast with sequential architectures, where a sequence of instructions is executed one after the other, parallel architectures allow to execute many instructions simultaneously. There are many types of parallelism, and each of them needs dedicated hardware resources. Shared-Memory Parallel Computers are machines with multiple processors that communicate through variables stored in a shared address space. OpenMP^TM API is the de-facto standard for development on shared-memory multiprocessing machines. It is based on a thread paradigm: a process consists of many threads, that is, active executions of instructions within the process. Threads share the same memory space and, in a multiprocessing system, they can be executed simultaneously. In this experiment, we exploited an 8-Core machine in order to speedup the Conjugate Gradient method for the harmonic parameterization problem. In this case, the speedup scales almost perfectly with the number of processors.

[Movie]

The Multigrid method (MG) exploits the fact that a problem can be represented on different scales of resolution. Many iterative methods kill the hight frequencies of the error very quickly but they fail to converge when this error is smooth. For this reason, they are called smoothers. A well known smoother for MG is the Gauss-Seidel Method. By restricting the error to a coarser resolution of the problem, its low frequencies are accentuated; we can compute the error in the coarser resolution, prolong it to the fine resolution and finally correct the initial approximation. By using another MG to solve the residual equation in the coarser level, a recursive V-cycle MG is created. When a sufficiently coarse level is reached, the residual equation is solved by using a direct solver and the error is propagated back to the finest resolution. In this experiment, we implemented a MG for finite element simulation of deformable bodies based on hexahedral cells and we exploited multiprocessing programming to speedup the solver.

[Movie]

The Finite Element Method (FEM) can be used to solve the governing partial differential equations for the simulation of deformable bodies. Often, the elastic forces are linearized in order to simplify the computation: with this strategy, the Lagrangian Equation of Motion reduces to solve a linear system each time step. However, under large rotations, linearized forces introduce unrealistic behaviors like growth in volume. In order to remove these artifacts, a method called Stiffness Warping can be used. In this experiment we show the typical artifacts introduced by the linearization of the elastic forces.

[Movie]

The goal of the National Center of Competence in Research NCCR (Computational Medicine) is to utilize information technology for improved health care. A key part of the development of interactive methods for generalized surgery simulation and training is the cutting and re-meshing of the surface of the deformable models, represented by triangle meshes. To make this robust and versatile, a tessellated splitting surface (defined by the movement of a knife) is trimmed against the model surface (and vice-versa). In a next step, the two trimmed surfaces are stitched together to create a new closed model surface. The goal of this project was to implement robust trimming and stitching of the splitting. A delicate part of these algorithms was to rebuilt the half-edge data structure for the new surfaces.

[Movie]