ITK  4.6.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< typename TInput, typename TOutput, typename 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 
88 protected:
89 
92 
93  bool m_Relocate;
95 
101 
107  virtual MeasureType MeasureEdge(OutputQEType *iEdge) = 0;
108 
112  void FillPriorityQueue();
113 
118  void PushElement(OutputQEType *iEdge);
119 
125  bool IsEdgeOKToBeProcessed(OutputQEType *iEdge);
126 
130  void Extract();
131 
136  void DeleteElement(OutputQEType *iEdge);
137 
138  virtual void DeletePoint(const OutputPointIdentifier & iIdToBeDeleted,
139  const OutputPointIdentifier & iRemaing);
140 
146  virtual void PushOrUpdateElement(OutputQEType *iEdge);
147 
151  virtual void JoinVertexFailed();
152 
157 
162  virtual unsigned int CheckQEProcessingStatus();
163 
168  virtual bool ProcessWithTopologicalGuarantee();
169 
174 
178  void RemoveSamosa();
179 
184  void TagElementOut(OutputQEType *iEdge);
185 
189  void RemoveEye();
190 
196  virtual OutputPointType Relocate(OutputQEType *iEdge) = 0;
197 
203  const OutputPointIdentifier & iId,
204  const OutputPointType & iPt)
205  {
206  OutputMeshPointer output = this->GetOutput();
207  OutputCellsContainerPointer cells = output->GetCells();
209 
210  std::list< OutputCellIdentifier > r1, r2, elements_to_be_tested;
211  OutputQEType * qe = iEdge;
212  OutputQEType * qe_it = qe->GetOnext();
213 
214  do
215  {
216  r1.push_back( qe_it->GetLeft() );
217  qe_it = qe_it->GetOnext();
218  }
219  while ( qe_it != qe );
220 
221  qe = iEdge->GetSym();
222  qe_it = qe->GetOnext();
223 
224  do
225  {
226  r2.push_back( qe_it->GetLeft() );
227  qe_it = qe_it->GetOnext();
228  }
229  while ( qe_it != qe );
230 
231  r1.sort();
232  r2.sort();
233 
234  std::set_symmetric_difference( r1.begin(), r1.end(),
235  r2.begin(), r2.end(),
236  std::back_inserter(elements_to_be_tested) );
237 
238  typename std::list< OutputCellIdentifier >::iterator
239  it = elements_to_be_tested.begin();
240 
241  typedef TriangleHelper< OutputPointType > TriangleType;
242 
243  bool orientation_ok(true);
244  OutputCellIdentifier c_id(0);
245  OutputPolygonType * poly;
247 
248  int k(0), replace_k(0);
249  OutputPointType pt[3];
250 
251  OutputVectorType n_bef, n_aft;
252 
253  while ( ( it != elements_to_be_tested.end() ) && orientation_ok )
254  {
255  c_id = *it;
256  poly = dynamic_cast< OutputPolygonType * >( cells->GetElement(c_id) );
257 
258  qe = poly->GetEdgeRingEntry();
259  qe_it = qe;
260  k = 0;
261 
262  do
263  {
264  p_id = qe_it->GetOrigin();
265  if ( p_id == iId )
266  {
267  replace_k = k;
268  }
269  pt[k++] = output->GetPoint(p_id);
270  qe_it = qe_it->GetLnext();
271  }
272  while ( qe_it != qe );
273 
274  n_bef = TriangleType::ComputeNormal(pt[0], pt[1], pt[2]);
275  switch ( replace_k )
276  {
277  default:
278  case 0:
279  n_aft = TriangleType::ComputeNormal(iPt, pt[1], pt[2]);
280  break;
281  case 1:
282  n_aft = TriangleType::ComputeNormal(pt[0], iPt, pt[2]);
283  break;
284  case 2:
285  n_aft = TriangleType::ComputeNormal(pt[0], pt[1], iPt);
286  break;
287  }
288 
289  orientation_ok = ( n_bef * n_aft ) < 0.;
290  ++it;
291  }
292 
293  return orientation_ok;
294  }
295 
300  bool IsCriterionSatisfied();
301 
302 private:
304  void operator=(const Self &);
305 
306 };
307 }
308 
309 #include "itkEdgeDecimationQuadEdgeMeshFilter.hxx"
310 #endif
void DeleteElement(OutputQEType *iEdge)
Delete a given edge in the priority queue.
DecimationQuadEdgeMeshFilter< TInput, TOutput, TCriterion > Superclass
QuadEdgeMeshEulerOperatorJoinVertexFunction< OutputMeshType, OutputQEType > OperatorType
bool IsEdgeOKToBeProcessed(OutputQEType *iEdge)
Check if iEdge is valid and then can be processed.
QuadEdgeMeshPolygonCell< OutputCellType > OutputPolygonType
OutputMeshType * GetOutput(void)
Collapse a given edge by joining its dest and its org.
virtual void PushOrUpdateElement(OutputQEType *iEdge)
Push iEdge in the priority queue if it is not already, else its corresponding priority value is updat...
QuadEdgeType * GetEdgeRingEntry() const
OutputMeshType::CellsContainerPointer OutputCellsContainerPointer
OutputMeshType::CellsContainerIterator OutputCellsContainerIterator
unsigned long SizeValueType
Definition: itkIntTypes.h:143
virtual bool ProcessWithoutAnyTopologicalGuarantee()
virtual void DeletePoint(const OutputPointIdentifier &iIdToBeDeleted, const OutputPointIdentifier &iRemaing)
A convenience class for computation of various triangle elements in 2D or 3D.
void PushElement(OutputQEType *iEdge)
Push one edge in the priority queue.
bool CheckOrientation(OutputQEType *iEdge, const OutputPointIdentifier &iId, const OutputPointType &iPt)
void FillPriorityQueue()
Fill the priority queue.
std::map< OutputQEType *, PriorityQueueItemType * > QueueMapType
virtual unsigned int CheckQEProcessingStatus()
CriterionType::PriorityQueueWrapperType PriorityQueueItemType
PriorityQueueContainer< PriorityQueueItemType *, ElementWrapperPointerInterface< PriorityQueueItemType * >, PriorityType > PriorityQueueType
void TagElementOut(OutputQEType *iEdge)
virtual MeasureType MeasureEdge(OutputQEType *iEdge)=0
Compute the measure value for iEdge.
virtual OutputPointType Relocate(OutputQEType *iEdge)=0
void Extract()
Extract the edge to be processed.
SizeValueType NumberOfCommonVerticesIn0Ring() const