Developer Documentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
TopologyKernel.cc
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$ *
38  * $Date$ *
39  * $LastChangedBy$ *
40  * *
41 \*===========================================================================*/
42 
43 #ifndef NDEBUG
44 #include <iostream>
45 #endif
46 
47 #include <queue>
48 
49 #include "TopologyKernel.hh"
50 
51 namespace OpenVolumeMesh {
52 
53 // Initialize constants
54 const VertexHandle TopologyKernel::InvalidVertexHandle = VertexHandle(-1);
55 const EdgeHandle TopologyKernel::InvalidEdgeHandle = EdgeHandle(-1);
56 const HalfEdgeHandle TopologyKernel::InvalidHalfEdgeHandle = HalfEdgeHandle(-1);
57 const FaceHandle TopologyKernel::InvalidFaceHandle = FaceHandle(-1);
58 const HalfFaceHandle TopologyKernel::InvalidHalfFaceHandle = HalfFaceHandle(-1);
59 const CellHandle TopologyKernel::InvalidCellHandle = CellHandle(-1);
60 
61 TopologyKernel::TopologyKernel() :
62  n_vertices_(0u),
63  v_bottom_up_(true),
64  e_bottom_up_(true),
65  f_bottom_up_(true),
66  deferred_deletion(true),
67  fast_deletion(true)
68 {
69 }
70 
71 TopologyKernel::~TopologyKernel() {
72 }
73 
74 //========================================================================================
75 
77 
78  ++n_vertices_;
79  vertex_deleted_.push_back(false);
80 
81  // Create item for vertex bottom-up incidences
82  if(v_bottom_up_) {
83  outgoing_hes_per_vertex_.resize(n_vertices_);
84  }
85 
86  // Resize vertex props
87  resize_vprops(n_vertices_);
88 
89  // Return 0-indexed handle
90  return VertexHandle((int)(n_vertices_ - 1));
91 }
92 
93 //========================================================================================
94 
97  const VertexHandle& _toVertex,
98  bool _allowDuplicates) {
99 
100  // If the conditions are not fulfilled, assert will fail (instead
101  // of returning an invalid handle)
102  assert(_fromVertex.is_valid() && (size_t)_fromVertex.idx() < n_vertices());
103  assert(_toVertex.is_valid() && (size_t)_toVertex.idx() < n_vertices());
104 
105  // Test if edge does not exist, yet
106  if(!_allowDuplicates) {
107  if(v_bottom_up_) {
108 
109  assert((size_t)_fromVertex.idx() < outgoing_hes_per_vertex_.size());
110  std::vector<HalfEdgeHandle>& ohes = outgoing_hes_per_vertex_[_fromVertex.idx()];
111  for(std::vector<HalfEdgeHandle>::const_iterator he_it = ohes.begin(),
112  he_end = ohes.end(); he_it != he_end; ++he_it) {
113  if(halfedge(*he_it).to_vertex() == _toVertex) {
114  return edge_handle(*he_it);
115  }
116  }
117  } else {
118  for(size_t i = 0; i < edges_.size(); ++i) {
119  if(edge(EdgeHandle(i)).from_vertex() == _fromVertex && edge(EdgeHandle(i)).to_vertex() == _toVertex) {
120  return EdgeHandle(i);
121  } else if(edge(EdgeHandle(i)).from_vertex() == _toVertex && edge(EdgeHandle(i)).to_vertex() == _fromVertex) {
122  return EdgeHandle(i);
123  }
124  }
125  }
126  }
127 
128  // Create edge object
129  OpenVolumeMeshEdge e(_fromVertex, _toVertex);
130 
131  // Store edge locally
132  edges_.push_back(e);
133  edge_deleted_.push_back(false);
134 
135  // Resize props
137 
138  EdgeHandle eh((int)edges_.size()-1);
139 
140  // Update vertex bottom-up incidences
141  if(v_bottom_up_) {
142  assert((size_t)_fromVertex.idx() < outgoing_hes_per_vertex_.size());
143  assert((size_t)_toVertex.idx() < outgoing_hes_per_vertex_.size());
144 
145  outgoing_hes_per_vertex_[_fromVertex.idx()].push_back(halfedge_handle(eh, 0));
146  outgoing_hes_per_vertex_[_toVertex.idx()].push_back(halfedge_handle(eh, 1));
147  }
148 
149  // Create item for edge bottom-up incidences
150  if(e_bottom_up_) {
151  incident_hfs_per_he_.resize(n_halfedges());
152  }
153 
154  // Get handle of recently created edge
155  return eh;
156 }
157 
158 //========================================================================================
159 
161 FaceHandle TopologyKernel::add_face(const std::vector<HalfEdgeHandle>& _halfedges, bool _topologyCheck) {
162 
163 #ifndef NDEBUG
164  // Assert that halfedges are valid
165  for(std::vector<HalfEdgeHandle>::const_iterator it = _halfedges.begin(),
166  end = _halfedges.end(); it != end; ++it)
167  assert(it->is_valid() && (size_t)it->idx() < edges_.size() * 2u);
168 #endif
169 
170  // Perform topology check
171  if(_topologyCheck) {
172 
173  /*
174  * Test if halfedges are connected
175  *
176  * The test works as follows:
177  * For every edge in the parameter vector
178  * put all incident vertices into a
179  * set of either "from"-vertices or "to"-vertices,
180  * respectively.
181  * If and only if all edges are connected,
182  * then both sets are identical.
183  */
184 
185  std::set<VertexHandle> fromVertices;
186  std::set<VertexHandle> toVertices;
187 
188  for(std::vector<HalfEdgeHandle>::const_iterator it = _halfedges.begin(),
189  end = _halfedges.end(); it != end; ++it) {
190 
191  fromVertices.insert(halfedge(*it).from_vertex());
192  toVertices.insert(halfedge(*it).to_vertex());
193  }
194 
195  for(std::set<VertexHandle>::const_iterator v_it = fromVertices.begin(),
196  v_end = fromVertices.end(); v_it != v_end; ++v_it) {
197  if(toVertices.count(*v_it) != 1) {
198  // The situation here is different, the caller has requested a
199  // topology check and expects an invalid handle if the half-edges
200  // are not connected. Give him a message in debug mode.
201 #ifndef NDEBUG
202  std::cerr << "add_face(): The specified halfedges are not connected!" << std::endl;
203 #endif
204  return InvalidFaceHandle;
205  }
206  }
207 
208  // The halfedges are now guaranteed to be connected
209  }
210 
211  // Create face
212  OpenVolumeMeshFace face(_halfedges);
213 
214  faces_.push_back(face);
215  face_deleted_.push_back(false);
216 
217  // Get added face's handle
218  FaceHandle fh(faces_.size() - 1);
219 
220  // Resize props
222 
223  // Update edge bottom-up incidences
224  if(e_bottom_up_) {
225 
226  for(std::vector<HalfEdgeHandle>::const_iterator it = _halfedges.begin(),
227  end = _halfedges.end(); it != end; ++it) {
228 
229  assert((size_t)it->idx() < incident_hfs_per_he_.size());
230  assert((size_t)opposite_halfedge_handle(*it).idx() < incident_hfs_per_he_.size());
231 
232  incident_hfs_per_he_[it->idx()].push_back(halfface_handle(fh, 0));
233  incident_hfs_per_he_[opposite_halfedge_handle(*it).idx()].push_back(halfface_handle(fh, 1));
234  }
235  }
236 
237  // Create item for face bottom-up incidences
238  if(f_bottom_up_) {
239  incident_cell_per_hf_.resize(n_halffaces(), InvalidCellHandle);
240  }
241 
242  // Return handle of recently created face
243  return fh;
244 }
245 
246 //========================================================================================
247 
250 FaceHandle TopologyKernel::add_face(const std::vector<VertexHandle>& _vertices) {
251 
252 #ifndef NDEBUG
253  // Assert that all vertices have valid indices
254  for(std::vector<VertexHandle>::const_iterator it = _vertices.begin(),
255  end = _vertices.end(); it != end; ++it)
256  assert(it->is_valid() && (size_t)it->idx() < n_vertices());
257 #endif
258 
259  // Add edge for each pair of vertices
260  std::vector<HalfEdgeHandle> halfedges;
261  std::vector<VertexHandle>::const_iterator it = _vertices.begin();
262  std::vector<VertexHandle>::const_iterator end = _vertices.end();
263  for(; (it+1) != end; ++it) {
264  EdgeHandle e_idx = add_edge(*it, *(it+1));
265 
266  // Swap halfedge if edge already existed and
267  // has been initially defined in reverse orientation
268  int swap = 0;
269  if(edge(e_idx).to_vertex() == *it) swap = 1;
270 
271  halfedges.push_back(halfedge_handle(e_idx, swap));
272  }
273  EdgeHandle e_idx = add_edge(*it, *_vertices.begin());
274  int swap = 0;
275  if(edge(e_idx).to_vertex() == *it) swap = 1;
276  halfedges.push_back(halfedge_handle(e_idx, swap));
277 
278  // Add face
279 #ifndef NDEBUG
280  return add_face(halfedges, true);
281 #else
282  return add_face(halfedges, false);
283 #endif
284 }
285 
286 //========================================================================================
287 
288 void TopologyKernel::reorder_incident_halffaces(const EdgeHandle& _eh) {
289 
290  /* Put halffaces in clockwise order via the
291  * same cell property which now exists.
292  * Note, this only works for manifold configurations though.
293  * Proceed as follows: Pick one starting halfface. Assuming
294  * that all halfface normals point into the incident cell,
295  * we find the adjacent halfface within the incident cell
296  * along the considered halfedge. We set the found halfface
297  * to be the one to be processed next. If we reach an outside
298  * region, we try to go back from the starting halfface in reverse
299  * order. If the complex is properly connected (the pairwise
300  * intersection of two adjacent 3-dimensional cells is always
301  * a 2-dimensional entity, namely a facet), such an ordering
302  * always exists and will be found. If not, a correct order
303  * can not be given and, as a result, the related iterators
304  * will address the related entities in an arbitrary fashion.
305  */
306 
307  for(unsigned char s = 0; s <= 1; s++) {
308 
309  HalfEdgeHandle cur_he = halfedge_handle(_eh, s);
310  std::vector<HalfFaceHandle> new_halffaces;
311  HalfFaceHandle start_hf = InvalidHalfFaceHandle;
312  HalfFaceHandle cur_hf = InvalidHalfFaceHandle;
313 
314  // Start with one incident halfface and go into the first direction
315  assert((size_t)cur_he.idx() < incident_hfs_per_he_.size());
316 
317  if(incident_hfs_per_he_[cur_he.idx()].size() != 0) {
318 
319  // Get start halfface
320  cur_hf = *incident_hfs_per_he_[cur_he.idx()].begin();
321  start_hf = cur_hf;
322 
323  while(cur_hf != InvalidHalfFaceHandle) {
324 
325  // Add halfface
326  new_halffaces.push_back(cur_hf);
327 
328  // Go to next halfface
329  cur_hf = adjacent_halfface_in_cell(cur_hf, cur_he);
330 
331  if(cur_hf != InvalidHalfFaceHandle)
332  cur_hf = opposite_halfface_handle(cur_hf);
333 
334  // End when we're through
335  if(cur_hf == start_hf) break;
336  // if one of the faces of the cell was already incident to another cell we need this check
337  // to prevent running into an infinite loop.
338  if(std::find(new_halffaces.begin(), new_halffaces.end(), cur_hf) != new_halffaces.end()) break;
339  }
340 
341  // First direction has terminated
342  // If new_halffaces has the same size as old (unordered)
343  // vector of incident halffaces, we are done here
344  // If not, try the other way round
345  if(new_halffaces.size() != incident_hfs_per_he_[cur_he.idx()].size()) {
346 
347  // Get opposite of start halfface
348  cur_hf = start_hf;
349 
350  while(cur_hf != InvalidHalfFaceHandle) {
351 
352  cur_hf = opposite_halfface_handle(cur_hf);
353  cur_hf = adjacent_halfface_in_cell(cur_hf, cur_he);
354 
355  if(cur_hf == start_hf) break;
356 
357  if(cur_hf != InvalidHalfFaceHandle)
358  new_halffaces.insert(new_halffaces.begin(), cur_hf);
359  else break;
360  // if one of the faces of the cell was already incident to another cell we need this check
361  // to prevent running into an infinite loop.
362  if(std::find(new_halffaces.begin(), new_halffaces.end(), cur_hf) != new_halffaces.end()) break;
363  }
364  }
365 
366  // Everything worked just fine, set the new ordered vector
367  if(new_halffaces.size() == incident_hfs_per_he_[cur_he.idx()].size()) {
368  incident_hfs_per_he_[cur_he.idx()] = new_halffaces;
369  }
370  }
371  }
372 }
373 
374 //========================================================================================
375 
377 CellHandle TopologyKernel::add_cell(const std::vector<HalfFaceHandle>& _halffaces, bool _topologyCheck) {
378 
379 #ifndef NDEBUG
380  // Assert that halffaces have valid indices
381  for(std::vector<HalfFaceHandle>::const_iterator it = _halffaces.begin(),
382  end = _halffaces.end(); it != end; ++it)
383  assert(it->is_valid() && ((size_t)it->idx() < faces_.size() * 2u));
384 #endif
385 
386  // Perform topology check
387  if(_topologyCheck) {
388 
389  /*
390  * Test if all halffaces are connected and form a two-manifold
391  * => Cell is closed
392  *
393  * This test is simple: The number of involved half-edges has to be
394  * exactly twice the number of involved edges.
395  */
396 
397  std::set<HalfEdgeHandle> incidentHalfedges;
398  std::set<EdgeHandle> incidentEdges;
399 
400  for(std::vector<HalfFaceHandle>::const_iterator it = _halffaces.begin(),
401  end = _halffaces.end(); it != end; ++it) {
402 
403  OpenVolumeMeshFace hface = halfface(*it);
404  for(std::vector<HalfEdgeHandle>::const_iterator he_it = hface.halfedges().begin(),
405  he_end = hface.halfedges().end(); he_it != he_end; ++he_it) {
406  incidentHalfedges.insert(*he_it);
407  incidentEdges.insert(edge_handle(*he_it));
408  }
409  }
410 
411  if(incidentHalfedges.size() != (incidentEdges.size() * 2u)) {
412 #ifndef NDEBUG
413  std::cerr << "add_cell(): The specified half-faces are not connected!" << std::endl;
414 #endif
415  return InvalidCellHandle;
416  }
417 
418  // The halffaces are now guaranteed to form a two-manifold
419  }
420 
421  // Create new cell
422  OpenVolumeMeshCell cell(_halffaces);
423 
424  cells_.push_back(cell);
425  cell_deleted_.push_back(false);
426 
427  // Resize props
429 
430  CellHandle ch((int)cells_.size()-1);
431 
432  // Update face bottom-up incidences
433  if(f_bottom_up_) {
434 
435  std::set<EdgeHandle> cell_edges;
436  for(std::vector<HalfFaceHandle>::const_iterator it = _halffaces.begin(),
437  end = _halffaces.end(); it != end; ++it) {
438  assert((size_t)it->idx() < incident_cell_per_hf_.size());
439 
440 #ifndef NDEBUG
441  if(_topologyCheck) {
442  if(incident_cell_per_hf_[it->idx()] != InvalidCellHandle) {
443  // Shouldn't this situation be dealt with before adding the
444  // cell and return InvalidCellHandle in this case?
445  // Mike: Not if the user intends to add non-manifold
446  // configurations. Although, in this case, he should be
447  // warned about it.
448  std::cerr << "add_cell(): One of the specified half-faces is already incident to another cell!" << std::endl;
449  }
450  }
451 #endif
452 
453  // Overwrite incident cell for current half-face
454  incident_cell_per_hf_[it->idx()] = ch;
455 
456  // Collect all edges of cell
457  const std::vector<HalfEdgeHandle> hes = halfface(*it).halfedges();
458  for(std::vector<HalfEdgeHandle>::const_iterator he_it = hes.begin(),
459  he_end = hes.end(); he_it != he_end; ++he_it) {
460  cell_edges.insert(edge_handle(*he_it));
461  }
462  }
463 
464  if(e_bottom_up_) {
465 
466  // Try to reorder all half-faces w.r.t.
467  // their incident half-edges such that all
468  // half-faces are in cyclic order around
469  // a half-edge
470  for(std::set<EdgeHandle>::const_iterator e_it = cell_edges.begin(),
471  e_end = cell_edges.end(); e_it != e_end; ++e_it) {
472  reorder_incident_halffaces(*e_it);
473  }
474  }
475  }
476 
477  return ch;
478 }
479 
480 //========================================================================================
481 
483 void TopologyKernel::set_edge(const EdgeHandle& _eh, const VertexHandle& _fromVertex, const VertexHandle& _toVertex) {
484 
485  Edge& e = edge(_eh);
486 
487  // Update bottom-up entries
488  if(has_vertex_bottom_up_incidences()) {
489 
490  const VertexHandle& fv = e.from_vertex();
491  const VertexHandle& tv = e.to_vertex();
492 
493  const HalfEdgeHandle heh0 = halfedge_handle(_eh, 0);
494  const HalfEdgeHandle heh1 = halfedge_handle(_eh, 1);
495 
496  std::vector<HalfEdgeHandle>::iterator h_end =
497  std::remove(outgoing_hes_per_vertex_[fv.idx()].begin(), outgoing_hes_per_vertex_[fv.idx()].end(), heh0);
498  outgoing_hes_per_vertex_[fv.idx()].resize(h_end - outgoing_hes_per_vertex_[fv.idx()].begin());
499 
500  h_end = std::remove(outgoing_hes_per_vertex_[tv.idx()].begin(), outgoing_hes_per_vertex_[tv.idx()].end(), heh1);
501  outgoing_hes_per_vertex_[tv.idx()].resize(h_end - outgoing_hes_per_vertex_[tv.idx()].begin());
502 
503  outgoing_hes_per_vertex_[_fromVertex.idx()].push_back(heh0);
504  outgoing_hes_per_vertex_[_toVertex.idx()].push_back(heh1);
505  }
506 
507  e.set_from_vertex(_fromVertex);
508  e.set_to_vertex(_toVertex);
509 }
510 
511 //========================================================================================
512 
514 void TopologyKernel::set_face(const FaceHandle& _fh, const std::vector<HalfEdgeHandle>& _hes) {
515 
516  Face& f = face(_fh);
517 
518  if(has_edge_bottom_up_incidences()) {
519 
520  const HalfFaceHandle hf0 = halfface_handle(_fh, 0);
521  const HalfFaceHandle hf1 = halfface_handle(_fh, 1);
522 
523  const std::vector<HalfEdgeHandle>& hes = f.halfedges();
524 
525  for(std::vector<HalfEdgeHandle>::const_iterator he_it = hes.begin(),
526  he_end = hes.end(); he_it != he_end; ++he_it) {
527 
528  std::vector<HalfFaceHandle>::iterator h_end =
529  std::remove(incident_hfs_per_he_[he_it->idx()].begin(),
530  incident_hfs_per_he_[he_it->idx()].end(), hf0);
531  incident_hfs_per_he_[he_it->idx()].resize(h_end - incident_hfs_per_he_[he_it->idx()].begin());
532 
533  h_end = std::remove(incident_hfs_per_he_[opposite_halfedge_handle(*he_it).idx()].begin(),
534  incident_hfs_per_he_[opposite_halfedge_handle(*he_it).idx()].end(), hf1);
535  incident_hfs_per_he_[opposite_halfedge_handle(*he_it).idx()].resize(h_end - incident_hfs_per_he_[opposite_halfedge_handle(*he_it).idx()].begin());
536  }
537 
538  for(std::vector<HalfEdgeHandle>::const_iterator he_it = _hes.begin(),
539  he_end = _hes.end(); he_it != he_end; ++he_it) {
540 
541  incident_hfs_per_he_[he_it->idx()].push_back(hf0);
542  incident_hfs_per_he_[opposite_halfedge_handle(*he_it).idx()].push_back(hf1);
543  }
544 
545  // TODO: Reorder incident half-faces
546  }
547 
548  f.set_halfedges(_hes);
549 }
550 
551 //========================================================================================
552 
554 void TopologyKernel::set_cell(const CellHandle& _ch, const std::vector<HalfFaceHandle>& _hfs) {
555 
556  Cell& c = cell(_ch);
557 
558  if(has_face_bottom_up_incidences()) {
559 
560  const std::vector<HalfFaceHandle>& hfs = c.halffaces();
561  for(std::vector<HalfFaceHandle>::const_iterator hf_it = hfs.begin(),
562  hf_end = hfs.end(); hf_it != hf_end; ++hf_it) {
563 
564  incident_cell_per_hf_[*hf_it] = InvalidCellHandle;
565  }
566 
567  for(std::vector<HalfFaceHandle>::const_iterator hf_it = _hfs.begin(),
568  hf_end = _hfs.end(); hf_it != hf_end; ++hf_it) {
569 
570  incident_cell_per_hf_[*hf_it] = _ch;
571  }
572  }
573 
574  c.set_halffaces(_hfs);
575 }
576 
577 //========================================================================================
578 
592 
593  std::vector<VertexHandle> vs;
594  vs.push_back(_h);
595 
596  std::set<EdgeHandle> incidentEdges_s;
597  get_incident_edges(vs, incidentEdges_s);
598 
599  std::set<FaceHandle> incidentFaces_s;
600  get_incident_faces(incidentEdges_s, incidentFaces_s);
601 
602  std::set<CellHandle> incidentCells_s;
603  get_incident_cells(incidentFaces_s, incidentCells_s);
604 
605  // Delete cells
606  for(std::set<CellHandle>::const_reverse_iterator c_it = incidentCells_s.rbegin(),
607  c_end = incidentCells_s.rend(); c_it != c_end; ++c_it) {
608  delete_cell_core(*c_it);
609  }
610 
611  // Delete faces
612  for(std::set<FaceHandle>::const_reverse_iterator f_it = incidentFaces_s.rbegin(),
613  f_end = incidentFaces_s.rend(); f_it != f_end; ++f_it) {
614  delete_face_core(*f_it);
615  }
616 
617  // Delete edges
618  for(std::set<EdgeHandle>::const_reverse_iterator e_it = incidentEdges_s.rbegin(),
619  e_end = incidentEdges_s.rend(); e_it != e_end; ++e_it) {
620  delete_edge_core(*e_it);
621  }
622 
623  // Delete vertex
624  return delete_vertex_core(_h);
625 }
626 
627 //========================================================================================
628 
642 
643  std::vector<EdgeHandle> es;
644  es.push_back(_h);
645 
646  std::set<FaceHandle> incidentFaces_s;
647  get_incident_faces(es, incidentFaces_s);
648 
649  std::set<CellHandle> incidentCells_s;
650  get_incident_cells(incidentFaces_s, incidentCells_s);
651 
652  // Delete cells
653  for(std::set<CellHandle>::const_reverse_iterator c_it = incidentCells_s.rbegin(),
654  c_end = incidentCells_s.rend(); c_it != c_end; ++c_it) {
655  delete_cell_core(*c_it);
656  }
657 
658  // Delete faces
659  for(std::set<FaceHandle>::const_reverse_iterator f_it = incidentFaces_s.rbegin(),
660  f_end = incidentFaces_s.rend(); f_it != f_end; ++f_it) {
661  delete_face_core(*f_it);
662  }
663 
664  // Delete edge
665  return delete_edge_core(_h);
666 }
667 
668 //========================================================================================
669 
683 
684  std::vector<FaceHandle> fs;
685  fs.push_back(_h);
686 
687  std::set<CellHandle> incidentCells_s;
688  get_incident_cells(fs, incidentCells_s);
689 
690  // Delete cells
691  for(std::set<CellHandle>::const_reverse_iterator c_it = incidentCells_s.rbegin(),
692  c_end = incidentCells_s.rend(); c_it != c_end; ++c_it) {
693  delete_cell_core(*c_it);
694  }
695 
696  // Delete face
697  return delete_face_core(_h);
698 }
699 
700 //========================================================================================
701 
712 
713  return delete_cell_core(_h);
714 }
715 
720 {
721  if (!deferred_deletion_enabled())
722  return; // nothing todo
723 
724  deferred_deletion = false;
725 
726  for (unsigned int i = n_cells(); i > 0; --i)
727  if (is_deleted(CellHandle(i-1)))
728  {
729  cell_deleted_[i-1] = false;
731  }
732 
733  for (unsigned int i = n_faces(); i > 0; --i)
734  if (is_deleted(FaceHandle(i-1)))
735  {
736  face_deleted_[i-1] = false;
738  }
739 
740  for (unsigned int i = n_edges(); i > 0; --i)
741  if (is_deleted(EdgeHandle(i-1)))
742  {
743  edge_deleted_[i-1] = false;
745  }
746 
747  for (unsigned int i = n_vertices(); i > 0; --i)
748  if (is_deleted(VertexHandle(i-1)))
749  {
750  vertex_deleted_[i-1] = false;
752  }
753 
754 
755  deferred_deletion = true;
756 
757 }
758 
759 //========================================================================================
760 
761 template <class ContainerT>
762 void TopologyKernel::get_incident_edges(const ContainerT& _vs,
763  std::set<EdgeHandle>& _es) const {
764 
765  _es.clear();
766 
767  if(v_bottom_up_) {
768 
769  for(typename ContainerT::const_iterator v_it = _vs.begin(),
770  v_end = _vs.end(); v_it != v_end; ++v_it) {
771 
772  const std::vector<HalfEdgeHandle>& inc_hes = outgoing_hes_per_vertex_[v_it->idx()];
773 
774  for(std::vector<HalfEdgeHandle>::const_iterator he_it = inc_hes.begin(),
775  he_end = inc_hes.end(); he_it != he_end; ++he_it) {
776 
777  _es.insert(edge_handle(*he_it));
778  }
779  }
780  } else {
781 
782  for(typename ContainerT::const_iterator v_it = _vs.begin(),
783  v_end = _vs.end(); v_it != v_end; ++v_it) {
784 
785  for(EdgeIter e_it = edges_begin(), e_end = edges_end(); e_it != e_end; ++e_it) {
786 
787  const Edge& e = edge(*e_it);
788 
789  if(e.from_vertex() == *v_it || e.to_vertex() == *v_it) {
790  _es.insert(*e_it);
791  }
792  }
793  }
794  }
795 }
796 
797 //========================================================================================
798 
799 template <class ContainerT>
800 void TopologyKernel::get_incident_faces(const ContainerT& _es,
801  std::set<FaceHandle>& _fs) const {
802 
803  _fs.clear();
804 
805  if(e_bottom_up_) {
806 
807  for(typename ContainerT::const_iterator e_it = _es.begin(),
808  e_end = _es.end(); e_it != e_end; ++e_it) {
809 
810  for(HalfEdgeHalfFaceIter hehf_it = hehf_iter(halfedge_handle(*e_it, 0));
811  hehf_it.valid(); ++hehf_it) {
812 
813  const FaceHandle fh = face_handle(*hehf_it);
814 
815  if(_fs.count(fh) == 0) {
816  _fs.insert(fh);
817  }
818  }
819  }
820  } else {
821 
822  for(typename ContainerT::const_iterator e_it = _es.begin(),
823  e_end = _es.end(); e_it != e_end; ++e_it) {
824 
825  for(FaceIter f_it = faces_begin(),
826  f_end = faces_end(); f_it != f_end; ++f_it) {
827 
828  const std::vector<HalfEdgeHandle>& hes = face(*f_it).halfedges();
829 
830  for(std::vector<HalfEdgeHandle>::const_iterator he_it = hes.begin(),
831  he_end = hes.end(); he_it != he_end; ++he_it) {
832 
833  if(edge_handle(*he_it) == *e_it) {
834  _fs.insert(*f_it);
835  break;
836  }
837  }
838  }
839  }
840  }
841 }
842 
843 //========================================================================================
844 
845 template <class ContainerT>
846 void TopologyKernel::get_incident_cells(const ContainerT& _fs,
847  std::set<CellHandle>& _cs) const {
848 
849  _cs.clear();
850 
851  if(f_bottom_up_) {
852 
853  for(typename ContainerT::const_iterator f_it = _fs.begin(),
854  f_end = _fs.end(); f_it != f_end; ++f_it) {
855 
856  const HalfFaceHandle hfh0 = halfface_handle(*f_it, 0);
857  const HalfFaceHandle hfh1 = halfface_handle(*f_it, 1);
858 
859  const CellHandle c0 = incident_cell(hfh0);
860  const CellHandle c1 = incident_cell(hfh1);
861 
862  if(c0.is_valid()) _cs.insert(c0);
863  if(c1.is_valid()) _cs.insert(c1);
864  }
865  } else {
866 
867  for(typename ContainerT::const_iterator f_it = _fs.begin(),
868  f_end = _fs.end(); f_it != f_end; ++f_it) {
869 
870  for(CellIter c_it = cells_begin(), c_end = cells_end();
871  c_it != c_end; ++c_it) {
872 
873  const std::vector<HalfFaceHandle>& hfs = cell(*c_it).halffaces();
874 
875  for(std::vector<HalfFaceHandle>::const_iterator hf_it = hfs.begin(),
876  hf_end = hfs.end(); hf_it != hf_end; ++hf_it) {
877 
878  if(face_handle(*hf_it) == *f_it) {
879  _cs.insert(*c_it);
880  break;
881  }
882  }
883  }
884  }
885  }
886 }
887 
888 //========================================================================================
889 
908 
909  VertexHandle h = _h;
910  assert(h.is_valid() && (size_t)h.idx() < n_vertices());
911 
912  if (fast_deletion_enabled() && !deferred_deletion_enabled()) // for fast deletion swap handle with last not deleted vertex
913  {
914  VertexHandle last_undeleted_vertex = VertexHandle(n_vertices()-1);
915  assert(!vertex_deleted_[last_undeleted_vertex.idx()]);
916  swap_vertices(h, last_undeleted_vertex);
917  h = last_undeleted_vertex;
918  }
919 
920  if (deferred_deletion_enabled())
921  {
922  vertex_deleted_[h.idx()] = true;
923 // deleted_vertices_.push_back(h);
924 
925  // Iterator to next element in vertex list
926 // return (vertices_begin() + h.idx()+1);
927  return VertexIter(this, VertexHandle(h.idx()+1));
928  }
929  else
930  {
931  // 1)
932  if(v_bottom_up_) {
933 
934  // Decrease all vertex handles >= _h in all edge definitions
935  for(int i = h.idx(), end = n_vertices(); i < end; ++i) {
936  const std::vector<HalfEdgeHandle>& hes = outgoing_hes_per_vertex_[i];
937  for(std::vector<HalfEdgeHandle>::const_iterator he_it = hes.begin(),
938  he_end = hes.end(); he_it != he_end; ++he_it) {
939 
940  Edge& e = edge(edge_handle(*he_it));
941  if(e.from_vertex().idx() == i) {
942  e.set_from_vertex(VertexHandle(i-1));
943  }
944  if(e.to_vertex().idx() == i) {
945  e.set_to_vertex(VertexHandle(i-1));
946  }
947  }
948  }
949 
950  } else {
951 
952  // Iterate over all edges
953  for(EdgeIter e_it = edges_begin(), e_end = edges_end();
954  e_it != e_end; ++e_it) {
955 
956  // Decrease all vertex handles in edge definitions that are greater than _h
957  if(edge(*e_it).from_vertex() > h) {
958  edge(*e_it).set_from_vertex(VertexHandle(edge(*e_it).from_vertex().idx() - 1));
959  }
960  if(edge(*e_it).to_vertex() > h) {
961  edge(*e_it).set_to_vertex(VertexHandle(edge(*e_it).to_vertex().idx() - 1));
962  }
963  }
964  }
965 
966  // 2)
967 
968  if(v_bottom_up_) {
969  assert((size_t)h.idx() < outgoing_hes_per_vertex_.size());
970  outgoing_hes_per_vertex_.erase(outgoing_hes_per_vertex_.begin() + h.idx());
971  }
972 
973 
974  // 3)
975 
976  --n_vertices_;
977  vertex_deleted_.erase(vertex_deleted_.begin() + h.idx());
978 
979  // 4)
980 
981  vertex_deleted(h);
982 
983  // Iterator to next element in vertex list
984 // return (vertices_begin() + h.idx());
985  return VertexIter(this, h);
986 
987  }
988 }
989 
990 //========================================================================================
991 
1012 
1013  EdgeHandle h = _h;
1014 
1015  assert(h.is_valid() && (size_t)h.idx() < edges_.size());
1016 
1017  if (fast_deletion_enabled() && !deferred_deletion_enabled()) // for fast deletion swap handle with last one
1018  {
1019  EdgeHandle last_edge = EdgeHandle(edges_.size()-1);
1020  assert(!edge_deleted_[last_edge.idx()]);
1021  swap_edges(h, last_edge);
1022  h = last_edge;
1023  }
1024 
1025 
1026  // 1)
1027  if(v_bottom_up_) {
1028 
1029  VertexHandle v0 = edge(h).from_vertex();
1030  VertexHandle v1 = edge(h).to_vertex();
1031  assert(v0.is_valid() && (size_t)v0.idx() < outgoing_hes_per_vertex_.size());
1032  assert(v1.is_valid() && (size_t)v1.idx() < outgoing_hes_per_vertex_.size());
1033 
1034  outgoing_hes_per_vertex_[v0.idx()].erase(
1035  std::remove(outgoing_hes_per_vertex_[v0.idx()].begin(),
1036  outgoing_hes_per_vertex_[v0.idx()].end(),
1037  halfedge_handle(h, 0)),
1038  outgoing_hes_per_vertex_[v0.idx()].end());
1039 
1040  outgoing_hes_per_vertex_[v1.idx()].erase(
1041  std::remove(outgoing_hes_per_vertex_[v1.idx()].begin(),
1042  outgoing_hes_per_vertex_[v1.idx()].end(),
1043  halfedge_handle(h, 1)),
1044  outgoing_hes_per_vertex_[v1.idx()].end());
1045  }
1046 
1047  if (deferred_deletion_enabled())
1048  {
1049  edge_deleted_[h.idx()] = true;
1050 // deleted_edges_.push_back(h);
1051 
1052  // Return iterator to next element in list
1053 // return (edges_begin() + h.idx()+1);
1054  return EdgeIter(this, EdgeHandle(h.idx()+1));
1055  }
1056  else
1057  {
1058 
1059  if (!fast_deletion_enabled())
1060  {
1061  // 2)
1062  if(e_bottom_up_) {
1063 
1064  assert((size_t)halfedge_handle(h, 0).idx() < incident_hfs_per_he_.size());
1065 
1066  // Decrease all half-edge handles > he and
1067  // delete all half-edge handles == he in face definitions
1068  // Get all faces that need updates
1069  std::set<FaceHandle> update_faces;
1070  for(std::vector<std::vector<HalfFaceHandle> >::const_iterator iit =
1071  (incident_hfs_per_he_.begin() + halfedge_handle(h, 0).idx()),
1072  iit_end = incident_hfs_per_he_.end(); iit != iit_end; ++iit) {
1073  for(std::vector<HalfFaceHandle>::const_iterator it = iit->begin(),
1074  end = iit->end(); it != end; ++it) {
1075  update_faces.insert(face_handle(*it));
1076  }
1077  }
1078  // Update respective handles
1080  for(std::set<FaceHandle>::iterator f_it = update_faces.begin(),
1081  f_end = update_faces.end(); f_it != f_end; ++f_it) {
1082 
1083  std::vector<HalfEdgeHandle> hes = face(*f_it).halfedges();
1084 
1085  // Delete current half-edge from face's half-edge list
1086  hes.erase(std::remove(hes.begin(), hes.end(), halfedge_handle(h, 0)), hes.end());
1087  hes.erase(std::remove(hes.begin(), hes.end(), halfedge_handle(h, 1)), hes.end());
1088 
1089  #if defined(__clang_major__) && (__clang_major__ >= 5)
1090  for(std::vector<HalfEdgeHandle>::iterator it = hes.begin(), end = hes.end();
1091  it != end; ++it) {
1092  cor.correctValue(*it);
1093  }
1094  #else
1095  std::for_each(hes.begin(), hes.end(),
1096  fun::bind(&HEHandleCorrection::correctValue, &cor, fun::placeholders::_1));
1097  #endif
1098  face(*f_it).set_halfedges(hes);
1099  }
1100  } else {
1101 
1102  // Iterate over all faces
1103  for(FaceIter f_it = faces_begin(), f_end = faces_end();
1104  f_it != f_end; ++f_it) {
1105 
1106  // Get face's half-edges
1107  std::vector<HalfEdgeHandle> hes = face(*f_it).halfedges();
1108 
1109  // Delete current half-edge from face's half-edge list
1110  hes.erase(std::remove(hes.begin(), hes.end(), halfedge_handle(h, 0)), hes.end());
1111  hes.erase(std::remove(hes.begin(), hes.end(), halfedge_handle(h, 1)), hes.end());
1112 
1113  // Decrease all half-edge handles greater than _h in face
1115  #if defined(__clang_major__) && (__clang_major__ >= 5)
1116  for(std::vector<HalfEdgeHandle>::iterator it = hes.begin(), end = hes.end();
1117  it != end; ++it) {
1118  cor.correctValue(*it);
1119  }
1120  #else
1121  std::for_each(hes.begin(), hes.end(),
1122  fun::bind(&HEHandleCorrection::correctValue, &cor, fun::placeholders::_1));
1123  #endif
1124  face(*f_it).set_halfedges(hes);
1125  }
1126  }
1127  }
1128 
1129  // 3)
1130 
1131  if(e_bottom_up_) {
1132  assert((size_t)halfedge_handle(h, 1).idx() < incident_hfs_per_he_.size());
1133 
1134  incident_hfs_per_he_.erase(incident_hfs_per_he_.begin() + halfedge_handle(h, 1).idx());
1135  incident_hfs_per_he_.erase(incident_hfs_per_he_.begin() + halfedge_handle(h, 0).idx());
1136  }
1137 
1138  if (!fast_deletion_enabled())
1139  {
1140  // 4)
1141  if(v_bottom_up_) {
1143  #if defined(__clang_major__) && (__clang_major__ >= 5)
1144  for(std::vector<std::vector<HalfEdgeHandle> >::iterator it = outgoing_hes_per_vertex_.begin(),
1145  end = outgoing_hes_per_vertex_.end(); it != end; ++it) {
1146  cor.correctVecValue(*it);
1147  }
1148  #else
1149  std::for_each(outgoing_hes_per_vertex_.begin(),
1150  outgoing_hes_per_vertex_.end(),
1151  fun::bind(&HEHandleCorrection::correctVecValue, &cor, fun::placeholders::_1));
1152  #endif
1153  }
1154  }
1155 
1156 
1157  // 5)
1158  edges_.erase(edges_.begin() + h.idx());
1159  edge_deleted_.erase(edge_deleted_.begin() + h.idx());
1160 
1161 
1162  // 6)
1163 
1164  edge_deleted(h);
1165 
1166  // Return iterator to next element in list
1167 // return (edges_begin() + h.idx());
1168  return EdgeIter(this, h);
1169 
1170  }
1171 }
1172 
1173 //========================================================================================
1174 
1195 
1196  FaceHandle h = _h;
1197 
1198  assert(h.is_valid() && (size_t)h.idx() < faces_.size());
1199 
1200 
1201  if (fast_deletion_enabled() && !deferred_deletion_enabled()) // for fast deletion swap handle with last one
1202  {
1203  FaceHandle last_face = FaceHandle(faces_.size()-1);
1204  assert(!face_deleted_[last_face.idx()]);
1205  swap_faces(h, last_face);
1206  h = last_face;
1207  }
1208 
1209  // 1)
1210  if(e_bottom_up_) {
1211 
1212  const std::vector<HalfEdgeHandle>& hes = face(h).halfedges();
1213  for(std::vector<HalfEdgeHandle>::const_iterator he_it = hes.begin(),
1214  he_end = hes.end(); he_it != he_end; ++he_it) {
1215 
1216  assert((size_t)std::max(he_it->idx(), opposite_halfedge_handle(*he_it).idx()) < incident_hfs_per_he_.size());
1217 
1218  incident_hfs_per_he_[he_it->idx()].erase(
1219  std::remove(incident_hfs_per_he_[he_it->idx()].begin(),
1220  incident_hfs_per_he_[he_it->idx()].end(),
1221  halfface_handle(h, 0)), incident_hfs_per_he_[he_it->idx()].end());
1222 
1223 
1224  incident_hfs_per_he_[opposite_halfedge_handle(*he_it).idx()].erase(
1225  std::remove(incident_hfs_per_he_[opposite_halfedge_handle(*he_it).idx()].begin(),
1226  incident_hfs_per_he_[opposite_halfedge_handle(*he_it).idx()].end(),
1227  halfface_handle(h, 1)), incident_hfs_per_he_[opposite_halfedge_handle(*he_it).idx()].end());
1228  }
1229  }
1230 
1231  if (deferred_deletion_enabled())
1232  {
1233  face_deleted_[h.idx()] = true;
1234 // deleted_faces_.push_back(h);
1235 
1236  // Return iterator to next element in list
1237 // return (faces_begin() + h.idx()+1);
1238  return FaceIter(this, FaceHandle(h.idx()+1));
1239  }
1240  else
1241  {
1242 
1243  if (!fast_deletion_enabled())
1244  {
1245  // 2)
1246  if(f_bottom_up_) {
1247 
1248  // Decrease all half-face handles > _h in all cells
1249  // and delete all half-face handles == _h
1250  std::set<CellHandle> update_cells;
1251  for(std::vector<CellHandle>::const_iterator c_it = (incident_cell_per_hf_.begin() + halfface_handle(h, 0).idx()),
1252  c_end = incident_cell_per_hf_.end(); c_it != c_end; ++c_it) {
1253  if(!c_it->is_valid()) continue;
1254  update_cells.insert(*c_it);
1255  }
1256  for(std::set<CellHandle>::const_iterator c_it = update_cells.begin(),
1257  c_end = update_cells.end(); c_it != c_end; ++c_it) {
1258 
1259  std::vector<HalfFaceHandle> hfs = cell(*c_it).halffaces();
1260 
1261  // Delete current half-faces from cell's half-face list
1262  hfs.erase(std::remove(hfs.begin(), hfs.end(), halfface_handle(h, 0)), hfs.end());
1263  hfs.erase(std::remove(hfs.begin(), hfs.end(), halfface_handle(h, 1)), hfs.end());
1264 
1266 #if defined(__clang_major__) && (__clang_major__ >= 5)
1267  for(std::vector<HalfFaceHandle>::iterator it = hfs.begin(),
1268  end = hfs.end(); it != end; ++it) {
1269  cor.correctValue(*it);
1270  }
1271 #else
1272  std::for_each(hfs.begin(), hfs.end(),
1273  fun::bind(&HFHandleCorrection::correctValue, &cor, fun::placeholders::_1));
1274 #endif
1275  cell(*c_it).set_halffaces(hfs);
1276  }
1277 
1278  } else {
1279 
1280  // Iterate over all cells
1281  for(CellIter c_it = cells_begin(), c_end = cells_end(); c_it != c_end; ++c_it) {
1282 
1283  std::vector<HalfFaceHandle> hfs = cell(*c_it).halffaces();
1284 
1285  // Delete current half-faces from cell's half-face list
1286  hfs.erase(std::remove(hfs.begin(), hfs.end(), halfface_handle(h, 0)), hfs.end());
1287  hfs.erase(std::remove(hfs.begin(), hfs.end(), halfface_handle(h, 1)), hfs.end());
1288 
1290 #if defined(__clang_major__) && (__clang_major__ >= 5)
1291  for(std::vector<HalfFaceHandle>::iterator it = hfs.begin(),
1292  end = hfs.end(); it != end; ++it) {
1293  cor.correctValue(*it);
1294  }
1295 #else
1296  std::for_each(hfs.begin(), hfs.end(),
1297  fun::bind(&HFHandleCorrection::correctValue, &cor, fun::placeholders::_1));
1298 #endif
1299  cell(*c_it).set_halffaces(hfs);
1300  }
1301  }
1302  }
1303 
1304 
1305  // 3)
1306  if(f_bottom_up_) {
1307  assert((size_t)halfface_handle(h, 1).idx() < incident_cell_per_hf_.size());
1308 
1309  incident_cell_per_hf_.erase(incident_cell_per_hf_.begin() + halfface_handle(h, 1).idx());
1310  incident_cell_per_hf_.erase(incident_cell_per_hf_.begin() + halfface_handle(h, 0).idx());
1311  }
1312 
1313 
1314  if (!fast_deletion_enabled())
1315  {
1316  // 4)
1317  if(e_bottom_up_) {
1319 #if defined(__clang_major__) && (__clang_major__ >= 5)
1320  for(std::vector<std::vector<HalfFaceHandle> >::iterator it = incident_hfs_per_he_.begin(), end = incident_hfs_per_he_.end(); it != end; ++it) {
1321  cor.correctVecValue(*it);
1322  }
1323 #else
1324  std::for_each(incident_hfs_per_he_.begin(),
1325  incident_hfs_per_he_.end(),
1326  fun::bind(&HFHandleCorrection::correctVecValue, &cor, fun::placeholders::_1));
1327 #endif
1328  }
1329  }
1330 
1331  // 5)
1332  faces_.erase(faces_.begin() + h.idx());
1333  face_deleted_.erase(face_deleted_.begin() + h.idx());
1334 
1335  // 6)
1336  face_deleted(h);
1337 
1338  // Return iterator to next element in list
1339 // return (faces_begin() + h.idx());
1340  return FaceIter(this, h);
1341  }
1342 
1343 }
1344 
1345 //========================================================================================
1346 
1363 
1364  CellHandle h = _h;
1365 
1366  assert(h.is_valid() && (size_t)h.idx() < cells_.size());
1367 
1368 
1369  if (fast_deletion_enabled() && !deferred_deletion_enabled()) // for fast deletion swap handle with last not deleted cell
1370  {
1371  CellHandle last_undeleted_cell = CellHandle(cells_.size()-1);
1372  assert(!cell_deleted_[last_undeleted_cell.idx()]);
1373  swap_cells(h, last_undeleted_cell);
1374  h = last_undeleted_cell;
1375  }
1376 
1377 
1378  // 1)
1379  if(f_bottom_up_) {
1380  const std::vector<HalfFaceHandle>& hfs = cell(h).halffaces();
1381  for(std::vector<HalfFaceHandle>::const_iterator hf_it = hfs.begin(),
1382  hf_end = hfs.end(); hf_it != hf_end; ++hf_it) {
1383  assert((size_t)hf_it->idx() < incident_cell_per_hf_.size());
1384  if (incident_cell_per_hf_[hf_it->idx()] == h)
1385  incident_cell_per_hf_[hf_it->idx()] = InvalidCellHandle;
1386  }
1387  }
1388 
1389  if (deferred_deletion_enabled())
1390  {
1391  cell_deleted_[h.idx()] = true;
1392 // deleted_cells_.push_back(h);
1393 // deleted_cells_set.insert(h);
1394 
1395 // return (cells_begin() + h.idx()+1);
1396  return CellIter(this, CellHandle(h.idx()+1));
1397  }
1398  else
1399  {
1400  // 2)
1401  if (!fast_deletion_enabled())
1402  {
1403  if(f_bottom_up_) {
1404  CHandleCorrection cor(h);
1405 #if defined(__clang_major__) && (__clang_major__ >= 5)
1406  for(std::vector<CellHandle>::iterator it = incident_cell_per_hf_.begin(),
1407  end = incident_cell_per_hf_.end(); it != end; ++it) {
1408  cor.correctValue(*it);
1409  }
1410 #else
1411  std::for_each(incident_cell_per_hf_.begin(),
1412  incident_cell_per_hf_.end(),
1413  fun::bind(&CHandleCorrection::correctValue, &cor, fun::placeholders::_1));
1414 #endif
1415  }
1416  }
1417 
1418  // 3)
1419  cells_.erase(cells_.begin() + h.idx());
1420  cell_deleted_.erase(cell_deleted_.begin() + h.idx());
1421 
1422  // 4)
1423  cell_deleted(h);
1424 
1425  // return handle to original position
1426 // return (cells_begin() + h.idx()+1);
1427  return CellIter(this, h);
1428  }
1429 }
1430 
1431 void TopologyKernel::swap_cells(CellHandle _h1, CellHandle _h2)
1432 {
1433  assert(_h1.idx() >= 0 && _h1.idx() < (int)cells_.size());
1434  assert(_h2.idx() >= 0 && _h2.idx() < (int)cells_.size());
1435 
1436  if (_h1 == _h2)
1437  return;
1438 
1439  int id1 = _h1.idx();
1440  int id2 = _h2.idx();
1441 
1442  Cell c1 = cells_[id1];
1443  Cell c2 = cells_[id2];
1444 
1445  // correct pointers to those cells
1446  std::vector<HalfFaceHandle> hfhs1 = c1.halffaces();
1447  for (unsigned int i = 0; i < hfhs1.size(); ++i)
1448  {
1449  HalfFaceHandle hfh = hfhs1[i];
1450  if (incident_cell_per_hf_[hfh.idx()] == id1)
1451  incident_cell_per_hf_[hfh.idx()] = id2;
1452  }
1453 
1454  std::vector<HalfFaceHandle> hfhs2 = c2.halffaces();
1455  for (unsigned int i = 0; i < hfhs2.size(); ++i)
1456  {
1457  HalfFaceHandle hfh = hfhs2[i];
1458  if (incident_cell_per_hf_[hfh.idx()] == id2)
1459  incident_cell_per_hf_[hfh.idx()] = id1;
1460  }
1461 
1462  // swap vector entries
1463  std::swap(cells_[id1], cells_[id2]);
1464  bool tmp = cell_deleted_[id1];
1465  cell_deleted_[id1] = cell_deleted_[id2];
1466  cell_deleted_[id2] = tmp;
1467  swap_cell_properties(_h1, _h2);
1468 }
1469 
1470 void TopologyKernel::swap_faces(FaceHandle _h1, FaceHandle _h2)
1471 {
1472  assert(_h1.idx() >= 0 && _h1.idx() < (int)faces_.size());
1473  assert(_h2.idx() >= 0 && _h2.idx() < (int)faces_.size());
1474 
1475  if (_h1 == _h2)
1476  return;
1477 
1478 
1479  std::vector<unsigned int> ids;
1480  ids.push_back(_h1.idx());
1481  ids.push_back(_h2.idx());
1482 
1483  unsigned int id1 = _h1.idx();
1484  unsigned int id2 = _h2.idx();
1485 
1486  // correct pointers to those faces
1487 
1488  // correct cells that contain a swapped faces
1489  if (has_face_bottom_up_incidences())
1490  {
1491  std::set<unsigned int> processed_cells; // to ensure ids are only swapped once (in the case that the two swapped faces belong to a common cell)
1492  for (unsigned int i = 0; i < 2; ++i) // For both swapped faces
1493  {
1494  unsigned int id = ids[i];
1495  for (unsigned int j = 0; j < 2; ++j) // for both halffaces
1496  {
1497  HalfFaceHandle hfh = HalfFaceHandle(2*id+j);
1498  CellHandle ch = incident_cell_per_hf_[hfh];
1499  if (!ch.is_valid())
1500  continue;
1501 
1502 
1503 
1504  if (processed_cells.find(ch.idx()) == processed_cells.end())
1505  {
1506 
1507  Cell& c = cells_[ch.idx()];
1508 
1509  // replace old halffaces with new halffaces where the ids are swapped
1510 
1511  std::vector<HalfFaceHandle> new_halffaces;
1512  for (unsigned int k = 0; k < c.halffaces().size(); ++k)
1513  if (c.halffaces()[k].idx()/2 == (int)id1) // if halfface belongs to swapped face
1514  new_halffaces.push_back(HalfFaceHandle(2 * id2 + (c.halffaces()[k].idx() % 2)));
1515  else if (c.halffaces()[k].idx()/2 == (int)id2) // if halfface belongs to swapped face
1516  new_halffaces.push_back(HalfFaceHandle(2 * id1 + (c.halffaces()[k].idx() % 2)));
1517  else
1518  new_halffaces.push_back(c.halffaces()[k]);
1519  c.set_halffaces(new_halffaces);
1520 
1521  processed_cells.insert(ch.idx());
1522  }
1523  }
1524  }
1525  }
1526  else
1527  {
1528  // serach for all cells that contain a swapped face
1529  for (unsigned int i = 0; i < cells_.size(); ++i)
1530  {
1531  Cell& c = cells_[i];
1532 
1533  // check if c contains a swapped face
1534  bool contains_swapped_face = false;
1535  for (unsigned int k = 0; k < c.halffaces().size(); ++k)
1536  {
1537  if (c.halffaces()[k].idx()/2 == (int)id1)
1538  contains_swapped_face = true;
1539  if (c.halffaces()[k].idx()/2 == (int)id2)
1540  contains_swapped_face = true;
1541  if (contains_swapped_face)
1542  break;
1543  }
1544 
1545  if (contains_swapped_face)
1546  {
1547  // replace old halffaces with new halffaces where the ids are swapped
1548  std::vector<HalfFaceHandle> new_halffaces;
1549  for (unsigned int k = 0; k < c.halffaces().size(); ++k)
1550  if (c.halffaces()[k].idx()/2 == (int)id1) // if halfface belongs to swapped face
1551  new_halffaces.push_back(HalfFaceHandle(2 * id2 + (c.halffaces()[k].idx() % 2)));
1552  else if (c.halffaces()[k].idx()/2 == (int)id2) // if halfface belongs to swapped face
1553  new_halffaces.push_back(HalfFaceHandle(2 * id1 + (c.halffaces()[k].idx() % 2)));
1554  else
1555  new_halffaces.push_back(c.halffaces()[k]);
1556  c.set_halffaces(new_halffaces);
1557  }
1558  }
1559  }
1560 
1561  // correct bottom up indices
1562 
1563  if (has_edge_bottom_up_incidences())
1564  {
1565  std::set<unsigned int> processed_halfedges; // to ensure ids are only swapped once (in the case that a halfedge is incident to both swapped faces)
1566  for (unsigned int i = 0; i < 2; ++i) // For both swapped faces
1567  {
1568  unsigned int id = ids[i];
1569  for (unsigned int j = 0; j < 2; ++j) // for both halffaces
1570  {
1571  HalfFaceHandle hfh = HalfFaceHandle(2*id+j);
1572  Face hf = halfface(hfh);
1573 
1574  for (unsigned int k = 0; k < hf.halfedges().size(); ++k)
1575  {
1576  HalfEdgeHandle heh = hf.halfedges()[k];
1577 
1578  if (processed_halfedges.find(heh.idx()) != processed_halfedges.end())
1579  continue;
1580 
1581  std::vector<HalfFaceHandle>& incident_halffaces = incident_hfs_per_he_[heh.idx()];
1582  for (unsigned int l = 0; l < incident_halffaces.size(); ++l)
1583  {
1584  HalfFaceHandle& hfh2 = incident_halffaces[l];
1585 
1586  if (hfh2.idx()/2 == (int)id1) // if halfface belongs to swapped face
1587  hfh2 = HalfFaceHandle(2 * id2 + (hfh2.idx() % 2));
1588  else if (hfh2.idx()/2 == (int)id2) // if halfface belongs to swapped face
1589  hfh2 = HalfFaceHandle(2 * id1 + (hfh2.idx() % 2));
1590  }
1591 
1592  processed_halfedges.insert(heh);
1593  }
1594  }
1595  }
1596  }
1597 
1598  // swap vector entries
1599  std::swap(faces_[ids[0]], faces_[ids[1]]);
1600  bool tmp = face_deleted_[ids[0]];
1601  face_deleted_[ids[0]] = face_deleted_[ids[1]];
1602  face_deleted_[ids[1]] = tmp;
1603  std::swap(incident_cell_per_hf_[2*ids[0]+0], incident_cell_per_hf_[2*ids[1]+0]);
1604  std::swap(incident_cell_per_hf_[2*ids[0]+1], incident_cell_per_hf_[2*ids[1]+1]);
1605  swap_face_properties(_h1, _h2);
1606  swap_halfface_properties(halfface_handle(_h1, 0), halfface_handle(_h2, 0));
1607  swap_halfface_properties(halfface_handle(_h1, 1), halfface_handle(_h2, 1));
1608 
1609 }
1610 
1611 void TopologyKernel::swap_edges(EdgeHandle _h1, EdgeHandle _h2)
1612 {
1613  assert(_h1.idx() >= 0 && _h1.idx() < (int)edges_.size());
1614  assert(_h2.idx() >= 0 && _h2.idx() < (int)edges_.size());
1615 
1616  if (_h1 == _h2)
1617  return;
1618 
1619  std::vector<unsigned int> ids;
1620  ids.push_back(_h1.idx());
1621  ids.push_back(_h2.idx());
1622 
1623 
1624  // correct pointers to those edges
1625 
1626  if (has_edge_bottom_up_incidences())
1627  {
1628  std::set<unsigned int> processed_faces; // to ensure ids are only swapped once (in the case that the two swapped edges belong to a common face)
1629 
1630  for (unsigned int i = 0; i < 2; ++i) // For both swapped edges
1631  {
1632  HalfEdgeHandle heh = HalfEdgeHandle(2*ids[i]);
1633 
1634 
1635  std::vector<HalfFaceHandle>& incident_halffaces = incident_hfs_per_he_[heh.idx()];
1636  for (unsigned int j = 0; j < incident_halffaces.size(); ++j) // for each incident halfface
1637  {
1638  HalfFaceHandle hfh = incident_halffaces[j];
1639 
1640  unsigned int f_id = hfh.idx() / 2;
1641 
1642  if (processed_faces.find(f_id) == processed_faces.end())
1643  {
1644 
1645  Face& f = faces_[f_id];
1646 
1647  // replace old incident halfedges with new incident halfedges where the ids are swapped
1648  std::vector<HalfEdgeHandle> new_halfedges;
1649  for (unsigned int k = 0; k < f.halfedges().size(); ++k)
1650  {
1651  HalfEdgeHandle heh2 = f.halfedges()[k];
1652  if (heh2.idx() / 2 == (int)ids[0])
1653  new_halfedges.push_back(HalfEdgeHandle(2*ids[1] + (heh2.idx() % 2)));
1654  else if (heh2.idx() / 2 == (int)ids[1])
1655  new_halfedges.push_back(HalfEdgeHandle(2*ids[0] + (heh2.idx() % 2)));
1656  else
1657  new_halfedges.push_back(heh2);
1658  }
1659  f.set_halfedges(new_halfedges);
1660 
1661  processed_faces.insert(f_id);
1662  }
1663  }
1664  }
1665  }
1666  else
1667  {
1668  // search for all faces that contain one of the swapped edges
1669  for (unsigned int i = 0; i < faces_.size(); ++i)
1670  {
1671  Face& f = faces_[i];
1672 
1673  // check if f contains a swapped edge
1674  bool contains_swapped_edge = false;
1675  for (unsigned int k = 0; k < f.halfedges().size(); ++k)
1676  {
1677  if (f.halfedges()[k].idx()/2 == (int)ids[0])
1678  contains_swapped_edge = true;
1679  if (f.halfedges()[k].idx()/2 == (int)ids[1])
1680  contains_swapped_edge = true;
1681  if (contains_swapped_edge)
1682  break;
1683  }
1684 
1685  if (contains_swapped_edge)
1686  {
1687  // replace old incident halfedges with new incident halfedges where the ids are swapped
1688  std::vector<HalfEdgeHandle> new_halfedges;
1689  for (unsigned int k = 0; k < f.halfedges().size(); ++k)
1690  {
1691  HalfEdgeHandle heh2 = f.halfedges()[k];
1692  if (heh2.idx() / 2 == (int)ids[0])
1693  new_halfedges.push_back(HalfEdgeHandle(2*ids[1] + (heh2.idx() % 2)));
1694  else if (heh2.idx() / 2 == (int)ids[1])
1695  new_halfedges.push_back(HalfEdgeHandle(2*ids[0] + (heh2.idx() % 2)));
1696  else
1697  new_halfedges.push_back(heh2);
1698  }
1699  f.set_halfedges(new_halfedges);
1700  }
1701  }
1702  }
1703 
1704  // correct bottom up incidences
1705 
1706  if (has_vertex_bottom_up_incidences())
1707  {
1708  std::set<int> processed_vertices;
1709  for (unsigned int i = 0; i < 2; ++i) // For both swapped edges
1710  {
1711  Edge e = edge(EdgeHandle(ids[i]));
1712  std::vector<VertexHandle> vhs;
1713  vhs.push_back(e.from_vertex());
1714  vhs.push_back(e.to_vertex());
1715 
1716  for (unsigned int j = 0; j < 2; ++j) // for both incident vertices
1717  {
1718  if (processed_vertices.find(vhs[j].idx()) != processed_vertices.end())
1719  continue;
1720 
1721  std::vector<HalfEdgeHandle>& outgoing_hes = outgoing_hes_per_vertex_[vhs[j].idx()];
1722  for (unsigned int k = 0; k < outgoing_hes.size(); ++k)
1723  {
1724  HalfEdgeHandle& heh = outgoing_hes[k];
1725  if (heh.idx() / 2 == (int)ids[0])
1726  heh = HalfEdgeHandle(2 * ids[1] + (heh.idx() % 2));
1727  else if (heh.idx() / 2 == (int)ids[1])
1728  heh = HalfEdgeHandle(2 * ids[0] + (heh.idx() % 2));
1729  }
1730  processed_vertices.insert(vhs[j]);
1731  }
1732 
1733  }
1734  }
1735 
1736  // swap vector entries
1737  std::swap(edges_[ids[0]], edges_[ids[1]]);
1738  bool tmp = edge_deleted_[ids[0]];
1739  edge_deleted_[ids[0]] = edge_deleted_[ids[1]];
1740  edge_deleted_[ids[1]] = tmp;
1741  std::swap(incident_hfs_per_he_[2*ids[0]+0], incident_hfs_per_he_[2*ids[1]+0]);
1742  std::swap(incident_hfs_per_he_[2*ids[0]+1], incident_hfs_per_he_[2*ids[1]+1]);
1743  swap_edge_properties(_h1, _h2);
1744  swap_halfedge_properties(halfedge_handle(_h1, 0), halfedge_handle(_h2, 0));
1745  swap_halfedge_properties(halfedge_handle(_h1, 1), halfedge_handle(_h2, 1));
1746 
1747 }
1748 
1749 void TopologyKernel::swap_vertices(VertexHandle _h1, VertexHandle _h2)
1750 {
1751  assert(_h1.idx() >= 0 && _h1.idx() < (int)n_vertices_);
1752  assert(_h2.idx() >= 0 && _h2.idx() < (int)n_vertices_);
1753 
1754  if (_h1 == _h2)
1755  return;
1756 
1757  std::vector<unsigned int> ids;
1758  ids.push_back(_h1.idx());
1759  ids.push_back(_h2.idx());
1760 
1761 
1762  // correct pointers to those vertices
1763 
1764  if (has_vertex_bottom_up_incidences())
1765  {
1766  for (unsigned int i = 0; i < 2; ++i) // For both swapped vertices
1767  {
1768  std::set<unsigned int> processed_edges; // to ensure ids are only swapped once (in the case that the two swapped vertices are connected by an edge)
1769  std::vector<HalfEdgeHandle>& outgoing_hes = outgoing_hes_per_vertex_[ids[i]];
1770  for (unsigned int k = 0; k < outgoing_hes.size(); ++k) // for each outgoing halfedge
1771  {
1772  unsigned int e_id = outgoing_hes[k].idx() / 2;
1773 
1774  if (processed_edges.find(e_id) == processed_edges.end())
1775  {
1776  Edge& e = edges_[e_id];
1777  if (e.from_vertex() == (int)ids[0])
1778  e.set_from_vertex(VertexHandle(ids[1]));
1779  else if (e.from_vertex() == (int)ids[1])
1780  e.set_from_vertex(VertexHandle(ids[0]));
1781 
1782  if (e.to_vertex() == (int)ids[0])
1783  e.set_to_vertex(VertexHandle(ids[1]));
1784  else if (e.to_vertex() == (int)ids[1])
1785  e.set_to_vertex(VertexHandle(ids[0]));
1786 
1787  processed_edges.insert(e_id);
1788  }
1789  }
1790  }
1791 
1792  }
1793  else
1794  {
1795  // search for all edges containing a swapped vertex
1796 
1797  for (unsigned int i = 0; i < edges_.size(); ++i)
1798  {
1799  Edge& e = edges_[i];
1800  if (e.from_vertex() == (int)ids[0])
1801  e.set_from_vertex(VertexHandle(ids[1]));
1802  else if (e.from_vertex() == (int)ids[1])
1803  e.set_from_vertex(VertexHandle(ids[0]));
1804 
1805  if (e.to_vertex() == (int)ids[0])
1806  e.set_to_vertex(VertexHandle(ids[1]));
1807  else if (e.to_vertex() == (int)ids[1])
1808  e.set_to_vertex(VertexHandle(ids[0]));
1809  }
1810  }
1811 
1812  // swap vector entries
1813  bool tmp = vertex_deleted_[ids[0]];
1814  vertex_deleted_[ids[0]] = vertex_deleted_[ids[1]];
1815  vertex_deleted_[ids[1]] = tmp;
1816  std::swap(outgoing_hes_per_vertex_[ids[0]], outgoing_hes_per_vertex_[ids[1]]);
1817  swap_vertex_properties(_h1, _h2);
1818 }
1819 
1820 //========================================================================================
1821 
1822 void TopologyKernel::delete_multiple_vertices(const std::vector<bool>& _tag) {
1823 
1824  assert(_tag.size() == n_vertices());
1825 
1826  std::vector<int> newIndices(n_vertices(), -1);
1827  int curIdx = 0;
1828 
1829  std::vector<int>::iterator idx_it = newIndices.begin();
1830  for(std::vector<bool>::const_iterator t_it = _tag.begin(),
1831  t_end = _tag.end(); t_it != t_end; ++t_it, ++idx_it) {
1832 
1833  if(!(*t_it)) {
1834  // Not marked as deleted
1835  *idx_it = curIdx;
1836  ++curIdx;
1837  } else {
1838  --n_vertices_;
1839  }
1840  }
1841 
1842  // Delete properties accordingly
1843  delete_multiple_vertex_props(_tag);
1844 
1845  EdgeCorrector corrector(newIndices);
1846  std::for_each(edges_.begin(), edges_.end(), corrector);
1847 }
1848 
1849 //========================================================================================
1850 
1851 void TopologyKernel::delete_multiple_edges(const std::vector<bool>& _tag) {
1852 
1853  assert(_tag.size() == n_edges());
1854 
1855  std::vector<int> newIndices(n_edges(), -1);
1856  int curIdx = 0;
1857 
1858  std::vector<Edge> newEdges;
1859 
1860  std::vector<int>::iterator idx_it = newIndices.begin();
1861  std::vector<Edge>::const_iterator e_it = edges_.begin();
1862 
1863  for(std::vector<bool>::const_iterator t_it = _tag.begin(),
1864  t_end = _tag.end(); t_it != t_end; ++t_it, ++idx_it, ++e_it) {
1865 
1866  if(!(*t_it)) {
1867  // Not marked as deleted
1868 
1869  newEdges.push_back(*e_it);
1870 
1871  *idx_it = curIdx;
1872  ++curIdx;
1873  }
1874  }
1875 
1876  // Swap edges
1877  edges_.swap(newEdges);
1878 
1879  // Delete properties accordingly
1880  delete_multiple_edge_props(_tag);
1881 
1882  FaceCorrector corrector(newIndices);
1883  std::for_each(faces_.begin(), faces_.end(), corrector);
1884 }
1885 
1886 //========================================================================================
1887 
1888 void TopologyKernel::delete_multiple_faces(const std::vector<bool>& _tag) {
1889 
1890  assert(_tag.size() == n_faces());
1891 
1892  std::vector<int> newIndices(n_faces(), -1);
1893  int curIdx = 0;
1894 
1895  std::vector<Face> newFaces;
1896 
1897  std::vector<int>::iterator idx_it = newIndices.begin();
1898  std::vector<Face>::const_iterator f_it = faces_.begin();
1899 
1900  for(std::vector<bool>::const_iterator t_it = _tag.begin(),
1901  t_end = _tag.end(); t_it != t_end; ++t_it, ++idx_it, ++f_it) {
1902 
1903  if(!(*t_it)) {
1904  // Not marked as deleted
1905 
1906  newFaces.push_back(*f_it);
1907 
1908  *idx_it = curIdx;
1909  ++curIdx;
1910  }
1911  }
1912 
1913  // Swap faces
1914  faces_.swap(newFaces);
1915 
1916  // Delete properties accordingly
1917  delete_multiple_face_props(_tag);
1918 
1919  CellCorrector corrector(newIndices);
1920  std::for_each(cells_.begin(), cells_.end(), corrector);
1921 }
1922 
1923 //========================================================================================
1924 
1925 void TopologyKernel::delete_multiple_cells(const std::vector<bool>& _tag) {
1926 
1927  assert(_tag.size() == n_cells());
1928 
1929  std::vector<Cell> newCells;
1930 
1931  std::vector<Cell>::const_iterator c_it = cells_.begin();
1932 
1933  for(std::vector<bool>::const_iterator t_it = _tag.begin(),
1934  t_end = _tag.end(); t_it != t_end; ++t_it, ++c_it) {
1935 
1936  if(!(*t_it)) {
1937  // Not marked as deleted
1938 
1939  newCells.push_back(*c_it);
1940  }
1941  }
1942 
1943  // Swap cells
1944  cells_.swap(newCells);
1945 
1946  // Delete properties accordingly
1947  delete_multiple_cell_props(_tag);
1948 }
1949 
1950 //========================================================================================
1951 
1953 
1954  assert(_first >= cells_begin());
1955  assert(_last <= cells_end());
1956 
1957  std::vector<Cell>::iterator it = cells_.erase(cells_.begin() + _first->idx(), cells_.begin() + _last->idx());
1958 
1959  // Re-compute face bottom-up incidences if necessary
1960  if(f_bottom_up_) {
1961  f_bottom_up_ = false;
1962  enable_face_bottom_up_incidences(true);
1963  }
1964 
1965  return CellIter(this, CellHandle(it - cells_.begin()));
1966 }
1967 
1968 void TopologyKernel::enable_deferred_deletion(bool _enable)
1969 {
1970  if (deferred_deletion && !_enable)
1971  collect_garbage();
1972 
1973  deferred_deletion = _enable;
1974 }
1975 
1976 //========================================================================================
1977 
1979 const OpenVolumeMeshEdge& TopologyKernel::edge(const EdgeHandle& _edgeHandle) const {
1980 
1981  // Test if edge is valid
1982  assert(_edgeHandle.is_valid() && (size_t)_edgeHandle.idx() < edges_.size());
1983 
1984  return edges_[_edgeHandle.idx()];
1985 }
1986 
1987 //========================================================================================
1988 
1990 const OpenVolumeMeshFace& TopologyKernel::face(const FaceHandle& _faceHandle) const {
1991 
1992  // Test if face is valid
1993  assert(_faceHandle.is_valid() && (size_t)_faceHandle.idx() < faces_.size());
1994 
1995  return faces_[_faceHandle.idx()];
1996 }
1997 
1998 //========================================================================================
1999 
2001 const OpenVolumeMeshCell& TopologyKernel::cell(const CellHandle& _cellHandle) const {
2002 
2003  // Test if cell is valid
2004  assert(_cellHandle.is_valid() && (size_t)_cellHandle.idx() < cells_.size());
2005 
2006  return cells_[_cellHandle.idx()];
2007 }
2008 
2009 //========================================================================================
2010 
2013 
2014  // Test if edge is valid
2015  assert(_edgeHandle.is_valid() && (size_t)_edgeHandle.idx() < edges_.size());
2016 
2017  return edges_[_edgeHandle.idx()];
2018 }
2019 
2020 //========================================================================================
2021 
2024 
2025  // Test if face is valid
2026  assert((size_t)_faceHandle.idx() < faces_.size());
2027  assert(_faceHandle.idx() >= 0);
2028 
2029  return faces_[_faceHandle.idx()];
2030 }
2031 
2032 //========================================================================================
2033 
2036 
2037  // Test if cell is valid
2038  assert((size_t)_cellHandle.idx() < cells_.size());
2039  assert(_cellHandle.idx() >= 0);
2040 
2041  return cells_[_cellHandle.idx()];
2042 }
2043 
2044 //========================================================================================
2045 
2048 
2049  // Is handle in range?
2050  assert((size_t)_halfEdgeHandle.idx() < (edges_.size() * 2));
2051  assert(_halfEdgeHandle.idx() >= 0);
2052 
2053  // In case the handle is even, just return the corresponding edge
2055  if(_halfEdgeHandle.idx() % 2 == 0)
2056  return edges_[(int)(_halfEdgeHandle.idx() / 2)];
2057  else
2058  return opposite_halfedge(edges_[(int)(_halfEdgeHandle.idx() / 2)]);
2059 }
2060 
2061 //========================================================================================
2062 
2065 
2066  // Is handle in range?
2067  assert((size_t)_halfFaceHandle.idx() < (faces_.size() * 2));
2068  assert(_halfFaceHandle.idx() >= 0);
2069 
2070  // In case the handle is not even, just return the corresponding face
2071  // Otherwise return the opposite halfface via opposite()
2072  if(_halfFaceHandle.idx() % 2 == 0)
2073  return faces_[(int)(_halfFaceHandle.idx() / 2)];
2074  else
2075  return opposite_halfface(faces_[(int)(_halfFaceHandle.idx() / 2)]);
2076 }
2077 
2078 //========================================================================================
2079 
2082 
2083  // Is handle in range?
2084  assert(_halfEdgeHandle.idx() >= 0);
2085  assert((size_t)_halfEdgeHandle.idx() < (edges_.size() * 2));
2086 
2087  // In case the handle is not even, just return the corresponding edge
2088  // Otherwise return the opposite halfedge via opposite()
2089  if(_halfEdgeHandle.idx() % 2 != 0)
2090  return edges_[(int)(_halfEdgeHandle.idx() / 2)];
2091  else
2092  return opposite_halfedge(edges_[(int)(_halfEdgeHandle.idx() / 2)]);
2093 }
2094 
2095 //========================================================================================
2096 
2099 
2100  // Is handle in range?
2101  assert(_halfFaceHandle.idx() >= 0);
2102  assert((size_t)_halfFaceHandle.idx() < (faces_.size() * 2));
2103 
2104  // In case the handle is not even, just return the corresponding face
2105  // Otherwise return the opposite via the first face's opposite() function
2106  if(_halfFaceHandle.idx() % 2 != 0)
2107  return faces_[(int)(_halfFaceHandle.idx() / 2)];
2108  else
2109  return opposite_halfface(faces_[(int)(_halfFaceHandle.idx() / 2)]);
2110 }
2111 
2112 //========================================================================================
2113 
2115 
2116  assert(_vh1.idx() < (int)n_vertices());
2117  assert(_vh2.idx() < (int)n_vertices());
2118 
2119  for(VertexOHalfEdgeIter voh_it = voh_iter(_vh1); voh_it.valid(); ++voh_it) {
2120  if(halfedge(*voh_it).to_vertex() == _vh2) {
2121  return *voh_it;
2122  }
2123  }
2124 
2125  return InvalidHalfEdgeHandle;
2126 }
2127 
2128 //========================================================================================
2129 
2130 HalfFaceHandle TopologyKernel::halfface(const std::vector<VertexHandle>& _vs) const {
2131 
2132  assert(_vs.size() > 2);
2133 
2134  VertexHandle v0 = _vs[0], v1 = _vs[1], v2 = _vs[2];
2135 
2136  assert(v0.is_valid() && v1.is_valid() && v2.is_valid());
2137 
2138  HalfEdgeHandle he0 = halfedge(v0, v1);
2139  if(!he0.is_valid()) return InvalidHalfFaceHandle;
2140  HalfEdgeHandle he1 = halfedge(v1, v2);
2141  if(!he1.is_valid()) return InvalidHalfFaceHandle;
2142 
2143  std::vector<HalfEdgeHandle> hes;
2144  hes.push_back(he0);
2145  hes.push_back(he1);
2146 
2147  return halfface(hes);
2148 }
2149 
2150 HalfFaceHandle TopologyKernel::halfface_extensive(const std::vector<VertexHandle>& _vs) const
2151 {
2152  //TODO: schöner machen
2153 
2154  assert(_vs.size() > 2);
2155 
2156  VertexHandle v0 = _vs[0];
2157  VertexHandle v1 = _vs[1];
2158 
2159  assert(v0.is_valid() && v1.is_valid());
2160 
2161  HalfEdgeHandle he0 = halfedge(v0, v1);
2162  if(!he0.is_valid()) return InvalidHalfFaceHandle;
2163 
2164  for(HalfEdgeHalfFaceIter hehf_it = hehf_iter(he0); hehf_it.valid(); ++hehf_it)
2165  {
2166  std::vector<HalfEdgeHandle> hes = halfface(*hehf_it).halfedges();
2167 
2168  if (hes.size() != _vs.size())
2169  continue;
2170 
2171  int offset = 0;
2172  for (unsigned int i = 0; i < hes.size(); ++i)
2173  if (hes[i] == he0)
2174  offset = i;
2175 
2176  bool all_vertices_found = true;
2177 
2178  for (unsigned int i = 0; i < hes.size(); ++i)
2179  {
2180  HalfEdgeHandle heh = hes[(i+offset)%hes.size()];
2181  if (halfedge(heh).from_vertex() != _vs[i])
2182  {
2183  all_vertices_found = false;
2184  break;
2185  }
2186  }
2187 
2188  if (all_vertices_found)
2189  return *hehf_it;
2190  }
2191 
2192  return InvalidHalfFaceHandle;
2193 }
2194 
2195 //========================================================================================
2196 
2197 HalfFaceHandle TopologyKernel::halfface(const std::vector<HalfEdgeHandle>& _hes) const {
2198 
2199  assert(_hes.size() >= 2);
2200 
2201  HalfEdgeHandle he0 = _hes[0], he1 = _hes[1];
2202 
2203  assert(he0.is_valid() && he1.is_valid());
2204 
2205  for(HalfEdgeHalfFaceIter hehf_it = hehf_iter(he0); hehf_it.valid(); ++hehf_it) {
2206 
2207  std::vector<HalfEdgeHandle> hes = halfface(*hehf_it).halfedges();
2208  if(std::find(hes.begin(), hes.end(), he1) != hes.end()) {
2209  return *hehf_it;
2210  }
2211  }
2212 
2213  return InvalidHalfFaceHandle;
2214 }
2215 
2216 //========================================================================================
2217 
2219 
2220  assert(_heh.is_valid() && (size_t)_heh.idx() < edges_.size() * 2u);
2221  assert(_hfh.is_valid() && (size_t)_hfh.idx() < faces_.size() * 2u);
2222 
2223  std::vector<HalfEdgeHandle> hes = halfface(_hfh).halfedges();
2224 
2225  for(std::vector<HalfEdgeHandle>::const_iterator it = hes.begin();
2226  it != hes.end(); ++it) {
2227  if(*it == _heh) {
2228  if((it + 1) != hes.end()) return *(it + 1);
2229  else return *hes.begin();
2230  }
2231  }
2232 
2233  return InvalidHalfEdgeHandle;
2234 }
2235 
2236 //========================================================================================
2237 
2239 
2240  assert(_heh.is_valid() && (size_t)_heh.idx() < edges_.size() * 2u);
2241  assert(_hfh.is_valid() && (size_t)_hfh.idx() < faces_.size() * 2u);
2242 
2243  std::vector<HalfEdgeHandle> hes = halfface(_hfh).halfedges();
2244 
2245  for(std::vector<HalfEdgeHandle>::const_iterator it = hes.begin();
2246  it != hes.end(); ++it) {
2247  if(*it == _heh) {
2248  if(it != hes.begin()) return *(it - 1);
2249  else return *(hes.end() - 1);
2250  }
2251  }
2252 
2253  return InvalidHalfEdgeHandle;
2254 }
2255 
2256 //========================================================================================
2257 
2259 TopologyKernel::adjacent_halfface_in_cell(const HalfFaceHandle& _halfFaceHandle, const HalfEdgeHandle& _halfEdgeHandle) const {
2260 
2261  assert(_halfFaceHandle.is_valid() && (size_t)_halfFaceHandle.idx() < faces_.size() * 2u);
2262  assert(_halfEdgeHandle.is_valid() && (size_t)_halfEdgeHandle.idx() < edges_.size() * 2u);
2263  assert(has_face_bottom_up_incidences());
2264  assert((size_t)_halfFaceHandle.idx() < incident_cell_per_hf_.size());
2265 
2266  if(incident_cell_per_hf_[_halfFaceHandle.idx()] == InvalidCellHandle) {
2267  // Specified halfface is on the outside of the complex
2268  return InvalidHalfFaceHandle;
2269  }
2270 
2271  OpenVolumeMeshCell c = cell(incident_cell_per_hf_[_halfFaceHandle.idx()]);
2272 
2273  // Make sure that _halfFaceHandle is incident to _halfEdgeHandle
2274  bool skipped = false;
2275  bool found = false;
2276  HalfFaceHandle idx = InvalidHalfFaceHandle;
2277  for(std::vector<HalfFaceHandle>::const_iterator hf_it = c.halffaces().begin();
2278  hf_it != c.halffaces().end(); ++hf_it) {
2279 
2280  if(*hf_it == _halfFaceHandle) {
2281  skipped = true;
2282  continue;
2283  }
2284 
2285  OpenVolumeMeshFace hf = halfface(*hf_it);
2286  for(std::vector<HalfEdgeHandle>::const_iterator he_it = hf.halfedges().begin();
2287  he_it != hf.halfedges().end(); ++he_it) {
2288 
2289  if(edge_handle(*he_it) == edge_handle(_halfEdgeHandle)) {
2290  found = true;
2291  idx = *hf_it;
2292  }
2293  if(skipped && found) break;
2294  }
2295  if(skipped && found) break;
2296  }
2297  return ((skipped && found) ? idx : InvalidHalfFaceHandle);
2298 }
2299 
2300 //========================================================================================
2301 
2303 
2304  if(!has_face_bottom_up_incidences()) {
2305  return InvalidCellHandle;
2306  }
2307  if((size_t)_halfFaceHandle.idx() >= incident_cell_per_hf_.size() || _halfFaceHandle.idx() < 0) {
2308  return InvalidCellHandle;
2309  }
2310 
2311  return incident_cell_per_hf_[_halfFaceHandle.idx()];
2312 }
2313 
2314 //========================================================================================
2315 
2316 void TopologyKernel::compute_vertex_bottom_up_incidences() {
2317 
2318  // Clear incidences
2319  outgoing_hes_per_vertex_.clear();
2320  outgoing_hes_per_vertex_.resize(n_vertices());
2321 
2322  // Store outgoing halfedges per vertex
2323  size_t n_edges = edges_.size();
2324  for(size_t i = 0; i < n_edges; ++i) {
2325  if (edge_deleted_[i])
2326  continue;
2327 
2328  VertexHandle from = edges_[i].from_vertex();
2329  // If this condition is not fulfilled, it is out of caller's control and
2330  // definitely our bug, therefore an assert
2331  assert((size_t)from.idx() < outgoing_hes_per_vertex_.size());
2332 
2333  outgoing_hes_per_vertex_[from.idx()].push_back(halfedge_handle(EdgeHandle(i), 0));
2334 
2335  VertexHandle to = edges_[i].to_vertex();
2336  assert((size_t)to.idx() < outgoing_hes_per_vertex_.size());
2337 
2338  // Store opposite halfedge handle
2339  outgoing_hes_per_vertex_[to.idx()].push_back(halfedge_handle(EdgeHandle(i), 1));
2340  }
2341 }
2342 
2343 //========================================================================================
2344 
2345 void TopologyKernel::compute_edge_bottom_up_incidences() {
2346 
2347  // Clear
2348  incident_hfs_per_he_.clear();
2349  incident_hfs_per_he_.resize(edges_.size() * 2u);
2350 
2351  // Store incident halffaces per halfedge
2352  size_t n_faces = faces_.size();
2353  for(size_t i = 0; i < n_faces; ++i) {
2354  if (face_deleted_[i])
2355  continue;
2356 
2357  std::vector<HalfEdgeHandle> halfedges = faces_[i].halfedges();
2358 
2359  // Go over all halfedges
2360  for(std::vector<HalfEdgeHandle>::const_iterator he_it = halfedges.begin();
2361  he_it != halfedges.end(); ++he_it) {
2362 
2363  incident_hfs_per_he_[he_it->idx()].push_back(halfface_handle(FaceHandle(i), 0));
2364  incident_hfs_per_he_[opposite_halfedge_handle(*he_it).idx()].push_back(
2365  halfface_handle(FaceHandle(i), 1));
2366  }
2367  }
2368 }
2369 
2370 //========================================================================================
2371 
2372 void TopologyKernel::compute_face_bottom_up_incidences() {
2373 
2374  // Clear
2375  incident_cell_per_hf_.clear();
2376  incident_cell_per_hf_.resize(faces_.size() * 2u, InvalidCellHandle);
2377 
2378  size_t n_cells = cells_.size();
2379  for(size_t i = 0; i < n_cells; ++i) {
2380  if (cell_deleted_[i])
2381  continue;
2382 
2383  std::vector<HalfFaceHandle> halffaces = cells_[i].halffaces();
2384 
2385  // Go over all halffaces
2386  for(std::vector<HalfFaceHandle>::const_iterator hf_it = halffaces.begin();
2387  hf_it != halffaces.end(); ++hf_it) {
2388 
2389  if(incident_cell_per_hf_[hf_it->idx()] == InvalidCellHandle) {
2390 
2391  incident_cell_per_hf_[hf_it->idx()] = CellHandle(i);
2392 
2393  } else {
2394 
2395 #ifndef NDEBUG
2396  std::cerr << "compute_face_bottom_up_incidences(): Detected non-three-manifold configuration!" << std::endl;
2397  std::cerr << "Connectivity probably won't work." << std::endl;
2398 #endif
2399  continue;
2400  }
2401  }
2402  }
2403 }
2404 
2405 } // Namespace OpenVolumeMesh
void set_cell(const CellHandle &_ch, const std::vector< HalfFaceHandle > &_hfs)
Set the half-faces of a cell.
virtual size_t n_cells() const
Get number of cells in mesh.
HalfFaceHandle adjacent_halfface_in_cell(const HalfFaceHandle &_halfFaceHandle, const HalfEdgeHandle &_halfEdgeHandle) const
Get halfface that is adjacent (w.r.t. a common halfedge) within the same cell.
FaceIter delete_face_core(const FaceHandle &_h)
Delete face from mesh.
virtual VertexHandle add_vertex()
Add abstract vertex.
const Face & face(const FaceHandle &_faceHandle) const
Get face with handle _faceHandle.
void resize_cprops(size_t _nc)
Change size of stored cell properties.
Edge halfedge(const HalfEdgeHandle &_halfEdgeHandle) const
Get edge that corresponds to halfedge with handle _halfEdgeHandle.
virtual size_t n_vertices() const
Get number of vertices in mesh.
virtual EdgeHandle add_edge(const VertexHandle &_fromVertex, const VertexHandle &_toHandle, bool _allowDuplicates=false)
Add edge.
void resize_eprops(size_t _ne)
Change size of stored edge properties.
virtual CellIter delete_cell(const CellHandle &_h)
Delete cell from mesh.
CellHandle incident_cell(const HalfFaceHandle &_halfFaceHandle) const
Get cell that is incident to the given halfface.
virtual void collect_garbage()
Delete all entities that are marked as deleted.
virtual CellHandle add_cell(const std::vector< HalfFaceHandle > &_halffaces, bool _topologyCheck=false)
Add cell via incident halffaces.
EdgeIter delete_edge_core(const EdgeHandle &_h)
Delete edge from mesh.
CellIter delete_cell_range(const CellIter &_first, const CellIter &_last)
Delete range of cells.
const Cell & cell(const CellHandle &_cellHandle) const
Get cell with handle _cellHandle.
Face halfface(const HalfFaceHandle &_halfFaceHandle) const
Get face that corresponds to halfface with handle _halfFaceHandle.
const Edge & edge(const EdgeHandle &_edgeHandle) const
Get edge with handle _edgeHandle.
virtual size_t n_edges() const
Get number of edges in mesh.
virtual EdgeIter delete_edge(const EdgeHandle &_h)
Delete edge from mesh.
static HalfEdgeHandle halfedge_handle(const EdgeHandle &_h, const unsigned char _subIdx)
Conversion function.
HalfEdgeHandle prev_halfedge_in_halfface(const HalfEdgeHandle &_heh, const HalfFaceHandle &_hfh) const
Get previous halfedge within a halfface.
HalfFaceHandle halfface_extensive(const std::vector< VertexHandle > &_vs) const
void set_face(const FaceHandle &_fh, const std::vector< HalfEdgeHandle > &_hes)
Set the half-edges of a face.
static HalfFaceHandle halfface_handle(const FaceHandle &_h, const unsigned char _subIdx)
Conversion function.
static EdgeHandle edge_handle(const HalfEdgeHandle &_h)
Handle conversion.
Face opposite_halfface(const HalfFaceHandle &_halfFaceHandle) const
Get opposite halfface that corresponds to halfface with handle _halfFaceHandle.
virtual FaceHandle add_face(const std::vector< HalfEdgeHandle > &_halfedges, bool _topologyCheck=false)
Add face via incident edges.
virtual FaceIter delete_face(const FaceHandle &_h)
Delete face from mesh.
void resize_fprops(size_t _nf)
Change size of stored face properties.
HalfEdgeHandle next_halfedge_in_halfface(const HalfEdgeHandle &_heh, const HalfFaceHandle &_hfh) const
Get next halfedge within a halfface.
void set_edge(const EdgeHandle &_eh, const VertexHandle &_fromVertex, const VertexHandle &_toVertex)
Set the vertices of an edge.
bool bind(osg::GeometryPtr &_geo, Mesh &_mesh)
Definition: bindT.hh:106
CellIter delete_cell_core(const CellHandle &_h)
Delete cell from mesh.
virtual size_t n_halffaces() const
Get number of halffaces in mesh.
Edge opposite_halfedge(const HalfEdgeHandle &_halfEdgeHandle) const
Get opposite halfedge that corresponds to halfedge with handle _halfEdgeHandle.
virtual VertexIter delete_vertex(const VertexHandle &_h)
Delete vertex from mesh.
VertexIter delete_vertex_core(const VertexHandle &_h)
Delete vertex from mesh.
void resize_vprops(size_t _nv)
Change size of stored vertex properties.
virtual size_t n_faces() const
Get number of faces in mesh.
virtual size_t n_halfedges() const
Get number of halfedges in mesh.