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