ITK
4.1.0
Insight Segmentation and Registration Toolkit
|
00001 /*========================================================================= 00002 * 00003 * Copyright Insight Software Consortium 00004 * 00005 * Licensed under the Apache License, Version 2.0 (the "License"); 00006 * you may not use this file except in compliance with the License. 00007 * You may obtain a copy of the License at 00008 * 00009 * http://www.apache.org/licenses/LICENSE-2.0.txt 00010 * 00011 * Unless required by applicable law or agreed to in writing, software 00012 * distributed under the License is distributed on an "AS IS" BASIS, 00013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00014 * See the License for the specific language governing permissions and 00015 * limitations under the License. 00016 * 00017 *=========================================================================*/ 00018 #ifndef __itkQuadEdgeMesh_h 00019 #define __itkQuadEdgeMesh_h 00020 00021 #include "vcl_cstdarg.h" 00022 #include <queue> 00023 #include <vector> 00024 #include <list> 00025 00026 #include "itkMesh.h" 00027 00028 #include "itkQuadEdgeMeshTraits.h" 00029 #include "itkQuadEdgeMeshLineCell.h" 00030 #include "itkQuadEdgeMeshPolygonCell.h" 00031 00032 #include "itkQuadEdgeMeshFrontIterator.h" 00033 #include "itkConceptChecking.h" 00034 00035 /**** 00036 * \brief Documentation of itkQE namespace 00037 * \todo More comments here ! 00038 * 00039 * \note Design notes: some QuadEdgeMesh algorithms are based on iterating 00040 * various connectivity operators e.g. curvature driven surface deformation. 00041 * Many of those connectivity altering operators (e.g. the Euler operators) 00042 * are lightweight in the sense that they only modify very limited regions 00043 * of a QuadEdgeMesh: they typically act within the range of couple edges of 00044 * distance from a considered vertex, edge or face. 00045 * On the one side, we cannot choose to implement those atomic operations 00046 * as "classical" itk filters since each filter invocation yields a new 00047 * copy of the input mesh as its output: this would drasticaly 00048 * increase the memory consumption. 00049 * In fact, those atomic operations have a too much finer grain to be 00050 * implemeted as filters: the filter is more at the scale of the 00051 * application of a large number of such atomic operations. 00052 * One the other hand, we cannot choose to implement those atomic operations 00053 * as methods of this QuadEdgeMesh class (or a derived one) at the risk of 00054 * rapid code bloat. 00055 * Maybe we could choose to make thematic regroupment within derived 00056 * classes, but this would force an end user to multiple inheritance which 00057 * can prove to be a drag in a templated context. 00058 * Eventually, we chose to implement them as function object: the 00059 * loosely coupling of those operation methods with the targeted QuadEdgeMesh 00060 * object and heavier invocation syntax are a small price to pay in 00061 * exchange for optimal memory usage and end user modularity. 00062 * But we couldn't inherit from \ref FunctionBase since its 00063 * Evaluate( const InputType& input ) method promises to leave its 00064 * argument (the mesh we want to modify in our case) untouched. 00065 * Hence we created the \ref itkQE::MeshFunctionBase class whose main 00066 * difference with \ref FunctionBase is that its Evaluate() 00067 * method allows to modify the considered mesh. 00068 * When considering a new QuadEdgeMesh method we are left with four possible 00069 * "slots" to implement it: 00070 * - the QuadEdgeMesh method 00071 * - a derived class from FunctionBase when the method leaves 00072 * the mesh constant. 00073 * - a derived class from \ref itkQE::MeshFunctionBase when the 00074 * method modifies the mesh (typically in the case of Euler operators) 00075 * - as a classic Mesh filter. 00076 * The choice of the slot is a mere matter of trade-off and in order 00077 * to keep QuadEdgeMesh tiny and humanly readable key decision factors 00078 * can be the occurence of the calls and the human level complexity of 00079 * the code. 00080 * With those criteria in mind we made the following choices: 00081 * - really atomic, lightweight and general purpose methods like 00082 * \ref Mesh::ComputeNumberOfPoints are left within the Mesh class. 00083 * - heavier methods and less often called like 00084 * \ref SanityCheckMeshFunction were implemented as derived classes of 00085 * \ref FunctionBase. 00086 * - methods with the same weight (measured e.g. in number of lines of 00087 * code) but that modify the considered mesh, like 00088 * \ref BoundaryEdgesMeshFunction or 00089 * \ref ZipMeshFunction, were implemented as derived classes of 00090 * \ref itkQE::MeshFunctionBase. Still the mesh modifications are 00091 * really limited and concern a couple edges. 00092 * - more specialised methods, with a wider scope and that require a 00093 * copy of the mesh should follow the classical itk Filter pattern, 00094 * like \ref itkQE::MeshExtractComponentFilter, and inherit from 00095 * \ref MeshToMeshFilter. 00096 */ 00097 namespace itk 00098 { 00099 00112 template< typename TPixel, unsigned int VDimension, 00113 typename TTraits = QuadEdgeMeshTraits< TPixel, VDimension, bool, bool > > 00114 class ITK_EXPORT QuadEdgeMesh:public Mesh< TPixel, VDimension, TTraits > 00115 { 00116 public: 00117 00119 typedef TTraits Traits; 00120 typedef TPixel PixelType; 00121 00123 typedef QuadEdgeMesh Self; 00124 typedef Mesh< TPixel, VDimension, Traits > Superclass; 00125 typedef SmartPointer< Self > Pointer; 00126 typedef SmartPointer< const Self > ConstPointer; 00127 00129 itkStaticConstMacro(PointDimension, unsigned int, 00130 Traits::PointDimension); 00131 itkStaticConstMacro(MaxTopologicalDimension, unsigned int, 00132 Traits::MaxTopologicalDimension); 00134 00136 typedef typename Superclass::CellPixelType CellPixelType; 00137 typedef typename Superclass::CoordRepType CoordRepType; 00138 typedef typename Superclass::PointIdentifier PointIdentifier; 00139 typedef typename Superclass::PointHashType PointHashType; 00140 typedef typename Superclass::PointType PointType; 00141 typedef typename Superclass::CellTraits CellTraits; 00142 00143 typedef typename CellTraits::PointIdInternalIterator PointIdInternalIterator; 00144 typedef typename CellTraits::PointIdIterator PointIdIterator; 00145 00146 // Point section: 00147 typedef typename Superclass::PointsContainer PointsContainer; 00148 typedef typename Superclass::PointsContainerPointer PointsContainerPointer; 00149 typedef CoordRepType CoordRepArrayType[ 00150 itkGetStaticConstMacro(PointDimension)]; 00151 00152 // Point data section: 00153 typedef typename Superclass::PointDataContainer PointDataContainer; 00154 typedef typename Superclass::PointDataContainerPointer 00155 PointDataContainerPointer; 00156 typedef typename Superclass::PointDataContainerIterator 00157 PointDataContainerIterator; 00158 typedef typename Superclass::PointsContainerConstIterator 00159 PointsContainerConstIterator; 00160 typedef typename Superclass::PointsContainerIterator 00161 PointsContainerIterator; 00162 00163 // Cell section: 00164 typedef typename Superclass::CellIdentifier CellIdentifier; 00165 typedef typename Superclass::CellType CellType; 00166 typedef typename Superclass::CellAutoPointer CellAutoPointer; 00167 typedef typename Superclass::CellFeatureIdentifier CellFeatureIdentifier; 00168 typedef typename Superclass::CellFeatureCount CellFeatureCount; 00169 typedef typename Superclass::CellMultiVisitorType CellMultiVisitorType; 00170 typedef typename Superclass::CellsContainer CellsContainer; 00171 typedef typename Superclass::CellsContainerPointer CellsContainerPointer; 00172 00173 typedef typename Superclass::CellsContainerConstIterator 00174 CellsContainerConstIterator; 00175 typedef typename Superclass::CellsContainerIterator 00176 CellsContainerIterator; 00177 00178 typedef typename Superclass::CellLinksContainer CellLinksContainer; 00179 typedef typename Superclass::CellLinksContainerPointer 00180 CellLinksContainerPointer; 00181 typedef typename Superclass::CellLinksContainerIterator 00182 CellLinksContainerIterator; 00183 00184 // Cell data section: 00185 typedef typename Superclass::CellDataContainer CellDataContainer; 00186 typedef typename Superclass::CellDataContainerPointer 00187 CellDataContainerPointer; 00188 typedef typename Superclass::CellDataContainerIterator 00189 CellDataContainerIterator; 00190 00191 // Point / Cell correspondance section: 00192 typedef typename Superclass::PointCellLinksContainer 00193 PointCellLinksContainer; 00194 typedef typename Superclass::PointCellLinksContainerIterator 00195 PointCellLinksContainerIterator; 00196 00197 // BoundaryAssignMents section: 00198 typedef typename Superclass::BoundaryAssignmentsContainer 00199 BoundaryAssignmentsContainer; 00200 typedef typename Superclass::BoundaryAssignmentsContainerPointer 00201 BoundaryAssignmentsContainerPointer; 00202 typedef typename Superclass::BoundaryAssignmentsContainerVector 00203 BoundaryAssignmentsContainerVector; 00204 00205 // Miscelaneous section: 00206 typedef typename Superclass::BoundingBoxPointer BoundingBoxPointer; 00207 typedef typename Superclass::BoundingBoxType BoundingBoxType; 00208 typedef typename Superclass::RegionType RegionType; 00209 typedef typename Superclass::InterpolationWeightType 00210 InterpolationWeightType; 00211 00213 typedef typename Traits::PrimalDataType PrimalDataType; 00214 typedef typename Traits::DualDataType DualDataType; 00215 typedef typename Traits::QEPrimal QEPrimal; 00216 typedef typename Traits::QEDual QEDual; 00217 typedef typename Traits::QEPrimal QEType; 00218 // See the TODO entry dated from 2005-05-28 00219 // struct QEType : public QEPrimal, public QEDual {} 00220 typedef typename Traits::VertexRefType VertexRefType; 00221 typedef typename Traits::FaceRefType FaceRefType; 00222 typedef typename Traits::VectorType VectorType; 00223 00225 typedef QuadEdgeMeshLineCell< CellType > EdgeCellType; 00226 typedef QuadEdgeMeshPolygonCell< CellType > PolygonCellType; 00227 00229 typedef std::queue< PointIdentifier > FreePointIndexesType; 00230 typedef std::queue< CellIdentifier > FreeCellIndexesType; 00231 00233 typedef std::vector< PointIdentifier > PointIdList; 00234 typedef std::list< QEPrimal * > EdgeListType; 00235 typedef EdgeListType * EdgeListPointerType; 00236 00238 static const PointIdentifier m_NoPoint; 00239 00241 static const CellIdentifier m_NoFace; 00242 public: 00243 00245 itkNewMacro(Self); 00246 itkTypeMacro(QuadEdgeMesh, Mesh); 00248 00249 #if !defined( CABLE_CONFIGURATION ) 00250 00251 itkQEDefineFrontIteratorMethodsMacro(Self); 00252 #endif 00253 public: 00254 00255 // Multithreading framework: not tested yet. 00256 virtual bool RequestedRegionIsOutsideOfTheBufferedRegion() 00257 { 00258 return ( false ); 00259 } 00260 00261 virtual void Initialize(); 00262 00264 virtual void Clear(); 00265 00266 CellsContainer * GetEdgeCells() { return m_EdgeCellsContainer; } 00267 const CellsContainer * GetEdgeCells() const { return m_EdgeCellsContainer; } 00268 void SetEdgeCells(CellsContainer *edgeCells) 00269 { m_EdgeCellsContainer = edgeCells; } 00270 void SetEdgeCell(CellIdentifier cellId, CellAutoPointer & cellPointer) 00271 { m_EdgeCellsContainer->InsertElement( cellId, cellPointer.ReleaseOwnership() ); } 00272 00279 virtual void CopyInformation(const DataObject *data) { (void)data; } 00280 virtual void Graft(const DataObject *data); 00282 00284 void SqueezePointsIds(); 00285 00287 void BuildCellLinks() {} 00288 00289 #if !defined( CABLE_CONFIGURATION ) 00290 00291 void SetBoundaryAssignments(int dimension, 00292 BoundaryAssignmentsContainer *container) 00293 { 00294 (void)dimension; 00295 (void)container; 00296 } 00298 00300 BoundaryAssignmentsContainerPointer GetBoundaryAssignments(int dimension) 00301 { 00302 (void)dimension; 00303 return ( (BoundaryAssignmentsContainerPointer)0 ); 00304 } 00306 00308 const BoundaryAssignmentsContainerPointer GetBoundaryAssignments( 00309 int dimension) const 00310 { 00311 (void)dimension; 00312 return ( (BoundaryAssignmentsContainerPointer)0 ); 00313 } 00315 00316 #endif 00317 00319 void SetBoundaryAssignment(int dimension, CellIdentifier cellId, 00320 CellFeatureIdentifier featureId, 00321 CellIdentifier boundaryId) 00322 { 00323 (void)dimension; 00324 (void)cellId; 00325 (void)featureId; 00326 (void)boundaryId; 00327 } 00329 00331 bool GetBoundaryAssignment(int dimension, CellIdentifier cellId, 00332 CellFeatureIdentifier featureId, 00333 CellIdentifier *boundaryId) const 00334 { 00335 (void)dimension; 00336 (void)cellId; 00337 (void)featureId; 00338 (void)boundaryId; 00339 return ( false ); // ALEX: is it the good way? 00340 } 00342 00344 bool RemoveBoundaryAssignment(int dimension, CellIdentifier cellId, 00345 CellFeatureIdentifier featureId) 00346 { 00347 (void)dimension; 00348 (void)cellId; 00349 (void)featureId; 00350 return ( false ); // ALEX: is it the good way? 00351 } 00353 00355 bool GetCellBoundaryFeature(int dimension, CellIdentifier cellId, 00356 CellFeatureIdentifier featureId, 00357 CellAutoPointer & cellAP) const 00358 { 00359 (void)dimension; 00360 (void)cellId; 00361 (void)featureId; 00362 (void)cellAP; 00363 return ( false ); 00364 } 00366 00368 CellIdentifier GetCellBoundaryFeatureNeighbors(int dimension, 00369 CellIdentifier cellId, 00370 CellFeatureIdentifier featureId, 00371 std::set< CellIdentifier > *cellSet) 00372 { 00373 (void)dimension; 00374 (void)cellId; 00375 (void)featureId; 00376 (void)cellSet; 00377 return NumericTraits<CellIdentifier>::Zero; 00378 } 00380 00382 CellIdentifier GetCellNeighbors(CellIdentifier itkNotUsed(cellId), 00383 std::set< CellIdentifier > * itkNotUsed(cellSet)) 00384 { 00385 return NumericTraits<CellIdentifier>::Zero; 00386 } 00387 00389 bool GetAssignedCellBoundaryIfOneExists(int dimension, 00390 CellIdentifier cellId, 00391 CellFeatureIdentifier featureId, 00392 CellAutoPointer & cellAP) const 00393 { 00394 (void)dimension; 00395 (void)cellId; 00396 (void)featureId; 00397 (void)cellAP; 00398 return ( false ); // ALEX: is it the good way? 00399 } 00401 00403 void SetCell(CellIdentifier cId, CellAutoPointer & cell); 00404 00406 virtual PointIdentifier FindFirstUnusedPointIndex(); 00407 00408 virtual CellIdentifier FindFirstUnusedCellIndex(); 00409 00410 virtual void PushOnContainer(EdgeCellType *newEdge); 00411 00412 // Adding Point/Edge/Face methods 00413 virtual PointIdentifier AddPoint(const PointType & p); 00414 00416 virtual QEPrimal * AddEdge(const PointIdentifier & orgPid, 00417 const PointIdentifier & destPid); 00418 00419 virtual QEPrimal * AddEdgeWithSecurePointList(const PointIdentifier & orgPid, 00420 const PointIdentifier & destPid); 00421 00423 virtual void AddFace(QEPrimal *e); 00424 00429 virtual QEPrimal * AddFace(const PointIdList & points); 00430 00431 virtual QEPrimal * AddFaceWithSecurePointList(const PointIdList & points); 00432 00433 virtual QEPrimal * AddFaceWithSecurePointList(const PointIdList & points, 00434 bool CheckEdges); 00435 00437 virtual QEPrimal * AddFaceTriangle(const PointIdentifier & aPid, 00438 const PointIdentifier & bPid, 00439 const PointIdentifier & cPid); 00440 00442 virtual void DeletePoint(const PointIdentifier & pid); 00443 00444 virtual void DeleteEdge(const PointIdentifier & orgPid, 00445 const PointIdentifier & destPid); 00446 00447 virtual void DeleteEdge(QEPrimal *e); 00448 00449 virtual void LightWeightDeleteEdge(EdgeCellType *e); 00450 00451 virtual void LightWeightDeleteEdge(QEPrimal *e); 00452 00453 virtual void DeleteFace(FaceRefType faceToDelete); 00454 00455 // 00456 bool GetPoint(PointIdentifier pid, PointType *pt) const 00457 { 00458 return ( Superclass::GetPoint(pid, pt) ); 00459 } 00460 00461 virtual PointType GetPoint(const PointIdentifier & pid) const; 00462 00463 virtual VectorType GetVector(const PointIdentifier & pid) const; 00464 00465 virtual QEPrimal * GetEdge() const; 00466 00467 virtual QEPrimal * GetEdge(const CellIdentifier & eid) const; 00468 00469 virtual QEPrimal * FindEdge(const PointIdentifier & pid0) const; 00470 00471 virtual QEPrimal * FindEdge(const PointIdentifier & pid0, 00472 const PointIdentifier & pid1) const; 00473 00474 virtual EdgeCellType * FindEdgeCell(const PointIdentifier & pid0, 00475 const PointIdentifier & pid1) const; 00476 00478 CoordRepType ComputeEdgeLength(QEPrimal *e); 00479 00480 PointIdentifier ComputeNumberOfPoints() const; 00481 00482 CellIdentifier ComputeNumberOfFaces() const; 00483 00484 CellIdentifier ComputeNumberOfEdges() const; 00485 00486 PointIdentifier Splice(QEPrimal *a, QEPrimal *b); 00487 00488 #ifdef ITK_USE_CONCEPT_CHECKING 00489 00492 #endif 00493 00494 // for reusability of a mesh in the MeshToMesh filter 00495 void ClearFreePointAndCellIndexesLists() 00496 { 00497 while ( !this->m_FreePointIndexes.empty() ) 00498 { 00499 this->m_FreePointIndexes.pop(); 00500 } 00501 while ( !this->m_FreeCellIndexes.empty() ) 00502 { 00503 this->m_FreeCellIndexes.pop(); 00504 } 00505 } 00506 00507 CellIdentifier GetNumberOfFaces() const { return ( m_NumberOfFaces ); } 00508 CellIdentifier GetNumberOfEdges() const { return ( m_NumberOfEdges ); } 00509 protected: 00511 QuadEdgeMesh(); 00512 virtual ~QuadEdgeMesh(); 00514 00516 virtual void ClearCellsContainer(); 00517 00518 CellsContainerPointer m_EdgeCellsContainer; 00519 private: 00520 QuadEdgeMesh(const Self &); //purposely not implemented 00521 void operator=(const Self &); //purposely not implemented 00522 00523 CellIdentifier m_NumberOfFaces; 00524 CellIdentifier m_NumberOfEdges; 00525 protected: 00526 FreePointIndexesType m_FreePointIndexes; 00527 FreeCellIndexesType m_FreeCellIndexes; 00528 }; 00529 } 00530 00531 #ifndef ITK_MANUAL_INSTANTIATION 00532 #include "itkQuadEdgeMesh.hxx" 00533 #endif 00534 00535 #endif 00536