Shape-Specific Functions

Jump to navigation Jump to search

When invoking a topology map to map from points to cells, you have access to an identifier that tells you the cell shape. But currently there are no facilities that do anything particular to that cell shape (such as interpolate). At the moment this is all left to the user, and the only real way to do that is to implement a big switch statement.

In VTK you typically can get a vtkCell object to represent the shape and state of a cell. This object has several subclasses with virtual methods that implement a variety of useful operations. Such an implementation is not practical for the VTK-m execution environment, but we should have something equivalent.

Minor Change to CellType.h

The current list of enumerations in CellType.h is ripped from VTK, which is good because they match. Although, they are symbols in the vtkm namespace, they are named like macros (or something in the global namespace). I've also come to like the term "shape" over "type" as it is more descriptive. Thus I would like the names in the definition to change to something like the following.

namespace vtkm {

/// CellShapeIdEnum stores the type of each cell.  Currently these are designed
/// to match up with VTK cell types.
enum CellShapeIdEnum
  // Linear cells
  CELL_SHAPE_EMPTY              = 0,
  CELL_SHAPE_VERTEX             = 1,
  CELL_SHAPE_LINE               = 3,
  //CELL_SHAPE_POLY_LINE        = 4,
  CELL_SHAPE_TRIANGLE           = 5,
  CELL_SHAPE_POLYGON            = 7,
  CELL_SHAPE_PIXEL              = 8,
  CELL_SHAPE_QUAD               = 9,
  CELL_SHAPE_TETRA              = 10,
  CELL_SHAPE_VOXEL              = 11,
  CELL_SHAPE_WEDGE              = 13,
  CELL_SHAPE_PYRAMID            = 14,


} // namespace vtkm

Cell Shape Tags

The problem with a cell class is that you have to build some state when you construct it so that it is self contained, but much of that work may not actually be needed.

A more efficient approach (and one that works better on accelerator devices) is to define a tag for the cell shape and then overload functions or specialize classes on that shape tag. Of course, you still need integer identifiers for shape so that they can be stored in arrays or otherwise defined when the shape is not known at compile time. Thus, both need to exist and there needs to be a mechanism to go between them.

The first step is to establish a set of cell shape tag classes. Each one should have a field named CellShapeId set to the corresponding ID. So, for example, the implementation for CellShapeTagHexahedron could look like this.

struct CellShapeTagHexahedron {
  static const vtkm::IdComponent CellShapeId = vtkm::CELL_SHAPE_HEXAHEDRON;

There should also be a VTKM_IS_CELL_SHAPE_TAG macro that does a compile-time check that a class is a valid cell shape tag.

Since the tag has the ID built into it, going from tags to IDs is straightforward. To go the other way, there needs to be a traits-like class named something like CellShapeIdToTag to get a tag from an ID known at compile time.

template<vtkm::IdComponent CellShapeId>
struct CellShapeIdToTag;

struct CellShapeIdToTag<vtkm::CELL_SHAPE_HEXAHEDRON> {
  typedef vtkm::CellShapeTagHexahedron Tag;

Generic Cell Shape Tags

The problem with tags is that their type must be known at compile time, which is often not the case for us. To resolve this issue, there needs to be a special generic tag with an ID set at run time.

struct CellShapeTagGeneric {
  CellShapeTagGeneric(vtkm::IdComponent shapeId) : CellShapeId(shapeId) {  }

  const vtkm::IdComponent CellShapeId;

At some point when we get a CellShapeTagGeneric or a cell shape ID in a variable in any other form, we at some point need to be able to branch on the shape and execute the appropriate function. We can do this using a mechanism similar to VTK's vtkTemplateMacro. We could probably call it vtkmGenericCellShapeMacro. It would be defined something like this:

#define vtkmGenericCellShapeMacroCase(cellShapeId, call) \
  case cellShapeId: \
    { \
      typedef typename CellShapeIdToTag<cellShapeId>::Tag CellShapeTag; \
      call; \
    } \
#define vtkmGenericCellShapeMacro(call, worklet) \
  vtkmGenericCellShapeMacroCase(CELL_SHAPE_EMPTY, call); \
  vtkmGenericCellShapeMacroCase(CELL_SHAPE_VERTEX, call); \
  ... \
  default: worklet.RaiseError("Encountered unknown cell shape."); break

This macro can be used to provide a generic shape overload in the middle of a function or method implementation that specializes on cell shape.

void MyCellOperation(vtkm::CellShapeTagEmpty,
                     const vtkm::exec::FunctorBase &worklet)

void MyCellOperation(vtkm::CellShapeTagVoxel,
                     const vtkm::exec::FunctorBase &worklet)


template<typename WorkletType>
void MyCellOperation(vtkm::CellShapeTagGeneric cellShape,
                     const vtkm::exec::FunctorBase &worklet)
      MyCellOperation(CellShapeTag(), worklet)

Pixels and Voxels

2 special cell shapes are pixels and voxels. These shapes are essentially the same as quads and hexahedrons. The only differences (from what I can tell from VTK) are:

  • Pixels and voxels are axis aligned. The always come from regular grids (images) or rectilinear grids. Curvilinear grids (structured) are actually quads/hexahedra even though the topology is still on a grid because they are not (necessarily) axis aligned.
  • Pixels and voxels have a different node ordering than quads and hexahedra, respectively. I believe the pixel and voxel ordering is designed such that the bits correspond to ijk index offsets.

There is a problem with these two shapes in that it is not really possible for the cell set alone to determine whether cells are voxels vs. hexahedra because this determination depends on the coordinate system. I propose getting rid of the pixel and voxel cell shapes altogether for the following reasons.

  • As stated, there is no way for the structured CellSet/Connectivity class to determine which class it should return.
  • I have always felt the alternate ordering is more trouble than it is worth. I don't think I have ever seen the pixel/voxel ordering used cleverly, but I have certainly seen plenty of bugs when coders did not realize they had to deal with a special case.
  • Any operation that works on a hexahedra should automatically work on a voxel. (Likewise for quads and pixels.) When you have distinct cell shapes, it adds an extra layer of coding to make work.

There are still several operations that can be resolved much faster when it is known the cell is axis aligned (for example world to point coordinates). This is best managed by specializing on the class holding the point coordinates.

SAND 2015-6548 O