Developer Documentation

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
78 FaceHandle
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
95 CellHandle
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]);
349 hf5 = TopologyKernel::halfface_extensive(vs);
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]);
356 FaceHandle fh = TopologyKernel::add_face(vs);
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]);
365 FaceHandle fh = TopologyKernel::add_face(vs);
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]);
374 FaceHandle fh = TopologyKernel::add_face(vs);
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]);
383 FaceHandle fh = TopologyKernel::add_face(vs);
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]);
392 FaceHandle fh = TopologyKernel::add_face(vs);
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]);
401 FaceHandle fh = TopologyKernel::add_face(vs);
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
OpenVolumeMesh::HexahedralMeshTopologyKernel::add_cell
virtual CellHandle add_cell(const std::vector< HalfFaceHandle > &_halffaces, bool _topologyCheck=false)
Overridden function.
Definition: HexahedralMeshTopologyKernel.cc:96
OpenVolumeMesh::OpenVolumeMeshFace
Definition: BaseEntities.hh:90
OpenVolumeMesh::TopologyKernel::add_face
virtual FaceHandle add_face(const std::vector< HalfEdgeHandle > &_halfedges, bool _topologyCheck=false)
Add face via incident edges.
Definition: TopologyKernel.cc:161
OpenVolumeMesh::TopologyKernel::edge_handle
static EdgeHandle edge_handle(const HalfEdgeHandle &_h)
Handle conversion.
Definition: TopologyKernel.hh:933
OpenVolumeMesh::HandleT
Definition: OpenVolumeMeshHandle.hh:93
OpenVolumeMesh::TopologyKernel::halfface
Face halfface(const HalfFaceHandle &_halfFaceHandle) const
Get face that corresponds to halfface with handle _halfFaceHandle.
Definition: TopologyKernel.cc:2072
OpenVolumeMesh
Definition: ColorAttrib.hh:53
OpenVolumeMesh::TopologyKernel::add_cell
virtual CellHandle add_cell(const std::vector< HalfFaceHandle > &_halffaces, bool _topologyCheck=false)
Add cell via incident halffaces.
Definition: TopologyKernel.cc:378
OpenVolumeMesh::HexahedralMeshTopologyKernel::add_face
virtual FaceHandle add_face(const std::vector< HalfEdgeHandle > &_halfedges, bool _topologyCheck=false)
Add face via incident edges.
Definition: HexahedralMeshTopologyKernel.cc:62
OpenVolumeMesh::TopologyKernel::incident_cell
CellHandle incident_cell(const HalfFaceHandle &_halfFaceHandle) const
Get cell that is incident to the given halfface.
Definition: TopologyKernel.cc:2310
OpenVolumeMesh::TopologyKernel::halfface_handle
static HalfFaceHandle halfface_handle(const FaceHandle &_h, const unsigned char _subIdx)
Conversion function.
Definition: TopologyKernel.hh:924
OpenVolumeMesh::TopologyKernel::next_halfedge_in_halfface
HalfEdgeHandle next_halfedge_in_halfface(const HalfEdgeHandle &_heh, const HalfFaceHandle &_hfh) const
Get next halfedge within a halfface.
Definition: TopologyKernel.cc:2226
OpenVolumeMesh::TopologyKernel::halfface_extensive
HalfFaceHandle halfface_extensive(const std::vector< VertexHandle > &_vs) const
Definition: TopologyKernel.cc:2158