libinsighttoolkit3-dev 3.20.1-1 / usr / include / InsightToolkit / Review / itkQuadEdgeMesh.h

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

  Program:   Insight Segmentation & Registration Toolkit
  Module:    itkQuadEdgeMesh.h
  Language:  C++
  Date:      $Date$
  Version:   $Revision$

  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"

/****
 * \brief Documentation of itkQE namespace
 * \todo More comments here !
 *
 * \note Design notes: some QuadEdgeMesh algorithms are based on iterating
 * various connectivity operators e.g. curvature driven surface deformation.
 * Many of those connectivity altering operators (e.g. the Euler operators)
 * are lightweight in the sense that they only modify very limited regions
 * of a QuadEdgeMesh: they typically act within the range of couple edges of
 * distance from a considered vertex, edge or face.
 * On the one side, we cannot choose to implement those atomic operations
 * as "classical" itk filters since each filter invocation yields a new
 * copy of the input mesh as its output: this would drasticaly
 * increase the memory consumption.
 * In fact, those atomic operations have a too much finer grain to be
 * implemeted as filters: the filter is more at the scale of the
 * application of a large number of such atomic operations.
 * One the other hand, we cannot choose to implement those atomic operations
 * as methods of this QuadEdgeMesh class (or a derived one) at the risk of
 * rapid code bloat.
 * Maybe we could choose to make thematic regroupment within derived
 * classes, but this would force an end user to multiple inheritance which
 * can prove to be a drag in a templated context.
 * Eventually, we chose to implement them as function object: the
 * loosely coupling of those operation methods with the targeted QuadEdgeMesh
 * object and heavier invocation syntax are a small price to pay in
 * exchange for optimal memory usage and end user modularity.
 * But we couldn't inherit from \ref FunctionBase since its
 * Evaluate( const InputType& input ) method promises to leave its
 * argument (the mesh we want to modify in our case) untouched.
 * Hence we created the \ref itkQE::MeshFunctionBase class whose main
 * difference with \ref FunctionBase is that its Evaluate()
 * method allows to modify the considered mesh.
 * When considering a new QuadEdgeMesh method we are left with four possible
 * "slots" to implement it:
 *   - the QuadEdgeMesh method
 *   - a derived class from FunctionBase when the method leaves
 *     the mesh constant.
 *   - a derived class from \ref itkQE::MeshFunctionBase when the
 *     method modifies the mesh (typically in the case of Euler operators)
 *   - as a classic Mesh filter.
 * The choice of the slot is a mere matter of trade-off and in order
 * to keep QuadEdgeMesh tiny and humanly readable key decision factors
 * can be the occurence of the calls and the human level complexity of
 * the code.
 * With those criteria in mind we made the following choices:
 *   - really atomic, lightweight and general purpose methods like
 *     \ref Mesh::ComputeNumberOfPoints are left within the Mesh class.
 *   - heavier methods and less often called like
 *     \ref SanityCheckMeshFunction were implemented as derived classes of
 *     \ref FunctionBase.
 *   - methods with the same weight (measured e.g. in number of lines of
 *     code) but that modify the considered mesh, like
 *     \ref BoundaryEdgesMeshFunction or
 *     \ref ZipMeshFunction, were implemented as derived classes of
 *     \ref itkQE::MeshFunctionBase. Still the mesh modifications are
 *     really limited and concern a couple edges.
 *   - more specialised methods, with a wider scope and that require a
 *     copy of the mesh should follow the classical itk Filter pattern,
 *     like \ref itkQE::MeshExtractComponentFilter, and inherit from
 *     \ref MeshToMeshFilter.
 */
namespace itk
{
/**
 * \class QuadEdgeMesh
 *
 * \brief Mesh class for 2D manifolds embedded in ND space.
 *
 * \author Alexandre Gouaillard, Leonardo Florez-Valencia, Eric Boix
 *
 * This implementation was contributed as a paper to the Insight Journal
 * http://insight-journal.org/midas/handle.php?handle=1926/306
 *
 */
template< typename TPixel, unsigned int VDimension,
  typename TTraits = QuadEdgeMeshTraits< TPixel, VDimension, bool, bool > >
class QuadEdgeMesh : public Mesh< TPixel, VDimension, TTraits >
{
public:
  /** Input template parameters. */
  typedef TTraits Traits;
  typedef TPixel  PixelType;

  /** Standard typedefs. */
  typedef QuadEdgeMesh                            Self;
  typedef Mesh< TPixel, VDimension, Traits >      Superclass;
  typedef SmartPointer< Self >                    Pointer;
  typedef SmartPointer< const Self >              ConstPointer;

  /** Convenient constants obtained from MeshTraits. */
  itkStaticConstMacro( PointDimension, unsigned int,
                       Traits::PointDimension );
  itkStaticConstMacro( MaxTopologicalDimension, unsigned int,
                       Traits::MaxTopologicalDimension );

  /** Types defined in superclass. */
  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;

  /** Specific types for a quad-edge structure. */
  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;

  /** Possible specialized cell types. */
  typedef QuadEdgeMeshLineCell< CellType >    EdgeCellType;
  typedef QuadEdgeMeshPolygonCell< CellType > PolygonCellType;

  /** Free insertion indexes. */
  typedef std::queue< PointIdentifier > FreePointIndexesType;
  typedef std::queue< CellIdentifier >  FreeCellIndexesType;

  /** Auxiliary types. */
  typedef std::vector< PointIdentifier >    PointIdList;
  typedef std::list< QEPrimal* >            EdgeListType;
  typedef EdgeListType*                     EdgeListPointerType;

  /** Reserved PointIdentifier designated to represent the absence of Point */
  static const PointIdentifier m_NoPoint;

  /** Reserved CellIdentifier designated to represent the absence of Face */
  static const CellIdentifier m_NoFace;

public:

  /** Basic Object interface. */
  itkNewMacro( Self );
  itkTypeMacro( QuadEdgeMesh, Mesh );

#if !defined(CABLE_CONFIGURATION)
  /** FrontIterator definitions */
  itkQEDefineFrontIteratorMethodsMacro( Self );
#endif

public:

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

  virtual void Initialize();

  /** another way of deleting all the cells */
  virtual void Clear();

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


  /** Overloaded to avoid a bug in Mesh that prevents proper inheritance
   * Refer to
   * http://public.kitware.com/pipermail/insight-users/2005-March/012459.html
   * and
   * http://public.kitware.com/pipermail/insight-users/2005-April/012613.html
   */
  virtual void CopyInformation( const DataObject* data ) { (void)data; }
  virtual void Graft( const DataObject* data );

  /** squeeze the point container to be able to write the file properly */
  void SqueezePointsIds( );

  /** overloaded method for backward compatibility */
  void BuildCellLinks() { }

#if !defined(CABLE_CONFIGURATION)
  /** overloaded method for backward compatibility */
  void SetBoundaryAssignments(int dimension,
                              BoundaryAssignmentsContainer* container)
    {
    (void)dimension;
    (void)container;
    }
  
  /** overloaded method for backward compatibility */
  BoundaryAssignmentsContainerPointer GetBoundaryAssignments(int dimension)
    {
    (void)dimension;
    return( (BoundaryAssignmentsContainerPointer)0 );
    }

  /** overloaded method for backward compatibility */
  const BoundaryAssignmentsContainerPointer GetBoundaryAssignments(
    int dimension) const
    {
    (void)dimension;
    return( (const BoundaryAssignmentsContainerPointer)0 );
    }
#endif

  /** overloaded method for backward compatibility */
  void SetBoundaryAssignment(int dimension, CellIdentifier cellId,
                             CellFeatureIdentifier featureId,
                             CellIdentifier boundaryId)
    {
    (void)dimension;
    (void)cellId;
    (void)featureId;
    (void)boundaryId;
    }

  /** overloaded method for backward compatibility */
  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?
    }

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

  /** overloaded method for backward compatibility */
  bool GetCellBoundaryFeature(int dimension, CellIdentifier cellId,
                              CellFeatureIdentifier featureId,
                              CellAutoPointer& cellAP) const
    { 
    (void)dimension;
    (void)cellId;
    (void)featureId;
    (void)cellAP;
    return( false );
    }

  /** overloaded method for backward compatibility */
  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 );
    }
  
  /** NOTE ALEX: this method do not use CellFeature and thus could be recoded */
  unsigned long GetCellNeighbors( CellIdentifier cellId,
                                  std::set<CellIdentifier>* cellSet )
    {
    (void)cellId;
    cellSet = (std::set<CellIdentifier>*)0;
    return( (unsigned long)0 );
    }

  /** overloaded method for backward compatibility */
  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?
    }

  /** overloaded method for backward compatibility */
  void SetCell( CellIdentifier cId, CellAutoPointer& cell );

  /** Methods to simplify point/edge insertion/search. */
  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 );

  /** Add a polygonal face to the Mesh, suppose QE layer ready */
  virtual void      AddFace( QEPrimal* e );

  /** Add a polygonal face to the Mesh. The list of points 
   * is expected to be ordered counter-clock wise. The inside
   * of the new face will be on the left side of the edges 
   * formed by consecutive points in this list. */
  virtual QEPrimal* AddFace( const PointIdList& points );
  virtual QEPrimal* AddFaceWithSecurePointList( const PointIdList& points );
  virtual QEPrimal* AddFaceWithSecurePointList( const PointIdList& points,
                                                bool CheckEdges );

  /** Adds a triangular face to the Mesh */
  virtual QEPrimal* AddFaceTriangle( const PointIdentifier& aPid,
                                     const PointIdentifier& bPid,
                                     const PointIdentifier& cPid );

  /** Deletion methods */
  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;

  ///  Compute the euclidian length of argument edge
  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
  /** Begin concept checking */
  itkConceptMacro(DimensionShouldBe3,
    (Concept::SameDimension<itkGetStaticConstMacro(PointDimension),3>));
  /** End concept checking */
#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:
  /** Constructor and Destructor. */
  QuadEdgeMesh();
  virtual ~QuadEdgeMesh(); 

  /** Release the memory of each one of the cells independently. */
  virtual void ClearCellsContainer();

  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