HexahedralMeshTopologyKernel.cc 15.9 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*===========================================================================*\
 *                                                                           *
 *                            OpenVolumeMesh                                 *
 *        Copyright (C) 2011 by Computer Graphics Group, RWTH Aachen         *
 *                        www.openvolumemesh.org                             *
 *                                                                           *
 *---------------------------------------------------------------------------*
 *  This file is part of OpenVolumeMesh.                                     *
 *                                                                           *
 *  OpenVolumeMesh is free software: you can redistribute it and/or modify   *
 *  it under the terms of the GNU Lesser General Public License as           *
 *  published by the Free Software Foundation, either version 3 of           *
 *  the License, or (at your option) any later version with the              *
 *  following exceptions:                                                    *
 *                                                                           *
 *  If other files instantiate templates or use macros                       *
 *  or inline functions from this file, or you compile this file and         *
 *  link it with other files to produce an executable, this file does        *
 *  not by itself cause the resulting executable to be covered by the        *
 *  GNU Lesser General Public License. This exception does not however       *
 *  invalidate any other reasons why the executable file might be            *
 *  covered by the GNU Lesser General Public License.                        *
 *                                                                           *
 *  OpenVolumeMesh is distributed in the hope that it will be useful,        *
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of           *
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
 *  GNU Lesser General Public License for more details.                      *
 *                                                                           *
 *  You should have received a copy of the GNU LesserGeneral Public          *
 *  License along with OpenVolumeMesh.  If not,                              *
 *  see <http://www.gnu.org/licenses/>.                                      *
 *                                                                           *
\*===========================================================================*/

/*===========================================================================*\
 *                                                                           *
 *   $Revision$                                                         *
 *   $Date$                    *
 *   $LastChangedBy$                                                *
 *                                                                           *
\*===========================================================================*/

#include "HexahedralMeshTopologyKernel.hh"

namespace OpenVolumeMesh {

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
65

    if(_halfedges.size() != 4) {
        std::cerr << "Face valence is not four! Aborting." << std::endl;
66
        return TopologyKernel::InvalidFaceHandle;
67
68
    }

69
    return TopologyKernel::add_face(_halfedges, _topologyCheck);
70
71
72
73
}

//========================================================================================

74

75
FaceHandle
76
HexahedralMeshTopologyKernel::add_face(const std::vector<VertexHandle>& _vertices) {
77
78
79

    if(_vertices.size() != 4) {
        std::cerr << "Face valence is not four! Aborting." << std::endl;
80
        return TopologyKernel::InvalidFaceHandle;
81
82
    }

83
    return TopologyKernel::add_face(_vertices);
84
85
86
87
}

//========================================================================================

88

89
CellHandle
90
HexahedralMeshTopologyKernel::add_cell(const std::vector<HalfFaceHandle>& _halffaces, bool _topologyCheck) {
91

92
#ifndef NDEBUG
93
94
    if(_halffaces.size() != 6) {
        std::cerr << "Cell valence is not six! Aborting." << std::endl;
95
        return TopologyKernel::InvalidCellHandle;
96
    }
97
    for(std::vector<HalfFaceHandle>::const_iterator it = _halffaces.begin();
98
            it != _halffaces.end(); ++it) {
99
        if(TopologyKernel::halfface(*it).halfedges().size() != 4) {
100
            std::cerr << "Incident face does not have valence four! Aborting." << std::endl;
101
            return TopologyKernel::InvalidCellHandle;
102
103
        }
    }
104
#endif
105
106
107
108
109

    // Create new halffaces vector
    std::vector<HalfFaceHandle> ordered_halffaces;

    // The user wants the faces to be reordered
110
111
112
113
114
115
116
117
118
119
120
    if(_topologyCheck) {

        // Are faces in correct ordering?
        bool ordered = check_halfface_ordering(_halffaces);

        if(!ordered) {

            std::cerr << "The specified half-faces are not in correct order. Trying automatic re-ordering." << std::endl;

            // Ordering array (see below for details)
            const int orderTop[] = {2, 4, 3, 5};
121
            //const int orderBot[] = {3, 4, 2, 5};
122

123
            ordered_halffaces.resize(6, TopologyKernel::InvalidHalfFaceHandle);
124

125
126
            // Create top side
            ordered_halffaces[0] = _halffaces[0];
127

128
129
130
131
132
            // Go over all incident halfedges
            std::vector<HalfEdgeHandle> hes = TopologyKernel::halfface(ordered_halffaces[0]).halfedges();
            unsigned int idx = 0;
            for(std::vector<HalfEdgeHandle>::const_iterator he_it = hes.begin();
                    he_it != hes.end(); ++he_it) {
133

134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
                HalfFaceHandle ahfh = get_adjacent_halfface(ordered_halffaces[0], *he_it, _halffaces);
                if(ahfh == TopologyKernel::InvalidHalfFaceHandle) {
                    std::cerr << "The current halfface is invalid!" << std::endl;
                    continue;
                }
                ordered_halffaces[orderTop[idx]] = ahfh;
                ++idx;
            }

            // Now set bottom-halfface
            HalfFaceHandle cur_hf = ordered_halffaces[0];
            HalfEdgeHandle cur_he = *(TopologyKernel::halfface(cur_hf).halfedges().begin());
            cur_hf = get_adjacent_halfface(cur_hf, cur_he, _halffaces);
            cur_he = TopologyKernel::opposite_halfedge_handle(cur_he);
            cur_he = TopologyKernel::next_halfedge_in_halfface(cur_he, cur_hf);
            cur_he = TopologyKernel::next_halfedge_in_halfface(cur_he, cur_hf);
            cur_hf = get_adjacent_halfface(cur_hf, cur_he, _halffaces);

            if(cur_hf != TopologyKernel::InvalidHalfFaceHandle) {
                ordered_halffaces[1] = cur_hf;
            } else {
155
                std::cerr << "The current halfface is invalid!" << std::endl;
156
                return TopologyKernel::InvalidCellHandle;
157
158
159
            }

        } else {
160
161
            // Assume right ordering at the user's risk
            ordered_halffaces = _halffaces;
162
163
164
165
166
167
168
        }

    } else {
        // Just copy the original ones
        ordered_halffaces = _halffaces;
    }

169
170
171
172
173
174
175
    return TopologyKernel::add_cell(ordered_halffaces, _topologyCheck);
}

//========================================================================================

bool HexahedralMeshTopologyKernel::check_halfface_ordering(const std::vector<HalfFaceHandle>& _hfs) const {

176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
    /*
     * The test works as follows: Test for both the first and second face in the list,
     * whether the following order holds (clockwise):
     *
     * View from above, outside.
     *           ____
     *          | 4  |
     *      ____|____|____
     *     | 5  | 1  | 6  |
     *     |____|____|____|
     *          | 3  |
     *          |____|
     *
     * View from below, outside.
     *           ____
     *          | 3  |
     *      ____|____|____
     *     | 5  | 2  | 6  |
     *     |____|____|____|
     *          | 4  |
     *          |____|
     */

199
200
201
202
203
    const int orderTop[] = {2, 4, 3, 5};
    const int orderBot[] = {3, 4, 2, 5};

    HalfFaceHandle hfhTop = _hfs[0];
    HalfFaceHandle hfhBot = _hfs[1];
204

205
206
    std::vector<HalfEdgeHandle> halfedgesTop = TopologyKernel::halfface(_hfs[0]).halfedges();
    std::vector<HalfEdgeHandle> halfedgesBot = TopologyKernel::halfface(_hfs[1]).halfedges();
207
208
209
210
211

    int offsetTop = -1;
    int offsetBot = -1;

    // Traverse halfedges top
212
    for(std::vector<HalfEdgeHandle>::const_iterator it = halfedgesTop.begin();
213
214
            it != halfedgesTop.end(); ++it) {

215
        HalfFaceHandle ahfh = get_adjacent_halfface(hfhTop, *it, _hfs);
216
217

        if(offsetTop == -1) {
218
219
220
221
            if(ahfh == _hfs[2])       offsetTop = 0;
            else if(ahfh == _hfs[4])  offsetTop = 1;
            else if(ahfh == _hfs[3])  offsetTop = 2;
            else if(ahfh == _hfs[5])  offsetTop = 3;
222
223
        } else {
            offsetTop = (offsetTop + 1) % 4;
224
            if(ahfh != _hfs[orderTop[offsetTop]]) {
225
                std::cerr << "Faces not in right order!" << std::endl;
226
                return false;
227
228
229
230
231
232
            }
        }
    }

    if(offsetTop == -1) {
        std::cerr << "Faces not in right order!" << std::endl;
233
        return false;
234
235
236
    }

    // Traverse halfedges bottom
237
    for(std::vector<HalfEdgeHandle>::const_iterator it = halfedgesBot.begin();
238
239
            it != halfedgesBot.end(); ++it) {

240
        HalfFaceHandle ahfh = get_adjacent_halfface(hfhBot, *it, _hfs);
241
242

        if(offsetBot == -1) {
243
244
245
246
            if(ahfh == _hfs[3])       offsetBot = 0;
            else if(ahfh == _hfs[4])  offsetBot = 1;
            else if(ahfh == _hfs[2])  offsetBot = 2;
            else if(ahfh == _hfs[5])  offsetBot = 3;
247
248
        } else {
            offsetBot = (offsetBot + 1) % 4;
249
            if(ahfh != _hfs[orderBot[offsetBot]]) {
250
                std::cerr << "Faces not in right order!" << std::endl;
251
                return false;
252
253
254
255
256
257
            }
        }
    }

    if(offsetBot == -1) {
        std::cerr << "Faces not in right order!" << std::endl;
258
        return false;
259
260
    }

261
    return true;
262
263
264
265
}

//========================================================================================

266
CellHandle
267
HexahedralMeshTopologyKernel::add_cell(const std::vector<VertexHandle>& _vertices, bool _topologyCheck) {
268
269
270

    assert(_vertices.size() == 8);

271
272
    if(!TopologyKernel::has_full_bottom_up_incidences()) {
        std::cerr << "Error: This function needs bottom-up incidences to be enabled!" << std::endl;
273
274
275
276
277
278
279
280
        return CellHandle(-1);
    }

    if(_vertices.size() != 8) {
        std::cerr << "The number of vertices is not eight!" << std::endl;
        return CellHandle(-1);
    }

281
    HalfFaceHandle hf0, hf1, hf2, hf3, hf4, hf5;
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374

    std::vector<VertexHandle> vs;

    // Half-face XF
    vs.push_back(_vertices[2]);
    vs.push_back(_vertices[1]);
    vs.push_back(_vertices[0]);
    hf0 = TopologyKernel::halfface(vs); vs.clear();

    // Half-face XB
    vs.push_back(_vertices[6]);
    vs.push_back(_vertices[5]);
    vs.push_back(_vertices[4]);
    hf1 = TopologyKernel::halfface(vs); vs.clear();

    // Half-face YF
    vs.push_back(_vertices[1]);
    vs.push_back(_vertices[2]);
    vs.push_back(_vertices[6]);
    hf2 = TopologyKernel::halfface(vs); vs.clear();

    // Half-face YB
    vs.push_back(_vertices[5]);
    vs.push_back(_vertices[3]);
    vs.push_back(_vertices[0]);
    hf3 = TopologyKernel::halfface(vs); vs.clear();

    // Half-face ZF
    vs.push_back(_vertices[7]);
    vs.push_back(_vertices[4]);
    vs.push_back(_vertices[0]);
    hf4 = TopologyKernel::halfface(vs); vs.clear();

    // Half-face ZB
    vs.push_back(_vertices[3]);
    vs.push_back(_vertices[5]);
    vs.push_back(_vertices[6]);
    hf5 = TopologyKernel::halfface(vs);

    if(!hf0.is_valid()) {

        vs.clear();
        vs.push_back(_vertices[3]); vs.push_back(_vertices[2]);
        vs.push_back(_vertices[1]); vs.push_back(_vertices[0]);
        FaceHandle fh = TopologyKernel::add_face(vs);
        hf0 = halfface_handle(fh, 0);
    }

    if(!hf1.is_valid()) {

        vs.clear();
        vs.push_back(_vertices[7]); vs.push_back(_vertices[6]);
        vs.push_back(_vertices[5]); vs.push_back(_vertices[4]);
        FaceHandle fh = TopologyKernel::add_face(vs);
        hf1 = halfface_handle(fh, 0);
    }

    if(!hf2.is_valid()) {

        vs.clear();
        vs.push_back(_vertices[1]); vs.push_back(_vertices[2]);
        vs.push_back(_vertices[6]); vs.push_back(_vertices[7]);
        FaceHandle fh = TopologyKernel::add_face(vs);
        hf2 = halfface_handle(fh, 0);
    }

    if(!hf3.is_valid()) {

        vs.clear();
        vs.push_back(_vertices[4]); vs.push_back(_vertices[5]);
        vs.push_back(_vertices[3]); vs.push_back(_vertices[0]);
        FaceHandle fh = TopologyKernel::add_face(vs);
        hf3 = halfface_handle(fh, 0);
    }

    if(!hf4.is_valid()) {

        vs.clear();
        vs.push_back(_vertices[1]); vs.push_back(_vertices[7]);
        vs.push_back(_vertices[4]); vs.push_back(_vertices[0]);
        FaceHandle fh = TopologyKernel::add_face(vs);
        hf4 = halfface_handle(fh, 0);
    }

    if(!hf5.is_valid()) {

        vs.clear();
        vs.push_back(_vertices[2]); vs.push_back(_vertices[3]);
        vs.push_back(_vertices[5]); vs.push_back(_vertices[6]);
        FaceHandle fh = TopologyKernel::add_face(vs);
        hf5 = halfface_handle(fh, 0);
    }

Mike Kremer's avatar
Mike Kremer committed
375
376
    assert(hf0.is_valid()); assert(hf1.is_valid()); assert(hf2.is_valid());
    assert(hf3.is_valid()); assert(hf4.is_valid()); assert(hf5.is_valid());
377

378

379
380
381
382
    std::vector<HalfFaceHandle> hfs;
    hfs.push_back(hf0); hfs.push_back(hf1); hfs.push_back(hf2);
    hfs.push_back(hf3); hfs.push_back(hf4); hfs.push_back(hf5);

383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
    if (_topologyCheck) {
       /*
        * Test if all halffaces are connected and form a two-manifold
        * => Cell is closed
        *
        * This test is simple: The number of involved half-edges has to be
        * exactly twice the number of involved edges.
        */

        std::set<HalfEdgeHandle> incidentHalfedges;
        std::set<EdgeHandle>     incidentEdges;

        for(std::vector<HalfFaceHandle>::const_iterator it = hfs.begin(),
            end = hfs.end(); it != end; ++it) {

          OpenVolumeMeshFace hface = halfface(*it);
          for(std::vector<HalfEdgeHandle>::const_iterator he_it = hface.halfedges().begin(),
              he_end = hface.halfedges().end(); he_it != he_end; ++he_it) {
            incidentHalfedges.insert(*he_it);
            incidentEdges.insert(edge_handle(*he_it));
          }
        }

        if(incidentHalfedges.size() != (incidentEdges.size() * 2u)) {
          std::cerr << "The specified halffaces are not connected!" << std::endl;
          return InvalidCellHandle;
        }
        // The halffaces are now guaranteed to form a two-manifold
    }

413
414
415
416
    return TopologyKernel::add_cell(hfs,false);
}

//========================================================================================
417

418
const HalfFaceHandle&
419
HexahedralMeshTopologyKernel::get_adjacent_halfface(const HalfFaceHandle& _hfh, const HalfEdgeHandle& _heh,
420
421
422
423
        const std::vector<HalfFaceHandle>& _halffaces) const {

    // Search for halfface that is incident to the opposite
    // halfedge of _heh
424
    HalfEdgeHandle o_he = TopologyKernel::opposite_halfedge_handle(_heh);
425

426
    for(std::vector<HalfFaceHandle>::const_iterator it = _halffaces.begin();
427
428
            it != _halffaces.end(); ++it) {
        if(*it == _hfh) continue;
429
        std::vector<HalfEdgeHandle> halfedges = TopologyKernel::halfface(*it).halfedges();
430
        for(std::vector<HalfEdgeHandle>::const_iterator h_it = halfedges.begin();
431
432
433
434
435
                h_it != halfedges.end(); ++h_it) {
            if(*h_it == o_he) return *it;
        }
    }

436
    return TopologyKernel::InvalidHalfFaceHandle;
437
438
439
}

} // Namespace OpenVolumeMesh