| OpenMesh

ArrayKernelT_impl.hh
1 /* ========================================================================= *
2 * *
3 * OpenMesh *
4 * Copyright (c) 2001-2015, RWTH-Aachen University *
5 * Department of Computer Graphics and Multimedia *
6 * All rights reserved. *
7 * www.openmesh.org *
8 * *
9 *---------------------------------------------------------------------------*
10 * This file is part of OpenMesh. *
11 *---------------------------------------------------------------------------*
12 * *
13 * Redistribution and use in source and binary forms, with or without *
14 * modification, are permitted provided that the following conditions *
15 * are met: *
16 * *
17 * 1. Redistributions of source code must retain the above copyright notice, *
18 * this list of conditions and the following disclaimer. *
19 * *
20 * 2. Redistributions in binary form must reproduce the above copyright *
21 * notice, this list of conditions and the following disclaimer in the *
22 * documentation and/or other materials provided with the distribution. *
23 * *
24 * 3. Neither the name of the copyright holder nor the names of its *
25 * contributors may be used to endorse or promote products derived from *
26 * this software without specific prior written permission. *
27 * *
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
30 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
31 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
32 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
33 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
34 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR *
35 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF *
36 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING *
37 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS *
38 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
39 * *
40 * ========================================================================= */
41
42 #define OPENMESH_ARRAY_KERNEL_C
43
44 //== INCLUDES =================================================================
45
46 #include <OpenMesh/Core/Mesh/ArrayKernel.hh>
47
48 //== NAMESPACES ===============================================================
49
50 namespace OpenMesh
51 {
52
53 //== IMPLEMENTATION ==========================================================
54
55 template<typename std_API_Container_VHandlePointer,
56 typename std_API_Container_HHandlePointer,
57 typename std_API_Container_FHandlePointer>
58 void ArrayKernel::garbage_collection(std_API_Container_VHandlePointer& vh_to_update,
59 std_API_Container_HHandlePointer& hh_to_update,
60 std_API_Container_FHandlePointer& fh_to_update,
61 bool _v, bool _e, bool _f)
62 {
63
64 #ifdef DEBUG
65 #ifndef OM_GARBAGE_NO_STATUS_WARNING
66 if ( !this->has_vertex_status() )
67 omerr() << "garbage_collection: No vertex status available. You can request it: mesh.request_vertex_status() or define OM_GARBAGE_NO_STATUS_WARNING to silence this warning." << std::endl;
68 if ( !this->has_edge_status() )
69 omerr() << "garbage_collection: No edge status available. You can request it: mesh.request_edge_status() or define OM_GARBAGE_NO_STATUS_WARNING to silence this warning." << std::endl;
70 if ( !this->has_face_status() )
71 omerr() << "garbage_collection: No face status available. You can request it: mesh.request_face_status() or define OM_GARBAGE_NO_STATUS_WARNING to silence this warning." << std::endl;
72 #endif
73 #endif
74
75 const bool track_vhandles = ( !vh_to_update.empty() );
76 const bool track_hhandles = ( !hh_to_update.empty() );
77 const bool track_fhandles = ( !fh_to_update.empty() );
78
79 int i, i0, i1;
80
81 int nV = int(n_vertices());
82 int nE = int(n_edges());
83 int nH = int(2*n_edges());
84 int nF = (int(n_faces()));
85
86 std::vector<VertexHandle> vh_map;
87 std::vector<HalfedgeHandle> hh_map;
88 std::vector<FaceHandle> fh_map;
89
90 std::map <int, int> vertex_inverse_map;
91 std::map <int, int> halfedge_inverse_map;
92 std::map <int, int> face_inverse_map;
93
94 // setup handle mapping:
95 vh_map.reserve(nV);
96 for (i=0; i<nV; ++i) vh_map.push_back(VertexHandle(i));
97
98 hh_map.reserve(nH);
99 for (i=0; i<nH; ++i) hh_map.push_back(HalfedgeHandle(i));
100
101 fh_map.reserve(nF);
102 for (i=0; i<nF; ++i) fh_map.push_back(FaceHandle(i));
103
104 // remove deleted vertices
105 if (_v && n_vertices() > 0 && this->has_vertex_status() )
106 {
107 i0=0; i1=nV-1;
108
109 while (1)
110 {
111 // find 1st deleted and last un-deleted
112 while (!status(VertexHandle(i0)).deleted() && i0 < i1) ++i0;
113 while ( status(VertexHandle(i1)).deleted() && i0 < i1) --i1;
114 if (i0 >= i1) break;
115
116 // If we keep track of the vertex handles for updates,
117 // we need to have the opposite direction
118 if ( track_vhandles ) {
119 vertex_inverse_map[i1] = i0;
120 vertex_inverse_map[i0] = -1;
121 }
122
123 // swap
124 std::swap(vertices_[i0], vertices_[i1]);
125 std::swap(vh_map[i0], vh_map[i1]);
126 vprops_swap(i0, i1);
127 };
128
129 vertices_.resize(status(VertexHandle(i0)).deleted() ? i0 : i0+1);
130 vprops_resize(n_vertices());
131 }
132
133
134 // remove deleted edges
135 if (_e && n_edges() > 0 && this->has_edge_status() )
136 {
137 i0=0; i1=nE-1;
138
139 while (1)
140 {
141 // find 1st deleted and last un-deleted
142 while (!status(EdgeHandle(i0)).deleted() && i0 < i1) ++i0;
143 while ( status(EdgeHandle(i1)).deleted() && i0 < i1) --i1;
144 if (i0 >= i1) break;
145
146 // If we keep track of the vertex handles for updates,
147 // we need to have the opposite direction
148 if ( track_hhandles ) {
149 halfedge_inverse_map[2*i1] = 2 * i0;
150 halfedge_inverse_map[2*i0] = -1;
151
152 halfedge_inverse_map[2*i1 + 1] = 2 * i0 + 1;
153 halfedge_inverse_map[2*i0 + 1] = -1;
154 }
155
156 // swap
157 std::swap(edges_[i0], edges_[i1]);
158 std::swap(hh_map[2*i0], hh_map[2*i1]);
159 std::swap(hh_map[2*i0+1], hh_map[2*i1+1]);
160 eprops_swap(i0, i1);
161 hprops_swap(2*i0, 2*i1);
162 hprops_swap(2*i0+1, 2*i1+1);
163 };
164
165 edges_.resize(status(EdgeHandle(i0)).deleted() ? i0 : i0+1);
166 eprops_resize(n_edges());
167 hprops_resize(n_halfedges());
168 }
169
170
171 // remove deleted faces
172 if (_f && n_faces() > 0 && this->has_face_status() )
173 {
174 i0=0; i1=nF-1;
175
176 while (1)
177 {
178 // find 1st deleted and last un-deleted
179 while (!status(FaceHandle(i0)).deleted() && i0 < i1) ++i0;
180 while ( status(FaceHandle(i1)).deleted() && i0 < i1) --i1;
181 if (i0 >= i1) break;
182
183 // If we keep track of the face handles for updates,
184 // we need to have the opposite direction
185 if ( track_fhandles ) {
186 face_inverse_map[i1] = i0;
187 face_inverse_map[i0] = -1;
188 }
189
190 // swap
191 std::swap(faces_[i0], faces_[i1]);
192 std::swap(fh_map[i0], fh_map[i1]);
193 fprops_swap(i0, i1);
194 };
195
196 faces_.resize(status(FaceHandle(i0)).deleted() ? i0 : i0+1);
197 fprops_resize(n_faces());
198 }
199
200
201 // update handles of vertices
202 if (_e)
203 {
204 KernelVertexIter v_it(vertices_begin()), v_end(vertices_end());
205 VertexHandle vh;
206
207 for (; v_it!=v_end; ++v_it)
208 {
209 vh = handle(*v_it);
210 if (!is_isolated(vh))
211 {
212 set_halfedge_handle(vh, hh_map[halfedge_handle(vh).idx()]);
213 }
214 }
215 }
216
217 HalfedgeHandle hh;
218 // update handles of halfedges
219 for (KernelEdgeIter e_it(edges_begin()); e_it != edges_end(); ++e_it)
220 {//in the first pass update the (half)edges vertices
221 hh = halfedge_handle(handle(*e_it), 0);
222 set_vertex_handle(hh, vh_map[to_vertex_handle(hh).idx()]);
223 hh = halfedge_handle(handle(*e_it), 1);
224 set_vertex_handle(hh, vh_map[to_vertex_handle(hh).idx()]);
225 }
226 for (KernelEdgeIter e_it(edges_begin()); e_it != edges_end(); ++e_it)
227 {//in the second pass update the connectivity of the (half)edges
228 hh = halfedge_handle(handle(*e_it), 0);
229 set_next_halfedge_handle(hh, hh_map[next_halfedge_handle(hh).idx()]);
230 if (!is_boundary(hh))
231 {
232 set_face_handle(hh, fh_map[face_handle(hh).idx()]);
233 }
234 hh = halfedge_handle(handle(*e_it), 1);
235 set_next_halfedge_handle(hh, hh_map[next_halfedge_handle(hh).idx()]);
236 if (!is_boundary(hh))
237 {
238 set_face_handle(hh, fh_map[face_handle(hh).idx()]);
239 }
240 }
241
242 // update handles of faces
243 if (_e)
244 {
245 KernelFaceIter f_it(faces_begin()), f_end(faces_end());
246 FaceHandle fh;
247
248 for (; f_it!=f_end; ++f_it)
249 {
250 fh = handle(*f_it);
251 set_halfedge_handle(fh, hh_map[halfedge_handle(fh).idx()]);
252 }
253 }
254
255 const int vertexCount = int(vertices_.size());
256 const int halfedgeCount = int(edges_.size() * 2);
257 const int faceCount = int(faces_.size());
258
259 // Update the vertex handles in the vertex handle vector
260 typename std_API_Container_VHandlePointer::iterator v_it(vh_to_update.begin()), v_it_end(vh_to_update.end());
261 for(; v_it != v_it_end; ++v_it)
262 {
263
264 // Only changed vertices need to be considered
265 if ( (*v_it)->idx() != vh_map[(*v_it)->idx()].idx() ) {
266 *(*v_it) = VertexHandle(vertex_inverse_map[(*v_it)->idx()]);
267
268 // Vertices above the vertex count have to be already mapped, or they are invalid now!
269 } else if ( ((*v_it)->idx() >= vertexCount) && (vertex_inverse_map.find((*v_it)->idx()) == vertex_inverse_map.end()) ) {
270 (*v_it)->invalidate();
271 }
272
273 }
274
275 // Update the halfedge handles in the halfedge handle vector
276 typename std_API_Container_HHandlePointer::iterator hh_it(hh_to_update.begin()), hh_it_end(hh_to_update.end());
277 for(; hh_it != hh_it_end; ++hh_it)
278 {
279 // Only changed faces need to be considered
280 if ( (*hh_it)->idx() != hh_map[(*hh_it)->idx()].idx() ) {
281 *(*hh_it) = HalfedgeHandle(halfedge_inverse_map[(*hh_it)->idx()]);
282
283 // Vertices above the face count have to be already mapped, or they are invalid now!
284 } else if ( ((*hh_it)->idx() >= halfedgeCount) && (halfedge_inverse_map.find((*hh_it)->idx()) == halfedge_inverse_map.end()) ) {
285 (*hh_it)->invalidate();
286 }
287
288 }
289
290 // Update the face handles in the face handle vector
291 typename std_API_Container_FHandlePointer::iterator fh_it(fh_to_update.begin()), fh_it_end(fh_to_update.end());
292 for(; fh_it != fh_it_end; ++fh_it)
293 {
294
295 // Only changed faces need to be considered
296 if ( (*fh_it)->idx() != fh_map[(*fh_it)->idx()].idx() ) {
297 *(*fh_it) = FaceHandle(face_inverse_map[(*fh_it)->idx()]);
298
299 // Vertices above the face count have to be already mapped, or they are invalid now!
300 } else if ( ((*fh_it)->idx() >= faceCount) && (face_inverse_map.find((*fh_it)->idx()) == face_inverse_map.end()) ) {
301 (*fh_it)->invalidate();
302 }
303
304 }
305 }
306
307 }
308
OpenMesh::FaceHandle
Handle for a face entity.
Definition: Handles.hh:141
OpenMesh::ArrayKernel::garbage_collection
void garbage_collection(bool _v=true, bool _e=true, bool _f=true)
garbage collection
Definition: ArrayKernel.cc:166
OpenMesh::BaseHandle::invalidate
void invalidate()
reset handle to be invalid
Definition: Handles.hh:77
OpenMesh::BaseKernel::vprops_resize
void vprops_resize(size_t _n) const
Resizes all vertex property vectors to the specified size.
Definition: BaseKernel.hh:703
OpenMesh::ArrayKernel::status
const StatusInfo & status(VertexHandle _vh) const
Status Query API.
Definition: ArrayKernel.hh:501
OpenMesh::VertexHandle
Handle for a vertex entity.
Definition: Handles.hh:120
OpenMesh::ArrayKernel::is_boundary
bool is_boundary(HalfedgeHandle _heh) const
Is halfedge _heh a boundary halfedge (is its face handle invalid) ?
Definition: ArrayKernel.hh:398
OpenMesh::EdgeHandle
Handle for a edge entity.
Definition: Handles.hh:134
OpenMesh
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:59
OpenMesh::HalfedgeHandle
Handle for a halfedge entity.
Definition: Handles.hh:127