1 /*=========================================================================
2  *
3  *  Copyright Insight Software Consortium
4  *
5  *  Licensed under the Apache License, Version 2.0 (the "License");
6  *  you may not use this file except in compliance with the License.
7  *  You may obtain a copy of the License at
8  *
9  *         http://www.apache.org/licenses/LICENSE-2.0.txt
10  *
11  *  Unless required by applicable law or agreed to in writing, software
12  *  distributed under the License is distributed on an "AS IS" BASIS,
13  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  *  See the License for the specific language governing permissions and
15  *  limitations under the License.
16  *
17  *=========================================================================*/
18 #ifndef itkQuadEdgeMesh_h
19 #define itkQuadEdgeMesh_h
20 
21 #include <cstdarg>
22 #include <queue>
23 #include <vector>
24 #include <list>
25 
26 #include "itkMesh.h"
27 
28 #include "itkQuadEdgeMeshTraits.h"
29 #include "itkQuadEdgeMeshLineCell.h"
30 #include "itkQuadEdgeMeshPolygonCell.h"
31 
32 #include "itkQuadEdgeMeshFrontIterator.h"
33 #include "itkConceptChecking.h"
34 
35 
36 namespace itk
37 {
38 /**
39  * \class QuadEdgeMesh
40  *
41  * \brief Mesh class for 2D manifolds embedded in ND space.
42  *
43  * \author Alexandre Gouaillard, Leonardo Florez-Valencia, Eric Boix
44  *
45  * This implementation was contributed as a paper to the Insight Journal
46  * https://hdl.handle.net/1926/306
47  *
48  * \ingroup ITKQuadEdgeMesh
49  */
50 template< typename TPixel, unsigned int VDimension,
51           typename TTraits = QuadEdgeMeshTraits< TPixel, VDimension, bool, bool > >
52 class ITK_TEMPLATE_EXPORT QuadEdgeMesh:public Mesh< TPixel, VDimension, TTraits >
53 {
54 public:
55   ITK_DISALLOW_COPY_AND_ASSIGN(QuadEdgeMesh);
56 
57   /** Input template parameters. */
58   using Traits = TTraits;
59   using PixelType = TPixel;
60 
61   /** Standard type alias. */
62   using Self = QuadEdgeMesh;
63   using Superclass = Mesh< TPixel, VDimension, Traits >;
64   using Pointer = SmartPointer< Self >;
65   using ConstPointer = SmartPointer< const Self >;
66 
67   /** Convenient constants obtained from MeshTraits. */
68   static constexpr unsigned int PointDimension = Traits::PointDimension;
69   static constexpr unsigned int MaxTopologicalDimension = Traits::MaxTopologicalDimension;
70 
71   /** Types defined in superclass. */
72   using CellPixelType = typename Superclass::CellPixelType;
73   using CoordRepType = typename Superclass::CoordRepType;
74   using PointIdentifier = typename Superclass::PointIdentifier;
75   using PointHashType = typename Superclass::PointHashType;
76   using PointType = typename Superclass::PointType;
77   using CellTraits = typename Superclass::CellTraits;
78 
79   using PointIdInternalIterator = typename CellTraits::PointIdInternalIterator;
80   using PointIdIterator = typename CellTraits::PointIdIterator;
81 
82   // Point section:
83   using PointsContainer = typename Superclass::PointsContainer;
84   using PointsContainerPointer = typename Superclass::PointsContainerPointer;
85   typedef CoordRepType CoordRepArrayType[Self::PointDimension];
86 
87   // Point data section:
88   using PointDataContainer = typename Superclass::PointDataContainer;
89   using PointDataContainerPointer = typename Superclass::PointDataContainerPointer;
90   using PointDataContainerIterator = typename Superclass::PointDataContainerIterator;
91   using PointsContainerConstIterator = typename Superclass::PointsContainerConstIterator;
92   using PointsContainerIterator = typename Superclass::PointsContainerIterator;
93 
94   // Cell section:
95   using CellIdentifier = typename Superclass::CellIdentifier;
96   using CellType = typename Superclass::CellType;
97   using CellAutoPointer = typename Superclass::CellAutoPointer;
98   using CellFeatureIdentifier = typename Superclass::CellFeatureIdentifier;
99   using CellFeatureCount = typename Superclass::CellFeatureCount;
100   using CellMultiVisitorType = typename Superclass::CellMultiVisitorType;
101   using CellsContainer = typename Superclass::CellsContainer;
102   using CellsContainerPointer = typename Superclass::CellsContainerPointer;
103 
104   using CellsContainerConstIterator = typename Superclass::CellsContainerConstIterator;
105   using CellsContainerIterator = typename Superclass::CellsContainerIterator;
106 
107   using CellLinksContainer = typename Superclass::CellLinksContainer;
108   using CellLinksContainerPointer = typename Superclass::CellLinksContainerPointer;
109   using CellLinksContainerIterator = typename Superclass::CellLinksContainerIterator;
110 
111   // Cell data section:
112   using CellDataContainer = typename Superclass::CellDataContainer;
113   using CellDataContainerPointer = typename Superclass::CellDataContainerPointer;
114   using CellDataContainerIterator = typename Superclass::CellDataContainerIterator;
115 
116   // Point / Cell correspondance section:
117   using PointCellLinksContainer = typename Superclass::PointCellLinksContainer;
118   using PointCellLinksContainerIterator = typename Superclass::PointCellLinksContainerIterator;
119 
120   // BoundaryAssignMents section:
121   using BoundaryAssignmentsContainer = typename Superclass::BoundaryAssignmentsContainer;
122   using BoundaryAssignmentsContainerPointer = typename Superclass::BoundaryAssignmentsContainerPointer;
123   using BoundaryAssignmentsContainerVector = typename Superclass::BoundaryAssignmentsContainerVector;
124 
125   // Miscellaneous section:
126   using BoundingBoxPointer = typename Superclass::BoundingBoxPointer;
127   using BoundingBoxType = typename Superclass::BoundingBoxType;
128   using RegionType = typename Superclass::RegionType;
129   using InterpolationWeightType = typename Superclass::InterpolationWeightType;
130 
131   /** Specific types for a quad-edge structure. */
132   using PrimalDataType = typename Traits::PrimalDataType;
133   using DualDataType = typename Traits::DualDataType;
134   using QEPrimal = typename Traits::QEPrimal;
135   using QEDual = typename Traits::QEDual;
136   using QEType = typename Traits::QEPrimal;
137   // See the TODO entry dated from 2005-05-28
138   // struct QEType : public QEPrimal, public QEDual {}
139   using VertexRefType = typename Traits::VertexRefType;
140   using FaceRefType = typename Traits::FaceRefType;
141   using VectorType = typename Traits::VectorType;
142 
143   /** Possible specialized cell types. */
144   using EdgeCellType = QuadEdgeMeshLineCell< CellType >;
145   using PolygonCellType = QuadEdgeMeshPolygonCell< CellType >;
146 
147   /** Free insertion indexes. */
148   using FreePointIndexesType = std::queue< PointIdentifier >;
149   using FreeCellIndexesType = std::queue< CellIdentifier >;
150 
151   /** Auxiliary types. */
152   using PointIdList = std::vector< PointIdentifier >;
153   using EdgeListType = std::list< QEPrimal * >;
154   using EdgeListPointerType = EdgeListType *;
155 
156   /** Reserved PointIdentifier designated to represent the absence of Point */
157   static const PointIdentifier m_NoPoint;
158 
159   /** Reserved CellIdentifier designated to represent the absence of Face */
160   static const CellIdentifier m_NoFace;
161 
162 public:
163 
164   /** Basic Object interface. */
165   itkNewMacro(Self);
166   itkTypeMacro(QuadEdgeMesh, Mesh);
167 
168 #if !defined( ITK_WRAPPING_PARSER )
169   /** FrontIterator definitions */
170   itkQEDefineFrontIteratorMethodsMacro(Self);
171 #endif
172 
173 public:
174 
175   // Multithreading framework: not tested yet.
RequestedRegionIsOutsideOfTheBufferedRegion()176   bool RequestedRegionIsOutsideOfTheBufferedRegion() override
177   {
178     return ( false );
179   }
180 
181   void Initialize() override;
182 
183   /** another way of deleting all the cells */
184   virtual void Clear();
185 
GetEdgeCells()186   CellsContainer * GetEdgeCells() { return m_EdgeCellsContainer; }
GetEdgeCells()187   const CellsContainer * GetEdgeCells() const { return m_EdgeCellsContainer; }
SetEdgeCells(CellsContainer * edgeCells)188   void SetEdgeCells(CellsContainer *edgeCells)
189   { m_EdgeCellsContainer = edgeCells; }
SetEdgeCell(CellIdentifier cellId,CellAutoPointer & cellPointer)190   void SetEdgeCell(CellIdentifier cellId, CellAutoPointer & cellPointer)
191   { m_EdgeCellsContainer->InsertElement( cellId, cellPointer.ReleaseOwnership() ); }
192 
193   /** Overloaded to avoid a bug in Mesh that prevents proper inheritance
194    * Refer to
195    * http://public.kitware.com/pipermail/insight-users/2005-March/012459.html
196    * and
197    * http://public.kitware.com/pipermail/insight-users/2005-April/012613.html
198    */
CopyInformation(const DataObject * data)199   void CopyInformation(const DataObject *data) override { (void)data; }
200   void Graft(const DataObject *data) override;
201 
202   /** squeeze the point container to be able to write the file properly */
203   void SqueezePointsIds();
204 
205   /** overloaded method for backward compatibility */
BuildCellLinks()206   void BuildCellLinks() {}
207 
208 #if !defined( ITK_WRAPPING_PARSER )
209   /** overloaded method for backward compatibility */
SetBoundaryAssignments(int dimension,BoundaryAssignmentsContainer * container)210   void SetBoundaryAssignments(int dimension,
211                               BoundaryAssignmentsContainer *container)
212   {
213     (void)dimension;
214     (void)container;
215   }
216 
217   /** overloaded method for backward compatibility */
GetBoundaryAssignments(int dimension)218   BoundaryAssignmentsContainerPointer GetBoundaryAssignments(int dimension)
219   {
220     (void)dimension;
221     return ( nullptr );
222   }
223 
224   /** overloaded method for backward compatibility */
GetBoundaryAssignments(int dimension)225   const BoundaryAssignmentsContainerPointer GetBoundaryAssignments(
226     int dimension) const
227   {
228     (void)dimension;
229     return ( nullptr );
230   }
231 
232 #endif
233 
234   /** overloaded method for backward compatibility */
SetBoundaryAssignment(int dimension,CellIdentifier cellId,CellFeatureIdentifier featureId,CellIdentifier boundaryId)235   void SetBoundaryAssignment(int dimension, CellIdentifier cellId,
236                              CellFeatureIdentifier featureId,
237                              CellIdentifier boundaryId)
238   {
239     (void)dimension;
240     (void)cellId;
241     (void)featureId;
242     (void)boundaryId;
243   }
244 
245   /** overloaded method for backward compatibility */
GetBoundaryAssignment(int dimension,CellIdentifier cellId,CellFeatureIdentifier featureId,CellIdentifier * boundaryId)246   bool GetBoundaryAssignment(int dimension, CellIdentifier cellId,
247                              CellFeatureIdentifier featureId,
248                              CellIdentifier *boundaryId) const
249   {
250     (void)dimension;
251     (void)cellId;
252     (void)featureId;
253     (void)boundaryId;
254     return ( false ); // ALEX: is it the good way?
255   }
256 
257   /** overloaded method for backward compatibility */
RemoveBoundaryAssignment(int dimension,CellIdentifier cellId,CellFeatureIdentifier featureId)258   bool RemoveBoundaryAssignment(int dimension, CellIdentifier cellId,
259                                 CellFeatureIdentifier featureId)
260   {
261     (void)dimension;
262     (void)cellId;
263     (void)featureId;
264     return ( false ); // ALEX: is it the good way?
265   }
266 
267   /** overloaded method for backward compatibility */
GetCellBoundaryFeature(int dimension,CellIdentifier cellId,CellFeatureIdentifier featureId,CellAutoPointer & cellAP)268   bool GetCellBoundaryFeature(int dimension, CellIdentifier cellId,
269                               CellFeatureIdentifier featureId,
270                               CellAutoPointer & cellAP) const
271   {
272     (void)dimension;
273     (void)cellId;
274     (void)featureId;
275     (void)cellAP;
276     return ( false );
277   }
278 
279   /** overloaded method for backward compatibility */
GetCellBoundaryFeatureNeighbors(int dimension,CellIdentifier cellId,CellFeatureIdentifier featureId,std::set<CellIdentifier> * cellSet)280   CellIdentifier GetCellBoundaryFeatureNeighbors(int dimension,
281                                                 CellIdentifier cellId,
282                                                 CellFeatureIdentifier featureId,
283                                                 std::set< CellIdentifier > *cellSet)
284   {
285     (void)dimension;
286     (void)cellId;
287     (void)featureId;
288     (void)cellSet;
289     return NumericTraits<CellIdentifier>::ZeroValue();
290   }
291 
292   /** NOTE ALEX: this method do not use CellFeature and thus could be recoded */
GetCellNeighbors(CellIdentifier itkNotUsed (cellId),std::set<CellIdentifier> * itkNotUsed (cellSet))293   CellIdentifier GetCellNeighbors(CellIdentifier itkNotUsed(cellId),
294                                  std::set< CellIdentifier > * itkNotUsed(cellSet))
295   {
296     return NumericTraits<CellIdentifier>::ZeroValue();
297   }
298 
299   /** overloaded method for backward compatibility */
GetAssignedCellBoundaryIfOneExists(int dimension,CellIdentifier cellId,CellFeatureIdentifier featureId,CellAutoPointer & cellAP)300   bool GetAssignedCellBoundaryIfOneExists(int dimension,
301                                           CellIdentifier cellId,
302                                           CellFeatureIdentifier featureId,
303                                           CellAutoPointer & cellAP) const
304   {
305     (void)dimension;
306     (void)cellId;
307     (void)featureId;
308     (void)cellAP;
309     return ( false ); // ALEX: is it the good way?
310   }
311 
312   /** overloaded method for backward compatibility */
313   void SetCell(CellIdentifier cId, CellAutoPointer & cell);
314 
315   /** Methods to simplify point/edge insertion/search. */
316   virtual PointIdentifier FindFirstUnusedPointIndex();
317 
318   virtual CellIdentifier  FindFirstUnusedCellIndex();
319 
320   virtual void PushOnContainer(EdgeCellType *newEdge);
321 
322   // Adding Point/Edge/Face methods
323   virtual PointIdentifier AddPoint(const PointType & p);
324 
325   /** */
326   virtual QEPrimal * AddEdge(const PointIdentifier & orgPid,
327                              const PointIdentifier & destPid);
328 
329   virtual QEPrimal * AddEdgeWithSecurePointList(const PointIdentifier & orgPid,
330                                                 const PointIdentifier & destPid);
331 
332   /** Add a polygonal face to the Mesh, suppose QE layer ready */
333   virtual void      AddFace(QEPrimal *e);
334 
335   /** Add a polygonal face to the Mesh. The list of points
336    * is expected to be ordered counter-clock wise. The inside
337    * of the new face will be on the left side of the edges
338    * formed by consecutive points in this list. */
339   virtual QEPrimal * AddFace(const PointIdList & points);
340 
341   virtual QEPrimal * AddFaceWithSecurePointList(const PointIdList & points);
342 
343   virtual QEPrimal * AddFaceWithSecurePointList(const PointIdList & points,
344                                                 bool CheckEdges);
345 
346   /** Adds a triangular face to the Mesh */
347   virtual QEPrimal * AddFaceTriangle(const PointIdentifier & aPid,
348                                      const PointIdentifier & bPid,
349                                      const PointIdentifier & cPid);
350 
351   /** Deletion methods */
352   virtual void DeletePoint(const PointIdentifier & pid);
353 
354   virtual void DeleteEdge(const PointIdentifier & orgPid,
355                           const PointIdentifier & destPid);
356 
357   virtual void DeleteEdge(QEPrimal *e);
358 
359   virtual void LightWeightDeleteEdge(EdgeCellType *e);
360 
361   virtual void LightWeightDeleteEdge(QEPrimal *e);
362 
363   virtual void DeleteFace(FaceRefType faceToDelete);
364 
365   //
GetPoint(PointIdentifier pid,PointType * pt)366   bool GetPoint(PointIdentifier pid, PointType *pt) const
367   {
368     return ( Superclass::GetPoint(pid, pt) );
369   }
370 
371   virtual PointType  GetPoint(const PointIdentifier & pid) const;
372 
373   virtual VectorType GetVector(const PointIdentifier & pid) const;
374 
375   virtual QEPrimal *  GetEdge() const;
376 
377   virtual QEPrimal *  GetEdge(const CellIdentifier & eid) const;
378 
379   virtual QEPrimal *  FindEdge(const PointIdentifier & pid0) const;
380 
381   virtual QEPrimal *  FindEdge(const PointIdentifier & pid0,
382                                const PointIdentifier & pid1) const;
383 
384   virtual EdgeCellType *  FindEdgeCell(const PointIdentifier & pid0,
385                                        const PointIdentifier & pid1) const;
386 
387   ///  Compute the euclidian length of argument edge
388   CoordRepType ComputeEdgeLength(QEPrimal *e);
389 
390   PointIdentifier ComputeNumberOfPoints() const;
391 
392   CellIdentifier ComputeNumberOfFaces() const;
393 
394   CellIdentifier ComputeNumberOfEdges() const;
395 
396   PointIdentifier Splice(QEPrimal *a, QEPrimal *b);
397 
398 #ifdef ITK_USE_CONCEPT_CHECKING
399   // Begin concept checking
400   // End concept checking
401 #endif
402 
403   // for reusability of a mesh in the MeshToMesh filter
ClearFreePointAndCellIndexesLists()404   void ClearFreePointAndCellIndexesLists()
405   {
406     while ( !this->m_FreePointIndexes.empty() )
407       {
408       this->m_FreePointIndexes.pop();
409       }
410     while ( !this->m_FreeCellIndexes.empty() )
411       {
412       this->m_FreeCellIndexes.pop();
413       }
414   }
415 
GetNumberOfFaces()416   CellIdentifier GetNumberOfFaces() const { return ( m_NumberOfFaces ); }
GetNumberOfEdges()417   CellIdentifier GetNumberOfEdges() const { return ( m_NumberOfEdges ); }
418 
419 protected:
420   /** Constructor and Destructor. */
421   QuadEdgeMesh();
422   ~QuadEdgeMesh() override;
423 
424   /** Release the memory of each one of the cells independently. */
425   virtual void ClearCellsContainer();
426 
427   CellsContainerPointer m_EdgeCellsContainer;
428 
429 private:
430   CellIdentifier m_NumberOfFaces;
431   CellIdentifier m_NumberOfEdges;
432 
433 protected:
434   FreePointIndexesType m_FreePointIndexes;
435   FreeCellIndexesType  m_FreeCellIndexes;
436 };
437 }
438 
439 #ifndef ITK_MANUAL_INSTANTIATION
440 #include "itkQuadEdgeMesh.hxx"
441 #endif
442 
443 #endif
444