surface_mesh.h

/********************************************************************
 * Copyright (C) 2015-2021 by Liangliang Nan <liangliang.nan@gmail.com>
 * Copyright (C) 2011-2013 by Graphics & Geometry Group, Bielefeld University
 * Copyright (C) 2001-2005 by Computer Graphics Group, RWTH Aachen
 *
 * The code in this file is partly from Surface_mesh (v1.1) with
 * modifications and enhancement:
 *      https://opensource.cit-ec.de/projects/surface_mesh
 * The original code was distributed under the GNU GPL License.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public License
 * as published by the Free Software Foundation, version 2.
 *
 * This library 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
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 ********************************************************************/
 
#ifndef EASY3D_CORE_SURFACE_MESH_H
#define EASY3D_CORE_SURFACE_MESH_H
 
#include <easy3d/core/model.h>
#include <easy3d/core/types.h>
#include <easy3d/core/property.h>
 
namespace easy3d {

    class SurfaceMesh : public Model
    {
 
    public: //------------------------------------------------------ topology types

        class BaseHandle
        {
        public:
            explicit BaseHandle(int _idx=-1) : idx_(_idx) {}

            int idx() const { return idx_; }

            void reset() { idx_=-1; }

            bool is_valid() const { return idx_ != -1; }

            bool operator==(const BaseHandle& _rhs) const {
                return idx_ == _rhs.idx_;
            }

            bool operator!=(const BaseHandle& _rhs) const {
                return idx_ != _rhs.idx_;
            }

            bool operator<(const BaseHandle& _rhs) const {
                return idx_ < _rhs.idx_;
            }

            struct Hash {
                std::size_t operator()(const BaseHandle& h) const { return h.idx(); }
            };
 
        private:
            friend class SurfaceMesh;
            int idx_;
        };
 

        struct Vertex : BaseHandle
        {
            explicit Vertex(int _idx=-1) : BaseHandle(_idx) {}
            std::ostream& operator<<(std::ostream& os) const { return os << 'v' << idx(); }
        };
 

        struct Halfedge : BaseHandle
        {
            explicit Halfedge(int _idx=-1) : BaseHandle(_idx) {}
            std::ostream& operator<<(std::ostream& os) const { return os << 'h' << idx(); }
        };
 

        struct Edge : BaseHandle
        {
            explicit Edge(int _idx=-1) : BaseHandle(_idx) {}
            std::ostream& operator<<(std::ostream& os) const { return os << 'e' << idx(); }
        };
 

        struct Face : BaseHandle
        {
            explicit Face(int _idx=-1) : BaseHandle(_idx) {}
            std::ostream& operator<<(std::ostream& os) const { return os << 'f' << idx(); }
        };
 
 
    public: //-------------------------------------------------- connectivity types

        struct VertexConnectivity
        {
            Halfedge  halfedge_;
        };
 

        struct HalfedgeConnectivity
        {
            Face      face_;
            Vertex    vertex_;
            Halfedge  next_;
            Halfedge  prev_;
        };
 

        struct FaceConnectivity
        {
            Halfedge  halfedge_;
        };
 
 
 
    public: //------------------------------------------------------ property types

        template <class T> class VertexProperty : public Property<T>
        {
        public:

            VertexProperty() = default;
            explicit VertexProperty(Property<T> p) : Property<T>(p) {}

            typename Property<T>::reference operator[](Vertex v) {
                return Property<T>::operator[](v.idx());
            }

            typename Property<T>::const_reference operator[](Vertex v) const {
                return Property<T>::operator[](v.idx());
            }
        };
 

        template <class T> class HalfedgeProperty : public Property<T>
        {
        public:

            HalfedgeProperty() = default;
            explicit HalfedgeProperty(Property<T> p) : Property<T>(p) {}

            typename Property<T>::reference operator[](Halfedge h) {
                return Property<T>::operator[](h.idx());
            }

            typename Property<T>::const_reference operator[](Halfedge h) const {
                return Property<T>::operator[](h.idx());
            }
        };
 

        template <class T> class EdgeProperty : public Property<T>
        {
        public:

            EdgeProperty() = default;
            explicit EdgeProperty(Property<T> p) : Property<T>(p) {}

            typename Property<T>::reference operator[](Edge e) {
                return Property<T>::operator[](e.idx());
            }

            typename Property<T>::const_reference operator[](Edge e) const {
                return Property<T>::operator[](e.idx());
            }
        };
 

        template <class T> class FaceProperty : public Property<T>
        {
        public:

            FaceProperty() = default;
            explicit FaceProperty(Property<T> p) : Property<T>(p) {}

            typename Property<T>::reference operator[](Face f) {
                return Property<T>::operator[](f.idx());
            }

            typename Property<T>::const_reference operator[](Face f) const {
                return Property<T>::operator[](f.idx());
            }
        };
 

        template <class T> class ModelProperty : public Property<T>
        {
        public:

            ModelProperty() = default;
            explicit ModelProperty(Property<T> p) : Property<T>(p) {}

            typename Property<T>::reference operator[](size_t idx) {
                return Property<T>::operator[](idx);
            }

            typename Property<T>::const_reference operator[](size_t idx) const {
                return Property<T>::operator[](idx);
            }
        };
 
 
 
    public: //------------------------------------------------------ iterator types

        class VertexIterator
        {
        public:
            explicit VertexIterator(Vertex v=Vertex(), const SurfaceMesh* m=nullptr) : hnd_(v), mesh_(m) {
                if (mesh_ && mesh_->has_garbage()) while (mesh_->is_valid(hnd_) && mesh_->is_deleted(hnd_)) ++hnd_.idx_;
            }

            Vertex operator*()  const { return  hnd_; }

            bool operator==(const VertexIterator& rhs) const {
                return (hnd_==rhs.hnd_);
            }

            bool operator!=(const VertexIterator& rhs) const {
                return !operator==(rhs);
            }

            VertexIterator& operator++() {
                ++hnd_.idx_;
                assert(mesh_);
                while (mesh_->has_garbage() && mesh_->is_valid(hnd_) && mesh_->is_deleted(hnd_)) ++hnd_.idx_;
                return *this;
            }

            VertexIterator& operator--() {
                --hnd_.idx_;
                assert(mesh_);
                while (mesh_->has_garbage() && mesh_->is_valid(hnd_) && mesh_->is_deleted(hnd_)) --hnd_.idx_;
                return *this;
            }
 
        private:
            Vertex  hnd_;
            const SurfaceMesh* mesh_;
        };
 

        class HalfedgeIterator
        {
        public:
            explicit HalfedgeIterator(Halfedge h=Halfedge(), const SurfaceMesh* m=nullptr) : hnd_(h), mesh_(m) {
                if (mesh_ && mesh_->has_garbage()) while (mesh_->is_valid(hnd_) && mesh_->is_deleted(hnd_)) ++hnd_.idx_;
            }

            Halfedge operator*() const { return  hnd_; }

            bool operator==(const HalfedgeIterator& rhs) const {
                return (hnd_==rhs.hnd_);
            }

            bool operator!=(const HalfedgeIterator& rhs) const {
                return !operator==(rhs);
            }

            HalfedgeIterator& operator++() {
                ++hnd_.idx_;
                assert(mesh_);
                while (mesh_->has_garbage() && mesh_->is_valid(hnd_) && mesh_->is_deleted(hnd_)) ++hnd_.idx_;
                return *this;
            }

            HalfedgeIterator& operator--() {
                --hnd_.idx_;
                assert(mesh_);
                while (mesh_->has_garbage() && mesh_->is_valid(hnd_) && mesh_->is_deleted(hnd_)) --hnd_.idx_;
                return *this;
            }
 
        private:
            Halfedge  hnd_;
            const SurfaceMesh* mesh_;
        };
 

        class EdgeIterator
        {
        public:
            explicit EdgeIterator(Edge e=Edge(), const SurfaceMesh* m=nullptr) : hnd_(e), mesh_(m) {
                if (mesh_ && mesh_->has_garbage()) while (mesh_->is_valid(hnd_) && mesh_->is_deleted(hnd_)) ++hnd_.idx_;
            }

            Edge operator*()  const { return  hnd_; }

            bool operator==(const EdgeIterator& rhs) const {
                return (hnd_==rhs.hnd_);
            }

            bool operator!=(const EdgeIterator& rhs) const {
                return !operator==(rhs);
            }

            EdgeIterator& operator++() {
                ++hnd_.idx_;
                assert(mesh_);
                while (mesh_->has_garbage() && mesh_->is_valid(hnd_) && mesh_->is_deleted(hnd_)) ++hnd_.idx_;
                return *this;
            }

            EdgeIterator& operator--() {
                --hnd_.idx_;
                assert(mesh_);
                while (mesh_->has_garbage() && mesh_->is_valid(hnd_) && mesh_->is_deleted(hnd_)) --hnd_.idx_;
                return *this;
            }
 
        private:
            Edge  hnd_;
            const SurfaceMesh* mesh_;
        };
 

        class FaceIterator
        {
        public:
            explicit FaceIterator(Face f=Face(), const SurfaceMesh* m=nullptr) : hnd_(f), mesh_(m) {
                if (mesh_ && mesh_->has_garbage()) while (mesh_->is_valid(hnd_) && mesh_->is_deleted(hnd_)) ++hnd_.idx_;
            }

            Face operator*()  const { return  hnd_; }

            bool operator==(const FaceIterator& rhs) const {
                return (hnd_==rhs.hnd_);
            }

            bool operator!=(const FaceIterator& rhs) const {
                return !operator==(rhs);
            }

            FaceIterator& operator++() {
                ++hnd_.idx_;
                assert(mesh_);
                while (mesh_->has_garbage() && mesh_->is_valid(hnd_) && mesh_->is_deleted(hnd_)) ++hnd_.idx_;
                return *this;
            }

            FaceIterator& operator--() {
                --hnd_.idx_;
                assert(mesh_);
                while (mesh_->has_garbage() && mesh_->is_valid(hnd_) && mesh_->is_deleted(hnd_)) --hnd_.idx_;
                return *this;
            }
 
        private:
            Face  hnd_;
            const SurfaceMesh* mesh_;
        };
 
 
 
    public: //-------------------------- containers for C++11 range-based for loops

        class VertexContainer
        {
        public:
            VertexContainer(VertexIterator _begin, VertexIterator _end) : begin_(_begin), end_(_end) {}
            VertexIterator begin() const { return begin_; }
            VertexIterator end()   const { return end_;   }
        private:
            VertexIterator begin_, end_;
        };
 

        class HalfedgeContainer
        {
        public:
            HalfedgeContainer(HalfedgeIterator _begin, HalfedgeIterator _end) : begin_(_begin), end_(_end) {}
            HalfedgeIterator begin() const { return begin_; }
            HalfedgeIterator end()   const { return end_;   }
        private:
            HalfedgeIterator begin_, end_;
        };
 

        class EdgeContainer
        {
        public:
            EdgeContainer(EdgeIterator _begin, EdgeIterator _end) : begin_(_begin), end_(_end) {}
            EdgeIterator begin() const { return begin_; }
            EdgeIterator end()   const { return end_;   }
        private:
            EdgeIterator begin_, end_;
        };
 

        class FaceContainer
        {
        public:
            FaceContainer(FaceIterator _begin, FaceIterator _end) : begin_(_begin), end_(_end) {}
            FaceIterator begin() const { return begin_; }
            FaceIterator end()   const { return end_;   }
        private:
            FaceIterator begin_, end_;
        };
 
 
 
    public: //---------------------------------------------------- circulator types

        class VertexAroundVertexCirculator
        {
        public:
            explicit VertexAroundVertexCirculator(const SurfaceMesh* m = nullptr, Vertex v = Vertex())
                : mesh_(m), active_(true)
            {
                if (mesh_) halfedge_ = mesh_->out_halfedge(v);
            }

            bool operator==(const VertexAroundVertexCirculator& rhs) const {
                assert(mesh_);
                return (active_ && (mesh_==rhs.mesh_) && (halfedge_==rhs.halfedge_));
            }

            bool operator!=(const VertexAroundVertexCirculator& rhs) const {
                return !operator==(rhs);
            }

            VertexAroundVertexCirculator& operator++() {
                assert(mesh_);
                halfedge_ = mesh_->prev_around_source(halfedge_);
                active_ = true;
                return *this;
            }

            VertexAroundVertexCirculator& operator--() {
                assert(mesh_);
                halfedge_ = mesh_->next_around_source(halfedge_);
                return *this;
            }

            Vertex operator*() const {
                assert(mesh_);
                return mesh_->target(halfedge_);
            }

            operator bool() const { return halfedge_.is_valid(); }

            Halfedge halfedge() const { return halfedge_; }

            VertexAroundVertexCirculator& begin() { active_=!halfedge_.is_valid(); return *this; }
            VertexAroundVertexCirculator& end()   { active_=true;  return *this; }
 
        private:
            const SurfaceMesh*  mesh_;
            Halfedge         halfedge_;
            // helper for C++11 range-based for-loops
            bool active_;
        };
 

        class HalfedgeAroundVertexCirculator
        {
        public:
            explicit HalfedgeAroundVertexCirculator(const SurfaceMesh* m=nullptr, Vertex v=Vertex())
            : mesh_(m), active_(true)
            {
                if (mesh_) halfedge_ = mesh_->out_halfedge(v);
            }

            bool operator==(const HalfedgeAroundVertexCirculator& rhs) const {
                assert(mesh_);
                return (active_ && (mesh_==rhs.mesh_) && (halfedge_==rhs.halfedge_));
            }

            bool operator!=(const HalfedgeAroundVertexCirculator& rhs) const {
                return !operator==(rhs);
            }

            HalfedgeAroundVertexCirculator& operator++() {
                assert(mesh_);
                halfedge_ = mesh_->prev_around_source(halfedge_);
                active_ = true;
                return *this;
            }

            HalfedgeAroundVertexCirculator& operator--() {
                assert(mesh_);
                halfedge_ = mesh_->next_around_source(halfedge_);
                return *this;
            }

            Halfedge operator*() const { return halfedge_; }

            operator bool() const { return halfedge_.is_valid(); }

            HalfedgeAroundVertexCirculator& begin() { active_=!halfedge_.is_valid(); return *this; }
            HalfedgeAroundVertexCirculator& end()   { active_=true;  return *this; }
 
        private:
            const SurfaceMesh*  mesh_;
            Halfedge         halfedge_;
            // helper for C++11 range-based for-loops
            bool active_;
        };
 

        class FaceAroundVertexCirculator
        {
        public:
            explicit FaceAroundVertexCirculator(const SurfaceMesh* m=nullptr, Vertex v=Vertex())
            : mesh_(m), active_(true)
            {
                if (mesh_) {
                    halfedge_ = mesh_->out_halfedge(v);
                    if (halfedge_.is_valid() && mesh_->is_border(halfedge_))
                        operator++();
                }
            }

            bool operator==(const FaceAroundVertexCirculator& rhs) const {
                assert(mesh_);
                return (active_ && (mesh_==rhs.mesh_) && (halfedge_==rhs.halfedge_));
            }

            bool operator!=(const FaceAroundVertexCirculator& rhs) const {
                return !operator==(rhs);
            }

            FaceAroundVertexCirculator& operator++() {
                assert(mesh_ && halfedge_.is_valid());
                do {
                    halfedge_ = mesh_->prev_around_source(halfedge_);
                } while (mesh_->is_border(halfedge_));
                active_ = true;
                return *this;
            }

            FaceAroundVertexCirculator& operator--() {
                assert(mesh_ && halfedge_.is_valid());
                do
                    halfedge_ = mesh_->next_around_source(halfedge_);
                while (mesh_->is_border(halfedge_));
                return *this;
            }

            Face operator*() const {
                assert(mesh_ && halfedge_.is_valid());
                return mesh_->face(halfedge_);
            }

            operator bool() const { return halfedge_.is_valid(); }

            FaceAroundVertexCirculator& begin() { active_=!halfedge_.is_valid(); return *this; }
            FaceAroundVertexCirculator& end()   { active_=true;  return *this; }
 
        private:
            const SurfaceMesh*  mesh_;
            Halfedge         halfedge_;
            // helper for C++11 range-based for-loops
            bool active_;
        };
 

        class VertexAroundFaceCirculator
        {
        public:
            explicit VertexAroundFaceCirculator(const SurfaceMesh* m=nullptr, Face f=Face())
            : mesh_(m), active_(true)
            {
                if (mesh_) halfedge_ = mesh_->halfedge(f);
            }

            bool operator==(const VertexAroundFaceCirculator& rhs) const {
                assert(mesh_);
                return (active_ && (mesh_==rhs.mesh_) && (halfedge_==rhs.halfedge_));
            }

            bool operator!=(const VertexAroundFaceCirculator& rhs) const {
                return !operator==(rhs);
            }

            VertexAroundFaceCirculator& operator++() {
                assert(mesh_ && halfedge_.is_valid());
                halfedge_ = mesh_->next(halfedge_);
                active_ = true;
                return *this;
            }

            VertexAroundFaceCirculator& operator--() {
                assert(mesh_ && halfedge_.is_valid());
                halfedge_ = mesh_->prev(halfedge_);
                return *this;
            }

            Vertex operator*() const {
                assert(mesh_ && halfedge_.is_valid());
                return mesh_->target(halfedge_);
            }

            VertexAroundFaceCirculator& begin() { active_=false; return *this; }
            VertexAroundFaceCirculator& end()   { active_=true;  return *this; }
 
        private:
            const SurfaceMesh*  mesh_;
            Halfedge         halfedge_;
            // helper for C++11 range-based for-loops
            bool active_;
        };
 

        class HalfedgeAroundFaceCirculator
        {
        public:
            explicit HalfedgeAroundFaceCirculator(const SurfaceMesh* m=nullptr, Face f=Face())
            : mesh_(m), active_(true)
            {
                if (mesh_) halfedge_ = mesh_->halfedge(f);
            }

            bool operator==(const HalfedgeAroundFaceCirculator& rhs) const {
                assert(mesh_);
                return (active_ && (mesh_==rhs.mesh_) && (halfedge_==rhs.halfedge_));
            }

            bool operator!=(const HalfedgeAroundFaceCirculator& rhs) const {
                return !operator==(rhs);
            }

            HalfedgeAroundFaceCirculator& operator++() {
                assert(mesh_ && halfedge_.is_valid());
                halfedge_ = mesh_->next(halfedge_);
                active_ = true;
                return *this;
            }

            HalfedgeAroundFaceCirculator& operator--() {
                assert(mesh_ && halfedge_.is_valid());
                halfedge_ = mesh_->prev(halfedge_);
                return *this;
            }

            Halfedge operator*() const { return halfedge_; }

            HalfedgeAroundFaceCirculator& begin() { active_=false; return *this; }
            HalfedgeAroundFaceCirculator& end()   { active_=true;  return *this; }
 
        private:
            const SurfaceMesh*  mesh_;
            Halfedge         halfedge_;
            // helper for C++11 range-based for-loops
            bool active_;
        };
 
 
 
    public: //-------------------------------------------- constructor / destructor



        SurfaceMesh();

        ~SurfaceMesh() override = default;

        SurfaceMesh(const SurfaceMesh& rhs) { operator=(rhs); }

        SurfaceMesh& operator=(const SurfaceMesh& rhs);

        SurfaceMesh& operator+=(const SurfaceMesh& other) { join(other); return *this; }

        SurfaceMesh& join(const SurfaceMesh& other);

        SurfaceMesh& assign(const SurfaceMesh& rhs);


        bool read(const std::string& filename);

        bool write(const std::string& filename) const;
 
    public: //----------------------------------------------- add new vertex / face



        Vertex add_vertex(const vec3& p) { Vertex v = new_vertex(); vpoint_[v] = p; return v; }

        Face add_face(const std::vector<Vertex>& vertices);

        Face add_triangle(Vertex v1, Vertex v2, Vertex v3);

        Face add_quad(Vertex v1, Vertex v2, Vertex v3, Vertex v4);

 
 
    public: //--------------------------------------------------- memory management



        unsigned int vertices_size() const { return (unsigned int) vprops_.size(); }
        unsigned int halfedges_size() const { return (unsigned int) hprops_.size(); }
        unsigned int edges_size() const { return (unsigned int) eprops_.size(); }
        unsigned int faces_size() const { return (unsigned int) fprops_.size(); }
 

        unsigned int n_vertices() const { return vertices_size() - deleted_vertices_; }
        unsigned int n_halfedges() const { return halfedges_size() - 2*deleted_edges_; }
        unsigned int n_edges() const { return edges_size() - deleted_edges_; }
        unsigned int n_faces() const { return faces_size() - deleted_faces_; }

        void clear();

        void reserve(unsigned int n_vertices, unsigned int n_edges, unsigned int n_faces);

        void resize(unsigned int nv, unsigned int ne, unsigned int nf) {
            vprops_.resize(nv);
            hprops_.resize(2 * ne);
            eprops_.resize(ne);
            fprops_.resize(nf);
        }

        bool has_garbage() const { return garbage_; }

        void collect_garbage();
 

        bool is_deleted(Vertex v) const {
            return vdeleted_[v];
        }

        bool is_deleted(Halfedge h) const {
            return edeleted_[edge(h)];
        }

        bool is_deleted(Edge e) const {
            return edeleted_[e];
        }

        bool is_deleted(Face f) const {
            return fdeleted_[f];
        }
 

        bool is_valid(Vertex v) const {
            return (0 <= v.idx()) && (v.idx() < (int)vertices_size());
        }

        bool is_valid(Halfedge h) const {
            return (0 <= h.idx()) && (h.idx() < (int)halfedges_size());
        }

        bool is_valid(Edge e) const {
            return (0 <= e.idx()) && (e.idx() < (int)edges_size());
        }

        bool is_valid(Face f) const {
            return (0 <= f.idx()) && (f.idx() < (int)faces_size());
        }

 
 
 
    public: //---------------------------------------------- low-level connectivity



        Halfedge out_halfedge(Vertex v) const {
            return vconn_[v].halfedge_;
        }

        void set_out_halfedge(Vertex v, Halfedge h) {
            vconn_[v].halfedge_ = h;
        }

        bool is_border(Vertex v) const {
            Halfedge h(out_halfedge(v));
            return (!(h.is_valid() && face(h).is_valid()));
        }

        bool is_isolated(Vertex v) const {
            return !out_halfedge(v).is_valid();
        }

        bool is_manifold(Vertex v) const
        {
            // [Liangliang: I doubt. It should also check if more than 1 cones meet at the same vertex.
            //              See the "resolve_non_manifold_vertices()" in manifold_builder.cpp
 
            // The vertex is non-manifold if more than one gap exists, i.e.
            // more than one outgoing boundary halfedge.
            int n(0);
            HalfedgeAroundVertexCirculator hit = halfedges(v), hend=hit;
            if (hit) do
            {
                if (is_border(*hit))
                    ++n;
            }
            while (++hit!=hend);
            return n<2;
        }

        bool is_degenerate(Face f) const;

        Vertex target(Halfedge h) const {
            return hconn_[h].vertex_;
        }

        Vertex source(Halfedge h) const {
            return target(opposite(h));
        }

        void set_target(Halfedge h, Vertex v) {
            hconn_[h].vertex_ = v;
        }

        Face face(Halfedge h) const {
            return hconn_[h].face_;
        }

        void set_face(Halfedge h, Face f) {
            hconn_[h].face_ = f;
        }

        Halfedge next(Halfedge h) const {
            return hconn_[h].next_;
        }

        void set_next(Halfedge h, Halfedge nh) {
            hconn_[h].next_ = nh;
            hconn_[nh].prev_ = h;
        }

        Halfedge prev(Halfedge h) const {
            return hconn_[h].prev_;
        }

        Halfedge opposite(Halfedge h) const {
            return Halfedge((h.idx() & 1) ? h.idx()-1 : h.idx()+1);
        }

        Halfedge prev_around_source(Halfedge h) const {
            return opposite(prev(h));
        }

        Halfedge next_around_source(Halfedge h) const {
            return next(opposite(h));
        }

        Halfedge prev_around_target(Halfedge h) const {
            return prev(opposite(h));
        }

        Halfedge next_around_target(Halfedge h) const {
            return opposite(next(h));
        }

        Edge edge(Halfedge h) const {
            return Edge(h.idx() >> 1);
        }

        bool is_border(Halfedge h) const {
            return !face(h).is_valid();
        }
 

        Halfedge halfedge(Edge e, unsigned int i) const {
            assert(i<=1);
            return Halfedge(static_cast<int>((e.idx() << 1) + i));
        }

        Vertex vertex(Edge e, unsigned int i) const {
            assert(i<=1);
            return target(halfedge(e, i));
        }

        Face face(Edge e, unsigned int i) const {
            assert(i<=1);
            return face(halfedge(e, i));
        }

        bool is_border(Edge e) const {
            return (is_border(halfedge(e, 0)) || is_border(halfedge(e, 1)));
        }

        Halfedge halfedge(Face f) const {
            return fconn_[f].halfedge_;
        }

        void set_halfedge(Face f, Halfedge h) {
            fconn_[f].halfedge_ = h;
        }

        bool is_border(Face f) const
        {
            Halfedge h  = halfedge(f);
            Halfedge hh = h;
            do
            {
                if (is_border(opposite(h)))
                    return true;
                h = next(h);
            }
            while (h != hh);
            return false;
        }

 
 
 
    public: //--------------------------------------------------- property handling



        template <class T> VertexProperty<T> add_vertex_property(const std::string& name, const T t=T()) {
            return VertexProperty<T>(vprops_.add<T>(name, t));
        }

        template <class T> HalfedgeProperty<T> add_halfedge_property(const std::string& name, const T t=T()) {
            return HalfedgeProperty<T>(hprops_.add<T>(name, t));
        }

        template <class T> EdgeProperty<T> add_edge_property(const std::string& name, const T t=T()) {
            return EdgeProperty<T>(eprops_.add<T>(name, t));
        }

        template <class T> FaceProperty<T> add_face_property(const std::string& name, const T t=T()) {
            return FaceProperty<T>(fprops_.add<T>(name, t));
        }

        template <class T> ModelProperty<T> add_model_property(const std::string& name, const T t=T()) {
            return ModelProperty<T>(mprops_.add<T>(name, t));
        }
 

        template <class T> VertexProperty<T> get_vertex_property(const std::string& name) const {
            return VertexProperty<T>(vprops_.get<T>(name));
        }

        template <class T> HalfedgeProperty<T> get_halfedge_property(const std::string& name) const {
            return HalfedgeProperty<T>(hprops_.get<T>(name));
        }

        template <class T> EdgeProperty<T> get_edge_property(const std::string& name) const {
            return EdgeProperty<T>(eprops_.get<T>(name));
        }

        template <class T> FaceProperty<T> get_face_property(const std::string& name) const {
            return FaceProperty<T>(fprops_.get<T>(name));
        }

        template <class T> ModelProperty<T> get_model_property(const std::string& name) const {
            return ModelProperty<T>(mprops_.get<T>(name));
        }

        template <class T> VertexProperty<T> vertex_property(const std::string& name, const T t=T()) {
            return VertexProperty<T>(vprops_.get_or_add<T>(name, t));
        }

        template <class T> HalfedgeProperty<T> halfedge_property(const std::string& name, const T t=T()) {
            return HalfedgeProperty<T>(hprops_.get_or_add<T>(name, t));
        }

        template <class T> EdgeProperty<T> edge_property(const std::string& name, const T t=T()) {
            return EdgeProperty<T>(eprops_.get_or_add<T>(name, t));
        }

        template <class T> FaceProperty<T> face_property(const std::string& name, const T t=T()) {
            return FaceProperty<T>(fprops_.get_or_add<T>(name, t));
        }

        template <class T> ModelProperty<T> model_property(const std::string& name, const T t=T()) {
            return ModelProperty<T>(mprops_.get_or_add<T>(name, t));
        }
 

        template<class T>
        bool remove_vertex_property(VertexProperty<T> &p) { return vprops_.remove(p); }

        bool remove_vertex_property(const std::string &n) { return vprops_.remove(n); }

        template<class T>
        bool remove_halfedge_property(HalfedgeProperty<T> &p) { return hprops_.remove(p); }

        bool remove_halfedge_property(const std::string &n) { return hprops_.remove(n); }

        template<class T>
        bool remove_edge_property(EdgeProperty<T> &p) { return eprops_.remove(p); }

        bool remove_edge_property(const std::string &n) { return eprops_.remove(n); }

        template<class T>
        bool remove_face_property(FaceProperty<T> &p) { return fprops_.remove(p); }

        bool remove_face_property(const std::string &n) { return fprops_.remove(n); }

        template<class T>
        bool remove_model_property(ModelProperty<T> &p) { return mprops_.remove(p); }

        bool remove_model_property(const std::string &n) { return mprops_.remove(n); }

        bool rename_vertex_property(const std::string &old_name, const std::string &new_name) {
            return vprops_.rename(old_name, new_name);
        }

        bool rename_face_property(const std::string &old_name, const std::string &new_name) {
            return fprops_.rename(old_name, new_name);
        }

        bool rename_edge_property(const std::string &old_name, const std::string &new_name) {
            return eprops_.rename(old_name, new_name);
        }

        bool rename_halfedge_property(const std::string &old_name, const std::string &new_name) {
            return hprops_.rename(old_name, new_name);
        }

        bool rename_model_property(const std::string &old_name, const std::string &new_name) {
            return mprops_.rename(old_name, new_name);
        }
 

        const std::type_info& get_vertex_property_type(const std::string& name) const {
            return vprops_.get_type(name);
        }

        const std::type_info& get_halfedge_property_type(const std::string& name) const {
            return hprops_.get_type(name);
        }

        const std::type_info& get_edge_property_type(const std::string& name) const {
            return eprops_.get_type(name);
        }

        const std::type_info& get_face_property_type(const std::string& name) const {
            return fprops_.get_type(name);
        }

        const std::type_info& get_model_property_type(const std::string& name) const {
            return mprops_.get_type(name);
        }
 

        std::vector<std::string> vertex_properties() const {
            return vprops_.properties();
        }

        std::vector<std::string> halfedge_properties() const {
            return hprops_.properties();
        }

        std::vector<std::string> edge_properties() const {
            return eprops_.properties();
        }

        std::vector<std::string> face_properties() const {
            return fprops_.properties();
        }

        std::vector<std::string> model_properties() const {
            return mprops_.properties();
        }

        void property_stats(std::ostream &output) const override;

 
 
    public: //--------------------------------------------- iterators & circulators



        VertexIterator vertices_begin() const {
            return VertexIterator(Vertex(0), this);
        }

        VertexIterator vertices_end() const {
            return VertexIterator(Vertex(static_cast<int>(vertices_size())), this);
        }

        VertexContainer vertices() const {
            return VertexContainer(vertices_begin(), vertices_end());
        }

        HalfedgeIterator halfedges_begin() const {
            return HalfedgeIterator(Halfedge(0), this);
        }

        HalfedgeIterator halfedges_end() const {
            return HalfedgeIterator(Halfedge(static_cast<int>(halfedges_size())), this);
        }

        HalfedgeContainer halfedges() const {
            return HalfedgeContainer(halfedges_begin(), halfedges_end());
        }

        EdgeIterator edges_begin() const {
            return EdgeIterator(Edge(0), this);
        }

        EdgeIterator edges_end() const {
            return EdgeIterator(Edge(static_cast<int>(edges_size())), this);
        }

        EdgeContainer edges() const {
            return EdgeContainer(edges_begin(), edges_end());
        }

        FaceIterator faces_begin() const {
            return FaceIterator(Face(0), this);
        }

        FaceIterator faces_end() const {
            return FaceIterator(Face(static_cast<int>(faces_size())), this);
        }

        FaceContainer faces() const {
            return FaceContainer(faces_begin(), faces_end());
        }

        VertexAroundVertexCirculator vertices(Vertex v) const {
            return VertexAroundVertexCirculator(this, v);
        }

        HalfedgeAroundVertexCirculator halfedges(Vertex v) const {
            return HalfedgeAroundVertexCirculator(this, v);
        }

        FaceAroundVertexCirculator faces(Vertex v) const {
            return FaceAroundVertexCirculator(this, v);
        }

        VertexAroundFaceCirculator vertices(Face f) const {
            return VertexAroundFaceCirculator(this, f);
        }

        HalfedgeAroundFaceCirculator halfedges(Face f) const {
            return HalfedgeAroundFaceCirculator(this, f);
        }

 
 
    public: //--------------------------------------------- higher-level operations



        bool is_closed() const;

        bool is_triangle_mesh() const;

        bool is_quad_mesh() const;

        void triangulate();

        void triangulate(Face f);

        void reverse_orientation();

        bool is_collapse_ok(Halfedge h) const;

        void collapse(Halfedge h);
 

        Vertex split(Face f, const vec3& p) { Vertex v=add_vertex(p); split(f,v); return v; }

        void split(Face f, Vertex v);
 

        Halfedge split(Edge e, const vec3& p) { return split(e, add_vertex(p)); }
 

        Halfedge split(Edge e, Vertex v);
 

        Halfedge insert_vertex(Edge e, const vec3& p)
        {
            return insert_vertex(halfedge(e,0), add_vertex(p));
        }

        Halfedge insert_vertex(Edge e, Vertex v)
        {
            return insert_vertex(halfedge(e,0), v);
        }

        Halfedge insert_vertex(Halfedge h, Vertex v);

        bool join_edges(Vertex v);
        bool can_join_edges(Vertex v) const;
 

        Halfedge insert_edge(Halfedge h0, Halfedge h1);
 

        bool is_flip_ok(Edge e) const;

        void flip(Edge e);
 

        bool is_stitch_ok(Halfedge h0, Halfedge h1);

        void stitch(Halfedge h0, Halfedge h1);
 

        unsigned int valence(Vertex v) const;

        unsigned int valence(Face f) const;

        Halfedge find_halfedge(Vertex start, Vertex end) const;

        Edge find_edge(Vertex a, Vertex b) const;

        void delete_vertex(Vertex v);

        void delete_edge(Edge e);

        void delete_face(Face f);

 
 
    public: //------------------------------------------ geometry-related functions



        const vec3& position(Vertex v) const { return vpoint_[v]; }

        vec3& position(Vertex v) { return vpoint_[v]; }

        const std::vector<vec3>& points() const override { return vpoint_.vector(); }

        std::vector<vec3>& points() override { return vpoint_.vector(); }

        void update_face_normals();

        vec3 compute_face_normal(Face f) const;

        void update_vertex_normals();

        vec3 compute_vertex_normal(Vertex v) const;

        float edge_length(Edge e) const;
        float edge_length(Halfedge h) const;

 
 
    private: //---------------------------------------------- allocate new elements

        Vertex new_vertex()
        {
            vprops_.push_back();
            return Vertex(static_cast<int>(vertices_size()-1));
        }

        Halfedge new_edge(Vertex start, Vertex end)
        {
            assert(start != end);
 
            eprops_.push_back();
            hprops_.push_back();
            hprops_.push_back();
 
            Halfedge h0(static_cast<int>(halfedges_size()-2));
            Halfedge h1(static_cast<int>(halfedges_size()-1));
 
            set_target(h0, end);
            set_target(h1, start);
 
            return h0;
        }

        Face new_face()
        {
            fprops_.push_back();
            return Face(static_cast<int>(faces_size()-1));
        }
 
 
    private: //--------------------------------------------------- helper functions

        void adjust_outgoing_halfedges();

        void adjust_outgoing_halfedge(Vertex v);

        void remove_edge(Halfedge h);

        void remove_loop(Halfedge h);

        bool can_merge_vertices(Halfedge h0, Halfedge h1) const;
 
    private: //------------------------------------------------------- private data
 
        PropertyContainer vprops_;
        PropertyContainer hprops_;
        PropertyContainer eprops_;
        PropertyContainer fprops_;
        PropertyContainer mprops_;
 
        VertexProperty<VertexConnectivity>      vconn_;
        HalfedgeProperty<HalfedgeConnectivity>  hconn_;
        FaceProperty<FaceConnectivity>          fconn_;
 
        VertexProperty<bool>  vdeleted_;
        EdgeProperty<bool>    edeleted_;
        FaceProperty<bool>    fdeleted_;
 
        VertexProperty<vec3>  vpoint_;
        VertexProperty<vec3>  vnormal_;
        FaceProperty<vec3>    fnormal_;
 
        unsigned int deleted_vertices_;
        unsigned int deleted_edges_;
        unsigned int deleted_faces_;
        bool garbage_;
 
        // helper data for add_face()
        typedef std::pair<Halfedge, Halfedge>  NextCacheEntry;
        typedef std::vector<NextCacheEntry>    NextCache;
        std::vector<Vertex>      add_face_vertices_;
        std::vector<Halfedge>    add_face_halfedges_;
        std::vector<bool>        add_face_is_new_;
        std::vector<bool>        add_face_needs_adjust_;
        NextCache                add_face_next_cache_;
 
        friend class SurfaceMeshBuilder;
    };
 
 
    //------------------------------------------------------------ output operators

    inline std::ostream& operator<<(std::ostream& os, SurfaceMesh::Vertex v)
    {
        return (os << 'v' << v.idx());
    }

    inline std::ostream& operator<<(std::ostream& os, SurfaceMesh::Halfedge h)
    {
        return (os << 'h' << h.idx());
    }

    inline std::ostream& operator<<(std::ostream& os, SurfaceMesh::Edge e)
    {
        return (os << 'e' << e.idx());
    }

    inline std::ostream& operator<<(std::ostream& os, SurfaceMesh::Face f)
    {
        return (os << 'f' << f.idx());
    }
 
} // namespace easy3d
 
#endif // EASY3D_CORE_SURFACE_MESH_H