lib/cpPlugins/Extensions/DataStructures/QuadEdge.h

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