surface_mesh_builder.h

/********************************************************************
 * Copyright (C) 2015 Liangliang Nan <liangliang.nan@gmail.com>
 * https://3d.bk.tudelft.nl/liangliang/
 *
 * This file is part of Easy3D. If it is useful in your research/work,
 * I would be grateful if you show your appreciation by citing it:
 * ------------------------------------------------------------------
 *      Liangliang Nan.
 *      Easy3D: a lightweight, easy-to-use, and efficient C++ library
 *      for processing and rendering 3D data.
 *      Journal of Open Source Software, 6(64), 3255, 2021.
 * ------------------------------------------------------------------
 *
 * Easy3D is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License Version 3
 * as published by the Free Software Foundation.
 *
 * Easy3D 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 ********************************************************************/
 
#ifndef EASY3D_CORE_SURFACE_MESH_BUILDER_H
#define EASY3D_CORE_SURFACE_MESH_BUILDER_H
 
 
#include <unordered_map>
#include <easy3d/core/surface_mesh.h>
 
 
namespace easy3d {

    class SurfaceMeshBuilder {
    public:
        typedef SurfaceMesh::Vertex   Vertex;   
        typedef SurfaceMesh::Halfedge Halfedge; 
        typedef SurfaceMesh::Face     Face;     
        
    public:
        explicit SurfaceMeshBuilder(SurfaceMesh *mesh);
        ~SurfaceMeshBuilder();
 
        // -------------------------------------------------------------------------------------------------------------

        void begin_surface();

        Vertex add_vertex(const vec3 &p);

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

        void end_surface(bool log_issues = true);
 
        // -------------------------------------------------------------------------------------------------------------

        const std::vector<Vertex> &face_vertices() const { return face_vertices_; }
 
    private:
 
        // A face (without duplicating a vertex) cannot be added to a SurfaceMesh if
        //  - it has less than 3 vertices, or
        //  - it has self duplicated vertices, or
        //  - one of the vertex is out-of-range.
        bool vertices_valid(const std::vector<Vertex> &vertices);
 
        // Copy a vertex v and its attributes.
        // Return the new vertex.
        Vertex copy_vertex(Vertex v);
 
        // A vertex might have been copied a few times. If copies occurred before, the original vertex will never work.
        // To avoid unnecessary duplication, we reuse one of its copy that is not on a closed disk. We test each copy in
        // the order the copies were made. If no valid copy can be found, we make a new copy.
        // If no copy exists and v is on a closed disk, we simply copy it.
        Vertex get(Vertex v);
 
        // Resolve all non-manifold vertices of a mesh.
        // Return the number of non-manifold vertices.
        std::size_t resolve_non_manifold_vertices(SurfaceMesh *mesh);
 
        // Vertices might be copied, for two reasons:
        //  - resolve non-manifoldness. In two phases: during the construction of the mesh by call to 'add_face()' and
        //    in 'resolve_non_manifold_vertices()'.
        //  - ensure boundary consistency. All happen during the construction of the mesh by call to 'add_face()'.
        //
        // The copied vertices: vertices in 'second' were copied from 'first'.
        // Usually only a small number of vertices will be copied, so no need to use vertex property.
        typedef std::unordered_map<Vertex, std::vector<Vertex>, Vertex::Hash> CopyRecord;
 
        // Resolve the non-manifoldness of a vertex that is denoted by an incoming halfedge.
        // @param h The halfedge pointing to the non-manifold vertex.
        // Return the number of vertex copies.
        std::size_t resolve_non_manifold_vertex(Halfedge h, SurfaceMesh *mesh, CopyRecord &copy_record);
 
    private:
        SurfaceMesh *mesh_;
 
        // faces with less than three vertices
        std::size_t num_faces_less_three_vertices_;
 
        // faces with duplicate vertices
        std::size_t num_faces_duplicate_vertices;
 
        // faces with out-of-range vertex indices
        std::size_t num_faces_out_of_range_vertices_;
 
        // faces with unknown topology
        std::size_t num_faces_unknown_topology_;
 
        // record for linking a face to the mesh
        CopyRecord copied_vertices_for_linking_;
        // all copy record
        CopyRecord copied_vertices_;
 
        // The actual vertices after the face was successfully added to the mesh.
        std::vector<Vertex> face_vertices_;
 
        // A vertex property to record the original vertex of each vertex.
        SurfaceMesh::VertexProperty <Vertex> original_vertex_;
 
        // The record of all halfedges (each associated with a valid face) originating from a vertex.
        // This is used for fast query of duplicate edges. All vertices are their original indices.
        //  - first: the index of a vertex
        //  - second: the indices of the target vertices
        std::unordered_map<int, std::vector<int> > outgoing_halfedges_;
    };
 
}
 
#endif // EASY3D_CORE_SURFACE_MESH_BUILDER_H