HOOPS Exchange Hierarchy Traversal: Part 1
By Brad Flubacher • This is the first of a two-part article, in which we will develop a generalized algorithm for traversing the object hierarchy implemented in HOOPS Exchange. Traversing the object hierarchy is an important and ubiquitous part of almost every workflow. The algorithm we’re describing here can be found inside the Exchange Toolkit.
HOOPS Exchange is a software development toolkit that provides application developers the ability to read a variety of standard and proprietary 3D file formats, such as STL, OBJ, STEP, IGES, SolidWorks and CATIA. In addition to 3D geometry, HOOPS Exchange provides access to the assembly tree, which is the logical structure of the 3D data authored by the designer.
The data structures used to represent the complex 3D data set have a hierarchical relationship. For example, after using HOOPS Exchange to load a file you are provided with an A3DAsmModelFile object. This “top-level” object is composed of one or more assembly nodes, stored as a C-style array of A3DAsmProductOccurence objects. Furthermore, these assembly node objects are recursive. That is, an A3DAsmProductOccurence can contain an array of “child” A3DAsmProductOccurrence objects and/or an A3DAsmPartDefinition, which represents a 3D part.
Additional examples of the hierarchical relationship between objects can be seen by examining the topological objects present in HOOPS Exchange B-Rep data. In this classic scenario, we find A3DTopoBrepData contains and array of A3DTopoConnexes, which contain an array of A3DTopoShell objects. Shells contain faces, which contain loops, which contain co-edges, which contain edges, which finally contain vertices.
By now, we have established that the hierarchical relationship between objects is pervasive in HOOPS Exchange and a generalized algorithm for traversing objects is desirable.
Our goal is to create a generic algorithm that takes two inputs- an “owning” object of arbitrary type, and a type-specifier. The return value from this algorithm should be a collection of objects, all of the specified child type, that are owned by the owning object- either directly or implicitly through intermediate objects. We’ll achieve this goal in steps.
First, we need a function to return the objects that are immediately contained within the parent. For example, to retrieve all faces within a shell, we would write the function as follows:
std::vector<A3DTopoFace*> getShellFaces(A3DTopoShell *shell) {
std::vector<A3DTopoFace*> result;
A3DTopoShellData shell_d;
A3D_INITIALIZE_DATA(A3DTopoShellData, shell_d);
A3DTopoShellGet(shell, &shell_d);
if(shell_d.m_uiFaceSize > 0) {
result.insert(result.begin(),
shell_d.m_ppFaces,
shell_d.m_ppFaces + shell_d.m_uiFaceSize);
}
A3DTopoShellGet(nullptr, &shell_d);
return result;
}
This function body is a pattern which would be repeated for each object in the hierarchy. As you can see this is a bit verbose and not very generic.
Let’s start changing things to make this more concise. If we use the Data Access tools available in ExhangeToolkit.h, we can drastically simplify the code to something much more manageable:
std::vector<A3DTopoFace*> getShellFaces(A3DTopoShell *shell) {
ts3d::A3DTopoShellWrapper shell_d(shell);
return ts3d::toVector(shell_d->m_ppFaces, shell_d->m_uiFaceSize);
}
In addition to being more manageable, this implementation is also less error prone.
To make this more generic, we can use the fact that both A3DTopoShell and A3DTopoFace are aliases for the same type (void). Since this code is “Exchange-centric”, we can replace the argument type and return type with A3DEntity. This type denotes the base type in Exchange and is also aliased to the void type.
After making this change, our function signature is starting to look a little more generic:
std::vector<A3DEntity*> getShellFaces(A3DEntity *shell) {
ts3d::A3DTopoShellWrapper shell_d(shell);
return ts3d::toVector(shell_d->m_ppFaces, shell_d->m_uiFaceSize);
}
As a next step, we could modify this function to accept any type of parent and return the collection of children by switching on the entity type.
ts3d::EntityArray getChildren(A3DEntity *ntt) {
switch(ts3d::getEntityType(ntt)) {
case kA3DTypeTopoShell:
return getShellFaces(ntt);
case kA3DTypeTopoFace:
return getFaceLoops(ntt);
// and so on and so forth
}
return ts3d::EntityArray();
}
The function getFaceLoops would be implemented like getShellFaces. The keen observer (you, no doubt) will notice that we’ve swapped out the std::vector and replaced it with ts3d::EntityArray. They’re equivalent types. This change further favors brevity and maintainability.
The switch statement implements only two cases above, so it handles only two Exchange object types. It could be extended to handle all object types used in the Exchange architecture. To do this, we would need to declare a unique function for each type of object and implement it to return the children available within. This would result in a lot of code, even with all the changes we made to make it more concise (and less error prone). We can somewhat manage this massive expansion in code using function objects and an unordered hash.
Let’s take this set of changes in two steps.
Still focusing on just the two object types we’ve referenced so far, by using function objects and an unordered hash we can rewrite the getChildren function as follows.
ts3d::EntityArray getChildren(A3DEntity *ntt) {
using Getter = std::function<ts3d::EntityArray(A3DEntity*)>;
using ParentTypeToGetter = std::unordered_map<A3DEEntityType, Getter>;
static ParentTypeToGetter _getterMap = {
{ kA3DTypeTopoShell, getShellFaces },
{ kA3DTypeTopoFace, getFaceLoops }
};
return _getterMap[ts3d::getEntityType(ntt)](ntt);
}
We’re keepin’ it tight here.
Handling new types can now be done in two steps- first, by adding a get function, then by adding an entry in the unordered hash for the parent object type (key), paired with the get function (value). But let’s face it- Once we’ve implemented this function completely, who is going to use the individual get functions directly? Maybe someone, but let’s ignore them for now.
Using lambdas, we can eliminate the independent get functions as well, further reducing the number of lines of code we must write (and maintain). For code clarity, we’ve added some newlines as well.
ts3d::EntityArray getChildren(A3DEntity *ntt) {
using Getter = std::function<ts3d::EntityArray(A3DEntity*)>;
using ParentTypeToGetter = std::unordered_map<A3DEEntityType, Getter>;
static ParentTypeToGetter _getterMap = {
{
kA3DTypeTopoShell,
[](A3DEntity *ntt) {
ts3d::A3DTopoShellWrapper d(ntt);
return ts3d::toVector(d->m_ppFaces, d->m_uiFaceSize);
}
},
{
kA3DTypeTopoFace,
[](A3DEntity *ntt) {
ts3d::A3DTopoFaceWrapper d(ntt);
return ts3d::toVector(d->m_ppLoops, d->m_uiLoopSize);
}
}
};
return _getterMap[ts3d::getEntityType(ntt)](ntt);
}
This is really great place to pause and be sure you have a firm grasp on what’s been presented so far. If you came to this article and were like “tldr, let me get to the point...”, to you, I say “Abort! Abort!”. It’s going to get a little more complicated from here out.
If you have been following along, then you should be comfortable with the last code snippet. You should understand that in this snippet, we’re constructing a static unordered hash that allows us to lookup a function object by Exchange object type. In this snippet, we’ve only populated the unordered hash with two getters for two object types with the understanding that a complete implementation would include all getters for all object types.
The complete implementation of getChildren would be useful by itself. But we can do more to make it even better. For example, if we look at A3DAsmProductOccurrence, we notice that there are different types of children that our function might return. The function could return children that are of type A3DAsmProductOccurrence, A3DAsmPartDefinition, A3DMkpView, A3DGraphCamera, or A3DMkpAnnotationEntity. It would be more generic (and useful) if we allowed the consumer of our function to specify which type of child objects they want.
Let’s implement getChildren so it handles the case we’ve just described. Again, understand that a complete implementation will include all parent object types, along with getters for all possible types of children. Here, we’re presenting only a small set that is representative of the whole.
ts3d::EntityArray getChildren(A3DEntity *ntt, A3DEEntityType const child_type) {
using Getter = std::function<ts3d::EntityArray(A3DEntity*)>;
using ChildTypeToGetter = std::unordered_map<A3DEEntityType, Getter>;
using ParentTypeToChildTypeToGetter = std::unordered_map<A3DEEntityType, GetterMap>;
static ParentTypeToChildTypeToGetter _getterMapByParentType = {
{
kA3DTypeTopoShell, // parent type
{
{
kA3DTypeTopoFace, // child type
[](A3DEntity *ntt) { // getter
ts3d::A3DTopoShellWrapper d(ntt);
return ts3d::toVector(d->m_ppFaces, d->m_uiFaceSize);
}
}
}
},
{
kA3DTypeTopoFace, // parent type
{
{
kA3DTypeTopoLoop, // child type
[](A3DEntity *ntt) { // getter
ts3d::A3DTopoFaceWrapper d(ntt);
return ts3d::toVector(d->m_ppLoops, d->m_uiLoopSize);
}
}
}
},
{
kA3DTypeAsmProductOccurrence, // parent type
{
{
kA3DTypeAsmProductOccurrence, // child type
[](A3DEntity *ntt) { // getter
ts3d::A3DAsmProductOccurrenceWrapper d(ntt);
return ts3d::toVector(d->m_ppPOccurrences,
d->m_uiPOccurrencesSize);
}
},
{
kA3DTypeGraphCamera, // child type
[](A3DEntity *ntt) { // getter
ts3d::A3DAsmProductOccurrenceWrapper d(ntt);
return ts3d::toVector(d->m_ppCamera, d->m_uiCameraSize);
}
} // … and so on and so forth …
}
}
};
auto const parent_it = _getterMapByParentType.find( ts3d::getEntityType( ntt ) );
if(std::end(_getterMapByParentType) == parent_it) {
return ts3d::EntityArray();
}
auto const child_it = parent_it->second.find(child_type);
if(std::end(parent_it->second) == child_it) {
return ts3d::EntityArray();
}
return child_it->second(ntt);
}
Imagine if had jumped straight to this implementation. It would be a bit overwhelming, and confusing for sure. But we’ve taken a series of logical steps to arrive at this. So, what do we have?
We’ve (partially) implemented a function that takes an arbitrary parent object (ntt) and a desired child object type (child_type). Internally, the function is composed of a static map (_getterMapByParentType) that allows us to look up the needed getter function by parent type, then by desired child type. I’ve added a couple of comments to make the structure of the constructor more readable.
Now, imagine this structure completely populated with all Exchange object types and getter functions for all possible types of children. Instead of thinking about this as just functionality, think of this as a data model. It is a data model that expresses the complete set of parent-child relationships present in HOOPS Exchange! Perhaps you can see where we are going with this.
It seems that this is a natural place to conclude Part 1 of the article. We’ve established a concise approach to capture both the object hierarchy employed by Exchange, as well as embedded functionality that allows us to traverse it. In Part 2, we’ll dive into the algorithm that uses the data model we’ve just created to intelligently navigate the hierarchy, allowing the consumer to obtain descendants of an arbitrary type from a given parent object.
If you have any questions or comments on what’s been presented here, please feel free to comment below! I’ll be happy to continue the conversation.