itkEdgeDecimationQuadEdgeMeshFilter.h

Go to the documentation of this file.

/*=========================================================================
 *
 *  Copyright Insight Software Consortium
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *         http://www.apache.org/licenses/LICENSE-2.0.txt
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 *
 *=========================================================================*/
#ifndef itkEdgeDecimationQuadEdgeMeshFilter_h
#define itkEdgeDecimationQuadEdgeMeshFilter_h

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

#include "itkQuadEdgeMeshEulerOperatorJoinVertexFunction.h"
#include "itkQuadEdgeMeshPolygonCell.h"

#include "itkDecimationQuadEdgeMeshFilter.h"
#include "itkPriorityQueueContainer.h"
#include "itkTriangleHelper.h"

namespace itk
{
template< typename TInput, typename TOutput, typename TCriterion >
class ITK_TEMPLATE_EXPORT EdgeDecimationQuadEdgeMeshFilter:
  public DecimationQuadEdgeMeshFilter< TInput, TOutput, TCriterion >
{
public:
  using Self = EdgeDecimationQuadEdgeMeshFilter;
  using Pointer = SmartPointer< Self >;
  using ConstPointer = SmartPointer< const Self >;
  using Superclass = DecimationQuadEdgeMeshFilter<
    TInput, TOutput, TCriterion >;

  itkTypeMacro(EdgeDecimationQuadEdgeMeshFilter, DecimationQuadEdgeMeshFilter);

  using InputMeshType = TInput;
  using InputMeshPointer = typename InputMeshType::Pointer;

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

  using OutputPolygonType = QuadEdgeMeshPolygonCell< OutputCellType >;

  using CriterionType = TCriterion;
  using CriterionPointer = typename CriterionType::Pointer;
  using MeasureType = typename CriterionType::MeasureType;
  using PriorityType = typename CriterionType::PriorityType;
  using PriorityQueueItemType = typename CriterionType::PriorityQueueWrapperType;

  using PriorityQueueType = PriorityQueueContainer< PriorityQueueItemType *,
                                  ElementWrapperPointerInterface< PriorityQueueItemType * >,
                                  PriorityType >;
  using PriorityQueuePointer = typename PriorityQueueType::Pointer;

  using QueueMapType = std::map< OutputQEType *, PriorityQueueItemType * >;
  using QueueMapConstIterator = typename QueueMapType::const_iterator;
  using QueueMapIterator = typename QueueMapType::iterator;

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

protected:

  EdgeDecimationQuadEdgeMeshFilter();
  ~EdgeDecimationQuadEdgeMeshFilter() override;

  bool m_Relocate{true};
  bool m_CheckOrientation{false};

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

  virtual MeasureType MeasureEdge(OutputQEType *iEdge) = 0;

  void FillPriorityQueue() override;

  void PushElement(OutputQEType *iEdge);

  bool IsEdgeOKToBeProcessed(OutputQEType *iEdge);

  void Extract() override;

  void DeleteElement(OutputQEType *iEdge);

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

  virtual void PushOrUpdateElement(OutputQEType *iEdge);

  virtual void JoinVertexFailed();

  bool ProcessWithoutAnyTopologicalGuarantee() override;

  virtual unsigned int CheckQEProcessingStatus();

  bool ProcessWithTopologicalGuarantee() override;

  SizeValueType NumberOfCommonVerticesIn0Ring() const;

  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();

    using TriangleType = TriangleHelper< OutputPointType >;

    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() override;

private:
  EdgeDecimationQuadEdgeMeshFilter(const Self &) = delete;
  void operator=(const Self &) = delete;

};
}

#include "itkEdgeDecimationQuadEdgeMeshFilter.hxx"
#endif