GCC Code Coverage Report

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 <geogram/parameterization/mesh_param_validator.h>
41			#include <geogram/mesh/mesh.h>
42			#include <geogram/mesh/mesh_geometry.h>
43			#include <algorithm>
44
45			namespace {
46			using namespace GEO;
47
48		✗	double chart_facet_area_2d(
49			Mesh& M, index_t f, Attribute<double>& tex_coord
50			) {
51			double result = 0.0;
52			// Check for empty facet, should not happen.
53		✗	if(M.facets.corners_end(f) == M.facets.corners_begin(f)) {
54			return result;
55			}
56			index_t c0 = M.facets.corners_begin(f);
57			index_t v0 = M.facet_corners.vertex(c0);
58		✗	vec2 p0(tex_coord[2*v0], tex_coord[2*v0+1]);
59		✗	for(
60		✗	index_t c1 = M.facets.corners_begin(f) + 1;
61		✗	c1 + 1 < M.facets.corners_end(f); ++c1
62			) {
63			index_t c2 = c1+1;
64			index_t v1 = M.facet_corners.vertex(c1);
65		✗	vec2 p1(tex_coord[2*v1], tex_coord[2*v1+1]);
66			index_t v2 = M.facet_corners.vertex(c2);
67		✗	vec2 p2(tex_coord[2*v2], tex_coord[2*v2+1]);
68		✗	result += GEO::Geom::triangle_area(
69			p0, p1, p2
70			);
71			}
72			return result;
73			}
74
75		✗	void get_chart_bbox_2d(
76			Mesh& chart, Attribute<double>& tex_coord,
77			double& xmin, double& ymin, double& xmax, double& ymax
78			) {
79		✗	xmin = Numeric::max_float64();
80		✗	ymin = Numeric::max_float64();
81		✗	xmax = -Numeric::max_float64();
82		✗	ymax = -Numeric::max_float64();
83		✗	for(index_t v: chart.vertices) {
84		✗	double x = tex_coord[2*v];
85		✗	double y = tex_coord[2*v+1];
86		✗	xmin = std::min(xmin, x);
87		✗	xmax = std::max(xmax, x);
88		✗	ymin = std::min(ymin, y);
89		✗	ymax = std::max(ymax, y);
90			}
91		✗	}
92
93			}
94
95			namespace GEO {
96
97		✗	ParamValidator::ParamValidator() {
98		✗	graph_size_ = 1024;
99		✗	graph_mem_ = new Numeric::uint8[size_t(graph_size_ * graph_size_)];
100		✗	x_left_ = new int[size_t(graph_size_)];
101		✗	x_right_ = new int[size_t(graph_size_)];
102		✗	max_overlap_ratio_ = 0.005;
103		✗	max_scaling_ = 20.0;
104			// XAtlas is able to put charts in holes, so we no longer
105			// need to split long skinny charts. (before it was 0.25)
106		✗	min_fill_ratio_ = 0.0;
107		✗	verbose_ = false;
108		✗	}
109
110		✗	ParamValidator::~ParamValidator() {
111		✗	delete[] graph_mem_;
112			graph_mem_ = nullptr;
113		✗	delete[] x_left_;
114			x_left_ = nullptr;
115		✗	delete[] x_right_;
116			x_right_ = nullptr;
117		✗	}
118
119		✗	bool ParamValidator::chart_is_valid(Mesh& chart) {
120			Attribute<double> tex_coord;
121		✗	tex_coord.bind_if_is_defined(
122		✗	chart.vertices.attributes(), "tex_coord"
123			);
124		✗	geo_assert(tex_coord.is_bound() && tex_coord.dimension() == 2);
125
126		✗	for(index_t v: chart.vertices) {
127		✗	if(GEO::Numeric::is_nan(tex_coord[2*v]) ||
128		✗	GEO::Numeric::is_nan(tex_coord[2*v+1])) {
129		✗	if(verbose_) {
130		✗	Logger::out("ParamValidator")
131			<< "NaN detected in tex coords" << std::endl;
132			}
133			return false;
134			}
135			}
136
137			// Check global overlaps and "wire-like" charts
138			// (wasting parameter space)
139		✗	compute_fill_and_overlap_ratio(chart);
140		✗	if(verbose_) {
141		✗	Logger::out("ParamValidator")
142			<< "Fill ratio = " << fill_ratio() << std::endl;
143		✗	Logger::out("ParamValidator")
144			<< "Overlap ratio = " << overlap_ratio() << std::endl;
145			}
146
147		✗	double comp_scaling = chart_scaling(chart);
148		✗	if(verbose_) {
149		✗	Logger::out("ParamValidator")
150			<< "Scaling = " << comp_scaling << std::endl;
151			}
152
153
154			// If more than 'min_fill_ratio_' of the parameter space is empty,
155			// reject chart.
156		✗	if(Numeric::is_nan(fill_ratio()) || fill_ratio() < min_fill_ratio_) {
157		✗	if(verbose_) {
158		✗	Logger::out("ParamValidator")
159			<< "----> REJECT: filling ratio"
160			<< std::endl;
161			}
162		✗	return false;
163			}
164
165			// If more than 'max_overlap_ratio_' of the pixels correspond to
166			// more than one facet, reject chart.
167			if(
168		✗	Numeric::is_nan(overlap_ratio()) ||
169		✗	overlap_ratio() > max_overlap_ratio_
170			) {
171		✗	if(verbose_) {
172		✗	Logger::out("ParamValidator")
173			<< "----> REJECT: overlap ratio"
174			<< std::endl;
175			}
176		✗	return false;
177			}
178
179		✗	if(Numeric::is_nan(comp_scaling) || comp_scaling > max_scaling_) {
180		✗	if(verbose_) {
181		✗	Logger::out("ParamValidator")
182			<< "----> REJECT: scaling "
183			<< std::endl;
184			}
185		✗	return false;
186			}
187
188		✗	if(verbose_) {
189		✗	Logger::out("ParamValidator")
190			<< "----> PASS." << std::endl;
191			}
192			return true;
193			}
194
195		✗	double ParamValidator::chart_scaling(
196			Mesh& chart
197			) {
198			Attribute<double> tex_coord;
199		✗	tex_coord.bind_if_is_defined(
200		✗	chart.vertices.attributes(), "tex_coord"
201			);
202		✗	geo_assert(tex_coord.is_bound() && tex_coord.dimension() == 2);
203
204			// Compute largest facet area.
205		✗	double max_area = 0;
206		✗	for(index_t f: chart.facets) {
207		✗	max_area = std::max(
208		✗	GEO::Geom::mesh_facet_area(chart,f), max_area
209			);
210			}
211
212			// Ignore facets smaller than 1% of the largest facet.
213		✗	double area_treshold = 0.001 * max_area;
214
215			std::vector<double> facet_scaling;
216		✗	facet_scaling.reserve(chart.facets.nb());
217
218		✗	for(index_t f: chart.facets) {
219		✗	double area = Geom::mesh_facet_area(chart,f);
220		✗	double area2d = chart_facet_area_2d(chart,f,tex_coord);
221		✗	if(area > area_treshold) {
222		✗	facet_scaling.push_back(area2d / area);
223			}
224			}
225
226			// Ignore 1% of the values at each end.
227		✗	std::sort(facet_scaling.begin(), facet_scaling.end());
228		✗	index_t offset = index_t(double(facet_scaling.size()) * 0.01);
229			index_t begin = offset;
230
231		✗	if(begin >= facet_scaling.size()) {
232			return 1.0;
233			}
234
235		✗	if(index_t(facet_scaling.size()) <= (1+offset)) {
236			return 1.0;
237			}
238
239		✗	index_t end = index_t(facet_scaling.size()) - 1 - offset;
240
241		✗	return facet_scaling[end] / facet_scaling[begin];
242			}
243
244		✗	void ParamValidator::compute_fill_and_overlap_ratio(Mesh& chart) {
245			Attribute<double> tex_coord;
246		✗	tex_coord.bind_if_is_defined(
247		✗	chart.vertices.attributes(), "tex_coord"
248			);
249		✗	geo_assert(tex_coord.is_bound() && tex_coord.dimension() == 2);
250		✗	begin_rasterizer(chart,tex_coord);
251		✗	for(index_t f : chart.facets) {
252			index_t c1 = chart.facets.corners_begin(f);
253			index_t v1 = chart.facet_corners.vertex(c1);
254		✗	vec2 p1(tex_coord[2*v1], tex_coord[2*v1+1]);
255		✗	for(
256		✗	index_t c2=c1+1; c2+1<chart.facets.corners_end(f); ++c2
257			) {
258			index_t c3=c2+1;
259			index_t v2 = chart.facet_corners.vertex(c2);
260			index_t v3 = chart.facet_corners.vertex(c3);
261		✗	vec2 p2(tex_coord[2*v2], tex_coord[2*v2+1]);
262		✗	vec2 p3(tex_coord[2*v3], tex_coord[2*v3+1]);
263		✗	rasterize_triangle(p1,p2,p3);
264			}
265			}
266		✗	end_rasterizer();
267		✗	}
268
269		✗	void ParamValidator::begin_rasterizer(Mesh& chart, Attribute<double>& tex_coord) {
270		✗	Memory::clear(graph_mem_, size_t(graph_size_ * graph_size_));
271			double xmin, ymin, xmax, ymax;
272		✗	get_chart_bbox_2d(chart, tex_coord, xmin, ymin, xmax, ymax);
273		✗	user_x_min_ = xmin;
274		✗	user_y_min_ = ymin;
275		✗	user_width_ = xmax - xmin;
276		✗	user_height_ = ymax - ymin;
277		✗	user_size_ = std::max(user_width_, user_height_);
278		✗	}
279
280
281		✗	void ParamValidator::transform(const vec2& p, int& x, int& y) {
282		✗	x = int( double(graph_size_-1) * (p.x - user_x_min_) / user_size_);
283		✗	y = int( double(graph_size_-1) * (p.y - user_y_min_) / user_size_);
284		✗	geo_clamp(x,0,int(graph_size_-1));
285		✗	geo_clamp(y,0,int(graph_size_-1));
286		✗	}
287
288		✗	void ParamValidator::rasterize_triangle(
289			const vec2& p1, const vec2& p2, const vec2& p3
290			) {
291			int x[3];
292			int y[3];
293
294		✗	transform(p1,x[0],y[0]);
295		✗	transform(p2,x[1],y[1]);
296		✗	transform(p3,x[2],y[2]);
297
298		✗	int ymin = 32767;
299		✗	int ymax = -1;
300
301		✗	for(int i=0; i<3; i++) {
302		✗	ymin = std::min(ymin, y[i]);
303		✗	ymax = std::max(ymax, y[i]);
304			}
305
306		✗	int signed_area =
307		✗	(x[1] - x[0]) * (y[2] - y[0]) -
308		✗	(x[2] - x[0]) * (y[1] - y[0]);
309		✗	bool ccw = (signed_area < 0);
310
311		✗	if(ymin == ymax) {
312		✗	return;
313			}
314
315		✗	for(int i=0; i<3; i++) {
316		✗	int j=(i+1)%3;
317		✗	int x1 = x[i];
318		✗	int y1 = y[i];
319		✗	int x2 = x[j];
320		✗	int y2 = y[j];
321		✗	if(y1 == y2) {
322		✗	continue;
323			}
324		✗	bool is_left = (y2 < y1) ^ ccw;
325
326			// I want the set of lit pixels to be
327			// independent from the order of the
328			// extremities.
329			bool swp = false;
330			if(y2 == y1) {
331			if(x1 > x2) {
332			swp = 1;
333			}
334			} else {
335		✗	if(y1 > y2) {
336			swp = 1;
337			}
338			}
339			if(swp) {
340			int tmp;
341			tmp = x2;
342			x2 = x1;
343			x1 = tmp;
344			tmp = y2;
345			y2 = y1;
346			y1 = tmp;
347			}
348
349			// Bresenham algo.
350		✗	int dx = x2 - x1;
351		✗	int dy = y2 - y1;
352		✗	int sx = dx > 0 ? 1 : -1;
353		✗	int sy = dy > 0 ? 1 : -1;
354		✗	dx *= sx;
355		✗	dy *= sy;
356			int X = x1;
357			int Y = y1;
358
359		✗	int* line_x = is_left ? x_left_ : x_right_;
360		✗	line_x[Y] = X;
361
362		✗	int e = dy - 2 * dx;
363		✗	while(Y < y2 - 1) {
364
365		✗	Y += sy;
366		✗	e -= 2 * dx;
367
368		✗	while(e < 0) {
369		✗	X += sx;
370		✗	e += 2 * dy;
371			}
372
373		✗	line_x[Y] = X;
374			}
375
376		✗	line_x[y2] = x2;
377			}
378
379		✗	for(int Y = ymin; Y < ymax; ++Y) {
380		✗	for(int X = x_left_[Y]; X < x_right_[Y]; ++X) {
381		✗	graph_mem_[Y * graph_size_ + X]++;
382			}
383			}
384			}
385
386		✗	void ParamValidator::end_rasterizer() {
387			int nb_filled = 0;
388			int nb_overlapped = 0;
389			int width = 0;
390			int height = 0;
391		✗	if(user_width_ > user_height_) {
392		✗	width = graph_size_;
393		✗	height = int((user_height_ * double(graph_size_)) / user_width_);
394			} else {
395		✗	height = graph_size_;
396		✗	width = int((user_width_ * double(graph_size_)) / user_height_);
397			}
398
399		✗	for(int x=0; x<width; x++) {
400		✗	for(int y=0; y<height; y++) {
401		✗	Numeric::uint8 pixel = graph_mem_[y * graph_size_ + x];
402		✗	if(pixel > 0) {
403		✗	nb_filled++;
404		✗	if(pixel > 1) {
405		✗	nb_overlapped++;
406			}
407			}
408			}
409			}
410
411		✗	fill_ratio_ = double(nb_filled) / double(width * height);
412		✗	overlap_ratio_ = double(nb_overlapped) / double(width * height);
413		✗	}
414			}
415