euler

Introduction

This is a C++ reimplementation of the Euler operators in the Geometric WorkBench as described in Martti Mantyla's book

An Introduction to Solid Modeling

The Euler operators implemented include

1. mvfs (make edge, face and shell: generate skeletal topology of a genus 0 B-rep)
2. mev (make edge and vertex: vertex splitting)
3. mef (make edge and face: face cutting)
4. kemr (kill edge and make ring: converting a simple face to a face with hole),
5. kfmrh (kill face, and make ring and hole: connected sum)
6. kffmh (kill face and face, and make hole: connected sum)

and their inverse operators.

The high level operations include,

1. arc and circle (a lamina disk) generation
2. translational sweep of a face
3. rotational sweep of a wire
4. rotational sweep of a face

An output routine is provided for saving the B-rep of the constructed solid model as an OFF file.

Source code is downloadable at the end of this page after some background introduction of the Euler operators.

About kffmh

The last Euler operator, kffmh, is my understanding of the topological connected sum (it could be in the Euler operator set of some sources other than Mantyla's book). The operator also allows simpler implementation of rotational sweeping of a lamina (instead of a wire). Furthermore, gluing operation is straightforward using kffmh.

About Plane Models of Closed Orientable 2-Manifolds

1. Cells
   1. 0-cell is a point
   2. 1-cell is an arc
   3. 2-cell is a disk
   4. ...
2. Cell complex: a set of various dimensional cells, with cells attached to boundaries of lower dimensional cells.

3. Plane models are essentially cell complex with some restrictions,
   1. only 0, 1 and 2 dimensional cells; they are called vertices, edges, and faces, respectively.
   2. an annulus is acceptable as a valid building block, therefore the inner loops of faces.
   3. closed manifold guarantee:
      • one edge is identified exactly with another edge, therefore the neighborhood at any edge interior point is an open *disk*
        • The pair of edges to be identified always belong to certain (possible the same) face, each of the pair is justifiably called half edge; further, each half edges inherits the orientation from its hosting face.
      • sectors adjacent to an identified vertex connect perfectly into a disk, therefore neighborhood of vertex is again an open *disk*.
   4. orientable manifold guarantee.
      • every face interior is to the right (or to the left, so long as consistent) of the its boundary orientation; equivalently, the identified pair of (half) edges has to be of opposite orientation.
   5. an implicit convention:
      • sometimes it is assumed that there is another far away boundary polygon surrounding the outer boundary polygon, forming a topological annulus; however, it is really considered to be an open disk as the imaginary boundary is assumed to be identified (collapsed into) to a point (see example below).

   In summary, a plane model in 2-space is homeomorphic to an orientable closed 2-manifold in 3-space, under the following 3 restrictions,

   1. edge identification
   2. cyclical identification
   3. orientability

4. An example: plane model of a cube.
   • Notice that faces are always to the right of their oriented boundaries.
   • Notice also that we do not merge pairs of edges, with opposite directions, into simple edges. It turns out that pairs of oppositely oriented (half) edges are more natural than the usual (full) edges, in the topological sense of cell decomposition and boundary (of open cells) identification. Computationally, this translates into the fact that half edge data structure is better than winged edge data structure.
   

5. Another example: skeletal model of a sphere (or any genus 0 closed orientable 2-manifold)
   • Notice that the dotted circle minus the vertex is topologically an open disk, under the assumption that the dotted circle is collapsed to one point.
   

Euler Operators

1. Initialize the skeletal topology of a genus 0 closed orientable 2-manifold (mvfs). See the above image for an illustration.

2. Edge cycle subdivision (mev).
   
   Notice that [e1, e2) could be zero range (i.e., e1 = e2).

3. Edge loop subdivision (mef).
   
   Notice that [e1, e2) could be zero range (i.e., e1 = e2).

4. Face topological change: annulus to disk (kemr). *
   

5. Global topological change: connected sum.
   1. kill a simple face, make its boundary to be an inner loop of another face.
   2. if both faces are from the same shell, the net effect is kill a face, make a ring and a hole, i.e., kfmrh.
   3. if each face is from a different shell, the net effect is kill a face and a shell, make a ring, i.e., kfsmr.

Notice that each operator above has its inverse.

Minimal Euler Operator Set and Minimal Euler Operations

Edge cycle (at a vertex) subdivision and edge loop (at a face) subdivision are 2 fundamental manipulation on plane models of oriented closed 2-manifolds. As annulus are allowed in the data structure (inner loops), one more essential operation is required to convert from a disk to an annulus. Finally, global topology may be changed by connected sum. Of course, to start with all these operations, a skeletal topology has to be initialized. Putting all these together, we have 5 basic Euler operators namely

mev, mef, kemr, kfmrh , and mvfs,

in the aforementioned order.

Given any tuple (v, e, f, r, h, s=1), denoting the number of vertices, edges, faces, rings (inner loops), holes, and shells (connected components) of a solid model ( with only one connected component ), the minimal (non-minimal situation could arise, because each operator has its inverse which undoes the result) operations needed to construct the solid can be derived as follow,

1. (1) mvfs, as this is the only operator modifying shell number.
2. (h) kfmrh, as this is the only operator modifying hole number.
3. (f+h-1) mef, as mvfs, kfmrh, and mef are the only operators modifying face number, and the first two have already been done.
4. (v-1) mev, as mvfs (done already), and mev are the only operators modifying vertex number.
5. (r-h) kemr, as kfmrh (done already) and kemr are the only operators modifying ring number.

Notice that the edge number from the above optimal construction is automatically right by the euler equation

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

A more formal derivation can be given by considering all topologically valid solid models as a hyper plane in the 6-space of (v,e, f, r, h, s) and taking the five essential Euler operators, plus the plane normal, as a basis of the 6-space. The coordinates, under this basis, of any 6-tuple, then gives the minimal operations required to construct a solid model with the given 6-tuple as its topological specification.

Download

download

Installation

In unix environment, type

 make test-file-name 

to compile a test program named test-file-name (the name has to start with 'test')

---