Main Page   Groups   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Concepts

itkQuadEdgeMesh.h

Go to the documentation of this file.
00001 /*=========================================================================
00002 
00003   Program:   Insight Segmentation & Registration Toolkit
00004   Module:    $RCSfile: itkQuadEdgeMesh.h,v $
00005   Language:  C++
00006   Date:      $Date: 2009-09-08 20:00:56 $
00007   Version:   $Revision: 1.38 $
00008 
00009   Copyright (c) Insight Software Consortium. All rights reserved.
00010   See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.
00011 
00012      This software is distributed WITHOUT ANY WARRANTY; without even
00013      the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
00014      PURPOSE.  See the above copyright notices for more information.
00015 
00016 =========================================================================*/
00017 
00018 #ifndef __itkQuadEdgeMesh_h
00019 #define __itkQuadEdgeMesh_h
00020 
00021 #include "vcl_cstdarg.h"
00022 #include <queue>
00023 #include <vector>
00024 #include <list>
00025 
00026 #include "itkMesh.h"
00027 
00028 #include "itkQuadEdgeMeshTraits.h"
00029 #include "itkQuadEdgeMeshLineCell.h"
00030 #include "itkQuadEdgeMeshPolygonCell.h"
00031 
00032 #include "itkQuadEdgeMeshFrontIterator.h"
00033 #include "itkConceptChecking.h"
00034 
00035 /****
00036  * \brief Documentation of itkQE namespace
00037  * \todo More comments here !
00038  *
00039  * \note Design notes: some QuadEdgeMesh algorithms are based on iterating
00040  * various connectivity operators e.g. curvature driven surface deformation.
00041  * Many of those connectivity altering operators (e.g. the Euler operators)
00042  * are lightweight in the sense that they only modify very limited regions
00043  * of a QuadEdgeMesh: they typically act within the range of couple edges of
00044  * distance from a considered vertex, edge or face.
00045  * On the one side, we cannot choose to implement those atomic operations
00046  * as "classical" itk filters since each filter invocation yields a new
00047  * copy of the input mesh as its output: this would drasticaly
00048  * increase the memory consumption.
00049  * In fact, those atomic operations have a too much finer grain to be
00050  * implemeted as filters: the filter is more at the scale of the
00051  * application of a large number of such atomic operations.
00052  * One the other hand, we cannot choose to implement those atomic operations
00053  * as methods of this QuadEdgeMesh class (or a derived one) at the risk of
00054  * rapid code bloat.
00055  * Maybe we could choose to make thematic regroupment within derived
00056  * classes, but this would force an end user to multiple inheritance which
00057  * can prove to be a drag in a templated context.
00058  * Eventually, we chose to implement them as function object: the
00059  * loosely coupling of those operation methods with the targeted QuadEdgeMesh
00060  * object and heavier invocation syntax are a small price to pay in
00061  * exchange for optimal memory usage and end user modularity.
00062  * But we couldn't inherit from \ref FunctionBase since its
00063  * Evaluate( const InputType& input ) method promises to leave its
00064  * argument (the mesh we want to modify in our case) untouched.
00065  * Hence we created the \ref itkQE::MeshFunctionBase class whose main
00066  * difference with \ref FunctionBase is that its Evaluate()
00067  * method allows to modify the considered mesh.
00068  * When considering a new QuadEdgeMesh method we are left with four possible
00069  * "slots" to implement it:
00070  *   - the QuadEdgeMesh method
00071  *   - a derived class from FunctionBase when the method leaves
00072  *     the mesh constant.
00073  *   - a derived class from \ref itkQE::MeshFunctionBase when the
00074  *     method modifies the mesh (typically in the case of Euler operators)
00075  *   - as a classic Mesh filter.
00076  * The choice of the slot is a mere matter of trade-off and in order
00077  * to keep QuadEdgeMesh tiny and humanly readable key decision factors
00078  * can be the occurence of the calls and the human level complexity of
00079  * the code.
00080  * With those criteria in mind we made the following choices:
00081  *   - really atomic, lightweight and general purpose methods like
00082  *     \ref Mesh::ComputeNumberOfPoints are left within the Mesh class.
00083  *   - heavier methods and less often called like
00084  *     \ref SanityCheckMeshFunction were implemented as derived classes of
00085  *     \ref FunctionBase.
00086  *   - methods with the same weight (measured e.g. in number of lines of
00087  *     code) but that modify the considered mesh, like
00088  *     \ref BoundaryEdgesMeshFunction or
00089  *     \ref ZipMeshFunction, were implemented as derived classes of
00090  *     \ref itkQE::MeshFunctionBase. Still the mesh modifications are
00091  *     really limited and concern a couple edges.
00092  *   - more specialised methods, with a wider scope and that require a
00093  *     copy of the mesh should follow the classical itk Filter pattern,
00094  *     like \ref itkQE::MeshExtractComponentFilter, and inherit from
00095  *     \ref MeshToMeshFilter.
00096  */
00097 namespace itk
00098 {
00099 
00111 template< typename TPixel, unsigned int VDimension,
00112   typename TTraits = QuadEdgeMeshTraits< TPixel, VDimension, bool, bool > >
00113 class QuadEdgeMesh : public Mesh< TPixel, VDimension, TTraits >
00114 {
00115 public:
00116 
00118   typedef TTraits Traits;
00119   typedef TPixel  PixelType;
00120 
00122   typedef QuadEdgeMesh                            Self;
00123   typedef Mesh< TPixel, VDimension, Traits >      Superclass;
00124   typedef SmartPointer< Self >                    Pointer;
00125   typedef SmartPointer< const Self >              ConstPointer;
00126 
00128   itkStaticConstMacro( PointDimension, unsigned int,
00129                        Traits::PointDimension );
00130   itkStaticConstMacro( MaxTopologicalDimension, unsigned int,
00131                        Traits::MaxTopologicalDimension );
00133 
00135   typedef typename Superclass::CellPixelType    CellPixelType;
00136   typedef typename Superclass::CoordRepType     CoordRepType;
00137   typedef typename Superclass::PointIdentifier  PointIdentifier;
00138   typedef typename Superclass::PointHashType    PointHashType;
00139   typedef typename Superclass::PointType        PointType;
00140   typedef typename Superclass::CellTraits       CellTraits;
00141 
00142   typedef typename CellTraits::PointIdInternalIterator PointIdInternalIterator;
00143   typedef typename CellTraits::PointIdIterator         PointIdIterator;
00144 
00145   // Point section:
00146   typedef typename Superclass::PointsContainer        PointsContainer;
00147   typedef typename Superclass::PointsContainerPointer PointsContainerPointer;
00148   typedef typename Superclass::PointLocatorPointer    PointLocatorPointer;
00149   typedef typename Superclass::PointLocatorType       PointLocatorType;
00150   typedef CoordRepType  CoordRepArrayType[ 
00151                               itkGetStaticConstMacro( PointDimension ) ];
00152 
00153   // Point data section:
00154   typedef typename Superclass::PointDataContainer     PointDataContainer;
00155   typedef typename Superclass::PointDataContainerPointer
00156                                PointDataContainerPointer;
00157   typedef typename Superclass::PointDataContainerIterator
00158                                PointDataContainerIterator;
00159   typedef typename Superclass::PointsContainerConstIterator
00160                                PointsContainerConstIterator;
00161   typedef typename Superclass::PointsContainerIterator
00162                                PointsContainerIterator;
00163 
00164   // Cell section:
00165   typedef typename Superclass::CellIdentifier         CellIdentifier;
00166   typedef typename Superclass::CellType               CellType;
00167   typedef typename Superclass::CellAutoPointer        CellAutoPointer;
00168   typedef typename Superclass::CellFeatureIdentifier  CellFeatureIdentifier;
00169   typedef typename Superclass::CellFeatureCount       CellFeatureCount;
00170   typedef typename Superclass::CellMultiVisitorType   CellMultiVisitorType;
00171   typedef typename Superclass::CellsContainer         CellsContainer;
00172   typedef typename Superclass::CellsContainerPointer  CellsContainerPointer;
00173 
00174   typedef typename Superclass::CellsContainerConstIterator
00175                                                   CellsContainerConstIterator;
00176   typedef typename Superclass::CellsContainerIterator
00177                                                   CellsContainerIterator;
00178 
00179   typedef typename Superclass::CellLinksContainer CellLinksContainer;
00180   typedef typename Superclass::CellLinksContainerPointer
00181                                                   CellLinksContainerPointer;
00182   typedef typename Superclass::CellLinksContainerIterator
00183                                                   CellLinksContainerIterator;
00184 
00185   // Cell data section:
00186   typedef typename Superclass::CellDataContainer  CellDataContainer;
00187   typedef typename Superclass::CellDataContainerPointer
00188                                                   CellDataContainerPointer;
00189   typedef typename Superclass::CellDataContainerIterator
00190                                                   CellDataContainerIterator;
00191 
00192   // Point / Cell correspondance section:
00193   typedef typename Superclass::PointCellLinksContainer
00194                                         PointCellLinksContainer;
00195   typedef typename Superclass::PointCellLinksContainerIterator
00196                                         PointCellLinksContainerIterator;
00197 
00198   // BoundaryAssignMents section:
00199   typedef typename Superclass::BoundaryAssignmentsContainer
00200                                BoundaryAssignmentsContainer;
00201   typedef typename Superclass::BoundaryAssignmentsContainerPointer
00202                                BoundaryAssignmentsContainerPointer;
00203   typedef typename Superclass::BoundaryAssignmentsContainerVector
00204                                BoundaryAssignmentsContainerVector;
00205 
00206   // Miscelaneous section:
00207   typedef typename Superclass::BoundingBoxPointer         BoundingBoxPointer;
00208   typedef typename Superclass::BoundingBoxType            BoundingBoxType;
00209   typedef typename Superclass::RegionType                 RegionType;
00210   typedef typename Superclass::InterpolationWeightType
00211                                InterpolationWeightType;
00212 
00214   typedef typename Traits::PrimalDataType PrimalDataType;
00215   typedef typename Traits::DualDataType   DualDataType;
00216   typedef typename Traits::QEPrimal       QEPrimal;
00217   typedef typename Traits::QEDual         QEDual;
00218   typedef typename Traits::QEPrimal       QEType;
00219   // See the TODO entry dated from 2005-05-28
00220   // struct QEType : public QEPrimal, public QEDual {}
00221   typedef typename Traits::VertexRefType  VertexRefType;
00222   typedef typename Traits::FaceRefType    FaceRefType;
00223   typedef typename Traits::VectorType     VectorType;
00224 
00226   typedef QuadEdgeMeshLineCell< CellType >    EdgeCellType;
00227   typedef QuadEdgeMeshPolygonCell< CellType > PolygonCellType;
00228 
00230   typedef std::queue< PointIdentifier > FreePointIndexesType;
00231   typedef std::queue< CellIdentifier >  FreeCellIndexesType;
00232 
00234   typedef std::vector< PointIdentifier >    PointIdList;
00235   typedef std::list< QEPrimal* >            EdgeListType;
00236   typedef EdgeListType*                     EdgeListPointerType;
00237 
00239   static const PointIdentifier m_NoPoint;
00240 
00242   static const CellIdentifier m_NoFace;
00243 
00244 public:
00245 
00247   itkNewMacro( Self );
00248   itkTypeMacro( QuadEdgeMesh, Mesh );
00250 
00251 #if !defined(CABLE_CONFIGURATION)
00252 
00253   itkQEDefineFrontIteratorMethodsMacro( Self );
00254 #endif
00255 
00256 public:
00257 
00258   // Multithreading framework: not tested yet.
00259   virtual bool RequestedRegionIsOutsideOfTheBufferedRegion()
00260     {
00261     return( false );
00262     }
00263 
00264   virtual void Initialize();
00265 
00267   virtual void Clear();
00268 
00269   CellsContainer * GetEdgeCells() {return m_EdgeCellsContainer;}
00270   const CellsContainer * GetEdgeCells() const {return m_EdgeCellsContainer;}
00271   void SetEdgeCells(CellsContainer * edgeCells)
00272     {m_EdgeCellsContainer = edgeCells;}
00273   void SetEdgeCell(CellIdentifier cellId, CellAutoPointer & cellPointer )
00274     {m_EdgeCellsContainer->InsertElement(cellId,cellPointer.ReleaseOwnership());}
00275 
00276 
00283   virtual void CopyInformation( const DataObject* data ) { (void)data; }
00284   virtual void Graft( const DataObject* data );
00286 
00288   void SqueezePointsIds( );
00289 
00291   void BuildCellLinks() { }
00292 
00293 #if !defined(CABLE_CONFIGURATION)
00294 
00295   void SetBoundaryAssignments(int dimension,
00296                               BoundaryAssignmentsContainer* container)
00297     {
00298     (void)dimension;
00299     (void)container;
00300     }
00302 
00304   BoundaryAssignmentsContainerPointer GetBoundaryAssignments(int dimension)
00305     {
00306     (void)dimension;
00307     return( (BoundaryAssignmentsContainerPointer)0 );
00308     }
00310 
00312   const BoundaryAssignmentsContainerPointer GetBoundaryAssignments(
00313     int dimension) const
00314     {
00315     (void)dimension;
00316     return( (const BoundaryAssignmentsContainerPointer)0 );
00317     }
00318 #endif
00319 
00320 
00322   void SetBoundaryAssignment(int dimension, CellIdentifier cellId,
00323                              CellFeatureIdentifier featureId,
00324                              CellIdentifier boundaryId)
00325     {
00326     (void)dimension;
00327     (void)cellId;
00328     (void)featureId;
00329     (void)boundaryId;
00330     }
00332 
00334   bool GetBoundaryAssignment(int dimension, CellIdentifier cellId,
00335                              CellFeatureIdentifier featureId,
00336                              CellIdentifier* boundaryId) const
00337     {
00338     (void)dimension;
00339     (void)cellId;
00340     (void)featureId;
00341     (void)boundaryId;
00342     return( false ); // ALEX: is it the good way?
00343     }
00345 
00347   bool RemoveBoundaryAssignment(int dimension, CellIdentifier cellId,
00348                                 CellFeatureIdentifier featureId)
00349     {
00350     (void)dimension;
00351     (void)cellId;
00352     (void)featureId;
00353     return( false ); // ALEX: is it the good way?
00354     }
00356 
00358   bool GetCellBoundaryFeature(int dimension, CellIdentifier cellId,
00359                               CellFeatureIdentifier featureId,
00360                               CellAutoPointer& cellAP) const
00361     { 
00362     (void)dimension;
00363     (void)cellId;
00364     (void)featureId;
00365     (void)cellAP;
00366     return( false );
00367     }
00369 
00371   unsigned long GetCellBoundaryFeatureNeighbors(int dimension,
00372                                              CellIdentifier cellId,
00373                                              CellFeatureIdentifier featureId,
00374                                              std::set<CellIdentifier>* cellSet)
00375     {
00376     (void)dimension;
00377     (void)cellId;
00378     (void)featureId;
00379     cellSet = (std::set<CellIdentifier>*)0;
00380     return( (unsigned long)0 );
00381     }
00383 
00385   unsigned long GetCellNeighbors( CellIdentifier cellId,
00386                                   std::set<CellIdentifier>* cellSet )
00387     {
00388     (void)cellId;
00389     cellSet = (std::set<CellIdentifier>*)0;
00390     return( (unsigned long)0 );
00391     }
00393 
00395   bool GetAssignedCellBoundaryIfOneExists(int dimension,
00396                                           CellIdentifier cellId,
00397                                           CellFeatureIdentifier featureId,
00398                                           CellAutoPointer& cellAP) const
00399     {
00400     (void)dimension;
00401     (void)featureId;
00402     (void)cellAP;
00403     return( false ); // ALEX: is it the good way?
00404     }
00406 
00408   void SetCell( CellIdentifier cId, CellAutoPointer& cell );
00409 
00411   virtual PointIdentifier FindFirstUnusedPointIndex();
00412   virtual CellIdentifier  FindFirstUnusedCellIndex();
00414 
00415   virtual void PushOnContainer( EdgeCellType* newEdge );
00416 
00417   // Adding Point/Edge/Face methods
00418   virtual PointIdentifier AddPoint( const PointType& p );
00419   
00421   virtual QEPrimal* AddEdge( const PointIdentifier& orgPid,
00422                              const PointIdentifier& destPid );
00423   virtual QEPrimal* AddEdgeWithSecurePointList( const PointIdentifier& orgPid,
00424                              const PointIdentifier& destPid );
00426 
00428   virtual void      AddFace( QEPrimal* e );
00429 
00434   virtual QEPrimal* AddFace( const PointIdList& points );
00435   virtual QEPrimal* AddFaceWithSecurePointList( const PointIdList& points );
00436   virtual QEPrimal* AddFaceWithSecurePointList( const PointIdList& points,
00437                                                 bool CheckEdges );
00439 
00441   virtual QEPrimal* AddFaceTriangle( const PointIdentifier& aPid,
00442                                      const PointIdentifier& bPid,
00443                                      const PointIdentifier& cPid );
00444 
00446   virtual void DeletePoint( const PointIdentifier& pid );
00447   virtual void DeleteEdge( const PointIdentifier& orgPid,
00448                            const PointIdentifier& destPid );
00449   virtual void DeleteEdge( QEPrimal* e );
00450   virtual void LightWeightDeleteEdge( EdgeCellType* e );
00451   virtual void LightWeightDeleteEdge( QEPrimal* e );
00452   virtual void DeleteFace( FaceRefType faceToDelete );
00454 
00455   // 
00456   bool GetPoint( PointIdentifier pid, PointType * pt) const
00457     {
00458     return( Superclass::GetPoint( pid, pt ) );
00459     }
00460   virtual PointType  GetPoint ( const PointIdentifier& pid ) const;
00461   virtual VectorType GetVector( const PointIdentifier& pid ) const;
00462   virtual QEPrimal*  GetEdge() const;
00463   virtual QEPrimal*  GetEdge( const CellIdentifier& eid ) const;
00464   virtual QEPrimal*  FindEdge( const PointIdentifier& pid0 ) const;
00465   virtual QEPrimal*  FindEdge( const PointIdentifier& pid0,
00466                                const PointIdentifier& pid1 ) const;
00467 
00468   virtual EdgeCellType*  FindEdgeCell( const PointIdentifier& pid0,
00469                                  const PointIdentifier& pid1 ) const;
00470 
00472   CoordRepType ComputeEdgeLength( QEPrimal* e );
00473 
00474   unsigned long ComputeNumberOfPoints() const;
00475   unsigned long ComputeNumberOfFaces() const;
00476   unsigned long ComputeNumberOfEdges() const;
00477 
00478   PointIdentifier Splice( QEPrimal* a, QEPrimal* b );
00479 
00480 #ifdef ITK_USE_CONCEPT_CHECKING
00481 
00482   itkConceptMacro(DimensionShouldBe3,
00483     (Concept::SameDimension<itkGetStaticConstMacro(PointDimension),3>));
00484 
00486 #endif
00487 
00488   // for reusability of a mesh in the MeshToMesh filter
00489   void ClearFreePointAndCellIndexesLists( )
00490     {
00491     while( !this->m_FreePointIndexes.empty( ) )
00492       {
00493       this->m_FreePointIndexes.pop( );
00494       }
00495     while( !this->m_FreeCellIndexes.empty( ) )
00496       {
00497       this->m_FreeCellIndexes.pop( );
00498       }
00499     }
00500 
00501   CellIdentifier GetNumberOfFaces( ) const {return( m_NumberOfFaces ); }
00502   CellIdentifier GetNumberOfEdges( ) const {return( m_NumberOfEdges ); }
00503 
00504 protected:
00506   QuadEdgeMesh();
00507   virtual ~QuadEdgeMesh(); 
00509 
00511   virtual void ClearCellsContainer();
00512 
00513   CellsContainerPointer  m_EdgeCellsContainer;
00514 
00515 private:
00516   QuadEdgeMesh( const Self& );    //purposely not implemented
00517   void operator=( const Self& );  //purposely not implemented
00518   CellIdentifier m_NumberOfFaces;
00519   CellIdentifier m_NumberOfEdges;
00520 
00521 protected:
00522   FreePointIndexesType m_FreePointIndexes;
00523   FreeCellIndexesType  m_FreeCellIndexes;
00524 
00525 };
00526 
00527 }
00528 
00529 
00530 #ifndef ITK_MANUAL_INSTANTIATION
00531 #include "itkQuadEdgeMesh.txx"
00532 #endif
00533 
00534 #endif
00535 

Generated at Tue Sep 15 04:25:07 2009 for ITK by doxygen 1.5.8 written by Dimitri van Heesch, © 1997-2000