itkQuadEdgeMesh.h

Go to the documentation of this file.

/*=========================================================================

  Program:   Insight Segmentation & Registration Toolkit
  Module:    $RCSfile: itkQuadEdgeMesh.h,v $
  Language:  C++
  Date:      $Date: 2009-02-07 23:16:28 $
  Version:   $Revision: 1.33 $

  Copyright (c) Insight Software Consortium. All rights reserved.
  See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.

     This software is distributed WITHOUT ANY WARRANTY; without even
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
     PURPOSE.  See the above copyright notices for more information.

=========================================================================*/

#ifndef __itkQuadEdgeMesh_h
#define __itkQuadEdgeMesh_h

#include "vcl_cstdarg.h"
#include <queue>
#include <vector>
#include <list>

#include "itkMesh.h"

#include "itkQuadEdgeMeshTraits.h"
#include "itkQuadEdgeMeshLineCell.h"
#include "itkQuadEdgeMeshPolygonCell.h"

#include "itkQuadEdgeMeshFrontIterator.h"
#include "itkConceptChecking.h"

namespace itk
{

template< typename TPixel, unsigned int VDimension,
  typename TTraits = QuadEdgeMeshTraits< TPixel, VDimension, bool, bool > >
class QuadEdgeMesh : public Mesh< TPixel, VDimension, TTraits >
{
public:

  typedef TTraits Traits;
  typedef TPixel  PixelType;

  typedef QuadEdgeMesh                            Self;
  typedef Mesh< TPixel, VDimension, Traits >      Superclass;
  typedef SmartPointer< Self >                    Pointer;
  typedef SmartPointer< const Self >              ConstPointer;

  itkStaticConstMacro( PointDimension, unsigned int,
                       Traits::PointDimension );
  itkStaticConstMacro( MaxTopologicalDimension, unsigned int,
                       Traits::MaxTopologicalDimension );

  typedef typename Superclass::CellPixelType    CellPixelType;
  typedef typename Superclass::CoordRepType     CoordRepType;
  typedef typename Superclass::PointIdentifier  PointIdentifier;
  typedef typename Superclass::PointHashType    PointHashType;
  typedef typename Superclass::PointType        PointType;
  typedef typename Superclass::CellTraits       CellTraits;

  typedef typename CellTraits::PointIdInternalIterator PointIdInternalIterator;
  typedef typename CellTraits::PointIdIterator         PointIdIterator;

  // Point section:
  typedef typename Superclass::PointsContainer        PointsContainer;
  typedef typename Superclass::PointsContainerPointer PointsContainerPointer;
  typedef typename Superclass::PointLocatorPointer    PointLocatorPointer;
  typedef typename Superclass::PointLocatorType       PointLocatorType;
  typedef CoordRepType  CoordRepArrayType[ 
                              itkGetStaticConstMacro( PointDimension ) ];

  // Point data section:
  typedef typename Superclass::PointDataContainer     PointDataContainer;
  typedef typename Superclass::PointDataContainerPointer
                               PointDataContainerPointer;
  typedef typename Superclass::PointDataContainerIterator
                               PointDataContainerIterator;
  typedef typename Superclass::PointsContainerConstIterator
                               PointsContainerConstIterator;
  typedef typename Superclass::PointsContainerIterator
                               PointsContainerIterator;

  // Cell section:
  typedef typename Superclass::CellIdentifier         CellIdentifier;
  typedef typename Superclass::CellType               CellType;
  typedef typename Superclass::CellAutoPointer        CellAutoPointer;
  typedef typename Superclass::CellFeatureIdentifier  CellFeatureIdentifier;
  typedef typename Superclass::CellFeatureCount       CellFeatureCount;
  typedef typename Superclass::CellMultiVisitorType   CellMultiVisitorType;
  typedef typename Superclass::CellsContainer         CellsContainer;
  typedef typename Superclass::CellsContainerPointer  CellsContainerPointer;

  typedef typename Superclass::CellsContainerConstIterator
                                                  CellsContainerConstIterator;
  typedef typename Superclass::CellsContainerIterator
                                                  CellsContainerIterator;

  typedef typename Superclass::CellLinksContainer CellLinksContainer;
  typedef typename Superclass::CellLinksContainerPointer
                                                  CellLinksContainerPointer;
  typedef typename Superclass::CellLinksContainerIterator
                                                  CellLinksContainerIterator;

  // Cell data section:
  typedef typename Superclass::CellDataContainer  CellDataContainer;
  typedef typename Superclass::CellDataContainerPointer
                                                  CellDataContainerPointer;
  typedef typename Superclass::CellDataContainerIterator
                                                  CellDataContainerIterator;

  // Point / Cell correspondance section:
  typedef typename Superclass::PointCellLinksContainer
                                        PointCellLinksContainer;
  typedef typename Superclass::PointCellLinksContainerIterator
                                        PointCellLinksContainerIterator;

  // BoundaryAssignMents section:
  typedef typename Superclass::BoundaryAssignmentsContainer
                               BoundaryAssignmentsContainer;
  typedef typename Superclass::BoundaryAssignmentsContainerPointer
                               BoundaryAssignmentsContainerPointer;
  typedef typename Superclass::BoundaryAssignmentsContainerVector
                               BoundaryAssignmentsContainerVector;

  // Miscelaneous section:
  typedef typename Superclass::BoundingBoxPointer         BoundingBoxPointer;
  typedef typename Superclass::BoundingBoxType            BoundingBoxType;
  typedef typename Superclass::RegionType                 RegionType;
  typedef typename Superclass::InterpolationWeightType
                               InterpolationWeightType;

  typedef typename Traits::PrimalDataType PrimalDataType;
  typedef typename Traits::DualDataType   DualDataType;
  typedef typename Traits::QEPrimal       QEPrimal;
  typedef typename Traits::QEDual         QEDual;
  typedef typename Traits::QEPrimal       QEType;
  // See the TODO entry dated from 2005-05-28
  // struct QEType : public QEPrimal, public QEDual {}
  typedef typename Traits::VertexRefType  VertexRefType;
  typedef typename Traits::FaceRefType    FaceRefType;
  typedef typename Traits::VectorType     VectorType;

  typedef QuadEdgeMeshLineCell< CellType >    EdgeCellType;
  typedef QuadEdgeMeshPolygonCell< CellType > PolygonCellType;

  typedef std::queue< PointIdentifier > FreePointIndexesType;
  typedef std::queue< CellIdentifier >  FreeCellIndexesType;

  typedef std::vector< PointIdentifier >    PointIdList;
  typedef std::list< QEPrimal* >            EdgeListType;
  typedef EdgeListType*                     EdgeListPointerType;

  static const PointIdentifier m_NoPoint;

  static const CellIdentifier m_NoFace;

public:

  itkNewMacro( Self );
  itkTypeMacro( QuadEdgeMesh, Mesh );

  itkQEDefineFrontIteratorMethodsMacro( Self );


public:

  // Multithreading framework: not tested yet.
  virtual bool RequestedRegionIsOutsideOfTheBufferedRegion()
    {
    return( false );
    }

  virtual void Initialize();

  virtual void Clear();

  CellsContainerPointer GetEdgeCells() {return m_EdgeCellsContainer;}
  const CellsContainerPointer GetEdgeCells() const {return m_EdgeCellsContainer;}
  void SetEdgeCells(CellsContainerPointer edgeCells)
    {m_EdgeCellsContainer = edgeCells;}
  void SetEdgeCell(CellIdentifier cellId, CellAutoPointer & cellPointer )
    {m_EdgeCellsContainer->InsertElement(cellId,cellPointer.ReleaseOwnership());}


  virtual void CopyInformation( const DataObject* data ) { (void)data; }
  virtual void Graft( const DataObject* data );

  void SqueezePointsIds( );

  void BuildCellLinks() { }

  void SetBoundaryAssignments(int dimension,
                              BoundaryAssignmentsContainer* container)
    {
    (void)dimension;
    (void)container;
    }

  BoundaryAssignmentsContainerPointer GetBoundaryAssignments(int dimension)
    {
    (void)dimension;
    return( (BoundaryAssignmentsContainerPointer)0 );
    }

  const BoundaryAssignmentsContainerPointer GetBoundaryAssignments(
    int dimension) const
    {
    (void)dimension;
    return( (const BoundaryAssignmentsContainerPointer)0 );
    }

  void SetBoundaryAssignment(int dimension, CellIdentifier cellId,
                             CellFeatureIdentifier featureId,
                             CellIdentifier boundaryId)
    {
    (void)dimension;
    (void)cellId;
    (void)featureId;
    (void)boundaryId;
    }

  bool GetBoundaryAssignment(int dimension, CellIdentifier cellId,
                             CellFeatureIdentifier featureId,
                             CellIdentifier* boundaryId) const
    {
    (void)dimension;
    (void)cellId;
    (void)featureId;
    (void)boundaryId;
    return( false ); // ALEX: is it the good way?
    }

  bool RemoveBoundaryAssignment(int dimension, CellIdentifier cellId,
                                CellFeatureIdentifier featureId)
    {
    (void)dimension;
    (void)cellId;
    (void)featureId;
    return( false ); // ALEX: is it the good way?
    }

  bool GetCellBoundaryFeature(int dimension, CellIdentifier cellId,
                              CellFeatureIdentifier featureId,
                              CellAutoPointer& cellAP) const
    { 
    (void)dimension;
    (void)cellId;
    (void)featureId;
    (void)cellAP;
    return( false );
    }

  unsigned long GetCellBoundaryFeatureNeighbors(int dimension,
                                             CellIdentifier cellId,
                                             CellFeatureIdentifier featureId,
                                             std::set<CellIdentifier>* cellSet)
    {
    (void)dimension;
    (void)cellId;
    (void)featureId;
    cellSet = (std::set<CellIdentifier>*)0;
    return( (unsigned long)0 );
    }

  unsigned long GetCellNeighbors( CellIdentifier cellId,
                                  std::set<CellIdentifier>* cellSet )
    {
    (void)cellId;
    cellSet = (std::set<CellIdentifier>*)0;
    return( (unsigned long)0 );
    }

  bool GetAssignedCellBoundaryIfOneExists(int dimension,
                                          CellIdentifier cellId,
                                          CellFeatureIdentifier featureId,
                                          CellAutoPointer& cellAP) const
    {
    (void)dimension;
    (void)featureId;
    (void)cellAP;
    return( false ); // ALEX: is it the good way?
    }

  void SetCell( CellIdentifier cId, CellAutoPointer& cell );

  virtual PointIdentifier FindFirstUnusedPointIndex();
  virtual CellIdentifier  FindFirstUnusedCellIndex();

  virtual void PushOnContainer( EdgeCellType* newEdge );

  // Adding Point/Edge/Face methods
  virtual PointIdentifier AddPoint( const PointType& p );
  
  virtual QEPrimal* AddEdge( const PointIdentifier& orgPid,
                             const PointIdentifier& destPid );
  virtual QEPrimal* AddEdgeWithSecurePointList( const PointIdentifier& orgPid,
                             const PointIdentifier& destPid );

  virtual void      AddFace( QEPrimal* e );

  virtual QEPrimal* AddFace( const PointIdList& points );
  virtual QEPrimal* AddFaceWithSecurePointList( const PointIdList& points );
  virtual QEPrimal* AddFaceWithSecurePointList( const PointIdList& points,
                                                bool CheckEdges );

  virtual QEPrimal* AddFaceTriangle( const PointIdentifier& aPid,
                                     const PointIdentifier& bPid,
                                     const PointIdentifier& cPid );

  virtual void DeletePoint( const PointIdentifier& pid );
  virtual void DeleteEdge( const PointIdentifier& orgPid,
                           const PointIdentifier& destPid );
  virtual void DeleteEdge( QEPrimal* e );
  virtual void LightWeightDeleteEdge( EdgeCellType* e );
  virtual void LightWeightDeleteEdge( QEPrimal* e );
  virtual void DeleteFace( FaceRefType faceToDelete );

  // 
  bool GetPoint( PointIdentifier pid, PointType * pt) const
    {
    return( Superclass::GetPoint( pid, pt ) );
    }
  virtual PointType  GetPoint ( const PointIdentifier& pid ) const;
  virtual VectorType GetVector( const PointIdentifier& pid ) const;
  virtual QEPrimal*  GetEdge() const;
  virtual QEPrimal*  GetEdge( const CellIdentifier& eid ) const;
  virtual QEPrimal*  FindEdge( const PointIdentifier& pid0 ) const;
  virtual QEPrimal*  FindEdge( const PointIdentifier& pid0,
                               const PointIdentifier& pid1 ) const;

  virtual EdgeCellType*  FindEdgeCell( const PointIdentifier& pid0,
                                 const PointIdentifier& pid1 ) const;

  CoordRepType ComputeEdgeLength( QEPrimal* e );

  unsigned long ComputeNumberOfPoints() const;
  unsigned long ComputeNumberOfFaces() const;
  unsigned long ComputeNumberOfEdges() const;

  PointIdentifier Splice( QEPrimal* a, QEPrimal* b );

#ifdef ITK_USE_CONCEPT_CHECKING

  itkConceptMacro(DimensionShouldBe3,
    (Concept::SameDimension<itkGetStaticConstMacro(PointDimension),3>));

#endif

  // for reusability of a mesh in the MeshToMesh filter
  void ClearFreePointAndCellIndexesLists( )
    {
    while( !this->m_FreePointIndexes.empty( ) )
      {
      this->m_FreePointIndexes.pop( );
      }
    while( !this->m_FreeCellIndexes.empty( ) )
      {
      this->m_FreeCellIndexes.pop( );
      }
    }

  CellIdentifier GetNumberOfFaces( ) const {return( m_NumberOfFaces ); }
  CellIdentifier GetNumberOfEdges( ) const {return( m_NumberOfEdges ); }

protected:
  QuadEdgeMesh();
  virtual ~QuadEdgeMesh(); 

  CellsContainerPointer  m_EdgeCellsContainer;

private:
  QuadEdgeMesh( const Self& );    //purposely not implemented
  void operator=( const Self& );  //purposely not implemented
  CellIdentifier m_NumberOfFaces;
  CellIdentifier m_NumberOfEdges;

protected:
  FreePointIndexesType m_FreePointIndexes;
  FreeCellIndexesType  m_FreeCellIndexes;

};

}


#ifndef ITK_MANUAL_INSTANTIATION
#include "itkQuadEdgeMesh.txx"
#endif

#endif