Developer Documentation
StatusAttribT_impl.hh
1 /*===========================================================================*\
2  * *
3  * OpenVolumeMesh *
4  * Copyright (C) 2011 by Computer Graphics Group, RWTH Aachen *
5  * www.openvolumemesh.org *
6  * *
7  *---------------------------------------------------------------------------*
8  * This file is part of OpenVolumeMesh. *
9  * *
10  * OpenVolumeMesh is free software: you can redistribute it and/or modify *
11  * it under the terms of the GNU Lesser General Public License as *
12  * published by the Free Software Foundation, either version 3 of *
13  * the License, or (at your option) any later version with the *
14  * following exceptions: *
15  * *
16  * If other files instantiate templates or use macros *
17  * or inline functions from this file, or you compile this file and *
18  * link it with other files to produce an executable, this file does *
19  * not by itself cause the resulting executable to be covered by the *
20  * GNU Lesser General Public License. This exception does not however *
21  * invalidate any other reasons why the executable file might be *
22  * covered by the GNU Lesser General Public License. *
23  * *
24  * OpenVolumeMesh is distributed in the hope that it will be useful, *
25  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
26  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
27  * GNU Lesser General Public License for more details. *
28  * *
29  * You should have received a copy of the GNU LesserGeneral Public *
30  * License along with OpenVolumeMesh. If not, *
31  * see <http://www.gnu.org/licenses/>. *
32  * *
33 \*===========================================================================*/
34 
35 /*===========================================================================*\
36  * *
37  * $Revision: 36 $ *
38  * $Date: 2012-01-10 18:00:06 +0100 (Di, 10 Jan 2012) $ *
39  * $LastChangedBy: kremer $ *
40  * *
41 \*===========================================================================*/
42 
43 #define STATUSATTRIBT_CC
44 
45 #include "StatusAttrib.hh"
46 
47 #include "../Core/TopologyKernel.hh"
48 #include "../Core/PropertyDefines.hh"
49 
50 #include <map>
51 
52 namespace OpenVolumeMesh {
53 //========================================================================================
54 
55 template<typename std_API_Container_VHandlePointer,
56  typename std_API_Container_HHandlePointer,
57  typename std_API_Container_HFHandlePointer,
58  typename std_API_Container_CHandlePointer>
59 void StatusAttrib::garbage_collection(std_API_Container_VHandlePointer &vh_to_update,
60  std_API_Container_HHandlePointer &hh_to_update,
61  std_API_Container_HFHandlePointer &hfh_to_update,
62  std_API_Container_CHandlePointer &ch_to_update,
63  bool _preserveManifoldness) {
64 
65  /*
66  * This is not a real garbage collection in its conventional
67  * sense. What happens in this routine are the following steps:
68  *
69  * 1. If an entity of dimension n is marked to be deleted,
70  * also mark all incident entities of dimension n + 1
71  * for deletion. Do this in a bottom-up fashion.
72  * 2. Then delete all entities in top-down manner, so that
73  * no invalid incident higher-dimensional entity is generated.
74  * 3. If desired, search for all isolated entities and mark
75  * them deleted in a top-down manner.
76  * 4. Delete all entities marked deleted in step 4 in order
77  * to prevent manifoldness.
78  */
79 
80  // setup tracking so we can update the given handles
81  bool track_vh = !vh_to_update.empty();
82  bool track_hh = !hh_to_update.empty();
83  bool track_hfh = !hfh_to_update.empty();
84  bool track_ch = !ch_to_update.empty();
85  int offset_vh = 0;
86  int offset_hh = 0;
87  int offset_hfh = 0;
88  int offset_ch = 0;
89 
90  std::map<int,int> vh_map;
91  std::map<int,int> hh_map;
92  std::map<int,int> hfh_map;
93  std::map<int,int> ch_map;
94 
95  // initialise the maps
96  if (track_vh) {
97  typename std_API_Container_VHandlePointer::iterator it = vh_to_update.begin();
98  typename std_API_Container_VHandlePointer::iterator end = vh_to_update.end();
99 
100  for (; it != end; ++it) {
101  vh_map[(*it)->idx()] = (*it)->idx();
102  }
103  }
104  if (track_hh) {
105  typename std_API_Container_HHandlePointer::iterator it = hh_to_update.begin();
106  typename std_API_Container_HHandlePointer::iterator end = hh_to_update.end();
107 
108  for (; it != end; ++it) {
109  hh_map[(*it)->idx()] = (*it)->idx();
110  }
111  }
112  if (track_hfh) {
113  typename std_API_Container_HFHandlePointer::iterator it = hfh_to_update.begin();
114  typename std_API_Container_HFHandlePointer::iterator end = hfh_to_update.end();
115 
116  for (; it != end; ++it) {
117  hfh_map[(*it)->idx()] = (*it)->idx();
118  }
119  }
120  if (track_ch) {
121  typename std_API_Container_CHandlePointer::iterator it = ch_to_update.begin();
122  typename std_API_Container_CHandlePointer::iterator end = ch_to_update.end();
123 
124  for (; it != end; ++it) {
125  ch_map[(*it)->idx()] = (*it)->idx();
126  }
127  }
128 
129  // Mark all higher-dimensional entities incident to
130  // entities marked as deleted from bottom to top
131  mark_higher_dim_entities();
132 
133  std::vector<int> vertexIndexMap(kernel_.n_vertices(), -1);
134 
135  // Turn off bottom-up incidences
136  bool v_bu = kernel_.has_vertex_bottom_up_incidences();
137  bool e_bu = kernel_.has_edge_bottom_up_incidences();
138  bool f_bu = kernel_.has_face_bottom_up_incidences();
139 
140  kernel_.enable_bottom_up_incidences(false);
141 
142  std::vector<bool> tags(kernel_.n_cells(), false);
143  std::vector<bool>::iterator tag_it = tags.begin();
144 
145  for(CellIter c_it = kernel_.cells_begin(); c_it != kernel_.cells_end(); ++c_it, ++tag_it) {
146  *tag_it = c_status_[*c_it].deleted();
147 
148  if (track_ch) {
149  if (c_status_[*c_it].deleted()) {
150  ++offset_ch;
151  if (ch_map.find(c_it->idx()) != ch_map.end())
152  ch_map[c_it->idx()] = -1;
153  } else {
154  if (ch_map.find(c_it->idx()) != ch_map.end())
155  ch_map[c_it->idx()] = c_it->idx() - offset_ch;
156  }
157  }
158  }
159  kernel_.delete_multiple_cells(tags);
160 
161  tags.resize(kernel_.n_faces(), false);
162  tag_it = tags.begin();
163 
164  for(FaceIter f_it = kernel_.faces_begin(); f_it != kernel_.faces_end(); ++f_it, ++tag_it) {
165  *tag_it = f_status_[*f_it].deleted();
166 
167  if (track_hfh) {
168  int halfface_idx = f_it->idx() * 2;
169  if (f_status_[*f_it].deleted()) {
170  offset_hfh += 2;
171  if (hfh_map.find(halfface_idx) != hfh_map.end()) {
172  hfh_map[halfface_idx] = -1;
173  }
174  if (hfh_map.find(halfface_idx + 1) != hfh_map.end()) {
175  hfh_map[halfface_idx + 1] = -1;
176  }
177  } else {
178  if (hfh_map.find(halfface_idx) != hfh_map.end()) {
179  hfh_map[halfface_idx] = halfface_idx - offset_hfh;
180  }
181  if (hfh_map.find(halfface_idx + 1) != hfh_map.end()) {
182  hfh_map[halfface_idx + 1] = halfface_idx + 1 - offset_hfh;
183  }
184  }
185  }
186  }
187  kernel_.delete_multiple_faces(tags);
188 
189  tags.resize(kernel_.n_edges(), false);
190  tag_it = tags.begin();
191 
192  for(EdgeIter e_it = kernel_.edges_begin(); e_it != kernel_.edges_end(); ++e_it, ++tag_it) {
193  *tag_it = e_status_[*e_it].deleted();
194 
195  if (track_hh) {
196  int halfedge_idx = e_it->idx() * 2;
197  if (e_status_[*e_it].deleted()) {
198  offset_hh += 2;
199  if (hh_map.find(halfedge_idx) != hh_map.end()) {
200  hh_map[halfedge_idx] = -1;
201  }
202  if (hh_map.find(halfedge_idx + 1) != hh_map.end()) {
203  hh_map[halfedge_idx + 1] = -1;
204  }
205  } else {
206  if (hh_map.find(halfedge_idx) != hh_map.end()) {
207  hh_map[halfedge_idx] = halfedge_idx - offset_hh;
208  }
209  if (hh_map.find(halfedge_idx + 1) != hh_map.end()) {
210  hh_map[halfedge_idx + 1] = halfedge_idx + 1 - offset_hh;
211  }
212  }
213  }
214  }
215  kernel_.delete_multiple_edges(tags);
216 
217  tags.resize(kernel_.n_vertices(), false);
218  tag_it = tags.begin();
219 
220  for(VertexIter v_it = kernel_.vertices_begin(); v_it != kernel_.vertices_end(); ++v_it, ++tag_it) {
221  *tag_it = v_status_[*v_it].deleted();
222 
223  if (track_vh) {
224  if (v_status_[*v_it].deleted()) {
225  if (vh_map.find(v_it->idx()) != vh_map.end()) {
226  ++offset_vh;
227  vh_map[v_it->idx()] = -1;
228  }
229  } else {
230  if (vh_map.find(v_it->idx()) != vh_map.end()) {
231  vh_map[v_it->idx()] = v_it->idx() - offset_vh;
232  }
233  }
234  }
235  }
236  kernel_.delete_multiple_vertices(tags);
237 
238  // update given handles
239  if (track_vh) {
240  typename std_API_Container_VHandlePointer::iterator it = vh_to_update.begin();
241  typename std_API_Container_VHandlePointer::iterator end = vh_to_update.end();
242 
243  for (; it != end; ++it) {
244  *(*it) = VertexHandle( vh_map[(*it)->idx()] );
245  }
246  }
247  if (track_hh) {
248  typename std_API_Container_HHandlePointer::iterator it = hh_to_update.begin();
249  typename std_API_Container_HHandlePointer::iterator end = hh_to_update.end();
250 
251  for (; it != end; ++it) {
252  *(*it) = HalfEdgeHandle( hh_map[(*it)->idx()] );
253  }
254  }
255  if (track_hfh) {
256  typename std_API_Container_HFHandlePointer::iterator it = hfh_to_update.begin();
257  typename std_API_Container_HFHandlePointer::iterator end = hfh_to_update.end();
258 
259  for (; it != end; ++it) {
260  *(*it) = HalfFaceHandle( hfh_map[(*it)->idx()] );
261  }
262  }
263  if (track_ch) {
264  typename std_API_Container_CHandlePointer::iterator it = ch_to_update.begin();
265  typename std_API_Container_CHandlePointer::iterator end = ch_to_update.end();
266 
267  for (; it != end; ++it) {
268  *(*it) = CellHandle( ch_map[(*it)->idx()] );
269  }
270  }
271 
272  // Todo: Resize props
273 
274  if(v_bu) kernel_.enable_vertex_bottom_up_incidences(true);
275  if(e_bu) kernel_.enable_edge_bottom_up_incidences(true);
276  if(f_bu) kernel_.enable_face_bottom_up_incidences(true);
277 
278  // Step 6
279  if(_preserveManifoldness) {
280  if(kernel_.has_full_bottom_up_incidences()) {
281 
282  // Go over all faces and find those
283  // that are not incident to any cell
284  for(FaceIter f_it = kernel_.faces_begin(); f_it != kernel_.faces_end(); ++f_it) {
285 
286  // Get half-faces
287  HalfFaceHandle hf0 = kernel_.halfface_handle(*f_it, 0);
288  HalfFaceHandle hf1 = kernel_.halfface_handle(*f_it, 1);
289 
290  // If neither of the half-faces is incident to a cell, delete face
291  if(kernel_.incident_cell(hf0) == TopologyKernel::InvalidCellHandle &&
292  kernel_.incident_cell(hf1) == TopologyKernel::InvalidCellHandle) {
293 
294  f_status_[*f_it].set_deleted(true);
295  }
296  }
297 
298  // Go over all edges and find those
299  // whose half-edges are not incident to any half-face
300  for(EdgeIter e_it = kernel_.edges_begin(); e_it != kernel_.edges_end(); ++e_it) {
301 
302  // Get half-edges
303  HalfEdgeHandle he = kernel_.halfedge_handle(*e_it, 0);
304 
305  // If the half-edge isn't incident to a half-face, delete edge
306  HalfEdgeHalfFaceIter hehf_it = kernel_.hehf_iter(he);
307 
308  if(!hehf_it.valid()) {
309 
310  e_status_[*e_it].set_deleted(true);
311 
312  } else {
313  bool validFace = false;
314  for(; hehf_it.valid(); ++hehf_it) {
315  if(!f_status_[kernel_.face_handle(*hehf_it)].deleted()) {
316  validFace = true;
317  break;
318  }
319  }
320  if(!validFace) {
321  e_status_[*e_it].set_deleted(true);
322  }
323  }
324  }
325 
326  // Go over all vertices and find those
327  // that are not incident to any edge
328  for(VertexIter v_it = kernel_.vertices_begin(); v_it != kernel_.vertices_end(); ++v_it) {
329 
330  // If neither of the half-edges is incident to a half-face, delete edge
331  VertexOHalfEdgeIter voh_it = kernel_.voh_iter(*v_it);
332 
333  if(!voh_it.valid()) {
334 
335  v_status_[*v_it].set_deleted(true);
336  } else {
337 
338  bool validEdge = false;
339  for(; voh_it.valid(); ++voh_it) {
340  if(!e_status_[kernel_.edge_handle(*voh_it)].deleted()) {
341  validEdge = true;
342  break;
343  }
344  }
345  if(!validEdge) {
346  v_status_[*v_it].set_deleted(true);
347  }
348  }
349  }
350 
351  // Recursive call
352  garbage_collection(vh_to_update, hh_to_update, hfh_to_update, ch_to_update, false);
353 
354  } else {
355 #ifndef NDEBUG
356  std::cerr << "Preservation of three-manifoldness in garbage_collection() "
357  << "requires bottom-up incidences!" << std::endl;
358 #endif
359  return;
360  }
361  }
362 }
363 } // Namespace OpenVolumeMesh
size_t n_edges() const override
Get number of edges in mesh.
size_t n_cells() const override
Get number of cells in mesh.
CellHandle incident_cell(const HalfFaceHandle &_halfFaceHandle) const
Get cell that is incident to the given halfface.
void garbage_collection(bool _preserveManifoldness=false)
Delete all entities that have been marked as deleted.
static EdgeHandle edge_handle(const HalfEdgeHandle &_h)
Handle conversion.
static HalfFaceHandle halfface_handle(const FaceHandle &_h, const unsigned char _subIdx)
Conversion function.
size_t n_faces() const override
Get number of faces in mesh.
size_t n_vertices() const override
Get number of vertices in mesh.
static HalfEdgeHandle halfedge_handle(const EdgeHandle &_h, const unsigned char _subIdx)
Conversion function.