Algorithmes sur GPU de visualisation et de calcul pour des maillages non-structurés

Luc Buatois. ( 2008 )
INPL

Abstract

Most recent algorithms for Geometry Processing or Computational Fluid Dynamics (CFD) are using new types of grids made of arbitrary polyhedra, in other words strongly unstructured grids. In case of CFD simulations, these grids can be mapped with scalar or vector fields representing physical properties (for example : density, porosity, permeability). This thesis proposes new tools for visualization and computation on strongly unstructured grids. Visualization of such grids that have variable geometry and topology, poses the problem of how to store data and how algorithms could handle such variability. Doing computations on such grids poses the problem of solving large sparse unstructured linear systems. The ever-growing parallel power of GPUs makes them more and more valuable for handling theses tasks. However, using GPUs calls for defining new algorithms highly adapted to their specific programming model. Our contributions are : (1) An efficient generic visualization method that uses GPU’s power to ac- celerate isosurface extraction for large unstructured grids. (2) An adaptative cell classification method that accelerates isosurface extraction by pre-selecting only intersected cells. (3) An efficient algorithm for temporal interpolation of isosurfaces. This algrithm helps to visualize in a continuous maner the evolution of isosurfaces through time. (4) A massively parallel algorithm for solving large sparse unstructured linear systems on the GPU. Its originality comes from its adaptation to sparse matrices with random pattern, which enables to solve any sparse linear system, thus the ones that come from strongly unstructured grids.

Download / Links

BibTeX Reference

@PHDTHESIS{,
    author = { Buatois, Luc },
     title = { Algorithmes sur GPU de visualisation et de calcul pour des maillages non-structurés },
      year = { 2008 },
    school = { INPL },
  abstract = { Most recent algorithms for Geometry Processing or Computational Fluid Dynamics (CFD) are
using new types of grids made of arbitrary polyhedra, in other words strongly unstructured grids. In
case of CFD simulations, these grids can be mapped with scalar or vector fields representing physical
properties (for example : density, porosity, permeability).
This thesis proposes new tools for visualization and computation on strongly unstructured grids.
Visualization of such grids that have variable geometry and topology, poses the problem of how to store
data and how algorithms could handle such variability. Doing computations on such grids poses the
problem of solving large sparse unstructured linear systems. The ever-growing parallel power of GPUs
makes them more and more valuable for handling theses tasks. However, using GPUs calls for defining
new algorithms highly adapted to their specific programming model.
Our contributions are : (1) An efficient generic visualization method that uses GPU’s power to ac-
celerate isosurface extraction for large unstructured grids. (2) An adaptative cell classification method
that accelerates isosurface extraction by pre-selecting only intersected cells. (3) An efficient algorithm for
temporal interpolation of isosurfaces. This algrithm helps to visualize in a continuous maner the evolution
of isosurfaces through time. (4) A massively parallel algorithm for solving large sparse unstructured linear
systems on the GPU. Its originality comes from its adaptation to sparse matrices with random pattern,
which enables to solve any sparse linear system, thus the ones that come from strongly unstructured
grids. }
}