ITK  4.2.0
Insight Segmentation and Registration Toolkit
itkEdgeDecimationQuadEdgeMeshFilter.h
Go to the documentation of this file.
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 
27 
30 #include "itkTriangleHelper.h"
31 
32 namespace itk
33 {
39 template< class TInput, class TOutput, class TCriterion >
41  public DecimationQuadEdgeMeshFilter< TInput, TOutput, TCriterion >
42 {
43 public:
48  TInput, TOutput, TCriterion > Superclass;
49 
52 
53  typedef TInput InputMeshType;
54  typedef typename InputMeshType::Pointer InputMeshPointer;
55 
56  typedef TOutput OutputMeshType;
57  typedef typename OutputMeshType::Pointer OutputMeshPointer;
58  typedef typename OutputMeshType::PointIdentifier OutputPointIdentifier;
59  typedef typename OutputMeshType::PointType OutputPointType;
60  typedef typename OutputPointType::VectorType OutputVectorType;
61  typedef typename OutputMeshType::QEType OutputQEType;
62  typedef typename OutputMeshType::EdgeCellType OutputEdgeCellType;
63  typedef typename OutputMeshType::CellType OutputCellType;
64  typedef typename OutputMeshType::CellIdentifier OutputCellIdentifier;
65  typedef typename OutputMeshType::CellsContainerPointer OutputCellsContainerPointer;
66  typedef typename OutputMeshType::CellsContainerIterator OutputCellsContainerIterator;
67 
69 
70  typedef TCriterion CriterionType;
71  typedef typename CriterionType::Pointer CriterionPointer;
72  typedef typename CriterionType::MeasureType MeasureType;
73  typedef typename CriterionType::PriorityType PriorityType;
74  typedef typename CriterionType::PriorityQueueWrapperType PriorityQueueItemType;
75 
80 
81  typedef std::map< OutputQEType *, PriorityQueueItemType * > QueueMapType;
82  typedef typename QueueMapType::const_iterator QueueMapConstIterator;
83  typedef typename QueueMapType::iterator QueueMapIterator;
84 
87 protected:
88 
91 
92  bool m_Relocate;
94 
100 
106  virtual MeasureType MeasureEdge(OutputQEType *iEdge) = 0;
107 
111  void FillPriorityQueue();
112 
117  void PushElement(OutputQEType *iEdge);
118 
124  bool IsEdgeOKToBeProcessed(OutputQEType *iEdge);
125 
129  void Extract();
130 
135  void DeleteElement(OutputQEType *iEdge);
136 
137  virtual void DeletePoint(const OutputPointIdentifier & iIdToBeDeleted,
138  const OutputPointIdentifier & iRemaing);
139 
145  virtual void PushOrUpdateElement(OutputQEType *iEdge);
146 
150  virtual void JoinVertexFailed();
151 
155  virtual bool ProcessWithoutAnyTopologicalGuarantee();
156 
161  virtual unsigned int CheckQEProcessingStatus();
162 
167  virtual bool ProcessWithTopologicalGuarantee();
168 
172  SizeValueType NumberOfCommonVerticesIn0Ring() const;
173 
177  void RemoveSamosa();
178 
183  void TagElementOut(OutputQEType *iEdge);
184 
188  void RemoveEye();
189 
195  virtual OutputPointType Relocate(OutputQEType *iEdge) = 0;
196 
201  bool CheckOrientation(OutputQEType *iEdge,
202  const OutputPointIdentifier & iId,
203  const OutputPointType & iPt)
204  {
205  OutputMeshPointer output = this->GetOutput();
206  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  typedef TriangleHelper< OutputPointType > TriangleType;
241 
242  bool orientation_ok(true);
243  OutputCellIdentifier c_id(0);
244  OutputPolygonType * poly;
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 
299  bool IsCriterionSatisfied();
300 
301 private:
302  EdgeDecimationQuadEdgeMeshFilter(const Self &);
303  void operator=(const Self &);
304 };
305 }
306 
307 #include "itkEdgeDecimationQuadEdgeMeshFilter.hxx"
308 #endif
309