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 virtual 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 : public BaseHandle
        {
            explicit Vertex(int _idx=-1) : BaseHandle(_idx) {}
            std::ostream& operator<<(std::ostream& os) const { return os << 'v' << idx(); }
        };
 
 
        struct Halfedge : public BaseHandle
        {
            explicit Halfedge(int _idx=-1) : BaseHandle(_idx) {}
            std::ostream& operator<<(std::ostream& os) const { return os << 'h' << idx(); }
        };
 
 
        struct Edge : public BaseHandle
        {
            explicit Edge(int _idx=-1) : BaseHandle(_idx) {}
            std::ostream& operator<<(std::ostream& os) const { return os << 'e' << idx(); }
        };
 
 
        struct Face : public 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_; }
 
            // helper for C++11 range-based for-loops
            VertexAroundVertexCirculator& begin() { active_=!halfedge_.is_valid(); return *this; }
            // helper for C++11 range-based for-loops
            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(); }
 
            // helper for C++11 range-based for-loops
            HalfedgeAroundVertexCirculator& begin() { active_=!halfedge_.is_valid(); return *this; }
            // helper for C++11 range-based for-loops
            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(); }
 
            // helper for C++11 range-based for-loops
            FaceAroundVertexCirculator& begin() { active_=!halfedge_.is_valid(); return *this; }
            // helper for C++11 range-based for-loops
            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_);
            }
 
            // helper for C++11 range-based for-loops
            VertexAroundFaceCirculator& begin() { active_=false; return *this; }
            // helper for C++11 range-based for-loops
            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_; }
 
            // helper for C++11 range-based for-loops
            HalfedgeAroundFaceCirculator& begin() { active_=false; return *this; }
            // helper for C++11 range-based for-loops
            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 nvertices,
                     unsigned int nedges,
                     unsigned int nfaces );
 
        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