Anatomy of CAD feature

Packed map of integers

Analysis Situs expresses all CAD features with unordered sets of indices addressing the corresponding B-rep faces. The 1-based index is a king in that software. Putting the indices together, we can reference a group of boundary elements in a persistent (serializable) way. While there is a standard collection in C++ for exactly that matter (std::set), we have not used it from the very beginning and preferred what OpenCascade provided. Basically, the kernel comes up with all kinds of collections you might want to have in your code, and some of these data structures are surprisingly good. One such is TColStd_PackedMapOfInteger (PMOI). This data structure provides a memory-efficient way of managing integer sets encoded in a bitwise manner.

The PMOI data structure utilizes the old idea of turning a single integer value (its 32 bits) into a bitmask that can be seen as a set of 32 potential integers. All you need is to enumerate all bits from right to left, starting from zero and provide the necessary bitwise operations. Like this, if the N-th bit is turned on, then your set is said to contain an integer value N.

Let MASK_LOW encode the decimal 31 value which is the max shift we can take in the range of 32 bits available for a single integer value. Each value that’s gonna be stored in the packed map is low-masked first so that we are sure not to violate the boundary constraint.

1 & MASK_LOW = 1
2 & MASK_LOW = 2
...
31 & MASK_LOW = 31
32 & MASK_LOW = 0
33 & MASK_LOW = 1
...

It's pretty obvious that one integer is not enough. Actually, with low-masking alone, we won’t be able to distinguish 1 from 32, 2 from 33 and so on. Therefore, this whole principle should be extended somehow dynamically, and that is something we can easily do. Take the number 33 as an example in its binary representation:

1 0 0 0 0 1

If we right-shift this value by 5 bitwise positions (and 5 is the length of our low mask), we get the value of 1 in the decimal system. The same applies to all numbers up to 1 1 1 1 1 1 which is the decimal 63. So this shifting by 5 bitwise positions gives as the index of a bucket in the map. And we can have as many buckets as we want, because they are all going to be allocated from the heap memory.

But memory is less of a problem for the feature recognition scenarios. Why we use PMOI is basically because it provides set theory logical operators: unite, difference and intersection.

Debugging considerations

There are pros and cons to using non-standard collections, of course. One advantage exploited by Analysis Situs is the compatibility of PMOI with the OCAF framework. The packed map has got a standard attribute in there, so we don't have to extend the OCAF framework of OpenCascade, which is good news by itself. The drawback, however, is that such a custom type is clearly a foreigner to your IDE and debugger. As a result, you could not benefit from handy embedded "watchers" in debugging sessions. How would you know which indices are held within your packed map while standing on a breakpoint in a tedious debugging session?

In what follows, asiAlgo_Feature is the type definition alias for TColStd_PackedMapOfInteger.

The utilization of conventional watching toolkit, such as .natvis files is hopeless since we have to decode the bitmask, and that does not look manageable with declarative XML-ish approaches proposed by Visual Studio.

What we can do, though, is we can develop a specific function to dump the contents of a packed map in the debugging console and then invoke that function right from within the debugging session. Consider the following chunk of code:

class asiAlgo
{
  inline void Dump(const asiAlgo_Feature& feature)
  {
    for ( asiAlgo_Feature::Iterator fit(feature); fit.More(); fit.Next() )
      std::cout << fit.Key() << " ";
    std::cout << std::endl;
  }
}

This code is a bit problematic though. Since we have an inline function, the chances are the compiler is going to "optimize" that function simply by wiping it out from the built library. To not allow the compiler doing that, we have to expose symbols in the corresponding dynamic library, so that this function becomes part of our module's API. We can use printing to OutputDebugStringW to see the diagnostic dump right in the Command Window of Visual Studio:

void asiAlgo::Dump(const asiAlgo_Feature& feature)
{
  std::wostringstream sstream;
  
  for ( asiAlgo_Feature::Iterator fit(feature); fit.More(); fit.Next() )
    sstream << fit.Key() << " ";
  
  sstream << std::endl;
  
  // Dump the debug (Windows-only) and standard outputs.
#ifdef _WIN32
  OutputDebugStringW( sstream.str().c_str() );
#endif
  std::cout << sstream.str().c_str();
}

To take advantage of this function, call the following line from your debugging terminal while standing on a breakpoint (we assume that there is a variable named feature of PMOI type that you want to inspect):

> ? ({,,asiAlgo.dll}asiAlgo::Dump)(feature)