]> Creatis software - cpMesh.git/blob - lib/cpm/DataStructures/QuadEdge.h
f383d5e2b0c1d6327081da98dbd46e3ee77fcd2c
[cpMesh.git] / lib / cpm / DataStructures / QuadEdge.h
1 #ifndef __CPM__DATASTRUCTURES__QUADEDGE__H__
2 #define __CPM__DATASTRUCTURES__QUADEDGE__H__
3
4 #include <itkLightObject.h>
5 #include <cpm/DataStructures/QuadEdgeIterators.h>
6
7 namespace cpm
8 {
9   namespace DataStructures
10   {
11     /**
12      */
13     template< typename P, typename D, bool IsPrimal = true >
14     class QuadEdge
15       : public itk::LightObject
16     {
17     public:
18       typedef QuadEdge                        Self;
19       typedef itk::LightObject                Superclass;
20       typedef itk::SmartPointer< Self >       Pointer;
21       typedef itk::SmartPointer< const Self > ConstPointer;
22
23       /// Vertices and faces types
24       typedef P TPrimalGeometry;
25       typedef D TDualGeometry;
26
27       /**
28        * Dual type, basically the same type with swapped template
29        * parameters.
30        */
31       typedef QuadEdge< D, P, !IsPrimal > TDual;
32       typedef Self                        TPrimal;
33       typedef typename TDual::Pointer     PtrDual;
34       friend TDual;
35
36       /// Iterators
37       typedef QuadEdgeIterator< TPrimal >           Iterator;
38       typedef QuadEdgeConstIterator< TPrimal >      ConstIterator;
39       typedef QuadEdgePointIterator< TPrimal >      PointIterator;
40       typedef QuadEdgePointConstIterator< TPrimal > PointConstIterator;
41
42     public:
43       itkNewMacro( Self );
44       itkTypeMacro( QuadEdge, itkLightObject );
45
46       cpmDataStructuresQEAllIteratorsMacro( Onext );
47       cpmDataStructuresQEAllIteratorsMacro( Lnext );
48       cpmDataStructuresQEAllIteratorsMacro( Rnext );
49       cpmDataStructuresQEAllIteratorsMacro( Dnext );
50       cpmDataStructuresQEAllIteratorsMacro( Oprev );
51       cpmDataStructuresQEAllIteratorsMacro( Lprev );
52       cpmDataStructuresQEAllIteratorsMacro( Rprev );
53       cpmDataStructuresQEAllIteratorsMacro( Dprev );
54
55     public:
56       void CreateRings( );
57
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 ); }
67
68       /// First order configuration methods
69       inline void SetOnext( TPrimal* e )
70         { this->m_Onext = e; }
71       inline void SetRot( TDual* e )
72         { this->m_Rot = e; }
73
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 ); }
79
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( )
94         { return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot ); }
95
96       /// Second order accessors: around base rings (const versions)
97       inline const TPrimal* GetSym( ) const
98         { return( this->m_Rot->m_Rot ); }
99       inline const TDual* GetInvRot( ) const
100         { return( this->m_Rot->m_Rot->m_Rot ); }
101
102       /// Second order accessors: neighboring topology (const versions)
103       inline const TPrimal* GetLnext( ) const
104         { return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot ); }
105       inline const TPrimal* GetRnext( ) const
106         { return( this->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot ); }
107       inline const TPrimal* GetDnext( ) const
108         { return( this->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot ); }
109       inline const TPrimal* GetOprev( ) const
110         { return( this->m_Rot->m_Onext->m_Rot ); }
111       inline const TPrimal* GetLprev( ) const
112         { return( this->m_Onext->m_Rot->m_Rot ); }
113       inline const TPrimal* GetRprev( ) const
114         { return( this->m_Rot->m_Rot->m_Onext ); }
115       inline const TPrimal* GetDprev( ) const
116         { return( this->m_Rot->m_Rot->m_Rot->m_Onext->m_Rot->m_Rot->m_Rot ); }
117
118       /// Get geometry methods
119       inline P& GetOrigin( )
120         { return ( this->m_Origin ); }
121       inline P& GetDestination( )
122         { return ( this->m_Rot->m_Rot->m_Origin ); }
123       inline D& GetRight( )
124         { return ( this->m_Rot->m_Origin ); }
125       inline D& GetLeft( )
126         { return ( this->m_Rot->m_Rot->m_Rot->m_Origin ); }
127
128       /// Get geometry methods (const versions)
129       inline const P& GetOrigin( ) const
130         { return ( this->m_Origin ); }
131       inline const P& GetDestination( ) const
132         { return ( this->m_Rot->m_Rot->m_Origin ); }
133       inline const D& GetRight( ) const
134         { return ( this->m_Rot->m_Origin ); }
135       inline const D& GetLeft( ) const
136         { return ( this->m_Rot->m_Rot->m_Rot->m_Origin ); }
137
138       /// Set geometry methods
139       inline void SetOrigin( const P& v )
140         { this->m_Origin = v; }
141       inline void SetDestination( const P& v )
142         { this->m_Rot->m_Rot->m_Origin = v; }
143       inline void SetRight( const D& v )
144         { this->m_Rot->m_Origin = v; }
145       inline void SetLeft( const D& v )
146         { this->m_Rot->m_Rot->m_Rot->m_Origin = v; }
147       inline void UnsetOrigin( )
148         { this->m_Origin = TPrimal::NoGeometry; }
149       inline void UnsetDestination( )
150         { this->m_Rot->m_Rot->m_Origin = TPrimal::NoGeometry; }
151       inline void UnsetRight( )
152         { this->m_Rot->m_Origin = TDual::NoGeometry; }
153       inline void UnsetLeft( )
154         { this->m_Rot->m_Rot->m_Rot->m_Origin = TDual::NoGeometry; }
155
156       /**
157        * Set the Left( ) of all the edges in the Lnext( ) ring of "this"
158        * with the same given geometrical information.
159        * @param  faceGeom Looks at most maxSize edges in the Lnext( ) ring.
160        * @return Returns true on success. False otherwise.
161        */
162       void SetLnextRingGeometry( const D& v );
163       void UnsetLnextRingGeometry( );
164
165       /// Topological queries
166       inline bool IsIsolated( ) const
167         { return( this == this->m_Onext ); }
168       bool IsEdgeInOnextRing( const TPrimal* e ) const;
169       bool IsEdgeInLnextRing( const TPrimal* e ) const;
170       unsigned int GetOnextRingSize( ) const;
171       unsigned int GetLnextRingSize( ) const;
172
173       /**
174        * @return Returns true when "this" has no faces set on both sides.
175        *         Return false otherwise.
176        */
177       inline bool IsWire( )
178         { return( !( this->IsLeftSet( ) ) && !( this->IsRightSet( ) ) ); }
179
180       /**
181        * @return Returns true when "this" is on the boundary i.e.
182        *         one and only one of the faces is set. Return false
183        *         otherwise.
184        */
185       inline bool IsAtBorder( ) const;
186
187       /**
188        * @return Returns true when "this" has faces set on both sides.
189        *         Return false otherwise.
190        */
191       inline bool IsInternal( ) const
192         { return ( this->IsLeftSet( ) && this->IsRightSet( ) ); }
193
194       /// Geometrical queries
195       inline bool IsOriginSet( ) const
196         { return ( this->m_Origin != Self::NoGeometry ); }
197       inline bool IsDestinationSet( ) const
198         { return ( this->m_Rot->m_Rot->IsOriginSet( ) ); }
199       inline bool IsRightSet( ) const
200         { return ( this->m_Rot->IsOriginSet( ) ); }
201       inline bool IsLeftSet( ) const
202         { return ( this->m_Rot->m_Rot->m_Rot->IsOriginSet( ) ); }
203
204       /**
205        * \brief Check wether edge's Origin is internal to the mesh (as
206        * opposed to being on the boundary) by looking if all the edges
207        * in the Onext() ring have a face set on both their Left() and
208        * Right() side.
209        */
210       bool IsOriginInternal( ) const;
211
212       /**
213        * Definition: an edge is said to be a boundary edge when it is
214        * adjacent to i.e. when at least one of the faces edge->GetLeft() or
215        * edge->GetRight() is unset.  Definition: an point is said to be a
216        * boundary point when at least one of the edges of it's Onext() ring
217        * is a boundary edge.
218        *
219        * Assume "this" edge belongs to a triangulation (i.e. it belongs to a
220        * QEMesh which represents a 2-manifold) which possesses a boundary.
221        * Assume "this" edge instance is a boundary edge. Let us denote by P
222        * the point which is the origin of "this" edge i.e. P is
223        * this->Origin().  By definition P is a boundary point.  Then AT
224        * LEAST two [see the note below] edges of the Onext() ring of P
225        * [which all have the point P as Origin()] are themselves boundary
226        * edges. And among those boundary edges AT LEAST one has it's Left()
227        * face unset.  By iterating over the Onext() ring (which defines a
228        * local ordering on edges) this method searches for the first edge
229        * whose Left() face is unset AND which is encountered AFTER edgeTest.
230        *
231        * @param edgeTest When present, this edge will be considered as
232        *        the entry edge in the Onext() ring. When absent it shall
233        *        be defaulted to "this" edge. (see the warning below).
234        * @return When "this" edge is a boundary edge, return the first
235        *         edge in "this" Onext() ring whose Left() face is unset
236        *         AND located after edgeTest.
237        *         When "this" edge is NOT a boundary edge the 0 is
238        *         returned.
239        * @warning When the Mesh possessing "this" edge is a 2-manifold
240        *          then result of this method is unique in the sense that
241        *          it is independent from the edgeTest parameter.
242        *          But when the Mesh is not 2-manifold (this state can
243        *          happen at intermediary stages of the building process,
244        *          or during "surgical" operations on the Mesh, and
245        *          even though the Mesh represents a triangulation)
246        *          the result of this method is not unique in the sense
247        *          that the result depends on the edgeTest parameter.
248        *          Let us illusatre this dependence by considering a
249        *          Mesh (which is a triangulation) which is not a 2-manifold.
250        *          Assume the point P (the origin of "this" edge i.e.
251        *          P = this->Originv()) is TWICE on the border i.e. it
252        *          is adjacent twice to noface. We can consider the situation
253        *          of the following diagram, which depicts some Onext()
254        *          ring around point P:
255        *
256        *                       \         /                               //
257        *                        \   *   /                                //
258        *                        i3     b2              counter-clockwise //
259        *                  *       \   /   NO FACE      Onext() order.    //
260        *                           \ /                                   //
261        *                 ----b4-----P----b1------                        //
262        *                           /|\                                   //
263        *               NO FACE    / | \                                  //
264        *                         /  |  \    *  <------ a * indicates the //
265        *                        /   |   \         the presence of a face //
266        *                       /    |    \                               //
267        *                     b5    i6     i7                             //
268        *                     /   *  |  *   \                             //
269        *                    /       |       \                            //
270        *
271        *          On this example, and if we assume the Onext() oder is
272        *          represented counter-clockwise, the edges are ordered as
273        *          follows:
274        *             b1, b2, i3, b4, b5, i6, i7
275        *          (when arbitrarily starting at edge b1).
276        *          We have four Boundary edges labeled b1, b2, b4, b5 and
277        *          we have three internal edges (i.e. non boundary edges)
278        *          labeled i3, i6 and i7.
279        *          Depending on edgeTest, the result of this method
280        *          will NOT return the same edge:
281        *            - when edgeTest == b5 (or i6 or i7 or b1) then the edge
282        *              b1 will be returned,
283        *            - when edgeTest == b2 (or i3 or b4) then the edge
284        *              b4 will be returned,
285        *          Eventually, when edgeTest is absent, the result shall
286        *          depend on the position of "this" in the Onext() ring().
287        *
288        */
289       TPrimal* GetNextBorderEdgeWithUnsetLeft( TPrimal* edge = NULL ) const;
290
291       /**
292        * Assume "this->Originv()" is a boundary point P that is thrice adjacent
293        * to noface and consider the given situation is the one depicted by
294        * the following diagram where:
295        *   - P is "this->Originv()" instance,
296        *   - the * (star) indicates the presence of a face,
297        *   - b1, b2, b3, b4, b5, b6 denote boundary edges,
298        *   - p denotes some generic point,
299        *   - A and B denote some specific points we want to discuss,
300        *   - the Onext() ring order is represented counter-clockwise
301        *     [which is coherent with the definition of edge->GetRigth()]
302        *     i.e. the ordering of the edges is:
303        *          b1, b2, b3, b4, b5, b6, b1...
304        *
305        *                    p       N       p
306        *                   / \      O      / \                            //
307        *                  /   \           /   \                           //
308        *                 /     \    F    /     \       counter-clockwise  //
309        *                /      b3   A   b2      \      Onext() ring order //
310        *               /         \  C  /         \                        //
311        *              /     *     \ E /     *     \                       //
312        *             /             \ /             \                      //
313        *             A------b4------P------b1-------B                     //
314        *                           / \                                    //
315        *                          /   \                                   //
316        *             NO FACE     /     \      NO FACE                     //
317        *                        /       \                                 //
318        *                      b5         b6                               //
319        *                      /     *     \                               //
320        *                     /             \                              //
321        *                    p---------------p                             //
322        *
323        * At P this Mesh doesn't represent a 2-manifold (since we are thrice
324        * on the boundary). Nevertheless such a situation could arise in
325        * intermediary stages (e.g. when building the Mesh, or during
326        * surgical changes on the Mesh).
327        *    Now, assume we are asked to build the triangle [P, A, B]. Note
328        * that this request is not absurd since the current situation at
329        * P isn't the one of a 2-manifold: hence when building the current
330        * Onext() ring of P, we had not enough information to decide
331        * wheter b4.Onext() should be b5 or b1. It is ONLY when we are
332        * required to build the triangle [P, A, B] that we have the
333        * additional information that b4.Onext() is indeed b1.
334        *    When we are required to build triangle [P, A, B], we hence
335        * need to change the Onext() ring order at P, i.e. we need to deal
336        * with the triangle [P, b5, b6] which currently prevents
337        * b4.Onext() to be b1. In other terms, when considering the
338        * additional information that b4.Onext() is b1, and before
339        * building the triangle [P, A, B], we need to reorder
340        * the Onext() ring of P from it's current state
341        *    b1, b2, b3, b4, b5, b6, b1...
342        * to an order coherent with the [P, A, B] request, i.e.
343        *     b1, b2, b5, b6, b3, b4, b1...
344        *
345        * In order to establish the "proper" Onext() ring at P we use
346        * two Splice operations. The algorithm goes:
347        *   - first disconnect the piece of the surface containing the edge
348        *     [PB] (it would be the same process if we chose [PA]) from
349        *     the Onext() ring at P.
350        *   - second, re-integrate the disconnected piece at the desired
351        *     location i.e. side by side with [PA] (respectively [PB] if
352        *     we chose [PA] at first stage).
353        * By "piece of surface containing the edge [PB]" we mean [all]
354        * the triangle[s] starting at [PB] in the Onext() order and
355        * having a left face set.
356        *
357        * We can illustrate this process on bit more general diagram than
358        * the last case (where the "piece of surface containing the edge
359        * [PB]" is constituted by two triangles) and when using
360        * the arguments of this method (i.e. [PA] = this and [PB] = second).
361        * The initial stage is the following (we note first=this=[PA] and
362        * second=[PB]) where the Onext() ring order is:
363        *     first, b2, b3, second, b5, bsplice, b7, first...
364        *
365        *                    p       N       A                            //
366        *                   / \      O      / \                           //
367        *                  /   \           /   \                          //
368        *                 /     \    F    /     \     counter-clockwise   //
369        *                /      b2   A  first    \    Onext() ring order  //
370        *               /         \  C  /         \                       //
371        *              /     *     \ E /     *     \                      //
372        *             /             \ /             \                     //
373        *            p-------b3------P------b7-------p                    //
374        *                           /|\                                   //
375        *                          / | \                                  //
376        *          NO FACE        /  |  \      NO FACE                    //
377        *                        /   |   \                                //
378        *                  second   b5   bsplice                          //
379        *                      /  *  |  *  \                              //
380        *                     /      |      \                             //
381        *                    B-------p-------p                            //
382        *
383        * The first stage, implemented as
384        *     second->Oprev()->Splice( bsplice ),
385        * yields the following diagram:
386        *
387        *                    p       N       A                            //
388        *                   / \      O      / \                           //
389        *                  /   \     F     /   \                          //
390        *                 /     \    A    /     \      counter-clockwise  //
391        *                /      b2   C  first    \     Onext() ring order //
392        *               /         \  E  /         \                       //
393        *              /     *     \   /     *     \                      //
394        *             /             \ /             \                     //
395        *            p-------b3------P------b7-------p                    //
396        *                                                                 //
397        *                         NO FACE                                 //
398        *                                                                 //
399        *                           /|\                                   //
400        *                          / | \                                  //
401        *                         /  |  \                                 //
402        *                        /   |   \                                //
403        *                  second   b5   bsplice                          //
404        *                      /  *  |  *  \                              //
405        *                     /      |      \                             //
406        *                    B-------p-------p                            //
407        *
408        * and the second stage, implemented as
409        *      first->Splice( bsplice ),
410        * yields the following diagram:
411        *
412        *                                    A                            //
413        *         B__        NO FACE        / \                           //
414        *         |  \__                   /   \                          //
415        *         |     \__               /     \       counter-          //
416        *         |      second         first    \      clockwise for all //
417        *         |           \__       /         \                       //
418        *         |     *        \__   /     *     \                      //
419        *         |                 \ /             \                     //
420        *         p-------b5---------P------b7-------p                    //
421        *         |               __/|\                                   //
422        *         |     *      __/   | \                                  //
423        *         |           /      |  \      NO FACE                    //
424        *         |     bsplice      |   \                                //
425        *         |   __/           b2    b3                              //
426        *         p__/               |  *  \                              //
427        *                NO FACE     |      \                             //
428        *                            p-------p                            //
429        *
430        */
431       inline static bool ReorderOnextRing( TPrimal* first, TPrimal* second );
432
433       /**
434        * \brief Basic quad-edge topological method.
435        *
436        * This method describes all possible topological operations on an
437        * edge since it is its own inverse. It works in two ways:
438        *
439        *   1. If this->m_Org != b->m_Org, it slice a face in two.
440        *   2. If this->m_Org == b->m_Org, it unifies two faces.
441        */
442       inline static void Splice( TPrimal* a, TPrimal* b );
443
444     protected:
445       QuadEdge( );
446       virtual ~QuadEdge( );
447
448     public:
449       static const TPrimalGeometry NoGeometry;
450
451     protected:
452       Pointer         m_Onext;  /**< Onext ring */
453       PtrDual         m_Rot;    /**< Rot ring */
454       TPrimalGeometry m_Origin; /**< Geometry attached to edge's origin */
455     };
456
457   } // ecapseman
458
459 } // ecapseman
460
461 #include <cpm/DataStructures/QuadEdge.hxx>
462
463 #endif // __CPM__DATASTRUCTURES__QUADEDGE__H__
464
465 // eof - $RCSfile$