GCC Code Coverage Report

Directory: ./
File: tests/test_nn_search/main.cpp
Date: 2026-09-07 02:28:19
Exec Total Coverage
Lines: 46 63 73.0%
Functions: 1 1 100.0%
Branches: 82 234 35.0%
Line Branch Exec Source
1 /*
2 * Copyright (c) 2000-2022 Inria
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * * Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 * * Redistributions in binary form must reproduce the above copyright notice,
11 * this list of conditions and the following disclaimer in the documentation
12 * and/or other materials provided with the distribution.
13 * * Neither the name of the ALICE Project-Team nor the names of its
14 * contributors may be used to endorse or promote products derived from this
15 * software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
21 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 * POSSIBILITY OF SUCH DAMAGE.
28 *
29 * Contact: Bruno Levy
30 *
31 * https://www.inria.fr/fr/bruno-levy
32 *
33 * Inria,
34 * Domaine de Voluceau,
35 * 78150 Le Chesnay - Rocquencourt
36 * FRANCE
37 *
38 */
39
40 #include "nn_search_ANN.h"
41 #include <geogram/basic/common.h>
42 #include <geogram/basic/logger.h>
43 #include <geogram/basic/process.h>
44 #include <geogram/basic/command_line.h>
45 #include <geogram/basic/command_line_args.h>
46 #include <geogram/basic/stopwatch.h>
47 #include <geogram/points/nn_search.h>
48 #include <geogram/mesh/mesh.h>
49 #include <geogram/mesh/mesh_io.h>
50
51 #if defined(GEO_OS_APPLE) && defined(__arm64__)
52 #define GEO_APPLE_M1
53 #endif
54
55 36 int main(int argc, char** argv) {
56
57 using namespace GEO;
58
59 36 GEO::initialize(GEO::GEOGRAM_INSTALL_ALL);
60
3/6
✓ Branch 0 taken 36 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 36 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 36 times.
✗ Branch 7 not taken.
 108 geo_register_NearestNeighborSearch_creator(
61 NearestNeighborSearch_ANN, "ANN"
62 );
63
3/6
✓ Branch 0 taken 36 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 36 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 36 times.
✗ Branch 7 not taken.
 108 geo_register_NearestNeighborSearch_creator(
64 NearestNeighborSearch_ANN_BruteForce, "ANN_BruteForce"
65 );
66
67 try {
68
69
2/4
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 36 times.
✗ Branch 5 not taken.
 36 Stopwatch W("Total time");
70
71
2/4
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 36 times.
✗ Branch 5 not taken.
 36 CmdLine::import_arg_group("standard");
72
2/4
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 36 times.
✗ Branch 5 not taken.
 36 CmdLine::import_arg_group("algo");
73
74
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 CmdLine::declare_arg(
75
3/8
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 36 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 36 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 72 "algo:nn_check", "ANN", "reference for nn search"
76 );
77
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 CmdLine::declare_arg(
78
3/8
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 36 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 36 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 72 "algo:nn_nb", 10, "number of nearest neighbors"
79 );
80
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 CmdLine::declare_arg(
81
4/10
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 36 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 36 times.
✓ Branch 9 taken 36 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 108 "by_index", false, "query points by index"
82 );
83
84 std::vector<std::string> filenames;
85
4/6
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 36 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 32 times.
✓ Branch 7 taken 4 times.
 72 if(!CmdLine::parse(argc, argv, filenames, "pointsfile")) {
86 return 1;
87 }
88
89
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 Mesh M;
90
3/6
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 32 times.
✗ Branch 7 not taken.
 64 if(!mesh_load(filenames[0], M)) {
91 return 1;
92 }
93
94
2/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.
 32 std::string NN1_algo = CmdLine::get_arg("algo:nn_search");
95
2/6
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 32 std::string NN2_algo = CmdLine::get_arg("algo:nn_check");
96
2/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.
 32 bool by_index = CmdLine::get_arg_bool("by_index");
97
98
99
2/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.
 32 Logger::out("NN Search") << "Using " << NN1_algo << std::endl;
100
3/8
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 32 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 64 Logger::out("NN Search")
101 << "Using " << NN2_algo << " for reference"
102 << std::endl;
103
104 NearestNeighborSearch_var NN1 = NearestNeighborSearch::create(
105 coord_index_t(M.vertices.dimension()), NN1_algo
106
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 );
107
108 NearestNeighborSearch_var NN2 = NearestNeighborSearch::create(
109 coord_index_t(M.vertices.dimension()), NN2_algo
110
1/2
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
 32 );
111
112
2/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.
 32 NN1->set_points(M.vertices.nb(), M.vertices.point_ptr(0));
113
2/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.
 32 NN2->set_points(M.vertices.nb(), M.vertices.point_ptr(0));
114
115
4/6
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 4 times.
✓ Branch 7 taken 28 times.
 64 index_t nb_neigh = CmdLine::get_arg_uint("algo:nn_nb");
116
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 28 times.
 32 if(nb_neigh > M.vertices.nb()) {
117
2/4
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 4 Logger::warn("NN Search")
118 << "We only have "
119 << M.vertices.nb() << " points and "
120 << nb_neigh << " neighbors are queried !"
121 << std::endl;
122
2/6
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 8 Logger::warn("NN Search")
123 << "Using " << M.vertices.nb() << " neighbors."
124 << std::endl;
125 nb_neigh = M.vertices.nb();
126 }
127
128 vector<index_t> neigh1(nb_neigh);
129 vector<double> sq_dist1(nb_neigh);
130
131 vector<index_t> neigh2(nb_neigh);
132 vector<double> sq_dist2(nb_neigh);
133
134 bool match = true;
135
2/2
✓ Branch 0 taken 35242 times.
✓ Branch 1 taken 32 times.
 35274 for(index_t i = 0; i < M.vertices.nb(); ++i) {
136 const double* q = M.vertices.point_ptr(i);
137
138 neigh1.assign(nb_neigh,NO_INDEX);
139
2/4
✓ Branch 1 taken 35242 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 35242 times.
✗ Branch 5 not taken.
 35242 sq_dist1.assign(nb_neigh,0.0);
140 neigh2.assign(nb_neigh,NO_INDEX);
141
1/2
✓ Branch 1 taken 35242 times.
✗ Branch 2 not taken.
 35242 sq_dist2.assign(nb_neigh,0.0);
142
143
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 35242 times.
 35242 if(by_index) {
144 ✗ NN1->get_nearest_neighbors(
145 nb_neigh, i, neigh1.data(), sq_dist1.data()
146 );
147 ✗ NN2->get_nearest_neighbors(
148 nb_neigh, i, neigh2.data(), sq_dist2.data()
149 );
150 } else {
151
2/4
✓ Branch 1 taken 35242 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 35242 times.
✗ Branch 5 not taken.
 35242 NN1->get_nearest_neighbors(
152 nb_neigh, q, neigh1.data(), sq_dist1.data()
153 );
154
2/4
✓ Branch 1 taken 35242 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 35242 times.
✗ Branch 5 not taken.
 35242 NN2->get_nearest_neighbors(
155 nb_neigh, q, neigh2.data(), sq_dist2.data()
156 );
157 }
158
159
2/2
✓ Branch 0 taken 352354 times.
✓ Branch 1 taken 35242 times.
 387596 for(index_t j=0; j < nb_neigh; ++j) {
160 //std::cerr << i << " " << j << " "
161 // << neigh1[j] << " " << neigh2[j] << std::endl;
162
1/8
✗ Branch 0 not taken.
✓ Branch 1 taken 352354 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 352354 geo_assert(neigh1[j] != NO_INDEX);
163
1/8
✗ Branch 0 not taken.
✓ Branch 1 taken 352354 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 352354 geo_assert(neigh2[j] != NO_INDEX);
164 }
165
166 bool has_mismatch = false;
167
168
2/2
✓ Branch 0 taken 352354 times.
✓ Branch 1 taken 35242 times.
 387596 for(index_t j=0; j < nb_neigh; ++j) {
169
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 352354 times.
 352354 if(sq_dist1[j] != sq_dist2[j]) {
170 has_mismatch = true;
171 match = false;
172 ✗ Logger::err("Mismatch") << i << "[" << j << "]"
173 ✗ << (sq_dist2[j] - sq_dist1[j])
174 << " indices: "
175 ✗ << neigh1[j] << " " << neigh2[j]
176 << std::endl;
177 }
178 }
179
180
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 35242 times.
 35242 if(has_mismatch) {
181 {
182 ✗ std::ostream& out = Logger::err("Mismatch");
183 ✗ out << i << " ref ";
184 ✗ for(index_t j=0; j < nb_neigh; ++j) {
185 ✗ out << sq_dist1[j] << " ";
186 }
187 out << std::endl;
188 }
189 {
190 ✗ std::ostream& out = Logger::err("Mismatch");
191 ✗ out << i << " tst ";
192 ✗ for(index_t j=0; j < nb_neigh; ++j) {
193 ✗ out << sq_dist2[j] << " ";
194 }
195 out << std::endl;
196 }
197 }
198 }
199
1/2
✓ Branch 0 taken 32 times.
✗ Branch 1 not taken.
 32 if(match) {
200
3/6
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 32 times.
✗ Branch 7 not taken.
 64 Logger::out("NN Search")
201 << NN1_algo << " and " << NN2_algo << " match."
202 << std::endl;
203 } else {
204 ✗ Logger::err("NN Search")
205 << NN1_algo << " and " << NN2_algo << " mismatch."
206 << std::endl;
207 return 2;
208 }
209 36 }
210 ✗ catch(const std::exception& e) {
211 ✗ std::cerr << "Received an exception: " << e.what() << std::endl;
212 return 1;
213 ✗ }
214
215 32 annClose();
216
217 32 return 0;
218 }
219