Developer Documentation
TetrahedralMeshTopologyKernel.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 #include "TetrahedralMeshTopologyKernel.hh"
44 
45 #include <iostream>
46 
47 namespace OpenVolumeMesh {
48 
49 
50 TetrahedralMeshTopologyKernel::TetrahedralMeshTopologyKernel() {
51 
52 }
53 
54 //========================================================================================
55 
56 
57 TetrahedralMeshTopologyKernel::~TetrahedralMeshTopologyKernel() {
58 
59 }
60 
61 //========================================================================================
62 
63 
64 FaceHandle TetrahedralMeshTopologyKernel::add_face(const std::vector<HalfEdgeHandle>& _halfedges, bool _topologyCheck) {
65 
66  if(_halfedges.size() != 3) {
67 #ifndef NDEBUG
68  std::cerr << "TetrahedralMeshTopologyKernel::add_face(): Face valence is not three! Returning" << std::endl;
69  std::cerr << "invalid handle." << std::endl;
70 #endif
71  return TopologyKernel::InvalidFaceHandle;
72  }
73 
74  return TopologyKernel::add_face(_halfedges, _topologyCheck);
75 }
76 
77 //========================================================================================
78 
79 
81 TetrahedralMeshTopologyKernel::add_face(const std::vector<VertexHandle>& _vertices) {
82 
83  if(_vertices.size() != 3) {
84 #ifndef NDEBUG
85  std::cerr << "TetrahedralMeshTopologyKernel::add_face(): Face valence is not three! Returning" << std::endl;
86  std::cerr << "invalid handle." << std::endl;
87 #endif
88  return TopologyKernel::InvalidFaceHandle;
89  }
90 
91  return TopologyKernel::add_face(_vertices);
92 }
93 
94 //========================================================================================
95 
96 
98 TetrahedralMeshTopologyKernel::add_cell(const std::vector<HalfFaceHandle>& _halffaces, bool _topologyCheck) {
99 
100  if(_halffaces.size() != 4) {
101 // To make this consistent with add_face
102 #ifndef NDEBUG
103  std::cerr << "Cell valence is not four! Aborting." << std::endl;
104 #endif
105  return TopologyKernel::InvalidCellHandle;
106  }
107  for(std::vector<HalfFaceHandle>::const_iterator it = _halffaces.begin();
108  it != _halffaces.end(); ++it) {
109  if(TopologyKernel::halfface(*it).halfedges().size() != 3) {
110 #ifndef NDEBUG
111  std::cerr << "Incident face does not have valence three! Aborting." << std::endl;
112 #endif
113  return TopologyKernel::InvalidCellHandle;
114  }
115  }
116 
117  return TopologyKernel::add_cell(_halffaces, _topologyCheck);
118 }
119 
120 
121 HalfEdgeHandle TetrahedralMeshTopologyKernel::add_halfedge(const VertexHandle& _fromVertex, const VertexHandle& _toVertex)
122 {
123  HalfEdgeHandle he = halfedge(_fromVertex, _toVertex);
124  if (he != InvalidHalfEdgeHandle)
125  return he;
126  else
127  return halfedge_handle(add_edge(_fromVertex, _toVertex), 0);
128 }
129 
130 HalfFaceHandle TetrahedralMeshTopologyKernel::add_halfface(const std::vector<HalfEdgeHandle>& _halfedges, bool _topologyCheck)
131 {
132  HalfFaceHandle hf = halfface(_halfedges);
133  if (hf != InvalidHalfFaceHandle)
134  return hf;
135  else
136  return halfface_handle(add_face(_halfedges, _topologyCheck), 0);
137 }
138 
139 HalfFaceHandle TetrahedralMeshTopologyKernel::add_halfface(VertexHandle _vh0, VertexHandle _vh1, VertexHandle _vh2, bool _topologyCheck)
140 {
141  std::vector<HalfEdgeHandle> halfedges;
142  halfedges.push_back(add_halfedge(_vh0, _vh1));
143  halfedges.push_back(add_halfedge(_vh1, _vh2));
144  halfedges.push_back(add_halfedge(_vh2, _vh0));
145  return add_halfface(halfedges, _topologyCheck);
146 }
147 
148 /*void TetrahedralMeshTopologyKernel::replaceHalfFace(CellHandle ch, HalfFaceHandle hf_del, HalfFaceHandle hf_ins)
149 {
150  Cell& c = cells_[ch.idx()];
151  std::vector<HalfFaceHandle> hfs;
152  for (unsigned int i = 0; i < c.halffaces().size(); ++i)
153  if (c.halffaces()[i] != hf_del)
154  hfs.push_back(c.halffaces()[i]);
155  else
156  hfs.push_back(hf_ins);
157  c.set_halffaces(hfs);
158 }
159 
160 void TetrahedralMeshTopologyKernel::replaceHalfEdge(HalfFaceHandle hfh, HalfEdgeHandle he_del, HalfEdgeHandle he_ins)
161 {
162  FaceHandle fh = face_handle(hfh);
163  unsigned char oppF = hfh.idx() - halfface_handle(fh, 0);
164  if (oppF == 1)
165  {
166  he_del = opposite_halfedge_handle(he_del);
167  he_ins = opposite_halfedge_handle(he_ins);
168  }
169  Face& f = faces_[fh.idx()];
170  std::vector<HalfEdgeHandle> hes;
171  for (unsigned int i = 0; i < f.halfedges().size(); ++i)
172  if (f.halfedges()[i] != he_del)
173  hes.push_back(f.halfedges()[i]);
174  else
175  hes.push_back(he_ins);
176  f.set_halfedges(hes);
177 
178 }*/
179 
180 /*
181 void TetrahedralMeshTopologyKernel::collapse_edge(HalfEdgeHandle _heh)
182 {
183 
184  std::vector<bool> deleteTagFaces(faces_.size(), false);
185  std::vector<bool> deleteTagEdges(edges_.size(), false);
186  std::vector<bool> deleteTagCells(cells_.size(), false);
187 
188  for (HalfEdgeHalfFaceIter hehf_it = hehf_iter(_heh); hehf_it.valid(); ++hehf_it)
189  {
190  CellHandle ch = incident_cell(*hehf_it);
191  if (ch.is_valid())
192  {
193  HalfFaceHandle hf134 = *hehf_it;
194  HalfFaceHandle hf143 = opposite_halfface_handle(hf143);
195  HalfEdgeHandle he13 = prev_halfedge_in_halfface(_heh, hf134);
196  HalfEdgeHandle he41 = next_halfedge_in_halfface(_heh, hf134);
197  HalfFaceHandle hf123 = adjacent_halfface_in_cell(hf134, he13);
198  HalfFaceHandle hf142 = adjacent_halfface_in_cell(hf134, he41);
199  HalfFaceHandle hf132 = opposite_halfface_handle(hf123);
200  CellHandle ch0123 = incident_cell(hf132);
201  HalfEdgeHandle he32 = next_halfedge_in_halfface(he13, hf132);
202  HalfEdgeHandle he23 = opposite_halfedge_handle(he32);
203  HalfEdgeHandle he14 = opposite_halfedge_handle(he41);
204  HalfEdgeHandle he31 = opposite_halfedge_handle(he13);
205  HalfEdgeHandle he42 = next_halfedge_in_halfface(he14, hf142);
206  HalfEdgeHandle he24 = opposite_halfedge_handle(he42);
207  HalfFaceHandle hf243 = adjacent_halfface_in_cell(hf134, he41);
208  HalfFaceHandle hf234 = opposite_halfface_handle(hf234);
209  HalfEdgeHandle he12 = next_halfedge_in_halfface(he42, hf142);
210  HalfEdgeHandle he21 = opposite_halfedge_handle(he12);
211 
212  if (ch0123.is_valid())
213  {
214  HalfFaceHandle hf031 = adjacent_halfface_in_cell(hf132, he13);
215  HalfFaceHandle hf023 = adjacent_halfface_in_cell(hf132, he32);
216 
217  replaceHalfEdge(hf031, he31, he41);
218  replaceHalfEdge(hf023, he23, he24);
219  replaceHalfFace(ch0123, hf132, hf142);
220  }
221 
222  //copyHalfFaceAndHalfEdgeProperties(hf132, 142);
223 
224  incident_cell_per_hf_[hf142.idx()] = ch0123;
225 
226 
227  deleteTagCells[ch.idx()] = true;
228  deleteTagFaces[face_handle(hf132).idx()] = true;
229  deleteTagFaces[face_handle(*hehf_it).idx()] = true;
230  deleteTagEdges[edge_handle(he13).idx()] = true;
231  deleteTagEdges[edge_handle(he32).idx()] = true;
232 
233  std::set<HalfFaceHandle> excludeFaces;
234  excludeFaces.insert(hf134);
235  excludeFaces.insert(hf143);
236  excludeFaces.insert(hf123);
237  excludeFaces.insert(hf132);
238  excludeFaces.insert(hf243);
239  excludeFaces.insert(hf234);
240 
241  std::vector<std::pair<HalfEdgeHandle, HalfEdgeHandle> > joinpartners;
242  joinpartners.push_back(std::make_pair(he41, he31));
243  joinpartners.push_back(std::make_pair(he14, he13));
244  joinpartners.push_back(std::make_pair(he42, he32));
245  joinpartners.push_back(std::make_pair(he24, he23));
246 
247  for (unsigned int i = 0; i < joinpartners.size(); ++i)
248  {
249  HalfEdgeHandle target = joinpartners[i].first;
250  HalfEdgeHandle source = joinpartners[i].second;
251  std::vector<HalfFaceHandle> incidentHfs;
252  for (unsigned int j = 0; j < incident_hfs_per_he_[target.idx()].size(); ++j)
253  {
254  HalfFaceHandle cur_hf = incident_hfs_per_he_[target.idx()][j];
255  if ((excludeFaces.find(cur_hf) == excludeFaces.end()) && !deleteTagFaces[face_handle(cur_hf).idx()])
256  incidentHfs.push_back(cur_hf);
257  }
258  for (unsigned int i = 0; i < incident_hfs_per_he_[source.idx()].size(); ++i)
259  {
260  HalfFaceHandle cur_hf = incident_hfs_per_he_[source.idx()][i];
261  if ((excludeFaces.find(cur_hf) == excludeFaces.end()) && !deleteTagFaces[face_handle(cur_hf).idx()])
262  incidentHfs.push_back(cur_hf);
263  }
264 
265  std::swap(incident_hfs_per_he_[target], incidentHfs);
266  }
267 
268  std::vector<HalfFaceHandle>& vec = incident_hfs_per_he_[he21];
269  vec.erase(std::remove(vec.begin(), vec.end(), hf132), vec.end());
270  std::vector<HalfFaceHandle>& vec2 = incident_hfs_per_he_[he12];
271  vec2.erase(std::remove(vec2.begin(), vec2.end(), hf123), vec2.end());
272 
273  }
274  else
275  {
276  deleteTagFaces[face_handle(*hehf_it).idx()] = true;
277  }
278  }
279 
280 
281  VertexHandle from_vh = halfedge(_heh).from_vertex();
282  VertexHandle to_vh = halfedge(_heh).to_vertex();
283  for (VertexOHalfEdgeIter voh_it = voh_iter(from_vh); voh_it.valid(); ++voh_it )
284  {
285  Edge he = halfedge(*voh_it);
286  if (he.to_vertex() == to_vh)
287  {
288  std::vector<HalfEdgeHandle>& vec = outgoing_hes_per_vertex_[to_vh];
289  vec.erase(std::remove(vec.begin(), vec.end(), opposite_halfedge_handle(*voh_it)), vec.end());
290  }
291  EdgeHandle eh = edge_handle(*voh_it);
292  if (!deleteTagEdges[eh.idx()])
293  {
294  std::vector<HalfEdgeHandle>& vec = outgoing_hes_per_vertex_[to_vh];
295  vec.push_back(opposite_halfedge_handle(*voh_it));
296 
297  Edge& e = edges_[eh.idx()];
298  if (e.from_vertex() == from_vh)
299  e.set_from_vertex(to_vh);
300  if (e.to_vertex() == from_vh)
301  e.set_to_vertex(to_vh);
302 
303  }
304  }
305 
306  outgoing_hes_per_vertex_[from_vh].clear();
307 
308  deleteTagEdges[edge_handle(_heh).idx()] = true;
309 
310  delete_multiple_cells(deleteTagCells);
311  delete_multiple_faces(deleteTagFaces);
312  delete_multiple_edges(deleteTagEdges);
313  delete_vertex(from_vh);
314 }
315 */
316 
317 
318 //void TetrahedralMeshTopologyKernel::swapCellProperties(CellHandle source, CellHandle destination)
319 //{
320 // swapPropertyElements(cell_props_begin(), cell_props_end(), source, destination);
321 //}
322 
323 //void TetrahedralMeshTopologyKernel::swapHalfFaceProperties(HalfFaceHandle source, HalfFaceHandle destination)
324 //{
325 // swapPropertyElements(halfface_props_begin(), halfface_props_end(), source, destination);
326 //}
327 
328 //void TetrahedralMeshTopologyKernel::swapHalfEdgeProperties(HalfEdgeHandle source, HalfEdgeHandle destination)
329 //{
330 // swapPropertyElements(halfedge_props_begin(), halfedge_props_end(), source, destination);
331 //}
332 
333 VertexHandle TetrahedralMeshTopologyKernel::collapse_edge(HalfEdgeHandle _heh)
334 {
335  bool deferred_deletion_tmp = deferred_deletion_enabled();
336 
337  if (!deferred_deletion_tmp)
338  enable_deferred_deletion(true);
339 
340  VertexHandle from_vh = halfedge(_heh).from_vertex();
341  VertexHandle to_vh = halfedge(_heh).to_vertex();
342 
343 
344  // find cells that will collapse, i.e. are incident to the collapsing halfedge
345  std::set<CellHandle> collapsingCells;
346  for (HalfEdgeHalfFaceIter hehf_it = hehf_iter(_heh); hehf_it.valid(); ++hehf_it)
347  {
348  HalfFaceHandle hfh = *hehf_it;
349  CellHandle ch = incident_cell(hfh);
350  if (ch.is_valid())
351  collapsingCells.insert(ch);
352  }
353 
354  std::vector<CellHandle> incidentCells;
355  for (VertexCellIter vc_it = vc_iter(from_vh); vc_it.valid(); ++vc_it)
356  incidentCells.push_back(*vc_it);
357 
358  for (unsigned int i = 0; i < incidentCells.size(); ++i)
359  {
360  CellHandle ch = incidentCells[i];
361 
362  if (collapsingCells.find(ch) != collapsingCells.end())
363  continue;
364 
365  Cell c = cell(ch);
366 
367  std::vector<HalfFaceHandle> newHalffaces;
368 
369  for (unsigned int i = 0; i < 4; ++i)
370  {
371  Face hf = halfface(c.halffaces()[i]);
372  std::vector<HalfEdgeHandle> newHalfedges;
373 
374  for (unsigned int j = 0; j < 3; ++j)
375  {
376  Edge e = halfedge(hf.halfedges()[j]);
377  VertexHandle newStart = (e.from_vertex() == from_vh) ? to_vh: e.from_vertex();
378  VertexHandle newEnd = (e.to_vertex() == from_vh) ? to_vh : e.to_vertex();
379 
380  HalfEdgeHandle heh = add_halfedge(newStart, newEnd);
381  newHalfedges.push_back(heh);
382  swap_halfedge_properties(hf.halfedges()[j], heh);
383  }
384 
385  HalfFaceHandle hfh = add_halfface(newHalfedges);
386  newHalffaces.push_back(hfh);
387  swap_halfface_properties(c.halffaces()[i], hfh);
388  }
389 
390  delete_cell(ch);
391 
392  CellHandle newCell = add_cell(newHalffaces);
393 
394  swap_cell_properties(ch, newCell);
395 
396  }
397 
398 
399  VertexHandle survivingVertex = to_vh;
400 
401  if (!deferred_deletion_tmp)
402  {
403  if (fast_deletion_enabled())
404  {
405  // from_vh is swapped with last vertex and then deleted
406  if (to_vh.idx() == (int)n_vertices() - 1)
407  survivingVertex = from_vh;
408  }
409  else
410  {
411  // from_vh is deleted and every vertex id larger than from_vh is reduced by one
412  if (from_vh.idx() < to_vh.idx())
413  survivingVertex = VertexHandle(to_vh.idx() - 1);
414  }
415  }
416 
417  delete_vertex(from_vh);
418 
419  enable_deferred_deletion(deferred_deletion_tmp);
420 
421  return survivingVertex;
422 
423 }
424 
425 void TetrahedralMeshTopologyKernel::split_edge(HalfEdgeHandle _heh, VertexHandle _vh)
426 {
427  bool deferred_deletion_tmp = deferred_deletion_enabled();
428 
429  if (!deferred_deletion_tmp)
430  enable_deferred_deletion(true);
431 
432  for (HalfEdgeHalfFaceIter hehf_it = hehf_iter(_heh); hehf_it.valid(); ++hehf_it)
433  {
434  CellHandle ch = incident_cell(*hehf_it);
435  if (ch.is_valid())
436  {
437  std::vector<VertexHandle> vertices = get_cell_vertices(*hehf_it, _heh);
438 
439  delete_cell(ch);
440 
441  add_cell(vertices[0], _vh, vertices[2], vertices[3]);
442  add_cell(_vh, vertices[1], vertices[2], vertices[3]);
443  }
444 
445  }
446 
447  delete_edge(edge_handle(_heh));
448 
449  enable_deferred_deletion(deferred_deletion_tmp);
450 
451 }
452 
453 void TetrahedralMeshTopologyKernel::split_face(FaceHandle _fh, VertexHandle _vh)
454 {
455  bool deferred_deletion_tmp = deferred_deletion_enabled();
456 
457  if (!deferred_deletion_tmp)
458  enable_deferred_deletion(true);
459 
460  for (unsigned int i = 0; i < 2; ++i)
461  {
462  HalfFaceHandle hfh = halfface_handle(_fh, i);
463  CellHandle ch = incident_cell(hfh);
464  if (ch.is_valid())
465  {
466  std::vector<VertexHandle> vertices = get_cell_vertices(hfh);
467 
468  delete_cell(ch);
469 
470  add_cell(vertices[0], vertices[1], _vh, vertices[3]);
471  add_cell(vertices[0], _vh, vertices[2], vertices[3]);
472  add_cell(_vh, vertices[1], vertices[2], vertices[3]);
473  }
474  }
475 
476  delete_face(_fh);
477 
478  enable_deferred_deletion(deferred_deletion_tmp);
479 
480 }
481 
482 
483 std::vector<VertexHandle> TetrahedralMeshTopologyKernel::get_cell_vertices(CellHandle ch) const
484 {
485  return get_cell_vertices(cell(ch).halffaces().front());
486 }
487 
488 std::vector<VertexHandle> TetrahedralMeshTopologyKernel::get_cell_vertices(CellHandle ch, VertexHandle vh) const
489 {
490  HalfFaceHandle hfh = cell(ch).halffaces()[0];
491  Face f = halfface(hfh);
492  HalfEdgeHandle heh;
493  for (unsigned int i = 0; i < 3; ++i)
494  {
495  Edge e = halfedge(f.halfedges()[i]);
496  if (e.from_vertex() == vh)
497  {
498  heh = f.halfedges()[i];
499  break;
500  }
501  }
502  if (!heh.is_valid())
503  {
504  hfh = adjacent_halfface_in_cell(hfh, f.halfedges()[0]);
505  heh = prev_halfedge_in_halfface(opposite_halfedge_handle(f.halfedges()[0]), hfh);
506  }
507 
508  return get_cell_vertices(hfh,heh);
509 
510 }
511 
512 std::vector<VertexHandle> TetrahedralMeshTopologyKernel::get_cell_vertices(HalfFaceHandle hfh) const
513 {
514  return get_cell_vertices(hfh, halfface(hfh).halfedges().front());
515 }
516 
517 std::vector<VertexHandle> TetrahedralMeshTopologyKernel::get_cell_vertices(HalfFaceHandle hfh, HalfEdgeHandle heh) const
518 {
519  std::vector<VertexHandle> vertices;
520 
521  // add vertices of halfface
522  for (unsigned int i = 0; i < 3; ++i)
523  {
524  Edge e = halfedge(heh);
525  vertices.push_back(e.from_vertex());
526  heh = next_halfedge_in_halfface(heh, hfh);
527  }
528 
529  Cell c = cell(incident_cell(hfh));
530  HalfFaceHandle otherHfh = c.halffaces()[0];
531  if (otherHfh == hfh)
532  otherHfh = c.halffaces()[1];
533 
534  Face otherF = halfface(otherHfh);
535 
536  for (unsigned int i = 0; i < otherF.halfedges().size(); ++i)
537  {
538  HalfEdgeHandle he = otherF.halfedges()[i];
539  Edge e = halfedge(he);
540  if (std::find(vertices.begin(), vertices.end(), e.to_vertex()) == vertices.end())
541  {
542  vertices.push_back(e.to_vertex());
543  return vertices;
544  }
545  }
546 
547  return vertices;
548 }
549 
550 std::vector<VertexHandle> TetrahedralMeshTopologyKernel::get_halfface_vertices(HalfFaceHandle hfh) const
551 {
552  return get_halfface_vertices(hfh, halfface(hfh).halfedges().front());
553 }
554 
555 std::vector<VertexHandle> TetrahedralMeshTopologyKernel::get_halfface_vertices(HalfFaceHandle hfh, VertexHandle vh) const
556 {
557  Face hf = halfface(hfh);
558  for (unsigned int i = 0; i < 3; ++i)
559  if (halfedge(hf.halfedges()[i]).from_vertex() == vh)
560  return get_halfface_vertices(hfh, hf.halfedges()[i]);
561 
562  return std::vector<VertexHandle>();
563 }
564 
565 std::vector<VertexHandle> TetrahedralMeshTopologyKernel::get_halfface_vertices(HalfFaceHandle hfh, HalfEdgeHandle heh) const
566 {
567  std::vector<VertexHandle> vertices;
568 
569  // add vertices of halfface
570  for (unsigned int i = 0; i < 3; ++i)
571  {
572  Edge e = halfedge(heh);
573  vertices.push_back(e.from_vertex());
574  heh = next_halfedge_in_halfface(heh, hfh);
575  }
576 
577  return vertices;
578 }
579 
580 
581 //========================================================================================
582 
584 TetrahedralMeshTopologyKernel::add_cell(const std::vector<VertexHandle>& _vertices, bool _topologyCheck) {
585 
586  // debug mode checks
587  assert(TopologyKernel::has_full_bottom_up_incidences());
588  assert(_vertices.size() == 4);
589 
590  // release mode checks
591  if(!TopologyKernel::has_full_bottom_up_incidences()) {
592  return CellHandle(-1);
593  }
594 
595  if(_vertices.size() != 4) {
596  return CellHandle(-1);
597  }
598 
599  HalfFaceHandle hf0, hf1, hf2, hf3;
600 
601  std::vector<VertexHandle> vs;
602 
603  vs.push_back(_vertices[0]);
604  vs.push_back(_vertices[1]);
605  vs.push_back(_vertices[2]);
606  hf0 = TopologyKernel::halfface(vs);
607  if(!hf0.is_valid()) {
609  hf0 = halfface_handle(fh, 0);
610  }
611  vs.clear();
612 
613  vs.push_back(_vertices[0]);
614  vs.push_back(_vertices[2]);
615  vs.push_back(_vertices[3]);
616  hf1 = TopologyKernel::halfface(vs);
617  if(!hf1.is_valid()) {
619  hf1 = halfface_handle(fh, 0);
620  }
621  vs.clear();
622 
623  vs.push_back(_vertices[0]);
624  vs.push_back(_vertices[3]);
625  vs.push_back(_vertices[1]);
626  hf2 = TopologyKernel::halfface(vs);
627  if(!hf2.is_valid()) {
629  hf2 = halfface_handle(fh, 0);
630  }
631  vs.clear();
632 
633  vs.push_back(_vertices[1]);
634  vs.push_back(_vertices[3]);
635  vs.push_back(_vertices[2]);
636  hf3 = TopologyKernel::halfface(vs);
637  if(!hf3.is_valid()) {
639  hf3 = halfface_handle(fh, 0);
640  }
641  vs.clear();
642 
643  assert(hf0.is_valid());
644  assert(hf1.is_valid());
645  assert(hf2.is_valid());
646  assert(hf3.is_valid());
647 
648 
649  std::vector<HalfFaceHandle> hfs;
650  hfs.push_back(hf0);
651  hfs.push_back(hf1);
652  hfs.push_back(hf2);
653  hfs.push_back(hf3);
654 
655  if (_topologyCheck) {
656  /*
657  * Test if all halffaces are connected and form a two-manifold
658  * => Cell is closed
659  *
660  * This test is simple: The number of involved half-edges has to be
661  * exactly twice the number of involved edges.
662  */
663 
664  std::set<HalfEdgeHandle> incidentHalfedges;
665  std::set<EdgeHandle> incidentEdges;
666 
667  for(std::vector<HalfFaceHandle>::const_iterator it = hfs.begin(),
668  end = hfs.end(); it != end; ++it) {
669 
670  OpenVolumeMeshFace hface = halfface(*it);
671  for(std::vector<HalfEdgeHandle>::const_iterator he_it = hface.halfedges().begin(),
672  he_end = hface.halfedges().end(); he_it != he_end; ++he_it) {
673  incidentHalfedges.insert(*he_it);
674  incidentEdges.insert(edge_handle(*he_it));
675  }
676  }
677 
678  if(incidentHalfedges.size() != (incidentEdges.size() * 2u)) {
679 #ifndef NDEBUG
680  std::cerr << "The specified halffaces are not connected!" << std::endl;
681 #endif
682  return InvalidCellHandle;
683  }
684  // The halffaces are now guaranteed to form a two-manifold
685 
686  if(has_face_bottom_up_incidences()) {
687 
688  for(std::vector<HalfFaceHandle>::const_iterator it = hfs.begin(),
689  end = hfs.end(); it != end; ++it) {
690  if(incident_cell(*it) != InvalidCellHandle) {
691 #ifndef NDEBUG
692  std::cerr << "Warning: One of the specified half-faces is already incident to another cell!" << std::endl;
693 #endif
694  return InvalidCellHandle;
695  }
696  }
697 
698  }
699 
700  }
701 
702  return TopologyKernel::add_cell(hfs, false);
703 }
704 
706 {
707  std::vector<HalfFaceHandle> halffaces;
708  halffaces.push_back(add_halfface(_vh0, _vh1, _vh2));
709  halffaces.push_back(add_halfface(_vh0, _vh2, _vh3));
710  halffaces.push_back(add_halfface(_vh0, _vh3, _vh1));
711  halffaces.push_back(add_halfface(_vh1, _vh3, _vh2));
712  return add_cell(halffaces, _topologyCheck);
713 }
714 
715 //========================================================================================
716 
717 } // Namespace OpenVolumeMesh
virtual VertexIter delete_vertex(const VertexHandle &_h)
Delete vertex from mesh.
static HalfEdgeHandle halfedge_handle(const EdgeHandle &_h, const unsigned char _subIdx)
Conversion function.
const Cell & cell(const CellHandle &_cellHandle) const
Get cell with handle _cellHandle.
virtual FaceHandle add_face(const std::vector< HalfEdgeHandle > &_halfedges, bool _topologyCheck=false)
Add face via incident edges.
virtual FaceHandle add_face(const std::vector< HalfEdgeHandle > &_halfedges, bool _topologyCheck=false)
Add face via incident edges.
virtual EdgeHandle add_edge(const VertexHandle &_fromVertex, const VertexHandle &_toHandle, bool _allowDuplicates=false)
Add edge.
virtual FaceIter delete_face(const FaceHandle &_h)
Delete face from mesh.
static EdgeHandle edge_handle(const HalfEdgeHandle &_h)
Handle conversion.
Face halfface(const HalfFaceHandle &_halfFaceHandle) const
Get face that corresponds to halfface with handle _halfFaceHandle.
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.
virtual CellHandle add_cell(const std::vector< HalfFaceHandle > &_halffaces, bool _topologyCheck=false)
Add cell via incident halffaces.
HalfEdgeHandle prev_halfedge_in_halfface(const HalfEdgeHandle &_heh, const HalfFaceHandle &_hfh) const
Get previous halfedge within a halfface.
virtual CellHandle add_cell(const std::vector< HalfFaceHandle > &_halffaces, bool _topologyCheck=false)
Add cell via incident halffaces.
CellHandle incident_cell(const HalfFaceHandle &_halfFaceHandle) const
Get cell that is incident to the given halfface.
Edge halfedge(const HalfEdgeHandle &_halfEdgeHandle) const
Get edge that corresponds to halfedge with handle _halfEdgeHandle.
static HalfFaceHandle halfface_handle(const FaceHandle &_h, const unsigned char _subIdx)
Conversion function.
HalfEdgeHandle next_halfedge_in_halfface(const HalfEdgeHandle &_heh, const HalfFaceHandle &_hfh) const
Get next halfedge within a halfface.
virtual size_t n_vertices() const
Get number of vertices in mesh.
virtual CellIter delete_cell(const CellHandle &_h)
Delete cell from mesh.
virtual EdgeIter delete_edge(const EdgeHandle &_h)
Delete edge from mesh.