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