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

    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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
    }

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

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

153
    std::pair<VertexCellIter, VertexCellIter> vertex_cells(const VertexHandle& _h, int _max_laps = 1) const {
Max Lyon's avatar
Max Lyon committed
154
155
156
157
158
159
        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);
160
161
    }

162
    std::pair<HalfEdgeCellIter, HalfEdgeCellIter> halfedge_cells(const HalfEdgeHandle& _h, int _max_laps = 1) const {
Max Lyon's avatar
Max Lyon committed
163
164
        HalfEdgeCellIter begin = hec_iter(_h, _max_laps);
        return std::make_pair(begin, make_end_circulator(begin));
165
166
    }

Max Lyon's avatar
Max Lyon committed
167
168
    CellVertexIter cv_iter(const CellHandle& _h, int _max_laps = 1) const {
        return CellVertexIter(_h, this, _max_laps);
169
170
    }

Max Lyon's avatar
Max Lyon committed
171
172
173
    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));
174
175
    }

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

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

Max Lyon's avatar
Max Lyon committed
185
186
    HalfFaceVertexIter hfv_iter(const HalfFaceHandle& _h, int _max_laps = 1) const {
        return HalfFaceVertexIter(_h, this, _max_laps);
Mike Kremer's avatar
Mike Kremer committed
187
188
    }

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

Max Lyon's avatar
Max Lyon committed
194
195
196
197
198
199
200
201
202
203
204
205
206
    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
     */

207
208
209
210
211
212
213
214
215
216
217
218
219
    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
220
        return VertexIter(this, VertexHandle((int)n_vertices()));
221
222
    }

Max Lyon's avatar
Max Lyon committed
223
224
225
226
    std::pair<VertexIter, VertexIter> vertices() const {
        return std::make_pair(vertices_begin(), vertices_end());
    }

227
228
229
230
231
232
233
234
235
    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
236
        return EdgeIter(this, EdgeHandle((int)edges_.size()));
237
238
    }

Max Lyon's avatar
Max Lyon committed
239
240
241
242
    std::pair<EdgeIter, EdgeIter> edges() const {
        return std::make_pair(edges_begin(), edges_end());
    }

243
244
245
246
247
248
249
250
251
    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
252
        return HalfEdgeIter(this, HalfEdgeHandle((int)edges_.size() * 2));
253
254
    }

Max Lyon's avatar
Max Lyon committed
255
256
257
258
    std::pair<HalfEdgeIter, HalfEdgeIter> halfedges() const {
        return std::make_pair(halfedges_begin(), halfedges_end());
    }

259
260
261
262
263
264
265
266
267
    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
268
        return FaceIter(this, FaceHandle((int)faces_.size()));
269
270
    }

Max Lyon's avatar
Max Lyon committed
271
272
273
274
    std::pair<FaceIter, FaceIter> faces() const {
        return std::make_pair(faces_begin(), faces_end());
    }

275
276
277
278
279
280
281
282
283
    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
284
        return HalfFaceIter(this, HalfFaceHandle((int)faces_.size() * 2));
285
286
    }

Max Lyon's avatar
Max Lyon committed
287
288
289
290
    std::pair<HalfFaceIter, HalfFaceIter> halffaces() const {
        return std::make_pair(halffaces_begin(), halffaces_end());
    }

291
292
293
294
295
296
297
298
299
    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
300
        return CellIter(this, CellHandle((int)cells_.size()));
301
302
    }

Max Lyon's avatar
Max Lyon committed
303
304
305
306
    std::pair<CellIter, CellIter> cells() const {
        return std::make_pair(cells_begin(), cells_end());
    }

307
308
309
310
311
    /*
     * Virtual functions with implementation
     */

    /// Get number of vertices in mesh
312
    virtual size_t n_vertices()   const { return n_vertices_; }
313
    /// Get number of edges in mesh
314
    virtual size_t n_edges()      const { return edges_.size(); }
315
    /// Get number of halfedges in mesh
316
    virtual size_t n_halfedges()  const { return edges_.size() * 2u; }
317
    /// Get number of faces in mesh
318
    virtual size_t n_faces()      const { return faces_.size(); }
319
    /// Get number of halffaces in mesh
320
    virtual size_t n_halffaces()  const { return faces_.size() * 2u; }
321
    /// Get number of cells in mesh
322
    virtual size_t n_cells()      const { return cells_.size(); }
323

324
325
    int genus() const {

Max Lyon's avatar
Max Lyon committed
326
327
328
329
        int g = (1 - (int)(n_vertices() -
                           n_edges() +
                           n_faces() -
                           n_cells()));
330
331
332
333
334
335

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

        // An error occured
        // The mesh might not be manifold
        return  -1;
336
337
    }

338
339
private:

340
    // Cache total vertex number
341
    size_t n_vertices_;
342
343

public:
344
345

    /// Add abstract vertex
346
    virtual VertexHandle add_vertex();
347
348
349
350

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

    /// Add edge
351
    virtual EdgeHandle add_edge(const VertexHandle& _fromVertex, const VertexHandle& _toHandle, bool _allowDuplicates = false);
352
353

    /// Add face via incident edges
354
355
356
357
358
359
    ///
    /// \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.
360
    virtual FaceHandle add_face(const std::vector<HalfEdgeHandle>& _halfedges, bool _topologyCheck = false);
361
362
363
364
365

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

    /// Add cell via incident halffaces
366
367
368
369
370
371
    ///
    /// \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.
372
    virtual CellHandle add_cell(const std::vector<HalfFaceHandle>& _halffaces, bool _topologyCheck = false);
373

374
375
376
377
378
379
380
381
382
    /// 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);

383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
    /*
     * 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
406
    Edge halfedge(const HalfEdgeHandle& _halfEdgeHandle) const;
407
408

    /// Get face that corresponds to halfface with handle _halfFaceHandle
409
    Face halfface(const HalfFaceHandle& _halfFaceHandle) const;
410
411

    /// Get opposite halfedge that corresponds to halfedge with handle _halfEdgeHandle
412
    Edge opposite_halfedge(const HalfEdgeHandle& _halfEdgeHandle) const;
413
414

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

417
    /// Get halfedge from vertex _vh1 to _vh2
418
    HalfEdgeHandle halfedge(const VertexHandle& _vh1, const VertexHandle& _vh2) const;
419

420
421
422
    /// Get half-face from list of incident vertices (in connected order)
    ///
    /// \note Only the first three vertices are checked
423
    HalfFaceHandle halfface(const std::vector<VertexHandle>& _vs) const;
424

425
426
427
428
429
    /// 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;

430
431
432
    /// Get half-face from list of incident half-edges
    ///
    /// \note Only the first two half-edges are checked
433
    HalfFaceHandle halfface(const std::vector<HalfEdgeHandle>& _hes) const;
434

435
    /// Get next halfedge within a halfface
436
    HalfEdgeHandle next_halfedge_in_halfface(const HalfEdgeHandle& _heh, const HalfFaceHandle& _hfh) const;
437
438

    /// Get previous halfedge within a halfface
439
    HalfEdgeHandle prev_halfedge_in_halfface(const HalfEdgeHandle& _heh, const HalfFaceHandle& _hfh) const;
440
441

    /// Get valence of vertex (number of incident edges)
442
    inline size_t valence(const VertexHandle& _vh) const {
443
444
445
        assert(has_vertex_bottom_up_incidences());
        assert(_vh.is_valid() && (size_t)_vh.idx() < outgoing_hes_per_vertex_.size());

446
447
448
449
        return outgoing_hes_per_vertex_[_vh.idx()].size();
    }

    /// Get valence of edge (number of incident faces)
450
    inline size_t valence(const EdgeHandle& _eh) const {
451
452
        assert(has_edge_bottom_up_incidences());
        assert(_eh.is_valid() && (size_t)_eh.idx() < edges_.size());
453
        assert((size_t)halfedge_handle(_eh, 0).idx() < incident_hfs_per_he_.size());
454

455
        return incident_hfs_per_he_[halfedge_handle(_eh, 0).idx()].size();
456
457
458
    }

    /// Get valence of face (number of incident edges)
459
    inline size_t valence(const FaceHandle& _fh) const {
460
        assert(_fh.is_valid() && (size_t)_fh.idx() < faces_.size());
461
462
463
464
465

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

    /// Get valence of cell (number of incident faces)
466
    inline size_t valence(const CellHandle& _ch) const {
467
        assert(_ch.is_valid() && (size_t)_ch.idx() < cells_.size());
468
469
470
471

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

472
473
474
    //=====================================================================
    // Delete entities
    //=====================================================================
475

476
public:
477

478
    virtual VertexIter delete_vertex(const VertexHandle& _h);
479

480
    virtual EdgeIter delete_edge(const EdgeHandle& _h);
481

482
    virtual FaceIter delete_face(const FaceHandle& _h);
483

484
    virtual CellIter delete_cell(const CellHandle& _h);
485

486
487
488
489
490
491
492
493
494
495
    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()];   }

496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
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);

515
516
protected:

517
518
519
520
521
522
523
524
    virtual void swap_cells(CellHandle _h1, CellHandle _h2);

    virtual void swap_faces(FaceHandle _h1, FaceHandle _h2);

    virtual void swap_edges(EdgeHandle _h1, EdgeHandle _h2);

    virtual void swap_vertices(VertexHandle _h1, VertexHandle _h2);

525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
    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:
        EdgeCorrector(const std::vector<int>& _newIndices) :
            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:
        FaceCorrector(const std::vector<int>& _newIndices) :
            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());
                *he_it = halfedge_handle(newIndices_[eh.idx()], opp);
            }
            _face.set_halfedges(hes);
        }
    private:
        const std::vector<int>& newIndices_;
    };

    class CellCorrector {
    public:
        CellCorrector(const std::vector<int>& _newIndices) :
            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());
                *hf_it = halfface_handle(newIndices_[fh.idx()], opp);
            }
            _cell.set_halffaces(hfs);
        }
    private:
        const std::vector<int>& newIndices_;
    };

public:

588
589
590
591
    /** \brief Delete range of cells
     *
     * Deletes all cells in range [_first, _last].
     *
592
593
594
     * @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
595
596
597
     */
    CellIter delete_cell_range(const CellIter& _first, const CellIter& _last);

598
public:
599
600

    /// Clear whole mesh
601
    virtual void clear(bool _clearProps = true) {
602
603
604
605

        edges_.clear();
        faces_.clear();
        cells_.clear();
606
607
608
609
        vertex_deleted_.clear();
        edge_deleted_.clear();
        face_deleted_.clear();
        cell_deleted_.clear();
610
611
612
        outgoing_hes_per_vertex_.clear();
        incident_hfs_per_he_.clear();
        incident_cell_per_hf_.clear();
Mike Kremer's avatar
Mike Kremer committed
613
        n_vertices_ = 0;
614

615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
        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);
        }
633
634
635
    }

    //=====================================================================
636
    // Bottom-up Incidences
637
638
    //=====================================================================

639
640
public:

641
    void enable_bottom_up_incidences(bool _enable = true) {
642

643
644
645
        enable_vertex_bottom_up_incidences(_enable);
        enable_edge_bottom_up_incidences(_enable);
        enable_face_bottom_up_incidences(_enable);
646
647
    }

648
    void enable_vertex_bottom_up_incidences(bool _enable = true) {
649
650

        if(_enable && !v_bottom_up_) {
651
            // Vertex bottom-up incidences have to be
652
            // recomputed for the whole mesh
653
            compute_vertex_bottom_up_incidences();
654
        }
655

656
657
658
659
        if(!_enable) {
            outgoing_hes_per_vertex_.clear();
        }

660
661
        v_bottom_up_ = _enable;
    }
662

663
    void enable_edge_bottom_up_incidences(bool _enable = true) {
664

665
        if(_enable && !e_bottom_up_) {
666
            // Edge bottom-up incidences have to be
667
            // recomputed for the whole mesh
668
            compute_edge_bottom_up_incidences();
669
670

            if(f_bottom_up_) {
Jan Möbius's avatar
Jan Möbius committed
671
#if defined(__clang_major__) && (__clang_major__ >= 5)
672
673
674
675
676
                for(EdgeIter e_it = edges_begin(), e_end = edges_end();
                    e_it != e_end; ++e_it) {
                    reorder_incident_halffaces(*e_it);
                }
#else
677
                std::for_each(edges_begin(), edges_end(),
678
                              fun::bind(&TopologyKernel::reorder_incident_halffaces, this, fun::placeholders::_1));
679
#endif
680
681
682
            }
        }

683
684
685
686
        if(!_enable) {
            incident_hfs_per_he_.clear();
        }

687
688
689
        e_bottom_up_ = _enable;
    }

690
    void enable_face_bottom_up_incidences(bool _enable = true) {
691

692
        bool updateOrder = false;
693
        if(_enable && !f_bottom_up_) {
694
            // Face bottom-up incidences have to be
695
            // recomputed for the whole mesh
696
            compute_face_bottom_up_incidences();
697

698
            updateOrder = true;
699
700
        }

701
702
703
704
        if(!_enable) {
            incident_cell_per_hf_.clear();
        }

705
        f_bottom_up_ = _enable;
706
707
708

        if(updateOrder) {
            if(e_bottom_up_) {
Jan Möbius's avatar
Jan Möbius committed
709
#if defined(__clang_major__) && (__clang_major__ >= 5)
710
711
712
713
714
                for(EdgeIter e_it = edges_begin(), e_end = edges_end();
                    e_it != e_end; ++e_it) {
                    reorder_incident_halffaces(*e_it);
                }
#else
715
                std::for_each(edges_begin(), edges_end(),
716
                              fun::bind(&TopologyKernel::reorder_incident_halffaces, this, fun::placeholders::_1));
717
#endif
718
719
            }
        }
720
721
    }

722
723
724
725
    bool has_full_bottom_up_incidences() const {
        return (has_vertex_bottom_up_incidences() &&
                has_edge_bottom_up_incidences() &&
                has_face_bottom_up_incidences());
726
727
    }

728
    bool has_vertex_bottom_up_incidences() const { return v_bottom_up_; }
729

730
    bool has_edge_bottom_up_incidences() const { return e_bottom_up_; }
731

732
    bool has_face_bottom_up_incidences() const { return f_bottom_up_; }
733

734

735
    void enable_deferred_deletion(bool _enable = true);
736
737
738
739
740
741
742
743
    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:
744

745
    void compute_vertex_bottom_up_incidences();
746

747
    void compute_edge_bottom_up_incidences();
748

749
    void compute_face_bottom_up_incidences();
750
751
752
753
754
755
756
757
758
759
760
761

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

762
private:
763
764
765
766
767
    bool v_bottom_up_;

    bool e_bottom_up_;

    bool f_bottom_up_;
768

769
770
771
772
    bool deferred_deletion;

    bool fast_deletion;

773
774
775
776
    //=====================================================================
    // Connectivity
    //=====================================================================

777
778
public:

779
780
781
782
783
784
    /// \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.
785
786
787
788
789
790
    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 {
791
792
793
794
795

        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;
796
797
798
    }

    bool is_boundary(const FaceHandle& _faceHandle) const {
799
800
        assert(_faceHandle.is_valid() && (size_t)_faceHandle.idx() < faces_.size());
        assert(has_face_bottom_up_incidences());
801
802
803
804
805
        return  is_boundary(halfface_handle(_faceHandle, 0)) ||
                is_boundary(halfface_handle(_faceHandle, 1));
    }

    bool is_boundary(const EdgeHandle& _edgeHandle) const {
806
807
808
        assert(has_edge_bottom_up_incidences());
        assert(_edgeHandle.is_valid() && (size_t)_edgeHandle.idx() < edges_.size());

809
810
811
812
813
814
815
816
817
818
        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 {
819
820
821
        assert(has_edge_bottom_up_incidences());
        assert(_halfedgeHandle.is_valid() && (size_t)_halfedgeHandle.idx() < edges_.size() * 2u);

822
823
824
825
826
827
828
829
830
831
        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 {
832
833
834
        assert(has_vertex_bottom_up_incidences());
        assert(_vertexHandle.is_valid() && (size_t)_vertexHandle.idx() < n_vertices());

835
836
837
838
839
840
        for(VertexOHalfEdgeIter voh_it = voh_iter(_vertexHandle); voh_it.valid(); ++voh_it) {
            if(is_boundary(*voh_it)) return true;
        }
        return false;
    }

841
    size_t n_vertices_in_cell(const CellHandle& _ch) const {
842
        assert(_ch.is_valid() && (size_t)_ch.idx() < cells_.size());
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862

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

863
    Edge opposite_halfedge(const Edge& _edge) const {
864
865
866
        return Edge(_edge.to_vertex(), _edge.from_vertex());
    }

867
    Face opposite_halfface(const Face& _face) const {
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
        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?
884
885
886
        assert(_h.is_valid());
        assert(_subIdx < 2);
        // if(_h.idx() < 0 || _subIdx > 1) return InvalidHalfEdgeHandle;
887
888
889
890
891
892
        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?
893
894
895
        assert(_h.is_valid());
        assert(_subIdx < 2);
        // if(_h.idx() < 0 || _subIdx > 1) return InvalidHalfFaceHandle;
896
        return HalfFaceHandle((2 * _h.idx()) + (_subIdx ? 1 : 0));
897
898
899
900
901
    }

    /// Handle conversion
    static inline EdgeHandle edge_handle(const HalfEdgeHandle& _h) {
        // Is handle in range?
902
903
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidEdgeHandle;
904
905
906
907
908
        return EdgeHandle((int)(_h.idx() / 2));
    }

    static inline FaceHandle face_handle(const HalfFaceHandle& _h) {
        // Is handle in range?
909
910
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidFaceHandle;
911
912
913
914
915
        return FaceHandle((int)(_h.idx() / 2));
    }

    static inline HalfEdgeHandle opposite_halfedge_handle(const HalfEdgeHandle& _h) {
        // Is handle in range?
916
917
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidHalfEdgeHandle;
918
919
920
921
922
923
924
925
926
927

        // 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?
928
929
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidHalfFaceHandle;
930
931
932
933
934
935
936
937

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

938
939
940
941
    bool inline needs_garbage_collection() const {
        return needs_garbage_collection_;
    }

942
943
944
945
946
947
948
949
950
951
protected:

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

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

    // List of cells
    std::vector<Cell> cells_;
952
953
954
955
956

    std::vector<bool> vertex_deleted_;
    std::vector<bool> edge_deleted_;
    std::vector<bool> face_deleted_;
    std::vector<bool> cell_deleted_;
957
    bool needs_garbage_collection_;
958

959
960
961
962
963
};

}

#endif /* TOPOLOGYKERNEL_HH_ */