Developer Documentation
ArrayKernelT.cc
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 /*===========================================================================*\
43  * *
44  * $Revision: 362 $ *
45  * $Date: 2011-01-26 10:21:12 +0100 (Mi, 26 Jan 2011) $ *
46  * *
47 \*===========================================================================*/
48 
49 #define OPENMESH_ARRAY_KERNEL_C
50 
51 //== INCLUDES =================================================================
52 
53 #include <OpenMesh/Core/Mesh/ArrayKernel.hh>
54 
55 //== NAMESPACES ===============================================================
56 
57 namespace OpenMesh
58 {
59 
60 //== IMPLEMENTATION ==========================================================
61 
62 template<typename std_API_Container_VHandlePointer,
63  typename std_API_Container_HHandlePointer,
64  typename std_API_Container_FHandlePointer>
65 void ArrayKernel::garbage_collection(std_API_Container_VHandlePointer& vh_to_update,
66  std_API_Container_HHandlePointer& hh_to_update,
67  std_API_Container_FHandlePointer& fh_to_update,
68  bool _v, bool _e, bool _f)
69 {
70 
71 #ifdef DEBUG
72  #ifndef OM_GARBAGE_NO_STATUS_WARNING
73  if ( !this->has_vertex_status() )
74  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;
75  if ( !this->has_edge_status() )
76  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;
77  if ( !this->has_face_status() )
78  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;
79  #endif
80 #endif
81 
82  const bool track_vhandles = ( !vh_to_update.empty() );
83  const bool track_hhandles = ( !hh_to_update.empty() );
84  const bool track_fhandles = ( !fh_to_update.empty() );
85 
86  int i, i0, i1;
87 
88  int nV = int(n_vertices());
89  int nE = int(n_edges());
90  int nH = int(2*n_edges());
91  int nF = (int(n_faces()));
92 
93  std::vector<VertexHandle> vh_map;
94  std::vector<HalfedgeHandle> hh_map;
95  std::vector<FaceHandle> fh_map;
96 
97  std::map <int, int> vertex_inverse_map;
98  std::map <int, int> halfedge_inverse_map;
99  std::map <int, int> face_inverse_map;
100 
101  // setup handle mapping:
102  vh_map.reserve(nV);
103  for (i=0; i<nV; ++i) vh_map.push_back(VertexHandle(i));
104 
105  hh_map.reserve(nH);
106  for (i=0; i<nH; ++i) hh_map.push_back(HalfedgeHandle(i));
107 
108  fh_map.reserve(nF);
109  for (i=0; i<nF; ++i) fh_map.push_back(FaceHandle(i));
110 
111  // remove deleted vertices
112  if (_v && n_vertices() > 0 && this->has_vertex_status() )
113  {
114  i0=0; i1=nV-1;
115 
116  while (1)
117  {
118  // find 1st deleted and last un-deleted
119  while (!status(VertexHandle(i0)).deleted() && i0 < i1) ++i0;
120  while ( status(VertexHandle(i1)).deleted() && i0 < i1) --i1;
121  if (i0 >= i1) break;
122 
123  // If we keep track of the vertex handles for updates,
124  // we need to have the opposite direction
125  if ( track_vhandles ) {
126  vertex_inverse_map[i1] = i0;
127  vertex_inverse_map[i0] = -1;
128  }
129 
130  // swap
131  std::swap(vertices_[i0], vertices_[i1]);
132  std::swap(vh_map[i0], vh_map[i1]);
133  vprops_swap(i0, i1);
134  };
135 
136  vertices_.resize(status(VertexHandle(i0)).deleted() ? i0 : i0+1);
137  vprops_resize(n_vertices());
138  }
139 
140 
141  // remove deleted edges
142  if (_e && n_edges() > 0 && this->has_edge_status() )
143  {
144  i0=0; i1=nE-1;
145 
146  while (1)
147  {
148  // find 1st deleted and last un-deleted
149  while (!status(EdgeHandle(i0)).deleted() && i0 < i1) ++i0;
150  while ( status(EdgeHandle(i1)).deleted() && i0 < i1) --i1;
151  if (i0 >= i1) break;
152 
153  // If we keep track of the vertex handles for updates,
154  // we need to have the opposite direction
155  if ( track_hhandles ) {
156  halfedge_inverse_map[2*i1] = 2 * i0;
157  halfedge_inverse_map[2*i0] = -1;
158 
159  halfedge_inverse_map[2*i1 + 1] = 2 * i0 + 1;
160  halfedge_inverse_map[2*i0 + 1] = -1;
161  }
162 
163  // swap
164  std::swap(edges_[i0], edges_[i1]);
165  std::swap(hh_map[2*i0], hh_map[2*i1]);
166  std::swap(hh_map[2*i0+1], hh_map[2*i1+1]);
167  eprops_swap(i0, i1);
168  hprops_swap(2*i0, 2*i1);
169  hprops_swap(2*i0+1, 2*i1+1);
170  };
171 
172  edges_.resize(status(EdgeHandle(i0)).deleted() ? i0 : i0+1);
173  eprops_resize(n_edges());
174  hprops_resize(n_halfedges());
175  }
176 
177 
178  // remove deleted faces
179  if (_f && n_faces() > 0 && this->has_face_status() )
180  {
181  i0=0; i1=nF-1;
182 
183  while (1)
184  {
185  // find 1st deleted and last un-deleted
186  while (!status(FaceHandle(i0)).deleted() && i0 < i1) ++i0;
187  while ( status(FaceHandle(i1)).deleted() && i0 < i1) --i1;
188  if (i0 >= i1) break;
189 
190  // If we keep track of the face handles for updates,
191  // we need to have the opposite direction
192  if ( track_fhandles ) {
193  face_inverse_map[i1] = i0;
194  face_inverse_map[i0] = -1;
195  }
196 
197  // swap
198  std::swap(faces_[i0], faces_[i1]);
199  std::swap(fh_map[i0], fh_map[i1]);
200  fprops_swap(i0, i1);
201  };
202 
203  faces_.resize(status(FaceHandle(i0)).deleted() ? i0 : i0+1);
204  fprops_resize(n_faces());
205  }
206 
207 
208  // update handles of vertices
209  if (_e)
210  {
211  KernelVertexIter v_it(vertices_begin()), v_end(vertices_end());
212  VertexHandle vh;
213 
214  for (; v_it!=v_end; ++v_it)
215  {
216  vh = handle(*v_it);
217  if (!is_isolated(vh))
218  {
219  set_halfedge_handle(vh, hh_map[halfedge_handle(vh).idx()]);
220  }
221  }
222  }
223 
224  HalfedgeHandle hh;
225  // update handles of halfedges
226  for (KernelEdgeIter e_it(edges_begin()); e_it != edges_end(); ++e_it)
227  {//in the first pass update the (half)edges vertices
228  hh = halfedge_handle(handle(*e_it), 0);
229  set_vertex_handle(hh, vh_map[to_vertex_handle(hh).idx()]);
230  hh = halfedge_handle(handle(*e_it), 1);
231  set_vertex_handle(hh, vh_map[to_vertex_handle(hh).idx()]);
232  }
233  for (KernelEdgeIter e_it(edges_begin()); e_it != edges_end(); ++e_it)
234  {//in the second pass update the connectivity of the (half)edges
235  hh = halfedge_handle(handle(*e_it), 0);
236  set_next_halfedge_handle(hh, hh_map[next_halfedge_handle(hh).idx()]);
237  if (!is_boundary(hh))
238  {
239  set_face_handle(hh, fh_map[face_handle(hh).idx()]);
240  }
241  hh = halfedge_handle(handle(*e_it), 1);
242  set_next_halfedge_handle(hh, hh_map[next_halfedge_handle(hh).idx()]);
243  if (!is_boundary(hh))
244  {
245  set_face_handle(hh, fh_map[face_handle(hh).idx()]);
246  }
247  }
248 
249  // update handles of faces
250  if (_e)
251  {
252  KernelFaceIter f_it(faces_begin()), f_end(faces_end());
253  FaceHandle fh;
254 
255  for (; f_it!=f_end; ++f_it)
256  {
257  fh = handle(*f_it);
258  set_halfedge_handle(fh, hh_map[halfedge_handle(fh).idx()]);
259  }
260  }
261 
262  const int vertexCount = int(vertices_.size());
263  const int halfedgeCount = int(edges_.size() * 2);
264  const int faceCount = int(faces_.size());
265 
266  // Update the vertex handles in the vertex handle vector
267  typename std_API_Container_VHandlePointer::iterator v_it(vh_to_update.begin()), v_it_end(vh_to_update.end());
268  for(; v_it != v_it_end; ++v_it)
269  {
270 
271  // Only changed vertices need to be considered
272  if ( (*v_it)->idx() != vh_map[(*v_it)->idx()].idx() ) {
273  *(*v_it) = VertexHandle(vertex_inverse_map[(*v_it)->idx()]);
274 
275  // Vertices above the vertex count have to be already mapped, or they are invalid now!
276  } else if ( ((*v_it)->idx() >= vertexCount) && (vertex_inverse_map.find((*v_it)->idx()) == vertex_inverse_map.end()) ) {
277  (*v_it)->invalidate();
278  }
279 
280  }
281 
282  // Update the halfedge handles in the halfedge handle vector
283  typename std_API_Container_HHandlePointer::iterator hh_it(hh_to_update.begin()), hh_it_end(hh_to_update.end());
284  for(; hh_it != hh_it_end; ++hh_it)
285  {
286  // Only changed faces need to be considered
287  if ( (*hh_it)->idx() != hh_map[(*hh_it)->idx()].idx() ) {
288  *(*hh_it) = HalfedgeHandle(halfedge_inverse_map[(*hh_it)->idx()]);
289 
290  // Vertices above the face count have to be already mapped, or they are invalid now!
291  } else if ( ((*hh_it)->idx() >= halfedgeCount) && (halfedge_inverse_map.find((*hh_it)->idx()) == halfedge_inverse_map.end()) ) {
292  (*hh_it)->invalidate();
293  }
294 
295  }
296 
297  // Update the face handles in the face handle vector
298  typename std_API_Container_FHandlePointer::iterator fh_it(fh_to_update.begin()), fh_it_end(fh_to_update.end());
299  for(; fh_it != fh_it_end; ++fh_it)
300  {
301 
302  // Only changed faces need to be considered
303  if ( (*fh_it)->idx() != fh_map[(*fh_it)->idx()].idx() ) {
304  *(*fh_it) = FaceHandle(face_inverse_map[(*fh_it)->idx()]);
305 
306  // Vertices above the face count have to be already mapped, or they are invalid now!
307  } else if ( ((*fh_it)->idx() >= faceCount) && (face_inverse_map.find((*fh_it)->idx()) == face_inverse_map.end()) ) {
308  (*fh_it)->invalidate();
309  }
310 
311  }
312 }
313 
314 }
315 
void vprops_resize(size_t _n) const
Resizes all vertex property vectors to the specified size.
Definition: BaseKernel.hh:693
Handle for a edge entity.
Definition: Handles.hh:139
const StatusInfo & status(VertexHandle _vh) const
Status Query API.
Definition: ArrayKernel.hh:506
Handle for a halfedge entity.
Definition: Handles.hh:132
Handle for a vertex entity.
Definition: Handles.hh:125
void garbage_collection(bool _v=true, bool _e=true, bool _f=true)
garbage collection
Definition: ArrayKernel.cc:172
void invalidate()
reset handle to be invalid
Definition: Handles.hh:82
bool is_boundary(HalfedgeHandle _heh) const
Is halfedge _heh a boundary halfedge (is its face handle invalid) ?
Definition: ArrayKernel.hh:403
Handle for a face entity.
Definition: Handles.hh:146