surface_mesh_geodesic.h

/********************************************************************
 * Copyright (C) 2020-2021 by Liangliang Nan <liangliang.nan@gmail.com>
 * Copyright (C) 2011-2020 the Polygon Mesh Processing Library developers.
 *
 * The code in this file is adapted from the PMP (Polygon Mesh Processing
 * Library) with modifications.
 *      https://github.com/pmp-library/pmp-library
 * The original code was distributed under a MIT-style license, see
 *      https://github.com/pmp-library/pmp-library/blob/master/LICENSE.txt
 ********************************************************************/
 
#ifndef EASY3D_ALGO_SURFACE_MESH_GEODESIC_H
#define EASY3D_ALGO_SURFACE_MESH_GEODESIC_H
 
#include <easy3d/core/surface_mesh.h>
#include <vector>
#include <set>
#include <cfloat>
#include <climits>
 
namespace easy3d {

    class SurfaceMeshGeodesic {
    public:
        explicit SurfaceMeshGeodesic(SurfaceMesh *mesh, bool use_virtual_edges = true);
 
        // destructor
        ~SurfaceMeshGeodesic();

        unsigned int compute(const std::vector<SurfaceMesh::Vertex> &seed,
                             float max_dist = FLT_MAX,
                             unsigned int max_num = INT_MAX,
                             std::vector<SurfaceMesh::Vertex> *neighbors = nullptr);

        float operator()(SurfaceMesh::Vertex v) const { return distance_[v]; }

        void distance_to_texture_coordinates();
 
    private: // private types
        // functor for comparing two vertices w.r.t. their geodesic distance
        class VertexCmp {
        public:
            explicit VertexCmp(const SurfaceMesh::VertexProperty<float> &dist) : dist_(dist) {}
 
            bool operator()(SurfaceMesh::Vertex v0, SurfaceMesh::Vertex v1) const {
                return ((dist_[v0] == dist_[v1]) ? (v0 < v1)
                                                 : (dist_[v0] < dist_[v1]));
            }
 
        private:
            const SurfaceMesh::VertexProperty<float> &dist_;
        };
 
        // priority queue using geodesic distance as sorting criterion
        typedef std::set<SurfaceMesh::Vertex, VertexCmp> PriorityQueue;
 
        // virtual edges for walking through obtuse triangles
        struct VirtualEdge {
            VirtualEdge(SurfaceMesh::Vertex v, float l) : vertex(v), length(l) {}
 
            SurfaceMesh::Vertex vertex;
            float length;
        };
 
        // set for storing virtual edges
        typedef std::map<SurfaceMesh::Halfedge, VirtualEdge> VirtualEdges;
 
    private: // private methods
        void find_virtual_edges();
 
        unsigned int init_front(const std::vector<SurfaceMesh::Vertex> &seed,
                                std::vector<SurfaceMesh::Vertex> *neighbors);
 
        unsigned int propagate_front(float max_dist, unsigned int max_num,
                                     std::vector<SurfaceMesh::Vertex> *neighbors);
 
        void heap_vertex(SurfaceMesh::Vertex v);
 
        float distance(SurfaceMesh::Vertex v0, SurfaceMesh::Vertex v1, SurfaceMesh::Vertex v2, float r0 = FLT_MAX,
                       float r1 = FLT_MAX);
 
    private: // private data
        SurfaceMesh *mesh_;
 
        bool use_virtual_edges_;
        VirtualEdges virtual_edges_;
 
        PriorityQueue *front_;
 
        SurfaceMesh::VertexProperty<float> distance_;
        SurfaceMesh::VertexProperty<bool> processed_;
    };
 
} // namespace easy3d
 
 
#endif  // EASY3D_ALGO_SURFACE_MESH_GEODESIC_H