Euler Operators#

The topological primitives behind blend suppression, and why we use them.

Note

This document is intended for developers working on the shape_editing.euler module. For the algorithm that drives these operators, see Blend Suppression.

Euler Operators#

This document describes the Euler operators introduced in volmdlr_tools.shape_editing.euler. They are the topological foundation of the Blend Suppression algorithm: a small, provably-valid set of primitives for editing the connectivity of a boundary representation while leaving the geometry of the surviving elements untouched.

A good first read on the topic is the Euler Operators notes from Michigan Tech; this document summarizes the parts we rely on and how they map onto our implementation.

Why topological operators at all?#

A boundary representation (BRep) is two things glued together:

  • a topology — the combinatorial structure of which vertices bound which edges, which edges bound which faces, and which faces bound which shells; and

  • a geometry — the actual point, curve and surface that each of those elements carries.

Most edits we want to perform on a CAD model (removing a fillet, collapsing a face) are fundamentally topological edits: the question “which faces now meet at which new edge?” must be answered before “where exactly does that new edge lie in space?”. If you mutate geometry and topology together in one step, it is easy to produce a shell that is no longer closed, an edge shared by three faces, or a face with a self-intersecting boundary — a model the downstream kernel will reject.

Euler operators solve this by guaranteeing that every intermediate model is a valid manifold, purely by construction. The geometry is reconstructed afterwards, in a separate pass (see normalization).

The Euler–Poincaré formula#

For a closed, orientable polyhedral surface the counts of vertices V, edges E, faces F, loops L (face boundaries — outer wire plus any inner wires), shells S and genus G (through-holes / handles) are not independent. They satisfy the Euler–Poincaré formula:

V - E + F - (L - F) - 2(S - G) = 0

For the simplest case — a single closed shell, genus 0, every face with exactly one loop (L = F, S = 1, G = 0) — this reduces to the familiar

V - E + F = 2

which is exactly the invariant the engine checks with EulerEngine.euler_poincare_ok().

An Euler operator is any topological edit that preserves this equation. Because the formula is an invariant of every valid manifold, an edit that keeps the formula balanced cannot turn a valid model into a topologically impossible one. This is the entire reason for working through these operators rather than deleting faces directly.

The make / kill operator pairs#

Euler operators come in complementary make / kill pairs; each “make” adds elements and its “kill” inverse removes them, both keeping the formula balanced. The ones relevant here:

Operator

Δ counts

Effect

MEV make-edge-vertex

V+1, E+1

split a vertex by sprouting a new edge and vertex

MEF make-edge-face

E+1, F+1, L+1

split a face by drawing a new edge across it

MVFS make-vertex-face-shell

V+1, F+1, L+1, S+1

seed a brand-new shell

KEV kill-edge-vertex

V-1, E-1

inverse of MEV — remove an edge and merge a vertex away

KEF kill-edge-face

E-1, F-1, L-1

inverse of MEF — remove a face and one bounding edge

KVFS kill-vertex-face-shell

V-1, F-1, L-1, S-1

inverse of MVFS — delete an isolated shell

Each row leaves V - E + F - (L - F) - 2(S - G) unchanged, so any sequence of them maps a valid manifold to another valid manifold.

The three operators we implement#

Blend suppression needs only the kill side of three operators. They live in volmdlr_tools.shape_editing.euler.operators.EulerEngine:

Kill-edge-vertex (KEV) — engine.kev(edge, vertex_to_kill)#

Removes edge and merges vertex_to_kill into the other endpoint. Every other edge that referenced the killed vertex is rewired onto the survivor. V and E each drop by one; F is unchanged.

This is the workhorse for shrinking away the short edges a blend introduces along its boundary.

Kill-edge-face (KEF) — engine.kef(face, edge_to_kill, edge_to_keep)#

Removes face together with one of its bounding edges, collapsing edge_to_kill into its sibling edge_to_keep and rewiring the neighbouring face onto the survivor. E and F each drop by one.

This is what finally removes the blend face itself: once the blend’s boundary edges have been reduced to a single surviving spring edge, KEF deletes the blend face and welds its two support faces along that edge.

Kill-face-make-vertex (KFMV) — engine.kfmv(face)#

Collapses a whole face down to a single vertex. It is implemented as a loop of KEVs (kill the face’s bounding edges one at a time) followed by removing the now edge-less face. F drops by one and a vertex remains. This is how a vertex blend (the little triangular/spherical patch where three edge blends meet) is suppressed: it has no meaningful surviving edge of its own, so it collapses to the corner point.

The engine: staged application and history#

Two design points make the engine usable for multi-step recipes:

Plan against the original model, apply in stages. Operators record their requests onto a single topological-reduction pass; engine.apply() flushes the accumulated requests at once. The engine keeps a cumulative modification history, so an entity identified on the original model can be re-located to its current image between steps with engine.actualize(sub_shape). This matters because killing one edge renames the vertices and edges around it — the next operator in the recipe must reference the current image, not the stale original.

engine = EulerEngine(solid)
engine.kev(terminating_edge, vertex_to_kill)   # record
engine.apply()                                  # flush + advance history
blend_face_now = engine.actualize(blend_face)   # re-locate across the edit

Stable indexing. Sub-shapes are addressed by a 0-based index (engine.vertex(i), engine.edge(i), engine.face(i)) consistent with the AAG’s face/edge numbering, so a recipe expressed in graph terms maps directly onto kernel entities.

Topology first, geometry second#

The engine performs only the syntactic (topological) transformation. After it runs, the surviving edges still carry their old curves — for example, the spring edge that becomes the new sharp edge still geometrically lies where the blend boundary was. Reconstructing the correct geometry (intersecting the two support surfaces to find the restored sharp edge, re-deriving the corner vertices) is a deliberately separate concern, handled by the normalization pass described in Blend Suppression.

This separation is what keeps each half tractable: the topological half is exact and always valid by the Euler–Poincaré invariant, and the geometric half is a set of well-posed surface/curve intersections that can fail loudly (and trigger a roll-back) without ever having produced a malformed intermediate shell.

See also#

See Also#