itkEdgeDecimationQuadEdgeMeshFilter.h

Go to the documentation of this file.

/*=========================================================================
 *
 *  Copyright NumFOCUS
 *
 *  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
 *
 *         https://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:
  ITK_DISALLOW_COPY_AND_MOVE(EdgeDecimationQuadEdgeMeshFilter);
 
  using Self = EdgeDecimationQuadEdgeMeshFilter;
  using Pointer = SmartPointer<Self>;
  using ConstPointer = SmartPointer<const Self>;
  using Superclass = DecimationQuadEdgeMeshFilter<TInput, TOutput, TCriterion>;

  itkOverrideGetNameOfClassMacro(EdgeDecimationQuadEdgeMeshFilter);
 
  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 & iRemaining);

  virtual void
  PushOrUpdateElement(OutputQEType * iEdge);

  virtual void
  JoinVertexFailed();

  bool
  ProcessWithoutAnyTopologicalGuarantee() override;

  virtual unsigned int
  CheckQEProcessingStatus();

  bool
  ProcessWithTopologicalGuarantee() override;

  [[nodiscard]] 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();
    OutputQEType * qe = iEdge;
    OutputQEType * qe_it = qe->GetOnext();
 
    std::list<OutputCellIdentifier> r1;
    do
    {
      r1.push_back(qe_it->GetLeft());
      qe_it = qe_it->GetOnext();
    } while (qe_it != qe);
 
    qe = iEdge->GetSym();
    qe_it = qe->GetOnext();
 
    std::list<OutputCellIdentifier> r2;
    do
    {
      r2.push_back(qe_it->GetLeft());
      qe_it = qe_it->GetOnext();
    } while (qe_it != qe);
 
    r1.sort();
    r2.sort();
 
    std::list<OutputCellIdentifier> elements_to_be_tested;
    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);
    int             replace_k(0);
    OutputPointType pt[3];
 
    while ((it != elements_to_be_tested.end()) && orientation_ok)
    {
      OutputCellIdentifier c_id = *it;
      auto *               poly = dynamic_cast<OutputPolygonType *>(cells->GetElement(c_id));
 
      qe = poly->GetEdgeRingEntry();
      qe_it = qe;
      int k = 0;
 
      do
      {
        OutputPointIdentifier 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);
 
      OutputVectorType n_bef = TriangleType::ComputeNormal(pt[0], pt[1], pt[2]);
      OutputVectorType n_aft;
      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;
};
} // namespace itk
 
#include "itkEdgeDecimationQuadEdgeMeshFilter.hxx"
#endif