+++ /dev/null
-#ifndef __CPM__DATASTRUCTURES__QUADEDGE__H__
-#define __CPM__DATASTRUCTURES__QUADEDGE__H__
-
-#include <itkLightObject.h>
-#include <cpm/DataStructures/QuadEdgeIterators.h>
-
-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 <cpm/DataStructures/QuadEdge.hxx>
-
-#endif // __CPM__DATASTRUCTURES__QUADEDGE__H__
-
-// eof - $RCSfile$
git://git.creatis.insa-lyon.fr / cpMesh.git / blobdiff