1 /*=========================================================================
2  *
3  *  Copyright Insight Software Consortium
4  *
5  *  Licensed under the Apache License, Version 2.0 (the "License");
6  *  you may not use this file except in compliance with the License.
7  *  You may obtain a copy of the License at
8  *
9  *         http://www.apache.org/licenses/LICENSE-2.0.txt
10  *
11  *  Unless required by applicable law or agreed to in writing, software
12  *  distributed under the License is distributed on an "AS IS" BASIS,
13  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  *  See the License for the specific language governing permissions and
15  *  limitations under the License.
16  *
17  *=========================================================================*/
18 #ifndef itkEdgeDecimationQuadEdgeMeshFilter_h
19 #define itkEdgeDecimationQuadEdgeMeshFilter_h
20 
21 #include <list>
22 #include <map>
23 #include <algorithm>
24 
25 #include "itkQuadEdgeMeshEulerOperatorJoinVertexFunction.h"
26 #include "itkQuadEdgeMeshPolygonCell.h"
27 
28 #include "itkDecimationQuadEdgeMeshFilter.h"
29 #include "itkPriorityQueueContainer.h"
30 #include "itkTriangleHelper.h"
31 
32 namespace itk
33 {
34 /**
35  * \class EdgeDecimationQuadEdgeMeshFilter
36  * \brief
37  * \ingroup ITKQuadEdgeMeshFiltering
38  */
39 template< typename TInput, typename TOutput, typename TCriterion >
40 class ITK_TEMPLATE_EXPORT EdgeDecimationQuadEdgeMeshFilter:
41   public DecimationQuadEdgeMeshFilter< TInput, TOutput, TCriterion >
42 {
43 public:
44   using Self = EdgeDecimationQuadEdgeMeshFilter;
45   using Pointer = SmartPointer< Self >;
46   using ConstPointer = SmartPointer< const Self >;
47   using Superclass = DecimationQuadEdgeMeshFilter<
48     TInput, TOutput, TCriterion >;
49 
50   /** Run-time type information (and related methods).   */
51   itkTypeMacro(EdgeDecimationQuadEdgeMeshFilter, DecimationQuadEdgeMeshFilter);
52 
53   using InputMeshType = TInput;
54   using InputMeshPointer = typename InputMeshType::Pointer;
55 
56   using OutputMeshType = TOutput;
57   using OutputMeshPointer = typename OutputMeshType::Pointer;
58   using OutputPointIdentifier = typename OutputMeshType::PointIdentifier;
59   using OutputPointType = typename OutputMeshType::PointType;
60   using OutputVectorType = typename OutputPointType::VectorType;
61   using OutputQEType = typename OutputMeshType::QEType;
62   using OutputEdgeCellType = typename OutputMeshType::EdgeCellType;
63   using OutputCellType = typename OutputMeshType::CellType;
64   using OutputCellIdentifier = typename OutputMeshType::CellIdentifier;
65   using OutputCellsContainerPointer = typename OutputMeshType::CellsContainerPointer;
66   using OutputCellsContainerIterator = typename OutputMeshType::CellsContainerIterator;
67 
68   using OutputPolygonType = QuadEdgeMeshPolygonCell< OutputCellType >;
69 
70   using CriterionType = TCriterion;
71   using CriterionPointer = typename CriterionType::Pointer;
72   using MeasureType = typename CriterionType::MeasureType;
73   using PriorityType = typename CriterionType::PriorityType;
74   using PriorityQueueItemType = typename CriterionType::PriorityQueueWrapperType;
75 
76   using PriorityQueueType = PriorityQueueContainer< PriorityQueueItemType *,
77                                   ElementWrapperPointerInterface< PriorityQueueItemType * >,
78                                   PriorityType >;
79   using PriorityQueuePointer = typename PriorityQueueType::Pointer;
80 
81   using QueueMapType = std::map< OutputQEType *, PriorityQueueItemType * >;
82   using QueueMapConstIterator = typename QueueMapType::const_iterator;
83   using QueueMapIterator = typename QueueMapType::iterator;
84 
85   using OperatorType = QuadEdgeMeshEulerOperatorJoinVertexFunction< OutputMeshType, OutputQEType >;
86   using OperatorPointer = typename OperatorType::Pointer;
87 
88 protected:
89 
90   EdgeDecimationQuadEdgeMeshFilter();
91   ~EdgeDecimationQuadEdgeMeshFilter() override;
92 
93   bool m_Relocate{true};
94   bool m_CheckOrientation{false};
95 
96   PriorityQueuePointer m_PriorityQueue;
97   QueueMapType         m_QueueMapper;
98   OutputQEType *       m_Element;
99   PriorityType         m_Priority;
100   OperatorPointer      m_JoinVertexFunction;
101 
102   /**
103   * \brief Compute the measure value for iEdge
104   * \param[in] iEdge
105   * \return measure value
106   */
107   virtual MeasureType MeasureEdge(OutputQEType *iEdge) = 0;
108 
109   /**
110   * \brief Fill the priority queue
111   */
112   void FillPriorityQueue() override;
113 
114   /**
115   * \brief Push one edge in the priority queue
116   * \param[in] iEdge
117   */
118   void PushElement(OutputQEType *iEdge);
119 
120   /**
121   * \brief Check if iEdge is valid and then can be processed
122   * \param[in] iEdge
123   * \return
124   */
125   bool IsEdgeOKToBeProcessed(OutputQEType *iEdge);
126 
127   /**
128   * \brief Extract the edge to be processed
129   */
130   void Extract() override;
131 
132   /**
133   * \brief Delete a given edge in the priority queue
134   * \param[in] iEdge
135   */
136   void DeleteElement(OutputQEType *iEdge);
137 
138   virtual void DeletePoint(const OutputPointIdentifier & iIdToBeDeleted,
139                            const OutputPointIdentifier & iRemaing);
140 
141   /**
142   * \brief Push iEdge in the priority queue if it is not already, else
143   * its corresponding priority value is updated.
144   * \param[in] iEdge
145   */
146   virtual void PushOrUpdateElement(OutputQEType *iEdge);
147 
148   /**
149   * \brief
150   */
151   virtual void JoinVertexFailed();
152 
153   /**
154   * \brief
155   */
156   bool ProcessWithoutAnyTopologicalGuarantee() override;
157 
158   /**
159   * \brief
160   * \return
161   */
162   virtual unsigned int CheckQEProcessingStatus();
163 
164   /**
165   * \brief
166   * \return
167   */
168   bool ProcessWithTopologicalGuarantee() override;
169 
170   /**
171   * \brief
172   */
173   SizeValueType NumberOfCommonVerticesIn0Ring() const;
174 
175   /**
176   * \brief
177   */
178   void RemoveSamosa();
179 
180   /**
181   * \brief
182   * \param[in] iEdge
183   */
184   void TagElementOut(OutputQEType *iEdge);
185 
186   /**
187   * \brief
188   */
189   void RemoveEye();
190 
191   /**
192   * \brief
193   * \param[in] iEdge (the one which will be merged)
194   * \return the new location of merged points
195   */
196   virtual OutputPointType Relocate(OutputQEType *iEdge) = 0;
197 
198   /**
199   * \brief
200   * \todo Finish to implement this method!
201   */
CheckOrientation(OutputQEType * iEdge,const OutputPointIdentifier & iId,const OutputPointType & iPt)202   bool CheckOrientation(OutputQEType *iEdge,
203                         const OutputPointIdentifier & iId,
204                         const OutputPointType & iPt)
205   {
206     OutputMeshPointer           output = this->GetOutput();
207     OutputCellsContainerPointer cells = output->GetCells();
208 
209     std::list< OutputCellIdentifier > r1, r2, elements_to_be_tested;
210     OutputQEType *                    qe = iEdge;
211     OutputQEType *                    qe_it = qe->GetOnext();
212 
213     do
214       {
215       r1.push_back( qe_it->GetLeft() );
216       qe_it = qe_it->GetOnext();
217       }
218     while ( qe_it != qe );
219 
220     qe = iEdge->GetSym();
221     qe_it = qe->GetOnext();
222 
223     do
224       {
225       r2.push_back( qe_it->GetLeft() );
226       qe_it = qe_it->GetOnext();
227       }
228     while ( qe_it != qe );
229 
230     r1.sort();
231     r2.sort();
232 
233     std::set_symmetric_difference( r1.begin(), r1.end(),
234                                    r2.begin(), r2.end(),
235                                    std::back_inserter(elements_to_be_tested) );
236 
237     typename std::list< OutputCellIdentifier >::iterator
238     it = elements_to_be_tested.begin();
239 
240     using TriangleType = TriangleHelper< OutputPointType >;
241 
242     bool                  orientation_ok(true);
243     OutputCellIdentifier  c_id(0);
244     OutputPolygonType *   poly;
245     OutputPointIdentifier p_id;
246 
247     int             k(0), replace_k(0);
248     OutputPointType pt[3];
249 
250     OutputVectorType n_bef, n_aft;
251 
252     while ( ( it != elements_to_be_tested.end() ) && orientation_ok )
253       {
254       c_id = *it;
255       poly = dynamic_cast< OutputPolygonType * >( cells->GetElement(c_id) );
256 
257       qe = poly->GetEdgeRingEntry();
258       qe_it = qe;
259       k = 0;
260 
261       do
262         {
263         p_id = qe_it->GetOrigin();
264         if ( p_id == iId )
265           {
266           replace_k = k;
267           }
268         pt[k++] = output->GetPoint(p_id);
269         qe_it = qe_it->GetLnext();
270         }
271       while ( qe_it != qe );
272 
273       n_bef = TriangleType::ComputeNormal(pt[0], pt[1], pt[2]);
274       switch ( replace_k )
275         {
276         default:
277         case 0:
278           n_aft = TriangleType::ComputeNormal(iPt, pt[1], pt[2]);
279           break;
280         case 1:
281           n_aft = TriangleType::ComputeNormal(pt[0], iPt, pt[2]);
282           break;
283         case 2:
284           n_aft = TriangleType::ComputeNormal(pt[0], pt[1], iPt);
285           break;
286         }
287 
288       orientation_ok = ( n_bef * n_aft ) < 0.;
289       ++it;
290       }
291 
292     return orientation_ok;
293   }
294 
295   /**
296    * \brief
297    * \return
298    */
299   bool IsCriterionSatisfied() override;
300 
301 private:
302   EdgeDecimationQuadEdgeMeshFilter(const Self &) = delete;
303   void operator=(const Self &) = delete;
304 
305 };
306 }
307 
308 #include "itkEdgeDecimationQuadEdgeMeshFilter.hxx"
309 #endif
310