itkQuadEdgeMeshEdgeMergeDecimationFilter.h

Go to the documentation of this file.

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

  Program:   Insight Segmentation & Registration Toolkit
  Module:    $RCSfile: itkQuadEdgeMeshEdgeMergeDecimationFilter.h,v $
  Language:  C++
  Date:      $Date: 2009-02-11 15:05:41 $
  Version:   $Revision: 1.3 $

  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 __itkQuadEdgeMeshEdgeMergeDecimationFilter_h
#define __itkQuadEdgeMeshEdgeMergeDecimationFilter_h

#include <list>
#include <map>
#include <algorithm>

#include <itkQuadEdgeMeshEulerOperatorJoinVertexFunction.h>
#include <itkQuadEdgeMeshPolygonCell.h>

#include "itkQuadEdgeMeshDecimationFilter.h"
#include "itkPriorityQueueContainer.h"
#include "itkTriangleHelper.h"

namespace itk
{
template< class TInput, class TOutput, class TCriterion >
class QuadEdgeMeshEdgeMergeDecimationFilter :
      public QuadEdgeMeshDecimationFilter< TInput, TOutput, TCriterion >
{
public:
  typedef QuadEdgeMeshEdgeMergeDecimationFilter             Self;
  typedef SmartPointer< Self >                              Pointer;
  typedef SmartPointer< const Self >                        ConstPointer;
  typedef QuadEdgeMeshDecimationFilter< 
    TInput, TOutput, TCriterion >                           Superclass;

  itkTypeMacro( QuadEdgeMeshEdgeMergeDecimationFilter, QuadEdgeMeshDecimationFilter );

  typedef TInput                                            InputMeshType;
  typedef typename InputMeshType::Pointer                   InputMeshPointer;

  typedef TOutput                                           OutputMeshType;
  typedef typename OutputMeshType::Pointer                  OutputMeshPointer;
  typedef typename OutputMeshType::PointIdentifier          OutputPointIdentifier;
  typedef typename OutputMeshType::PointType                OutputPointType;
  typedef typename OutputPointType::VectorType              OutputVectorType;
  typedef typename OutputMeshType::QEType                   OutputQEType;
  typedef typename OutputMeshType::EdgeCellType             OutputEdgeCellType;
  typedef typename OutputMeshType::CellType                 OutputCellType;
  typedef typename OutputMeshType::CellIdentifier           OutputCellIdentifier;
  typedef typename OutputMeshType::CellsContainerPointer    OutputCellsContainerPointer;
  typedef typename OutputMeshType::CellsContainerIterator   OutputCellsContainerIterator;

  typedef QuadEdgeMeshPolygonCell< OutputCellType >         OutputPolygonType;

  typedef TCriterion                                        CriterionType;
  typedef typename CriterionType::Pointer                   CriterionPointer;
  typedef typename CriterionType::MeasureType               MeasureType;
  typedef typename CriterionType::PriorityType              PriorityType;
  typedef typename CriterionType::PriorityQueueWrapperType  PriorityQueueItemType;
    
  typedef PriorityQueueContainer< PriorityQueueItemType*,
    ElementWrapperPointerInterface< PriorityQueueItemType* >,
    PriorityType >                                          PriorityQueueType;
  typedef typename PriorityQueueType::Pointer               PriorityQueuePointer;

  typedef std::map< OutputQEType*, PriorityQueueItemType* > QueueMapType;
  typedef typename QueueMapType::iterator                   QueueMapIterator;

  typedef QuadEdgeMeshEulerOperatorJoinVertexFunction< 
    OutputMeshType, OutputQEType >                          OperatorType;
  typedef typename OperatorType::Pointer                    OperatorPointer;

protected:

  QuadEdgeMeshEdgeMergeDecimationFilter();
  virtual ~QuadEdgeMeshEdgeMergeDecimationFilter();

  bool m_Relocate;
  bool m_CheckOrientation;

  PriorityQueuePointer    m_PriorityQueue;
  QueueMapType            m_QueueMapper;
  OutputQEType*           m_Element;
  PriorityType            m_Priority;
  OperatorPointer         m_JoinVertexFunction;

  virtual MeasureType MeasureEdge( OutputQEType* iEdge ) = 0;

  void FillPriorityQueue();

  void PushElement( OutputQEType* iEdge );

  bool IsEdgeOKToBeProcessed( OutputQEType* iEdge );

  void Extract();

  void DeleteElement( OutputQEType* iEdge );

  virtual void DeletePoint( const OutputPointIdentifier& iIdToBeDeleted,
                            const OutputPointIdentifier& iRemaing );

  virtual void PushOrUpdateElement( OutputQEType* iEdge );

  virtual void JoinVertexFailed( );

  virtual bool ProcessWithoutAnyTopologicalGuarantee();

  virtual unsigned int CheckQEProcessingStatus( );

  virtual bool ProcessWithTopologicalGuarantee();

  size_t NumberOfCommonVerticesIn0Ring( );

  void RemoveSamosa();

  void TagElementOut( OutputQEType* iEdge );

  void RemoveEye();

  virtual OutputPointType Relocate( OutputQEType* iEdge ) = 0;

  bool CheckOrientation( OutputQEType* iEdge,
    const OutputPointIdentifier& iId,
    const OutputPointType& iPt )
    {
    OutputMeshPointer output = this->GetOutput();
    OutputCellsContainerPointer cells = output->GetCells();

    std::list< OutputCellIdentifier > r1, r2, elements_to_be_tested;
    OutputQEType* qe = iEdge;
    OutputQEType* qe_it = qe->GetOnext();

    do
      {
      r1.push_back( qe_it->GetLeft() );
      qe_it = qe_it->GetOnext();
      }while( qe_it != qe );

    qe = iEdge->GetSym();
    qe_it = qe->GetOnext();

    do
      {
      r2.push_back( qe_it->GetLeft() );
      qe_it = qe_it->GetOnext();
      }while( qe_it != qe );

    r1.sort();
    r2.sort();

    std::set_symmetric_difference( r1.begin(), r1.end(),
      r2.begin(), r2.end(),
      std::back_inserter( elements_to_be_tested ) );

    typename std::list< OutputCellIdentifier >::iterator
      it = elements_to_be_tested.begin();

    typedef TriangleHelper< OutputPointType > TriangleType;

    bool orientation_ok( true );
    OutputCellIdentifier c_id( 0 );
    OutputPolygonType* poly;
    OutputPointIdentifier p_id;

    int k( 0 ), replace_k( 0 );
    OutputPointType pt[3];

    OutputVectorType n_bef, n_aft;

    while( ( it != elements_to_be_tested.end() ) && orientation_ok )
      {
      c_id = *it;
      poly = dynamic_cast< OutputPolygonType* >( cells->GetElement( c_id ) );

      qe = poly->GetEdgeRingEntry( );
      qe_it = qe;
      k = 0;
          
      do
        {
        p_id = qe_it->GetOrigin( );
        if( p_id == iId )
          replace_k = k;
        pt[k++] = output->GetPoint( p_id );
        qe_it = qe_it->GetLnext( );
        }while( qe_it != qe );

      n_bef = TriangleType::ComputeNormal( pt[0], pt[1], pt[2] );
      switch( replace_k )
        {
        default:
        case 0:
          n_aft = TriangleType::ComputeNormal( iPt, pt[1], pt[2] );
          break;
        case 1:
          n_aft = TriangleType::ComputeNormal( pt[0], iPt, pt[2] );
          break;
        case 2:
          n_aft = TriangleType::ComputeNormal( pt[0], pt[1], iPt );
          break;
        }

      orientation_ok = ( n_bef * n_aft ) < 0.;
      ++it;
      }

    return orientation_ok;
    }

  bool IsCriterionSatisfied();

private:
  QuadEdgeMeshEdgeMergeDecimationFilter( const Self& );
  void operator = ( const Self& );
};
}

#include "itkQuadEdgeMeshEdgeMergeDecimationFilter.txx"
#endif