Polyhedron face connectivity improvements

Following discussions in the VTKHDF polyhedrons thread, we would like to discuss a potential improvement to the vtkUnstructuredGrid data model that allows reusing the same faces using different orientations in different polyhedral cells.

For that, as suggested by @olesenm , we would change the FaceLocations array to handle negative values: face n is referenced as -(n+1) to signify a flipped orientation (ie points are taken in the reverse order). This way, 2 adjacent polyhedrons sharing a face will only have to define this face once, and use the flipped orientation in the FaceLocations array for one of these polygons to get correct normal vectors. This saves on both storage space when written to disk, and in memory.

Impact

The required changes are mostly internal to vtkUnstructuredGrid. For instance, face streams will be unchanged. GetPolyhedronFaceLocations will be renamed to GetOrientedPolyhedronFaceLocations that returns a cell array, referencing positive or negative face ids as points, depending on their orientation. GetPolyhedronFaceLocations will be deprecated and will implement a compatibility layer, that creates new faces so that every face id is positive, as it was before. All code using GetPolyhedronFaceLocations will need to adapt to the new GetOrientedPolyhedronFaceLocationswhich will require new code to handle the negative face ids. It should be mostly transparent for readers/writers that simply copy the array from/to disk.

3 Likes

@ahernsean

Nice!

In some code ideas that will be related to this: I’ve also been looking at how to handle topological point merging (within the openfoam export code) since ghost points/cells don’t really seem tractable for non-trivial geometries. This looks to combine fairly well with the rest of the handling – I’m using hyperslabs when writing the VTKHDF, so the resulting file appears as if it was written in serial, irrespective of how many ranks were actually used.

Even when using the proposed oriented faces to cut down on the bookkeeping, it would be necessary that they continue to also support specifying duplicate faces as before. I’d assume that would be the case, but just wanted to make certain that that also remains in the spec. My use case would be to have positive/negative face addressing for everything within a processor rank, but still allow duplicated faces so that we don’t have to do any weird face flipping on processor-processor boundaries (the topological point merge happens at a later stage).

This is a great thread, it would be good to get these improvements in especially with Voronoi meshing coming on line.

Please make sure Jeff Lee is involved - maybe he is already but I CCd him just in case.

@ahernsean this could be of interest to somebody in your team.

Here’s a bit of my perspective on this discussion, especially since it grew out of the earlier vtkHDF thread on supporting polyhedron cells.

The original thread was primarily about on-disk representation: how to store polyhedron topology efficiently using shared faces, flat connectivity, and offsets. Those choices make a lot of sense for I/O and storage, and it seems reasonable for a reader to pay a one-time cost to rehydrate or normalize that data into whatever in-memory form we choose. In that sense, vtkHDF layout decisions feel largely orthogonal to the in-memory data model, which is probably why a new thread.

The current discussion is really about the in-memory representation in vtkUnstructuredGrid. Today that model is cell-centric: each polyhedron describes its faces inline, with orientation implied by point order. It’s simple, self-contained, and works well with existing filters, but it does duplicate shared faces and requires some reconstruction of face identity downstream by algorithms that require it.

From prior experience, a face-centric model is certainly possible. There, faces are first-class entities with explicit cell adjacency (f→C0, f→C1), and orientation is resolved implicitly based on ownership. That can simplify algorithms that explicitly traverse faces, but it also represents a more significant shift in how meshes are authored and reasoned about.

The proposed approach here (shared faces with signed orientation) feels like a reasonable middle ground from a storage perspective. Most of the complexity around face orientation and traversal can likely be contained within vtkPolyhedron and its helpers. Algorithms like Contour, Clip, IsInside, CellVolume, and ParametricCenter are already encapsulated there, and I’m not aware of any direct access of faces of a vtkUnstructuredGrid.

Where this is harder to hide is on the writing side. Users who construct or modify vtkUnstructuredGrid programmatically necessarily have to provide connectivity. Today that work is entirely local to a cell. Introducing shared faces and signed orientation risks pushing some notion of global face identity, canonical ordering, or cross-cell consistency onto writers, which represents a real change in the authoring model.

Many solvers do have explicit face topology; the issue here is that VTK is cell-centric and doesn’t treat faces as first-class. In parallel export (e.g. hyperslabs), writers emit locally valid topology and defer global reconciliation, so allowing apparent “duplicate faces” is really about avoiding forced cross-rank face coordination at write time.

There may also be performance implications to “shared” faces. Making face orientation explicit can reduce repeated inference in face-heavy algorithms, but if most filters remain cell-driven, a richer in-memory model may not show a clear performance win on its own. Likewise, it’s not obvious that an in-memory change alone enables materially larger problem sizes unless it significantly reduces working-set size or unlocks new traversal patterns.

For those reasons, I’d personally be cautious about changing the in-memory representation unless there’s a clear upside: either demonstrated performance benefits for existing or planned algorithms, or a concrete ability to accommodate significantly larger datasets. vtkHDF already gives us flexibility to optimize storage independently, so the bar for in-memory changes probably needs to be higher.

Rather than committing to an in-memory change up front, it might be useful to make the next steps more concrete: identify which existing filters would actually benefit from explicit face orientation or sharing, and whether that translates into measurable performance or memory wins. It would also help to be explicit about the full impact surface, algorithms and writers and also readers, since any in-memory change necessarily affects how data is materialized. Given that, a reasonable next step may be to prototype or benchmark specific use cases and workflows, to better understand where the complexity pays off before committing to a broader shift. I’m happy to help think through concrete examples or evaluation paths if that’s useful.

1 Like