ITK  4.4.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 #include "vcl_cstdarg.h"
22 #include <queue>
23 #include <vector>
24 #include <list>
25 
26 #include "itkMesh.h"
27 
28 #include "itkQuadEdgeMeshTraits.h"
31 
33 #include "itkConceptChecking.h"
34 
35 /****
36  * \brief Documentation of itkQE namespace
37  * \todo More comments here !
38  *
39  * \note Design notes: some QuadEdgeMesh algorithms are based on iterating
40  * various connectivity operators e.g. curvature driven surface deformation.
41  * Many of those connectivity altering operators (e.g. the Euler operators)
42  * are lightweight in the sense that they only modify very limited regions
43  * of a QuadEdgeMesh: they typically act within the range of couple edges of
44  * distance from a considered vertex, edge or face.
45  * On the one side, we cannot choose to implement those atomic operations
46  * as "classical" itk filters since each filter invocation yields a new
47  * copy of the input mesh as its output: this would drasticaly
48  * increase the memory consumption.
49  * In fact, those atomic operations have a too much finer grain to be
50  * implemeted as filters: the filter is more at the scale of the
51  * application of a large number of such atomic operations.
52  * One the other hand, we cannot choose to implement those atomic operations
53  * as methods of this QuadEdgeMesh class (or a derived one) at the risk of
54  * rapid code bloat.
55  * Maybe we could choose to make thematic regroupment within derived
56  * classes, but this would force an end user to multiple inheritance which
57  * can prove to be a drag in a templated context.
58  * Eventually, we chose to implement them as function object: the
59  * loosely coupling of those operation methods with the targeted QuadEdgeMesh
60  * object and heavier invocation syntax are a small price to pay in
61  * exchange for optimal memory usage and end user modularity.
62  * But we couldn't inherit from \ref FunctionBase since its
63  * Evaluate( const InputType& input ) method promises to leave its
64  * argument (the mesh we want to modify in our case) untouched.
65  * Hence we created the \ref itkQE::MeshFunctionBase class whose main
66  * difference with \ref FunctionBase is that its Evaluate()
67  * method allows to modify the considered mesh.
68  * When considering a new QuadEdgeMesh method we are left with four possible
69  * "slots" to implement it:
70  * - the QuadEdgeMesh method
71  * - a derived class from FunctionBase when the method leaves
72  * the mesh constant.
73  * - a derived class from \ref itkQE::MeshFunctionBase when the
74  * method modifies the mesh (typically in the case of Euler operators)
75  * - as a classic Mesh filter.
76  * The choice of the slot is a mere matter of trade-off and in order
77  * to keep QuadEdgeMesh tiny and humanly readable key decision factors
78  * can be the occurrence of the calls and the human level complexity of
79  * the code.
80  * With those criteria in mind we made the following choices:
81  * - really atomic, lightweight and general purpose methods like
82  * \ref Mesh::ComputeNumberOfPoints are left within the Mesh class.
83  * - heavier methods and less often called like
84  * \ref SanityCheckMeshFunction were implemented as derived classes of
85  * \ref FunctionBase.
86  * - methods with the same weight (measured e.g. in number of lines of
87  * code) but that modify the considered mesh, like
88  * \ref BoundaryEdgesMeshFunction or
89  * \ref ZipMeshFunction, were implemented as derived classes of
90  * \ref itkQE::MeshFunctionBase. Still the mesh modifications are
91  * really limited and concern a couple edges.
92  * - more specialised methods, with a wider scope and that require a
93  * copy of the mesh should follow the classical itk Filter pattern,
94  * like \ref itkQE::MeshExtractComponentFilter, and inherit from
95  * \ref MeshToMeshFilter.
96  */
97 namespace itk
98 {
99 
112 template< typename TPixel, unsigned int VDimension,
113  typename TTraits = QuadEdgeMeshTraits< TPixel, VDimension, bool, bool > >
114 class ITK_EXPORT QuadEdgeMesh:public Mesh< TPixel, VDimension, TTraits >
115 {
116 public:
117 
119  typedef TTraits Traits;
120  typedef TPixel PixelType;
121 
127 
129  itkStaticConstMacro(PointDimension, unsigned int,
130  Traits::PointDimension);
131  itkStaticConstMacro(MaxTopologicalDimension, unsigned int,
132  Traits::MaxTopologicalDimension);
134 
136  typedef typename Superclass::CellPixelType CellPixelType;
137  typedef typename Superclass::CoordRepType CoordRepType;
139  typedef typename Superclass::PointHashType PointHashType;
140  typedef typename Superclass::PointType PointType;
141  typedef typename Superclass::CellTraits CellTraits;
142 
143  typedef typename CellTraits::PointIdInternalIterator PointIdInternalIterator;
144  typedef typename CellTraits::PointIdIterator PointIdIterator;
145 
146  // Point section:
147  typedef typename Superclass::PointsContainer PointsContainer;
148  typedef typename Superclass::PointsContainerPointer PointsContainerPointer;
149  typedef CoordRepType CoordRepArrayType[
150  itkGetStaticConstMacro(PointDimension)];
151 
152  // Point data section:
153  typedef typename Superclass::PointDataContainer PointDataContainer;
154  typedef typename Superclass::PointDataContainerPointer
156  typedef typename Superclass::PointDataContainerIterator
158  typedef typename Superclass::PointsContainerConstIterator
160  typedef typename Superclass::PointsContainerIterator
162 
163  // Cell section:
165  typedef typename Superclass::CellType CellType;
166  typedef typename Superclass::CellAutoPointer CellAutoPointer;
167  typedef typename Superclass::CellFeatureIdentifier CellFeatureIdentifier;
168  typedef typename Superclass::CellFeatureCount CellFeatureCount;
169  typedef typename Superclass::CellMultiVisitorType CellMultiVisitorType;
170  typedef typename Superclass::CellsContainer CellsContainer;
171  typedef typename Superclass::CellsContainerPointer CellsContainerPointer;
172 
173  typedef typename Superclass::CellsContainerConstIterator
175  typedef typename Superclass::CellsContainerIterator
177 
178  typedef typename Superclass::CellLinksContainer CellLinksContainer;
179  typedef typename Superclass::CellLinksContainerPointer
181  typedef typename Superclass::CellLinksContainerIterator
183 
184  // Cell data section:
185  typedef typename Superclass::CellDataContainer CellDataContainer;
186  typedef typename Superclass::CellDataContainerPointer
188  typedef typename Superclass::CellDataContainerIterator
190 
191  // Point / Cell correspondance section:
192  typedef typename Superclass::PointCellLinksContainer
194  typedef typename Superclass::PointCellLinksContainerIterator
196 
197  // BoundaryAssignMents section:
198  typedef typename Superclass::BoundaryAssignmentsContainer
200  typedef typename Superclass::BoundaryAssignmentsContainerPointer
202  typedef typename Superclass::BoundaryAssignmentsContainerVector
204 
205  // Miscellaneous section:
206  typedef typename Superclass::BoundingBoxPointer BoundingBoxPointer;
207  typedef typename Superclass::BoundingBoxType BoundingBoxType;
208  typedef typename Superclass::RegionType RegionType;
209  typedef typename Superclass::InterpolationWeightType
211 
213  typedef typename Traits::PrimalDataType PrimalDataType;
214  typedef typename Traits::DualDataType DualDataType;
215  typedef typename Traits::QEPrimal QEPrimal;
216  typedef typename Traits::QEDual QEDual;
217  typedef typename Traits::QEPrimal QEType;
218  // See the TODO entry dated from 2005-05-28
219  // struct QEType : public QEPrimal, public QEDual {}
220  typedef typename Traits::VertexRefType VertexRefType;
221  typedef typename Traits::FaceRefType FaceRefType;
222  typedef typename Traits::VectorType VectorType;
223 
227 
229  typedef std::queue< PointIdentifier > FreePointIndexesType;
230  typedef std::queue< CellIdentifier > FreeCellIndexesType;
231 
233  typedef std::vector< PointIdentifier > PointIdList;
234  typedef std::list< QEPrimal * > EdgeListType;
236 
239 
241  static const CellIdentifier m_NoFace;
242 
243 public:
244 
246  itkNewMacro(Self);
247  itkTypeMacro(QuadEdgeMesh, Mesh);
249 
250 #if !defined( CABLE_CONFIGURATION )
251 
253 #endif
254 
255 public:
256 
257  // Multithreading framework: not tested yet.
258  virtual bool RequestedRegionIsOutsideOfTheBufferedRegion()
259  {
260  return ( false );
261  }
262 
263  virtual void Initialize();
264 
266  virtual void Clear();
267 
268  CellsContainer * GetEdgeCells() { return m_EdgeCellsContainer; }
269  const CellsContainer * GetEdgeCells() const { return m_EdgeCellsContainer; }
270  void SetEdgeCells(CellsContainer *edgeCells)
271  { m_EdgeCellsContainer = edgeCells; }
272  void SetEdgeCell(CellIdentifier cellId, CellAutoPointer & cellPointer)
273  { m_EdgeCellsContainer->InsertElement( cellId, cellPointer.ReleaseOwnership() ); }
274 
281  virtual void CopyInformation(const DataObject *data) { (void)data; }
282  virtual void Graft(const DataObject *data);
284 
286  void SqueezePointsIds();
287 
289  void BuildCellLinks() {}
290 
291 #if !defined( CABLE_CONFIGURATION )
292 
293  void SetBoundaryAssignments(int dimension,
294  BoundaryAssignmentsContainer *container)
295  {
296  (void)dimension;
297  (void)container;
298  }
300 
302  BoundaryAssignmentsContainerPointer GetBoundaryAssignments(int dimension)
303  {
304  (void)dimension;
306  }
308 
310  const BoundaryAssignmentsContainerPointer GetBoundaryAssignments(
311  int dimension) const
312  {
313  (void)dimension;
315  }
317 
318 #endif
319 
321  void SetBoundaryAssignment(int dimension, CellIdentifier cellId,
322  CellFeatureIdentifier featureId,
323  CellIdentifier boundaryId)
324  {
325  (void)dimension;
326  (void)cellId;
327  (void)featureId;
328  (void)boundaryId;
329  }
331 
333  bool GetBoundaryAssignment(int dimension, CellIdentifier cellId,
334  CellFeatureIdentifier featureId,
335  CellIdentifier *boundaryId) const
336  {
337  (void)dimension;
338  (void)cellId;
339  (void)featureId;
340  (void)boundaryId;
341  return ( false ); // ALEX: is it the good way?
342  }
344 
346  bool RemoveBoundaryAssignment(int dimension, CellIdentifier cellId,
347  CellFeatureIdentifier featureId)
348  {
349  (void)dimension;
350  (void)cellId;
351  (void)featureId;
352  return ( false ); // ALEX: is it the good way?
353  }
355 
357  bool GetCellBoundaryFeature(int dimension, CellIdentifier cellId,
358  CellFeatureIdentifier featureId,
359  CellAutoPointer & cellAP) const
360  {
361  (void)dimension;
362  (void)cellId;
363  (void)featureId;
364  (void)cellAP;
365  return ( false );
366  }
368 
370  CellIdentifier GetCellBoundaryFeatureNeighbors(int dimension,
371  CellIdentifier cellId,
372  CellFeatureIdentifier featureId,
373  std::set< CellIdentifier > *cellSet)
374  {
375  (void)dimension;
376  (void)cellId;
377  (void)featureId;
378  (void)cellSet;
380  }
382 
384  CellIdentifier GetCellNeighbors(CellIdentifier itkNotUsed(cellId),
385  std::set< CellIdentifier > * itkNotUsed(cellSet))
386  {
388  }
389 
391  bool GetAssignedCellBoundaryIfOneExists(int dimension,
392  CellIdentifier cellId,
393  CellFeatureIdentifier featureId,
394  CellAutoPointer & cellAP) const
395  {
396  (void)dimension;
397  (void)cellId;
398  (void)featureId;
399  (void)cellAP;
400  return ( false ); // ALEX: is it the good way?
401  }
403 
405  void SetCell(CellIdentifier cId, CellAutoPointer & cell);
406 
408  virtual PointIdentifier FindFirstUnusedPointIndex();
409 
410  virtual CellIdentifier FindFirstUnusedCellIndex();
411 
412  virtual void PushOnContainer(EdgeCellType *newEdge);
413 
414  // Adding Point/Edge/Face methods
415  virtual PointIdentifier AddPoint(const PointType & p);
416 
418  virtual QEPrimal * AddEdge(const PointIdentifier & orgPid,
419  const PointIdentifier & destPid);
420 
421  virtual QEPrimal * AddEdgeWithSecurePointList(const PointIdentifier & orgPid,
422  const PointIdentifier & destPid);
423 
425  virtual void AddFace(QEPrimal *e);
426 
431  virtual QEPrimal * AddFace(const PointIdList & points);
432 
433  virtual QEPrimal * AddFaceWithSecurePointList(const PointIdList & points);
434 
435  virtual QEPrimal * AddFaceWithSecurePointList(const PointIdList & points,
436  bool CheckEdges);
437 
439  virtual QEPrimal * AddFaceTriangle(const PointIdentifier & aPid,
440  const PointIdentifier & bPid,
441  const PointIdentifier & cPid);
442 
444  virtual void DeletePoint(const PointIdentifier & pid);
445 
446  virtual void DeleteEdge(const PointIdentifier & orgPid,
447  const PointIdentifier & destPid);
448 
449  virtual void DeleteEdge(QEPrimal *e);
450 
451  virtual void LightWeightDeleteEdge(EdgeCellType *e);
452 
453  virtual void LightWeightDeleteEdge(QEPrimal *e);
454 
455  virtual void DeleteFace(FaceRefType faceToDelete);
456 
457  //
458  bool GetPoint(PointIdentifier pid, PointType *pt) const
459  {
460  return ( Superclass::GetPoint(pid, pt) );
461  }
462 
463  virtual PointType GetPoint(const PointIdentifier & pid) const;
464 
465  virtual VectorType GetVector(const PointIdentifier & pid) const;
466 
467  virtual QEPrimal * GetEdge() const;
468 
469  virtual QEPrimal * GetEdge(const CellIdentifier & eid) const;
470 
471  virtual QEPrimal * FindEdge(const PointIdentifier & pid0) const;
472 
473  virtual QEPrimal * FindEdge(const PointIdentifier & pid0,
474  const PointIdentifier & pid1) const;
475 
476  virtual EdgeCellType * FindEdgeCell(const PointIdentifier & pid0,
477  const PointIdentifier & pid1) const;
478 
480  CoordRepType ComputeEdgeLength(QEPrimal *e);
481 
482  PointIdentifier ComputeNumberOfPoints() const;
483 
484  CellIdentifier ComputeNumberOfFaces() const;
485 
486  CellIdentifier ComputeNumberOfEdges() const;
487 
488  PointIdentifier Splice(QEPrimal *a, QEPrimal *b);
489 
490 #ifdef ITK_USE_CONCEPT_CHECKING
491 
494 #endif
495 
496  // for reusability of a mesh in the MeshToMesh filter
497  void ClearFreePointAndCellIndexesLists()
498  {
499  while ( !this->m_FreePointIndexes.empty() )
500  {
501  this->m_FreePointIndexes.pop();
502  }
503  while ( !this->m_FreeCellIndexes.empty() )
504  {
505  this->m_FreeCellIndexes.pop();
506  }
507  }
508 
509  CellIdentifier GetNumberOfFaces() const { return ( m_NumberOfFaces ); }
510  CellIdentifier GetNumberOfEdges() const { return ( m_NumberOfEdges ); }
511 
512 protected:
514  QuadEdgeMesh();
515  virtual ~QuadEdgeMesh();
517 
519  virtual void ClearCellsContainer();
520 
522 
523 private:
524  QuadEdgeMesh(const Self &); //purposely not implemented
525  void operator=(const Self &); //purposely not implemented
526 
529 
530 protected:
533 };
534 }
535 
536 #ifndef ITK_MANUAL_INSTANTIATION
537 #include "itkQuadEdgeMesh.hxx"
538 #endif
539 
540 #endif
541