TriangleMesh.h

Go to the documentation of this file.

// ----------------------------------------------------------------------------
// -                        Open3D: www.open3d.org                            -
// ----------------------------------------------------------------------------
// The MIT License (MIT)
//
// Copyright (c) 2018 www.open3d.org
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
// IN THE SOFTWARE.
// ----------------------------------------------------------------------------

#pragma once

#include <Eigen/Core>
#include <memory>
#include <numeric>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#include "Open3D/Geometry/Image.h"
#include "Open3D/Geometry/MeshBase.h"
#include "Open3D/Utility/Helper.h"

namespace open3d {
namespace geometry {

class PointCloud;
class TetraMesh;

class TriangleMesh : public MeshBase {
public:
    TriangleMesh() : MeshBase(Geometry::GeometryType::TriangleMesh) {}
    TriangleMesh(const std::vector<Eigen::Vector3d> &vertices,
                 const std::vector<Eigen::Vector3i> &triangles)
        : MeshBase(Geometry::GeometryType::TriangleMesh, vertices),
          triangles_(triangles) {}
    ~TriangleMesh() override {}

public:
    virtual TriangleMesh &Clear() override;
    virtual TriangleMesh &Transform(
            const Eigen::Matrix4d &transformation) override;
    virtual TriangleMesh &Rotate(const Eigen::Matrix3d &R,
                                 bool center = true) override;

public:
    TriangleMesh &operator+=(const TriangleMesh &mesh);
    TriangleMesh operator+(const TriangleMesh &mesh) const;

    bool HasTriangles() const {
        return vertices_.size() > 0 && triangles_.size() > 0;
    }

    bool HasTriangleNormals() const {
        return HasTriangles() && triangles_.size() == triangle_normals_.size();
    }

    bool HasAdjacencyList() const {
        return vertices_.size() > 0 &&
               adjacency_list_.size() == vertices_.size();
    }

    bool HasTriangleUvs() const {
        return HasTriangles() && triangle_uvs_.size() == 3 * triangles_.size();
    }

    bool HasTextures() const {
        bool is_all_texture_valid = std::accumulate(
                textures_.begin(), textures_.end(), true,
                [](bool a, const Image &b) { return a && !b.IsEmpty(); });
        return !textures_.empty() && is_all_texture_valid;
    }

    bool HasTriangleMaterialIds() const {
        return HasTriangles() &&
               triangle_material_ids_.size() == triangles_.size();
    }

    TriangleMesh &NormalizeNormals() {
        MeshBase::NormalizeNormals();
        for (size_t i = 0; i < triangle_normals_.size(); i++) {
            triangle_normals_[i].normalize();
            if (std::isnan(triangle_normals_[i](0))) {
                triangle_normals_[i] = Eigen::Vector3d(0.0, 0.0, 1.0);
            }
        }
        return *this;
    }

    TriangleMesh &ComputeTriangleNormals(bool normalized = true);

    TriangleMesh &ComputeVertexNormals(bool normalized = true);

    TriangleMesh &ComputeAdjacencyList();

    TriangleMesh &RemoveDuplicatedVertices();

    TriangleMesh &RemoveDuplicatedTriangles();

    TriangleMesh &RemoveUnreferencedVertices();

    TriangleMesh &RemoveDegenerateTriangles();

    TriangleMesh &RemoveNonManifoldEdges();

    TriangleMesh &MergeCloseVertices(double eps);

    std::shared_ptr<TriangleMesh> FilterSharpen(
            int number_of_iterations,
            double strength,
            FilterScope scope = FilterScope::All) const;

    std::shared_ptr<TriangleMesh> FilterSmoothSimple(
            int number_of_iterations,
            FilterScope scope = FilterScope::All) const;

    std::shared_ptr<TriangleMesh> FilterSmoothLaplacian(
            int number_of_iterations,
            double lambda,
            FilterScope scope = FilterScope::All) const;

    std::shared_ptr<TriangleMesh> FilterSmoothTaubin(
            int number_of_iterations,
            double lambda = 0.5,
            double mu = -0.53,
            FilterScope scope = FilterScope::All) const;

    int EulerPoincareCharacteristic() const;

    std::vector<Eigen::Vector2i> GetNonManifoldEdges(
            bool allow_boundary_edges = true) const;

    bool IsEdgeManifold(bool allow_boundary_edges = true) const;

    std::vector<int> GetNonManifoldVertices() const;

    bool IsVertexManifold() const;

    std::vector<Eigen::Vector2i> GetSelfIntersectingTriangles() const;

    bool IsSelfIntersecting() const;

    bool IsBoundingBoxIntersecting(const TriangleMesh &other) const;

    bool IsIntersecting(const TriangleMesh &other) const;

    bool IsOrientable() const;

    bool IsWatertight() const;

    bool OrientTriangles();

    std::unordered_map<Eigen::Vector2i,
                       std::vector<int>,
                       utility::hash_eigen::hash<Eigen::Vector2i>>
    GetEdgeToTrianglesMap() const;

    std::unordered_map<Eigen::Vector2i,
                       std::vector<int>,
                       utility::hash_eigen::hash<Eigen::Vector2i>>
    GetEdgeToVerticesMap() const;

    static double ComputeTriangleArea(const Eigen::Vector3d &p0,
                                      const Eigen::Vector3d &p1,
                                      const Eigen::Vector3d &p2);

    double GetTriangleArea(size_t triangle_idx) const;

    static inline Eigen::Vector3i GetOrderedTriangle(int vidx0,
                                                     int vidx1,
                                                     int vidx2) {
        if (vidx0 > vidx2) {
            std::swap(vidx0, vidx2);
        }
        if (vidx0 > vidx1) {
            std::swap(vidx0, vidx1);
        }
        if (vidx1 > vidx2) {
            std::swap(vidx1, vidx2);
        }
        return Eigen::Vector3i(vidx0, vidx1, vidx2);
    }

    double GetSurfaceArea() const;

    double GetSurfaceArea(std::vector<double> &triangle_areas) const;

    static Eigen::Vector4d ComputeTrianglePlane(const Eigen::Vector3d &p0,
                                                const Eigen::Vector3d &p1,
                                                const Eigen::Vector3d &p2);

    Eigen::Vector4d GetTrianglePlane(size_t triangle_idx) const;

    static inline Eigen::Vector2i GetOrderedEdge(int vidx0, int vidx1) {
        return Eigen::Vector2i(std::min(vidx0, vidx1), std::max(vidx0, vidx1));
    }

    std::shared_ptr<PointCloud> SamplePointsUniformlyImpl(
            size_t number_of_points,
            std::vector<double> &triangle_areas,
            double surface_area,
            bool use_triangle_normal,
            int seed);

    std::shared_ptr<PointCloud> SamplePointsUniformly(
            size_t number_of_points,
            bool use_triangle_normal = false,
            int seed = -1);

    std::shared_ptr<PointCloud> SamplePointsPoissonDisk(
            size_t number_of_points,
            double init_factor = 5,
            const std::shared_ptr<PointCloud> pcl_init = nullptr,
            bool use_triangle_normal = false,
            int seed = -1);

    std::shared_ptr<TriangleMesh> SubdivideMidpoint(
            int number_of_iterations) const;

    std::shared_ptr<TriangleMesh> SubdivideLoop(int number_of_iterations) const;

    std::shared_ptr<TriangleMesh> SimplifyVertexClustering(
            double voxel_size,
            SimplificationContraction contraction =
                    SimplificationContraction::Average) const;

    std::shared_ptr<TriangleMesh> SimplifyQuadricDecimation(
            int target_number_of_triangles) const;

    std::shared_ptr<TriangleMesh> SelectByIndex(
            const std::vector<size_t> &indices) const;

    std::shared_ptr<TriangleMesh> Crop(
            const AxisAlignedBoundingBox &bbox) const;

    std::shared_ptr<TriangleMesh> Crop(const OrientedBoundingBox &bbox) const;

    std::tuple<std::vector<int>, std::vector<size_t>, std::vector<double>>
    ClusterConnectedTriangles() const;

    void RemoveTrianglesByIndex(const std::vector<size_t> &triangle_indices);

    void RemoveTrianglesByMask(const std::vector<bool> &triangle_mask);

    void RemoveVerticesByIndex(const std::vector<size_t> &vertex_indices);

    void RemoveVerticesByMask(const std::vector<bool> &vertex_mask);

    std::shared_ptr<TriangleMesh> DeformAsRigidAsPossible(
            const std::vector<int> &constraint_vertex_indices,
            const std::vector<Eigen::Vector3d> &constraint_vertex_positions,
            size_t max_iter,
            DeformAsRigidAsPossibleEnergy energy =
                    DeformAsRigidAsPossibleEnergy::Spokes,
            double smoothed_alpha = 0.01) const;

    static std::shared_ptr<TriangleMesh> CreateFromPointCloudAlphaShape(
            const PointCloud &pcd,
            double alpha,
            std::shared_ptr<TetraMesh> tetra_mesh = nullptr,
            std::vector<size_t> *pt_map = nullptr);

    static std::shared_ptr<TriangleMesh> CreateFromPointCloudBallPivoting(
            const PointCloud &pcd, const std::vector<double> &radii);

    static std::tuple<std::shared_ptr<TriangleMesh>, std::vector<double>>
    CreateFromPointCloudPoisson(const PointCloud &pcd,
                                size_t depth = 8,
                                size_t width = 0,
                                float scale = 1.1f,
                                bool linear_fit = false);

    static std::shared_ptr<TriangleMesh> CreateTetrahedron(double radius = 1.0);

    static std::shared_ptr<TriangleMesh> CreateOctahedron(double radius = 1.0);

    static std::shared_ptr<TriangleMesh> CreateIcosahedron(double radius = 1.0);

    static std::shared_ptr<TriangleMesh> CreateBox(double width = 1.0,
                                                   double height = 1.0,
                                                   double depth = 1.0);

    static std::shared_ptr<TriangleMesh> CreateSphere(double radius = 1.0,
                                                      int resolution = 20);

    static std::shared_ptr<TriangleMesh> CreateCylinder(double radius = 1.0,
                                                        double height = 2.0,
                                                        int resolution = 20,
                                                        int split = 4);

    static std::shared_ptr<TriangleMesh> CreateCone(double radius = 1.0,
                                                    double height = 2.0,
                                                    int resolution = 20,
                                                    int split = 1);

    static std::shared_ptr<TriangleMesh> CreateTorus(
            double torus_radius = 1.0,
            double tube_radius = 0.5,
            int radial_resolution = 30,
            int tubular_resolution = 20);

    static std::shared_ptr<TriangleMesh> CreateArrow(
            double cylinder_radius = 1.0,
            double cone_radius = 1.5,
            double cylinder_height = 5.0,
            double cone_height = 4.0,
            int resolution = 20,
            int cylinder_split = 4,
            int cone_split = 1);

    static std::shared_ptr<TriangleMesh> CreateCoordinateFrame(
            double size = 1.0,
            const Eigen::Vector3d &origin = Eigen::Vector3d(0.0, 0.0, 0.0));

    static std::shared_ptr<TriangleMesh> CreateMoebius(int length_split = 70,
                                                       int width_split = 15,
                                                       int twists = 1,
                                                       double radius = 1,
                                                       double flatness = 1,
                                                       double width = 1,
                                                       double scale = 1);

protected:
    // Forward child class type to avoid indirect nonvirtual base
    TriangleMesh(Geometry::GeometryType type) : MeshBase(type) {}

    void FilterSmoothLaplacianHelper(
            std::shared_ptr<TriangleMesh> &mesh,
            const std::vector<Eigen::Vector3d> &prev_vertices,
            const std::vector<Eigen::Vector3d> &prev_vertex_normals,
            const std::vector<Eigen::Vector3d> &prev_vertex_colors,
            const std::vector<std::unordered_set<int>> &adjacency_list,
            double lambda,
            bool filter_vertex,
            bool filter_normal,
            bool filter_color) const;

    std::unordered_map<Eigen::Vector2i,
                       double,
                       utility::hash_eigen::hash<Eigen::Vector2i>>
    ComputeEdgeWeightsCot(
            const std::unordered_map<Eigen::Vector2i,
                                     std::vector<int>,
                                     utility::hash_eigen::hash<Eigen::Vector2i>>
                    &edges_to_vertices,
            double min_weight = std::numeric_limits<double>::lowest()) const;

public:
    std::vector<Eigen::Vector3i> triangles_;
    std::vector<Eigen::Vector3d> triangle_normals_;
    std::vector<std::unordered_set<int>> adjacency_list_;
    std::vector<Eigen::Vector2d> triangle_uvs_;
    std::vector<int> triangle_material_ids_;
    std::vector<Image> textures_;
};

}  // namespace geometry
}  // namespace open3d