Combinatorial data structures for volume rendering unstructured grids

Guillaume Caumon and Bruno Levy and Jean-Claude Paul. ( 2003 )
INRIA

Abstract

We propose a hierarchy of algorithms and data structures for visualizing grids with various topologies. Our generic slicing-based rendering algorithm has a smaller complexity than previous approaches. The use of combinatorial information indeed confers an optimal complexity on the algorithm, which is linear with the size of the slices. The rendering method is able to process arbitrary meshes and does not require the preliminary tetrahedralization of the grid. Using the combinatorial information of the grid makes it possible to update quickly the data structure when the scalar field is modified. This generic method is applied to different types of grids. A first specialization for strongly unstructured grids, as used in recent partial differential equation schemes for Computational Fluid Dynamics (CFD), comes as an optimized version of our previous work on circular incident edges lists. Another instantiation of the method, that we call Cellular graphs, is applied to weakly heterogeneous grids. A structured version of cellular graphs is also declined to deal with curvilinear grids. For each of these applications, the data structure, the construction algorithm, and customizations to the generic rendering algorithm are thoroughly described.

Download / Links

    BibTeX Reference

    @TECHREPORT{Caumon03TVCG,
        author = { Caumon, Guillaume and Levy, Bruno and Paul, Jean-Claude },
         title = { Combinatorial data structures for volume rendering unstructured grids },
       chapter = { 0 },
          year = { 2003 },
    institution = { INRIA },
      abstract = { We propose a hierarchy of algorithms and data structures
    for visualizing grids with various topologies. Our generic
    slicing-based rendering algorithm has a smaller complexity than
    previous approaches. The use of combinatorial information indeed
    confers an optimal complexity on the algorithm, which is linear
    with the size of the slices. The rendering method is able to process
    arbitrary meshes and does not require the preliminary tetrahedralization
    of the grid. Using the combinatorial information of the
    grid makes it possible to update quickly the data structure when
    the scalar field is modified.
    This generic method is applied to different types of grids. A
    first specialization for strongly unstructured grids, as used in recent
    partial differential equation schemes for Computational Fluid
    Dynamics (CFD), comes as an optimized version of our previous
    work on circular incident edges lists. Another instantiation of the
    method, that we call Cellular graphs, is applied to weakly heterogeneous
    grids. A structured version of cellular graphs is also declined
    to deal with curvilinear grids. For each of these applications, the
    data structure, the construction algorithm, and customizations to
    the generic rendering algorithm are thoroughly described. }
    }