#ifndef __CPM__DATASTRUCTURES__QUADEDGE__H__ #define __CPM__DATASTRUCTURES__QUADEDGE__H__ #include #include namespace cpm { 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 ); cpmDataStructuresQEAllIteratorsMacro( Onext ); cpmDataStructuresQEAllIteratorsMacro( Lnext ); cpmDataStructuresQEAllIteratorsMacro( Rnext ); cpmDataStructuresQEAllIteratorsMacro( Dnext ); cpmDataStructuresQEAllIteratorsMacro( Oprev ); cpmDataStructuresQEAllIteratorsMacro( Lprev ); cpmDataStructuresQEAllIteratorsMacro( Rprev ); cpmDataStructuresQEAllIteratorsMacro( 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 } // ecapseman #include #endif // __CPM__DATASTRUCTURES__QUADEDGE__H__ // eof - $RCSfile$