Support 1D and 2D non linear cells in vtkPolyData

Development
1

Non-linear cells are natively used by simulations from the get-go, simply because p-refinement is often better than h-refinement. Higher polynomial orders yield better accuracy more quickly. While users can increase the number of linear cells to approximate curves in a mesh, curved faces and lines are not only more realistic—they also improve simulation convergence and visuals.

The current pain point is that VTK, as a scientific visualization library rather than a simple 3D viewer, often fails to faithfully render non-linear geometry. Currently, it performs fixed subdivision on the CPU. It would be far more efficient to dynamically subdivide on the GPU, allowing a quadratic face closer to the camera to have higher subdivision levels while distant faces use lower levels. This approach was demonstrated in vtkCellGrid (vtk/vtk!11009).

If vtkPolyData can store non-linear edges, triangles, quads, and polygons, we can upgrade vtkOpenGLPolyDataMapper to dynamically tessellate higher-order geometry based on its distance from the camera.

The dynamic tessellation logic used by vtkCellGrid shaders (see source) follows this pattern:

// 1. Transform each vertex into eye space
vec4 eyeSpacePos0 = MCVCMatrix * gl_in[0].gl_Position;
vec4 eyeSpacePos1 = MCVCMatrix * gl_in[1].gl_Position;

// 2. Scale "distance" from camera between 0 and 1
float distance0 = clamp((abs(eyeSpacePos0.z)) / (max_distance), 0.0f, 1.0f);
float distance1 = clamp((abs(eyeSpacePos1.z)) / (max_distance), 0.0f, 1.0f);

// 3. Interpolate edge tessellation level based on the closer vertex
float tessLevel0 = mix(max_tl, min_tl, min(distance1, distance0));

// 4. Set the corresponding outer edge tessellation levels
gl_TessLevelOuter[0] = 1;
gl_TessLevelOuter[1] = tessLevel0;

I see three potential paths forward:

  1. Handle it in the rendering layer: This involves writing a new set of mappers to draw 1D and 2D non-linear geometry from a vtkUnstructuredGrid. However, handling composite datasets with mixed PolyData and UnstructuredGrid becomes complicated.
  2. Pragmatic: Extend vtkPolyData with 4 additional vtkCellArray instances and update the polydata mapper to support them.
    vtkPolyData:
  - Verts
  - Lines
  - Polys
  - Strips
  - NonLinearLines (new)
  - NonLinearTris (new)
  - NonLinearQuads (new)
  - NonLinearPolys (new)
  3. Long term better: Reparent vtkPolyData to vtkUnstructuredGrid. This would grant the polydata mappers access to non-linear edges and faces. We would need to enforce cell insertion order (verts, lines, polys, strips, etc.) and strictly block 3D cells in vtkPolyData. If implemented correctly, this maintains backward compatibility while potentially reducing duplicate filters within VTK.

Since option 3 is a significant architectural change, i want to list the pros and cons of that:

Pros

  • It eliminates the style of development where filters must be written once for vtkPolyData and again for vtkUnstructuredGrid.
  • Since vtkUnstructuredGrid already supports non-linear cells (quadratic edges, tri6, quad8, etc.), vtkPolyData would inherit this capability “for free” at the data structure level.
  • Many filters like vtkClipDataSet and vtkThreshold have specialized PolyData versions. Merging the hierarchy could allow for a single, optimized implementation.
  • Users wouldn’t need to constantly use vtkGeometryFilter just to convert an unstructured surface mesh into a format the mapper accepts.

Cons & Risks

  • vtkPolyData is highly optimized for 2D topologies because it stores the cell connectivity arrays separately. vtkUnstructuredGrid will have a heavier memory footprint because it clumps all cells into one vtkCellArray. vtkCompositeArray will be the way to go if we want to keep those benefits.
  • Backward Compatibility: This is a nuclear option. Any external plugin or wrapped code that expects vtkPolyData to be a direct child ofvtkPointSet will break.
  • By definition, vtkPolyData should not contain 3D cells (tetrahedrons, hexes). Reparenting would require strict API “shimming” to throw errors or warnings if a user tries to insert a 3D cell.

Option 1 vs Option 2 vs. Option 3

Feature Option 1 (new mappers) Option 2 (Extend PolyData) Option 3 (Reparent)
Implementation Effort atrociously high moderate high
Risk of Breaking API low low high
Filter Compatibility — Requires updating filters Native support

If you want to add anything, please comment.

2

Thanks Jaswant for the detailed description. While there is a ton to talk about, one pressing question needs to be asked.

Who / what customer is going to pay for this? (this especially pertains to #3). VTK is full of partially implemented design patterns, we start with good intentions and the run out of $ or people and never finish. I’m worried that #3, to do it right, would not be completed and we’d be left with another partial implementation.

And I can’t see using VTK maintenance money. Just guessing, this is likely a large effort requiring support for 2-3 people for six months to a year. Maybe more if you count rewriting documentation, web pages, examples, and tests. Not to mention dealing with confused customers and external developers.

Also, as someone has mentioned, the importance of this capability, and the value it brings, should be considered before we make huge changes for modest benefits. We don’t want to be in a situation where the tail wags the dog.

3

The motivator is https://gitlab.kitware.com/paraview/paraview/-/work_items/17597 which was opened by LANL. I share similar concerns about the reparenting approach. Highly probable that will be in a perpetually WIP stage.

4

#2 is definitely the approach I favor. One question about it, though. The Verts, Lines, Polys, and Strips are separate cell arrays because presumably at one point in time (maybe it’s still the case) transferring those cells to the GPU as a group was/is faster than if they were all lumped into a single cell array. Is that going to be the case for the non-linear cell types, hence the 4 NonLinear* cell arrays you propose adding? Or could all nonlinear cells be lumped into one cell array? The separate cell arrays for different dimensionality cells in vtkPolyData has always been a little annoying to me, so if we could avoid propagating that to the nonlinear cell support, that could be nice.

5

i expect using different shader programs per non-linear cell type, so it would be easier if they were separate index buffer objects.

6

#3 is definitively too risky imo especially if we may lack funding to finished it properly, consumers of VTK such as ParaViw or Slicer (@lassoan) will not be happy if we start modifying vtkPolyData and let it in an unfinished state.

Regarding solution #1 and #2, AFAIU, your initial problem is “how can we render non linear cell in VTK ?”, right ?

I’m personally skeptical about resolving a rendering issue by modifying the data model itself. We already have vtkUnstructuredGrid and (maybe?) vtkCellGrid could cover it so creating a dedicated mapper to resolve it could be possible. From what you wrote, it will be difficult to do that and yes the refacto would be complex but not impossible. I’m also worry that if we start adding new cell types in the vtkPolyData we may add more and more cells type in the future.

1 Like