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
OpenVolumeMesh::FaceIter
Definition: Iterators.hh:995
OpenVolumeMesh::TopologyKernel::halfedge_handle
static HalfEdgeHandle halfedge_handle(const EdgeHandle &_h, const unsigned char _subIdx)
Conversion function.
Definition: TopologyKernel.hh:915
OpenVolumeMesh::StatusAttrib::garbage_collection
void garbage_collection(bool _preserveManifoldness=false)
Delete all entities that have been marked as deleted.
Definition: StatusAttrib.cc:153
OpenVolumeMesh::VertexOHalfEdgeIter
Definition: Iterators.hh:241
OpenVolumeMesh::HalfEdgeHalfFaceIter
Definition: Iterators.hh:365
OpenVolumeMesh::TopologyKernel::edge_handle
static EdgeHandle edge_handle(const HalfEdgeHandle &_h)
Handle conversion.
Definition: TopologyKernel.hh:933
OpenVolumeMesh::VertexIter
Definition: Iterators.hh:833
OpenVolumeMesh::HandleT< Entity::Vertex >
OpenVolumeMesh::TopologyKernel::n_faces
virtual size_t n_faces() const
Get number of faces in mesh.
Definition: TopologyKernel.hh:328
OpenVolumeMesh
Definition: ColorAttrib.hh:53
OpenVolumeMesh::CellIter
Definition: Iterators.hh:1103
OpenVolumeMesh::TopologyKernel::n_cells
virtual size_t n_cells() const
Get number of cells in mesh.
Definition: TopologyKernel.hh:332
OpenVolumeMesh::TopologyKernel::n_edges
virtual size_t n_edges() const
Get number of edges in mesh.
Definition: TopologyKernel.hh:324
OpenVolumeMesh::TopologyKernel::incident_cell
CellHandle incident_cell(const HalfFaceHandle &_halfFaceHandle) const
Get cell that is incident to the given halfface.
Definition: TopologyKernel.cc:2310
OpenVolumeMesh::TopologyKernel::halfface_handle
static HalfFaceHandle halfface_handle(const FaceHandle &_h, const unsigned char _subIdx)
Conversion function.
Definition: TopologyKernel.hh:924
OpenVolumeMesh::TopologyKernel::n_vertices
virtual size_t n_vertices() const
Get number of vertices in mesh.
Definition: TopologyKernel.hh:322
OpenVolumeMesh::EdgeIter
Definition: Iterators.hh:887