Skip to content

TopoShape Cache

Jump to bottom
Zheng, Lei edited this page Dec 12, 2023 · 1 revision

TopoShape Cache Implementation Notes

Motivation

The implementation of the new topological naming adds into Part::TopoShape a bidirectional map from text based element names into the conventional indexed based names. The text based element name is generated based on the shape history which makes is stable and relatively immune to topological changes. At the same time, the name can be decoded to trace into the history to make it possible to auto correct missing shape element reference due to model changes. However, this requires us to always generate the element naming map when extracting sub-elements from any TopoShape instance. This will inevidently cause slow down considering the frequency of sub-element extraction in normal system activities, most of which can be avoided because no element name referencing is required. This motivate us to find a way to delay the element map generation until it is actually required and to reuse the generated map in case of repeated future use.

OpenCasCade Details

OpenCasCade Technology (OCCT), the CAD kernel used by FreeCAD, represents a topological shape using class TopoDS_Shape with dynamic typing. Quote from OCCT document,

Identifies various topological shapes. This enumeration allows you to use dynamic typing of shapes. The values are listed in order of complexity, from the most complex to the most simple i.e. COMPOUND > COMPSOLID > SOLID > .... > VERTEX > SHAPE. Any shape can contain simpler shapes in its definition. Abstract topological data structure describes a basic entity, the shape (present in this enumeration as the SHAPE value), which can be divided into the following component topologies:

  • COMPOUND: A group of any of the shapes below.
  • COMPSOLID: A set of solids connected by their faces. This expands the notions of WIRE and SHELL to solids.
  • SOLID: A part of 3D space bounded by shells.
  • SHELL: A set of faces connected by some of the edges of their wire boundaries. A shell can be open or closed.
  • FACE: Part of a plane (in 2D geometry) or a surface (in 3D geometry) bounded by a closed wire. Its geometry is constrained (trimmed) by contours.
  • WIRE: A sequence of edges connected by their vertices. It can be open or closed depending on whether the edges are linked or not.
  • EDGE: A single dimensional shape corresponding to a curve, and bound by a vertex at each extremity.
  • VERTEX: A zero-dimensional shape corresponding to a point in geometry.

OCCT provides API to enumerate lower hierarchy shapes given its ancestor shape and vise versa. It also offers bidirectionally mapping API from a TopoDS_Shape to an integer index in its ancestor shape. The index is stable as long as the ancestor shape does not change. Here we need some internal knowledge of TopoDS_Shape before we dive into the details of FreeCAD TopoShape cache implementation. TopoDS_Shape is a light weight class having only three members

// geometry data, shared by reference counting
Handle(TopoDS_TShape) myTShape;

// Location of the shape
TopLoc_Location myLocation;

// Orientation of the shape, ignored when doing shape mapping
TopAbs_Orientation myOrient;

OCCT shape mapping relies on hashing of the pointer (instead of the value) of myTShape and the value of myLocation. TopLoc_Location (myLocation) is implemented as a linked list of nodes containing an elementary transformation (TopLoc_Datum3D, basically a reference counted gp_Trsf) and powers of the transformation (i.e. how many times the transformation is to be applied or reversed if negative). The list storing a series of transformations mirrors the hierarchical structure of sub-shapes forming more complex shape. The reason to preserve this hierarchy using a list is most likely for the sake of numerical stability. For example, extracting the same elementary shape in different hierarchy can be achieved by appending or stripping nodes in the list instead of matrix operation. The hashing of TopLoc_Location is done by combining hashes of all list nodes.

Note that this list of transformations concept has no equivalence in FreeCAD where the location is normally stored in a single Base::Placement which is a flattened accumulation of all transformations. In order for OCCT shape mapping to work, for example, say given a face and try to find out its index in a solid, the face must contain the original list of transformations (i.e. TopLoc_Location). Any changes to the location in either the face or the solid will cause the mapping to fail even if the effective transformations are identical.

Implementation

An internal cache is added to TopoShape to achieve the following goals,

  • Delay element map generation for sub-element shapes
  • Avoid repetitive element map generation
  • Minimize cache invalidate on shape location change

The cache information is captured by three private members of TopoShape

// Cache for this TopoShape
std::shared_ptr<Cache> _Cache;

// Cache for the top ancester TopoShape.
std::shared_ptr<Cache> _ParentCache;

// shape location accumulated from the top ancester till the immediate parent of this TopoShape
TopLoc_Location _SubLocation;

where Cache is a private class holding the actual caching content. Its simplified definition is listed below,

class Cache {
    // Reference counted element map for the owner TopoShape. The ElementMap of
    // a TopoShape is normally accessed through the inherited member function
    // ComplexGeoData::elementMap(). The extra shared pointer here is so that
    // other TopoShape instances with the same Cache can resuse the map once
    // generated.
    ElementMapPtr cachedElementMap;

    // Location of the original cached TopoDS_Shape.
    TopLoc_Location subLocation;
    
    // The cached TopoDS_Shape stripped off any location (i.e. a null TopoDS_Shape::myLocation).
    TopoDS_Shape shape;

    // Location (and the inverted location) of the last ancester shape used to
    // find this TopoShape. These two members are used to avoid repetitive
    // inverting the location of the same ancestor
    TopLoc_Location loc;
    TopLoc_Location locInv;

    // Class for caching the ancestor and children shapes mapping
    class Info {
        // OCCT map from the owner TopoShape to a list of children (i.e. lower hierarchical) TopoDS_Shape
        TopTools_IndexedMapOfShape shapes;

        // One to one corresponding TopoShape to each child TopoDS_Shape
        std::vector<TopoShape> topoShapes;

        // Caches the OCCT ancester shape maps, e.g.
        // Cache::infos[TopAbs_FACE].ancestors[TopAbs_EDGE] stores an OCCT
        // TopTools_IndexedDataMapOfShapeListOfShape that can return a list of
        // faces containing a given edge.
        std::array<AncestorInfo, TopAbs_SHAPE+1> ancestors;
    };

    // Ancestor and children shape caches of all shape types. Note that
    // infos[TopAbs_SHAPE] is also valid and stores the direct children of a
    // compound shape
    std::array<Info,TopAbs_SHAPE+1> infos;
};

To avoid cache rebuilt as much as possible, Cache stores the caching TopoDS_Shape with its location stripped so that the cache remains valid when the owner TopoShape is moved. When accessing its sub shapes, the sub shape location is re-constructed using the location in the owner TopoShape. The sub shape cache Cache::infos is initialized on demand through Cache::getInfo(sub_shape_type). The actual sub shape is accessed by calling Cache::Info::_getTopoShape(parent, index) which returns the sub shape in the form of a TopoShape instance (constructed on demand) with all caching structure initialized. For example, calling Cache::infos[TopAbs_FACE]._getTopoShape(parent_shape, 1) will return a TopoShape containing Face1 of parent_shape. The returned TopoShape will hold a reference in TopoShape::_ParentCache pointing towards the cache of the top ancestor shape. The element map will be generated on demand in TopoShape::flushElementMap() by calling TopoShape::mapSubElement().

Please note that the notion of top ancestor shape here is not in the sense of geometry modeling. It is defined as the last shape in the hierarchy (starting from the current shape counting upwards) that has a fully expanded element map. Once a sub shape has expanded the element map, it will reset its _ParentCache and become the top ancestor of its child shapes that are yet to expand its element map.

Clone this wiki locally