./features/Euler operators
Download Features Source code Terminology References

Introduction to Euler operators

Euler operators allow for atomic modification of a B-Rep model in a manner that keeps the following equation (known as Euler-Poincare formula) satisfied:

v - e + f = 2(s - h) + r

Here v is the number of vertices, e is the number of edges, f is the number of faces, s is the number of shells, h is the genus of the manifold, and r is the number of internal loops.

The very clear introduction to the concept of Euler operators can be found in the paper by [Mantyla and Sulonen, 1982] describing a test solid modeling system named Geometric Workbench (GWB). This system employed Euler operators to let the user incrementally create and modify shapes. M. Mantyla, the author of GWB, has also authored a comprehensive textbook on solid modeling [Mantyla, 1987] which gives a brilliant introduction to the solid modeling field in a truly scientific way.

There are two kinds of Euler operators:

The M-operators allow to create boundary elements, while the K-operators allow to eliminate them. The important practical property of those operators is that they preserve the topological consistency of a B-Rep model.

"In a formal sense, Euler operators form a sufficient set of solid definition and manipulation operatios. Even so, a solid modeler must include more user-oriented ways to create and handle solid models. Euler operators themselves are rather unintuitive and primitive and should not be directly visible to the end user. Nevertheless, it is advantageous to use them as primitives of higher-level operations to ensure that the models created are well formed." [Mantyla and Sulonen, 1982]

Informally speaking, Euler operators are like assembler language for B-Rep. The real modeling system should rely on them as much as possible. At the same time, the software system should keep Euler operators in the "engine room" to be more user-oriented.

Check Euler-Poincare property

To check if the Euler-Poincare property holds for the working part, use the check-euler command in Analysis Situs. You will have to specify the genus (i.e. the number of through holes) of your model. If no genus is passed in the Tcl command, a GUI prompt will appear to type it. The following image illustrates a simple shape with genus 0 for which the Euler-Poincare property holds.

Once KEV operator is done for a corner vertex, we can make sure that the topological consistency of the model is preserved.

At the same time, the model is not geometrically valid anymore. Euler operators ensure only the topological (i.e., "syntactical") integrity of the boundary representation.

KEF

KEF stand for "kill-edge-face". This operator is used to collapse two-edged face into a single edge. One application for this operator is blend suppression where two-edged faces may emerge as a result of suppressing cross-edges (you can find more information about this blend suppression technique in a remarkable work by [Venkataraman et al, 2002]).

KEF Euler operator is based on Topology Killer whose function is to remove the face and either remove or merge edges. Edge merging should be preferred in solid modeling cases as this strategy of edge elimination does not break sharing. The following image illustrates a naked edge which emerged as a result of edge removal.

In contrast, if edge merging is used, sharing is preserved at the data structure level.

Analysis Situs takes care not only to preserve sharing but also to ensure the correct propagation of edges' orientations. Since there is no guarantee that the substituted edge has the same geometric orientation as its pre-image in the UV space of a face, the orientation of image can be different from the original orientation.