Planning for iMesh to support structured grid and AMR

There are two problems of course supporting structured grid with iMesh. First, the interface itself, specification and data model require adjustments to accomodate it. In addition, we need implementations that support it. This document does not address the latter issue. It addresses only the issue of enabling the iMesh interface itself to support structured grid. Depending on how we tackle it, it won't necessarily be pretty, but I believe it can be made to work sufficiently. The purpose is to position iMesh for adoption by structured grid and/or AMR applications and tools.

The biggest difference between structured grid and unstructured grid has to do with regularity of relationships between entities (e.g. adjacencies). That means that explicit storage of those relationships is not necessary (or desired as it sort of defeats a large part of the purpose in using structured grids). Nonetheless, early on in the development of structrued grid support, its concievable that the implementation will wind up resorting to an unstructured mode of storage underneath the API. Note, that a structured grid does not necessarily imply topological square entities. You can have structured grid with triangles and hexagons too, easily.

Another key difference is that interaction with entites via one at a time methods is less applicable to structured grid. Structured grid is more likely to use array-based interaction with iMesh and/or iterator based. Nonetheless, all of the iMesh functions that create entities must be considered.

The storage for the coordinate field in iMesh is yet another potential problem. Currently, iMesh stores 2 or 3 values per vertex for 2 or 3D meshes. However, neither rectilinear nor uniform grids require this and doing so represents a large additional storage burden structured grided tools and applications are unlikely to accept.

We don't necessarily need design things such that a single iMesh instance is either wholly unstructured or wholly structured. We could design things in such a way that certain collections of entities form structured collections (probably via entity sets).

Some rough thoughts on a few design strategies are outlined below. Everyone is encouraged to comment and change content here as appropriate but hopefully all with the goal in mind of giving this activity a serious degree of consideration.

Minimalist design strategy

In this design strategy, we try as little as possible to not change any of the existing functions in iMesh and instead focus on ways of introducing altered usage semantics for structured grid. Th rationale for this approach is that if it can be made to work, the a lot of the data modeling and API specification issues don't need to be revisted in great detail. In addition, its concievable a lot of functions that work on any ole entity will not require adjustments to support structured grid.

Vertex and Entity Creation for structured grid

First, consider methods for creating vertex entities...

iMesh_createVtx(
    iMesh_Instance instance,
    double x, double y, double z,
    iBase_EntityHandle *ent,
    int *err);

iMesh_createVtxArr(
    iMesh_Instane instance,
    int num_verts,
    int storage_order,
    const double *new_coords
    int new_coords_size,
    iBase_EntityHandle **ents,
    int *ents_alloc,
    int *ents_size,
    int *err);

The first of these functions just doesn't make much sense at all for structured grid. I can see adding (or removing) whole (topological subspaces) bunches of verts to a structured grid but not a vertex at a time. So, I think a call to iMesh_createVtx() should fail on a structured grid. But, that would imply that the implementation knew the grid is intended to be unstructured, which is probably a good thing, and requires some additional information up front at the time the instance is created either via a new iMesh_setStructuredGrid() or with options to iMesh_newMesh.

In fact, come to think of it, if a caller wants to create a structured grid in 2 or 3D, just knowing a few tiny bits of information is sufficient to infer all entities and their relationships. That information would be number of verts in each of the 2 or 3 dimensions and topological entity type which for common cases would be quad2 for 2D or hexes for 3D. However, if we want to support mesh modification on structured grid -- and I think it would be a good idea too at least try -- we in fact do need the ability to both destroy and create whole swaths of vertex entities. So, we'd still need a call like createVtxArray. So, lets proceed with work on that function...

Also, if we want to support the notion that a single iMesh instance can have both structured and unstructured collections of entities, then we'd need to handle the IJK size of the portion of mesh here in the createVtxArr call and not in some more global call such as iMesh_newMesh.

To do this, I propose we add one or more enums to 'storage_order' to support structured grid options such as

enum iBase_StorageOrder
    iBase_BLOCKED,
    iBase_INTERLEAVED,
    iBase_RECTILINEAR2D_BLOCKED,
    iBase_CURVILINEAR2D_BLOCKED,
    iBase_CURVILINEAR2D_INTERLEAVED
    iBase_RECTILINEAR3D_BLOCKED,
    iBase_CURVILINEAR3D_BLOCKED,
    iBase_CURVILINEAR3D_INTERLEAVED

For iBase_RECT/iBase_CURV variants, the data passed in the *new_coords array is interpreted differently from the current design. Ok, I freely admit that what follows might be considered hackish by some but it will work and doesn't require any API change. Depending on whether a '2D' or '3D' variant is passed as the storage_order, then the first 2 or 3 entries in new_coords will be treated as integer values representing the size in logical coordinates in each dimension -- or perhaps these could go into the last entries in the array. Then real coordinate data will follow. For rectilinear grids, the real coordinate data follows as all the values for the first dimesion, followed by all values for second, etc. There is no 'interleave' form for rectilinear grids because the different dimension's coordinate arrays can, in general, be of different size making interleave impossible. For curvilinear grids, the real coordinate data follows as normal coordinate data would and it can either be interleaved or blocked.

Ok, what does the caller get back? Certainly, an array of entity handles would be fine to return. However, for a structured grid, something that makes a little more sense is a single handle to something that acts sort of like a logically indexed array of entity handles. To handle this, we'd add to the iBase_EntityType and iBase_EntityToplogy enums to provided indexed variants of the relevant types.

  enum iBase_EntityType {
    iBase_EntityType_MIN = 0,
    iBase_VERTEX = iBase_EntityType_MIN,
    iBase_EDGE,
    iBase_FACE,
    iBase_REGION,
    iBase_ALL_TYPES,
    iBase_INDEXED_VERTEX,
    iBase_INDEXED_EDGE,
    iBase_INDEXED_FACE,
    iBase_INDEXED_REGION,
    iBase_EntityType_MAX = iBase_ALL_TYPES
  };

  enum iMesh_EntityTopology {
    iMesh_EntityTopology_MIN = 0,
    iMesh_POINT = iMesh_EntityTopology_MIN, /**< a general zero-dimensional entity  */
    iMesh_LINE_SEGMENT,       /**< a general one-dimensional entity  */
    iMesh_POLYGON,            /**< a general two-dimensional element  */
    iMesh_TRIANGLE,           /**< a three-sided, two-dimensional element  */
    iMesh_QUADRILATERAL,      /**< a four-sided, two-dimensional element  */
    iMesh_POLYHEDRON,         /**< a general three-dimensional element */
    iMesh_TETRAHEDRON,        /**< a four-sided, three-dimensional element whose
                               *     faces are triangles */
    iMesh_HEXAHEDRON,         /**< a six-sided, three-dimensional element whose
                               *     faces are quadrilaterals */
    iMesh_PRISM,              /**< a five-sided, three-dimensional element which
                               *     has three quadrilateral faces and two
                               *     triangular faces  */
    iMesh_PYRAMID,            /**< a five-sided, three-dimensional element
                               *     which has one quadrilateral face and four
                               *     triangular faces */
    iMesh_SEPTAHEDRON,        /**< a hexahedral entity with one collapsed edge */
    iMesh_ALL_TOPOLOGIES,     /**< allows the user to request information
                               *     about all the topology types */
    iMesh_INDEXED_LINE_SEGMENT,
    iMesh_INDEXED_QUADRILATERAL,
    iMesh_INDEXED_HEXAHEDRON,
    iMesh_EntityTopology_MAX = iMesh_ALL_TOPOLOGIES
  };

So, a call for iMesh_createVtxArr for a structured grid would, at least above the API, create what amounts to a single, special kind of indexed vertex entity as well as return an iBase_EntityHandle to it. A call to getEntType for a handle to this special entity would return iBase_INDEXED_VERTEX. In addition, we would add a function to the API to, given a handle to an indexed entity, return a specific vertex entity handle from its indexed variant such as...

iMesh_indexEnt(
    iMesh_Instance inst,
    /*in */ const iBase_EntityHandle indexed_ent,
    /*in */ int logI, int logJ, int logK,
    /*out*/ iBase_EntityHandle *ent,
    /*out*/ int *err)

Very likely, the existing iterator methods could be made to work with this new kind of indexed entity without any API changes.

Higher dimensional entity creation for structured grid.

For same reasons only the Arr variant of vertex creation is appropriate for structured grid, so would only the Arr variant of higher dimensional entiy creation.

  void iMesh_createEntArr(iMesh_Instance instance,
                          /*in*/ const int new_entity_topology,
                          /*in*/ const iBase_EntityHandle* lower_order_entity_handles,
                          /*in*/ const int lower_order_entity_handles_size,
                          /*inout*/ iBase_EntityHandle** new_entity_handles,
                          /*inout*/ int* new_entity_handles_allocated,
                          /*out*/ int* new_entity_handles_size,
                          /*inout*/ int** status,
                          /*inout*/ int* status_allocated,
                          /*out*/ int* status_size,
                          /*out*/ int *err);

The new_entity_topology would be one of the new indexed variants of quads or hexes, iMesh_INDEXED_QUADRILATERAL or @iMesh_INDEXED_HEXAHEDRON. However, in this case, the only kind of lower dimensional entity to construct things from that would be permited is a handle to a vertex entity of type iBase_INDEXED_VERTEX and only a single handle to such an entity would need be passed in lower_order_entity_handles array.

Use existing entity set object instead of introducing new indexed variant of entities

The above thoughts introduced a notion of an indexed entity as a sort of magic pseudo container to act as a proxy for a slew of handles to entities all related to each other via structured gridded mesh indexing schemea. An alternative to introduce a new kind of entity is to instead use iMesh's existing entity set object to serve the same purpose. Not sure how this looks though especially since coordinate data is associated and created solely in concert with vertex entities. You have to sort of have created all the vertex entities and stuck them in an entity set before you can start embuing that entity set with special properties afforded to structured grids.

What about performing modification operations that corrupt structured assumptions.

So, suppoes we've got everything working and applications can create structured gridded representations that fit nicely into iMesh. What happens if an application performs some sort of entity deletion or entity addition that winds up corrupting the structured assumptions.
  • Don't ever permit it. The offending call could fail and return some new error code, iBase_STRUCTURE_CORRUPTING
  • The call could succeed but the underlying implementation then has the right to destructure the whole indexed collection of structured entities thereby tossing out all the efficiencies the original structured grid provided.
  • It would be nice for the application to inform the implementation which of the above it would prefer happens.

Likewise, what about creating an entity that lives between an entity belonging to a indexed collection of structured entities and normal entities. Think about creating a triangle entity on the boundary of some 2D, indexed collection of structured quads where one vertex of the edge is on one of the quads and the other vertex is some other normal entity?

What about modification operations that do not corrupt structure assumptions?

For structured grid, modification involves adding and removing whole swaths entities along one of the topological subspaces of the mesh. For example, removing a whole plane of vertex entites from a 3D grid. Again, just as for vertex and higher dimensional entities, for structured grid, only the Arr variant is relevant. The existing API is...

  void iMesh_deleteEntArr(iMesh_Instance instance,
                          /*in*/ const iBase_EntityHandle* entity_handles,
                          /*in*/ const int entity_handles_size,
                          /*out*/ int *err);


We need some way to help the application construct an iBase_EntityHandle proxy for a given subpace of INDEXED entities. This might involve a new iMesh function such as...

iMesh_indexEntArr(
    iMesh_Instance inst,
    const iBase_EntityHandle indexed_ent,
    int logI, int logJ, int logK,
    iBase_EntityHandle *indexed_ent_arr,
    int *err); 

This is similar to the iMesh_indexEnt method, introduced above, but instead of returning a handle for a single entity within an indexed, structured collection, it would return another special indexed entity representing the particular subspace (line in 1D or plane in 2D).

What about AMR?

This is where both iMesh entity sets and either tags or parent/child graph would have to be used. The fundamental issue is to indicate how different structured collections of indexed entities nest within each other forming an AMR hierarchy. In addition, there is some metadata involving refinement ratios and relative logical index of origins of inter-nesting regions that quite possibly would have to be handled as tags data on the entity sets.