#include <cpExtensions/DataStructures/QuadEdgeIterators.h>
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 <cpExtensions/DataStructures/QuadEdge.hxx>
+#endif // ITK_MANUAL_INSTANTIATION
#endif // __CPEXTENSIONS__DATASTRUCTURES__QUADEDGE__H__
git://git.creatis.insa-lyon.fr / cpPlugins.git / blobdiff