ITK  4.13.0
Insight Segmentation and Registration Toolkit
itkQuadEdgeMesh.h
Go to the documentation of this file.
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 #if !defined( ITK_LEGACY_FUTURE_REMOVE )
22 # include "vcl_cstdarg.h"
23 #endif
24 #include <cstdarg>
25 #include <queue>
26 #include <vector>
27 #include <list>
28 
29 #include "itkMesh.h"
30 
31 #include "itkQuadEdgeMeshTraits.h"
34 
36 #include "itkConceptChecking.h"
37 
38 /****
39  * \brief Documentation of itkQE namespace
40  * \todo More comments here !
41  *
42  * \note Design notes: some QuadEdgeMesh algorithms are based on iterating
43  * various connectivity operators e.g. curvature driven surface deformation.
44  * Many of those connectivity altering operators (e.g. the Euler operators)
45  * are lightweight in the sense that they only modify very limited regions
46  * of a QuadEdgeMesh: they typically act within the range of couple edges of
47  * distance from a considered vertex, edge or face.
48  * On the one side, we cannot choose to implement those atomic operations
49  * as "classical" itk filters since each filter invocation yields a new
50  * copy of the input mesh as its output: this would drasticaly
51  * increase the memory consumption.
52  * In fact, those atomic operations have a too much finer grain to be
53  * implemeted as filters: the filter is more at the scale of the
54  * application of a large number of such atomic operations.
55  * One the other hand, we cannot choose to implement those atomic operations
56  * as methods of this QuadEdgeMesh class (or a derived one) at the risk of
57  * rapid code bloat.
58  * Maybe we could choose to make thematic regroupment within derived
59  * classes, but this would force an end user to multiple inheritance which
60  * can prove to be a drag in a templated context.
61  * Eventually, we chose to implement them as function object: the
62  * loosely coupling of those operation methods with the targeted QuadEdgeMesh
63  * object and heavier invocation syntax are a small price to pay in
64  * exchange for optimal memory usage and end user modularity.
65  * But we couldn't inherit from \ref FunctionBase since its
66  * Evaluate( const InputType& input ) method promises to leave its
67  * argument (the mesh we want to modify in our case) untouched.
68  * Hence we created the \ref itkQE::MeshFunctionBase class whose main
69  * difference with \ref FunctionBase is that its Evaluate()
70  * method allows to modify the considered mesh.
71  * When considering a new QuadEdgeMesh method we are left with four possible
72  * "slots" to implement it:
73  * - the QuadEdgeMesh method
74  * - a derived class from FunctionBase when the method leaves
75  * the mesh constant.
76  * - a derived class from \ref itkQE::MeshFunctionBase when the
77  * method modifies the mesh (typically in the case of Euler operators)
78  * - as a classic Mesh filter.
79  * The choice of the slot is a mere matter of trade-off and in order
80  * to keep QuadEdgeMesh tiny and humanly readable key decision factors
81  * can be the occurrence of the calls and the human level complexity of
82  * the code.
83  * With those criteria in mind we made the following choices:
84  * - really atomic, lightweight and general purpose methods like
85  * \ref Mesh::ComputeNumberOfPoints are left within the Mesh class.
86  * - heavier methods and less often called like
87  * \ref SanityCheckMeshFunction were implemented as derived classes of
88  * \ref FunctionBase.
89  * - methods with the same weight (measured e.g. in number of lines of
90  * code) but that modify the considered mesh, like
91  * \ref BoundaryEdgesMeshFunction or
92  * \ref ZipMeshFunction, were implemented as derived classes of
93  * \ref itkQE::MeshFunctionBase. Still the mesh modifications are
94  * really limited and concern a couple edges.
95  * - more specialised methods, with a wider scope and that require a
96  * copy of the mesh should follow the classical itk Filter pattern,
97  * like \ref itkQE::MeshExtractComponentFilter, and inherit from
98  * \ref MeshToMeshFilter.
99  */
100 namespace itk
101 {
102 
115 template< typename TPixel, unsigned int VDimension,
116  typename TTraits = QuadEdgeMeshTraits< TPixel, VDimension, bool, bool > >
117 class ITK_TEMPLATE_EXPORT QuadEdgeMesh:public Mesh< TPixel, VDimension, TTraits >
118 {
119 public:
120 
122  typedef TTraits Traits;
123  typedef TPixel PixelType;
124 
130 
132  itkStaticConstMacro(PointDimension, unsigned int,
133  Traits::PointDimension);
134  itkStaticConstMacro(MaxTopologicalDimension, unsigned int,
135  Traits::MaxTopologicalDimension);
137 
139  typedef typename Superclass::CellPixelType CellPixelType;
140  typedef typename Superclass::CoordRepType CoordRepType;
142  typedef typename Superclass::PointHashType PointHashType;
144  typedef typename Superclass::CellTraits CellTraits;
145 
146  typedef typename CellTraits::PointIdInternalIterator PointIdInternalIterator;
147  typedef typename CellTraits::PointIdIterator PointIdIterator;
148 
149  // Point section:
151  typedef typename Superclass::PointsContainerPointer PointsContainerPointer;
152  typedef CoordRepType CoordRepArrayType[
153  itkGetStaticConstMacro(PointDimension)];
154 
155  // Point data section:
157  typedef typename Superclass::PointDataContainerPointer
159  typedef typename Superclass::PointDataContainerIterator
161  typedef typename Superclass::PointsContainerConstIterator
163  typedef typename Superclass::PointsContainerIterator
165 
166  // Cell section:
168  typedef typename Superclass::CellType CellType;
169  typedef typename Superclass::CellAutoPointer CellAutoPointer;
170  typedef typename Superclass::CellFeatureIdentifier CellFeatureIdentifier;
171  typedef typename Superclass::CellFeatureCount CellFeatureCount;
172  typedef typename Superclass::CellMultiVisitorType CellMultiVisitorType;
175 
176  typedef typename Superclass::CellsContainerConstIterator
178  typedef typename Superclass::CellsContainerIterator
180 
182  typedef typename Superclass::CellLinksContainerPointer
184  typedef typename Superclass::CellLinksContainerIterator
186 
187  // Cell data section:
189  typedef typename Superclass::CellDataContainerPointer
191  typedef typename Superclass::CellDataContainerIterator
193 
194  // Point / Cell correspondance section:
195  typedef typename Superclass::PointCellLinksContainer
197  typedef typename Superclass::PointCellLinksContainerIterator
199 
200  // BoundaryAssignMents section:
201  typedef typename Superclass::BoundaryAssignmentsContainer
203  typedef typename Superclass::BoundaryAssignmentsContainerPointer
205  typedef typename Superclass::BoundaryAssignmentsContainerVector
207 
208  // Miscellaneous section:
209  typedef typename Superclass::BoundingBoxPointer BoundingBoxPointer;
210  typedef typename Superclass::BoundingBoxType BoundingBoxType;
211  typedef typename Superclass::RegionType RegionType;
212  typedef typename Superclass::InterpolationWeightType
214 
216  typedef typename Traits::PrimalDataType PrimalDataType;
217  typedef typename Traits::DualDataType DualDataType;
218  typedef typename Traits::QEPrimal QEPrimal;
219  typedef typename Traits::QEDual QEDual;
220  typedef typename Traits::QEPrimal QEType;
221  // See the TODO entry dated from 2005-05-28
222  // struct QEType : public QEPrimal, public QEDual {}
223  typedef typename Traits::VertexRefType VertexRefType;
224  typedef typename Traits::FaceRefType FaceRefType;
225  typedef typename Traits::VectorType VectorType;
226 
230 
232  typedef std::queue< PointIdentifier > FreePointIndexesType;
233  typedef std::queue< CellIdentifier > FreeCellIndexesType;
234 
236  typedef std::vector< PointIdentifier > PointIdList;
237  typedef std::list< QEPrimal * > EdgeListType;
239 
242 
244  static const CellIdentifier m_NoFace;
245 
246 public:
247 
249  itkNewMacro(Self);
250  itkTypeMacro(QuadEdgeMesh, Mesh);
252 
253 #if !defined( ITK_WRAPPING_PARSER )
254 
256 #endif
257 
258 public:
259 
260  // Multithreading framework: not tested yet.
262  {
263  return ( false );
264  }
265 
266  virtual void Initialize() ITK_OVERRIDE;
267 
269  virtual void Clear();
270 
271  CellsContainer * GetEdgeCells() { return m_EdgeCellsContainer; }
272  const CellsContainer * GetEdgeCells() const { return m_EdgeCellsContainer; }
273  void SetEdgeCells(CellsContainer *edgeCells)
274  { m_EdgeCellsContainer = edgeCells; }
275  void SetEdgeCell(CellIdentifier cellId, CellAutoPointer & cellPointer)
276  { m_EdgeCellsContainer->InsertElement( cellId, cellPointer.ReleaseOwnership() ); }
277 
284  virtual void CopyInformation(const DataObject *data) ITK_OVERRIDE { (void)data; }
285  virtual void Graft(const DataObject *data) ITK_OVERRIDE;
287 
289  void SqueezePointsIds();
290 
292  void BuildCellLinks() {}
293 
294 #if !defined( ITK_WRAPPING_PARSER )
295 
296  void SetBoundaryAssignments(int dimension,
297  BoundaryAssignmentsContainer *container)
298  {
299  (void)dimension;
300  (void)container;
301  }
303 
306  {
307  (void)dimension;
309  }
311 
314  int dimension) const
315  {
316  (void)dimension;
317  return ( (BoundaryAssignmentsContainerPointer)ITK_NULLPTR );
318  }
320 
321 #endif
322 
324  void SetBoundaryAssignment(int dimension, CellIdentifier cellId,
325  CellFeatureIdentifier featureId,
326  CellIdentifier boundaryId)
327  {
328  (void)dimension;
329  (void)cellId;
330  (void)featureId;
331  (void)boundaryId;
332  }
334 
336  bool GetBoundaryAssignment(int dimension, CellIdentifier cellId,
337  CellFeatureIdentifier featureId,
338  CellIdentifier *boundaryId) const
339  {
340  (void)dimension;
341  (void)cellId;
342  (void)featureId;
343  (void)boundaryId;
344  return ( false ); // ALEX: is it the good way?
345  }
347 
349  bool RemoveBoundaryAssignment(int dimension, CellIdentifier cellId,
350  CellFeatureIdentifier featureId)
351  {
352  (void)dimension;
353  (void)cellId;
354  (void)featureId;
355  return ( false ); // ALEX: is it the good way?
356  }
358 
360  bool GetCellBoundaryFeature(int dimension, CellIdentifier cellId,
361  CellFeatureIdentifier featureId,
362  CellAutoPointer & cellAP) const
363  {
364  (void)dimension;
365  (void)cellId;
366  (void)featureId;
367  (void)cellAP;
368  return ( false );
369  }
371 
374  CellIdentifier cellId,
375  CellFeatureIdentifier featureId,
376  std::set< CellIdentifier > *cellSet)
377  {
378  (void)dimension;
379  (void)cellId;
380  (void)featureId;
381  (void)cellSet;
383  }
385 
388  std::set< CellIdentifier > * itkNotUsed(cellSet))
389  {
391  }
392 
395  CellIdentifier cellId,
396  CellFeatureIdentifier featureId,
397  CellAutoPointer & cellAP) const
398  {
399  (void)dimension;
400  (void)cellId;
401  (void)featureId;
402  (void)cellAP;
403  return ( false ); // ALEX: is it the good way?
404  }
406 
408  void SetCell(CellIdentifier cId, CellAutoPointer & cell);
409 
411  virtual PointIdentifier FindFirstUnusedPointIndex();
412 
413  virtual CellIdentifier FindFirstUnusedCellIndex();
414 
415  virtual void PushOnContainer(EdgeCellType *newEdge);
416 
417  // Adding Point/Edge/Face methods
418  virtual PointIdentifier AddPoint(const PointType & p);
419 
421  virtual QEPrimal * AddEdge(const PointIdentifier & orgPid,
422  const PointIdentifier & destPid);
423 
424  virtual QEPrimal * AddEdgeWithSecurePointList(const PointIdentifier & orgPid,
425  const PointIdentifier & destPid);
426 
428  virtual void AddFace(QEPrimal *e);
429 
434  virtual QEPrimal * AddFace(const PointIdList & points);
435 
436  virtual QEPrimal * AddFaceWithSecurePointList(const PointIdList & points);
437 
438  virtual QEPrimal * AddFaceWithSecurePointList(const PointIdList & points,
439  bool CheckEdges);
440 
442  virtual QEPrimal * AddFaceTriangle(const PointIdentifier & aPid,
443  const PointIdentifier & bPid,
444  const PointIdentifier & cPid);
445 
447  virtual void DeletePoint(const PointIdentifier & pid);
448 
449  virtual void DeleteEdge(const PointIdentifier & orgPid,
450  const PointIdentifier & destPid);
451 
452  virtual void DeleteEdge(QEPrimal *e);
453 
454  virtual void LightWeightDeleteEdge(EdgeCellType *e);
455 
456  virtual void LightWeightDeleteEdge(QEPrimal *e);
457 
458  virtual void DeleteFace(FaceRefType faceToDelete);
459 
460  //
461  bool GetPoint(PointIdentifier pid, PointType *pt) const
462  {
463  return ( Superclass::GetPoint(pid, pt) );
464  }
465 
466  virtual PointType GetPoint(const PointIdentifier & pid) const;
467 
468  virtual VectorType GetVector(const PointIdentifier & pid) const;
469 
470  virtual QEPrimal * GetEdge() const;
471 
472  virtual QEPrimal * GetEdge(const CellIdentifier & eid) const;
473 
474  virtual QEPrimal * FindEdge(const PointIdentifier & pid0) const;
475 
476  virtual QEPrimal * FindEdge(const PointIdentifier & pid0,
477  const PointIdentifier & pid1) const;
478 
479  virtual EdgeCellType * FindEdgeCell(const PointIdentifier & pid0,
480  const PointIdentifier & pid1) const;
481 
483  CoordRepType ComputeEdgeLength(QEPrimal *e);
484 
485  PointIdentifier ComputeNumberOfPoints() const;
486 
487  CellIdentifier ComputeNumberOfFaces() const;
488 
489  CellIdentifier ComputeNumberOfEdges() const;
490 
491  PointIdentifier Splice(QEPrimal *a, QEPrimal *b);
492 
493 #ifdef ITK_USE_CONCEPT_CHECKING
494  // Begin concept checking
495  // End concept checking
496 #endif
497 
498  // for reusability of a mesh in the MeshToMesh filter
500  {
501  while ( !this->m_FreePointIndexes.empty() )
502  {
503  this->m_FreePointIndexes.pop();
504  }
505  while ( !this->m_FreeCellIndexes.empty() )
506  {
507  this->m_FreeCellIndexes.pop();
508  }
509  }
510 
511  CellIdentifier GetNumberOfFaces() const { return ( m_NumberOfFaces ); }
512  CellIdentifier GetNumberOfEdges() const { return ( m_NumberOfEdges ); }
513 
514 protected:
516  QuadEdgeMesh();
517  virtual ~QuadEdgeMesh() ITK_OVERRIDE;
519 
521  virtual void ClearCellsContainer();
522 
523  CellsContainerPointer m_EdgeCellsContainer;
524 
525 private:
526  ITK_DISALLOW_COPY_AND_ASSIGN(QuadEdgeMesh);
527 
528  CellIdentifier m_NumberOfFaces;
529  CellIdentifier m_NumberOfEdges;
530 
531 protected:
532  FreePointIndexesType m_FreePointIndexes;
533  FreeCellIndexesType m_FreeCellIndexes;
534 };
535 }
536 
537 #ifndef ITK_MANUAL_INSTANTIATION
538 #include "itkQuadEdgeMesh.hxx"
539 #endif
540 
541 #endif
bool GetAssignedCellBoundaryIfOneExists(int dimension, CellIdentifier cellId, CellFeatureIdentifier featureId, CellAutoPointer &cellAP) const
QuadEdgeMeshLineCell< CellType > EdgeCellType
MeshTraits::PointDataContainer PointDataContainer
Definition: itkMesh.h:157
Traits::VectorType VectorType
const CellsContainer * GetEdgeCells() const
Traits::FaceRefType FaceRefType
Superclass::CellsContainerConstIterator CellsContainerConstIterator
const BoundaryAssignmentsContainerPointer GetBoundaryAssignments(int dimension) const
Superclass::PointType PointType
Superclass::CoordRepType CoordRepType
Superclass::CellsContainerPointer CellsContainerPointer
BoundaryAssignmentsContainerPointer GetBoundaryAssignments(int dimension)
Superclass::CellDataContainerIterator CellDataContainerIterator
Traits::QEPrimal QEPrimal
MeshTraits::PointsContainer PointsContainer
Definition: itkMesh.h:152
bool RemoveBoundaryAssignment(int dimension, CellIdentifier cellId, CellFeatureIdentifier featureId)
virtual bool RequestedRegionIsOutsideOfTheBufferedRegion() override
MeshTraits::CellIdentifier CellIdentifier
Definition: itkMesh.h:148
SmartPointer< Self > Pointer
Superclass::CellAutoPointer CellAutoPointer
static const PointIdentifier m_NoPoint
Implements the N-dimensional mesh structure.
Definition: itkMesh.h:108
Superclass::BoundingBoxPointer BoundingBoxPointer
Traits::QEPrimal QEType
Superclass::CellDataContainerPointer CellDataContainerPointer
Superclass::BoundaryAssignmentsContainer BoundaryAssignmentsContainer
Superclass::CellLinksContainerPointer CellLinksContainerPointer
Superclass::PointHashType PointHashType
MeshTraits::CellDataContainer CellDataContainer
Definition: itkMesh.h:158
Superclass::CellFeatureIdentifier CellFeatureIdentifier
void SetEdgeCells(CellsContainer *edgeCells)
bool GetCellBoundaryFeature(int dimension, CellIdentifier cellId, CellFeatureIdentifier featureId, CellAutoPointer &cellAP) const
void SetBoundaryAssignment(int dimension, CellIdentifier cellId, CellFeatureIdentifier featureId, CellIdentifier boundaryId)
Superclass::CellDataContainer CellDataContainer
void SetEdgeCell(CellIdentifier cellId, CellAutoPointer &cellPointer)
bool GetPoint(PointIdentifier pid, PointType *pt) const
Superclass::PointDataContainerIterator PointDataContainerIterator
Mesh< TPixel, VDimension, Traits > Superclass
Superclass::PointDataContainer PointDataContainer
Superclass::RegionType RegionType
Superclass::BoundaryAssignmentsContainerPointer BoundaryAssignmentsContainerPointer
Superclass::BoundingBoxType BoundingBoxType
virtual void CopyInformation(const DataObject *data) override
std::queue< CellIdentifier > FreeCellIndexesType
EdgeListType * EdgeListPointerType
Superclass::CellIdentifier CellIdentifier
static const CellIdentifier m_NoFace
CellTraits::PointIdInternalIterator PointIdInternalIterator
Superclass::CellLinksContainerIterator CellLinksContainerIterator
MeshTraits::PointIdentifier PointIdentifier
Definition: itkMesh.h:147
SmartPointer< const Self > ConstPointer
Superclass::CellTraits CellTraits
CellIdentifier GetCellNeighbors(CellIdentifier, std::set< CellIdentifier > *)
Superclass::PointCellLinksContainerIterator PointCellLinksContainerIterator
MeshTraits::CellLinksContainer CellLinksContainer
Definition: itkMesh.h:156
bool GetBoundaryAssignment(int dimension, CellIdentifier cellId, CellFeatureIdentifier featureId, CellIdentifier *boundaryId) const
Superclass::CellType CellType
CellsContainer::Pointer CellsContainerPointer
Definition: itkMesh.h:166
std::queue< PointIdentifier > FreePointIndexesType
void SetBoundaryAssignments(int dimension, BoundaryAssignmentsContainer *container)
Superclass::CellPixelType CellPixelType
MeshTraits::CellsContainer CellsContainer
Definition: itkMesh.h:154
Superclass::BoundaryAssignmentsContainerVector BoundaryAssignmentsContainerVector
CellIdentifier GetCellBoundaryFeatureNeighbors(int dimension, CellIdentifier cellId, CellFeatureIdentifier featureId, std::set< CellIdentifier > *cellSet)
Traits::VertexRefType VertexRefType
void ClearFreePointAndCellIndexesLists()
Superclass::PointsContainerConstIterator PointsContainerConstIterator
CellTraits::PointIdIterator PointIdIterator
Superclass::PointDataContainerPointer PointDataContainerPointer
Traits::QEDual QEDual
CellIdentifier GetNumberOfFaces() const
Mesh class for 2D manifolds embedded in ND space.
QuadEdgeMeshPolygonCell< CellType > PolygonCellType
Superclass::PointsContainerIterator PointsContainerIterator
Traits::PrimalDataType PrimalDataType
Superclass::PointCellLinksContainer PointCellLinksContainer
Superclass::CellFeatureCount CellFeatureCount
std::vector< PointIdentifier > PointIdList
Superclass::CellMultiVisitorType CellMultiVisitorType
Superclass::InterpolationWeightType InterpolationWeightType
#define itkQEDefineFrontIteratorMethodsMacro(MeshTypeArg)
Traits::DualDataType DualDataType
Superclass::PointsContainer PointsContainer
Superclass::CellsContainer CellsContainer
Superclass::CellLinksContainer CellLinksContainer
static ITK_CONSTEXPR_VAR double e
The base of the natural logarithm or Euler&#39;s number
Definition: itkMath.h:56
Superclass::PointIdentifier PointIdentifier
CellIdentifier GetNumberOfEdges() const
Superclass::PointsContainerPointer PointsContainerPointer
Base class for all data objects in ITK.
Class that connects the QuadEdgeMesh with the Mesh.
Superclass::CellsContainerIterator CellsContainerIterator
std::list< QEPrimal * > EdgeListType