lib/cpExtensions/DataStructures/QuadEdge.h

   1 #ifndef __CPEXTENSIONS__DATASTRUCTURES__QUADEDGE__H__
   2 #define __CPEXTENSIONS__DATASTRUCTURES__QUADEDGE__H__
   3
   4 #include <itkLightObject.h>
   5 #include <cpExtensions/DataStructures/QuadEdgeIterators.h>
   6
   7 namespace cpExtensions
   8 {
   9   namespace DataStructures
  10   {
  11     /**
  12      */
  13     template< typename P, typename D, bool IsPrimal = true >
  14     class QuadEdge
  15       : public itk::LightObject
  16     {
  17     public:
  18       typedef QuadEdge                        Self;
  19       typedef itk::LightObject                Superclass;
  20       typedef itk::SmartPointer< Self >       Pointer;
  21       typedef itk::SmartPointer< const Self > ConstPointer;
  22
  23       /// Vertices and faces types
  24       typedef P TPrimalGeometry;
  25       typedef D TDualGeometry;
  26
  27       /**
  28        * Dual type, basically the same type with swapped template
  29        * parameters.
  30        */
  31       typedef QuadEdge< D, P, !IsPrimal > TDual;
  32       typedef Self                        TPrimal;
  33       typedef typename TDual::Pointer     PtrDual;
  34       friend TDual;
  35
  36       /// Iterators
  37       typedef QuadEdgeIterator< TPrimal >           Iterator;
  38       typedef QuadEdgeConstIterator< TPrimal >      ConstIterator;
  39       typedef QuadEdgePointIterator< TPrimal >      PointIterator;
  40       typedef QuadEdgePointConstIterator< TPrimal > PointConstIterator;
  41
  42     public:
  43       itkNewMacro( Self );
  44       itkTypeMacro( QuadEdge, itkLightObject );
  45
  46       cpPluginsExtensionsQEAllIteratorsMacro( Onext );
  47       cpPluginsExtensionsQEAllIteratorsMacro( Lnext );
  48       cpPluginsExtensionsQEAllIteratorsMacro( Rnext );
  49       cpPluginsExtensionsQEAllIteratorsMacro( Dnext );
  50       cpPluginsExtensionsQEAllIteratorsMacro( Oprev );
  51       cpPluginsExtensionsQEAllIteratorsMacro( Lprev );
  52       cpPluginsExtensionsQEAllIteratorsMacro( Rprev );
  53       cpPluginsExtensionsQEAllIteratorsMacro( Dprev );
  54
  55     public:
  56       void CreateRings( );
  57
  58       /// First order access methods
  59       inline TPrimal* GetOnext( )
  60         { return( this->m_Onext ); }
  61       inline TDual* GetRot( )
  62         { return( this->m_Rot ); }
  63       inline const TPrimal* GetOnext( ) const
  64         { return( this->m_Onext ); }
  65       inline const TDual* GetRot( ) const
  66         { return( this->m_Rot ); }
  67
  68       /// First order configuration methods
  69       inline void SetOnext( TPrimal* e )
  70         { this->m_Onext = e; }
  71       inline void SetRot( TDual* e )
  72         { this->m_Rot = e; }
  73
  74       /// Second order accessors: around base rings
  75       inline TPrimal* GetSym( )
  76         { return( this->m_Rot->m_Rot ); }
  77       inline TDual* GetInvRot( )
  78         { return( this->m_Rot->m_Rot->m_Rot ); }
  79
  80       /// Second order accessors: neighboring topology
  81       inline TPrimal* GetLnext( )
  82         { return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot ); }
  83       inline TPrimal* GetRnext( )
  84         { return( this->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot ); }
  85       inline TPrimal* GetDnext( )
  86         { return( this->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot ); }
  87       inline TPrimal* GetOprev( )
  88         { return( this->m_Rot->m_Onext->m_Rot ); }
  89       inline TPrimal* GetLprev( )
  90         { return( this->m_Onext->m_Rot->m_Rot ); }
  91       inline TPrimal* GetRprev( )
  92         { return( this->m_Rot->m_Rot->m_Onext ); }
  93       inline TPrimal* GetDprev( )
  94         {
  95           return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot );
  96         }
  97
  98       /// Second order accessors: around base rings (const versions)
  99       inline const TPrimal* GetSym( ) const
 100         { return( this->m_Rot->m_Rot ); }
 101       inline const TDual* GetInvRot( ) const
 102         { return( this->m_Rot->m_Rot->m_Rot ); }
 103
 104       /// Second order accessors: neighboring topology (const versions)
 105       inline const TPrimal* GetLnext( ) const
 106         { return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot ); }
 107       inline const TPrimal* GetRnext( ) const
 108         { return( this->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot ); }
 109       inline const TPrimal* GetDnext( ) const
 110         { return( this->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot ); }
 111       inline const TPrimal* GetOprev( ) const
 112         { return( this->m_Rot->m_Onext->m_Rot ); }
 113       inline const TPrimal* GetLprev( ) const
 114         { return( this->m_Onext->m_Rot->m_Rot ); }
 115       inline const TPrimal* GetRprev( ) const
 116         { return( this->m_Rot->m_Rot->m_Onext ); }
 117       inline const TPrimal* GetDprev( ) const
 118         {
 119           return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot );
 120         }
 121
 122       /// Get geometry methods
 123       inline P& GetOrigin( )
 124         { return ( this->m_Origin ); }
 125       inline P& GetDestination( )
 126         { return ( this->m_Rot->m_Rot->m_Origin ); }
 127       inline D& GetRight( )
 128         { return ( this->m_Rot->m_Origin ); }
 129       inline D& GetLeft( )
 130         { return ( this->m_Rot->m_Rot->m_Rot->m_Origin ); }
 131
 132       /// Get geometry methods (const versions)
 133       inline const P& GetOrigin( ) const
 134         { return ( this->m_Origin ); }
 135       inline const P& GetDestination( ) const
 136         { return ( this->m_Rot->m_Rot->m_Origin ); }
 137       inline const D& GetRight( ) const
 138         { return ( this->m_Rot->m_Origin ); }
 139       inline const D& GetLeft( ) const
 140         { return ( this->m_Rot->m_Rot->m_Rot->m_Origin ); }
 141
 142       /// Set geometry methods
 143       inline void SetOrigin( const P& v )
 144         { this->m_Origin = v; }
 145       inline void SetDestination( const P& v )
 146         { this->m_Rot->m_Rot->m_Origin = v; }
 147       inline void SetRight( const D& v )
 148         { this->m_Rot->m_Origin = v; }
 149       inline void SetLeft( const D& v )
 150         { this->m_Rot->m_Rot->m_Rot->m_Origin = v; }
 151       inline void UnsetOrigin( )
 152         { this->m_Origin = TPrimal::NoGeometry; }
 153       inline void UnsetDestination( )
 154         { this->m_Rot->m_Rot->m_Origin = TPrimal::NoGeometry; }
 155       inline void UnsetRight( )
 156         { this->m_Rot->m_Origin = TDual::NoGeometry; }
 157       inline void UnsetLeft( )
 158         { this->m_Rot->m_Rot->m_Rot->m_Origin = TDual::NoGeometry; }
 159
 160       /**
 161        * Set the Left( ) of all the edges in the Lnext( ) ring of "this"
 162        * with the same given geometrical information.
 163        * @param  faceGeom Looks at most maxSize edges in the Lnext( ) ring.
 164        * @return Returns true on success. False otherwise.
 165        */
 166       void SetLnextRingGeometry( const D& v );
 167       void UnsetLnextRingGeometry( );
 168
 169       /// Topological queries
 170       inline bool IsIsolated( ) const
 171         { return( this == this->m_Onext ); }
 172       bool IsEdgeInOnextRing( const TPrimal* e ) const;
 173       bool IsEdgeInLnextRing( const TPrimal* e ) const;
 174       unsigned int GetOnextRingSize( ) const;
 175       unsigned int GetLnextRingSize( ) const;
 176
 177       /**
 178        * @return Returns true when "this" has no faces set on both sides.
 179        *         Return false otherwise.
 180        */
 181       inline bool IsWire( )
 182         { return( !( this->IsLeftSet( ) ) && !( this->IsRightSet( ) ) ); }
 183
 184       /**
 185        * @return Returns true when "this" is on the boundary i.e.
 186        *         one and only one of the faces is set. Return false
 187        *         otherwise.
 188        */
 189       inline bool IsAtBorder( ) const;
 190
 191       /**
 192        * @return Returns true when "this" has faces set on both sides.
 193        *         Return false otherwise.
 194        */
 195       inline bool IsInternal( ) const
 196         { return ( this->IsLeftSet( ) && this->IsRightSet( ) ); }
 197
 198       /// Geometrical queries
 199       inline bool IsOriginSet( ) const
 200         { return ( this->m_Origin != Self::NoGeometry ); }
 201       inline bool IsDestinationSet( ) const
 202         { return ( this->m_Rot->m_Rot->IsOriginSet( ) ); }
 203       inline bool IsRightSet( ) const
 204         { return ( this->m_Rot->IsOriginSet( ) ); }
 205       inline bool IsLeftSet( ) const
 206         { return ( this->m_Rot->m_Rot->m_Rot->IsOriginSet( ) ); }
 207
 208       /**
 209        * \brief Check wether edge's Origin is internal to the mesh (as
 210        * opposed to being on the boundary) by looking if all the edges
 211        * in the Onext() ring have a face set on both their Left() and
 212        * Right() side.
 213        */
 214       bool IsOriginInternal( ) const;
 215
 216       /**
 217        * Definition: an edge is said to be a boundary edge when it is
 218        * adjacent to i.e. when at least one of the faces edge->GetLeft() or
 219        * edge->GetRight() is unset.  Definition: an point is said to be a
 220        * boundary point when at least one of the edges of it's Onext() ring
 221        * is a boundary edge.
 222        *
 223        * Assume "this" edge belongs to a triangulation (i.e. it belongs to a
 224        * QEMesh which represents a 2-manifold) which possesses a boundary.
 225        * Assume "this" edge instance is a boundary edge. Let us denote by P
 226        * the point which is the origin of "this" edge i.e. P is
 227        * this->Origin().  By definition P is a boundary point.  Then AT
 228        * LEAST two [see the note below] edges of the Onext() ring of P
 229        * [which all have the point P as Origin()] are themselves boundary
 230        * edges. And among those boundary edges AT LEAST one has it's Left()
 231        * face unset.  By iterating over the Onext() ring (which defines a
 232        * local ordering on edges) this method searches for the first edge
 233        * whose Left() face is unset AND which is encountered AFTER edgeTest.
 234        *
 235        * @param edgeTest When present, this edge will be considered as
 236        *        the entry edge in the Onext() ring. When absent it shall
 237        *        be defaulted to "this" edge. (see the warning below).
 238        * @return When "this" edge is a boundary edge, return the first
 239        *         edge in "this" Onext() ring whose Left() face is unset
 240        *         AND located after edgeTest.
 241        *         When "this" edge is NOT a boundary edge the 0 is
 242        *         returned.
 243        * @warning When the Mesh possessing "this" edge is a 2-manifold
 244        *          then result of this method is unique in the sense that
 245        *          it is independent from the edgeTest parameter.
 246        *          But when the Mesh is not 2-manifold (this state can
 247        *          happen at intermediary stages of the building process,
 248        *          or during "surgical" operations on the Mesh, and
 249        *          even though the Mesh represents a triangulation)
 250        *          the result of this method is not unique in the sense
 251        *          that the result depends on the edgeTest parameter.
 252        *          Let us illusatre this dependence by considering a
 253        *          Mesh (which is a triangulation) which is not a 2-manifold.
 254        *          Assume the point P (the origin of "this" edge i.e.
 255        *          P = this->Originv()) is TWICE on the border i.e. it
 256        *          is adjacent twice to noface. We can consider the situation
 257        *          of the following diagram, which depicts some Onext()
 258        *          ring around point P:
 259        *
 260        *                       \         /                               //
 261        *                        \   *   /                                //
 262        *                        i3     b2              counter-clockwise //
 263        *                  *       \   /   NO FACE      Onext() order.    //
 264        *                           \ /                                   //
 265        *                 ----b4-----P----b1------                        //
 266        *                           /|\                                   //
 267        *               NO FACE    / | \                                  //
 268        *                         /  |  \    *  <------ a * indicates the //
 269        *                        /   |   \         the presence of a face //
 270        *                       /    |    \                               //
 271        *                     b5    i6     i7                             //
 272        *                     /   *  |  *   \                             //
 273        *                    /       |       \                            //
 274        *
 275        *          On this example, and if we assume the Onext() oder is
 276        *          represented counter-clockwise, the edges are ordered as
 277        *          follows:
 278        *             b1, b2, i3, b4, b5, i6, i7
 279        *          (when arbitrarily starting at edge b1).
 280        *          We have four Boundary edges labeled b1, b2, b4, b5 and
 281        *          we have three internal edges (i.e. non boundary edges)
 282        *          labeled i3, i6 and i7.
 283        *          Depending on edgeTest, the result of this method
 284        *          will NOT return the same edge:
 285        *            - when edgeTest == b5 (or i6 or i7 or b1) then the edge
 286        *              b1 will be returned,
 287        *            - when edgeTest == b2 (or i3 or b4) then the edge
 288        *              b4 will be returned,
 289        *          Eventually, when edgeTest is absent, the result shall
 290        *          depend on the position of "this" in the Onext() ring().
 291        *
 292        */
 293       TPrimal* GetNextBorderEdgeWithUnsetLeft( TPrimal* edge = NULL ) const;
 294
 295       /**
 296        * Assume "this->Originv()" is a boundary point P that is thrice
 297        * adjacent to noface and consider the given situation is the one
 298        * depicted by the following diagram where:
 299        *   - P is "this->Originv()" instance,
 300        *   - the * (star) indicates the presence of a face,
 301        *   - b1, b2, b3, b4, b5, b6 denote boundary edges,
 302        *   - p denotes some generic point,
 303        *   - A and B denote some specific points we want to discuss,
 304        *   - the Onext() ring order is represented counter-clockwise
 305        *     [which is coherent with the definition of edge->GetRigth()]
 306        *     i.e. the ordering of the edges is:
 307        *          b1, b2, b3, b4, b5, b6, b1...
 308        *
 309        *                    p       N       p
 310        *                   / \      O      / \                            //
 311        *                  /   \           /   \                           //
 312        *                 /     \    F    /     \       counter-clockwise  //
 313        *                /      b3   A   b2      \      Onext() ring order //
 314        *               /         \  C  /         \                        //
 315        *              /     *     \ E /     *     \                       //
 316        *             /             \ /             \                      //
 317        *             A------b4------P------b1-------B                     //
 318        *                           / \                                    //
 319        *                          /   \                                   //
 320        *             NO FACE     /     \      NO FACE                     //
 321        *                        /       \                                 //
 322        *                      b5         b6                               //
 323        *                      /     *     \                               //
 324        *                     /             \                              //
 325        *                    p---------------p                             //
 326        *
 327        * At P this Mesh doesn't represent a 2-manifold (since we are thrice
 328        * on the boundary). Nevertheless such a situation could arise in
 329        * intermediary stages (e.g. when building the Mesh, or during
 330        * surgical changes on the Mesh).
 331        *    Now, assume we are asked to build the triangle [P, A, B]. Note
 332        * that this request is not absurd since the current situation at
 333        * P isn't the one of a 2-manifold: hence when building the current
 334        * Onext() ring of P, we had not enough information to decide
 335        * wheter b4.Onext() should be b5 or b1. It is ONLY when we are
 336        * required to build the triangle [P, A, B] that we have the
 337        * additional information that b4.Onext() is indeed b1.
 338        *    When we are required to build triangle [P, A, B], we hence
 339        * need to change the Onext() ring order at P, i.e. we need to deal
 340        * with the triangle [P, b5, b6] which currently prevents
 341        * b4.Onext() to be b1. In other terms, when considering the
 342        * additional information that b4.Onext() is b1, and before
 343        * building the triangle [P, A, B], we need to reorder
 344        * the Onext() ring of P from it's current state
 345        *    b1, b2, b3, b4, b5, b6, b1...
 346        * to an order coherent with the [P, A, B] request, i.e.
 347        *     b1, b2, b5, b6, b3, b4, b1...
 348        *
 349        * In order to establish the "proper" Onext() ring at P we use
 350        * two Splice operations. The algorithm goes:
 351        *   - first disconnect the piece of the surface containing the edge
 352        *     [PB] (it would be the same process if we chose [PA]) from
 353        *     the Onext() ring at P.
 354        *   - second, re-integrate the disconnected piece at the desired
 355        *     location i.e. side by side with [PA] (respectively [PB] if
 356        *     we chose [PA] at first stage).
 357        * By "piece of surface containing the edge [PB]" we mean [all]
 358        * the triangle[s] starting at [PB] in the Onext() order and
 359        * having a left face set.
 360        *
 361        * We can illustrate this process on bit more general diagram than
 362        * the last case (where the "piece of surface containing the edge
 363        * [PB]" is constituted by two triangles) and when using
 364        * the arguments of this method (i.e. [PA] = this and [PB] = second).
 365        * The initial stage is the following (we note first=this=[PA] and
 366        * second=[PB]) where the Onext() ring order is:
 367        *     first, b2, b3, second, b5, bsplice, b7, first...
 368        *
 369        *                    p       N       A                            //
 370        *                   / \      O      / \                           //
 371        *                  /   \           /   \                          //
 372        *                 /     \    F    /     \     counter-clockwise   //
 373        *                /      b2   A  first    \    Onext() ring order  //
 374        *               /         \  C  /         \                       //
 375        *              /     *     \ E /     *     \                      //
 376        *             /             \ /             \                     //
 377        *            p-------b3------P------b7-------p                    //
 378        *                           /|\                                   //
 379        *                          / | \                                  //
 380        *          NO FACE        /  |  \      NO FACE                    //
 381        *                        /   |   \                                //
 382        *                  second   b5   bsplice                          //
 383        *                      /  *  |  *  \                              //
 384        *                     /      |      \                             //
 385        *                    B-------p-------p                            //
 386        *
 387        * The first stage, implemented as
 388        *     second->Oprev()->Splice( bsplice ),
 389        * yields the following diagram:
 390        *
 391        *                    p       N       A                            //
 392        *                   / \      O      / \                           //
 393        *                  /   \     F     /   \                          //
 394        *                 /     \    A    /     \      counter-clockwise  //
 395        *                /      b2   C  first    \     Onext() ring order //
 396        *               /         \  E  /         \                       //
 397        *              /     *     \   /     *     \                      //
 398        *             /             \ /             \                     //
 399        *            p-------b3------P------b7-------p                    //
 400        *                                                                 //
 401        *                         NO FACE                                 //
 402        *                                                                 //
 403        *                           /|\                                   //
 404        *                          / | \                                  //
 405        *                         /  |  \                                 //
 406        *                        /   |   \                                //
 407        *                  second   b5   bsplice                          //
 408        *                      /  *  |  *  \                              //
 409        *                     /      |      \                             //
 410        *                    B-------p-------p                            //
 411        *
 412        * and the second stage, implemented as
 413        *      first->Splice( bsplice ),
 414        * yields the following diagram:
 415        *
 416        *                                    A                            //
 417        *         B__        NO FACE        / \                           //
 418        *         |  \__                   /   \                          //
 419        *         |     \__               /     \       counter-          //
 420        *         |      second         first    \      clockwise for all //
 421        *         |           \__       /         \                       //
 422        *         |     *        \__   /     *     \                      //
 423        *         |                 \ /             \                     //
 424        *         p-------b5---------P------b7-------p                    //
 425        *         |               __/|\                                   //
 426        *         |     *      __/   | \                                  //
 427        *         |           /      |  \      NO FACE                    //
 428        *         |     bsplice      |   \                                //
 429        *         |   __/           b2    b3                              //
 430        *         p__/               |  *  \                              //
 431        *                NO FACE     |      \                             //
 432        *                            p-------p                            //
 433        *
 434        */
 435       inline static bool ReorderOnextRing( TPrimal* first, TPrimal* second );
 436
 437       /**
 438        * \brief Basic quad-edge topological method.
 439        *
 440        * This method describes all possible topological operations on an
 441        * edge since it is its own inverse. It works in two ways:
 442        *
 443        *   1. If this->m_Org != b->m_Org, it slice a face in two.
 444        *   2. If this->m_Org == b->m_Org, it unifies two faces.
 445        */
 446       inline static void Splice( TPrimal* a, TPrimal* b );
 447
 448     protected:
 449       QuadEdge( );
 450       virtual ~QuadEdge( );
 451
 452     public:
 453       static const TPrimalGeometry NoGeometry;
 454
 455     protected:
 456       Pointer         m_Onext;  /**< Onext ring */
 457       PtrDual         m_Rot;    /**< Rot ring */
 458       TPrimalGeometry m_Origin; /**< Geometry attached to edge's origin */
 459     };
 460
 461   } // ecapseman
 462
 463 } // ecapseman
 464
 465 #ifndef ITK_MANUAL_INSTANTIATION
 466 #include <cpExtensions/DataStructures/QuadEdge.hxx>
 467 #endif // ITK_MANUAL_INSTANTIATION
 468
 469 #endif // __CPEXTENSIONS__DATASTRUCTURES__QUADEDGE__H__
 470
 471 // eof - $RCSfile$