TopologyKernel.hh 25.5 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 46 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 78
/*===========================================================================*\
 *                                                                           *
 *                            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_

#include <set>
#include <vector>
#include <iostream>
#include <cassert>

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

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

84 85 86 87 88 89 90 91 92 93
    //=====================================================================
    // 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
94
    friend class HalfFaceVertexIter;
95
    friend class BoundaryHalfFaceHalfFaceIter;
96 97 98 99 100 101 102 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
    friend class BoundaryFaceIter;
    friend class VertexIter;
    friend class EdgeIter;
    friend class HalfEdgeIter;
    friend class FaceIter;
    friend class HalfFaceIter;
    friend class CellIter;

    VertexOHalfEdgeIter voh_iter(const VertexHandle& _h) const {
        return VertexOHalfEdgeIter(_h, this);
    }

    HalfEdgeHalfFaceIter hehf_iter(const HalfEdgeHandle& _h) const {
        return HalfEdgeHalfFaceIter(_h, this);
    }

    VertexCellIter vc_iter(const VertexHandle& _h) const {
        return VertexCellIter(_h, this);
    }

    HalfEdgeCellIter hec_iter(const HalfEdgeHandle& _h) const {
        return HalfEdgeCellIter(_h, this);
    }

    CellVertexIter cv_iter(const CellHandle& _h) const {
        return CellVertexIter(_h, this);
    }

    CellCellIter cc_iter(const CellHandle& _h) const {
        return CellCellIter(_h, this);
    }

Mike Kremer's avatar
Mike Kremer committed
128 129 130 131
    HalfFaceVertexIter hfv_iter(const HalfFaceHandle& _h) const {
        return HalfFaceVertexIter(_h, this);
    }

132 133 134 135
    BoundaryHalfFaceHalfFaceIter bhfhf_iter(const HalfFaceHandle& _ref_h) const {
        return BoundaryHalfFaceHalfFaceIter(_ref_h, this);
    }

136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218
    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()));
    }

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

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

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

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

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

    /*
     * Virtual functions with implementation
     */

    /// Get number of vertices in mesh
    virtual unsigned int n_vertices()   const { return n_vertices_; }
    /// Get number of edges in mesh
219
    virtual unsigned int n_edges()      const { return edges_.size(); }
220
    /// Get number of halfedges in mesh
221
    virtual unsigned int n_halfedges()  const { return edges_.size() * 2u; }
222
    /// Get number of faces in mesh
223
    virtual unsigned int n_faces()      const { return faces_.size(); }
224
    /// Get number of halffaces in mesh
225
    virtual unsigned int n_halffaces()  const { return faces_.size() * 2u; }
226
    /// Get number of cells in mesh
227
    virtual unsigned int n_cells()      const { return cells_.size(); }
228

229 230 231 232 233 234 235
    unsigned int genus() const {
        return  (1 - (n_vertices() -
                      n_edges() +
                      n_faces() -
                      n_cells())/2.0);
    }

236 237
private:

238
    // Cache total vertex number
239 240 241
    unsigned int n_vertices_;

public:
242 243

    /// Add abstract vertex
244
    virtual VertexHandle add_vertex();
245 246 247 248

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

    /// Add edge
249
    virtual EdgeHandle add_edge(const VertexHandle& _fromVertex, const VertexHandle& _toHandle, bool _allowDuplicates = false);
250 251

    /// Add face via incident edges
252
    virtual FaceHandle add_face(const std::vector<HalfEdgeHandle>& _halfedges, bool _topologyCheck = false);
253 254 255 256 257

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

    /// Add cell via incident halffaces
258
    virtual CellHandle add_cell(const std::vector<HalfFaceHandle>& _halffaces, bool _topologyCheck = false);
259

260 261 262 263 264 265 266 267 268
    /// 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);

269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291
    /*
     * 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
292
    Edge halfedge(const HalfEdgeHandle& _halfEdgeHandle) const;
293 294

    /// Get face that corresponds to halfface with handle _halfFaceHandle
295
    Face halfface(const HalfFaceHandle& _halfFaceHandle) const;
296 297

    /// Get opposite halfedge that corresponds to halfedge with handle _halfEdgeHandle
298
    Edge opposite_halfedge(const HalfEdgeHandle& _halfEdgeHandle) const;
299 300

    /// Get opposite halfface that corresponds to halfface with handle _halfFaceHandle
301
    Face opposite_halfface(const HalfFaceHandle& _halfFaceHandle) const;
302 303

    // Get halfedge from vertex _vh1 to _vh2
304
    HalfEdgeHandle halfedge(const VertexHandle& _vh1, const VertexHandle& _vh2) const;
305

306 307
    // Get half-face from list of incident vertices (in connected order)
    // Note: Only the first three vertices are checked
308
    HalfFaceHandle halfface(const std::vector<VertexHandle>& _vs) const;
309 310 311

    // Get half-face from list of incident half-edges
    // Note: Only the first two half-edges are checked
312
    HalfFaceHandle halfface(const std::vector<HalfEdgeHandle>& _hes) const;
313

314
    /// Get next halfedge within a halfface
315
    HalfEdgeHandle next_halfedge_in_halfface(const HalfEdgeHandle& _heh, const HalfFaceHandle& _hfh) const;
316 317

    /// Get previous halfedge within a halfface
318
    HalfEdgeHandle prev_halfedge_in_halfface(const HalfEdgeHandle& _heh, const HalfFaceHandle& _hfh) const;
319 320 321

    /// Get valence of vertex (number of incident edges)
    inline unsigned int valence(const VertexHandle& _vh) const {
322
        if(!v_bottom_up_) {
323
            std::cerr << "Could not get vertex valence: No bottom-up incidences for vertices available!" << std::endl;
324 325
            return 0u;
        }
326
        assert((unsigned int)_vh.idx() < outgoing_hes_per_vertex_.size());
327 328 329 330 331
        return outgoing_hes_per_vertex_[_vh.idx()].size();
    }

    /// Get valence of edge (number of incident faces)
    inline unsigned int valence(const EdgeHandle& _eh) const {
332
        if(!e_bottom_up_) {
333
            std::cerr << "Could not get edge valence: No bottom-up incidences for edges available!" << std::endl;
334 335
            return 0u;
        }
336
        assert((unsigned int)halfedge_handle(_eh, 0).idx() < incident_hfs_per_he_.size());
337
        return incident_hfs_per_he_[halfedge_handle(_eh, 0).idx()].size();
338 339 340 341 342
    }

    /// Get valence of face (number of incident edges)
    inline unsigned int valence(const FaceHandle& _fh) const {

343
        assert((unsigned int)_fh.idx() < faces_.size());
344 345 346 347 348 349
        return face(_fh).halfedges().size();
    }

    /// Get valence of cell (number of incident faces)
    inline unsigned int valence(const CellHandle& _ch) const {

350
        assert((unsigned int)_ch.idx() < cells_.size());
351 352 353
        return cell(_ch).halffaces().size();
    }

354 355 356
    //=====================================================================
    // Delete entities
    //=====================================================================
357

358
public:
359

360
    virtual VertexIter delete_vertex(const VertexHandle& _h);
361

362
    virtual EdgeIter delete_edge(const EdgeHandle& _h);
363

364
    virtual FaceIter delete_face(const FaceHandle& _h);
365

366
    virtual CellIter delete_cell(const CellHandle& _h);
367

368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386
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);

387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451
protected:

    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:

452 453 454 455
    /** \brief Delete range of cells
     *
     * Deletes all cells in range [_first, _last].
     *
456 457 458
     * @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
459 460 461
     */
    CellIter delete_cell_range(const CellIter& _first, const CellIter& _last);

462
public:
463 464

    /// Clear whole mesh
465
    virtual void clear(bool _clearProps = true) {
466 467 468 469 470 471 472

        edges_.clear();
        faces_.clear();
        cells_.clear();
        outgoing_hes_per_vertex_.clear();
        incident_hfs_per_he_.clear();
        incident_cell_per_hf_.clear();
Mike Kremer's avatar
Mike Kremer committed
473
        n_vertices_ = 0;
474

475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492
        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);
        }
493 494 495
    }

    //=====================================================================
496
    // Bottom-up Incidences
497 498
    //=====================================================================

499 500
public:

501
    void enable_bottom_up_incidences(bool _enable = true) {
502

503 504 505
        enable_vertex_bottom_up_incidences(_enable);
        enable_edge_bottom_up_incidences(_enable);
        enable_face_bottom_up_incidences(_enable);
506 507
    }

508
    void enable_vertex_bottom_up_incidences(bool _enable = true) {
509 510

        if(_enable && !v_bottom_up_) {
511
            // Vertex bottom-up incidences have to be
512
            // recomputed for the whole mesh
513
            compute_vertex_bottom_up_incidences();
514
        }
515

516 517 518 519
        if(!_enable) {
            outgoing_hes_per_vertex_.clear();
        }

520 521
        v_bottom_up_ = _enable;
    }
522

523
    void enable_edge_bottom_up_incidences(bool _enable = true) {
524

525
        if(_enable && !e_bottom_up_) {
526
            // Edge bottom-up incidences have to be
527
            // recomputed for the whole mesh
528
            compute_edge_bottom_up_incidences();
529 530 531

            if(f_bottom_up_) {
                std::for_each(edges_begin(), edges_end(),
532
                              fun::bind(&TopologyKernel::reorder_incident_halffaces, this, fun::placeholders::_1));
533 534 535
            }
        }

536 537 538 539
        if(!_enable) {
            incident_hfs_per_he_.clear();
        }

540 541 542
        e_bottom_up_ = _enable;
    }

543
    void enable_face_bottom_up_incidences(bool _enable = true) {
544

545
        bool updateOrder = false;
546
        if(_enable && !f_bottom_up_) {
547
            // Face bottom-up incidences have to be
548
            // recomputed for the whole mesh
549
            compute_face_bottom_up_incidences();
550

551
            updateOrder = true;
552 553
        }

554 555 556 557
        if(!_enable) {
            incident_cell_per_hf_.clear();
        }

558
        f_bottom_up_ = _enable;
559 560 561 562

        if(updateOrder) {
            if(e_bottom_up_) {
                std::for_each(edges_begin(), edges_end(),
563
                              fun::bind(&TopologyKernel::reorder_incident_halffaces, this, fun::placeholders::_1));
564 565
            }
        }
566 567
    }

568 569 570 571
    bool has_full_bottom_up_incidences() const {
        return (has_vertex_bottom_up_incidences() &&
                has_edge_bottom_up_incidences() &&
                has_face_bottom_up_incidences());
572 573
    }

574
    bool has_vertex_bottom_up_incidences() const { return v_bottom_up_; }
575

576
    bool has_edge_bottom_up_incidences() const { return e_bottom_up_; }
577

578
    bool has_face_bottom_up_incidences() const { return f_bottom_up_; }
579 580 581

private:

582
    void compute_vertex_bottom_up_incidences();
583

584
    void compute_edge_bottom_up_incidences();
585

586
    void compute_face_bottom_up_incidences();
587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603

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

    bool v_bottom_up_;

    bool e_bottom_up_;

    bool f_bottom_up_;
604 605 606 607 608

    //=====================================================================
    // Connectivity
    //=====================================================================

609 610
public:

611 612 613 614 615 616 617 618
    /// Get halfface that is adjacent (w.r.t. a common halfedge) within the same cell
    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 {
        return _halfFaceHandle.idx() >= 0 && (unsigned int)_halfFaceHandle.idx() < incident_cell_per_hf_.size() &&
619
                incident_cell_per_hf_[_halfFaceHandle.idx()] == InvalidCellHandle;
620 621 622 623 624 625 626 627
    }

    bool is_boundary(const FaceHandle& _faceHandle) const {
        return  is_boundary(halfface_handle(_faceHandle, 0)) ||
                is_boundary(halfface_handle(_faceHandle, 1));
    }

    bool is_boundary(const EdgeHandle& _edgeHandle) const {
628
        if(!e_bottom_up_) {
629
            std::cerr << "Error: Function is_boundary() needs bottom-up incidences for edges!" << std::endl;
630 631 632 633 634 635 636 637 638 639 640 641
            return false;
        }
        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 {
642
        if(!e_bottom_up_) {
643
            std::cerr << "Error: Function is_boundary() needs bottom-up incidences for edges!" << std::endl;
644 645 646 647 648 649 650 651 652 653 654 655
            return false;
        }
        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 {
656
        if(!v_bottom_up_) {
657
            std::cerr << "Error: Function is_boundary() needs bottom-up incidences for vertices!" << std::endl;
658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686
            return false;
        }
        for(VertexOHalfEdgeIter voh_it = voh_iter(_vertexHandle); voh_it.valid(); ++voh_it) {
            if(is_boundary(*voh_it)) return true;
        }
        return false;
    }

    unsigned int n_vertices_in_cell(const CellHandle& _ch) const {

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

687
    Edge opposite_halfedge(const Edge& _edge) const {
688 689 690
        return Edge(_edge.to_vertex(), _edge.from_vertex());
    }

691
    Face opposite_halfface(const Face& _face) const {
692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716

        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?
        if(_h.idx() < 0 || _subIdx > 1) return InvalidHalfEdgeHandle;
        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?
        if(_h.idx() < 0 || _subIdx > 1) return InvalidHalfFaceHandle;
717
        return HalfFaceHandle((2 * _h.idx()) + (_subIdx ? 1 : 0));
718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769
    }

    /// Handle conversion
    static inline EdgeHandle edge_handle(const HalfEdgeHandle& _h) {
        // Is handle in range?
        if(_h.idx() < 0) return InvalidEdgeHandle;
        return EdgeHandle((int)(_h.idx() / 2));
    }

    static inline FaceHandle face_handle(const HalfFaceHandle& _h) {
        // Is handle in range?
        if(_h.idx() < 0) return InvalidFaceHandle;
        return FaceHandle((int)(_h.idx() / 2));
    }

    static inline HalfEdgeHandle opposite_halfedge_handle(const HalfEdgeHandle& _h) {
        // Is handle in range?
        if(_h.idx() < 0) return InvalidHalfEdgeHandle;

        // 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?
        if(_h.idx() < 0) return InvalidHalfFaceHandle;

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

}

#endif /* TOPOLOGYKERNEL_HH_ */