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 itkQuadEdgeMesh_h 19 #define itkQuadEdgeMesh_h 20 21 #include <cstdarg> 22 #include <queue> 23 #include <vector> 24 #include <list> 25 26 #include "itkMesh.h" 27 28 #include "itkQuadEdgeMeshTraits.h" 29 #include "itkQuadEdgeMeshLineCell.h" 30 #include "itkQuadEdgeMeshPolygonCell.h" 31 32 #include "itkQuadEdgeMeshFrontIterator.h" 33 #include "itkConceptChecking.h" 34 35 36 namespace itk 37 { 38 /** 39 * \class QuadEdgeMesh 40 * 41 * \brief Mesh class for 2D manifolds embedded in ND space. 42 * 43 * \author Alexandre Gouaillard, Leonardo Florez-Valencia, Eric Boix 44 * 45 * This implementation was contributed as a paper to the Insight Journal 46 * https://hdl.handle.net/1926/306 47 * 48 * \ingroup ITKQuadEdgeMesh 49 */ 50 template< typename TPixel, unsigned int VDimension, 51 typename TTraits = QuadEdgeMeshTraits< TPixel, VDimension, bool, bool > > 52 class ITK_TEMPLATE_EXPORT QuadEdgeMesh:public Mesh< TPixel, VDimension, TTraits > 53 { 54 public: 55 ITK_DISALLOW_COPY_AND_ASSIGN(QuadEdgeMesh); 56 57 /** Input template parameters. */ 58 using Traits = TTraits; 59 using PixelType = TPixel; 60 61 /** Standard type alias. */ 62 using Self = QuadEdgeMesh; 63 using Superclass = Mesh< TPixel, VDimension, Traits >; 64 using Pointer = SmartPointer< Self >; 65 using ConstPointer = SmartPointer< const Self >; 66 67 /** Convenient constants obtained from MeshTraits. */ 68 static constexpr unsigned int PointDimension = Traits::PointDimension; 69 static constexpr unsigned int MaxTopologicalDimension = Traits::MaxTopologicalDimension; 70 71 /** Types defined in superclass. */ 72 using CellPixelType = typename Superclass::CellPixelType; 73 using CoordRepType = typename Superclass::CoordRepType; 74 using PointIdentifier = typename Superclass::PointIdentifier; 75 using PointHashType = typename Superclass::PointHashType; 76 using PointType = typename Superclass::PointType; 77 using CellTraits = typename Superclass::CellTraits; 78 79 using PointIdInternalIterator = typename CellTraits::PointIdInternalIterator; 80 using PointIdIterator = typename CellTraits::PointIdIterator; 81 82 // Point section: 83 using PointsContainer = typename Superclass::PointsContainer; 84 using PointsContainerPointer = typename Superclass::PointsContainerPointer; 85 typedef CoordRepType CoordRepArrayType[Self::PointDimension]; 86 87 // Point data section: 88 using PointDataContainer = typename Superclass::PointDataContainer; 89 using PointDataContainerPointer = typename Superclass::PointDataContainerPointer; 90 using PointDataContainerIterator = typename Superclass::PointDataContainerIterator; 91 using PointsContainerConstIterator = typename Superclass::PointsContainerConstIterator; 92 using PointsContainerIterator = typename Superclass::PointsContainerIterator; 93 94 // Cell section: 95 using CellIdentifier = typename Superclass::CellIdentifier; 96 using CellType = typename Superclass::CellType; 97 using CellAutoPointer = typename Superclass::CellAutoPointer; 98 using CellFeatureIdentifier = typename Superclass::CellFeatureIdentifier; 99 using CellFeatureCount = typename Superclass::CellFeatureCount; 100 using CellMultiVisitorType = typename Superclass::CellMultiVisitorType; 101 using CellsContainer = typename Superclass::CellsContainer; 102 using CellsContainerPointer = typename Superclass::CellsContainerPointer; 103 104 using CellsContainerConstIterator = typename Superclass::CellsContainerConstIterator; 105 using CellsContainerIterator = typename Superclass::CellsContainerIterator; 106 107 using CellLinksContainer = typename Superclass::CellLinksContainer; 108 using CellLinksContainerPointer = typename Superclass::CellLinksContainerPointer; 109 using CellLinksContainerIterator = typename Superclass::CellLinksContainerIterator; 110 111 // Cell data section: 112 using CellDataContainer = typename Superclass::CellDataContainer; 113 using CellDataContainerPointer = typename Superclass::CellDataContainerPointer; 114 using CellDataContainerIterator = typename Superclass::CellDataContainerIterator; 115 116 // Point / Cell correspondance section: 117 using PointCellLinksContainer = typename Superclass::PointCellLinksContainer; 118 using PointCellLinksContainerIterator = typename Superclass::PointCellLinksContainerIterator; 119 120 // BoundaryAssignMents section: 121 using BoundaryAssignmentsContainer = typename Superclass::BoundaryAssignmentsContainer; 122 using BoundaryAssignmentsContainerPointer = typename Superclass::BoundaryAssignmentsContainerPointer; 123 using BoundaryAssignmentsContainerVector = typename Superclass::BoundaryAssignmentsContainerVector; 124 125 // Miscellaneous section: 126 using BoundingBoxPointer = typename Superclass::BoundingBoxPointer; 127 using BoundingBoxType = typename Superclass::BoundingBoxType; 128 using RegionType = typename Superclass::RegionType; 129 using InterpolationWeightType = typename Superclass::InterpolationWeightType; 130 131 /** Specific types for a quad-edge structure. */ 132 using PrimalDataType = typename Traits::PrimalDataType; 133 using DualDataType = typename Traits::DualDataType; 134 using QEPrimal = typename Traits::QEPrimal; 135 using QEDual = typename Traits::QEDual; 136 using QEType = typename Traits::QEPrimal; 137 // See the TODO entry dated from 2005-05-28 138 // struct QEType : public QEPrimal, public QEDual {} 139 using VertexRefType = typename Traits::VertexRefType; 140 using FaceRefType = typename Traits::FaceRefType; 141 using VectorType = typename Traits::VectorType; 142 143 /** Possible specialized cell types. */ 144 using EdgeCellType = QuadEdgeMeshLineCell< CellType >; 145 using PolygonCellType = QuadEdgeMeshPolygonCell< CellType >; 146 147 /** Free insertion indexes. */ 148 using FreePointIndexesType = std::queue< PointIdentifier >; 149 using FreeCellIndexesType = std::queue< CellIdentifier >; 150 151 /** Auxiliary types. */ 152 using PointIdList = std::vector< PointIdentifier >; 153 using EdgeListType = std::list< QEPrimal * >; 154 using EdgeListPointerType = EdgeListType *; 155 156 /** Reserved PointIdentifier designated to represent the absence of Point */ 157 static const PointIdentifier m_NoPoint; 158 159 /** Reserved CellIdentifier designated to represent the absence of Face */ 160 static const CellIdentifier m_NoFace; 161 162 public: 163 164 /** Basic Object interface. */ 165 itkNewMacro(Self); 166 itkTypeMacro(QuadEdgeMesh, Mesh); 167 168 #if !defined( ITK_WRAPPING_PARSER ) 169 /** FrontIterator definitions */ 170 itkQEDefineFrontIteratorMethodsMacro(Self); 171 #endif 172 173 public: 174 175 // Multithreading framework: not tested yet. RequestedRegionIsOutsideOfTheBufferedRegion()176 bool RequestedRegionIsOutsideOfTheBufferedRegion() override 177 { 178 return ( false ); 179 } 180 181 void Initialize() override; 182 183 /** another way of deleting all the cells */ 184 virtual void Clear(); 185 GetEdgeCells()186 CellsContainer * GetEdgeCells() { return m_EdgeCellsContainer; } GetEdgeCells()187 const CellsContainer * GetEdgeCells() const { return m_EdgeCellsContainer; } SetEdgeCells(CellsContainer * edgeCells)188 void SetEdgeCells(CellsContainer *edgeCells) 189 { m_EdgeCellsContainer = edgeCells; } SetEdgeCell(CellIdentifier cellId,CellAutoPointer & cellPointer)190 void SetEdgeCell(CellIdentifier cellId, CellAutoPointer & cellPointer) 191 { m_EdgeCellsContainer->InsertElement( cellId, cellPointer.ReleaseOwnership() ); } 192 193 /** Overloaded to avoid a bug in Mesh that prevents proper inheritance 194 * Refer to 195 * http://public.kitware.com/pipermail/insight-users/2005-March/012459.html 196 * and 197 * http://public.kitware.com/pipermail/insight-users/2005-April/012613.html 198 */ CopyInformation(const DataObject * data)199 void CopyInformation(const DataObject *data) override { (void)data; } 200 void Graft(const DataObject *data) override; 201 202 /** squeeze the point container to be able to write the file properly */ 203 void SqueezePointsIds(); 204 205 /** overloaded method for backward compatibility */ BuildCellLinks()206 void BuildCellLinks() {} 207 208 #if !defined( ITK_WRAPPING_PARSER ) 209 /** overloaded method for backward compatibility */ SetBoundaryAssignments(int dimension,BoundaryAssignmentsContainer * container)210 void SetBoundaryAssignments(int dimension, 211 BoundaryAssignmentsContainer *container) 212 { 213 (void)dimension; 214 (void)container; 215 } 216 217 /** overloaded method for backward compatibility */ GetBoundaryAssignments(int dimension)218 BoundaryAssignmentsContainerPointer GetBoundaryAssignments(int dimension) 219 { 220 (void)dimension; 221 return ( nullptr ); 222 } 223 224 /** overloaded method for backward compatibility */ GetBoundaryAssignments(int dimension)225 const BoundaryAssignmentsContainerPointer GetBoundaryAssignments( 226 int dimension) const 227 { 228 (void)dimension; 229 return ( nullptr ); 230 } 231 232 #endif 233 234 /** overloaded method for backward compatibility */ SetBoundaryAssignment(int dimension,CellIdentifier cellId,CellFeatureIdentifier featureId,CellIdentifier boundaryId)235 void SetBoundaryAssignment(int dimension, CellIdentifier cellId, 236 CellFeatureIdentifier featureId, 237 CellIdentifier boundaryId) 238 { 239 (void)dimension; 240 (void)cellId; 241 (void)featureId; 242 (void)boundaryId; 243 } 244 245 /** overloaded method for backward compatibility */ GetBoundaryAssignment(int dimension,CellIdentifier cellId,CellFeatureIdentifier featureId,CellIdentifier * boundaryId)246 bool GetBoundaryAssignment(int dimension, CellIdentifier cellId, 247 CellFeatureIdentifier featureId, 248 CellIdentifier *boundaryId) const 249 { 250 (void)dimension; 251 (void)cellId; 252 (void)featureId; 253 (void)boundaryId; 254 return ( false ); // ALEX: is it the good way? 255 } 256 257 /** overloaded method for backward compatibility */ RemoveBoundaryAssignment(int dimension,CellIdentifier cellId,CellFeatureIdentifier featureId)258 bool RemoveBoundaryAssignment(int dimension, CellIdentifier cellId, 259 CellFeatureIdentifier featureId) 260 { 261 (void)dimension; 262 (void)cellId; 263 (void)featureId; 264 return ( false ); // ALEX: is it the good way? 265 } 266 267 /** overloaded method for backward compatibility */ GetCellBoundaryFeature(int dimension,CellIdentifier cellId,CellFeatureIdentifier featureId,CellAutoPointer & cellAP)268 bool GetCellBoundaryFeature(int dimension, CellIdentifier cellId, 269 CellFeatureIdentifier featureId, 270 CellAutoPointer & cellAP) const 271 { 272 (void)dimension; 273 (void)cellId; 274 (void)featureId; 275 (void)cellAP; 276 return ( false ); 277 } 278 279 /** overloaded method for backward compatibility */ GetCellBoundaryFeatureNeighbors(int dimension,CellIdentifier cellId,CellFeatureIdentifier featureId,std::set<CellIdentifier> * cellSet)280 CellIdentifier GetCellBoundaryFeatureNeighbors(int dimension, 281 CellIdentifier cellId, 282 CellFeatureIdentifier featureId, 283 std::set< CellIdentifier > *cellSet) 284 { 285 (void)dimension; 286 (void)cellId; 287 (void)featureId; 288 (void)cellSet; 289 return NumericTraits<CellIdentifier>::ZeroValue(); 290 } 291 292 /** NOTE ALEX: this method do not use CellFeature and thus could be recoded */ GetCellNeighbors(CellIdentifier itkNotUsed (cellId),std::set<CellIdentifier> * itkNotUsed (cellSet))293 CellIdentifier GetCellNeighbors(CellIdentifier itkNotUsed(cellId), 294 std::set< CellIdentifier > * itkNotUsed(cellSet)) 295 { 296 return NumericTraits<CellIdentifier>::ZeroValue(); 297 } 298 299 /** overloaded method for backward compatibility */ GetAssignedCellBoundaryIfOneExists(int dimension,CellIdentifier cellId,CellFeatureIdentifier featureId,CellAutoPointer & cellAP)300 bool GetAssignedCellBoundaryIfOneExists(int dimension, 301 CellIdentifier cellId, 302 CellFeatureIdentifier featureId, 303 CellAutoPointer & cellAP) const 304 { 305 (void)dimension; 306 (void)cellId; 307 (void)featureId; 308 (void)cellAP; 309 return ( false ); // ALEX: is it the good way? 310 } 311 312 /** overloaded method for backward compatibility */ 313 void SetCell(CellIdentifier cId, CellAutoPointer & cell); 314 315 /** Methods to simplify point/edge insertion/search. */ 316 virtual PointIdentifier FindFirstUnusedPointIndex(); 317 318 virtual CellIdentifier FindFirstUnusedCellIndex(); 319 320 virtual void PushOnContainer(EdgeCellType *newEdge); 321 322 // Adding Point/Edge/Face methods 323 virtual PointIdentifier AddPoint(const PointType & p); 324 325 /** */ 326 virtual QEPrimal * AddEdge(const PointIdentifier & orgPid, 327 const PointIdentifier & destPid); 328 329 virtual QEPrimal * AddEdgeWithSecurePointList(const PointIdentifier & orgPid, 330 const PointIdentifier & destPid); 331 332 /** Add a polygonal face to the Mesh, suppose QE layer ready */ 333 virtual void AddFace(QEPrimal *e); 334 335 /** Add a polygonal face to the Mesh. The list of points 336 * is expected to be ordered counter-clock wise. The inside 337 * of the new face will be on the left side of the edges 338 * formed by consecutive points in this list. */ 339 virtual QEPrimal * AddFace(const PointIdList & points); 340 341 virtual QEPrimal * AddFaceWithSecurePointList(const PointIdList & points); 342 343 virtual QEPrimal * AddFaceWithSecurePointList(const PointIdList & points, 344 bool CheckEdges); 345 346 /** Adds a triangular face to the Mesh */ 347 virtual QEPrimal * AddFaceTriangle(const PointIdentifier & aPid, 348 const PointIdentifier & bPid, 349 const PointIdentifier & cPid); 350 351 /** Deletion methods */ 352 virtual void DeletePoint(const PointIdentifier & pid); 353 354 virtual void DeleteEdge(const PointIdentifier & orgPid, 355 const PointIdentifier & destPid); 356 357 virtual void DeleteEdge(QEPrimal *e); 358 359 virtual void LightWeightDeleteEdge(EdgeCellType *e); 360 361 virtual void LightWeightDeleteEdge(QEPrimal *e); 362 363 virtual void DeleteFace(FaceRefType faceToDelete); 364 365 // GetPoint(PointIdentifier pid,PointType * pt)366 bool GetPoint(PointIdentifier pid, PointType *pt) const 367 { 368 return ( Superclass::GetPoint(pid, pt) ); 369 } 370 371 virtual PointType GetPoint(const PointIdentifier & pid) const; 372 373 virtual VectorType GetVector(const PointIdentifier & pid) const; 374 375 virtual QEPrimal * GetEdge() const; 376 377 virtual QEPrimal * GetEdge(const CellIdentifier & eid) const; 378 379 virtual QEPrimal * FindEdge(const PointIdentifier & pid0) const; 380 381 virtual QEPrimal * FindEdge(const PointIdentifier & pid0, 382 const PointIdentifier & pid1) const; 383 384 virtual EdgeCellType * FindEdgeCell(const PointIdentifier & pid0, 385 const PointIdentifier & pid1) const; 386 387 /// Compute the euclidian length of argument edge 388 CoordRepType ComputeEdgeLength(QEPrimal *e); 389 390 PointIdentifier ComputeNumberOfPoints() const; 391 392 CellIdentifier ComputeNumberOfFaces() const; 393 394 CellIdentifier ComputeNumberOfEdges() const; 395 396 PointIdentifier Splice(QEPrimal *a, QEPrimal *b); 397 398 #ifdef ITK_USE_CONCEPT_CHECKING 399 // Begin concept checking 400 // End concept checking 401 #endif 402 403 // for reusability of a mesh in the MeshToMesh filter ClearFreePointAndCellIndexesLists()404 void ClearFreePointAndCellIndexesLists() 405 { 406 while ( !this->m_FreePointIndexes.empty() ) 407 { 408 this->m_FreePointIndexes.pop(); 409 } 410 while ( !this->m_FreeCellIndexes.empty() ) 411 { 412 this->m_FreeCellIndexes.pop(); 413 } 414 } 415 GetNumberOfFaces()416 CellIdentifier GetNumberOfFaces() const { return ( m_NumberOfFaces ); } GetNumberOfEdges()417 CellIdentifier GetNumberOfEdges() const { return ( m_NumberOfEdges ); } 418 419 protected: 420 /** Constructor and Destructor. */ 421 QuadEdgeMesh(); 422 ~QuadEdgeMesh() override; 423 424 /** Release the memory of each one of the cells independently. */ 425 virtual void ClearCellsContainer(); 426 427 CellsContainerPointer m_EdgeCellsContainer; 428 429 private: 430 CellIdentifier m_NumberOfFaces; 431 CellIdentifier m_NumberOfEdges; 432 433 protected: 434 FreePointIndexesType m_FreePointIndexes; 435 FreeCellIndexesType m_FreeCellIndexes; 436 }; 437 } 438 439 #ifndef ITK_MANUAL_INSTANTIATION 440 #include "itkQuadEdgeMesh.hxx" 441 #endif 442 443 #endif 444