Outline of Design of STLBoost Implementation of iMesh

These notes are just a collection of ideas and issues in the design of fairly simple implementation of iMesh based on either STL or Boost container classes. The focus is on robustness and simplicity in implementation at the (hopefully minimal) sacrifice of performance.

Inventory of objects in the iMesh interface

  • iMesh instance(s)
    • Current specification says implementations are not required to distinguish between objects in different iMesh instances. So, if a caller accidentally interchanges objects from one iMesh instance within another, there is no requirement that an implementation detect this condition or handle it properly. The result is undefined.
  • entities (manifesting above the API as iBase_EntityHandle and _Arr_s of these)
    • vertex entities
      • which can have 1,2 or 3 numerical values associated with them representing lagrangian coordinates
    • higher dimensional entities (e.g. edges, faces, regions)
      • which are composed of lists of lower dimensional entities
      • which have adjacency with other entities
  • entity sets (manifesting above the API as iBase_EntitySetHandle)
    • the root set which has special meaning
    • which can behave like STL sets or STL lists
    • which can contain other sets
    • which can have parent/child relationships as well (a separate graph)
    • which can have sets or entities added to them and removed at will
  • iterators (iBase_EntityIterator and iBase_EntityArrIterator)
    • iterating over individual entities or arrays of entities
    • Iteration is defined over the members of a set
  • tags (manifesting above the API as iBase_TagHandle)
    • which can have different numbers of values of one of a few basic primitive types.
    • which can be associated (e.g. attached to) with almost any of the previously listed objects
      • A single entity, a group of entities, an entity set.
    • which contains data that can be read or written
  • Any instance of one of the above types of objects can be created or destroyed

Notes about entity and entity-set handles

Are the handles returned to the caller the same handles the implementation uses internally to, for example, refer to the lower-dimensional entities comprising a higher dimensional entity? Can the implementation manage a single pool of storage (memory) into which it places all entities and entity sets and simply return pointers to these objects as their handles? Can the handles used above the API store any useful data about the entities to which they refer? Or, is the only useful function the handles serve is for the caller to identify to the implementation which entities it is referring to?

Consider just vertex entities for a moment. The minimum storage required for a vertex entity is the 1, 2 or 3 numerical values (float or double) used to associate the (lagrange) coordinate field dof with the entity. In the FE codes with which I am familiar, references (e.g. handles) to individual vertex entities are the integral value indicating their position within the arrays storing the associated coordinate data. A higher dimensional element such as a hexahedron is constructed by identifying 8 integral values (in a specific order) representing 8 entries (vertex entities) within the coordinate arrays.

If we identified vertex entities by say an integral value, we could store them as an STL map<int, coords> where type coords was something like float[dim] where dim is {1,2,3}. However, such an approach would involve every vertex entity requiring sizeof(int)+sizeof(coords) storage for the map keys and values.

If a caller creates higher dimensional entities solely be enumerating vertex entities (e.g. a hexahedron defined by 8 vertex entities), what are requirements of implementation in terms of returning entity handles for the edges or faces of the entity? I mean, if the caller gives only the vertex entities comprising a hex, is implementation still required to return handles to faces or edges of that hex when requested? If so, that implies that there are face and edge instances in the implementation to which those handles refer, right? Or, is it ok to return a handle to something like proxy that stands in for face or edge entities that are not actually stored anywhere in the implementation?

Can we pass C++ references as iBase_EntityHandles?

I looked at this quite a bit and concluded it is not possible in general. First, iBase_EntityHandle is required to be a pointer type due to typedef iBase_EntityHandlle_Private* iBase_EntityHandle in iBase.h. You can't have pointers to C++ references. C++ tries really hard to hide the implementation of a reference anyways. So, if you wanted to copy a reference into the same memory space as an iBase_EntityHandle, that would mean sizeof(ref)<=sizeof(iBase_EntityHandle) which won't be true in general.

Can we design our handles so that we can detect iMesh instance/entity handle mixups?

The spec. doesn't require this but I think its too important an issue to overlook. Whether an implementation can detect errors in mixing entity handles from different iMesh instances (and maybe even different implementations of those instances) is undefined. However, I am wondering if its possible to design an implementation that can...

  • detect mixing entity handles among its own iMesh instances
  • detect mixing entity handles between its own implementation and other implementation's iMesh instances

One scheme I've considered comes at the price of an extra word per vertex element. We can hash coordinate data associated with a vertex element (or in the case of a non-lagrange coordinate field handled instead by iField for which iMesh will get dummy coordinate data, we can create a fictional id for each vertex element. Since the design I propose here will store the entire dimensional cascade for all elements, every element will either be a vertex element or refer to a vertex element. So, when iBase_EntityHandles are passed into this implementation, it will descend to its verticies and check that the hashed/id value for the vertex is valid. Hmm. that means higher dimensional elements are believed to be part of this implementation. Hmm, maybe this hash/id check then needs to be done at each dimensional entity? If we make this feature compile-time configurable, it would be possible to compile the library one way and get this extra level of error checking for debugging purposes but not suffer the extra stroage cost in real applications.

Cost of storage of full dimensional cascade of all entities

Consider a 2D mesh of NxN quadrilateral elements. For large N, there are approximately as many edge entities as there are vertex or quad entities. We could opt to store each quad as a list of its 4 vertex entities and never explicitly store edge entities (not sure what the implications are for getAdj calls). However, we could instead store a list of the unique edges and then store each quad as a list of its 4 edges. Either way, a quad involves 4 entity references (either 4 vertex entity references or 4 edge entity references). Assuming vertex and edge entity references require the same storage, the only significant difference between the two modes of storage is the extra space for the unique edges. Since an edge requires two vertex entity references (half again as much as a quad), storing the full dimensional cascade (each quad in terms of unique edges and each edge in terms of unique vertices), requires only 50% more storage. The benefit of such a storage scheme is that it makes the resulting database more flexible in terms of servicing adjacency queries. On the other hand, it makes deletion of entities a litte more complex.

How do these arguments pan out in an 3D mesh of NxNxN hexahedral elements? Storing hex in terms of vertex entities is 8 entity refs per hex. Storing each hex in terms of 6 (unique) face entities and then each face in terms of 4 (unique) edge entities and each edge in terms of 2 (unique) vertex entities I think means a hex involves, on average, 12 entity references rather than 8. So the storage cost for storing the full dimensional cascade is only 50% over storing ent-to-vertex entity.

So, regardless of how caller presents entities to the implementation, we could decide in the implementation to always, underneath the covers, maintain the complete entity hierarchy. The storage overhead is about 50%.

How does this design decision impact our ability to perhaps support a structured grid in a revised iMesh interface such as outlined here, Planning for iMesh to support structured grid and AMR. There, we will require the ability to have a sort of entity handle proxy that actually represents a larger, implicit collection of entities not actually explicitly stored but which can nonetheless by identified by a handle and acted upon like any ordinary entity handle.

Bare Minimum Implementation

What is the absolute minimum iMesh implementation? I don't think this has ever been established. But, from a common sense approach, the minimum useful mesh is a collection of vertex entities and nothing else; no entity sets or parent/child relationships and no tags. Such an iMesh implementation would probably be suitable for a number of discrete/gridless meshes (e.g. molecular, point clouds, etc).

In this context, we need to be able to create and destroy vertex entities of 1, 2 or 3 spatial dimensions. We need to be able to iterate over entities in the root set. We would need to be able to save and load the data to a file.