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

#ifndef TOPOLOGYKERNEL_HH_
#define TOPOLOGYKERNEL_HH_

38
#include <cassert>
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <set>
#include <vector>

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

namespace OpenVolumeMesh {

class TopologyKernel : public ResourceManager {
public:

52
    TopologyKernel() = default;
53
    ~TopologyKernel() override = default;
54
55
56

    TopologyKernel& operator=(const TopologyKernel&) = default;

57
58
59
    void assign(const TopologyKernel *other) {
        *this = *other;
    }
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

    /*
     * 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;

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

81
82
83
84
85
    //=====================================================================
    // Iterators
    //=====================================================================

    friend class VertexOHalfEdgeIter;
86
    friend class VertexVertexIter;
87
    friend class HalfEdgeHalfFaceIter;
88
    friend class VertexFaceIter;
89
90
91
92
    friend class VertexCellIter;
    friend class HalfEdgeCellIter;
    friend class CellVertexIter;
    friend class CellCellIter;
Mike Kremer's avatar
Mike Kremer committed
93
    friend class HalfFaceVertexIter;
94
    friend class BoundaryHalfFaceHalfFaceIter;
95
96
97
98
99
100
101
102
    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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
    /*
     * 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));
128
129
130
131
132
133
134
135
136
    }

    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
137
138
139
140
141
142
143
144
145
146
147
    }

    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));
    }

148
149
150
151
152
153
154
155
156
    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
157
158
159
160
    VertexCellIter vc_iter(const VertexHandle& _h, int _max_laps = 1) const {
        return VertexCellIter(_h, this, _max_laps);
    }

161
    std::pair<VertexCellIter, VertexCellIter> vertex_cells(const VertexHandle& _h, int _max_laps = 1) const {
Max Lyon's avatar
Max Lyon committed
162
163
164
165
166
167
        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);
168
169
    }

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

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

Max Lyon's avatar
Max Lyon committed
179
180
181
    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));
182
183
    }

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

Max Lyon's avatar
Max Lyon committed
188
189
190
    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));
191
192
    }

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

Max Lyon's avatar
Max Lyon committed
197
198
199
    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));
200
201
    }

Max Lyon's avatar
Max Lyon committed
202
203
204
205
206
207
208
209
210
211
212
213
214
    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
     */

215
216
217
218
219
220
221
222
223
224
225
226
227
    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
228
        return VertexIter(this, VertexHandle((int)n_vertices()));
229
230
    }

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

235
236
237
238
239
240
241
242
243
    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
244
        return EdgeIter(this, EdgeHandle((int)edges_.size()));
245
246
    }

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

251
252
253
254
255
256
257
258
259
    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
260
        return HalfEdgeIter(this, HalfEdgeHandle((int)edges_.size() * 2));
261
262
    }

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

267
268
269
270
271
272
273
274
275
    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
276
        return FaceIter(this, FaceHandle((int)faces_.size()));
277
278
    }

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

283
284
285
286
287
288
289
290
291
    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
292
        return HalfFaceIter(this, HalfFaceHandle((int)faces_.size() * 2));
293
294
    }

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

299
300
301
302
303
304
305
306
307
    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
308
        return CellIter(this, CellHandle((int)cells_.size()));
309
310
    }

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

315
316
317
318
319
    /*
     * Virtual functions with implementation
     */

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

332
333
334
335
336
337
338
339
340
341
342
343
344
    /// Get number of undeleted vertices in mesh
    size_t n_logical_vertices()   const { return n_vertices_ - n_deleted_vertices_; }
    /// Get number of undeleted edges in mesh
    size_t n_logical_edges()      const { return edges_.size() - n_deleted_edges_; }
    /// Get number of undeleted halfedges in mesh
    size_t n_logical_halfedges()  const { return n_logical_edges() * 2u; }
    /// Get number of undeleted faces in mesh
    size_t n_logical_faces()      const { return faces_.size() - n_deleted_faces_; }
    /// Get number of undeleted halffaces in mesh
    size_t n_logical_halffaces()  const { return n_faces() * 2u; }
    /// Get number of undeleted cells in mesh
    size_t n_logical_cells()      const { return cells_.size() - n_deleted_cells_; }

345
346
    int genus() const {

Max Lyon's avatar
Max Lyon committed
347
348
349
350
        int g = (1 - (int)(n_vertices() -
                           n_edges() +
                           n_faces() -
                           n_cells()));
351
352
353
354
355
356

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

        // An error occured
        // The mesh might not be manifold
        return  -1;
357
358
    }

359
360
private:

361
    // Cache total vertex number
362
    size_t n_vertices_ = 0u;
363
364

public:
365
366

    /// Add abstract vertex
367
    virtual VertexHandle add_vertex();
368
369
370
371

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

    /// Add edge
372
    virtual EdgeHandle add_edge(const VertexHandle& _fromVertex, const VertexHandle& _toHandle, bool _allowDuplicates = false);
373
374

    /// Add face via incident edges
375
376
377
378
379
380
    ///
    /// \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.
381
    virtual FaceHandle add_face(const std::vector<HalfEdgeHandle>& _halfedges, bool _topologyCheck = false);
382
383
384
385
386

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

    /// Add cell via incident halffaces
387
388
389
390
391
392
    ///
    /// \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.
393
    virtual CellHandle add_cell(const std::vector<HalfFaceHandle>& _halffaces, bool _topologyCheck = false);
394

395
396
397
398
399
400
401
402
403
    /// 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);

404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
    /*
     * 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
427
    Edge halfedge(const HalfEdgeHandle& _halfEdgeHandle) const;
428
429

    /// Get face that corresponds to halfface with handle _halfFaceHandle
430
    Face halfface(const HalfFaceHandle& _halfFaceHandle) const;
431
432

    /// Get opposite halfedge that corresponds to halfedge with handle _halfEdgeHandle
433
    Edge opposite_halfedge(const HalfEdgeHandle& _halfEdgeHandle) const;
434
435

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

438
    /// Get halfedge from vertex _vh1 to _vh2
439
    HalfEdgeHandle halfedge(const VertexHandle& _vh1, const VertexHandle& _vh2) const;
440

441
442
443
    /// Get half-face from list of incident vertices (in connected order)
    ///
    /// \note Only the first three vertices are checked
444
    HalfFaceHandle halfface(const std::vector<VertexHandle>& _vs) const;
445

446
447
448
449
450
    /// 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;

451
452
453
    /// Get half-face from list of incident half-edges
    ///
    /// \note Only the first two half-edges are checked
454
    HalfFaceHandle halfface(const std::vector<HalfEdgeHandle>& _hes) const;
455

456
    /// Get next halfedge within a halfface
457
    HalfEdgeHandle next_halfedge_in_halfface(const HalfEdgeHandle& _heh, const HalfFaceHandle& _hfh) const;
458
459

    /// Get previous halfedge within a halfface
460
    HalfEdgeHandle prev_halfedge_in_halfface(const HalfEdgeHandle& _heh, const HalfFaceHandle& _hfh) const;
461
462

    /// Get valence of vertex (number of incident edges)
463
    inline size_t valence(const VertexHandle& _vh) const {
464
        assert(has_vertex_bottom_up_incidences());
465
        assert(_vh.is_valid() && _vh.uidx() < outgoing_hes_per_vertex_.size());
466

467
468
469
470
        return outgoing_hes_per_vertex_[_vh.idx()].size();
    }

    /// Get valence of edge (number of incident faces)
471
    inline size_t valence(const EdgeHandle& _eh) const {
472
        assert(has_edge_bottom_up_incidences());
473
474
        assert(_eh.is_valid() && _eh.uidx() < edges_.size());
        assert(halfedge_handle(_eh, 0).uidx() < incident_hfs_per_he_.size());
475

476
        return incident_hfs_per_he_[halfedge_handle(_eh, 0).idx()].size();
477
478
479
    }

    /// Get valence of face (number of incident edges)
480
    inline size_t valence(const FaceHandle& _fh) const {
481
        assert(_fh.is_valid() && _fh.uidx() < faces_.size());
482
483
484
485
486

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

    /// Get valence of cell (number of incident faces)
487
    inline size_t valence(const CellHandle& _ch) const {
488
        assert(_ch.is_valid() && _ch.uidx() < cells_.size());
489
490
491
492

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

493
494
495
    //=====================================================================
    // Delete entities
    //=====================================================================
496

497
public:
498

499
    virtual VertexIter delete_vertex(const VertexHandle& _h);
500

501
    virtual EdgeIter delete_edge(const EdgeHandle& _h);
502

503
    virtual FaceIter delete_face(const FaceHandle& _h);
504

505
    virtual CellIter delete_cell(const CellHandle& _h);
506

507
508
509
510
511
512
513
514
515
516
    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()];   }

517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
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);

536
public:
537

538
539
    /// Exchanges the indices of two cells while keeping the mesh otherwise unaffected.
    virtual void swap_cell_indices(CellHandle _h1, CellHandle _h2);
540

541
542
    /// Exchanges the indices of two faces while keeping the mesh otherwise unaffected.
    virtual void swap_face_indices(FaceHandle _h1, FaceHandle _h2);
543

544
545
    /// Exchanges the indices of two edges while keeping the mesh otherwise unaffected.
    virtual void swap_edge_indices(EdgeHandle _h1, EdgeHandle _h2);
546

547
548
549
550
    /// Exchanges the indices of two vertices while keeping the mesh otherwise unaffected.
    virtual void swap_vertex_indices(VertexHandle _h1, VertexHandle _h2);

protected:
551

552
553
554
555
556
557
558
559
560
561
    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
562
        explicit EdgeCorrector(const std::vector<int>& _newIndices) :
563
564
565
566
567
568
569
570
571
572
573
574
            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
575
        explicit FaceCorrector(const std::vector<int>& _newIndices) :
576
577
578
579
580
581
582
583
            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);
584
                unsigned char opp = he_it->idx() == halfedge_handle(eh, 1).idx();
Max Lyon's avatar
Max Lyon committed
585
                *he_it = halfedge_handle(EdgeHandle(newIndices_[eh.idx()]), opp);
586
587
588
589
590
591
592
593
594
            }
            _face.set_halfedges(hes);
        }
    private:
        const std::vector<int>& newIndices_;
    };

    class CellCorrector {
    public:
Jan Möbius's avatar
Jan Möbius committed
595
        explicit CellCorrector(const std::vector<int>& _newIndices) :
596
597
598
599
600
601
602
603
            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);
604
                unsigned char opp = hf_it->idx() == halfface_handle(fh, 1).idx();
Max Lyon's avatar
Max Lyon committed
605
                *hf_it = halfface_handle(FaceHandle(newIndices_[fh.idx()]), opp);
606
607
608
609
610
611
612
613
614
            }
            _cell.set_halffaces(hfs);
        }
    private:
        const std::vector<int>& newIndices_;
    };

public:

615
616
617
618
    /** \brief Delete range of cells
     *
     * Deletes all cells in range [_first, _last].
     *
619
620
621
     * @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
622
623
624
     */
    CellIter delete_cell_range(const CellIter& _first, const CellIter& _last);

625
public:
626
627

    /// Clear whole mesh
628
    virtual void clear(bool _clearProps = true) {
629
630
631
632

        edges_.clear();
        faces_.clear();
        cells_.clear();
633
634
635
636
        vertex_deleted_.clear();
        edge_deleted_.clear();
        face_deleted_.clear();
        cell_deleted_.clear();
637
638
639
640
        n_deleted_vertices_ = 0;
        n_deleted_edges_ = 0;
        n_deleted_faces_ = 0;
        n_deleted_cells_ = 0;
641
642
643
        outgoing_hes_per_vertex_.clear();
        incident_hfs_per_he_.clear();
        incident_cell_per_hf_.clear();
Mike Kremer's avatar
Mike Kremer committed
644
        n_vertices_ = 0;
645

646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
        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);
        }
664
665
666
    }

    //=====================================================================
667
    // Bottom-up Incidences
668
669
    //=====================================================================

670
671
public:

672
    void enable_bottom_up_incidences(bool _enable = true) {
673

674
675
676
        enable_vertex_bottom_up_incidences(_enable);
        enable_edge_bottom_up_incidences(_enable);
        enable_face_bottom_up_incidences(_enable);
677
678
    }

679
    void enable_vertex_bottom_up_incidences(bool _enable = true) {
680
681

        if(_enable && !v_bottom_up_) {
682
            // Vertex bottom-up incidences have to be
683
            // recomputed for the whole mesh
684
            compute_vertex_bottom_up_incidences();
685
        }
686

687
688
689
690
        if(!_enable) {
            outgoing_hes_per_vertex_.clear();
        }

691
692
        v_bottom_up_ = _enable;
    }
693

694
    void enable_edge_bottom_up_incidences(bool _enable = true) {
695

696
        if(_enable && !e_bottom_up_) {
697
            // Edge bottom-up incidences have to be
698
            // recomputed for the whole mesh
699
            compute_edge_bottom_up_incidences();
700
701

            if(f_bottom_up_) {
Jan Möbius's avatar
Jan Möbius committed
702
#if defined(__clang_major__) && (__clang_major__ >= 5)
703
704
705
706
707
                for(EdgeIter e_it = edges_begin(), e_end = edges_end();
                    e_it != e_end; ++e_it) {
                    reorder_incident_halffaces(*e_it);
                }
#else
708
                std::for_each(edges_begin(), edges_end(),
709
                              fun::bind(&TopologyKernel::reorder_incident_halffaces, this, fun::placeholders::_1));
710
#endif
711
712
713
            }
        }

714
715
716
717
        if(!_enable) {
            incident_hfs_per_he_.clear();
        }

718
719
720
        e_bottom_up_ = _enable;
    }

721
    void enable_face_bottom_up_incidences(bool _enable = true) {
722

723
        bool updateOrder = false;
724
        if(_enable && !f_bottom_up_) {
725
            // Face bottom-up incidences have to be
726
            // recomputed for the whole mesh
727
            compute_face_bottom_up_incidences();
728

729
            updateOrder = true;
730
731
        }

732
733
734
735
        if(!_enable) {
            incident_cell_per_hf_.clear();
        }

736
        f_bottom_up_ = _enable;
737
738
739

        if(updateOrder) {
            if(e_bottom_up_) {
Jan Möbius's avatar
Jan Möbius committed
740
#if defined(__clang_major__) && (__clang_major__ >= 5)
741
742
743
744
745
                for(EdgeIter e_it = edges_begin(), e_end = edges_end();
                    e_it != e_end; ++e_it) {
                    reorder_incident_halffaces(*e_it);
                }
#else
746
                std::for_each(edges_begin(), edges_end(),
747
                              fun::bind(&TopologyKernel::reorder_incident_halffaces, this, fun::placeholders::_1));
748
#endif
749
750
            }
        }
751
752
    }

753
754
755
756
    bool has_full_bottom_up_incidences() const {
        return (has_vertex_bottom_up_incidences() &&
                has_edge_bottom_up_incidences() &&
                has_face_bottom_up_incidences());
757
758
    }

759
    bool has_vertex_bottom_up_incidences() const { return v_bottom_up_; }
760

761
    bool has_edge_bottom_up_incidences() const { return e_bottom_up_; }
762

763
    bool has_face_bottom_up_incidences() const { return f_bottom_up_; }
764

765

766
    void enable_deferred_deletion(bool _enable = true);
767
768
769
770
771
772
773
774
    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:
775

776
    void compute_vertex_bottom_up_incidences();
777

778
    void compute_edge_bottom_up_incidences();
779

780
    void compute_face_bottom_up_incidences();
781
782
783
784
785
786
787
788
789
790
791
792

    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_;

793
private:
794
    bool v_bottom_up_ = true;
795

796
    bool e_bottom_up_ = true;
797

798
    bool f_bottom_up_ = true;
799

800
    bool deferred_deletion = true;
801

802
    bool fast_deletion = true;
803

804
805
806
807
    //=====================================================================
    // Connectivity
    //=====================================================================

808
809
public:

810
811
812
813
814
815
    /// \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.
816
817
818
819
820
821
    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 {
822

823
        assert(_halfFaceHandle.is_valid() && _halfFaceHandle.uidx() < faces_.size() * 2u);
824
        assert(has_face_bottom_up_incidences());
825
        assert(_halfFaceHandle.uidx() < incident_cell_per_hf_.size());
826
        return incident_cell_per_hf_[_halfFaceHandle.idx()] == InvalidCellHandle;
827
828
829
    }

    bool is_boundary(const FaceHandle& _faceHandle) const {
830
        assert(_faceHandle.is_valid() && _faceHandle.uidx() < faces_.size());
831
        assert(has_face_bottom_up_incidences());
832
833
834
835
836
        return  is_boundary(halfface_handle(_faceHandle, 0)) ||
                is_boundary(halfface_handle(_faceHandle, 1));
    }

    bool is_boundary(const EdgeHandle& _edgeHandle) const {
837
        assert(has_edge_bottom_up_incidences());
838
        assert(_edgeHandle.is_valid() && _edgeHandle.uidx() < edges_.size());
839

840
841
842
843
844
845
846
847
848
849
        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 {
850
        assert(has_edge_bottom_up_incidences());
851
        assert(_halfedgeHandle.is_valid() && _halfedgeHandle.uidx() < edges_.size() * 2u);
852

853
854
855
856
857
858
859
860
861
862
        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 {
863
        assert(has_vertex_bottom_up_incidences());
864
        assert(_vertexHandle.is_valid() && _vertexHandle.uidx() < n_vertices());
865

866
867
868
869
870
871
        for(VertexOHalfEdgeIter voh_it = voh_iter(_vertexHandle); voh_it.valid(); ++voh_it) {
            if(is_boundary(*voh_it)) return true;
        }
        return false;
    }

872
    size_t n_vertices_in_cell(const CellHandle& _ch) const {
873
        assert(_ch.is_valid() && _ch.uidx() < cells_.size());
874

875
        std::set<VertexHandle> vhs;
876
877
878
879
880
881
        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) {
882
                vhs.insert(halfedge(*he_it).to_vertex());
883
884
            }
        }
885
        return vhs.size();
886
887
888
889
890
891
892
893
    }

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

    /*
     * Non-virtual functions
     */

894
    Edge opposite_halfedge(const Edge& _edge) const {
895
896
897
        return Edge(_edge.to_vertex(), _edge.from_vertex());
    }

898
    Face opposite_halfface(const Face& _face) const {
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
        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?
915
916
917
        assert(_h.is_valid());
        assert(_subIdx < 2);
        // if(_h.idx() < 0 || _subIdx > 1) return InvalidHalfEdgeHandle;
918
919
920
921
922
923
        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?
924
925
926
        assert(_h.is_valid());
        assert(_subIdx < 2);
        // if(_h.idx() < 0 || _subIdx > 1) return InvalidHalfFaceHandle;
927
        return HalfFaceHandle((2 * _h.idx()) + (_subIdx ? 1 : 0));
928
929
930
931
932
    }

    /// Handle conversion
    static inline EdgeHandle edge_handle(const HalfEdgeHandle& _h) {
        // Is handle in range?
933
934
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidEdgeHandle;
935
936
937
938
939
        return EdgeHandle((int)(_h.idx() / 2));
    }

    static inline FaceHandle face_handle(const HalfFaceHandle& _h) {
        // Is handle in range?
940
941
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidFaceHandle;
942
943
944
945
946
        return FaceHandle((int)(_h.idx() / 2));
    }

    static inline HalfEdgeHandle opposite_halfedge_handle(const HalfEdgeHandle& _h) {
        // Is handle in range?
947
948
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidHalfEdgeHandle;
949
950
951
952
953
954
955
956
957
958

        // 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?
959
960
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidHalfFaceHandle;
961
962
963
964
965
966
967
968

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

969
    bool inline needs_garbage_collection() const {
970
        return n_deleted_vertices_ > 0 || n_deleted_edges_ > 0 || n_deleted_faces_ > 0 || n_deleted_cells_ > 0;
971
972
    }

973
974
975
976
977
978
979
980
981
982
protected:

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

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

    // List of cells
    std::vector<Cell> cells_;
983
984
985
986
987

    std::vector<bool> vertex_deleted_;
    std::vector<bool> edge_deleted_;
    std::vector<bool> face_deleted_;
    std::vector<bool> cell_deleted_;
988
989
990
991
992
993

    // number of elements deleted, but not yet garbage collected
    size_t n_deleted_vertices_ = 0;
    size_t n_deleted_edges_ = 0;
    size_t n_deleted_faces_ = 0;
    size_t n_deleted_cells_ = 0;
994

995
996
997
998
999
};

}

#endif /* TOPOLOGYKERNEL_HH_ */