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

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

#ifndef TOPOLOGYKERNEL_HH_
#define TOPOLOGYKERNEL_HH_

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

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

namespace OpenVolumeMesh {

class TopologyKernel : public ResourceManager {
public:

    TopologyKernel();
    virtual ~TopologyKernel();

    /*
     * Defines and constants
     */

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

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

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

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

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

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

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

public:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    /*
     * Iterators
     */

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

334 335
    int genus() const {

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

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

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

348 349
private:

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

public:
354 355

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

486
public:
487

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

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

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

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

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


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

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

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

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

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

    VertexIter delete_vertex_core(const VertexHandle& _h);

    EdgeIter delete_edge_core(const EdgeHandle& _h);

    FaceIter delete_face_core(const FaceHandle& _h);

    CellIter delete_cell_core(const CellHandle& _h);

525 526
protected:

527 528 529 530 531 532 533 534
    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);

535 536 537 538 539 540 541 542 543 544
    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
545
        explicit EdgeCorrector(const std::vector<int>& _newIndices) :
546 547 548 549 550 551 552 553 554 555 556 557
            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
558
        explicit FaceCorrector(const std::vector<int>& _newIndices) :
559 560 561 562 563 564 565 566 567
            newIndices_(_newIndices) {}

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

                EdgeHandle eh = edge_handle(*he_it);
                unsigned char opp = (he_it->idx() - halfedge_handle(eh, 0).idx());
Max Lyon's avatar
Max Lyon committed
568
                *he_it = halfedge_handle(EdgeHandle(newIndices_[eh.idx()]), opp);
569 570 571 572 573 574 575 576 577
            }
            _face.set_halfedges(hes);
        }
    private:
        const std::vector<int>& newIndices_;
    };

    class CellCorrector {
    public:
Jan Möbius's avatar
Jan Möbius committed
578
        explicit CellCorrector(const std::vector<int>& _newIndices) :
579 580 581 582 583 584 585 586 587
            newIndices_(_newIndices) {}

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

                FaceHandle fh = face_handle(*hf_it);
                unsigned char opp = (hf_it->idx() - halfface_handle(fh, 0).idx());
Max Lyon's avatar
Max Lyon committed
588
                *hf_it = halfface_handle(FaceHandle(newIndices_[fh.idx()]), opp);
589 590 591 592 593 594 595 596 597
            }
            _cell.set_halffaces(hfs);
        }
    private:
        const std::vector<int>& newIndices_;
    };

public:

598 599 600 601
    /** \brief Delete range of cells
     *
     * Deletes all cells in range [_first, _last].
     *
602 603 604
     * @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
605 606 607
     */
    CellIter delete_cell_range(const CellIter& _first, const CellIter& _last);

608
public:
609 610

    /// Clear whole mesh
611
    virtual void clear(bool _clearProps = true) {
612 613 614 615

        edges_.clear();
        faces_.clear();
        cells_.clear();
616 617 618 619
        vertex_deleted_.clear();
        edge_deleted_.clear();
        face_deleted_.clear();
        cell_deleted_.clear();
620 621 622
        outgoing_hes_per_vertex_.clear();
        incident_hfs_per_he_.clear();
        incident_cell_per_hf_.clear();
Mike Kremer's avatar
Mike Kremer committed
623
        n_vertices_ = 0;
624

625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642
        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);
        }
643 644 645
    }

    //=====================================================================
646
    // Bottom-up Incidences
647 648
    //=====================================================================

649 650
public:

651
    void enable_bottom_up_incidences(bool _enable = true) {
652

653 654 655
        enable_vertex_bottom_up_incidences(_enable);
        enable_edge_bottom_up_incidences(_enable);
        enable_face_bottom_up_incidences(_enable);
656 657
    }

658
    void enable_vertex_bottom_up_incidences(bool _enable = true) {
659 660

        if(_enable && !v_bottom_up_) {
661
            // Vertex bottom-up incidences have to be
662
            // recomputed for the whole mesh
663
            compute_vertex_bottom_up_incidences();
664
        }
665

666 667 668 669
        if(!_enable) {
            outgoing_hes_per_vertex_.clear();
        }

670 671
        v_bottom_up_ = _enable;
    }
672

673
    void enable_edge_bottom_up_incidences(bool _enable = true) {
674

675
        if(_enable && !e_bottom_up_) {
676
            // Edge bottom-up incidences have to be
677
            // recomputed for the whole mesh
678
            compute_edge_bottom_up_incidences();
679 680

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

693 694 695 696
        if(!_enable) {
            incident_hfs_per_he_.clear();
        }

697 698 699
        e_bottom_up_ = _enable;
    }

700
    void enable_face_bottom_up_incidences(bool _enable = true) {
701

702
        bool updateOrder = false;
703
        if(_enable && !f_bottom_up_) {
704
            // Face bottom-up incidences have to be
705
            // recomputed for the whole mesh
706
            compute_face_bottom_up_incidences();
707

708
            updateOrder = true;
709 710
        }

711 712 713 714
        if(!_enable) {
            incident_cell_per_hf_.clear();
        }

715
        f_bottom_up_ = _enable;
716 717 718

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

732 733 734 735
    bool has_full_bottom_up_incidences() const {
        return (has_vertex_bottom_up_incidences() &&
                has_edge_bottom_up_incidences() &&
                has_face_bottom_up_incidences());
736 737
    }

738
    bool has_vertex_bottom_up_incidences() const { return v_bottom_up_; }
739

740
    bool has_edge_bottom_up_incidences() const { return e_bottom_up_; }
741

742
    bool has_face_bottom_up_incidences() const { return f_bottom_up_; }
743

744

745
    void enable_deferred_deletion(bool _enable = true);
746 747 748 749 750 751 752 753
    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:
754

755
    void compute_vertex_bottom_up_incidences();
756

757
    void compute_edge_bottom_up_incidences();
758

759
    void compute_face_bottom_up_incidences();
760 761 762 763 764 765 766 767 768 769 770 771

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

772
private:
773 774 775 776 777
    bool v_bottom_up_;

    bool e_bottom_up_;

    bool f_bottom_up_;
778

779 780 781 782
    bool deferred_deletion;

    bool fast_deletion;

783 784 785 786
    //=====================================================================
    // Connectivity
    //=====================================================================

787 788
public:

789 790 791 792 793 794
    /// \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.
795 796 797 798 799 800
    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 {
801 802 803 804 805

        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;
806 807 808
    }

    bool is_boundary(const FaceHandle& _faceHandle) const {
809 810
        assert(_faceHandle.is_valid() && (size_t)_faceHandle.idx() < faces_.size());
        assert(has_face_bottom_up_incidences());
811 812 813 814 815
        return  is_boundary(halfface_handle(_faceHandle, 0)) ||
                is_boundary(halfface_handle(_faceHandle, 1));
    }

    bool is_boundary(const EdgeHandle& _edgeHandle) const {
816 817 818
        assert(has_edge_bottom_up_incidences());
        assert(_edgeHandle.is_valid() && (size_t)_edgeHandle.idx() < edges_.size());

819 820 821 822 823 824 825 826 827 828
        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 {
829 830 831
        assert(has_edge_bottom_up_incidences());
        assert(_halfedgeHandle.is_valid() && (size_t)_halfedgeHandle.idx() < edges_.size() * 2u);

832 833 834 835 836 837 838 839 840 841
        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 {
842 843 844
        assert(has_vertex_bottom_up_incidences());
        assert(_vertexHandle.is_valid() && (size_t)_vertexHandle.idx() < n_vertices());

845 846 847 848 849 850
        for(VertexOHalfEdgeIter voh_it = voh_iter(_vertexHandle); voh_it.valid(); ++voh_it) {
            if(is_boundary(*voh_it)) return true;
        }
        return false;
    }

851
    size_t n_vertices_in_cell(const CellHandle& _ch) const {
852
        assert(_ch.is_valid() && (size_t)_ch.idx() < cells_.size());
853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872

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

873
    Edge opposite_halfedge(const Edge& _edge) const {
874 875 876
        return Edge(_edge.to_vertex(), _edge.from_vertex());
    }

877
    Face opposite_halfface(const Face& _face) const {
878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893
        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?
894 895 896
        assert(_h.is_valid());
        assert(_subIdx < 2);
        // if(_h.idx() < 0 || _subIdx > 1) return InvalidHalfEdgeHandle;
897 898 899 900 901 902
        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?
903 904 905
        assert(_h.is_valid());
        assert(_subIdx < 2);
        // if(_h.idx() < 0 || _subIdx > 1) return InvalidHalfFaceHandle;
906
        return HalfFaceHandle((2 * _h.idx()) + (_subIdx ? 1 : 0));
907 908 909 910 911
    }

    /// Handle conversion
    static inline EdgeHandle edge_handle(const HalfEdgeHandle& _h) {
        // Is handle in range?
912 913
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidEdgeHandle;
914 915 916 917 918
        return EdgeHandle((int)(_h.idx() / 2));
    }

    static inline FaceHandle face_handle(const HalfFaceHandle& _h) {
        // Is handle in range?
919 920
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidFaceHandle;
921 922 923 924 925
        return FaceHandle((int)(_h.idx() / 2));
    }

    static inline HalfEdgeHandle opposite_halfedge_handle(const HalfEdgeHandle& _h) {
        // Is handle in range?
926 927
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidHalfEdgeHandle;
928 929 930 931 932 933 934 935 936 937

        // 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?
938 939
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidHalfFaceHandle;
940 941 942 943 944 945 946 947

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

948 949 950 951
    bool inline needs_garbage_collection() const {
        return needs_garbage_collection_;
    }

952 953 954 955 956 957 958 959 960 961
protected:

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

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

    // List of cells
    std::vector<Cell> cells_;
962 963 964 965 966

    std::vector<bool> vertex_deleted_;
    std::vector<bool> edge_deleted_;
    std::vector<bool> face_deleted_;
    std::vector<bool> cell_deleted_;
967
    bool needs_garbage_collection_;
968

969 970 971 972 973
};

}

#endif /* TOPOLOGYKERNEL_HH_ */