25884549229

Committed 14 May 2026 08:08PM UTC coverage: 89.708% (+0.04%) from 89.667%

Build # 25884549229

Build Type

push

github

Committed by

dsieger

Commit Message

Report duplicate vertices

Coverage Stats

32 of 33 new or added lines in 1 file covered. (96.97%)

1 existing line in 1 file now uncovered.

5256 of 5859 relevant lines covered (89.71%)

641989.7 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

84.69

/src/pmp/algorithms/analysis.cpp

// Copyright 2026 the Polygon Mesh Processing Library developers.
// SPDX-License-Identifier: MIT

#include "pmp/algorithms/analysis.h"
#include "pmp/algorithms/utilities.h"
#include "pmp/algorithms/differential_geometry.h"
#include "pmp/tolerances.h"

#include <queue>

namespace pmp {

namespace {

// const version of connected_components, count only
int count_connected_components(const SurfaceMesh& mesh)
{
    std::vector<bool> visited(mesh.n_vertices(), false);

    int count = 0;

    for (auto v : mesh.vertices())
    {
        if (visited[v.idx()])
            continue;

        std::queue<Vertex> queue;
        queue.push(v);
        visited[v.idx()] = true;

        while (!queue.empty())
        {
            auto vv = queue.front();
            queue.pop();

            for (auto vc : mesh.vertices(vv))
            {
                if (!visited[vc.idx()])
                {
                    visited[vc.idx()] = true;
                    queue.push(vc);
                }
            }
        }

        ++count;
    }

    return count;
}

bool is_degenerate(const SurfaceMesh& mesh, Face f, Scalar eps)
{
    bool degenerate = false;

    // check for zero area
    if (face_area(mesh, f) < eps * eps)
        degenerate = true;

    // check for short edges
    for (auto h : mesh.halfedges(f))
        if (edge_length(mesh, mesh.edge(h)) < eps)
            degenerate = true;

    return degenerate;
}

// grid-based spatial hashing for duplicate vertex detection
// see Teschner et al., "Optimized Spatial Hashing for Collision Detection of Deformable Objects", VMV, 2003.
using Cell = std::tuple<int, int, int>;

struct CellHash
{
    size_t operator()(const Cell& c) const
    {
        const auto& [x, y, z] = c;
        size_t hx = std::hash<int>{}(x);
        size_t hy = std::hash<int>{}(y);
        size_t hz = std::hash<int>{}(z);
        return hx ^ (hy << 1) ^ (hz << 2);
    }
};

Cell cell_of(const Point& p, Scalar eps)
{
    return {int(std::floor(p[0] / eps)), //
            int(std::floor(p[1] / eps)), //
            int(std::floor(p[2] / eps))};
};

int count_duplicate_vertices(const SurfaceMesh& mesh, Scalar eps)
{
    std::unordered_map<Cell, std::vector<Vertex>, CellHash> grid;
    std::vector<bool> duplicate(mesh.n_vertices(), false);

    for (auto v : mesh.vertices())
    {
        const Point& p = mesh.position(v);

        const Cell c = cell_of(p, eps);

        for (int dx = -1; dx <= 1; ++dx)
            for (int dy = -1; dy <= 1; ++dy)
                for (int dz = -1; dz <= 1; ++dz)
                {
                    const auto& [x, y, z] = c;
                    Cell neighbor{x + dx, y + dy, z + dz};

                    auto it = grid.find(neighbor);

                    if (it == grid.end())
                        continue;

                    for (auto vv : it->second)
                        if (sqrnorm(mesh.position(vv) - p) < eps * eps)
                        {
                            duplicate[vv.idx()] = true;
                            duplicate[v.idx()] = true;
                        }
                }

        grid[c].push_back(v);
    }
    return std::count(duplicate.begin(), duplicate.end(), true);
}

} // namespace

AnalysisReport analyze(const SurfaceMesh& mesh)
{
    AnalysisReport report;

    // basic stats
    report.n_vertices = mesh.n_vertices();
    report.n_edges = mesh.n_edges();
    report.n_faces = mesh.n_faces();

    // mesh type
    report.is_triangle_mesh = mesh.is_triangle_mesh();
    report.is_quad_mesh = mesh.is_quad_mesh();

    // manifoldness and boundary
    for (auto v : mesh.vertices())
    {
        if (!mesh.is_manifold(v))
            report.is_manifold = false;
        if (mesh.is_boundary(v))
            report.has_boundary = true;
        if (mesh.is_isolated(v))
            ++report.n_isolated_vertices;
    }

    // eps according to bounding box diagonal
    constexpr Scalar relative_eps = detail::relative_epsilon<Scalar>();
    constexpr Scalar absolute_eps = detail::absolute_epsilon<Scalar>();
    const Scalar diagonal = bounds(mesh).size();
    const Scalar eps = std::max(relative_eps * diagonal, absolute_eps);

    for (auto f : mesh.faces())
        if (is_degenerate(mesh, f, eps))
            ++report.n_degenerate_faces;

    report.n_components = count_connected_components(mesh);

    report.n_duplicate_vertices = count_duplicate_vertices(mesh, eps);

    return report;
}

std::ostream& operator<<(std::ostream& os, const AnalysisReport& report)
{
    os << "Analysis Report:\n";
    os << "  vertices: " << report.n_vertices << "\n";
    os << "  edges: " << report.n_edges << "\n";
    os << "  faces: " << report.n_faces << "\n";
    os << "  boundary: " << (report.has_boundary ? "yes" : "no") << "\n";
    os << "  manifold: " << (report.is_manifold ? "yes" : "no") << "\n";
    os << "  triangle mesh: " << (report.is_triangle_mesh ? "yes" : "no")
       << "\n";
    os << "  quad mesh: " << (report.is_quad_mesh ? "yes" : "no") << "\n";
    os << "  components: " << report.n_components << "\n";
    os << "  isolated vertices: " << report.n_isolated_vertices << "\n";
    os << "  degenerate faces: " << report.n_degenerate_faces << "\n";
    os << "  duplicate vertices: " << report.n_duplicate_vertices << "\n";
    return os;
}

} // namespace pmp

1	// Copyright 2026 the Polygon Mesh Processing Library developers.
2	// SPDX-License-Identifier: MIT
3
4	#include "pmp/algorithms/analysis.h"
5	#include "pmp/algorithms/utilities.h"
6	#include "pmp/algorithms/differential_geometry.h"
7	#include "pmp/tolerances.h"
8
9	#include <queue>
10
11	namespace pmp {
12
13	namespace {
14
15	// const version of connected_components, count only
16	int count_connected_components(const SurfaceMesh& mesh)	13✔
17	{
18	std::vector<bool> visited(mesh.n_vertices(), false);	13✔
19
20	int count = 0;	13✔
21
22	for (auto v : mesh.vertices())	125✔
23	{
24	if (visited[v.idx()])	112✔
25	continue;	97✔
26
27	std::queue<Vertex> queue;	15✔
28	queue.push(v);	15✔
29	visited[v.idx()] = true;	15✔
30
31	while (!queue.empty())	127✔
32	{
33	auto vv = queue.front();	112✔
34	queue.pop();	112✔
35
36	for (auto vc : mesh.vertices(vv))	432✔
37	{
38	if (!visited[vc.idx()])	320✔
39	{
40	visited[vc.idx()] = true;	97✔
41	queue.push(vc);	97✔
42	}
43	}
44	}
45
46	++count;	15✔
47	}	15✔
48
49	return count;	13✔
50	}	13✔
51
52	bool is_degenerate(const SurfaceMesh& mesh, Face f, Scalar eps)	67✔
53	{
54	bool degenerate = false;	67✔
55
56	// check for zero area
57	if (face_area(mesh, f) < eps * eps)	67✔
58	degenerate = true;	4✔
59
60	// check for short edges
61	for (auto h : mesh.halfedges(f))	595✔
62	if (edge_length(mesh, mesh.edge(h)) < eps)	264✔
63	degenerate = true;	10✔
64
65	return degenerate;	67✔
66	}
67
68	// grid-based spatial hashing for duplicate vertex detection
69	// see Teschner et al., "Optimized Spatial Hashing for Collision Detection of Deformable Objects", VMV, 2003.
70	using Cell = std::tuple<int, int, int>;
71
72	struct CellHash
73	{
74	size_t operator()(const Cell& c) const	2,785✔
75	{
76	const auto& [x, y, z] = c;	2,785✔
77	size_t hx = std::hash<int>{}(x);	2,785✔
78	size_t hy = std::hash<int>{}(y);	2,785✔
79	size_t hz = std::hash<int>{}(z);	2,785✔
80	return hx ^ (hy << 1) ^ (hz << 2);	2,785✔
81	}
82	};
83
84	Cell cell_of(const Point& p, Scalar eps)	112✔
85	{
86	return {int(std::floor(p[0] / eps)), //	112✔
87	int(std::floor(p[1] / eps)), //	112✔
88	int(std::floor(p[2] / eps))};	112✔
89	};
90
91	int count_duplicate_vertices(const SurfaceMesh& mesh, Scalar eps)	13✔
92	{
93	std::unordered_map<Cell, std::vector<Vertex>, CellHash> grid;	13✔
94	std::vector<bool> duplicate(mesh.n_vertices(), false);	13✔
95
96	for (auto v : mesh.vertices())	125✔
97	{
98	const Point& p = mesh.position(v);	112✔
99
100	const Cell c = cell_of(p, eps);	112✔
101
102	for (int dx = -1; dx <= 1; ++dx)	448✔
103	for (int dy = -1; dy <= 1; ++dy)	1,344✔
104	for (int dz = -1; dz <= 1; ++dz)	4,032✔
105	{
106	const auto& [x, y, z] = c;	3,024✔
107	Cell neighbor{x + dx, y + dy, z + dz};	3,024✔
108
109	auto it = grid.find(neighbor);	3,024✔
110
111	if (it == grid.end())	3,024✔
112	continue;	3,017✔
113
114	for (auto vv : it->second)	19✔
115	if (sqrnorm(mesh.position(vv) - p) < eps * eps)	12✔
116	{
117	duplicate[vv.idx()] = true;	12✔
118	duplicate[v.idx()] = true;	12✔
119	}
120	}
121
122	grid[c].push_back(v);	112✔
123	}
124	return std::count(duplicate.begin(), duplicate.end(), true);	26✔
125	}	13✔
126
127	} // namespace
128
129	AnalysisReport analyze(const SurfaceMesh& mesh)	13✔
130	{
131	AnalysisReport report;	13✔
132
133	// basic stats
134	report.n_vertices = mesh.n_vertices();	13✔
135	report.n_edges = mesh.n_edges();	13✔
136	report.n_faces = mesh.n_faces();	13✔
137
138	// mesh type
139	report.is_triangle_mesh = mesh.is_triangle_mesh();	13✔
140	report.is_quad_mesh = mesh.is_quad_mesh();	13✔
141
142	// manifoldness and boundary
143	for (auto v : mesh.vertices())	237✔
144	{
145	if (!mesh.is_manifold(v))	112✔
146	report.is_manifold = false;	1✔
147	if (mesh.is_boundary(v))	112✔
148	report.has_boundary = true;	58✔
149	if (mesh.is_isolated(v))	112✔
150	++report.n_isolated_vertices;	3✔
151	}
152
153	// eps according to bounding box diagonal
154	constexpr Scalar relative_eps = detail::relative_epsilon<Scalar>();	13✔
155	constexpr Scalar absolute_eps = detail::absolute_epsilon<Scalar>();	13✔
156	const Scalar diagonal = bounds(mesh).size();	13✔
157	const Scalar eps = std::max(relative_eps * diagonal, absolute_eps);	13✔
158
159	for (auto f : mesh.faces())	147✔
160	if (is_degenerate(mesh, f, eps))	67✔
161	++report.n_degenerate_faces;	4✔
162
163	report.n_components = count_connected_components(mesh);	13✔
164
165	report.n_duplicate_vertices = count_duplicate_vertices(mesh, eps);	13✔
166
167	return report;	26✔
168	}
169
170	std::ostream& operator<<(std::ostream& os, const AnalysisReport& report)	×
171	{
172	os << "Analysis Report:\n";	×
173	os << " vertices: " << report.n_vertices << "\n";	×
174	os << " edges: " << report.n_edges << "\n";	×
175	os << " faces: " << report.n_faces << "\n";	×
176	os << " boundary: " << (report.has_boundary ? "yes" : "no") << "\n";	×
177	os << " manifold: " << (report.is_manifold ? "yes" : "no") << "\n";	×
178	os << " triangle mesh: " << (report.is_triangle_mesh ? "yes" : "no")	×
179	<< "\n";	×
180	os << " quad mesh: " << (report.is_quad_mesh ? "yes" : "no") << "\n";	×
181	os << " components: " << report.n_components << "\n";	×
182	os << " isolated vertices: " << report.n_isolated_vertices << "\n";	×
183	os << " degenerate faces: " << report.n_degenerate_faces << "\n";	×
NEW 184	os << " duplicate vertices: " << report.n_duplicate_vertices << "\n";	×
UNCOV 185	return os;	×
186	}
187
188	} // namespace pmp

pmp-library / pmp-library / 25884549229

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous