euler.h

Go to the documentation of this file.

/**
 *\file         euler.h
 *
 *\brief        Include all head files defining node types in euler.
 *
 *              They are solid, face, loop, edge, and vertex nodes.
 *
 *              Some significant change from the original Geometric WorkBench as 
 *              presented by Martti Mantyla as in "An Introduction to Solid Modeling".
 *
 *              0. First, this is a C++ implementation. And as such, it comes with      
 *                 many advantages; among them, most obviously, are the simpler and     
 *                 cleaner codes for node creation and deletion, including the proper   
 *                 link update.                                                         
 *                                                                                      
 *              1. From a *pure perspective* of topological plane model of a closed     
 *                 2-manifold, there are actually no such things as edges, instead,     
 *                 there are only half edges, with the condition each is identified to  
 *                 exactly another one. Therefore, there is no edge nodes in my         
 *                 design. The identification is archived by storing the opposite half  
 *                 edge in the half edge node (member o).                               
 *                                                                                      
 *              2. All half edges, including circular edge (end points coincident), have
 *                 their opposite halves, except singular half edge, i.e., of zero length,
 *                 which has nil as its opposite half edge link.
 * 
 *              3. Because there are only half edges, we simple use edge_t to denote the 
 *                 actually half edge type.
 *
 *\author       Xianming Chen\n
 *              Computer Science Department\n
 *              University of Utah
 *
 *\date         14 Aug 2006\n
 *              Copyright (c) 2006, University of Utah
 */


#ifndef _EULER_H
#define _EULER_H


#include "solid.h"
#include "face.h"
#include "loop.h"
#include "edge.h"
#include "vertex.h"



/*! \mainpage  euler
 *
 * \section intro_sec Introduction
 *
 * This is a C++ reimplementation of the Euler operators
 * in the Geometric WorkBench as described in Martti Mantyla's book
 *
 *  <em> An Introduction to Solid Modeling</em>
 *
 * The Euler operators implemented include 
 *
 * <OL type = '1'>
 * <LI> \em mvfs (<small>make edge, face and shell</small>: generate skeletal topology of a genus 0 B-rep)
 * <LI> \em mev (<small>make edge and vertex</small>: vertex splitting)
 * <LI> \em mef (<small>make edge and face</small>: face cutting)
 * <LI> \em kemr (<small>kill edge and make ring</small>: converting a simple face to a face with hole),
 * <LI> \em kfmrh (<small>kill face, and make ring and hole</small>: connected sum)
 * <LI> \em kffmh (<small>kill face and face, and make hole</small>: connected sum)
 * </OL>
 * and their inverse operators.
 *
 * The high level operations include,
 *
 * <OL type = '1'>
 * <LI> arc and circle (a lamina disk) generation
 * <LI> translational sweep of a face
 * <LI> rotational sweep of a wire
 * <LI> rotational sweep of a face
 * </OL>
 *
 * 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.
 *
 * \section kffmh_sec About kffmh
 *
 * The last Euler operator, \em 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 \em lamina (instead of a \em wire).
 * Furthermore, gluing operation is straightforward using \em kffmh. 
 *
 * \section tutorial_sec  About Plane Models of Closed Orientable 2-Manifolds
 * <OL TYPE="1">
 * <LI> Cells
 *   <OL TYPE="a">
 *   <LI> 0-cell is a point
 *   <LI> 1-cell is an arc
 *   <LI> 2-cell is a disk
 *   <LI> ...
 *   </OL> 
 * <LI> Cell complex: a set of various dimensional cells, with cells attached to boundaries of lower dimensional cells.
 *
 * <LI> Plane models are essentially cell complex with some restrictions,
 *   <OL TYPE="a">
 *   <LI> only 0, 1 and 2 dimensional cells; they are called vertices, edges, and faces, respectively.
 *   <LI> an annulus is acceptable as a valid building block, therefore the inner loops of faces.
 *   <LI> closed manifold guarantee: 
 *      <UL type="i">
 *      <LI> one edge is identified exactly with another edge, therefore the neighborhood at any edge interior point is an open *disk*
 *          <UL>
 *          <LI> 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. 
 *          </UL>
 *      <LI> sectors adjacent to an identified vertex connect perfectly into a disk, therefore neighborhood of vertex is again an open *disk*.
 *      </UL>
 *   <LI> orientable manifold guarantee.
 *      <UL>
 *      <LI> 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.
 *      </UL>
 *   <LI> an implicit convention: 
 *      <UL>
 *      <LI> 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).
 *      </UL>
 *   </OL>
 *
 *  In summary, a plane model in \em 2-space is homeomorphic to an orientable closed 2-manifold in \em 3-space, under the following 3 restrictions,
 *  <OL type='a'>
 *  <LI> edge identification
 *  <LI> cyclical identification
 *  <LI> orientability 
 *  </OL>
 *
 *
 * <LI> An example: plane model of a cube. 
 *      <UL type="a">
 *      <LI> Notice that faces are always to the right of their oriented boundaries.
 *      <LI> Notice also that we do not merge pairs of edges, with opposite directions, into simple edges. It turns out that  pairs of <em>oppositely oriented</em> (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.
 *      </UL>
 * \image html plane-model-of-cube.jpg
 *
 *
 *
 * <LI> Another example: skeletal model of a sphere (or any genus 0 closed orientable 2-manifold)
 *      <UL>
 *      <LI> 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.
 *      </UL>
 * \image html skeletal.jpg
 * </OL>
 *
 *
 *
 * \section euler_operators_sec  Euler Operators
 *    <OL type='1'>
 *    <LI> Initialize the skeletal topology of a genus 0 closed orientable 2-manifold (\em mvfs). See the above image for an illustration.
 *
 *    <LI> Edge cycle subdivision (\em mev).
 *
 *    \image html subdivide-cycle.jpg
 *    Notice that [e1, e2) could be zero range (i.e., e1 = e2).
 *
 *
 *    <LI> Edge loop subdivision (\em mef).
 *
 *    \image html subdivide-edge-loop.jpg
 *    Notice that [e1, e2) could be zero range (i.e., e1 = e2).
 *
 *
 *    <LI> Face topological change: annulus to disk (\em kemr).
 * *    \image html kemr.jpg
 *
 *    <LI> Global topological change: connected sum.
 *         <OL type = 'a'>
 *         <LI>kill a simple face, make its boundary to be an inner loop of another face.
 *         <LI>if both faces are from the same shell, the net effect is kill a face, make a ring and a hole, i.e., kfmrh.
 *         <LI>if each face is from a different shell, the net effect is kill a face and a shell, make a ring, i.e., kfsmr.
 *         </OL>
 *    </OL>
 *
 *  Notice that each operator above has its inverse.
 *
 * \section minimal_operations_sec  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 (\em inner \em 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
 *
 * <em> mev, mef, kemr, kfmrh </em>, and \em 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 (<em> with only one connected component </em>), 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,
 * <OL type='1'>
 * <LI> (1) \em mvfs, as this is the only operator modifying shell number.
 * <LI> (h) \em kfmrh, as this is the only operator modifying hole number.
 * <LI> (f+h-1) \em mef, as \em mvfs, \em kfmrh, and \em mef are the only operators modifying face number, and the first two have already been done.
 * <LI> (v-1) \em mev, as \em mvfs (done already), and \em mev are the only operators modifying vertex number.
 * <LI> (r-h) \em kemr, as \em kfmrh (done already) and \em kemr are the only operators modifying ring number.
 * </OL>
 *
 * Notice that the edge number from the above optimal construction is automatically right by the euler equation
 *
 * <em> v - e + f = 2(s-h) + r. </em>
 *
 *
 * 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.
 *
 *
 *
 *
 * \section download_sec Download
 *
 * <a href="euler.tar">download</a>
 *
 *
 *
 * \section install_sec Installation
 *
 * In unix environment, type 
 *
 *      \code make test-file-name \endcode 
 *
 * to compile a test program named test-file-name (the name has to start with 'test')
 * 
 * 
 *
 *  
 */



#endif

---