ITK  4.2.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;
138  typedef typename Superclass::PointIdentifier PointIdentifier;
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 public:
243 
245  itkNewMacro(Self);
246  itkTypeMacro(QuadEdgeMesh, Mesh);
248 
249 #if !defined( CABLE_CONFIGURATION )
250 
252 #endif
253 public:
254 
255  // Multithreading framework: not tested yet.
256  virtual bool RequestedRegionIsOutsideOfTheBufferedRegion()
257  {
258  return ( false );
259  }
260 
261  virtual void Initialize();
262 
264  virtual void Clear();
265 
266  CellsContainer * GetEdgeCells() { return m_EdgeCellsContainer; }
267  const CellsContainer * GetEdgeCells() const { return m_EdgeCellsContainer; }
268  void SetEdgeCells(CellsContainer *edgeCells)
269  { m_EdgeCellsContainer = edgeCells; }
270  void SetEdgeCell(CellIdentifier cellId, CellAutoPointer & cellPointer)
271  { m_EdgeCellsContainer->InsertElement( cellId, cellPointer.ReleaseOwnership() ); }
272 
279  virtual void CopyInformation(const DataObject *data) { (void)data; }
280  virtual void Graft(const DataObject *data);
282 
284  void SqueezePointsIds();
285 
287  void BuildCellLinks() {}
288 
289 #if !defined( CABLE_CONFIGURATION )
290 
291  void SetBoundaryAssignments(int dimension,
292  BoundaryAssignmentsContainer *container)
293  {
294  (void)dimension;
295  (void)container;
296  }
298 
300  BoundaryAssignmentsContainerPointer GetBoundaryAssignments(int dimension)
301  {
302  (void)dimension;
304  }
306 
308  const BoundaryAssignmentsContainerPointer GetBoundaryAssignments(
309  int dimension) const
310  {
311  (void)dimension;
313  }
315 
316 #endif
317 
319  void SetBoundaryAssignment(int dimension, CellIdentifier cellId,
320  CellFeatureIdentifier featureId,
321  CellIdentifier boundaryId)
322  {
323  (void)dimension;
324  (void)cellId;
325  (void)featureId;
326  (void)boundaryId;
327  }
329 
331  bool GetBoundaryAssignment(int dimension, CellIdentifier cellId,
332  CellFeatureIdentifier featureId,
333  CellIdentifier *boundaryId) const
334  {
335  (void)dimension;
336  (void)cellId;
337  (void)featureId;
338  (void)boundaryId;
339  return ( false ); // ALEX: is it the good way?
340  }
342 
344  bool RemoveBoundaryAssignment(int dimension, CellIdentifier cellId,
345  CellFeatureIdentifier featureId)
346  {
347  (void)dimension;
348  (void)cellId;
349  (void)featureId;
350  return ( false ); // ALEX: is it the good way?
351  }
353 
355  bool GetCellBoundaryFeature(int dimension, CellIdentifier cellId,
356  CellFeatureIdentifier featureId,
357  CellAutoPointer & cellAP) const
358  {
359  (void)dimension;
360  (void)cellId;
361  (void)featureId;
362  (void)cellAP;
363  return ( false );
364  }
366 
368  CellIdentifier GetCellBoundaryFeatureNeighbors(int dimension,
369  CellIdentifier cellId,
370  CellFeatureIdentifier featureId,
371  std::set< CellIdentifier > *cellSet)
372  {
373  (void)dimension;
374  (void)cellId;
375  (void)featureId;
376  (void)cellSet;
378  }
380 
382  CellIdentifier GetCellNeighbors(CellIdentifier itkNotUsed(cellId),
383  std::set< CellIdentifier > * itkNotUsed(cellSet))
384  {
386  }
387 
389  bool GetAssignedCellBoundaryIfOneExists(int dimension,
390  CellIdentifier cellId,
391  CellFeatureIdentifier featureId,
392  CellAutoPointer & cellAP) const
393  {
394  (void)dimension;
395  (void)cellId;
396  (void)featureId;
397  (void)cellAP;
398  return ( false ); // ALEX: is it the good way?
399  }
401 
403  void SetCell(CellIdentifier cId, CellAutoPointer & cell);
404 
406  virtual PointIdentifier FindFirstUnusedPointIndex();
407 
408  virtual CellIdentifier FindFirstUnusedCellIndex();
409 
410  virtual void PushOnContainer(EdgeCellType *newEdge);
411 
412  // Adding Point/Edge/Face methods
413  virtual PointIdentifier AddPoint(const PointType & p);
414 
416  virtual QEPrimal * AddEdge(const PointIdentifier & orgPid,
417  const PointIdentifier & destPid);
418 
419  virtual QEPrimal * AddEdgeWithSecurePointList(const PointIdentifier & orgPid,
420  const PointIdentifier & destPid);
421 
423  virtual void AddFace(QEPrimal *e);
424 
429  virtual QEPrimal * AddFace(const PointIdList & points);
430 
431  virtual QEPrimal * AddFaceWithSecurePointList(const PointIdList & points);
432 
433  virtual QEPrimal * AddFaceWithSecurePointList(const PointIdList & points,
434  bool CheckEdges);
435 
437  virtual QEPrimal * AddFaceTriangle(const PointIdentifier & aPid,
438  const PointIdentifier & bPid,
439  const PointIdentifier & cPid);
440 
442  virtual void DeletePoint(const PointIdentifier & pid);
443 
444  virtual void DeleteEdge(const PointIdentifier & orgPid,
445  const PointIdentifier & destPid);
446 
447  virtual void DeleteEdge(QEPrimal *e);
448 
449  virtual void LightWeightDeleteEdge(EdgeCellType *e);
450 
451  virtual void LightWeightDeleteEdge(QEPrimal *e);
452 
453  virtual void DeleteFace(FaceRefType faceToDelete);
454 
455  //
456  bool GetPoint(PointIdentifier pid, PointType *pt) const
457  {
458  return ( Superclass::GetPoint(pid, pt) );
459  }
460 
461  virtual PointType GetPoint(const PointIdentifier & pid) const;
462 
463  virtual VectorType GetVector(const PointIdentifier & pid) const;
464 
465  virtual QEPrimal * GetEdge() const;
466 
467  virtual QEPrimal * GetEdge(const CellIdentifier & eid) const;
468 
469  virtual QEPrimal * FindEdge(const PointIdentifier & pid0) const;
470 
471  virtual QEPrimal * FindEdge(const PointIdentifier & pid0,
472  const PointIdentifier & pid1) const;
473 
474  virtual EdgeCellType * FindEdgeCell(const PointIdentifier & pid0,
475  const PointIdentifier & pid1) const;
476 
478  CoordRepType ComputeEdgeLength(QEPrimal *e);
479 
480  PointIdentifier ComputeNumberOfPoints() const;
481 
482  CellIdentifier ComputeNumberOfFaces() const;
483 
484  CellIdentifier ComputeNumberOfEdges() const;
485 
486  PointIdentifier Splice(QEPrimal *a, QEPrimal *b);
487 
488 #ifdef ITK_USE_CONCEPT_CHECKING
489 
492 #endif
493 
494  // for reusability of a mesh in the MeshToMesh filter
495  void ClearFreePointAndCellIndexesLists()
496  {
497  while ( !this->m_FreePointIndexes.empty() )
498  {
499  this->m_FreePointIndexes.pop();
500  }
501  while ( !this->m_FreeCellIndexes.empty() )
502  {
503  this->m_FreeCellIndexes.pop();
504  }
505  }
506 
507  CellIdentifier GetNumberOfFaces() const { return ( m_NumberOfFaces ); }
508  CellIdentifier GetNumberOfEdges() const { return ( m_NumberOfEdges ); }
509 protected:
511  QuadEdgeMesh();
512  virtual ~QuadEdgeMesh();
514 
516  virtual void ClearCellsContainer();
517 
519 private:
520  QuadEdgeMesh(const Self &); //purposely not implemented
521  void operator=(const Self &); //purposely not implemented
522 
525 protected:
528 };
529 }
530 
531 #ifndef ITK_MANUAL_INSTANTIATION
532 #include "itkQuadEdgeMesh.hxx"
533 #endif
534 
535 #endif
536