iRel Use Cases

iRel Requirements
iRel Interface (v1_0)
EntArr Proposal (v1 1)
"None" Type Proposal

Geometry-Based Smoothing

In this use case, smoothing-based mesh improvement is performed, where vertex positions are modified to improve shape quality of the mesh. After vertex movement, vertices which resolve geometric edges and faces must be projected back to those entities. This use case is described in terms of the steps to be performed and the functions in iGeom, iMesh, and iRel which are called to accomplish those tasks.

  • Instantiate iGeom, iMesh, iRel:
    • iGeom_newGeom, iMesh_newMesh, iRel_newRel
  • Read geometry, mesh into iGeom, iMesh
    • iGeom_load, iMesh_load
  • Request iRel to find existing relations
    • iRel_inferAllRelationsAndType(iRel_Instance, iRel_PairHandle*ph, int*err)
      When called on CGM/MOAB data, this function returns a Relation Pair Handle with type iGeom/Ent – iMesh/EntitySet. This type of relation is retrieved by matching (iGeom_getEntType, GLOBAL_ID) on iGeom Entity with (GEOM_DIMENSION, GLOBAL_ID) on iMesh Entity Set, where upper case indicates a tag name/value on the indicated entity, and iGeom_ - prefixed names indicate API functions.
  • Request change of type, to iGeom/Ent – iMesh/Both
    • iRel_ChangePairType(iRel_PairHandle*, iRel_ENTITY, iRel_BOTH)
      By default, smoothing is done by looping over mesh entities, computing new vertex positions then projecting vertices to geometric owners. For this to be efficient, iRel must support O(1) query of geometric owner given a mesh entity. An Entity-EntitySet geometry-mesh relation will not typically give that performance. In this case, the relation type must be changed, at least during the operation of this algorithm. The relation type is changed back again after smoothing is complete, in order to reduce memory requirements (since an Entity-EntitySet requires O(#geom ents) storage, compared to O(#geom ents + # mesh ents) for Entity-Both type relations).
  • Loop over mesh elements, computing new vertex positions and projecting to geometric owner
    • iMesh_getEntities, iMesh_getEntAdj to get entities and adjacent vertices
    • iMesh_getVtxCoord, iMesh_setVtxCoord to get/set vertex coordinates
    • iRel_getEntEntRelation(iRel_Instance, iRel_PairHandle, iBase_EntityHandle vert, iBase_EntityHandle *geom_ent, int switch_side=1, int *err)
    • iGeom_getEntType, iGeom_getEntClosestPt to get geometry entity type and closest point
      In the call to iRel_getEntEntRelation, the switch_side parameter is passed in true, to indicate that the query is passing in the second side of the relation and requesting the entity corresponding to the first side of the relation. This mechanism is used to reduce the overall number of functions in iRel, e.g. to avoid having both iRel_getEntSetRelation and iRel_getSetEntRelation.
  • Change type back to iGeom/ENT-iMesh/SET
    • iRel_ChangePairType(iRel_PairHandle*, iRel_ENTITY, iRel_SET)
      Changing the type back to ENTITY-SET reduces memory required to store the relation to O(#geom ents), from O(#geom ents + #mesh ents). For large meshes, this savings can be substantial.

Classification/Reverse Classification

The efficient linkage of the mesh to the geometric model is critical for mesh generation and adaptation procedures since it allows the specification of analysis attributes in terms of the original geometric model, the proper approximation of the geometry during mesh adaptation and supports direct links to the geometric shape information of the original domain need to improve geometric approximation and useful in p-version element integration. The unique association of a mesh entity of type d, to the geometric model entity of type p, d ≤ p, on which it lies is termed geometric classification, shortly classification.

For each model entity, the set of equal order mesh entities classified on that model entity defines the reverse geometric classification for the geometric model entity.

In this section, the use case of how to change classification of mesh faces classified on a model face is presented. For the comparison of iRel specifications before and after EntityArray Relation Type proposal embedded in this document, §4.2.1 illustrates the algorithm based on the iRel v1.0 (last updated in September 2010) and §4.2.2 illustrates the algorithm with iRel v1.1 (the current one with EntityArray Relation Type)

Algorithm with iRel v1.0

  • Instantiate iGeom, iMesh, iRel:
    • iGeom_newGeom (&igeom), iMesh_newMesh (&imesh), iRel_newRel (&irel)
  • Read geometry, mesh into iGeom, iMesh
    • iGeom_load, iMesh_load
  • Construct relation pair with geometry (type iRel_ENTITY) and mesh (type iRel_BOTH)
    • iRel_PairHandle ph;
    • iRel_inferAllRelationsAndType(irel, &ph, &err)
      When called on CGM/MOAB data, this function returns a relation pair handle with type iGeom/Ent – iMesh/EntitySet. When called on GMI/FMDB, this function returns a relation pair handle with type iGeom/Entity – iMesh/Both.
    • If relation type is not iGeom/Entity-iMesh/Both, iRel_ChangePairType(&ph, iRel_ENTITY, iRel_BOTH)
      An iGeom/Entity-iMesh/EntitySet relation will not typically give that performance for operations with classification/reverse classification, CGM/MOAB should change its relation type to iGeom/Entity-iMesh/Both.
  • Given a model face gf, get mesh entities classified on it (get reverse classification)
    There are three of get relation functions and two set relation functions available for this job. Therefore, total six (3*2) get-set combinations are available. In this example, we use iRel_getEntSetIterRelation and iRel_setEntEnArrRelation.
    • iBase_EntityIterator iter;
    • iRel_getEntSetIterRelations (irel, &ph, gf, 0, &iter, &err)
      When called on CGM/MOAB, this function calls iMesh_initEntIter with entity set related to the geometric face gf. When called on GMI/FMDB, this function returns an internal reverse classification iterator.
    • Create an entity array with size n, where n is # mesh entities classified on gf
      Due to the array size n is unknown, one-round iteration over set with iMesh_getNextEntIter (&iter), iMesh_endEntIter(&iter) is performed. The time complexity of set iteration is O(m)
    • Fill the entity array entarr with mesh entities traversed through iterator; iMesh_getNextEntIter (&iter), iMesh_endEntIter(&iter). It is O(n) operation.
  • set classification of mesh entities to another model face another_gf (set classification).
    • iRel_setEntEntArrRelation (irel, &ph, another_gf, 0, entarr, n, &err)
      When called on CGM/MOAB, this function remove existing relation of gf and related entity set, and set the relation of another_gf with a set containing entities in entarr. When called on GMI/FMDB, for each mesh entity in entarr, this function updates its classification to another_gf. It is O(n) operation.

The algorithm above requires m mesh entity traversal, n mesh entity copy, and n mesh entity modification operation where m is # mesh entities of type(gf) and n is # of equal order mesh entities classified on gf.

Algorithm with iRel v1.1

  • Instantiate iGeom, iMesh, iRel:
    • iGeom_newGeom (&igeom), iMesh_newMesh (&imesh), iRel_newRel (&irel)
  • Read geometry, mesh into iGeom, iMesh
    • iGeom_load, iMesh_load
  • Construct relation pair with geometry (type iRel_ENTITY) and mesh (type iRel_ENTARR)
    • iRel_PairHandle ph;
    • iRel_createPair (irel, &ph, igeom, iRel_ENTITY, IGEOM_IFACE, imesh, iRel_ENTITYARR, IMESH_IFACE, &err)
      This function returns a relation pair with type iGeom/Entity – iMesh/EntityArray.
  • Given a model face gf, get an iterator on mesh entities classified on gf (get reverse classification)
    • iMesh_EntityIterator iter;
    • iRel_getEntEntArrRelation (irel, &ph, gf, 0, &iter, &err); // It is O(1) operation
      This function returns an entity iterator on mesh entities classified on gf.
    • iMesh_getNextEntIter (imesh, iter, f1, &has_next_item, &err);
  • set classification of mesh entities to another model face another_gf (set classification).
    • WHILE (has_next_item==true) // FOR each mesh entity classified on gf
      • Rel_setEntEntRelation (irel, &ph, another_gf, 0, *iter, &err);
      • iMesh_getNextEntIter (imesh, iter, f1, &has_next_item, &err);
    • ENDWHILE // This step is O(n) operation.
  • iMesh_endEntIter(imesh, iter, &err);

The algorithm in v1.1 doesn't need m mesh entity traversal nor n entity copying, where m is # mesh entities of type(gf), and n is # of equal order mesh entities classified on gf. See footnote3 for discussion.

Edge Swapping

Edge swapping on a triangle mesh can be used to improve mesh quality, after mesh generation or adaptive mesh refinement and coarsening. An edge swap is defined as taking an edge ab and two triangles abc and adb, forming new edge dc and triangles adc and dbc, and deleting edge ab and triangles abc and adb. In other words, the edge is "swapped" such that it cuts the quadrilateral along the other diagonal. This use case illustrates the use of iRel in the presence of mesh modification.

Algorithm description: for each edge e classified on a model face and the two connected tris classified on the same face, if the quality of those tris is less than that of the tris formed by the edge swap, perform the swap. Repeat until no mesh improvement is possible.

This procedure can be implemented in several ways; we illustrate two here.

See this footnote1 for a discussion of this algorithm:

Input: mesh instance, model face gf, function F(edge e, faces f1, f2) which returns true if e should be swapped; F is guaranteed to terminate at some point
Output: A modified mesh with edge swapping

Algorithm A:

do
  num_swaps = 0
  Get all edges classified on gf -> {e}
  for each edge ei in {e}
    Get 2 tris, f1, f2, adjacent to ei and classified on gf
    Get 2 vertices on ei, oriented in positive sense with respect to f1 -> v1, v2
    Get other vertex v3 in f1, v4 in f2 -> v3, v4
    if F(ei, f1, f2) = true
      Create edge e1(v4,v3), tris f3(v1,v4,v3), f4(v3,v2,v4)
      Add e1, f3, f4 to added entity list {a}
      Add ei, f1, f2 to deleted entity list {d}
      num_swaps++
    endif
  endfor
  Classify entities in {a} on gf
  Delete entities in {d}
  Clear {a}, {d}
while num_swaps > 0

See this footnote2 for further discussion.

Algorithm B:

do
  num_swaps = 0
  for each mesh edge ei classified on gf do
    Get 2 tris, f1, f2, adjacent to ei and classified on gf
    Get 2 vertices on ei, oriented in positive sense with respect to f1 -> v1, v2
    Get other vertex v3 in f1, v4 in f2 -> v3, v4
    if F(e, f1, f2) = true
      delete old entities ei, f1, f2;
      Create edge e1(v4,v3), tris f3(v1,v4,v3), f4(v3,v2,v4)
      set classification of e1, f3 and f4 and update reverse classification of gf;
      num_swaps++
    endif
  endfor
while num_swaps > 0

Psuedo code of edge swapping

Input: Instances imesh, igeom, irel, relation pair handle ph, model face gf, should-swap funtion F(e, f1, f2)

Algorithm with iRel v1.0

  • If relation type is not iGeom/Entity-iMesh/Both, iRel_ChangePairType(&ph, iRel_ENTITY, iRel_BOTH)
  • iRel_getEntSetRelation (ph, gf, false, &ent_set);
  • initialize added entity list {a}, deleted entity list {d}
  • do
    • num_swaps = 0
    • Get mesh edges classified on model face gf and initialize an iterator iter on them
      • iMesh_initEntIter (imesh, ent_set, iBase_EDGE, iMesh_ALL_TOPOLOGIES, &iter, &err);
      • iMesh_getNextEntIter (iter, e1, &has_next_item);
    • WHILE (has_next_item==true) // FOR each mesh edge e1 in ent_set
      • iBase_EntityHandle v1, v2, v3, v4, f1, f2, fs[], tmp_h[], gfs[]
      • get faces f1, f2 adjacent to e1, classified on gf, and not in {d}:
        • iMesh_getEntAdj(e1, iBase_FACE, tmp_h)
        • iRel_getEntArrEntArrRelation(ph, tmp_h, true, gfs)
        • for f in tmp_h, if gfs[f] == gf and f not in {d}, assign to f1, f2
      • get vertices in e1: iMesh_getEntAdj(e1, iBase_VERTEX, tmp_h) -> v1, v2
      • get other vertices v3, v4 such that v3 in f1, v4 in f2
        • uses iMesh_getEntAdj
      • if F(e1, f1, f2) = true
        • create edge e2(v4,v3), faces f3(v1,v4,v3), f4(v4,v2,v3), using iMesh_createEntArr
        • add e2, f3, f4 to {a}
        • add e1, f1, f2 to {d}
        • num_swaps++
      • end if
      • iMesh_getNextEntIter(iter, e1, &has_next_item);
    • end while
    • classify entities {a} on gf
      • create dummy list {g} with length = length{a}, all positions initialized to gf
      • iRel_setEntArrEntArrRelation(ph, a, true, g)
    • remove relation info from entities {d}
      • iRel_removeEntArrRelation(ph, d, true)
    • delete deleted entities
      • iMesh_deleteEntArr(d)
    • clear {a}, {d}
  • while num_swaps > 0
NOTES:
  1. Additional iRel function iRel_removeEntArrRelation is proposed
  2. List {d} can be std::set, with "find" complexity of logN, {a} can be std::vector
  3. Assumes iterator does not visit new edges and faces. If it does, insert check for edge in {a} at start of while loop. Or, if storage is not a concern, abandon use of iterators altogether in favor of local arrays.
  4. For more general cases, e.g. edge collapse, would need to check that edge isn't in deleted list.

Algorithm with iRel v1.1

  • Instantiate iGeom, iMesh, iRel:
    • iGeom_newGeom (&igeom), iMesh_newMesh (&imesh), iRel_newRel (&irel)
  • Read geometry, mesh into iGeom, iMesh
    • iGeom_load, iMesh_load
  • Constructing relation pair with geometry (type iRel_ENTITY) and mesh (type iRel_ENTARR)
    • iRel_PairHandle ph;
    • iRel_createPair (irel, &ph, igeom, iRel_ENTITY, IGEOM_IFACE, imesh, iRel_ENTITYARR, IMESH_IFACE, &err)
    • This function returns a relation pair with type iGeom/Entity – iMesh/EntityArray.
  • Get mesh faces classified on model face gf
    • iMesh_EntityIterator iter;
    • iRel_getEntEntArrRelation (irel, &ph, gf, 0, &iter, &err);
    • iMesh_getNextEntIter (imesh, iter, f1, &has_next_item, &err);
  • WHILE (has_next_item==true) // FOR each mesh face f1 in ent_set
    • get longest edge e of f1 and find another face f2 adjacent to e
      • iMesh_getAdjEnt
    • Among mesh vertices adjacent to f1 and f2, get two vertices v1 and v2 not adjacent to e
      • iMesh_getAdjEnt
    • With two vertices v1 and v2, create a new edge new_e
      • iMesh_createEnt (imesh, iMesh_LINE_SEGMENT, array[v1, v2], 2, new_e, &err);
    • Using the new edge, create two new faces new_f1 and new_f2
      • iMesh_createEnt (imesh, iMesh_TRIANGLE , array[new_e, …], 3, new_f1, &err);
      • iMesh_createEnt (imesh, iMesh_TRIANGLE , array[new_e, …], 3, new_f2, &err);
    • Set classification of newly created mesh entities to gf
      • iRel_setEntEntRelation (irel, &ph, gf, 0, new_e, &err);
      • iRel_setEntEntRelation (irel, &ph, gf, 0, new_f1, &err);
      • iRel_setEntEntRelation (irel, &ph, gf, 0, new_f2, &err);
    • Remove old mesh entities
      • iMesh_deleteEnt (imesh, e, &err);
      • iMesh_deleteEnt (imesh, f1, &err);
      • iMesh_deleteEnt (imesh, f2, &err);
        "no invalidated iterator with entity removal" is provided by underlying interfaces
    • Advance to next face
      • iMesh_getNextEntIter (imesh, iter, f1, &has_next_item, &err);
  • ENDWHILE
  • iMesh_endEntIter(imesh, iter, &err);

Discussion Notes

1 Note 1:

Mark Beall: The reason I suggested Seegyoung write the code with a simple reason to swap the edge (longest edge), was to not clutter up the example with the extra stuff that goes along with actually having a reason to do that. However these are fine, but I don't think we need all three examples to discuss.

Tim: I agree it makes things unnecessarily complicated. How about we say something like "function f(e, gf) returns whether edge e needs to be swapped", or something like that? One thing that opens us up to is needing some sort of termination criterion, that's what I was trying to do with the num_its.

Mark Beall: I think that would be fine. I think termination if there are now swaps to be done (with the stated assumption that whatever the criteria is would guarantee termination) would be fine. Actually, I need to think about that a bit more after writing the comments below - that function can be complicated by the need to check for entities that are in the deleted list (for operations other than a swap), so it might be best not to hide it.

2 Note 2:

Mark Beall: Need to check above if ei in {d} right after "for each edge ei in {e}"

Tim: Nope, it won't be, since we're iterating over edges in the for loop, deleting at the end of the while loop, and resetting {d} before the next iteration.

Mark Beall: You're right. However if we were doing collapses rather than swaps, it would be needed since other edges will be affected.

Tim: Yep.

Mark Beall: In my opinion, having to require the user to temporarily keep track of changes to classification, addition and deletion as in this example rather than being able to efficiently do that using iRel and iMesh means that code is more complicated and thus more error prone (simply because there is more code to write).

Tim: That depends on the cost of going through the API, and the storage datastructure for relations. In some cases, e.g. array-based storage containers, deleting in chunks will result in substantial savings.

Mark Beall: It's still more code, thus more errors. If the example above were doing collapses you'd have a lot more overhead in checking for entities that are connected to things than in this example (since you have to evaluate all of the faces that might be affected by the collapse, which are all of the faces connected to the vertex being collapsed, and you'll have to sort out which of those still exist.

Tim: This is devolving into a discussion about coding style. Clearly, the algorithm is targeted at the use case as described, and would probably be different for a different use case. Also, one of the reasons for including both Algorithm A and B above could be to allow description of a more general algorithm.

Mark Beall: I thought the question on the table was whether or not all iterators need to be updated due to any changes so that they are always valid in cases when things are removed and your Algorithm A was demonstrating how you would do things if that wasn't the case. If that is what we are talking about, then I'd say that this isn't about "style" at all, but rather about the code that would have to be written as a consequence of that design decision in the interface. If that's not what we're talking about here and both A and B should be completely valid ways of doing things (meaning that all iterators must be valid with deletions), and A is just an alternative approach if the implementation you're using happens to have better performance if you do the addition and deletions as a "batch" operation, then we don't have to discuss this aspect of things anymore and can move on.

Tim: I agree with these statements. My understanding so far was that this use case was meant to demonstrate usage of iRel under a relatively simple case of mesh modification. If we can come up with a different use case that both demonstrates the kind of things you'd see in edge collapses and is not horrendously complicated, it would be useful to replace this use case with that one. My intent with algorithms A and B was indeed that they should be equivalent, just different ways of approaching the problem.

Mark Beall: OK then, sorry I misunderstood the intent of what you wrote. Given that we agree on that, then I think the next step is to make sure that this requirement for iterators is clear in the spec. Then we can delete all of these comments. Given that, I think that simplifying the use case to your previous suggestion is a good idea and that we can then determine what iRel functions would be called in each case.

Tim: Yeah, and we should summarize this thread in a note at the end of this page; I'll do that, probably tomorrow; could you update the use case description and maybe the 1.1 algorithm? Since we haven't heard from Mark S. or Seegyoung, I'll assume they're fine with this too.

Mark Beall: Yes, I'll do that, might not get to it today. For some reason my "watch" on this page got removed and I didn't get a notice of your comment.
Mark Beall: I started to do this and I realized that I really wanted the two algorithms to be doing the same thing, however I would like the issue of mesh entities being deleted of the type we are iterating over. The original example looped over faces and then did swaps on edges, which is somewhat contrived (or requires more logic to understand why we might do that). So instead I'd like to just change the example to collapsing edges (e.g. any edges shorter than a certain length that can be collapsed will be collapsed) which is more realistic and does have the property of deleting entities of the type we are iterating over other than the one we just got from the iterator. Is that OK?

Tim: The only qualm I have with that is the extra logic that'll be needed to decide which edge of each pair that'll need to be deleted (depends on classification) and how that'll complicate the use case. Could you write up a straw man algorithm and send by email before we decide? Or, maybe we can move this conversation to a separate "Quest for the perfect use case discussion" page to avoid cluttering the final product...

Mark Beall: If I'm adding f1 and f2 to the deleted entity list, wouldn't that mean that they are still in the mesh and connected to other entities that they were previously connected to? If so, then the "Get 2 tris, f1, f2, adjacent to ei and classified on gf" would really involve getting all the faces adjacent to ei (some of which are in {d}) and find the 2 that aren't in {d}. You don't then have to worry about f1 or f2 being in {d} since there must be exactly 2 faces that meet that criteria. For a 3D version of this algorithm, that could be a lot of searching in {d}.

Tim: You're right; I'll figure out how to fix that. For a 3D version, I'd consider using a marking scheme in addition to the list for that reason.

3 Note 3

Tim: In the "Classification/Reverse Classification" use case, it is stated that the cost of constructing an iterator over the set of mesh entities classified on a model face is O(n). Strictly speaking, the cost is O(S(n)), or the cost of getting all entities in a set, which will vary by implementation. For example, in MOAB, this will be O(1), for both vector- and set-based sets. As stated, this seems to imply that querying the contents of a set in FMDB is always O(n). Similarly, for the use case as stated (but implemented using different calls to iRel), changing all of the entities classified on one model face to be classified on another model face will be O(S(n)), where S(n) is the complexity of querying or changing the total contents of a set. Again, the actual complexity depends on implementation; in MOAB, this will typically be O(1). Thus, the total cost for this use case, using v1.0 of iRel, will be 3*O(S(n)), assuming the cost of changing all contents is the same as retrieving all contents. For any

implementation using array-based sets, this will boil down to O(1).

Seegyoung: Constructing an iterator over mesh entities classified on a model face is O(1). The point is, in case of iRel v1.0, because of interchangeable EntArr/Set property, FMDB should do m mesh traversal, n mesh entity copy from set to entity array, and n mesh entity modification where m is # mesh entities of type(gf) and n is # of equal order mesh entities classified on gf. In case of FMDB, m mesh entity traversal is necessary to compute n, since it is unknown without equal order mesh entity traversal. However, with EntArr type, neither m mesh entity traversal nor n entity copying is needed.

Tim: If you're using the v1.1 algorithm above, then the step "Given a model face gf, get an iterator on mesh entities classified on gf " will be O(m), since you're not keeping a list on the Ent side, as stated before. Or, more precisely, iterating through the n entities classified on gf will be O(m), not O(n).

Also, I will point out that for complexity analysis, strictly speaking, O(n) is the same as 3*O(n).

Sorry for awkward writing - I was in a rush to give-out without thorough review; I rewrote the performance comparison.

Tim: In the algorithm for v1.1, getting an iterator to reverse classification (i.e. to entities classified on a model entity) is not guaranteed to be O(1) (see point 2 above). If this operation is in fact O(1), and the setEntEntRelation in the WHILE loop of this use case is O(n) for the whole while loop, then there must be extra constraints on how relations are stored in the implementation. That is, I don't see a way to support both O(1) retrieval and O(1) deletion of individual entities from (whatever stores) the EntArr.

You might ask how MOAB can then do this operation with O(1) complexity; the answer is in how you describe the use case and its implementation. As stated, this use case describes classification of all faces on a different model face.

Seegyoung: Yes, performance comparison depends on how we describe the use case and its implementation. Even for the same operation (e.g. getting an iterator to reverse classification), time complexity will be different from implementation to implementation. In case of FMDB, getting an iterator is constant time function. The sole purpose of the classification/rev. classification use case is to demonstrate how the iRel v1.0 doesn't effectively accommodate the implementations which stores the relation data in the underlying implementations.

Tim: How can constructing the iterator be O(1), if you're not storing anywhere the collection of entities classified on a model face gf? Pedantically you could say constructing the iterator is O(1), since technically that iterator just needs to store the handle for gf; if you want to go that way, fine, but then iterating that iterator to find the m entities classified on gf is still O(m), not O(n).