TopologyKernel.hh 32 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
88
89
90
91
92
    //=====================================================================
    // Iterators
    //=====================================================================

    friend class VertexOHalfEdgeIter;
    friend class HalfEdgeHalfFaceIter;
    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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
    /*
     * 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));
    }

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

    std::pair<VertexCellIter, VertexCellIter> vertex_cells(const VertexHandle& _h, int _max_laps = 1){
        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);
150
151
    }

Max Lyon's avatar
Max Lyon committed
152
153
154
    std::pair<HalfEdgeCellIter, HalfEdgeCellIter> halfedge_cells(const HalfEdgeHandle& _h, int _max_laps = 1){
        HalfEdgeCellIter begin = hec_iter(_h, _max_laps);
        return std::make_pair(begin, make_end_circulator(begin));
155
156
    }

Max Lyon's avatar
Max Lyon committed
157
158
    CellVertexIter cv_iter(const CellHandle& _h, int _max_laps = 1) const {
        return CellVertexIter(_h, this, _max_laps);
159
160
    }

Max Lyon's avatar
Max Lyon committed
161
162
163
    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));
164
165
    }

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

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

Max Lyon's avatar
Max Lyon committed
175
176
    HalfFaceVertexIter hfv_iter(const HalfFaceHandle& _h, int _max_laps = 1) const {
        return HalfFaceVertexIter(_h, this, _max_laps);
Mike Kremer's avatar
Mike Kremer committed
177
178
    }

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

Max Lyon's avatar
Max Lyon committed
184
185
186
187
188
189
190
191
192
193
194
195
196
    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
     */

197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
    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 {
        return VertexIter(this, VertexHandle(n_vertices()));
    }

Max Lyon's avatar
Max Lyon committed
213
214
215
216
    std::pair<VertexIter, VertexIter> vertices() const {
        return std::make_pair(vertices_begin(), vertices_end());
    }

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

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

    EdgeIter edges_end() const {
        return EdgeIter(this, EdgeHandle(edges_.size()));
    }

Max Lyon's avatar
Max Lyon committed
229
230
231
232
    std::pair<EdgeIter, EdgeIter> edges() const {
        return std::make_pair(edges_begin(), edges_end());
    }

233
234
235
236
237
238
239
240
241
242
243
244
    HalfEdgeIter he_iter() const {
        return HalfEdgeIter(this);
    }

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

    HalfEdgeIter halfedges_end() const {
        return HalfEdgeIter(this, HalfEdgeHandle(edges_.size() * 2));
    }

Max Lyon's avatar
Max Lyon committed
245
246
247
248
    std::pair<HalfEdgeIter, HalfEdgeIter> halfedges() const {
        return std::make_pair(halfedges_begin(), halfedges_end());
    }

249
250
251
252
253
254
255
256
257
258
259
260
    FaceIter f_iter() const {
        return FaceIter(this);
    }

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

    FaceIter faces_end() const {
        return FaceIter(this, FaceHandle(faces_.size()));
    }

Max Lyon's avatar
Max Lyon committed
261
262
263
264
    std::pair<FaceIter, FaceIter> faces() const {
        return std::make_pair(faces_begin(), faces_end());
    }

265
266
267
268
269
270
271
272
273
274
275
276
    HalfFaceIter hf_iter() const {
        return HalfFaceIter(this);
    }

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

    HalfFaceIter halffaces_end() const {
        return HalfFaceIter(this, HalfFaceHandle(faces_.size() * 2));
    }

Max Lyon's avatar
Max Lyon committed
277
278
279
280
    std::pair<HalfFaceIter, HalfFaceIter> halffaces() const {
        return std::make_pair(halffaces_begin(), halffaces_end());
    }

281
282
283
284
285
286
287
288
289
290
291
292
    CellIter c_iter() const {
        return CellIter(this);
    }

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

    CellIter cells_end() const {
        return CellIter(this, CellHandle(cells_.size()));
    }

Max Lyon's avatar
Max Lyon committed
293
294
295
296
    std::pair<CellIter, CellIter> cells() const {
        return std::make_pair(cells_begin(), cells_end());
    }

297
298
299
300
301
    /*
     * Virtual functions with implementation
     */

    /// Get number of vertices in mesh
302
    virtual size_t n_vertices()   const { return n_vertices_; }
303
    /// Get number of edges in mesh
304
    virtual size_t n_edges()      const { return edges_.size(); }
305
    /// Get number of halfedges in mesh
306
    virtual size_t n_halfedges()  const { return edges_.size() * 2u; }
307
    /// Get number of faces in mesh
308
    virtual size_t n_faces()      const { return faces_.size(); }
309
    /// Get number of halffaces in mesh
310
    virtual size_t n_halffaces()  const { return faces_.size() * 2u; }
311
    /// Get number of cells in mesh
312
    virtual size_t n_cells()      const { return cells_.size(); }
313

314
315
316
    int genus() const {

        int g = (1 - (n_vertices() -
317
318
                      n_edges() +
                      n_faces() -
319
320
321
322
323
324
325
                      n_cells()));

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

        // An error occured
        // The mesh might not be manifold
        return  -1;
326
327
    }

328
329
private:

330
    // Cache total vertex number
331
    size_t n_vertices_;
332
333

public:
334
335

    /// Add abstract vertex
336
    virtual VertexHandle add_vertex();
337
338
339
340

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

    /// Add edge
341
    virtual EdgeHandle add_edge(const VertexHandle& _fromVertex, const VertexHandle& _toHandle, bool _allowDuplicates = false);
342
343

    /// Add face via incident edges
344
345
346
347
348
349
    ///
    /// \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.
350
    virtual FaceHandle add_face(const std::vector<HalfEdgeHandle>& _halfedges, bool _topologyCheck = false);
351
352
353
354
355

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

    /// Add cell via incident halffaces
356
357
358
359
360
361
    ///
    /// \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.
362
    virtual CellHandle add_cell(const std::vector<HalfFaceHandle>& _halffaces, bool _topologyCheck = false);
363

364
365
366
367
368
369
370
371
372
    /// 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);

373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
    /*
     * 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
396
    Edge halfedge(const HalfEdgeHandle& _halfEdgeHandle) const;
397
398

    /// Get face that corresponds to halfface with handle _halfFaceHandle
399
    Face halfface(const HalfFaceHandle& _halfFaceHandle) const;
400
401

    /// Get opposite halfedge that corresponds to halfedge with handle _halfEdgeHandle
402
    Edge opposite_halfedge(const HalfEdgeHandle& _halfEdgeHandle) const;
403
404

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

407
    /// Get halfedge from vertex _vh1 to _vh2
408
    HalfEdgeHandle halfedge(const VertexHandle& _vh1, const VertexHandle& _vh2) const;
409

410
411
412
    /// Get half-face from list of incident vertices (in connected order)
    ///
    /// \note Only the first three vertices are checked
413
    HalfFaceHandle halfface(const std::vector<VertexHandle>& _vs) const;
414

415
416
417
    /// Get half-face from list of incident half-edges
    ///
    /// \note Only the first two half-edges are checked
418
    HalfFaceHandle halfface(const std::vector<HalfEdgeHandle>& _hes) const;
419

420
    /// Get next halfedge within a halfface
421
    HalfEdgeHandle next_halfedge_in_halfface(const HalfEdgeHandle& _heh, const HalfFaceHandle& _hfh) const;
422
423

    /// Get previous halfedge within a halfface
424
    HalfEdgeHandle prev_halfedge_in_halfface(const HalfEdgeHandle& _heh, const HalfFaceHandle& _hfh) const;
425
426

    /// Get valence of vertex (number of incident edges)
427
    inline size_t valence(const VertexHandle& _vh) const {
428
429
430
        assert(has_vertex_bottom_up_incidences());
        assert(_vh.is_valid() && (size_t)_vh.idx() < outgoing_hes_per_vertex_.size());

431
432
433
434
        return outgoing_hes_per_vertex_[_vh.idx()].size();
    }

    /// Get valence of edge (number of incident faces)
435
    inline size_t valence(const EdgeHandle& _eh) const {
436
437
        assert(has_edge_bottom_up_incidences());
        assert(_eh.is_valid() && (size_t)_eh.idx() < edges_.size());
438
        assert((size_t)halfedge_handle(_eh, 0).idx() < incident_hfs_per_he_.size());
439

440
        return incident_hfs_per_he_[halfedge_handle(_eh, 0).idx()].size();
441
442
443
    }

    /// Get valence of face (number of incident edges)
444
    inline size_t valence(const FaceHandle& _fh) const {
445
        assert(_fh.is_valid() && (size_t)_fh.idx() < faces_.size());
446
447
448
449
450

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

    /// Get valence of cell (number of incident faces)
451
    inline size_t valence(const CellHandle& _ch) const {
452
        assert(_ch.is_valid() && (size_t)_ch.idx() < cells_.size());
453
454
455
456

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

457
458
459
    //=====================================================================
    // Delete entities
    //=====================================================================
460

461
public:
462

463
    virtual VertexIter delete_vertex(const VertexHandle& _h);
464

465
    virtual EdgeIter delete_edge(const EdgeHandle& _h);
466

467
    virtual FaceIter delete_face(const FaceHandle& _h);
468

469
    virtual CellIter delete_cell(const CellHandle& _h);
470

471
472
473
474
475
476
477
478
479
480
    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()];   }

481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
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);

500
501
protected:

502
503
504
505
506
507
508
509
    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);

510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
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
    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:

573
574
575
576
    /** \brief Delete range of cells
     *
     * Deletes all cells in range [_first, _last].
     *
577
578
579
     * @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
580
581
582
     */
    CellIter delete_cell_range(const CellIter& _first, const CellIter& _last);

583
public:
584
585

    /// Clear whole mesh
586
    virtual void clear(bool _clearProps = true) {
587
588
589
590

        edges_.clear();
        faces_.clear();
        cells_.clear();
591
592
593
594
        vertex_deleted_.clear();
        edge_deleted_.clear();
        face_deleted_.clear();
        cell_deleted_.clear();
595
596
597
        outgoing_hes_per_vertex_.clear();
        incident_hfs_per_he_.clear();
        incident_cell_per_hf_.clear();
Mike Kremer's avatar
Mike Kremer committed
598
        n_vertices_ = 0;
599

600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
        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);
        }
618
619
620
    }

    //=====================================================================
621
    // Bottom-up Incidences
622
623
    //=====================================================================

624
625
public:

626
    void enable_bottom_up_incidences(bool _enable = true) {
627

628
629
630
        enable_vertex_bottom_up_incidences(_enable);
        enable_edge_bottom_up_incidences(_enable);
        enable_face_bottom_up_incidences(_enable);
631
632
    }

633
    void enable_vertex_bottom_up_incidences(bool _enable = true) {
634
635

        if(_enable && !v_bottom_up_) {
636
            // Vertex bottom-up incidences have to be
637
            // recomputed for the whole mesh
638
            compute_vertex_bottom_up_incidences();
639
        }
640

641
642
643
644
        if(!_enable) {
            outgoing_hes_per_vertex_.clear();
        }

645
646
        v_bottom_up_ = _enable;
    }
647

648
    void enable_edge_bottom_up_incidences(bool _enable = true) {
649

650
        if(_enable && !e_bottom_up_) {
651
            // Edge bottom-up incidences have to be
652
            // recomputed for the whole mesh
653
            compute_edge_bottom_up_incidences();
654
655

            if(f_bottom_up_) {
Jan Möbius's avatar
Jan Möbius committed
656
#if defined(__clang_major__) && (__clang_major__ >= 5)
657
658
659
660
661
                for(EdgeIter e_it = edges_begin(), e_end = edges_end();
                    e_it != e_end; ++e_it) {
                    reorder_incident_halffaces(*e_it);
                }
#else
662
                std::for_each(edges_begin(), edges_end(),
663
                              fun::bind(&TopologyKernel::reorder_incident_halffaces, this, fun::placeholders::_1));
664
#endif
665
666
667
            }
        }

668
669
670
671
        if(!_enable) {
            incident_hfs_per_he_.clear();
        }

672
673
674
        e_bottom_up_ = _enable;
    }

675
    void enable_face_bottom_up_incidences(bool _enable = true) {
676

677
        bool updateOrder = false;
678
        if(_enable && !f_bottom_up_) {
679
            // Face bottom-up incidences have to be
680
            // recomputed for the whole mesh
681
            compute_face_bottom_up_incidences();
682

683
            updateOrder = true;
684
685
        }

686
687
688
689
        if(!_enable) {
            incident_cell_per_hf_.clear();
        }

690
        f_bottom_up_ = _enable;
691
692
693

        if(updateOrder) {
            if(e_bottom_up_) {
Jan Möbius's avatar
Jan Möbius committed
694
#if defined(__clang_major__) && (__clang_major__ >= 5)
695
696
697
698
699
                for(EdgeIter e_it = edges_begin(), e_end = edges_end();
                    e_it != e_end; ++e_it) {
                    reorder_incident_halffaces(*e_it);
                }
#else
700
                std::for_each(edges_begin(), edges_end(),
701
                              fun::bind(&TopologyKernel::reorder_incident_halffaces, this, fun::placeholders::_1));
702
#endif
703
704
            }
        }
705
706
    }

707
708
709
710
    bool has_full_bottom_up_incidences() const {
        return (has_vertex_bottom_up_incidences() &&
                has_edge_bottom_up_incidences() &&
                has_face_bottom_up_incidences());
711
712
    }

713
    bool has_vertex_bottom_up_incidences() const { return v_bottom_up_; }
714

715
    bool has_edge_bottom_up_incidences() const { return e_bottom_up_; }
716

717
    bool has_face_bottom_up_incidences() const { return f_bottom_up_; }
718

719
720
721
722
723
724
725
726
727
728

    void enable_deferred_deletion(bool _enable = true) { deferred_deletion = _enable; }
    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:
729

730
    void compute_vertex_bottom_up_incidences();
731

732
    void compute_edge_bottom_up_incidences();
733

734
    void compute_face_bottom_up_incidences();
735
736
737
738
739
740
741
742
743
744
745
746

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

747
private:
748
749
750
751
752
    bool v_bottom_up_;

    bool e_bottom_up_;

    bool f_bottom_up_;
753

754
755
756
757
    bool deferred_deletion;

    bool fast_deletion;

758
759
760
761
    //=====================================================================
    // Connectivity
    //=====================================================================

762
763
public:

764
765
766
767
768
769
    /// \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.
770
771
772
773
774
775
    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 {
776
777
778
779
780

        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;
781
782
783
    }

    bool is_boundary(const FaceHandle& _faceHandle) const {
784
785
        assert(_faceHandle.is_valid() && (size_t)_faceHandle.idx() < faces_.size());
        assert(has_face_bottom_up_incidences());
786
787
788
789
790
        return  is_boundary(halfface_handle(_faceHandle, 0)) ||
                is_boundary(halfface_handle(_faceHandle, 1));
    }

    bool is_boundary(const EdgeHandle& _edgeHandle) const {
791
792
793
        assert(has_edge_bottom_up_incidences());
        assert(_edgeHandle.is_valid() && (size_t)_edgeHandle.idx() < edges_.size());

794
795
796
797
798
799
800
801
802
803
        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 {
804
805
806
        assert(has_edge_bottom_up_incidences());
        assert(_halfedgeHandle.is_valid() && (size_t)_halfedgeHandle.idx() < edges_.size() * 2u);

807
808
809
810
811
812
813
814
815
816
        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 {
817
818
819
        assert(has_vertex_bottom_up_incidences());
        assert(_vertexHandle.is_valid() && (size_t)_vertexHandle.idx() < n_vertices());

820
821
822
823
824
825
        for(VertexOHalfEdgeIter voh_it = voh_iter(_vertexHandle); voh_it.valid(); ++voh_it) {
            if(is_boundary(*voh_it)) return true;
        }
        return false;
    }

826
    size_t n_vertices_in_cell(const CellHandle& _ch) const {
827
        assert(_ch.is_valid() && (size_t)_ch.idx() < cells_.size());
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847

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

848
    Edge opposite_halfedge(const Edge& _edge) const {
849
850
851
        return Edge(_edge.to_vertex(), _edge.from_vertex());
    }

852
    Face opposite_halfface(const Face& _face) const {
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
        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?
869
870
871
        assert(_h.is_valid());
        assert(_subIdx < 2);
        // if(_h.idx() < 0 || _subIdx > 1) return InvalidHalfEdgeHandle;
872
873
874
875
876
877
        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?
878
879
880
        assert(_h.is_valid());
        assert(_subIdx < 2);
        // if(_h.idx() < 0 || _subIdx > 1) return InvalidHalfFaceHandle;
881
        return HalfFaceHandle((2 * _h.idx()) + (_subIdx ? 1 : 0));
882
883
884
885
886
    }

    /// Handle conversion
    static inline EdgeHandle edge_handle(const HalfEdgeHandle& _h) {
        // Is handle in range?
887
888
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidEdgeHandle;
889
890
891
892
893
        return EdgeHandle((int)(_h.idx() / 2));
    }

    static inline FaceHandle face_handle(const HalfFaceHandle& _h) {
        // Is handle in range?
894
895
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidFaceHandle;
896
897
898
899
900
        return FaceHandle((int)(_h.idx() / 2));
    }

    static inline HalfEdgeHandle opposite_halfedge_handle(const HalfEdgeHandle& _h) {
        // Is handle in range?
901
902
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidHalfEdgeHandle;
903
904
905
906
907
908
909
910
911
912

        // 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?
913
914
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidHalfFaceHandle;
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932

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

protected:

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

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

    // List of cells
    std::vector<Cell> cells_;
933
934
935
936
937
938

    std::vector<bool> vertex_deleted_;
    std::vector<bool> edge_deleted_;
    std::vector<bool> face_deleted_;
    std::vector<bool> cell_deleted_;

939
940
941
942
943
};

}

#endif /* TOPOLOGYKERNEL_HH_ */