X-Git-Url: https://git.creatis.insa-lyon.fr/pubgit/?a=blobdiff_plain;f=lib%2FcpExtensions%2FDataStructures%2FQuadEdge.h;h=bcb1f886365a9751c85e8fa8db8223fdde5ab789;hb=b5691a406e0f87d9f051cdd5877a4dfb299764a5;hp=9b0a66048dacb8d0ac42c05a505a810910efd701;hpb=2361f4f97631e09d88d8a5510a369817dcaa19db;p=cpPlugins.git diff --git a/lib/cpExtensions/DataStructures/QuadEdge.h b/lib/cpExtensions/DataStructures/QuadEdge.h index 9b0a660..bcb1f88 100644 --- a/lib/cpExtensions/DataStructures/QuadEdge.h +++ b/lib/cpExtensions/DataStructures/QuadEdge.h @@ -5,464 +5,466 @@ #include namespace cpExtensions +{ + namespace DataStructures { - namespace DataStructures + /** + */ + template< typename P, typename D, bool IsPrimal = true > + class QuadEdge + : public itk::LightObject { + public: + typedef QuadEdge Self; + typedef itk::LightObject Superclass; + typedef itk::SmartPointer< Self > Pointer; + typedef itk::SmartPointer< const Self > ConstPointer; + + /// Vertices and faces types + typedef P TPrimalGeometry; + typedef D TDualGeometry; + + /** + * Dual type, basically the same type with swapped template + * parameters. + */ + typedef QuadEdge< D, P, !IsPrimal > TDual; + typedef Self TPrimal; + typedef typename TDual::Pointer PtrDual; + friend TDual; + + /// Iterators + typedef QuadEdgeIterator< TPrimal > Iterator; + typedef QuadEdgeConstIterator< TPrimal > ConstIterator; + typedef QuadEdgePointIterator< TPrimal > PointIterator; + typedef QuadEdgePointConstIterator< TPrimal > PointConstIterator; + + public: + itkNewMacro( Self ); + itkTypeMacro( QuadEdge, itkLightObject ); + + cpPluginsExtensionsQEAllIteratorsMacro( Onext ); + cpPluginsExtensionsQEAllIteratorsMacro( Lnext ); + cpPluginsExtensionsQEAllIteratorsMacro( Rnext ); + cpPluginsExtensionsQEAllIteratorsMacro( Dnext ); + cpPluginsExtensionsQEAllIteratorsMacro( Oprev ); + cpPluginsExtensionsQEAllIteratorsMacro( Lprev ); + cpPluginsExtensionsQEAllIteratorsMacro( Rprev ); + cpPluginsExtensionsQEAllIteratorsMacro( Dprev ); + + public: + void CreateRings( ); + + /// First order access methods + inline TPrimal* GetOnext( ) + { return( this->m_Onext ); } + inline TDual* GetRot( ) + { return( this->m_Rot ); } + inline const TPrimal* GetOnext( ) const + { return( this->m_Onext ); } + inline const TDual* GetRot( ) const + { return( this->m_Rot ); } + + /// First order configuration methods + inline void SetOnext( TPrimal* e ) + { this->m_Onext = e; } + inline void SetRot( TDual* e ) + { this->m_Rot = e; } + + /// Second order accessors: around base rings + inline TPrimal* GetSym( ) + { return( this->m_Rot->m_Rot ); } + inline TDual* GetInvRot( ) + { return( this->m_Rot->m_Rot->m_Rot ); } + + /// Second order accessors: neighboring topology + inline TPrimal* GetLnext( ) + { return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot ); } + inline TPrimal* GetRnext( ) + { return( this->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot ); } + inline TPrimal* GetDnext( ) + { return( this->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot ); } + inline TPrimal* GetOprev( ) + { return( this->m_Rot->m_Onext->m_Rot ); } + inline TPrimal* GetLprev( ) + { return( this->m_Onext->m_Rot->m_Rot ); } + inline TPrimal* GetRprev( ) + { return( this->m_Rot->m_Rot->m_Onext ); } + inline TPrimal* GetDprev( ) + { + return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot ); + } + + /// Second order accessors: around base rings (const versions) + inline const TPrimal* GetSym( ) const + { return( this->m_Rot->m_Rot ); } + inline const TDual* GetInvRot( ) const + { return( this->m_Rot->m_Rot->m_Rot ); } + + /// Second order accessors: neighboring topology (const versions) + inline const TPrimal* GetLnext( ) const + { return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot ); } + inline const TPrimal* GetRnext( ) const + { return( this->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot ); } + inline const TPrimal* GetDnext( ) const + { return( this->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot ); } + inline const TPrimal* GetOprev( ) const + { return( this->m_Rot->m_Onext->m_Rot ); } + inline const TPrimal* GetLprev( ) const + { return( this->m_Onext->m_Rot->m_Rot ); } + inline const TPrimal* GetRprev( ) const + { return( this->m_Rot->m_Rot->m_Onext ); } + inline const TPrimal* GetDprev( ) const + { + return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot ); + } + + /// Get geometry methods + inline P& GetOrigin( ) + { return ( this->m_Origin ); } + inline P& GetDestination( ) + { return ( this->m_Rot->m_Rot->m_Origin ); } + inline D& GetRight( ) + { return ( this->m_Rot->m_Origin ); } + inline D& GetLeft( ) + { return ( this->m_Rot->m_Rot->m_Rot->m_Origin ); } + + /// Get geometry methods (const versions) + inline const P& GetOrigin( ) const + { return ( this->m_Origin ); } + inline const P& GetDestination( ) const + { return ( this->m_Rot->m_Rot->m_Origin ); } + inline const D& GetRight( ) const + { return ( this->m_Rot->m_Origin ); } + inline const D& GetLeft( ) const + { return ( this->m_Rot->m_Rot->m_Rot->m_Origin ); } + + /// Set geometry methods + inline void SetOrigin( const P& v ) + { this->m_Origin = v; } + inline void SetDestination( const P& v ) + { this->m_Rot->m_Rot->m_Origin = v; } + inline void SetRight( const D& v ) + { this->m_Rot->m_Origin = v; } + inline void SetLeft( const D& v ) + { this->m_Rot->m_Rot->m_Rot->m_Origin = v; } + inline void UnsetOrigin( ) + { this->m_Origin = TPrimal::NoGeometry; } + inline void UnsetDestination( ) + { this->m_Rot->m_Rot->m_Origin = TPrimal::NoGeometry; } + inline void UnsetRight( ) + { this->m_Rot->m_Origin = TDual::NoGeometry; } + inline void UnsetLeft( ) + { this->m_Rot->m_Rot->m_Rot->m_Origin = TDual::NoGeometry; } + + /** + * Set the Left( ) of all the edges in the Lnext( ) ring of "this" + * with the same given geometrical information. + * @param faceGeom Looks at most maxSize edges in the Lnext( ) ring. + * @return Returns true on success. False otherwise. + */ + void SetLnextRingGeometry( const D& v ); + void UnsetLnextRingGeometry( ); + + /// Topological queries + inline bool IsIsolated( ) const + { return( this == this->m_Onext ); } + bool IsEdgeInOnextRing( const TPrimal* e ) const; + bool IsEdgeInLnextRing( const TPrimal* e ) const; + unsigned int GetOnextRingSize( ) const; + unsigned int GetLnextRingSize( ) const; + + /** + * @return Returns true when "this" has no faces set on both sides. + * Return false otherwise. + */ + inline bool IsWire( ) + { return( !( this->IsLeftSet( ) ) && !( this->IsRightSet( ) ) ); } + /** + * @return Returns true when "this" is on the boundary i.e. + * one and only one of the faces is set. Return false + * otherwise. */ - template< typename P, typename D, bool IsPrimal = true > - class QuadEdge - : public itk::LightObject - { - public: - typedef QuadEdge Self; - typedef itk::LightObject Superclass; - typedef itk::SmartPointer< Self > Pointer; - typedef itk::SmartPointer< const Self > ConstPointer; - - /// Vertices and faces types - typedef P TPrimalGeometry; - typedef D TDualGeometry; - - /** - * Dual type, basically the same type with swapped template - * parameters. - */ - typedef QuadEdge< D, P, !IsPrimal > TDual; - typedef Self TPrimal; - typedef typename TDual::Pointer PtrDual; - friend TDual; - - /// Iterators - typedef QuadEdgeIterator< TPrimal > Iterator; - typedef QuadEdgeConstIterator< TPrimal > ConstIterator; - typedef QuadEdgePointIterator< TPrimal > PointIterator; - typedef QuadEdgePointConstIterator< TPrimal > PointConstIterator; - - public: - itkNewMacro( Self ); - itkTypeMacro( QuadEdge, itkLightObject ); - - cpPluginsExtensionsQEAllIteratorsMacro( Onext ); - cpPluginsExtensionsQEAllIteratorsMacro( Lnext ); - cpPluginsExtensionsQEAllIteratorsMacro( Rnext ); - cpPluginsExtensionsQEAllIteratorsMacro( Dnext ); - cpPluginsExtensionsQEAllIteratorsMacro( Oprev ); - cpPluginsExtensionsQEAllIteratorsMacro( Lprev ); - cpPluginsExtensionsQEAllIteratorsMacro( Rprev ); - cpPluginsExtensionsQEAllIteratorsMacro( Dprev ); - - public: - void CreateRings( ); - - /// First order access methods - inline TPrimal* GetOnext( ) - { return( this->m_Onext ); } - inline TDual* GetRot( ) - { return( this->m_Rot ); } - inline const TPrimal* GetOnext( ) const - { return( this->m_Onext ); } - inline const TDual* GetRot( ) const - { return( this->m_Rot ); } - - /// First order configuration methods - inline void SetOnext( TPrimal* e ) - { this->m_Onext = e; } - inline void SetRot( TDual* e ) - { this->m_Rot = e; } - - /// Second order accessors: around base rings - inline TPrimal* GetSym( ) - { return( this->m_Rot->m_Rot ); } - inline TDual* GetInvRot( ) - { return( this->m_Rot->m_Rot->m_Rot ); } - - /// Second order accessors: neighboring topology - inline TPrimal* GetLnext( ) - { return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot ); } - inline TPrimal* GetRnext( ) - { return( this->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot ); } - inline TPrimal* GetDnext( ) - { return( this->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot ); } - inline TPrimal* GetOprev( ) - { return( this->m_Rot->m_Onext->m_Rot ); } - inline TPrimal* GetLprev( ) - { return( this->m_Onext->m_Rot->m_Rot ); } - inline TPrimal* GetRprev( ) - { return( this->m_Rot->m_Rot->m_Onext ); } - inline TPrimal* GetDprev( ) - { - return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot ); - } - - /// Second order accessors: around base rings (const versions) - inline const TPrimal* GetSym( ) const - { return( this->m_Rot->m_Rot ); } - inline const TDual* GetInvRot( ) const - { return( this->m_Rot->m_Rot->m_Rot ); } - - /// Second order accessors: neighboring topology (const versions) - inline const TPrimal* GetLnext( ) const - { return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot ); } - inline const TPrimal* GetRnext( ) const - { return( this->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot ); } - inline const TPrimal* GetDnext( ) const - { return( this->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot ); } - inline const TPrimal* GetOprev( ) const - { return( this->m_Rot->m_Onext->m_Rot ); } - inline const TPrimal* GetLprev( ) const - { return( this->m_Onext->m_Rot->m_Rot ); } - inline const TPrimal* GetRprev( ) const - { return( this->m_Rot->m_Rot->m_Onext ); } - inline const TPrimal* GetDprev( ) const - { - return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot ); - } - - /// Get geometry methods - inline P& GetOrigin( ) - { return ( this->m_Origin ); } - inline P& GetDestination( ) - { return ( this->m_Rot->m_Rot->m_Origin ); } - inline D& GetRight( ) - { return ( this->m_Rot->m_Origin ); } - inline D& GetLeft( ) - { return ( this->m_Rot->m_Rot->m_Rot->m_Origin ); } - - /// Get geometry methods (const versions) - inline const P& GetOrigin( ) const - { return ( this->m_Origin ); } - inline const P& GetDestination( ) const - { return ( this->m_Rot->m_Rot->m_Origin ); } - inline const D& GetRight( ) const - { return ( this->m_Rot->m_Origin ); } - inline const D& GetLeft( ) const - { return ( this->m_Rot->m_Rot->m_Rot->m_Origin ); } - - /// Set geometry methods - inline void SetOrigin( const P& v ) - { this->m_Origin = v; } - inline void SetDestination( const P& v ) - { this->m_Rot->m_Rot->m_Origin = v; } - inline void SetRight( const D& v ) - { this->m_Rot->m_Origin = v; } - inline void SetLeft( const D& v ) - { this->m_Rot->m_Rot->m_Rot->m_Origin = v; } - inline void UnsetOrigin( ) - { this->m_Origin = TPrimal::NoGeometry; } - inline void UnsetDestination( ) - { this->m_Rot->m_Rot->m_Origin = TPrimal::NoGeometry; } - inline void UnsetRight( ) - { this->m_Rot->m_Origin = TDual::NoGeometry; } - inline void UnsetLeft( ) - { this->m_Rot->m_Rot->m_Rot->m_Origin = TDual::NoGeometry; } - - /** - * Set the Left( ) of all the edges in the Lnext( ) ring of "this" - * with the same given geometrical information. - * @param faceGeom Looks at most maxSize edges in the Lnext( ) ring. - * @return Returns true on success. False otherwise. - */ - void SetLnextRingGeometry( const D& v ); - void UnsetLnextRingGeometry( ); - - /// Topological queries - inline bool IsIsolated( ) const - { return( this == this->m_Onext ); } - bool IsEdgeInOnextRing( const TPrimal* e ) const; - bool IsEdgeInLnextRing( const TPrimal* e ) const; - unsigned int GetOnextRingSize( ) const; - unsigned int GetLnextRingSize( ) const; - - /** - * @return Returns true when "this" has no faces set on both sides. - * Return false otherwise. - */ - inline bool IsWire( ) - { return( !( this->IsLeftSet( ) ) && !( this->IsRightSet( ) ) ); } - - /** - * @return Returns true when "this" is on the boundary i.e. - * one and only one of the faces is set. Return false - * otherwise. - */ - inline bool IsAtBorder( ) const; - - /** - * @return Returns true when "this" has faces set on both sides. - * Return false otherwise. - */ - inline bool IsInternal( ) const - { return ( this->IsLeftSet( ) && this->IsRightSet( ) ); } - - /// Geometrical queries - inline bool IsOriginSet( ) const - { return ( this->m_Origin != Self::NoGeometry ); } - inline bool IsDestinationSet( ) const - { return ( this->m_Rot->m_Rot->IsOriginSet( ) ); } - inline bool IsRightSet( ) const - { return ( this->m_Rot->IsOriginSet( ) ); } - inline bool IsLeftSet( ) const - { return ( this->m_Rot->m_Rot->m_Rot->IsOriginSet( ) ); } - - /** - * \brief Check wether edge's Origin is internal to the mesh (as - * opposed to being on the boundary) by looking if all the edges - * in the Onext() ring have a face set on both their Left() and - * Right() side. - */ - bool IsOriginInternal( ) const; - - /** - * Definition: an edge is said to be a boundary edge when it is - * adjacent to i.e. when at least one of the faces edge->GetLeft() or - * edge->GetRight() is unset. Definition: an point is said to be a - * boundary point when at least one of the edges of it's Onext() ring - * is a boundary edge. - * - * Assume "this" edge belongs to a triangulation (i.e. it belongs to a - * QEMesh which represents a 2-manifold) which possesses a boundary. - * Assume "this" edge instance is a boundary edge. Let us denote by P - * the point which is the origin of "this" edge i.e. P is - * this->Origin(). By definition P is a boundary point. Then AT - * LEAST two [see the note below] edges of the Onext() ring of P - * [which all have the point P as Origin()] are themselves boundary - * edges. And among those boundary edges AT LEAST one has it's Left() - * face unset. By iterating over the Onext() ring (which defines a - * local ordering on edges) this method searches for the first edge - * whose Left() face is unset AND which is encountered AFTER edgeTest. - * - * @param edgeTest When present, this edge will be considered as - * the entry edge in the Onext() ring. When absent it shall - * be defaulted to "this" edge. (see the warning below). - * @return When "this" edge is a boundary edge, return the first - * edge in "this" Onext() ring whose Left() face is unset - * AND located after edgeTest. - * When "this" edge is NOT a boundary edge the 0 is - * returned. - * @warning When the Mesh possessing "this" edge is a 2-manifold - * then result of this method is unique in the sense that - * it is independent from the edgeTest parameter. - * But when the Mesh is not 2-manifold (this state can - * happen at intermediary stages of the building process, - * or during "surgical" operations on the Mesh, and - * even though the Mesh represents a triangulation) - * the result of this method is not unique in the sense - * that the result depends on the edgeTest parameter. - * Let us illusatre this dependence by considering a - * Mesh (which is a triangulation) which is not a 2-manifold. - * Assume the point P (the origin of "this" edge i.e. - * P = this->Originv()) is TWICE on the border i.e. it - * is adjacent twice to noface. We can consider the situation - * of the following diagram, which depicts some Onext() - * ring around point P: - * - * \ / // - * \ * / // - * i3 b2 counter-clockwise // - * * \ / NO FACE Onext() order. // - * \ / // - * ----b4-----P----b1------ // - * /|\ // - * NO FACE / | \ // - * / | \ * <------ a * indicates the // - * / | \ the presence of a face // - * / | \ // - * b5 i6 i7 // - * / * | * \ // - * / | \ // - * - * On this example, and if we assume the Onext() oder is - * represented counter-clockwise, the edges are ordered as - * follows: - * b1, b2, i3, b4, b5, i6, i7 - * (when arbitrarily starting at edge b1). - * We have four Boundary edges labeled b1, b2, b4, b5 and - * we have three internal edges (i.e. non boundary edges) - * labeled i3, i6 and i7. - * Depending on edgeTest, the result of this method - * will NOT return the same edge: - * - when edgeTest == b5 (or i6 or i7 or b1) then the edge - * b1 will be returned, - * - when edgeTest == b2 (or i3 or b4) then the edge - * b4 will be returned, - * Eventually, when edgeTest is absent, the result shall - * depend on the position of "this" in the Onext() ring(). - * - */ - TPrimal* GetNextBorderEdgeWithUnsetLeft( TPrimal* edge = NULL ) const; - - /** - * Assume "this->Originv()" is a boundary point P that is thrice - * adjacent to noface and consider the given situation is the one - * depicted by the following diagram where: - * - P is "this->Originv()" instance, - * - the * (star) indicates the presence of a face, - * - b1, b2, b3, b4, b5, b6 denote boundary edges, - * - p denotes some generic point, - * - A and B denote some specific points we want to discuss, - * - the Onext() ring order is represented counter-clockwise - * [which is coherent with the definition of edge->GetRigth()] - * i.e. the ordering of the edges is: - * b1, b2, b3, b4, b5, b6, b1... - * - * p N p - * / \ O / \ // - * / \ / \ // - * / \ F / \ counter-clockwise // - * / b3 A b2 \ Onext() ring order // - * / \ C / \ // - * / * \ E / * \ // - * / \ / \ // - * A------b4------P------b1-------B // - * / \ // - * / \ // - * NO FACE / \ NO FACE // - * / \ // - * b5 b6 // - * / * \ // - * / \ // - * p---------------p // - * - * At P this Mesh doesn't represent a 2-manifold (since we are thrice - * on the boundary). Nevertheless such a situation could arise in - * intermediary stages (e.g. when building the Mesh, or during - * surgical changes on the Mesh). - * Now, assume we are asked to build the triangle [P, A, B]. Note - * that this request is not absurd since the current situation at - * P isn't the one of a 2-manifold: hence when building the current - * Onext() ring of P, we had not enough information to decide - * wheter b4.Onext() should be b5 or b1. It is ONLY when we are - * required to build the triangle [P, A, B] that we have the - * additional information that b4.Onext() is indeed b1. - * When we are required to build triangle [P, A, B], we hence - * need to change the Onext() ring order at P, i.e. we need to deal - * with the triangle [P, b5, b6] which currently prevents - * b4.Onext() to be b1. In other terms, when considering the - * additional information that b4.Onext() is b1, and before - * building the triangle [P, A, B], we need to reorder - * the Onext() ring of P from it's current state - * b1, b2, b3, b4, b5, b6, b1... - * to an order coherent with the [P, A, B] request, i.e. - * b1, b2, b5, b6, b3, b4, b1... - * - * In order to establish the "proper" Onext() ring at P we use - * two Splice operations. The algorithm goes: - * - first disconnect the piece of the surface containing the edge - * [PB] (it would be the same process if we chose [PA]) from - * the Onext() ring at P. - * - second, re-integrate the disconnected piece at the desired - * location i.e. side by side with [PA] (respectively [PB] if - * we chose [PA] at first stage). - * By "piece of surface containing the edge [PB]" we mean [all] - * the triangle[s] starting at [PB] in the Onext() order and - * having a left face set. - * - * We can illustrate this process on bit more general diagram than - * the last case (where the "piece of surface containing the edge - * [PB]" is constituted by two triangles) and when using - * the arguments of this method (i.e. [PA] = this and [PB] = second). - * The initial stage is the following (we note first=this=[PA] and - * second=[PB]) where the Onext() ring order is: - * first, b2, b3, second, b5, bsplice, b7, first... - * - * p N A // - * / \ O / \ // - * / \ / \ // - * / \ F / \ counter-clockwise // - * / b2 A first \ Onext() ring order // - * / \ C / \ // - * / * \ E / * \ // - * / \ / \ // - * p-------b3------P------b7-------p // - * /|\ // - * / | \ // - * NO FACE / | \ NO FACE // - * / | \ // - * second b5 bsplice // - * / * | * \ // - * / | \ // - * B-------p-------p // - * - * The first stage, implemented as - * second->Oprev()->Splice( bsplice ), - * yields the following diagram: - * - * p N A // - * / \ O / \ // - * / \ F / \ // - * / \ A / \ counter-clockwise // - * / b2 C first \ Onext() ring order // - * / \ E / \ // - * / * \ / * \ // - * / \ / \ // - * p-------b3------P------b7-------p // - * // - * NO FACE // - * // - * /|\ // - * / | \ // - * / | \ // - * / | \ // - * second b5 bsplice // - * / * | * \ // - * / | \ // - * B-------p-------p // - * - * and the second stage, implemented as - * first->Splice( bsplice ), - * yields the following diagram: - * - * A // - * B__ NO FACE / \ // - * | \__ / \ // - * | \__ / \ counter- // - * | second first \ clockwise for all // - * | \__ / \ // - * | * \__ / * \ // - * | \ / \ // - * p-------b5---------P------b7-------p // - * | __/|\ // - * | * __/ | \ // - * | / | \ NO FACE // - * | bsplice | \ // - * | __/ b2 b3 // - * p__/ | * \ // - * NO FACE | \ // - * p-------p // - * - */ - inline static bool ReorderOnextRing( TPrimal* first, TPrimal* second ); - - /** - * \brief Basic quad-edge topological method. - * - * This method describes all possible topological operations on an - * edge since it is its own inverse. It works in two ways: - * - * 1. If this->m_Org != b->m_Org, it slice a face in two. - * 2. If this->m_Org == b->m_Org, it unifies two faces. - */ - inline static void Splice( TPrimal* a, TPrimal* b ); - - protected: - QuadEdge( ); - virtual ~QuadEdge( ); - - public: - static const TPrimalGeometry NoGeometry; - - protected: - Pointer m_Onext; /**< Onext ring */ - PtrDual m_Rot; /**< Rot ring */ - TPrimalGeometry m_Origin; /**< Geometry attached to edge's origin */ - }; - - } // ecapseman + inline bool IsAtBorder( ) const; + + /** + * @return Returns true when "this" has faces set on both sides. + * Return false otherwise. + */ + inline bool IsInternal( ) const + { return ( this->IsLeftSet( ) && this->IsRightSet( ) ); } + + /// Geometrical queries + inline bool IsOriginSet( ) const + { return ( this->m_Origin != Self::NoGeometry ); } + inline bool IsDestinationSet( ) const + { return ( this->m_Rot->m_Rot->IsOriginSet( ) ); } + inline bool IsRightSet( ) const + { return ( this->m_Rot->IsOriginSet( ) ); } + inline bool IsLeftSet( ) const + { return ( this->m_Rot->m_Rot->m_Rot->IsOriginSet( ) ); } + + /** + * \brief Check wether edge's Origin is internal to the mesh (as + * opposed to being on the boundary) by looking if all the edges + * in the Onext() ring have a face set on both their Left() and + * Right() side. + */ + bool IsOriginInternal( ) const; + + /** + * Definition: an edge is said to be a boundary edge when it is + * adjacent to i.e. when at least one of the faces edge->GetLeft() or + * edge->GetRight() is unset. Definition: an point is said to be a + * boundary point when at least one of the edges of it's Onext() ring + * is a boundary edge. + * + * Assume "this" edge belongs to a triangulation (i.e. it belongs to a + * QEMesh which represents a 2-manifold) which possesses a boundary. + * Assume "this" edge instance is a boundary edge. Let us denote by P + * the point which is the origin of "this" edge i.e. P is + * this->Origin(). By definition P is a boundary point. Then AT + * LEAST two [see the note below] edges of the Onext() ring of P + * [which all have the point P as Origin()] are themselves boundary + * edges. And among those boundary edges AT LEAST one has it's Left() + * face unset. By iterating over the Onext() ring (which defines a + * local ordering on edges) this method searches for the first edge + * whose Left() face is unset AND which is encountered AFTER edgeTest. + * + * @param edgeTest When present, this edge will be considered as + * the entry edge in the Onext() ring. When absent it shall + * be defaulted to "this" edge. (see the warning below). + * @return When "this" edge is a boundary edge, return the first + * edge in "this" Onext() ring whose Left() face is unset + * AND located after edgeTest. + * When "this" edge is NOT a boundary edge the 0 is + * returned. + * @warning When the Mesh possessing "this" edge is a 2-manifold + * then result of this method is unique in the sense that + * it is independent from the edgeTest parameter. + * But when the Mesh is not 2-manifold (this state can + * happen at intermediary stages of the building process, + * or during "surgical" operations on the Mesh, and + * even though the Mesh represents a triangulation) + * the result of this method is not unique in the sense + * that the result depends on the edgeTest parameter. + * Let us illusatre this dependence by considering a + * Mesh (which is a triangulation) which is not a 2-manifold. + * Assume the point P (the origin of "this" edge i.e. + * P = this->Originv()) is TWICE on the border i.e. it + * is adjacent twice to noface. We can consider the situation + * of the following diagram, which depicts some Onext() + * ring around point P: + * + * \ / // + * \ * / // + * i3 b2 counter-clockwise // + * * \ / NO FACE Onext() order. // + * \ / // + * ----b4-----P----b1------ // + * /|\ // + * NO FACE / | \ // + * / | \ * <------ a * indicates the // + * / | \ the presence of a face // + * / | \ // + * b5 i6 i7 // + * / * | * \ // + * / | \ // + * + * On this example, and if we assume the Onext() oder is + * represented counter-clockwise, the edges are ordered as + * follows: + * b1, b2, i3, b4, b5, i6, i7 + * (when arbitrarily starting at edge b1). + * We have four Boundary edges labeled b1, b2, b4, b5 and + * we have three internal edges (i.e. non boundary edges) + * labeled i3, i6 and i7. + * Depending on edgeTest, the result of this method + * will NOT return the same edge: + * - when edgeTest == b5 (or i6 or i7 or b1) then the edge + * b1 will be returned, + * - when edgeTest == b2 (or i3 or b4) then the edge + * b4 will be returned, + * Eventually, when edgeTest is absent, the result shall + * depend on the position of "this" in the Onext() ring(). + * + */ + TPrimal* GetNextBorderEdgeWithUnsetLeft( TPrimal* edge = NULL ) const; + + /** + * Assume "this->Originv()" is a boundary point P that is thrice + * adjacent to noface and consider the given situation is the one + * depicted by the following diagram where: + * - P is "this->Originv()" instance, + * - the * (star) indicates the presence of a face, + * - b1, b2, b3, b4, b5, b6 denote boundary edges, + * - p denotes some generic point, + * - A and B denote some specific points we want to discuss, + * - the Onext() ring order is represented counter-clockwise + * [which is coherent with the definition of edge->GetRigth()] + * i.e. the ordering of the edges is: + * b1, b2, b3, b4, b5, b6, b1... + * + * p N p + * / \ O / \ // + * / \ / \ // + * / \ F / \ counter-clockwise // + * / b3 A b2 \ Onext() ring order // + * / \ C / \ // + * / * \ E / * \ // + * / \ / \ // + * A------b4------P------b1-------B // + * / \ // + * / \ // + * NO FACE / \ NO FACE // + * / \ // + * b5 b6 // + * / * \ // + * / \ // + * p---------------p // + * + * At P this Mesh doesn't represent a 2-manifold (since we are thrice + * on the boundary). Nevertheless such a situation could arise in + * intermediary stages (e.g. when building the Mesh, or during + * surgical changes on the Mesh). + * Now, assume we are asked to build the triangle [P, A, B]. Note + * that this request is not absurd since the current situation at + * P isn't the one of a 2-manifold: hence when building the current + * Onext() ring of P, we had not enough information to decide + * wheter b4.Onext() should be b5 or b1. It is ONLY when we are + * required to build the triangle [P, A, B] that we have the + * additional information that b4.Onext() is indeed b1. + * When we are required to build triangle [P, A, B], we hence + * need to change the Onext() ring order at P, i.e. we need to deal + * with the triangle [P, b5, b6] which currently prevents + * b4.Onext() to be b1. In other terms, when considering the + * additional information that b4.Onext() is b1, and before + * building the triangle [P, A, B], we need to reorder + * the Onext() ring of P from it's current state + * b1, b2, b3, b4, b5, b6, b1... + * to an order coherent with the [P, A, B] request, i.e. + * b1, b2, b5, b6, b3, b4, b1... + * + * In order to establish the "proper" Onext() ring at P we use + * two Splice operations. The algorithm goes: + * - first disconnect the piece of the surface containing the edge + * [PB] (it would be the same process if we chose [PA]) from + * the Onext() ring at P. + * - second, re-integrate the disconnected piece at the desired + * location i.e. side by side with [PA] (respectively [PB] if + * we chose [PA] at first stage). + * By "piece of surface containing the edge [PB]" we mean [all] + * the triangle[s] starting at [PB] in the Onext() order and + * having a left face set. + * + * We can illustrate this process on bit more general diagram than + * the last case (where the "piece of surface containing the edge + * [PB]" is constituted by two triangles) and when using + * the arguments of this method (i.e. [PA] = this and [PB] = second). + * The initial stage is the following (we note first=this=[PA] and + * second=[PB]) where the Onext() ring order is: + * first, b2, b3, second, b5, bsplice, b7, first... + * + * p N A // + * / \ O / \ // + * / \ / \ // + * / \ F / \ counter-clockwise // + * / b2 A first \ Onext() ring order // + * / \ C / \ // + * / * \ E / * \ // + * / \ / \ // + * p-------b3------P------b7-------p // + * /|\ // + * / | \ // + * NO FACE / | \ NO FACE // + * / | \ // + * second b5 bsplice // + * / * | * \ // + * / | \ // + * B-------p-------p // + * + * The first stage, implemented as + * second->Oprev()->Splice( bsplice ), + * yields the following diagram: + * + * p N A // + * / \ O / \ // + * / \ F / \ // + * / \ A / \ counter-clockwise // + * / b2 C first \ Onext() ring order // + * / \ E / \ // + * / * \ / * \ // + * / \ / \ // + * p-------b3------P------b7-------p // + * // + * NO FACE // + * // + * /|\ // + * / | \ // + * / | \ // + * / | \ // + * second b5 bsplice // + * / * | * \ // + * / | \ // + * B-------p-------p // + * + * and the second stage, implemented as + * first->Splice( bsplice ), + * yields the following diagram: + * + * A // + * B__ NO FACE / \ // + * | \__ / \ // + * | \__ / \ counter- // + * | second first \ clockwise for all // + * | \__ / \ // + * | * \__ / * \ // + * | \ / \ // + * p-------b5---------P------b7-------p // + * | __/|\ // + * | * __/ | \ // + * | / | \ NO FACE // + * | bsplice | \ // + * | __/ b2 b3 // + * p__/ | * \ // + * NO FACE | \ // + * p-------p // + * + */ + inline static bool ReorderOnextRing( TPrimal* first, TPrimal* second ); + + /** + * \brief Basic quad-edge topological method. + * + * This method describes all possible topological operations on an + * edge since it is its own inverse. It works in two ways: + * + * 1. If this->m_Org != b->m_Org, it slice a face in two. + * 2. If this->m_Org == b->m_Org, it unifies two faces. + */ + inline static void Splice( TPrimal* a, TPrimal* b ); + + protected: + QuadEdge( ); + virtual ~QuadEdge( ); + + public: + static const TPrimalGeometry NoGeometry; + + protected: + Pointer m_Onext; /**< Onext ring */ + PtrDual m_Rot; /**< Rot ring */ + TPrimalGeometry m_Origin; /**< Geometry attached to edge's origin */ + }; + + } // ecapseman } // ecapseman +#ifndef ITK_MANUAL_INSTANTIATION #include +#endif // ITK_MANUAL_INSTANTIATION #endif // __CPEXTENSIONS__DATASTRUCTURES__QUADEDGE__H__