TopologyKernel.hh 33.6 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
/*===========================================================================*\
 *                                                                           *
 *                            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$                                                *
 *                                                                           *
\*===========================================================================*/

#ifndef TOPOLOGYKERNEL_HH_
#define TOPOLOGYKERNEL_HH_

46
#include <cassert>
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <set>
#include <vector>

#include "BaseEntities.hh"
#include "OpenVolumeMeshHandle.hh"
#include "ResourceManager.hh"
#include "Iterators.hh"

namespace OpenVolumeMesh {

class TopologyKernel : public ResourceManager {
public:

    TopologyKernel();
    virtual ~TopologyKernel();

    /*
     * Defines and constants
     */

    static const VertexHandle   InvalidVertexHandle;
    static const EdgeHandle     InvalidEdgeHandle;
    static const FaceHandle     InvalidFaceHandle;
    static const CellHandle     InvalidCellHandle;
    static const HalfEdgeHandle InvalidHalfEdgeHandle;
    static const HalfFaceHandle InvalidHalfFaceHandle;

    typedef OpenVolumeMeshEdge Edge;
    typedef OpenVolumeMeshFace Face;
    typedef OpenVolumeMeshCell Cell;

78
79
80
81
82
    // Add StatusAttrib to list of friend classes
    // since it provides a garbage collection
    // that needs access to some protected methods
    friend class StatusAttrib;

83
84
85
86
87
    //=====================================================================
    // Iterators
    //=====================================================================

    friend class VertexOHalfEdgeIter;
88
    friend class VertexVertexIter;
89
    friend class HalfEdgeHalfFaceIter;
90
    friend class VertexFaceIter;
91
92
93
94
    friend class VertexCellIter;
    friend class HalfEdgeCellIter;
    friend class CellVertexIter;
    friend class CellCellIter;
Mike Kremer's avatar
Mike Kremer committed
95
    friend class HalfFaceVertexIter;
96
    friend class BoundaryHalfFaceHalfFaceIter;
97
98
99
100
101
102
103
104
    friend class BoundaryFaceIter;
    friend class VertexIter;
    friend class EdgeIter;
    friend class HalfEdgeIter;
    friend class FaceIter;
    friend class HalfFaceIter;
    friend class CellIter;

Max Lyon's avatar
Max Lyon committed
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
    /*
     * Circulators
     */

protected:
    template <class Circulator>
    static Circulator make_end_circulator(const Circulator& _circ)
    {
        Circulator end = _circ;
        if (end.valid()) {
            end.lap(_circ.max_laps());
            end.valid(false);
        }
        return end;
    }

public:

    VertexOHalfEdgeIter voh_iter(const VertexHandle& _h, int _max_laps = 1) const {
        return VertexOHalfEdgeIter(_h, this, _max_laps);
    }

    std::pair<VertexOHalfEdgeIter, VertexOHalfEdgeIter> outgoing_halfedges(const VertexHandle& _h, int _max_laps = 1) const {
        VertexOHalfEdgeIter begin = voh_iter(_h, _max_laps);
        return std::make_pair(begin, make_end_circulator(begin));
130
131
132
133
134
135
136
137
138
    }

    VertexVertexIter vv_iter(const VertexHandle& _h, int _max_laps = 1) const {
        return VertexVertexIter(_h, this, _max_laps);
    }

    std::pair<VertexVertexIter, VertexVertexIter> vertex_vertices(const VertexHandle& _h, int _max_laps = 1) const {
        VertexVertexIter begin = vv_iter(_h, _max_laps);
        return std::make_pair(begin, make_end_circulator(begin));
Max Lyon's avatar
Max Lyon committed
139
140
141
142
143
144
145
146
147
148
149
    }

    HalfEdgeHalfFaceIter hehf_iter(const HalfEdgeHandle& _h, int _max_laps = 1) const {
        return HalfEdgeHalfFaceIter(_h, this, _max_laps);
    }

    std::pair<HalfEdgeHalfFaceIter, HalfEdgeHalfFaceIter> halfedge_halffaces(const HalfEdgeHandle& _h, int _max_laps = 1) const {
        HalfEdgeHalfFaceIter begin = hehf_iter(_h, _max_laps);
        return std::make_pair(begin, make_end_circulator(begin));
    }

150
151
152
153
154
155
156
157
158
    VertexFaceIter vf_iter(const VertexHandle& _h, int _max_laps = 1) const {
        return VertexFaceIter(_h, this, _max_laps);
    }

    std::pair<VertexFaceIter, VertexFaceIter> vertex_faces(const VertexHandle& _h, int _max_laps = 1) const {
        VertexFaceIter begin = vf_iter(_h, _max_laps);
        return std::make_pair(begin, make_end_circulator(begin));
    }

Max Lyon's avatar
Max Lyon committed
159
160
161
162
    VertexCellIter vc_iter(const VertexHandle& _h, int _max_laps = 1) const {
        return VertexCellIter(_h, this, _max_laps);
    }

163
    std::pair<VertexCellIter, VertexCellIter> vertex_cells(const VertexHandle& _h, int _max_laps = 1) const {
Max Lyon's avatar
Max Lyon committed
164
165
166
167
168
169
        VertexCellIter begin = vc_iter(_h, _max_laps);
        return std::make_pair(begin, make_end_circulator(begin));
    }

    HalfEdgeCellIter hec_iter(const HalfEdgeHandle& _h, int _max_laps = 1) const {
        return HalfEdgeCellIter(_h, this, _max_laps);
170
171
    }

172
    std::pair<HalfEdgeCellIter, HalfEdgeCellIter> halfedge_cells(const HalfEdgeHandle& _h, int _max_laps = 1) const {
Max Lyon's avatar
Max Lyon committed
173
174
        HalfEdgeCellIter begin = hec_iter(_h, _max_laps);
        return std::make_pair(begin, make_end_circulator(begin));
175
176
    }

Max Lyon's avatar
Max Lyon committed
177
178
    CellVertexIter cv_iter(const CellHandle& _h, int _max_laps = 1) const {
        return CellVertexIter(_h, this, _max_laps);
179
180
    }

Max Lyon's avatar
Max Lyon committed
181
182
183
    std::pair<CellVertexIter, CellVertexIter> cell_vertices(const CellHandle& _h, int _max_laps = 1) const {
        CellVertexIter begin = cv_iter(_h, _max_laps);
        return std::make_pair(begin, make_end_circulator(begin));
184
185
    }

Max Lyon's avatar
Max Lyon committed
186
187
    CellCellIter cc_iter(const CellHandle& _h, int _max_laps = 1) const {
        return CellCellIter(_h, this, _max_laps);
188
189
    }

Max Lyon's avatar
Max Lyon committed
190
191
192
    std::pair<CellCellIter, CellCellIter> cell_cells(const CellHandle& _h, int _max_laps = 1) const {
        CellCellIter begin = cc_iter(_h, _max_laps);
        return std::make_pair(begin, make_end_circulator(begin));
193
194
    }

Max Lyon's avatar
Max Lyon committed
195
196
    HalfFaceVertexIter hfv_iter(const HalfFaceHandle& _h, int _max_laps = 1) const {
        return HalfFaceVertexIter(_h, this, _max_laps);
Mike Kremer's avatar
Mike Kremer committed
197
198
    }

Max Lyon's avatar
Max Lyon committed
199
200
201
    std::pair<HalfFaceVertexIter, HalfFaceVertexIter> halfface_vertices(const HalfFaceHandle& _h, int _max_laps = 1) const {
        HalfFaceVertexIter begin = hfv_iter(_h, _max_laps);
        return std::make_pair(begin, make_end_circulator(begin));
202
203
    }

Max Lyon's avatar
Max Lyon committed
204
205
206
207
208
209
210
211
212
213
214
215
216
    BoundaryHalfFaceHalfFaceIter bhfhf_iter(const HalfFaceHandle& _ref_h, int _max_laps = 1) const {
        return BoundaryHalfFaceHalfFaceIter(_ref_h, this, _max_laps);
    }

    std::pair<BoundaryHalfFaceHalfFaceIter, BoundaryHalfFaceHalfFaceIter> boundary_halfface_halffaces(const HalfFaceHandle& _h, int _max_laps = 1) const {
        BoundaryHalfFaceHalfFaceIter begin = bhfhf_iter(_h, _max_laps);
        return std::make_pair(begin, make_end_circulator(begin));
    }

    /*
     * Iterators
     */

217
218
219
220
221
222
223
224
225
226
227
228
229
    BoundaryFaceIter bf_iter() const {
        return BoundaryFaceIter(this);
    }

    VertexIter v_iter() const {
        return VertexIter(this);
    }

    VertexIter vertices_begin() const {
        return VertexIter(this, VertexHandle(0));
    }

    VertexIter vertices_end() const {
Max Lyon's avatar
Max Lyon committed
230
        return VertexIter(this, VertexHandle((int)n_vertices()));
231
232
    }

Max Lyon's avatar
Max Lyon committed
233
234
235
236
    std::pair<VertexIter, VertexIter> vertices() const {
        return std::make_pair(vertices_begin(), vertices_end());
    }

237
238
239
240
241
242
243
244
245
    EdgeIter e_iter() const {
        return EdgeIter(this);
    }

    EdgeIter edges_begin() const {
        return EdgeIter(this, EdgeHandle(0));
    }

    EdgeIter edges_end() const {
Max Lyon's avatar
Max Lyon committed
246
        return EdgeIter(this, EdgeHandle((int)edges_.size()));
247
248
    }

Max Lyon's avatar
Max Lyon committed
249
250
251
252
    std::pair<EdgeIter, EdgeIter> edges() const {
        return std::make_pair(edges_begin(), edges_end());
    }

253
254
255
256
257
258
259
260
261
    HalfEdgeIter he_iter() const {
        return HalfEdgeIter(this);
    }

    HalfEdgeIter halfedges_begin() const {
        return HalfEdgeIter(this, HalfEdgeHandle(0));
    }

    HalfEdgeIter halfedges_end() const {
Max Lyon's avatar
Max Lyon committed
262
        return HalfEdgeIter(this, HalfEdgeHandle((int)edges_.size() * 2));
263
264
    }

Max Lyon's avatar
Max Lyon committed
265
266
267
268
    std::pair<HalfEdgeIter, HalfEdgeIter> halfedges() const {
        return std::make_pair(halfedges_begin(), halfedges_end());
    }

269
270
271
272
273
274
275
276
277
    FaceIter f_iter() const {
        return FaceIter(this);
    }

    FaceIter faces_begin() const {
        return FaceIter(this, FaceHandle(0));
    }

    FaceIter faces_end() const {
Max Lyon's avatar
Max Lyon committed
278
        return FaceIter(this, FaceHandle((int)faces_.size()));
279
280
    }

Max Lyon's avatar
Max Lyon committed
281
282
283
284
    std::pair<FaceIter, FaceIter> faces() const {
        return std::make_pair(faces_begin(), faces_end());
    }

285
286
287
288
289
290
291
292
293
    HalfFaceIter hf_iter() const {
        return HalfFaceIter(this);
    }

    HalfFaceIter halffaces_begin() const {
        return HalfFaceIter(this, HalfFaceHandle(0));
    }

    HalfFaceIter halffaces_end() const {
Max Lyon's avatar
Max Lyon committed
294
        return HalfFaceIter(this, HalfFaceHandle((int)faces_.size() * 2));
295
296
    }

Max Lyon's avatar
Max Lyon committed
297
298
299
300
    std::pair<HalfFaceIter, HalfFaceIter> halffaces() const {
        return std::make_pair(halffaces_begin(), halffaces_end());
    }

301
302
303
304
305
306
307
308
309
    CellIter c_iter() const {
        return CellIter(this);
    }

    CellIter cells_begin() const {
        return CellIter(this, CellHandle(0));
    }

    CellIter cells_end() const {
Max Lyon's avatar
Max Lyon committed
310
        return CellIter(this, CellHandle((int)cells_.size()));
311
312
    }

Max Lyon's avatar
Max Lyon committed
313
314
315
316
    std::pair<CellIter, CellIter> cells() const {
        return std::make_pair(cells_begin(), cells_end());
    }

317
318
319
320
321
    /*
     * Virtual functions with implementation
     */

    /// Get number of vertices in mesh
322
    virtual size_t n_vertices()   const { return n_vertices_; }
323
    /// Get number of edges in mesh
324
    virtual size_t n_edges()      const { return edges_.size(); }
325
    /// Get number of halfedges in mesh
326
    virtual size_t n_halfedges()  const { return edges_.size() * 2u; }
327
    /// Get number of faces in mesh
328
    virtual size_t n_faces()      const { return faces_.size(); }
329
    /// Get number of halffaces in mesh
330
    virtual size_t n_halffaces()  const { return faces_.size() * 2u; }
331
    /// Get number of cells in mesh
332
    virtual size_t n_cells()      const { return cells_.size(); }
333

334
335
    int genus() const {

Max Lyon's avatar
Max Lyon committed
336
337
338
339
        int g = (1 - (int)(n_vertices() -
                           n_edges() +
                           n_faces() -
                           n_cells()));
340
341
342
343
344
345

        if(g % 2 == 0) return (g / 2);

        // An error occured
        // The mesh might not be manifold
        return  -1;
346
347
    }

348
349
private:

350
    // Cache total vertex number
351
    size_t n_vertices_;
352
353

public:
354
355

    /// Add abstract vertex
356
    virtual VertexHandle add_vertex();
357
358
359
360

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

    /// Add edge
361
    virtual EdgeHandle add_edge(const VertexHandle& _fromVertex, const VertexHandle& _toHandle, bool _allowDuplicates = false);
362
363

    /// Add face via incident edges
364
365
366
367
368
369
    ///
    /// \return Handle of the new face, InvalidFaceHandle if \a _halfedges
    ///         are not connected and \a _topologyCheck is \a true.
    ///
    /// \warning If _halfedges are not connected and \a _topologyCheck is \a false,
    ///          the behavior is undefined.
370
    virtual FaceHandle add_face(const std::vector<HalfEdgeHandle>& _halfedges, bool _topologyCheck = false);
371
372
373
374
375

    /// Add face via incident vertices
    virtual FaceHandle add_face(const std::vector<VertexHandle>& _vertices);

    /// Add cell via incident halffaces
376
377
378
379
380
381
    ///
    /// \return Handle of the new cell, InvalidCellHandle if \a _topologyCheck is \a true and
    ///         \a _halffaces are not connected.
    ///
    /// \warning If _halffaces are not connected and \a _topologyCheck is \a false,
    ///          the behavior is undefined.
382
    virtual CellHandle add_cell(const std::vector<HalfFaceHandle>& _halffaces, bool _topologyCheck = false);
383

384
385
386
387
388
389
390
391
392
    /// Set the vertices of an edge
    void set_edge(const EdgeHandle& _eh, const VertexHandle& _fromVertex, const VertexHandle& _toVertex);

    /// Set the half-edges of a face
    void set_face(const FaceHandle& _fh, const std::vector<HalfEdgeHandle>& _hes);

    /// Set the half-faces of a cell
    void set_cell(const CellHandle& _ch, const std::vector<HalfFaceHandle>& _hfs);

393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
    /*
     * Non-virtual functions
     */

    /// Get edge with handle _edgeHandle
    const Edge& edge(const EdgeHandle& _edgeHandle) const;

    /// Get face with handle _faceHandle
    const Face& face(const FaceHandle& _faceHandle) const;

    /// Get cell with handle _cellHandle
    const Cell& cell(const CellHandle& _cellHandle) const;

    /// Get edge with handle _edgeHandle
    Edge& edge(const EdgeHandle& _edgeHandle);

    /// Get face with handle _faceHandle
    Face& face(const FaceHandle& _faceHandle);

    /// Get cell with handle _cellHandle
    Cell& cell(const CellHandle& _cellHandle);

    /// Get edge that corresponds to halfedge with handle _halfEdgeHandle
416
    Edge halfedge(const HalfEdgeHandle& _halfEdgeHandle) const;
417
418

    /// Get face that corresponds to halfface with handle _halfFaceHandle
419
    Face halfface(const HalfFaceHandle& _halfFaceHandle) const;
420
421

    /// Get opposite halfedge that corresponds to halfedge with handle _halfEdgeHandle
422
    Edge opposite_halfedge(const HalfEdgeHandle& _halfEdgeHandle) const;
423
424

    /// Get opposite halfface that corresponds to halfface with handle _halfFaceHandle
425
    Face opposite_halfface(const HalfFaceHandle& _halfFaceHandle) const;
426

427
    /// Get halfedge from vertex _vh1 to _vh2
428
    HalfEdgeHandle halfedge(const VertexHandle& _vh1, const VertexHandle& _vh2) const;
429

430
431
432
    /// Get half-face from list of incident vertices (in connected order)
    ///
    /// \note Only the first three vertices are checked
433
    HalfFaceHandle halfface(const std::vector<VertexHandle>& _vs) const;
434

435
436
437
438
439
    /// Get half-face from list of incident vertices (in connected order)
    ///
    /// \note All vertices are checked
    HalfFaceHandle halfface_extensive(const std::vector<VertexHandle>& _vs) const;

440
441
442
    /// Get half-face from list of incident half-edges
    ///
    /// \note Only the first two half-edges are checked
443
    HalfFaceHandle halfface(const std::vector<HalfEdgeHandle>& _hes) const;
444

445
    /// Get next halfedge within a halfface
446
    HalfEdgeHandle next_halfedge_in_halfface(const HalfEdgeHandle& _heh, const HalfFaceHandle& _hfh) const;
447
448

    /// Get previous halfedge within a halfface
449
    HalfEdgeHandle prev_halfedge_in_halfface(const HalfEdgeHandle& _heh, const HalfFaceHandle& _hfh) const;
450
451

    /// Get valence of vertex (number of incident edges)
452
    inline size_t valence(const VertexHandle& _vh) const {
453
454
455
        assert(has_vertex_bottom_up_incidences());
        assert(_vh.is_valid() && (size_t)_vh.idx() < outgoing_hes_per_vertex_.size());

456
457
458
459
        return outgoing_hes_per_vertex_[_vh.idx()].size();
    }

    /// Get valence of edge (number of incident faces)
460
    inline size_t valence(const EdgeHandle& _eh) const {
461
462
        assert(has_edge_bottom_up_incidences());
        assert(_eh.is_valid() && (size_t)_eh.idx() < edges_.size());
463
        assert((size_t)halfedge_handle(_eh, 0).idx() < incident_hfs_per_he_.size());
464

465
        return incident_hfs_per_he_[halfedge_handle(_eh, 0).idx()].size();
466
467
468
    }

    /// Get valence of face (number of incident edges)
469
    inline size_t valence(const FaceHandle& _fh) const {
470
        assert(_fh.is_valid() && (size_t)_fh.idx() < faces_.size());
471
472
473
474
475

        return face(_fh).halfedges().size();
    }

    /// Get valence of cell (number of incident faces)
476
    inline size_t valence(const CellHandle& _ch) const {
477
        assert(_ch.is_valid() && (size_t)_ch.idx() < cells_.size());
478
479
480
481

        return cell(_ch).halffaces().size();
    }

482
483
484
    //=====================================================================
    // Delete entities
    //=====================================================================
485

486
public:
487

488
    virtual VertexIter delete_vertex(const VertexHandle& _h);
489

490
    virtual EdgeIter delete_edge(const EdgeHandle& _h);
491

492
    virtual FaceIter delete_face(const FaceHandle& _h);
493

494
    virtual CellIter delete_cell(const CellHandle& _h);
495

496
497
498
499
500
501
502
503
504
505
    virtual void collect_garbage();


    virtual bool is_deleted(const VertexHandle& _h)   const { return vertex_deleted_[_h.idx()]; }
    virtual bool is_deleted(const EdgeHandle& _h)     const { return edge_deleted_[_h.idx()];   }
    virtual bool is_deleted(const HalfEdgeHandle& _h) const { return edge_deleted_[_h.idx()/2]; }
    virtual bool is_deleted(const FaceHandle& _h)     const { return face_deleted_[_h.idx()];   }
    virtual bool is_deleted(const HalfFaceHandle& _h) const { return face_deleted_[_h.idx()/2]; }
    virtual bool is_deleted(const CellHandle& _h)     const { return cell_deleted_[_h.idx()];   }

506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
private:

    template <class ContainerT>
    void get_incident_edges(const ContainerT& _vs, std::set<EdgeHandle>& _es) const;

    template <class ContainerT>
    void get_incident_faces(const ContainerT& _es, std::set<FaceHandle>& _fs) const;

    template <class ContainerT>
    void get_incident_cells(const ContainerT& _fs, std::set<CellHandle>& _cs) const;

    VertexIter delete_vertex_core(const VertexHandle& _h);

    EdgeIter delete_edge_core(const EdgeHandle& _h);

    FaceIter delete_face_core(const FaceHandle& _h);

    CellIter delete_cell_core(const CellHandle& _h);

525
public:
526

527
528
    /// Exchanges the indices of two cells while keeping the mesh otherwise unaffected.
    virtual void swap_cell_indices(CellHandle _h1, CellHandle _h2);
529

530
531
    /// Exchanges the indices of two faces while keeping the mesh otherwise unaffected.
    virtual void swap_face_indices(FaceHandle _h1, FaceHandle _h2);
532

533
534
    /// Exchanges the indices of two edges while keeping the mesh otherwise unaffected.
    virtual void swap_edge_indices(EdgeHandle _h1, EdgeHandle _h2);
535

536
537
538
539
    /// Exchanges the indices of two vertices while keeping the mesh otherwise unaffected.
    virtual void swap_vertex_indices(VertexHandle _h1, VertexHandle _h2);

protected:
540

541
542
543
544
545
546
547
548
549
550
    virtual void delete_multiple_vertices(const std::vector<bool>& _tag);

    virtual void delete_multiple_edges(const std::vector<bool>& _tag);

    virtual void delete_multiple_faces(const std::vector<bool>& _tag);

    virtual void delete_multiple_cells(const std::vector<bool>& _tag);

    class EdgeCorrector {
    public:
Jan Möbius's avatar
Jan Möbius committed
551
        explicit EdgeCorrector(const std::vector<int>& _newIndices) :
552
553
554
555
556
557
558
559
560
561
562
563
            newIndices_(_newIndices) {}

        void operator()(Edge& _edge) {
            _edge.set_from_vertex(VertexHandle(newIndices_[_edge.from_vertex().idx()]));
            _edge.set_to_vertex(VertexHandle(newIndices_[_edge.to_vertex().idx()]));
        }
    private:
        const std::vector<int>& newIndices_;
    };

    class FaceCorrector {
    public:
Jan Möbius's avatar
Jan Möbius committed
564
        explicit FaceCorrector(const std::vector<int>& _newIndices) :
565
566
567
568
569
570
571
572
573
            newIndices_(_newIndices) {}

        void operator()(Face& _face) {
            std::vector<HalfEdgeHandle> hes = _face.halfedges();
            for(std::vector<HalfEdgeHandle>::iterator he_it = hes.begin(),
                    he_end = hes.end(); he_it != he_end; ++he_it) {

                EdgeHandle eh = edge_handle(*he_it);
                unsigned char opp = (he_it->idx() - halfedge_handle(eh, 0).idx());
Max Lyon's avatar
Max Lyon committed
574
                *he_it = halfedge_handle(EdgeHandle(newIndices_[eh.idx()]), opp);
575
576
577
578
579
580
581
582
583
            }
            _face.set_halfedges(hes);
        }
    private:
        const std::vector<int>& newIndices_;
    };

    class CellCorrector {
    public:
Jan Möbius's avatar
Jan Möbius committed
584
        explicit CellCorrector(const std::vector<int>& _newIndices) :
585
586
587
588
589
590
591
592
593
            newIndices_(_newIndices) {}

        void operator()(Cell& _cell) {
            std::vector<HalfFaceHandle> hfs = _cell.halffaces();
            for(std::vector<HalfFaceHandle>::iterator hf_it = hfs.begin(),
                    hf_end = hfs.end(); hf_it != hf_end; ++hf_it) {

                FaceHandle fh = face_handle(*hf_it);
                unsigned char opp = (hf_it->idx() - halfface_handle(fh, 0).idx());
Max Lyon's avatar
Max Lyon committed
594
                *hf_it = halfface_handle(FaceHandle(newIndices_[fh.idx()]), opp);
595
596
597
598
599
600
601
602
603
            }
            _cell.set_halffaces(hfs);
        }
    private:
        const std::vector<int>& newIndices_;
    };

public:

604
605
606
607
    /** \brief Delete range of cells
     *
     * Deletes all cells in range [_first, _last].
     *
608
609
610
     * @param _first Iterator to first cell that is to be deleted
     * @param _last Iterator to last cell that is to be deleted
     * @return An iterator to the first cell after the deleted range
611
612
613
     */
    CellIter delete_cell_range(const CellIter& _first, const CellIter& _last);

614
public:
615
616

    /// Clear whole mesh
617
    virtual void clear(bool _clearProps = true) {
618
619
620
621

        edges_.clear();
        faces_.clear();
        cells_.clear();
622
623
624
625
        vertex_deleted_.clear();
        edge_deleted_.clear();
        face_deleted_.clear();
        cell_deleted_.clear();
626
627
628
        outgoing_hes_per_vertex_.clear();
        incident_hfs_per_he_.clear();
        incident_cell_per_hf_.clear();
Mike Kremer's avatar
Mike Kremer committed
629
        n_vertices_ = 0;
630

631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
        if(_clearProps) {

            // Delete all property data
            clear_vertex_props();
            clear_edge_props();
            clear_halfedge_props();
            clear_face_props();
            clear_halfface_props();
            clear_cell_props();
            clear_mesh_props();

        } else {
            // Resize props
            resize_vprops(0u);
            resize_eprops(0u);
            resize_fprops(0u);
            resize_cprops(0u);
        }
649
650
651
    }

    //=====================================================================
652
    // Bottom-up Incidences
653
654
    //=====================================================================

655
656
public:

657
    void enable_bottom_up_incidences(bool _enable = true) {
658

659
660
661
        enable_vertex_bottom_up_incidences(_enable);
        enable_edge_bottom_up_incidences(_enable);
        enable_face_bottom_up_incidences(_enable);
662
663
    }

664
    void enable_vertex_bottom_up_incidences(bool _enable = true) {
665
666

        if(_enable && !v_bottom_up_) {
667
            // Vertex bottom-up incidences have to be
668
            // recomputed for the whole mesh
669
            compute_vertex_bottom_up_incidences();
670
        }
671

672
673
674
675
        if(!_enable) {
            outgoing_hes_per_vertex_.clear();
        }

676
677
        v_bottom_up_ = _enable;
    }
678

679
    void enable_edge_bottom_up_incidences(bool _enable = true) {
680

681
        if(_enable && !e_bottom_up_) {
682
            // Edge bottom-up incidences have to be
683
            // recomputed for the whole mesh
684
            compute_edge_bottom_up_incidences();
685
686

            if(f_bottom_up_) {
Jan Möbius's avatar
Jan Möbius committed
687
#if defined(__clang_major__) && (__clang_major__ >= 5)
688
689
690
691
692
                for(EdgeIter e_it = edges_begin(), e_end = edges_end();
                    e_it != e_end; ++e_it) {
                    reorder_incident_halffaces(*e_it);
                }
#else
693
                std::for_each(edges_begin(), edges_end(),
694
                              fun::bind(&TopologyKernel::reorder_incident_halffaces, this, fun::placeholders::_1));
695
#endif
696
697
698
            }
        }

699
700
701
702
        if(!_enable) {
            incident_hfs_per_he_.clear();
        }

703
704
705
        e_bottom_up_ = _enable;
    }

706
    void enable_face_bottom_up_incidences(bool _enable = true) {
707

708
        bool updateOrder = false;
709
        if(_enable && !f_bottom_up_) {
710
            // Face bottom-up incidences have to be
711
            // recomputed for the whole mesh
712
            compute_face_bottom_up_incidences();
713

714
            updateOrder = true;
715
716
        }

717
718
719
720
        if(!_enable) {
            incident_cell_per_hf_.clear();
        }

721
        f_bottom_up_ = _enable;
722
723
724

        if(updateOrder) {
            if(e_bottom_up_) {
Jan Möbius's avatar
Jan Möbius committed
725
#if defined(__clang_major__) && (__clang_major__ >= 5)
726
727
728
729
730
                for(EdgeIter e_it = edges_begin(), e_end = edges_end();
                    e_it != e_end; ++e_it) {
                    reorder_incident_halffaces(*e_it);
                }
#else
731
                std::for_each(edges_begin(), edges_end(),
732
                              fun::bind(&TopologyKernel::reorder_incident_halffaces, this, fun::placeholders::_1));
733
#endif
734
735
            }
        }
736
737
    }

738
739
740
741
    bool has_full_bottom_up_incidences() const {
        return (has_vertex_bottom_up_incidences() &&
                has_edge_bottom_up_incidences() &&
                has_face_bottom_up_incidences());
742
743
    }

744
    bool has_vertex_bottom_up_incidences() const { return v_bottom_up_; }
745

746
    bool has_edge_bottom_up_incidences() const { return e_bottom_up_; }
747

748
    bool has_face_bottom_up_incidences() const { return f_bottom_up_; }
749

750

751
    void enable_deferred_deletion(bool _enable = true);
752
753
754
755
756
757
758
759
    bool deferred_deletion_enabled() const { return deferred_deletion; }


    void enable_fast_deletion(bool _enable = true) { fast_deletion = _enable; }
    bool fast_deletion_enabled() const { return fast_deletion; }


protected:
760

761
    void compute_vertex_bottom_up_incidences();
762

763
    void compute_edge_bottom_up_incidences();
764

765
    void compute_face_bottom_up_incidences();
766
767
768
769
770
771
772
773
774
775
776
777

    void reorder_incident_halffaces(const EdgeHandle& _eh);

    // Outgoing halfedges per vertex
    std::vector<std::vector<HalfEdgeHandle> > outgoing_hes_per_vertex_;

    // Incident halffaces per (directed) halfedge
    std::vector<std::vector<HalfFaceHandle> > incident_hfs_per_he_;

    // Incident cell (at most one) per halfface
    std::vector<CellHandle> incident_cell_per_hf_;

778
private:
779
780
781
782
783
    bool v_bottom_up_;

    bool e_bottom_up_;

    bool f_bottom_up_;
784

785
786
787
788
    bool deferred_deletion;

    bool fast_deletion;

789
790
791
792
    //=====================================================================
    // Connectivity
    //=====================================================================

793
794
public:

795
796
797
798
799
800
    /// \brief Get halfface that is adjacent (w.r.t. a common halfedge) within the same cell
    ///
    /// \return Handle of the adjacent half-face if \a _halfFaceHandle is not
    ///         at a boundary, \a InvalidHalfFaceHandle otherwise.
    ///
    /// \warning The mesh must have face bottom-up incidences.
801
802
803
804
805
806
    HalfFaceHandle adjacent_halfface_in_cell(const HalfFaceHandle& _halfFaceHandle, const HalfEdgeHandle& _halfEdgeHandle) const;

    /// Get cell that is incident to the given halfface
    CellHandle incident_cell(const HalfFaceHandle& _halfFaceHandle) const;

    bool is_boundary(const HalfFaceHandle& _halfFaceHandle) const {
807
808
809
810
811

        assert(_halfFaceHandle.is_valid() && (size_t)_halfFaceHandle.idx() < faces_.size() * 2u);
        assert(has_face_bottom_up_incidences());
        assert((size_t)_halfFaceHandle.idx() < incident_cell_per_hf_.size());
        return incident_cell_per_hf_[_halfFaceHandle.idx()] == InvalidCellHandle;
812
813
814
    }

    bool is_boundary(const FaceHandle& _faceHandle) const {
815
816
        assert(_faceHandle.is_valid() && (size_t)_faceHandle.idx() < faces_.size());
        assert(has_face_bottom_up_incidences());
817
818
819
820
821
        return  is_boundary(halfface_handle(_faceHandle, 0)) ||
                is_boundary(halfface_handle(_faceHandle, 1));
    }

    bool is_boundary(const EdgeHandle& _edgeHandle) const {
822
823
824
        assert(has_edge_bottom_up_incidences());
        assert(_edgeHandle.is_valid() && (size_t)_edgeHandle.idx() < edges_.size());

825
826
827
828
829
830
831
832
833
834
        for(HalfEdgeHalfFaceIter hehf_it = hehf_iter(halfedge_handle(_edgeHandle, 0));
                hehf_it.valid(); ++hehf_it) {
            if(is_boundary(face_handle(*hehf_it))) {
                return true;
            }
        }
        return false;
    }

    bool is_boundary(const HalfEdgeHandle& _halfedgeHandle) const {
835
836
837
        assert(has_edge_bottom_up_incidences());
        assert(_halfedgeHandle.is_valid() && (size_t)_halfedgeHandle.idx() < edges_.size() * 2u);

838
839
840
841
842
843
844
845
846
847
        for(HalfEdgeHalfFaceIter hehf_it = hehf_iter(_halfedgeHandle);
                hehf_it.valid(); ++hehf_it) {
            if(is_boundary(face_handle(*hehf_it))) {
                return true;
            }
        }
        return false;
    }

    bool is_boundary(const VertexHandle& _vertexHandle) const {
848
849
850
        assert(has_vertex_bottom_up_incidences());
        assert(_vertexHandle.is_valid() && (size_t)_vertexHandle.idx() < n_vertices());

851
852
853
854
855
856
        for(VertexOHalfEdgeIter voh_it = voh_iter(_vertexHandle); voh_it.valid(); ++voh_it) {
            if(is_boundary(*voh_it)) return true;
        }
        return false;
    }

857
    size_t n_vertices_in_cell(const CellHandle& _ch) const {
858
        assert(_ch.is_valid() && (size_t)_ch.idx() < cells_.size());
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878

        std::set<VertexHandle> vertices;
        std::vector<HalfFaceHandle> hfs = cell(_ch).halffaces();
        for(std::vector<HalfFaceHandle>::const_iterator hf_it = hfs.begin();
                hf_it != hfs.end(); ++hf_it) {
            std::vector<HalfEdgeHandle> hes = halfface(*hf_it).halfedges();
            for(std::vector<HalfEdgeHandle>::const_iterator he_it = hes.begin();
                he_it != hes.end(); ++he_it) {
                vertices.insert(halfedge(*he_it).to_vertex());
            }
        }
        return vertices.size();
    }

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

    /*
     * Non-virtual functions
     */

879
    Edge opposite_halfedge(const Edge& _edge) const {
880
881
882
        return Edge(_edge.to_vertex(), _edge.from_vertex());
    }

883
    Face opposite_halfface(const Face& _face) const {
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
        std::vector<HalfEdgeHandle> opp_halfedges;
        for(std::vector<HalfEdgeHandle>::const_iterator it = _face.halfedges().begin(); it
                != _face.halfedges().end(); ++it) {
            opp_halfedges.insert(opp_halfedges.begin(), opposite_halfedge_handle(*it));
        }

        return Face(opp_halfedges);
    }

    /*
     * Static functions
     */

    /// Conversion function
    static inline HalfEdgeHandle halfedge_handle(const EdgeHandle& _h, const unsigned char _subIdx) {
        // Is handle in range?
900
901
902
        assert(_h.is_valid());
        assert(_subIdx < 2);
        // if(_h.idx() < 0 || _subIdx > 1) return InvalidHalfEdgeHandle;
903
904
905
906
907
908
        return HalfEdgeHandle((2 * _h.idx()) + (_subIdx ? 1 : 0));
    }

    /// Conversion function
    static inline HalfFaceHandle halfface_handle(const FaceHandle& _h, const unsigned char _subIdx) {
        // Is handle in range?
909
910
911
        assert(_h.is_valid());
        assert(_subIdx < 2);
        // if(_h.idx() < 0 || _subIdx > 1) return InvalidHalfFaceHandle;
912
        return HalfFaceHandle((2 * _h.idx()) + (_subIdx ? 1 : 0));
913
914
915
916
917
    }

    /// Handle conversion
    static inline EdgeHandle edge_handle(const HalfEdgeHandle& _h) {
        // Is handle in range?
918
919
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidEdgeHandle;
920
921
922
923
924
        return EdgeHandle((int)(_h.idx() / 2));
    }

    static inline FaceHandle face_handle(const HalfFaceHandle& _h) {
        // Is handle in range?
925
926
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidFaceHandle;
927
928
929
930
931
        return FaceHandle((int)(_h.idx() / 2));
    }

    static inline HalfEdgeHandle opposite_halfedge_handle(const HalfEdgeHandle& _h) {
        // Is handle in range?
932
933
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidHalfEdgeHandle;
934
935
936
937
938
939
940
941
942
943

        // Is handle even?
        if(_h.idx() % 2 == 0) {
            return HalfEdgeHandle(_h.idx() + 1);
        }
        return HalfEdgeHandle(_h.idx() - 1);
    }

    static inline HalfFaceHandle opposite_halfface_handle(const HalfFaceHandle& _h) {
        // Is handle in range?
944
945
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidHalfFaceHandle;
946
947
948
949
950
951
952
953

        // Is handle even?
        if(_h.idx() % 2 == 0) {
            return HalfFaceHandle(_h.idx() + 1);
        }
        return HalfFaceHandle(_h.idx() - 1);
    }

954
955
956
957
    bool inline needs_garbage_collection() const {
        return needs_garbage_collection_;
    }

958
959
960
961
962
963
964
965
966
967
protected:

    // List of edges
    std::vector<Edge> edges_;

    // List of faces
    std::vector<Face> faces_;

    // List of cells
    std::vector<Cell> cells_;
968
969
970
971
972

    std::vector<bool> vertex_deleted_;
    std::vector<bool> edge_deleted_;
    std::vector<bool> face_deleted_;
    std::vector<bool> cell_deleted_;
973
    bool needs_garbage_collection_;
974

975
976
977
978
979
};

}

#endif /* TOPOLOGYKERNEL_HH_ */