Misplaced Pages

Euler operator (digital geometry)

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (July 2021) (Learn how and when to remove this message)
This article may require cleanup to meet Misplaced Pages's quality standards. The specific problem is: multiple dead refs - prune or replace with working ref. Please help improve this article if you can. (July 2021) (Learn how and when to remove this message)
(Learn how and when to remove this message)

In solid modeling and computer-aided design, the Euler operators modify the graph of connections to add or remove details of a mesh while preserving its topology. They are named by Baumgart after the Euler–Poincaré characteristic. He chose a set of operators sufficient to create useful meshes, some lose information and so are not invertible.

The boundary representation for a solid object, its surface, is a polygon mesh of vertices, edges and faces. Its topology is captured by the graph of the connections between faces. A given mesh may actually contain multiple unconnected shells (or bodies); each body may be partitioned into multiple connected components each defined by their edge loop boundary. To represent a hollow object, the inside and outside surfaces are separate shells.

Let the number of vertices be V, edges be E, faces be F, components H, shells S, and let the genus be G (S and G correspond to the b0 and b2 Betti numbers respectively). Then, to denote a meaningful geometric object, the mesh must satisfy the generalized Euler–Poincaré formula 

 V – E + F = H + 2 * (S – G)

The Euler operators preserve this characteristic. The Eastman paper lists the following basic operators, and their effects on the various terms:

Name Description ΔV ΔE ΔF ΔH ΔS ΔG
MBFLV Make Body-Face-Loop-Vertex +1 +1 +1
MEV Make Edge-Vertex +1 +1
MEFL Make Edge-Face-Loop +1 +1
MEKL Make Edge, Kill Loop +1 −1
KFLEVB Kill Faces-Loops-Edges-Vertices-Body −2 −n −n −1
KFLEVMG Kill Faces-Loops-Edges-Vertices, Make Genus −2 −n −n +1

Geometry

Euler operators modify the mesh's graph creating or removing faces, edges and vertices according to simple rules while preserving the overall topology thus maintaining a valid boundary (i.e. not introducing holes). The operators themselves don't define how geometric or graphical attributes map to the new graph: e.g. position, gradient, uv texture coordinate, these will depend on the particular implementation.

See also

  • Boundary representation
  • Lecture 31 of AML710 Computer Aided Design – Dr S. Hegde of Indian Institute of Technology Delhi

References

  1. Baumgart, B.G^ "Winged edge polyhedron representation", Stanford Artificial Intelligence Report No. CS-320, October, 1972.
Categories: