ITK  4.1.0
Insight Segmentation and Registration Toolkit
itkEdgeDecimationQuadEdgeMeshFilter.h
Go to the documentation of this file.
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 __itkEdgeDecimationQuadEdgeMeshFilter_h
00019 #define __itkEdgeDecimationQuadEdgeMeshFilter_h
00020 
00021 #include <list>
00022 #include <map>
00023 #include <algorithm>
00024 
00025 #include "itkQuadEdgeMeshEulerOperatorJoinVertexFunction.h"
00026 #include "itkQuadEdgeMeshPolygonCell.h"
00027 
00028 #include "itkDecimationQuadEdgeMeshFilter.h"
00029 #include "itkPriorityQueueContainer.h"
00030 #include "itkTriangleHelper.h"
00031 
00032 namespace itk
00033 {
00039 template< class TInput, class TOutput, class TCriterion >
00040 class ITK_EXPORT EdgeDecimationQuadEdgeMeshFilter:
00041   public DecimationQuadEdgeMeshFilter< TInput, TOutput, TCriterion >
00042 {
00043 public:
00044   typedef EdgeDecimationQuadEdgeMeshFilter Self;
00045   typedef SmartPointer< Self >             Pointer;
00046   typedef SmartPointer< const Self >       ConstPointer;
00047   typedef DecimationQuadEdgeMeshFilter<
00048     TInput, TOutput, TCriterion >          Superclass;
00049 
00051   itkTypeMacro(EdgeDecimationQuadEdgeMeshFilter, DecimationQuadEdgeMeshFilter);
00052 
00053   typedef TInput                          InputMeshType;
00054   typedef typename InputMeshType::Pointer InputMeshPointer;
00055 
00056   typedef TOutput                                         OutputMeshType;
00057   typedef typename OutputMeshType::Pointer                OutputMeshPointer;
00058   typedef typename OutputMeshType::PointIdentifier        OutputPointIdentifier;
00059   typedef typename OutputMeshType::PointType              OutputPointType;
00060   typedef typename OutputPointType::VectorType            OutputVectorType;
00061   typedef typename OutputMeshType::QEType                 OutputQEType;
00062   typedef typename OutputMeshType::EdgeCellType           OutputEdgeCellType;
00063   typedef typename OutputMeshType::CellType               OutputCellType;
00064   typedef typename OutputMeshType::CellIdentifier         OutputCellIdentifier;
00065   typedef typename OutputMeshType::CellsContainerPointer  OutputCellsContainerPointer;
00066   typedef typename OutputMeshType::CellsContainerIterator OutputCellsContainerIterator;
00067 
00068   typedef QuadEdgeMeshPolygonCell< OutputCellType > OutputPolygonType;
00069 
00070   typedef TCriterion                                       CriterionType;
00071   typedef typename CriterionType::Pointer                  CriterionPointer;
00072   typedef typename CriterionType::MeasureType              MeasureType;
00073   typedef typename CriterionType::PriorityType             PriorityType;
00074   typedef typename CriterionType::PriorityQueueWrapperType PriorityQueueItemType;
00075 
00076   typedef PriorityQueueContainer< PriorityQueueItemType *,
00077                                   ElementWrapperPointerInterface< PriorityQueueItemType * >,
00078                                   PriorityType >                                          PriorityQueueType;
00079   typedef typename PriorityQueueType::Pointer PriorityQueuePointer;
00080 
00081   typedef std::map< OutputQEType *, PriorityQueueItemType * > QueueMapType;
00082   typedef typename QueueMapType::const_iterator               QueueMapConstIterator;
00083   typedef typename QueueMapType::iterator                     QueueMapIterator;
00084 
00085   typedef QuadEdgeMeshEulerOperatorJoinVertexFunction< OutputMeshType, OutputQEType > OperatorType;
00086   typedef typename OperatorType::Pointer                                              OperatorPointer;
00087 protected:
00088 
00089   EdgeDecimationQuadEdgeMeshFilter();
00090   virtual ~EdgeDecimationQuadEdgeMeshFilter();
00091 
00092   bool m_Relocate;
00093   bool m_CheckOrientation;
00094 
00095   PriorityQueuePointer m_PriorityQueue;
00096   QueueMapType         m_QueueMapper;
00097   OutputQEType *       m_Element;
00098   PriorityType         m_Priority;
00099   OperatorPointer      m_JoinVertexFunction;
00100 
00106   virtual MeasureType MeasureEdge(OutputQEType *iEdge) = 0;
00107 
00111   void FillPriorityQueue();
00112 
00117   void PushElement(OutputQEType *iEdge);
00118 
00124   bool IsEdgeOKToBeProcessed(OutputQEType *iEdge);
00125 
00129   void Extract();
00130 
00135   void DeleteElement(OutputQEType *iEdge);
00136 
00137   virtual void DeletePoint(const OutputPointIdentifier & iIdToBeDeleted,
00138                            const OutputPointIdentifier & iRemaing);
00139 
00145   virtual void PushOrUpdateElement(OutputQEType *iEdge);
00146 
00150   virtual void JoinVertexFailed();
00151 
00155   virtual bool ProcessWithoutAnyTopologicalGuarantee();
00156 
00161   virtual unsigned int CheckQEProcessingStatus();
00162 
00167   virtual bool ProcessWithTopologicalGuarantee();
00168 
00172   SizeValueType NumberOfCommonVerticesIn0Ring() const;
00173 
00177   void RemoveSamosa();
00178 
00183   void TagElementOut(OutputQEType *iEdge);
00184 
00188   void RemoveEye();
00189 
00195   virtual OutputPointType Relocate(OutputQEType *iEdge) = 0;
00196 
00201   bool CheckOrientation(OutputQEType *iEdge,
00202                         const OutputPointIdentifier & iId,
00203                         const OutputPointType & iPt)
00204   {
00205     OutputMeshPointer           output = this->GetOutput();
00206     OutputCellsContainerPointer cells = output->GetCells();
00208 
00209     std::list< OutputCellIdentifier > r1, r2, elements_to_be_tested;
00210     OutputQEType *                    qe = iEdge;
00211     OutputQEType *                    qe_it = qe->GetOnext();
00212 
00213     do
00214       {
00215       r1.push_back( qe_it->GetLeft() );
00216       qe_it = qe_it->GetOnext();
00217       }
00218     while ( qe_it != qe );
00219 
00220     qe = iEdge->GetSym();
00221     qe_it = qe->GetOnext();
00222 
00223     do
00224       {
00225       r2.push_back( qe_it->GetLeft() );
00226       qe_it = qe_it->GetOnext();
00227       }
00228     while ( qe_it != qe );
00229 
00230     r1.sort();
00231     r2.sort();
00232 
00233     std::set_symmetric_difference( r1.begin(), r1.end(),
00234                                    r2.begin(), r2.end(),
00235                                    std::back_inserter(elements_to_be_tested) );
00236 
00237     typename std::list< OutputCellIdentifier >::iterator
00238     it = elements_to_be_tested.begin();
00239 
00240     typedef TriangleHelper< OutputPointType > TriangleType;
00241 
00242     bool                  orientation_ok(true);
00243     OutputCellIdentifier  c_id(0);
00244     OutputPolygonType *   poly;
00245     OutputPointIdentifier p_id;
00246 
00247     int             k(0), replace_k(0);
00248     OutputPointType pt[3];
00249 
00250     OutputVectorType n_bef, n_aft;
00251 
00252     while ( ( it != elements_to_be_tested.end() ) && orientation_ok )
00253       {
00254       c_id = *it;
00255       poly = dynamic_cast< OutputPolygonType * >( cells->GetElement(c_id) );
00256 
00257       qe = poly->GetEdgeRingEntry();
00258       qe_it = qe;
00259       k = 0;
00260 
00261       do
00262         {
00263         p_id = qe_it->GetOrigin();
00264         if ( p_id == iId )
00265           {
00266           replace_k = k;
00267           }
00268         pt[k++] = output->GetPoint(p_id);
00269         qe_it = qe_it->GetLnext();
00270         }
00271       while ( qe_it != qe );
00272 
00273       n_bef = TriangleType::ComputeNormal(pt[0], pt[1], pt[2]);
00274       switch ( replace_k )
00275         {
00276         default:
00277         case 0:
00278           n_aft = TriangleType::ComputeNormal(iPt, pt[1], pt[2]);
00279           break;
00280         case 1:
00281           n_aft = TriangleType::ComputeNormal(pt[0], iPt, pt[2]);
00282           break;
00283         case 2:
00284           n_aft = TriangleType::ComputeNormal(pt[0], pt[1], iPt);
00285           break;
00286         }
00287 
00288       orientation_ok = ( n_bef * n_aft ) < 0.;
00289       ++it;
00290       }
00291 
00292     return orientation_ok;
00293   }
00294 
00299   bool IsCriterionSatisfied();
00300 
00301 private:
00302   EdgeDecimationQuadEdgeMeshFilter(const Self &);
00303   void operator=(const Self &);
00304 };
00305 }
00306 
00307 #include "itkEdgeDecimationQuadEdgeMeshFilter.hxx"
00308 #endif
00309