VTK/Polyhedron Support

Overview

This work extends VTK to support polyhedron cells. This new cell type can be applied to computational fluid dynamics (CFD) and other similar applications. The work consists of two parts:

1. Support of the new polyhedron cell type including: (1) a new cell class called vtkPolyhedron that implements common APIs of vtkCell3D, (2) extended vtkUnstructuredGrid for storing and accessing this new cell type, and (3) modified vtkXMLUnstructuredGridReader/Writer for I/O of polyhedron meshes.
2. Implementation of mean value coordinates (MVC) interpolation method as a filter called vtkMeanValueCoordinateInterpolator. This filter is used in vtkPolyhedron as well as in vtkProbePolyhedron for smoothly interpolating/extrapolating point attributes (scalars, vectors, etc.) at a given point interior, exterior or on the surface of polyhedron cells.

Polyhedron Cell Support

A new 3D cell class vtkPolyhedron

vtkPolyhedron represents a 3D polyhedron cell defined by a set of polygon faces. Both convex and concave polyhedrons are supported. However the polyhedrons need to be watertight, non-self-intersecting and manifold (each edge is used exactly twice), and the face polygons needs to be planar. vtkPolyhedron is implemented as a subclass of vtkCell3D. All common API functions of vtkCell3D are implemented. A few critical functions are described briefly as follows.

• InterpolateFunctions, EvaluateLocation and EvaluatePosition: these three functions use vtkMeanValueCoordinateInterpolator to compute the interpolation weights of vertices of a polyhedron cell at any given point position. Note that the point can be interior, exterior or on the surface of the polyhedron cell.

• Triangulate: this function uses vtkOrderedTriangulator to tetrahedralize a polyhedron cell.

• IsInside: this function determines whether a point is inside the polyhedron by shooting rays in multiple random directions then counting the number of intersections with cell faces.

• Contour: this function computes the intersection between a contouring function and a polyhedron and outputs a polygonal contour. When the result contour is non-planar, it will be triangulated then outputs as a triangular mesh.

• Clip: this function clips the input polyhedron and outputs a new polyhedron. A clipping result is shown in Fig. 1.

Fig.1 Clipping a polyhedron mesh.

Polyhedron cells as face streams in vtkUnstructuredGrid

Similar to other 3D cells of VTK such as vtkTetra and vtkHexahedron, vtkPolyhedrons--defined as VTK_POLYHEDRON type in vtkCellTypes.h--are stored as cell elements in vtkUnstructuredGrid. However, previous 3D cells are regular ones whose geometries are fully determined by a set of vertex points with predefined implicit ordering. Unfortunately, such an implicit ordering does not exist in polyhedron cells, the connectivities between polyhedron vertices need to be explicitly defined. The extended vtkUnstructuredGrid stores polyhedron cells as face streams of the following format: [numberOfCellFaces, (numberOfPointsOfFace0, pointId0, pointId1, … ), (numberOfPointsOfFace1, pointId0, pointId1, …), … ].

To insert a polyhedron cell into an unstructured grid, the user can use InsertNextCell with a new set of parameter (see below). Where cellType is the type of cell (VTK_POLYHEDRON), nPoints is the number of unique points in the cell, PointIds is the list of the unique cell point Ids, nFaces is the number of faces in the cell, and faces is the face stream defined above but without the numberOfCellFaces element [(numberOfPointsOfFace0, pointId0, pointId1, … ),(numberOfPointsOfFace1, pointId0, pointId1, …),… ]. For instance, a cube has 8 unique points but each point Id will be repeated three times (in three adjacent faces) in the face stream.

     vtkIdType InsertNextCell(int cellType, vtkIdType nPoints, vtkIdType *pointIds, vtkIdType nFaces,   vtkIdType*faceStream)

The user can also insert polyhedron cells using InsertNextCell with the old parameter types. But note that the parameters need to be provided in a different format than regular cells. Here faceStream is the face stream without the numberOfCellFaces element, and faceStream1 is the complete face-stream.

     vtkIdType InsertNextCell(int cellType, vtkIdType nFaces, vtkIdType *faceStream)  

     vtkIdType InsertNextCell(int cellType, vtkIdList *faceStream1)

To get a polyhedron cell from vtkUnstructuredGrid, the user can use

     void GetFaceStream(vtkIdType cellId, vtkIdType& nFaces, vtkIdType* &faceStream)

     void GetFaceStream(vtkIdType cellId, vtkIdList *faceStream1)

IO of polyhedron cells through vtkXMLUnstructuredGridReader/Writer

Meshes containing polyhedron cells can be read from and write into a XML (.vtm) file using vtkXMLUnstructuredGridReader/Writer. To represent the vertex connectivity of polyhedron cells, we added two additional XML sub-fields to the cells field.

The original cells field consists of three sub-fields: (1) connectivity—an array storing the point Ids of the unique points of all cells, (2) offsets—an array indicating the end position (1-indexed) of each cell in the connectivity array, and (3) types—an array storing the types of each cell.

The new sub-fields are (1) faces—an array storing the face streams of all the cells and (2) faceoffsets —an array indicating the end position (1-indexed) of each cell in the faces array. Each cell in the faces array is represented using the face stream described earlier (with numberOfCellFaces).

These new sub-fields are optional. When a mesh does not contain any polyhedron cell, the new sub-fields will not be included in the XML (.vtm) file.

3D Mean Value Coordinates Interpolation

3D mean value coordinates (MVC) interpolation is an elegant yet efficient method for smoothly interpolating closed manifold polyhedrons. Given an input polyhedron with vertices vi (i=1,…,n) and a interpolation point x, the MVC interpolation weights of the vertices wi satisfy the following four preferred properties. (Strictly speaking, positivity property is only valid for convex polyhedrons, the other three properties are valid for both convex and concave polyhedrons). The interpolation/extrapolation point x can be interior, exterior or on the boundary of the input polyhedrons.

• Affine invariance: • Linear reproduction: • Positivity: • Smoothness: at least C1 continuous. vtkMeanValueCoordinatesInterpolator filter implements two specific MVC algorithms. The first one is specialized/optimized for tetrahedral meshes [1]. The second one is for general polyhedron meshes [2]. The filter will detect whether the input mesh is tetrahedralized then automatically choose the right algorithm. Details about the two algorithms can be found in the referenced papers. A result of interpolating/extrapolating a hemisphere polyhedron mesh onto a planar mesh is presented in Fig. 2.

Fig. 2. MVC interpolation. Vertex colors are defined on the hemisphere (input polyhedron mesh) and are interpolated/extrapolated onto a planar mesh passing through the bottom of the hemisphere. The left and right images respectively show the interpolation result viewed from both sides of the planar mesh.

References: [1] Tao Ju, Scott Schaefer, and Joe Warrent, "Mean Value Coordinates for Closed Triangular Meshes", ACM SIGGRAPH 2005.

[2] Torsten Langer, Alexander Belyaev, and Hans-Peter Seidel, "Spherical Barycentric Coordinates", Eurographics Symposium on Geometry Processing (2006).

Goals:

1. Add support for arbitrary polyhedral cell (manifold, watertight, may be concave)
2. Develop smooth interpolation functions for polyhedron
3. Create filters, examples and testing infrastructure supporting this technology
4. Application goal: support CFD solvers (finite volume methods for computational fluid dynamics and similar)

Summary of Implementation Plan:

• Identify interpolation functions
  • Mean Value Coordinates
  • Triangle meshes (paper by Tao Ju et al.)
  • Arbitrary polyhedron (paper by Torsten Langer et al.)
• Polyhedron cell support
  • vtkPolyhedron - more complex cell in that it requires explicit face representation
  • vtkUnstructuredGrid - modified to support polyhedron cell, new InsertNextCell() and related methods (e.g., GetFace()).
  • vtkGenericCell (and vtkUnstructuredGrid::GetCell() methods) expanded to include vtkPolyhedron
  • vtkCellTypes.h has new #define VTK_POLYHEDRON
• Implement cool related interpolation functions & filters (note items in green are complete)
  • vtkMeanValueCoordinatesInterpolator
  • vtkProbePolyhedron - probe the region (interior, surface, exterior) around a polyhedral mesh for data values.
  • vtkDeformPointSet - use MVC to deform any vtkPointSet using control mesh
  • vtkExtractPolyhedralMesh - for debugging, convert 3D cells to vtkPolyhedron
  • Would like to implement some VTK widgets to manipulate meshes
    • vtkPancakeWidget (local surface deformation)
    • vtkControlMeshWidget (for global deformation of geometry)

Implementation Issues:

• VTK File formats and IO
  • XML formats
  • Legacy formats
• Critical filters /functionality
  • Geometry Filter - should work once vtkCell::GetCellNeighbors() is implemented
  • Contouring - some work required
  • Clipping - serious work required
  • Search (vtkDataSet::FindCell() and FindPoint()) - should work once evaluation functions are implemented
• Impact on previous code
  • Previous vtkClipDataSet can now produce polyhedron as output, is this desirable?

Auxiliary Tasks

• vtkPolygon basis functions: replace silly 1/r^2 with the MVC 2D equivalent

Schedule

• Working on core functionality which should be done by mid 2010. Completion of all work depends on funding, schedule and customer support.
  • Basics- polygon2d, data API and integration, Mesh2Polyhedra filter, Evaluate/Location/Position functions() in vtkPolyhedron, GetCellNeighbors(), GetFace(), GetFaceIds() (Early March)
  • Core- geometry filter, IO (mid-March)
  • Algorithms- (clipping, contouring) (early to mid April)
  • Final tuning (mid to late April)

Contacts:

• Will Schroeder (will.schroeder at kitware.com)
• Hua Yang (hua.yang at kitware.com)