1 #ifndef __CPPLUGINS__EXTENSIONS__DATASTRUCTURES__QUADEDGE__H__
2 #define __CPPLUGINS__EXTENSIONS__DATASTRUCTURES__QUADEDGE__H__
4 #include <itkLightObject.h>
5 #include <cpPlugins/Extensions/DataStructures/QuadEdgeIterators.h>
11 namespace DataStructures
15 template< typename P, typename D, bool IsPrimal = true >
17 : public itk::LightObject
20 typedef QuadEdge Self;
21 typedef itk::LightObject Superclass;
22 typedef itk::SmartPointer< Self > Pointer;
23 typedef itk::SmartPointer< const Self > ConstPointer;
25 /// Vertices and faces types
26 typedef P TPrimalGeometry;
27 typedef D TDualGeometry;
30 * Dual type, basically the same type with swapped template
33 typedef QuadEdge< D, P, !IsPrimal > TDual;
35 typedef typename TDual::Pointer PtrDual;
39 typedef QuadEdgeIterator< TPrimal > Iterator;
40 typedef QuadEdgeConstIterator< TPrimal > ConstIterator;
41 typedef QuadEdgePointIterator< TPrimal > PointIterator;
42 typedef QuadEdgePointConstIterator< TPrimal > PointConstIterator;
46 itkTypeMacro( QuadEdge, itkLightObject );
48 cpPluginsExtensionsQEAllIteratorsMacro( Onext );
49 cpPluginsExtensionsQEAllIteratorsMacro( Lnext );
50 cpPluginsExtensionsQEAllIteratorsMacro( Rnext );
51 cpPluginsExtensionsQEAllIteratorsMacro( Dnext );
52 cpPluginsExtensionsQEAllIteratorsMacro( Oprev );
53 cpPluginsExtensionsQEAllIteratorsMacro( Lprev );
54 cpPluginsExtensionsQEAllIteratorsMacro( Rprev );
55 cpPluginsExtensionsQEAllIteratorsMacro( Dprev );
60 /// First order access methods
61 inline TPrimal* GetOnext( )
62 { return( this->m_Onext ); }
63 inline TDual* GetRot( )
64 { return( this->m_Rot ); }
65 inline const TPrimal* GetOnext( ) const
66 { return( this->m_Onext ); }
67 inline const TDual* GetRot( ) const
68 { return( this->m_Rot ); }
70 /// First order configuration methods
71 inline void SetOnext( TPrimal* e )
72 { this->m_Onext = e; }
73 inline void SetRot( TDual* e )
76 /// Second order accessors: around base rings
77 inline TPrimal* GetSym( )
78 { return( this->m_Rot->m_Rot ); }
79 inline TDual* GetInvRot( )
80 { return( this->m_Rot->m_Rot->m_Rot ); }
82 /// Second order accessors: neighboring topology
83 inline TPrimal* GetLnext( )
84 { return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot ); }
85 inline TPrimal* GetRnext( )
86 { return( this->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot ); }
87 inline TPrimal* GetDnext( )
88 { return( this->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot ); }
89 inline TPrimal* GetOprev( )
90 { return( this->m_Rot->m_Onext->m_Rot ); }
91 inline TPrimal* GetLprev( )
92 { return( this->m_Onext->m_Rot->m_Rot ); }
93 inline TPrimal* GetRprev( )
94 { return( this->m_Rot->m_Rot->m_Onext ); }
95 inline TPrimal* GetDprev( )
97 return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot );
100 /// Second order accessors: around base rings (const versions)
101 inline const TPrimal* GetSym( ) const
102 { return( this->m_Rot->m_Rot ); }
103 inline const TDual* GetInvRot( ) const
104 { return( this->m_Rot->m_Rot->m_Rot ); }
106 /// Second order accessors: neighboring topology (const versions)
107 inline const TPrimal* GetLnext( ) const
108 { return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot ); }
109 inline const TPrimal* GetRnext( ) const
110 { return( this->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot ); }
111 inline const TPrimal* GetDnext( ) const
112 { return( this->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot ); }
113 inline const TPrimal* GetOprev( ) const
114 { return( this->m_Rot->m_Onext->m_Rot ); }
115 inline const TPrimal* GetLprev( ) const
116 { return( this->m_Onext->m_Rot->m_Rot ); }
117 inline const TPrimal* GetRprev( ) const
118 { return( this->m_Rot->m_Rot->m_Onext ); }
119 inline const TPrimal* GetDprev( ) const
121 return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot );
124 /// Get geometry methods
125 inline P& GetOrigin( )
126 { return ( this->m_Origin ); }
127 inline P& GetDestination( )
128 { return ( this->m_Rot->m_Rot->m_Origin ); }
129 inline D& GetRight( )
130 { return ( this->m_Rot->m_Origin ); }
132 { return ( this->m_Rot->m_Rot->m_Rot->m_Origin ); }
134 /// Get geometry methods (const versions)
135 inline const P& GetOrigin( ) const
136 { return ( this->m_Origin ); }
137 inline const P& GetDestination( ) const
138 { return ( this->m_Rot->m_Rot->m_Origin ); }
139 inline const D& GetRight( ) const
140 { return ( this->m_Rot->m_Origin ); }
141 inline const D& GetLeft( ) const
142 { return ( this->m_Rot->m_Rot->m_Rot->m_Origin ); }
144 /// Set geometry methods
145 inline void SetOrigin( const P& v )
146 { this->m_Origin = v; }
147 inline void SetDestination( const P& v )
148 { this->m_Rot->m_Rot->m_Origin = v; }
149 inline void SetRight( const D& v )
150 { this->m_Rot->m_Origin = v; }
151 inline void SetLeft( const D& v )
152 { this->m_Rot->m_Rot->m_Rot->m_Origin = v; }
153 inline void UnsetOrigin( )
154 { this->m_Origin = TPrimal::NoGeometry; }
155 inline void UnsetDestination( )
156 { this->m_Rot->m_Rot->m_Origin = TPrimal::NoGeometry; }
157 inline void UnsetRight( )
158 { this->m_Rot->m_Origin = TDual::NoGeometry; }
159 inline void UnsetLeft( )
160 { this->m_Rot->m_Rot->m_Rot->m_Origin = TDual::NoGeometry; }
163 * Set the Left( ) of all the edges in the Lnext( ) ring of "this"
164 * with the same given geometrical information.
165 * @param faceGeom Looks at most maxSize edges in the Lnext( ) ring.
166 * @return Returns true on success. False otherwise.
168 void SetLnextRingGeometry( const D& v );
169 void UnsetLnextRingGeometry( );
171 /// Topological queries
172 inline bool IsIsolated( ) const
173 { return( this == this->m_Onext ); }
174 bool IsEdgeInOnextRing( const TPrimal* e ) const;
175 bool IsEdgeInLnextRing( const TPrimal* e ) const;
176 unsigned int GetOnextRingSize( ) const;
177 unsigned int GetLnextRingSize( ) const;
180 * @return Returns true when "this" has no faces set on both sides.
181 * Return false otherwise.
183 inline bool IsWire( )
184 { return( !( this->IsLeftSet( ) ) && !( this->IsRightSet( ) ) ); }
187 * @return Returns true when "this" is on the boundary i.e.
188 * one and only one of the faces is set. Return false
191 inline bool IsAtBorder( ) const;
194 * @return Returns true when "this" has faces set on both sides.
195 * Return false otherwise.
197 inline bool IsInternal( ) const
198 { return ( this->IsLeftSet( ) && this->IsRightSet( ) ); }
200 /// Geometrical queries
201 inline bool IsOriginSet( ) const
202 { return ( this->m_Origin != Self::NoGeometry ); }
203 inline bool IsDestinationSet( ) const
204 { return ( this->m_Rot->m_Rot->IsOriginSet( ) ); }
205 inline bool IsRightSet( ) const
206 { return ( this->m_Rot->IsOriginSet( ) ); }
207 inline bool IsLeftSet( ) const
208 { return ( this->m_Rot->m_Rot->m_Rot->IsOriginSet( ) ); }
211 * \brief Check wether edge's Origin is internal to the mesh (as
212 * opposed to being on the boundary) by looking if all the edges
213 * in the Onext() ring have a face set on both their Left() and
216 bool IsOriginInternal( ) const;
219 * Definition: an edge is said to be a boundary edge when it is
220 * adjacent to i.e. when at least one of the faces edge->GetLeft() or
221 * edge->GetRight() is unset. Definition: an point is said to be a
222 * boundary point when at least one of the edges of it's Onext() ring
223 * is a boundary edge.
225 * Assume "this" edge belongs to a triangulation (i.e. it belongs to a
226 * QEMesh which represents a 2-manifold) which possesses a boundary.
227 * Assume "this" edge instance is a boundary edge. Let us denote by P
228 * the point which is the origin of "this" edge i.e. P is
229 * this->Origin(). By definition P is a boundary point. Then AT
230 * LEAST two [see the note below] edges of the Onext() ring of P
231 * [which all have the point P as Origin()] are themselves boundary
232 * edges. And among those boundary edges AT LEAST one has it's Left()
233 * face unset. By iterating over the Onext() ring (which defines a
234 * local ordering on edges) this method searches for the first edge
235 * whose Left() face is unset AND which is encountered AFTER edgeTest.
237 * @param edgeTest When present, this edge will be considered as
238 * the entry edge in the Onext() ring. When absent it shall
239 * be defaulted to "this" edge. (see the warning below).
240 * @return When "this" edge is a boundary edge, return the first
241 * edge in "this" Onext() ring whose Left() face is unset
242 * AND located after edgeTest.
243 * When "this" edge is NOT a boundary edge the 0 is
245 * @warning When the Mesh possessing "this" edge is a 2-manifold
246 * then result of this method is unique in the sense that
247 * it is independent from the edgeTest parameter.
248 * But when the Mesh is not 2-manifold (this state can
249 * happen at intermediary stages of the building process,
250 * or during "surgical" operations on the Mesh, and
251 * even though the Mesh represents a triangulation)
252 * the result of this method is not unique in the sense
253 * that the result depends on the edgeTest parameter.
254 * Let us illusatre this dependence by considering a
255 * Mesh (which is a triangulation) which is not a 2-manifold.
256 * Assume the point P (the origin of "this" edge i.e.
257 * P = this->Originv()) is TWICE on the border i.e. it
258 * is adjacent twice to noface. We can consider the situation
259 * of the following diagram, which depicts some Onext()
260 * ring around point P:
264 * i3 b2 counter-clockwise //
265 * * \ / NO FACE Onext() order. //
267 * ----b4-----P----b1------ //
270 * / | \ * <------ a * indicates the //
271 * / | \ the presence of a face //
277 * On this example, and if we assume the Onext() oder is
278 * represented counter-clockwise, the edges are ordered as
280 * b1, b2, i3, b4, b5, i6, i7
281 * (when arbitrarily starting at edge b1).
282 * We have four Boundary edges labeled b1, b2, b4, b5 and
283 * we have three internal edges (i.e. non boundary edges)
284 * labeled i3, i6 and i7.
285 * Depending on edgeTest, the result of this method
286 * will NOT return the same edge:
287 * - when edgeTest == b5 (or i6 or i7 or b1) then the edge
288 * b1 will be returned,
289 * - when edgeTest == b2 (or i3 or b4) then the edge
290 * b4 will be returned,
291 * Eventually, when edgeTest is absent, the result shall
292 * depend on the position of "this" in the Onext() ring().
295 TPrimal* GetNextBorderEdgeWithUnsetLeft( TPrimal* edge = NULL ) const;
298 * Assume "this->Originv()" is a boundary point P that is thrice
299 * adjacent to noface and consider the given situation is the one
300 * depicted by the following diagram where:
301 * - P is "this->Originv()" instance,
302 * - the * (star) indicates the presence of a face,
303 * - b1, b2, b3, b4, b5, b6 denote boundary edges,
304 * - p denotes some generic point,
305 * - A and B denote some specific points we want to discuss,
306 * - the Onext() ring order is represented counter-clockwise
307 * [which is coherent with the definition of edge->GetRigth()]
308 * i.e. the ordering of the edges is:
309 * b1, b2, b3, b4, b5, b6, b1...
314 * / \ F / \ counter-clockwise //
315 * / b3 A b2 \ Onext() ring order //
319 * A------b4------P------b1-------B //
322 * NO FACE / \ NO FACE //
327 * p---------------p //
329 * At P this Mesh doesn't represent a 2-manifold (since we are thrice
330 * on the boundary). Nevertheless such a situation could arise in
331 * intermediary stages (e.g. when building the Mesh, or during
332 * surgical changes on the Mesh).
333 * Now, assume we are asked to build the triangle [P, A, B]. Note
334 * that this request is not absurd since the current situation at
335 * P isn't the one of a 2-manifold: hence when building the current
336 * Onext() ring of P, we had not enough information to decide
337 * wheter b4.Onext() should be b5 or b1. It is ONLY when we are
338 * required to build the triangle [P, A, B] that we have the
339 * additional information that b4.Onext() is indeed b1.
340 * When we are required to build triangle [P, A, B], we hence
341 * need to change the Onext() ring order at P, i.e. we need to deal
342 * with the triangle [P, b5, b6] which currently prevents
343 * b4.Onext() to be b1. In other terms, when considering the
344 * additional information that b4.Onext() is b1, and before
345 * building the triangle [P, A, B], we need to reorder
346 * the Onext() ring of P from it's current state
347 * b1, b2, b3, b4, b5, b6, b1...
348 * to an order coherent with the [P, A, B] request, i.e.
349 * b1, b2, b5, b6, b3, b4, b1...
351 * In order to establish the "proper" Onext() ring at P we use
352 * two Splice operations. The algorithm goes:
353 * - first disconnect the piece of the surface containing the edge
354 * [PB] (it would be the same process if we chose [PA]) from
355 * the Onext() ring at P.
356 * - second, re-integrate the disconnected piece at the desired
357 * location i.e. side by side with [PA] (respectively [PB] if
358 * we chose [PA] at first stage).
359 * By "piece of surface containing the edge [PB]" we mean [all]
360 * the triangle[s] starting at [PB] in the Onext() order and
361 * having a left face set.
363 * We can illustrate this process on bit more general diagram than
364 * the last case (where the "piece of surface containing the edge
365 * [PB]" is constituted by two triangles) and when using
366 * the arguments of this method (i.e. [PA] = this and [PB] = second).
367 * The initial stage is the following (we note first=this=[PA] and
368 * second=[PB]) where the Onext() ring order is:
369 * first, b2, b3, second, b5, bsplice, b7, first...
374 * / \ F / \ counter-clockwise //
375 * / b2 A first \ Onext() ring order //
379 * p-------b3------P------b7-------p //
382 * NO FACE / | \ NO FACE //
384 * second b5 bsplice //
387 * B-------p-------p //
389 * The first stage, implemented as
390 * second->Oprev()->Splice( bsplice ),
391 * yields the following diagram:
396 * / \ A / \ counter-clockwise //
397 * / b2 C first \ Onext() ring order //
401 * p-------b3------P------b7-------p //
409 * second b5 bsplice //
412 * B-------p-------p //
414 * and the second stage, implemented as
415 * first->Splice( bsplice ),
416 * yields the following diagram:
421 * | \__ / \ counter- //
422 * | second first \ clockwise for all //
426 * p-------b5---------P------b7-------p //
437 inline static bool ReorderOnextRing( TPrimal* first, TPrimal* second );
440 * \brief Basic quad-edge topological method.
442 * This method describes all possible topological operations on an
443 * edge since it is its own inverse. It works in two ways:
445 * 1. If this->m_Org != b->m_Org, it slice a face in two.
446 * 2. If this->m_Org == b->m_Org, it unifies two faces.
448 inline static void Splice( TPrimal* a, TPrimal* b );
452 virtual ~QuadEdge( );
455 static const TPrimalGeometry NoGeometry;
458 Pointer m_Onext; /**< Onext ring */
459 PtrDual m_Rot; /**< Rot ring */
460 TPrimalGeometry m_Origin; /**< Geometry attached to edge's origin */
469 #include <cpPlugins/Extensions/DataStructures/QuadEdge.hxx>
471 #endif // __CPPLUGINS__EXTENSIONS__DATASTRUCTURES__QUADEDGE__H__