Архивы

It should be already evident for all readers of the Manifold Geometry that OpenCascade implements boundary representation scheme for surface and solid modeling. The kernel allows for precise construction of curved shapes thanks to the powerful data structure composed of pure topological and geometric primitives. While handling the geometry is usually a well-understood practice, the topological skeleton of a model is sometimes tricky to manage due to the misunderstanding of the basic conception. Let's recap the fundamentals of B-Rep in OpenCascade and then discuss how to manage it.

— ... when it comes to topology, things become quite messy. It is always a challenge to develop a reliable modeling algorithm without falling down to crappy spaghetti code which no one can understand and maintain.
— It is good to hear you say that. I always feel stupid after a few hours of OpenCascade programming.

(conversation at FreeCAD forum)

The distinguishing between Topology and Geometry is one of the earliest principles of CAD modeling which emerged decades ago. The Geometry defines the mathematics of shape, e.g., the parametric equation of a surface. The Topology, on the other hand, describes the relationship between the pieces of geometry by structuring them into a simply connected two-manifold. Formally speaking, the Topology of a boundary representation defines the syntax of the model materialized in the computer memory as an oriented graph. The nodes of this graph are the topological entities which may have or not the associated geometric primitives. The Geometry in its turn injects the semantics into the structure of a model. The Topology is the skeleton, and the Geometry is the meat.

The Topology of B-Rep model is an oriented graph.

In the OpenCascade kernel, the separation between Topology and Geometry is fully exposed to the library users. For example, TopoDS_Face object is a topological element holding an internal reference to the parametric surface subclassing the generic Geom_Surface type. The package names (TopoDS and Geom in that case) are self-explanatory: the former stands for the Topology [Data Structure] and the latter — for the Geometry. These two concepts are so isolated that even to extract a surface from a face, you have to use dedicated extra tools:

Handle(Geom_Surface) surf = BRep_Tool::Surface(face);

Other geometric kernels (like ACIS or Parasolid) may not be so restrictive about the isolation of Topology and Geometry, but those two levels of abstraction are always present. In fact, it was a perfect idea to put the syntax of the model apart from its semantics as such a design gives some helpful implications. Many algorithms can benefit from such separation to avoid time-consuming and unreliable geometry analysis by exploiting the topological relations alone.

Another well-turned idea in the topology design was to introduce not only the topological entities themselves but also their occurrences in the model. For example, to represent an edge between two faces, you allocate a couple of edge occurrences pointing to the same 3D curve while having opposite orientations. Such occurrences are named coedges. The understanding of the OpenCascade's Topology starts from familiarizing with this Object/CoObject dualism.

CoObjects instantiate Objects while Objects include CoObjects. The relation of instancing allows for B-Rep sharing. The relation of inclusion shapes the topology graph.

Neither Objects nor CoObjects are aware of their parent elements. The absence of the link to the parent entity has its pros and cons. The positive side here is the minimalism of the data structure which is not a bad thing itself. On the other hand, there is a severe implication for all use cases which require local topology analysis. Having no link from an edge to its owning loop or a face, you are obliged to traverse the topology graph from its root or to cache the once found relations somehow. While the first approach with a full traverse suffers from the computational inefficiency, the second approach with caching is an awful practice which often leads to trashing tons of hours on maintenance and development. It is likely that in 90-ties the minimalistic design was a preferred way for expressing the topology elements within a CAD kernel operating on limited hardware. But... the conciseness does not come for free. In the new reality where the direct modeling paradigm pounces the market, the local editing operators have become a must-have feature. If your local operator requires a global topology traversal, is that a truly Local one? If you instead cache your topology for fast access, won't you get crazy to maintain your caches consistently because they will become a more abundant reflection of your minimalistic B-Rep? The answer is easy: do not be minimalistic. Take a look at C3D for example where you can easily take the owner objects from your CoObjects. Just recall this small hint if you will ever go for your own geometric kernel: Do Not Be Minimalistic.

Once you've got a well-formed boundary representation, a question on how to modify it arises. Well, most people treat the geometric kernel as a black box which should only serve the input requests doing what is asked by the user. Fortunately or not, we are not in the condition when you may simply take things for granted. The OpenCascade kernel is the open-sourced product which allows for taking out its hidden details and making them clear by the investigation. Then, like it or not, OpenCascade falls decades behind its commercial alternatives in terms of features. For example, there are no Euler operators, direct editing tools, local operators or advanced surface morphing facilities. Instead of judging this apparent incompleteness strictly, we'd rather accept the things as they are and remain grateful to the French software developers for publishing their work at some point. This was a real scholarly contribution with a significant impact on advancing the digital engineering field. However, let's get back to the cornerstone question of shape editing.

From the perspective of shape editing, there are two sorts of modeling operators: those which modify the Topology of the model and those which do not. The operators which keep the Topology unaffected are relatively easy to implement as you (the developer) should only care of the geometric primitives and their consistency. To put it simply, whenever modifying the host geometries of the edges and faces, make sure to avoid gaps and keep synchronous parameterization of your 3D curves and their UV images. Because the Topology of the model remains intact, you cannot break the syntax of the model in the pure geometric operators. The shared edges will remain physically shared in the computer memory even if you hapen to destroy them geometrically completely. That's a good property, but not many algorithms actually preserve the Topology. To name a few, it can be a face tweaking operator (move or rotate a selected face a bit), rehosting operator (change a surface of a face), simple offsets (without reintersections), draft angle, etc. Applying such operators does not lead to creating new or eliminating existing features. In essence, these operators are the homeomorphisms of the model.

Draft Angle is an example of Topology-preserving operator.

In contrast, the operators changing the Topology do affect the structure of a CAD model. Formally speaking, applying such operators affects the topology graph. And here another classification comes out. It appears that some Topology-affecting operators can be fully conducted on the topology graph without even touching geometry. Imagine removal of an interior hole in the part. To accomplish such modification, you only need to cut out the corresponding boundary elements from the topology graph and voila!

Removal of a through cylindrical hole is nothing but cutting out the face F with its loops W1, W2 and all underlying topological elements from the topology graph.

The Topology-only operators tend to be the simplest possible modeling algorithms, much simpler than the homeomorphisms discussed above. Indeed, such operators work with the data structure which does not contain any inaccuracies due to approximation or lossy data exchange. And the work itself is computation-free in the sense that it does not employ any computational geometry at all. Simple and perfect. However, most general operators (like Booleans) employ working at both levels of the boundary representation: Topology and Geometry. And that is the most difficult thing from the developer's and the architect's (there is always some architecture in a well-engineered algorithm) points of view.

The fundamental question for the algorithms dealing with the Topology is how to identify a specific boundary element such as the face, edge or vertex. The problem looks like nothing but becomes more complicated once you start practicing. There are three approaches to the identification of a topological element:

1. By it's transient (memory) pointer.
2. By it's numerical ID.
3. By it's name.

Only the memory pointers (the first approach) are available for no additional efforts. These pointers are simply the addresses of the corresponding shared entities in the heap memory (recall the Object/CoObject dualism). Most of the algorithms ever written with the use of OpenCascade operate with those transient IDs as this is the straightforward way of referencing the CAD model's elements. The only drawback of this approach is also self-evident: it is not persistent. A modeling recipe (called a "history tree" in the feature-based systems) which operates with the transient IDs of a model could not be reevaluated because such reevaluation will create a brand new model with entirely different transient IDs inside. Therefore, it is generally impossible to organize the computation schemes basing on the transient pointers alone: such pointers should first be extracted from a more persistent descriptor. The problem of persistent identification is thoroughly described in a well-known paper by J. Kripac [Kripac, J. 1997. A mechanism for persistently naming topological entities in history-based parametric solid models. Computer-Aided Design 29, 113–122.]. Although in the direct editing scenarios (in contrast to the history-based modeling) the problem of persistent naming is not on the surface, it still arises when the geometric processing stops to be trivial. To drive an automatic computation which employs several intermediate states of your CAD geometry, the algorithm should be able to reliably identify the faces, edges, and vertices of interest, even after these entities are recreated at some point.

The simplest solution to the persistent identification problem is the usage of serial identifiers for the topological primitives. Such identifiers can be associated with the elements of a topology graph by sequentially visiting its nodes and counting them. Although such an approach is persistent in a sense that the indices are not changed after the Topology-preserving reevaluation, such indexing is not stable enough. Indeed, any modification to the Topology of the model (i.e., to the topology graph) makes the previous enumeration invalid. A more "rigid" persistent identifier is necessary. As J. Kripac shows, a rigid persistent identification mechanism can be built on top of the modification history.

Attributed Adjacency Graph with the information on the recognized blend faces (snapshot from Analysis Situs).

To organize computations on a B-Rep shape, some additional data structures such as an Attributed Adjacency Graph (AAG) are found to be useful. The formalism of the graph theory facilitates constructing the mathematical models of geometric operators. It is important, however, to avoid misusing things. For example, an attributed graph may serve as a handy descriptor of a shape which holds additional information about the design or manufacturing features (which can be adequately referenced with the sequential IDs of faces). On the other hand, such extra descriptors are tough to be kept in an up-to-date state as long as a modeling operator unfolds. A descriptor such as an AAG is a knowledge holder for a frozen state of a CAD model. However, the shape editing algorithms are much easier to implement if they work directly with a boundary representation and query all necessary information right from the working body, i.e., without holding the working entities (Objects/CoObjects) in all sorts of caches whose debugging is a nightmare. In essence, a general modeling operator can be seen as a process of discrete transforming the topology graph from one state to another, where the supplementary structures like AAG are beneficial for describing those intermediate states.

There is finally a conclusion which we'd like to share with anybody delving into the low-level OpenCascade. Some points to check are as follows:

• Ask yourself which type of modification are you doing: Topology-only, Geometry-only or mixed?
• Use caches and supplementary structures (such as AAG) with care and only for the frozen state of geometry. Do not allow these structures to substitute your B-Rep and think a lot before attempting to actualize them (just build new ones instead).
• Use transient identifiers of the shape elements as much as possible. Fall back to the persistent IDs only when you have a good reason for doing so.
• Exploit the actual state of B-Rep shape as much as possible. For example, if you need to take faces adjacent to a specific one, ask this geometric question to the shape itself, not to the supplementary structures.

Beware that a well-formed geometric algorithm should be based on a well-shaped idea (ideally, a mathematical model). The architecture of a geometric algorithm means a lot after all.

Want to discuss this? Jump in to our forum.