Polyhedral cells: storing faces as vtkCellArray

Development
1

When storing face information for polyhedral cells, vtkUnstructuredGrid uses a vtkIdTypeArray in a special format that looks awfully similar to how vtkCellArray used maintain its internal storage. I wonder if it should simply be changed to using vtkCellArray instead. That allows us to use a non-interleaved storage for faces. Together with using a vtkCellArray for FaceLocations the one-2-many relationship can be easily preserved without resorting to custom layout used by the Faces array.

So here’s the proposed structure:

  • Connectivity (vtkCellArray): simply stores point ids for all points for each polyhedral element
  • Faces (vtkCellArray): each element defines a face. The indices per element directly refer to point ids.
  • FaceLocations (vtkCellArray): each element identifies a polyhedral cell. The indices per element reference face defined in the Face array.

Contrast this with how this information is currently stored:

  • Connectivity (vtkCellArray): simply stores point ids for all points for each polyhedral element (same as in the new proposal)
  • Faces (vtkIdTypeArray): an interlaved array of the form (numCellFaces, numFace0Pts, id1, id2, id3, numFace1Pts,id1, id2, id3, ...)
  • FaceLocations (vtkIdTypeArray): offset array into Faces array indicating where the faces for a corresponding cell are stored

Thoughts?

1 Like
2

This makes a lot of sense for the internals and don’t think it would affect downstream users.
Since you are considering opening it up, it could be potentially useful to accept a vtkCellArray directly. Eg,

vtkNew<vtkCellArray> polyFaces;
polyFaces->InsertNextCell( ... ); // face0
polyFaces->InsertNextCell( ... ); // faceN

grid->InsertNextPoly(polyFaces);

For assembling the poly faces, it would actually be useful to have some exposure to low-level methods in vtkCellArray when constructing them.
Would ideally like this type of usage

3

+1 a cleaner design that takes advantage of the relatively recent changes to vtkCellArray. I assume that you will be using vtkIdType - I suppose it would be too much trouble to support 32-bit and 64-bit storage types.

4

Indeed. The vtkCellArray for Faces/FaceLocations will be directly settable / accessible etc.

If I understand correctly, vtkCellArray will take care of this, right? We won’t have to worry about fixing to a fixed width – it could default the same way as Connectivity – but one can easily build on to use 32 or 64 bit ids.

5

If we want to be able to have this design pattern, we also need to consider moving the meta data of high order cells from vtkFieldData to vtkCellArray as well. Currently, for Bezier cells, the order is accessed through vtkPointData::GetRationalWeights, the the order of high order cells through vtkCellData::GetHigherOrderDegrees.

If we don’t move those as well, you cannot infer the whole geometry from a single vtkCellArray on such cells.

The internal Types array in vtkUnstructuredGrid will also need to be moved to vtkCellArray to have a full description of the geometry.

6

Oh I think I had in my mind the InsertNextCell being more general than what you’re talking about. It seems that we’re only talking about faces constructing polyhedrons so far. Maybe this should be renamed InsertNextFace if we implement that?

It would be nice to centralize all possible cell geometry inside vtkCellArray though, so one can infer the entire geometry from a union of a vtkPoints and a vtkCellArray.

7

I wouldn’t change anything at this point. Ideally, vtkCellArray should have been called vtkElementArray (or something more generic) and then what it stores could be context-dependent – cells, faces, whatever. Given that currently its called CellArray, InsertNextCell makes sense.

1 Like
8

Good points Yohann. Some reactions:

The internal Types array in vtkUnstructuredGrid will also need to be moved to vtkCellArray to have a full description of the geometry.

I’m not sure this is needed since we know the faces are polygons. Distinguishing from triangles, quads, and general polygons simply requires the number of points.

As far as adding metadata like “RationalWeights” to vtkCellArray let’s think this through carefully and distinguish topology from geometry. vtkCellArray is meant to embed topological information (e.g., independent of position). Point data typically is meant to embed geometric information (eg position in space)

9

After second thought, you’re right, it makes sense to keep this information at the point data level.

I suppose it is not that much of a big deal to have to carry a Types array inside vtkUnstructuredGrid, which is an essential array for 3D cells, since vtkPolyData would not need it.

In conclusion: I agree we should move vtkPolyhedron topological information inside vtkCellArray. The rest seems fine as is.

11

See a draft branch here: https://gitlab.kitware.com/vtk/vtk/-/merge_requests/9812

1 Like