Developer Documentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
HexahedralMeshTopologyKernel.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 "HexahedralMeshTopologyKernel.hh"
44 
45 namespace OpenVolumeMesh {
46 
47 
48 HexahedralMeshTopologyKernel::HexahedralMeshTopologyKernel() {
49 
50 }
51 
52 //========================================================================================
53 
54 
55 HexahedralMeshTopologyKernel::~HexahedralMeshTopologyKernel() {
56 
57 }
58 
59 //========================================================================================
60 
61 
62 FaceHandle HexahedralMeshTopologyKernel::add_face(const std::vector<HalfEdgeHandle>& _halfedges, bool _topologyCheck) {
63 
64  if(_halfedges.size() != 4) {
65 #ifndef NDEBUG
66  std::cerr << "HexahedralMeshTopologyKernel::add_face(): Face valence is not four! Returning" << std::endl;
67  std::cerr << "invalid handle." << std::endl;
68 #endif
69  return TopologyKernel::InvalidFaceHandle;
70  }
71 
72  return TopologyKernel::add_face(_halfedges, _topologyCheck);
73 }
74 
75 //========================================================================================
76 
77 
79 HexahedralMeshTopologyKernel::add_face(const std::vector<VertexHandle>& _vertices) {
80 
81  if(_vertices.size() != 4) {
82 #ifndef NDEBUG
83  std::cerr << "HexahedralMeshTopologyKernel::add_face(): Face valence is not four! Returning" << std::endl;
84  std::cerr << "invalid handle." << std::endl;
85 #endif
86  return TopologyKernel::InvalidFaceHandle;
87  }
88 
89  return TopologyKernel::add_face(_vertices);
90 }
91 
92 //========================================================================================
93 
94 
96 HexahedralMeshTopologyKernel::add_cell(const std::vector<HalfFaceHandle>& _halffaces, bool _topologyCheck) {
97 
98  if(_halffaces.size() != 6) {
99 // To make this consistent with add_face
100 #ifndef NDEBUG
101  std::cerr << "Cell valence is not six! Aborting." << std::endl;
102 #endif
103  return TopologyKernel::InvalidCellHandle;
104  }
105  for(std::vector<HalfFaceHandle>::const_iterator it = _halffaces.begin();
106  it != _halffaces.end(); ++it) {
107  if(TopologyKernel::halfface(*it).halfedges().size() != 4) {
108 #ifndef NDEBUG
109  std::cerr << "Incident face does not have valence four! Aborting." << std::endl;
110 #endif
111  return TopologyKernel::InvalidCellHandle;
112  }
113  }
114 
115  // Create new halffaces vector
116  std::vector<HalfFaceHandle> ordered_halffaces;
117 
118  // The user wants the faces to be reordered
119  if(_topologyCheck) {
120 
121  // Are faces in correct ordering?
122  bool ordered = check_halfface_ordering(_halffaces);
123 
124  if(!ordered) {
125 
126 #ifndef NDEBUG
127  std::cerr << "The specified half-faces are not in correct order. Trying automatic re-ordering." << std::endl;
128 #endif
129 
130  // Ordering array (see below for details)
131  const int orderTop[] = {2, 4, 3, 5};
132  //const int orderBot[] = {3, 4, 2, 5};
133 
134  ordered_halffaces.resize(6, TopologyKernel::InvalidHalfFaceHandle);
135 
136  // Create top side
137  ordered_halffaces[0] = _halffaces[0];
138 
139  // Go over all incident halfedges
140  std::vector<HalfEdgeHandle> hes = TopologyKernel::halfface(ordered_halffaces[0]).halfedges();
141  unsigned int idx = 0;
142  for(std::vector<HalfEdgeHandle>::const_iterator he_it = hes.begin();
143  he_it != hes.end(); ++he_it) {
144 
145  HalfFaceHandle ahfh = get_adjacent_halfface(ordered_halffaces[0], *he_it, _halffaces);
146  if(ahfh == TopologyKernel::InvalidHalfFaceHandle) {
147 #ifndef NDEBUG
148  std::cerr << "The current halfface is invalid!" << std::endl;
149 #endif
150  continue;
151  }
152  ordered_halffaces[orderTop[idx]] = ahfh;
153  ++idx;
154  }
155 
156  // Now set bottom-halfface
157  HalfFaceHandle cur_hf = ordered_halffaces[0];
158  HalfEdgeHandle cur_he = *(TopologyKernel::halfface(cur_hf).halfedges().begin());
159  cur_hf = get_adjacent_halfface(cur_hf, cur_he, _halffaces);
160  cur_he = TopologyKernel::opposite_halfedge_handle(cur_he);
161  cur_he = TopologyKernel::next_halfedge_in_halfface(cur_he, cur_hf);
162  cur_he = TopologyKernel::next_halfedge_in_halfface(cur_he, cur_hf);
163  cur_hf = get_adjacent_halfface(cur_hf, cur_he, _halffaces);
164 
165  if(cur_hf != TopologyKernel::InvalidHalfFaceHandle) {
166  ordered_halffaces[1] = cur_hf;
167  } else {
168 #ifndef NDEBUG
169  std::cerr << "The current halfface is invalid!" << std::endl;
170 #endif
171  return TopologyKernel::InvalidCellHandle;
172  }
173 
174  } else {
175  // Assume right ordering at the user's risk
176  ordered_halffaces = _halffaces;
177  }
178 
179  } else {
180  // Just copy the original ones
181  ordered_halffaces = _halffaces;
182  }
183 
184  return TopologyKernel::add_cell(ordered_halffaces, _topologyCheck);
185 }
186 
187 //========================================================================================
188 
189 bool HexahedralMeshTopologyKernel::check_halfface_ordering(const std::vector<HalfFaceHandle>& _hfs) const {
190 
191  /*
192  * The test works as follows: Test for both the first and second face in the list,
193  * whether the following order holds (clockwise):
194  *
195  * View from above, outside.
196  * ____
197  * | 4 |
198  * ____|____|____
199  * | 5 | 1 | 6 |
200  * |____|____|____|
201  * | 3 |
202  * |____|
203  *
204  * View from below, outside.
205  * ____
206  * | 3 |
207  * ____|____|____
208  * | 5 | 2 | 6 |
209  * |____|____|____|
210  * | 4 |
211  * |____|
212  */
213 
214  const int orderTop[] = {2, 4, 3, 5};
215  const int orderBot[] = {3, 4, 2, 5};
216 
217  HalfFaceHandle hfhTop = _hfs[0];
218  HalfFaceHandle hfhBot = _hfs[1];
219 
220  std::vector<HalfEdgeHandle> halfedgesTop = TopologyKernel::halfface(_hfs[0]).halfedges();
221  std::vector<HalfEdgeHandle> halfedgesBot = TopologyKernel::halfface(_hfs[1]).halfedges();
222 
223  int offsetTop = -1;
224  int offsetBot = -1;
225 
226  // Traverse halfedges top
227  for(std::vector<HalfEdgeHandle>::const_iterator it = halfedgesTop.begin();
228  it != halfedgesTop.end(); ++it) {
229 
230  HalfFaceHandle ahfh = get_adjacent_halfface(hfhTop, *it, _hfs);
231 
232  if(offsetTop == -1) {
233  if(ahfh == _hfs[2]) offsetTop = 0;
234  else if(ahfh == _hfs[4]) offsetTop = 1;
235  else if(ahfh == _hfs[3]) offsetTop = 2;
236  else if(ahfh == _hfs[5]) offsetTop = 3;
237  } else {
238  offsetTop = (offsetTop + 1) % 4;
239  if(ahfh != _hfs[orderTop[offsetTop]]) {
240 #ifndef NDEBUG
241  std::cerr << "Faces not in right order!" << std::endl;
242 #endif
243  return false;
244  }
245  }
246  }
247 
248  if(offsetTop == -1) {
249 #ifndef NDEBUG
250  std::cerr << "Faces not in right order!" << std::endl;
251 #endif
252  return false;
253  }
254 
255  // Traverse halfedges bottom
256  for(std::vector<HalfEdgeHandle>::const_iterator it = halfedgesBot.begin();
257  it != halfedgesBot.end(); ++it) {
258 
259  HalfFaceHandle ahfh = get_adjacent_halfface(hfhBot, *it, _hfs);
260 
261  if(offsetBot == -1) {
262  if(ahfh == _hfs[3]) offsetBot = 0;
263  else if(ahfh == _hfs[4]) offsetBot = 1;
264  else if(ahfh == _hfs[2]) offsetBot = 2;
265  else if(ahfh == _hfs[5]) offsetBot = 3;
266  } else {
267  offsetBot = (offsetBot + 1) % 4;
268  if(ahfh != _hfs[orderBot[offsetBot]]) {
269 #ifndef NDEBUG
270  std::cerr << "Faces not in right order!" << std::endl;
271 #endif
272  return false;
273  }
274  }
275  }
276 
277  if(offsetBot == -1) {
278 #ifndef NDEBUG
279  std::cerr << "Faces not in right order!" << std::endl;
280 #endif
281  return false;
282  }
283 
284  return true;
285 }
286 
287 //========================================================================================
288 
289 CellHandle
290 HexahedralMeshTopologyKernel::add_cell(const std::vector<VertexHandle>& _vertices, bool _topologyCheck) {
291 
292  // debug mode checks
293  assert(TopologyKernel::has_full_bottom_up_incidences());
294  assert(_vertices.size() == 8);
295 
296  // release mode checks
297  if(!TopologyKernel::has_full_bottom_up_incidences()) {
298  return CellHandle(-1);
299  }
300 
301  if(_vertices.size() != 8) {
302  return CellHandle(-1);
303  }
304 
305  HalfFaceHandle hf0, hf1, hf2, hf3, hf4, hf5;
306 
307  std::vector<VertexHandle> vs;
308 
309  // Half-face XF
310  vs.push_back(_vertices[3]);
311  vs.push_back(_vertices[2]);
312  vs.push_back(_vertices[1]);
313  vs.push_back(_vertices[0]);
314  hf0 = TopologyKernel::halfface_extensive(vs); vs.clear();
315 
316  // Half-face XB
317  vs.push_back(_vertices[7]);
318  vs.push_back(_vertices[6]);
319  vs.push_back(_vertices[5]);
320  vs.push_back(_vertices[4]);
321  hf1 = TopologyKernel::halfface_extensive(vs); vs.clear();
322 
323  // Half-face YF
324  vs.push_back(_vertices[1]);
325  vs.push_back(_vertices[2]);
326  vs.push_back(_vertices[6]);
327  vs.push_back(_vertices[7]);
328  hf2 = TopologyKernel::halfface_extensive(vs); vs.clear();
329 
330  // Half-face YB
331  vs.push_back(_vertices[4]);
332  vs.push_back(_vertices[5]);
333  vs.push_back(_vertices[3]);
334  vs.push_back(_vertices[0]);
335  hf3 = TopologyKernel::halfface_extensive(vs); vs.clear();
336 
337  // Half-face ZF
338  vs.push_back(_vertices[1]);
339  vs.push_back(_vertices[7]);
340  vs.push_back(_vertices[4]);
341  vs.push_back(_vertices[0]);
342  hf4 = TopologyKernel::halfface_extensive(vs); vs.clear();
343 
344  // Half-face ZB
345  vs.push_back(_vertices[2]);
346  vs.push_back(_vertices[3]);
347  vs.push_back(_vertices[5]);
348  vs.push_back(_vertices[6]);
350 
351  if(!hf0.is_valid()) {
352 
353  vs.clear();
354  vs.push_back(_vertices[3]); vs.push_back(_vertices[2]);
355  vs.push_back(_vertices[1]); vs.push_back(_vertices[0]);
357  hf0 = halfface_handle(fh, 0);
358  }
359 
360  if(!hf1.is_valid()) {
361 
362  vs.clear();
363  vs.push_back(_vertices[7]); vs.push_back(_vertices[6]);
364  vs.push_back(_vertices[5]); vs.push_back(_vertices[4]);
366  hf1 = halfface_handle(fh, 0);
367  }
368 
369  if(!hf2.is_valid()) {
370 
371  vs.clear();
372  vs.push_back(_vertices[1]); vs.push_back(_vertices[2]);
373  vs.push_back(_vertices[6]); vs.push_back(_vertices[7]);
375  hf2 = halfface_handle(fh, 0);
376  }
377 
378  if(!hf3.is_valid()) {
379 
380  vs.clear();
381  vs.push_back(_vertices[4]); vs.push_back(_vertices[5]);
382  vs.push_back(_vertices[3]); vs.push_back(_vertices[0]);
384  hf3 = halfface_handle(fh, 0);
385  }
386 
387  if(!hf4.is_valid()) {
388 
389  vs.clear();
390  vs.push_back(_vertices[1]); vs.push_back(_vertices[7]);
391  vs.push_back(_vertices[4]); vs.push_back(_vertices[0]);
393  hf4 = halfface_handle(fh, 0);
394  }
395 
396  if(!hf5.is_valid()) {
397 
398  vs.clear();
399  vs.push_back(_vertices[2]); vs.push_back(_vertices[3]);
400  vs.push_back(_vertices[5]); vs.push_back(_vertices[6]);
402  hf5 = halfface_handle(fh, 0);
403  }
404 
405  assert(hf0.is_valid()); assert(hf1.is_valid()); assert(hf2.is_valid());
406  assert(hf3.is_valid()); assert(hf4.is_valid()); assert(hf5.is_valid());
407 
408 
409  std::vector<HalfFaceHandle> hfs;
410  hfs.push_back(hf0); hfs.push_back(hf1); hfs.push_back(hf2);
411  hfs.push_back(hf3); hfs.push_back(hf4); hfs.push_back(hf5);
412 
413  if (_topologyCheck) {
414  /*
415  * Test if all halffaces are connected and form a two-manifold
416  * => Cell is closed
417  *
418  * This test is simple: The number of involved half-edges has to be
419  * exactly twice the number of involved edges.
420  */
421 
422  std::set<HalfEdgeHandle> incidentHalfedges;
423  std::set<EdgeHandle> incidentEdges;
424 
425  for(std::vector<HalfFaceHandle>::const_iterator it = hfs.begin(),
426  end = hfs.end(); it != end; ++it) {
427 
428  OpenVolumeMeshFace hface = halfface(*it);
429  for(std::vector<HalfEdgeHandle>::const_iterator he_it = hface.halfedges().begin(),
430  he_end = hface.halfedges().end(); he_it != he_end; ++he_it) {
431  incidentHalfedges.insert(*he_it);
432  incidentEdges.insert(edge_handle(*he_it));
433  }
434  }
435 
436  if(incidentHalfedges.size() != (incidentEdges.size() * 2u)) {
437 #ifndef NDEBUG
438  std::cerr << "The specified halffaces are not connected!" << std::endl;
439 #endif
440  return InvalidCellHandle;
441  }
442  // The halffaces are now guaranteed to form a two-manifold
443 
444  if(has_face_bottom_up_incidences()) {
445 
446  for(std::vector<HalfFaceHandle>::const_iterator it = hfs.begin(),
447  end = hfs.end(); it != end; ++it) {
448  if(incident_cell(*it) != InvalidCellHandle) {
449 #ifndef NDEBUG
450  std::cerr << "Warning: One of the specified half-faces is already incident to another cell!" << std::endl;
451 #endif
452  return InvalidCellHandle;
453  }
454  }
455 
456  }
457 
458  }
459 
460  return TopologyKernel::add_cell(hfs, false);
461 }
462 
463 //========================================================================================
464 
465 const HalfFaceHandle&
466 HexahedralMeshTopologyKernel::get_adjacent_halfface(const HalfFaceHandle& _hfh, const HalfEdgeHandle& _heh,
467  const std::vector<HalfFaceHandle>& _halffaces) const {
468 
469  // Search for halfface that is incident to the opposite
470  // halfedge of _heh
471  HalfEdgeHandle o_he = TopologyKernel::opposite_halfedge_handle(_heh);
472 
473  for(std::vector<HalfFaceHandle>::const_iterator it = _halffaces.begin();
474  it != _halffaces.end(); ++it) {
475  if(*it == _hfh) continue;
476  std::vector<HalfEdgeHandle> halfedges = TopologyKernel::halfface(*it).halfedges();
477  for(std::vector<HalfEdgeHandle>::const_iterator h_it = halfedges.begin();
478  h_it != halfedges.end(); ++h_it) {
479  if(*h_it == o_he) return *it;
480  }
481  }
482 
483  return TopologyKernel::InvalidHalfFaceHandle;
484 }
485 
486 } // Namespace OpenVolumeMesh
virtual CellHandle add_cell(const std::vector< HalfFaceHandle > &_halffaces, bool _topologyCheck=false)
Overridden function.
CellHandle incident_cell(const HalfFaceHandle &_halfFaceHandle) const
Get cell that is incident to the given halfface.
virtual CellHandle add_cell(const std::vector< HalfFaceHandle > &_halffaces, bool _topologyCheck=false)
Add cell via incident halffaces.
virtual FaceHandle add_face(const std::vector< HalfEdgeHandle > &_halfedges, bool _topologyCheck=false)
Add face via incident edges.
Face halfface(const HalfFaceHandle &_halfFaceHandle) const
Get face that corresponds to halfface with handle _halfFaceHandle.
HalfFaceHandle halfface_extensive(const std::vector< VertexHandle > &_vs) const
static HalfFaceHandle halfface_handle(const FaceHandle &_h, const unsigned char _subIdx)
Conversion function.
static EdgeHandle edge_handle(const HalfEdgeHandle &_h)
Handle conversion.
virtual FaceHandle add_face(const std::vector< HalfEdgeHandle > &_halfedges, bool _topologyCheck=false)
Add face via incident edges.
HalfEdgeHandle next_halfedge_in_halfface(const HalfEdgeHandle &_heh, const HalfFaceHandle &_hfh) const
Get next halfedge within a halfface.