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_atlas_maker.h>
41			#include <geogram/parameterization/mesh_LSCM.h>
42			#include <geogram/parameterization/mesh_ABF.h>
43			#include <geogram/parameterization/mesh_segmentation.h>
44			#include <geogram/parameterization/mesh_param_validator.h>
45			#include <geogram/parameterization/mesh_param_packer.h>
46			#include <geogram/mesh/mesh.h>
47			#include <geogram/mesh/mesh_geometry.h>
48			#include <geogram/mesh/mesh_halfedges.h>
49			#include <geogram/mesh/mesh_topology.h>
50			#include <geogram/mesh/mesh_io.h>
51			#include <geogram/points/principal_axes.h>
52			#include <geogram/basic/progress.h>
53			#include <deque>
54			#include <stack>
55
56			namespace {
57			using namespace GEO;
58
59			/**
60			* \brief Computes a mesh parameterization by projection onto the
61			* least squares average plane.
62			* \param[in] M the chart to be parameterized.
63			*/
64		✗	void mesh_parameterize_by_projection(Mesh& M) {
65			vec3 N;
66			vec3 center;
67
68		✗	if(M.facets.nb() == 1) {
69			index_t f = 0;
70		✗	center = Geom::mesh_facet_center(M, f);
71		✗	N = Geom::mesh_facet_normal(M,f);
72			} else {
73		✗	PrincipalAxes3d LSN;
74		✗	LSN.begin();
75		✗	for(index_t f : M.facets) {
76		✗	for(index_t c: M.facets.corners(f)) {
77			index_t v = M.facet_corners.vertex(c);
78		✗	LSN.add_point(M.vertices.point(v));
79			}
80			}
81		✗	LSN.end();
82			center = LSN.center();
83		✗	N = LSN.normal();
84			}
85
86		✗	vec3 U = normalize(Geom::perpendicular(N));
87		✗	vec3 V = normalize(cross(N,U));
88
89			Attribute<double> tex_coord;
90		✗	tex_coord.bind_if_is_defined(M.vertices.attributes(), "tex_coord");
91			if(!tex_coord.is_bound()) {
92		✗	tex_coord.create_vector_attribute(
93		✗	M.vertices.attributes(), "tex_coord", 2
94			);
95			}
96		✗	geo_assert(tex_coord.dimension() == 2);
97		✗	for(index_t v: M.vertices) {
98			vec3 p = M.vertices.point(v) - center;
99			double pu = dot(p,U);
100			double pv = dot(p,V);
101		✗	tex_coord[2*v] = pu;
102		✗	tex_coord[2*v+1] = pv;
103			}
104		✗	}
105
106		✗	void measure_chart(
107			Mesh& chart,
108			signed_index_t& Xi,
109			index_t& nb_borders,
110			double& volume, double& surface_area, double& holes_area
111			) {
112			vec3 origin(0.0, 0.0, 0.0);
113
114		✗	volume = 0.0;
115		✗	surface_area = 0.0;
116		✗	holes_area = 0.0;
117		✗	nb_borders = 0;
118
119		✗	vector<bool> visited(chart.facet_corners.nb(), false);
120			MeshHalfedges MH(chart);
121			vector<vec3> P;
122		✗	for(index_t f: chart.facets) {
123		✗	for(index_t c: chart.facets.corners(f)) {
124			if(
125		✗	chart.facet_corners.adjacent_facet(c) == NO_INDEX &&
126			!visited[c]
127			) {
128		✗	++nb_borders;
129		✗	P.resize(0);
130			MeshHalfedges::Halfedge H(f,c);
131			do {
132		✗	visited[H.corner] = true;
133		✗	index_t v = chart.facet_corners.vertex(H.corner);
134			P.push_back(chart.vertices.point(v));
135		✗	MH.move_to_next_around_border(H);
136		✗	} while(!visited[H.corner]);
137		✗	vec3 G{0.0,0.0,0.0};
138		✗	for(vec3 p : P) {
139			G += p;
140			}
141		✗	G = (1.0/double(P.size())) * G;
142		✗	for(index_t i=0; i<P.size(); ++i) {
143		✗	index_t j = (i+1)%P.size();
144		✗	holes_area += Geom::triangle_area(P[j],P[i],G);
145		✗	volume += Geom::tetra_signed_volume(
146			origin, P[j], P[i], G
147			);
148			}
149			}
150			}
151			}
152		✗	for(index_t f: chart.facets) {
153		✗	geo_assert(chart.facets.nb_vertices(f) == 3);
154		✗	vec3 p1 = chart.facets.point(f,0);
155		✗	vec3 p2 = chart.facets.point(f,1);
156		✗	vec3 p3 = chart.facets.point(f,2);
157		✗	volume += dot(p1,cross(p2,p3)) / 6.0;
158		✗	surface_area += Geom::triangle_area(p1,p2,p3);
159			}
160
161		✗	volume = ::fabs(volume);
162		✗	Xi = mesh_Xi(chart);
163		✗	}
164
165			enum ChartType {
166			CHART_TYPE_MONSTROID = 0,
167			CHART_TYPE_DISKOID = 1,
168			CHART_TYPE_CYLINDROID = 2,
169			CHART_TYPE_SOCKOID = 3
170			};
171
172			// Uncomment to save first segments with a name
173			// that indicates how it was classified
174			// #define DEBUG_CHART_CLASSIFICATION
175
176			#ifdef DEBUG_CHART_CLASSIFICATION
177			const char* chart_type_as_string(ChartType c) {
178			static const char* names[] = {
179			"monstroid",
180			"diskoid",
181			"cylindroid",
182			"sockoid"
183			};
184			return names[c];
185			}
186			#endif
187
188		✗	ChartType chart_type(Mesh& chart) {
189			signed_index_t Xi;
190			index_t nb_borders;
191			double volume;
192			double surface_area;
193			double holes_area;
194
195		✗	measure_chart(chart, Xi, nb_borders, volume, surface_area, holes_area);
196
197		✗	double hs_ratio = holes_area / surface_area;
198
199		✗	if(nb_borders == 1 && Xi == 1) {
200		✗	return (hs_ratio < 1.0/2.0) ?
201			CHART_TYPE_SOCKOID :
202		✗	CHART_TYPE_DISKOID ;
203			}
204
205		✗	if(nb_borders == 2 && Xi == 0 && hs_ratio < 1.0
206			) {
207			return (hs_ratio < 1.0) ?
208			CHART_TYPE_CYLINDROID :
209		✗	CHART_TYPE_DISKOID;
210			}
211
212			return CHART_TYPE_MONSTROID;
213			}
214
215			/**
216			* \brief Computes a texture atlas.
217			*/
218			class AtlasMaker {
219			public:
220
221		✗	AtlasMaker(Mesh& mesh) :
222		✗	mesh_(mesh),
223		✗	hard_angles_threshold_(0.0) {
224		✗	tex_coord_.bind_if_is_defined(
225		✗	mesh_.facet_corners.attributes(), "tex_coord"
226			);
227			if(!tex_coord_.is_bound()) {
228		✗	tex_coord_.create_vector_attribute(
229		✗	mesh_.facet_corners.attributes(), "tex_coord", 2
230			);
231			}
232		✗	geo_assert(tex_coord_.dimension() == 2);
233		✗	chart_parameterizer_ = PARAM_ABF;
234		✗	verbose_ = false;
235			#ifdef GEO_OS_ANDROID
236			max_chart_size_ = 3000;
237			#else
238		✗	max_chart_size_ = 30000;
239			#endif
240		✗	}
241
242		✗	~AtlasMaker() {
243		✗	}
244
245			void set_verbose(bool x) {
246		✗	verbose_ = x;
247			validator_.set_verbose(x);
248			}
249
250			void set_hard_angles_threshold(double x) {
251		✗	hard_angles_threshold_ = x;
252			}
253
254			void set_chart_parameterizer(ChartParameterizer param) {
255		✗	chart_parameterizer_ = param;
256			}
257
258		✗	void make_atlas() {
259
260		✗	ProgressTask progress("Atlas",100);
261		✗	progress.progress(0);
262
263			// Total number of facets in triangulated mesh
264			index_t total_f = 0;
265		✗	for(index_t f: mesh_.facets) {
266		✗	total_f += (mesh_.facets.nb_vertices(f)-2);
267			}
268
269			// Current number of parameterized facets
270			index_t param_f = 0;
271
272			std::stack<Mesh*> S;
273
274			{
275		✗	get_initial_segmentation();
276			vector<Mesh*> charts;
277		✗	get_charts(mesh_, charts);
278
279		✗	for(index_t i=0; i<charts.size(); ++i) {
280			#ifdef DEBUG_CHART_CLASSIFICATION
281			mesh_save(
282			*(charts[i]),
283			"chart_" + String::to_string(i) + "_" +
284			chart_type_as_string(chart_type(*charts[i])) +
285			".geogram"
286			);
287			#endif
288			S.push(charts[i]);
289			}
290			}
291
292			try {
293		✗	while(!S.empty()) {
294		✗	Mesh* M = S.top();
295			S.pop();
296
297		✗	if(verbose_) {
298		✗	Logger::out("MAM") << "Processing chart, size="
299			<< M->facets.nb() << std::endl;
300			}
301
302			if(
303		✗	precheck_chart(*M) &&
304		✗	parameterize_chart(*M) &&
305		✗	postcheck_chart(*M)
306			) {
307
308		✗	if(verbose_) {
309		✗	Logger::out("MAM") << "=== CHART OK" << std::endl;
310			}
311
312		✗	commit_chart(*M);
313		✗	param_f += M->facets.nb();
314		✗	progress.progress(param_f * 100 / total_f);
315
316			} else {
317
318		✗	if(verbose_) {
319		✗	Logger::out("MAM")
320			<< "=== CHART NOT OK (splitting)" << std::endl;
321			}
322
323			index_t nb_segments =
324		✗	M->facets.nb() / max_chart_size_ + 1;
325
326			MeshSegmenter segmenter = SEGMENT_GEOMETRIC_VSA_L2;
327
328
329		✗	ChartType type = chart_type(*M);
330		✗	switch(type) {
331		✗	case CHART_TYPE_MONSTROID:
332		✗	nb_segments = std::max(nb_segments, index_t(7));
333		✗	break;
334		✗	case CHART_TYPE_DISKOID:
335		✗	nb_segments = std::max(nb_segments, index_t(4));
336		✗	break;
337		✗	case CHART_TYPE_SOCKOID:
338		✗	nb_segments = 2;
339			segmenter = SEGMENT_INERTIA_AXIS;
340		✗	break;
341		✗	case CHART_TYPE_CYLINDROID:
342		✗	nb_segments = 2;
343			segmenter = SEGMENT_INERTIA_AXIS;
344		✗	break;
345			}
346
347			nb_segments = std::max(nb_segments, index_t(6));
348		✗	geo_assert(M->facets.nb() > 1);
349			if(
350		✗	M->facets.nb() <= nb_segments ||
351		✗	mesh_segment(*M, segmenter, nb_segments) < 2
352			) {
353			Attribute<index_t> chart(
354		✗	M->facets.attributes(),"chart"
355			);
356		✗	for(index_t f: M->facets) {
357		✗	chart[f] = f;
358			}
359			}
360			vector<Mesh*> charts;
361		✗	get_charts(*M, charts);
362		✗	for(Mesh* C: charts) {
363			S.push(C);
364			}
365			}
366		✗	delete M;
367			}
368		✗	} catch(...) {
369		✗	Logger::out("Atlas") << "Job canceled" << std::endl;
370		✗	}
371		✗	}
372
373			protected:
374
375			/*
376			* \brief Segments mesh along sharp creases and optional
377			* initial segmentation in the "chart" facet attribute.
378			* \details Sharp creases are edges for which the dihedral
379			* angle is larger than hard_angles_threshold_ or that are
380			* adjacent to two facets with different "chart" attribute
381			* (if specified).
382			*/
383
384		✗	void get_initial_segmentation() {
385			Attribute<index_t> initial_chart;
386		✗	if(Attribute<index_t>::is_defined(
387		✗	mesh_.facets.attributes(), "chart"
388			)) {
389		✗	initial_chart.bind(
390		✗	mesh_.facets.attributes(), "initial_chart"
391			);
392			}
393		✗	Attribute<index_t> chart(mesh_.facets.attributes(), "chart");
394		✗	for(index_t f: mesh_.facets) {
395			if(initial_chart.is_bound()) {
396		✗	initial_chart[f] = chart[f];
397			}
398		✗	chart[f] = NO_INDEX;
399			}
400
401			index_t cur_chart = 0;
402		✗	for(index_t f: mesh_.facets) {
403			std::stack<index_t> S;
404		✗	if(chart[f] == NO_INDEX) {
405		✗	chart[f] = cur_chart;
406			S.push(f);
407			do {
408		✗	index_t cur_f = S.top();
409			S.pop();
410		✗	for(index_t c: mesh_.facets.corners(cur_f)) {
411		✗	index_t f2=mesh_.facet_corners.adjacent_facet(c);
412
413		✗	if(f2 == NO_FACET) {
414		✗	continue;
415			}
416
417			bool is_on_chart_border = (
418		✗	Geom::mesh_unsigned_normal_angle(
419		✗	mesh_,cur_f,f2) > hard_angles_threshold_
420		✗	);
421			if(initial_chart.is_bound()) {
422		✗	is_on_chart_border = is_on_chart_border ||
423		✗	(initial_chart[cur_f] !=
424			initial_chart[f2]);
425			}
426		✗	if(chart[f2] != cur_chart && !is_on_chart_border) {
427		✗	chart[f2] = cur_chart;
428			S.push(f2);
429			}
430			}
431		✗	} while(!S.empty());
432		✗	++cur_chart;
433			}
434			}
435
436		✗	if(cur_chart == 1 && mesh_.facets.nb() > max_chart_size_) {
437		✗	index_t nb_charts = mesh_.facets.nb() / max_chart_size_ + 1;
438			nb_charts = std::max(nb_charts, index_t(4));
439		✗	mesh_segment(mesh_, SEGMENT_GEOMETRIC_VSA_L2, nb_charts);
440			}
441		✗	}
442
443			/**
444			* \brief Extracts one mesh per chart in input mesh
445			* \details Charts are determined from the "chart" facet attribute
446			* \param[in] M the mesh
447			* \param[in,out] charts the extracted charts. Caller
448			* has the responsibility of deallocating each individual
449			* mesh.
450			*/
451		✗	void get_charts(Mesh& M, vector<Mesh*>& charts) {
452		✗	Attribute<index_t> chart(M.facets.attributes(), "chart");
453		✗	Attribute<index_t> vertex_id(M.vertices.attributes(), "id");
454
455			// If M is a chart that was obtained by a previous call to
456			// get_charts(), M_corner is already bound (else it is unbound):
457			// For each facet corner of M, keeps the facet corner id in mesh_
458			// (will be used to transfer texture coordinates after chart
459			// parameterization).
460			Attribute<index_t> M_corner;
461		✗	M_corner.bind_if_is_defined(
462		✗	M.facet_corners.attributes(),"corner_id"
463			);
464
465			vector<index_t> facets;
466		✗	vector<bool> f_is_visited(M.facets.nb(),false);
467			std::stack<index_t> S;
468
469		✗	for(index_t f0: M.facets) {
470		✗	if(!f_is_visited[f0]) {
471
472		✗	charts.push_back(new Mesh);
473		✗	Mesh& C = *(charts[charts.size()-1]);
474		✗	C.vertices.set_dimension(3);
475			// For each facet corner of C, keeps the facet
476			// corner id in M (will be used to transfer texture
477			// coordinates after chart parameterization).
478			Attribute<index_t> C_corner(
479		✗	C.facet_corners.attributes(), "corner_id"
480			);
481
482			// Step 1: get chart facets
483		✗	facets.resize(0);
484			facets.push_back(f0);
485			f_is_visited[f0] = true;
486			S.push(f0);
487
488		✗	while(!S.empty()) {
489		✗	index_t f = S.top();
490			S.pop();
491		✗	for(index_t e=0; e<M.facets.nb_vertices(f); ++e) {
492		✗	index_t g = M.facets.adjacent(f,e);
493			if(
494		✗	g != NO_INDEX && !f_is_visited[g] &&
495		✗	chart[g] == chart[f0]
496			) {
497			facets.push_back(g);
498			f_is_visited[g] = true;
499			S.push(g);
500			}
501			}
502			}
503
504			// step 2: reset vertex ids
505		✗	for(index_t f: facets) {
506		✗	for(index_t c: M.facets.corners(f)) {
507			index_t v = M.facet_corners.vertex(c);
508		✗	vertex_id[v] = NO_INDEX;
509			}
510			}
511
512			// step 3: copy vertices
513			index_t nb_vertices = 0;
514		✗	for(index_t f: facets) {
515		✗	for(index_t c: M.facets.corners(f)) {
516			index_t v = M.facet_corners.vertex(c);
517		✗	if(vertex_id[v] == NO_INDEX) {
518			C.vertices.create_vertex(
519			M.vertices.point(v)
520			);
521		✗	vertex_id[v] = nb_vertices; // M to C
522		✗	++nb_vertices;
523			}
524			}
525			}
526
527			// step 4: copy (and triangulate) facets
528		✗	for(index_t f: facets) {
529			index_t c1 = M.facets.corners_begin(f);
530		✗	index_t v1 = vertex_id[M.facet_corners.vertex(c1)];
531		✗	for(
532		✗	index_t c2 = c1+1;
533		✗	c2+1 < M.facets.corners_end(f); ++c2
534			) {
535			index_t c3=c2+1;
536		✗	index_t v2=vertex_id[M.facet_corners.vertex(c2)];
537		✗	index_t v3=vertex_id[M.facet_corners.vertex(c3)];
538		✗	geo_assert(v1 < nb_vertices);
539		✗	geo_assert(v2 < nb_vertices);
540		✗	geo_assert(v3 < nb_vertices);
541		✗	index_t t = C.facets.create_triangle(v1,v2,v3);
542		✗	if(&M == &mesh_) {
543		✗	C_corner[C.facets.corner(t,0)] = c1;
544		✗	C_corner[C.facets.corner(t,1)] = c2;
545		✗	C_corner[C.facets.corner(t,2)] = c3;
546			} else {
547		✗	C_corner[C.facets.corner(t,0)] = M_corner[c1];
548		✗	C_corner[C.facets.corner(t,1)] = M_corner[c2];
549		✗	C_corner[C.facets.corner(t,2)] = M_corner[c3];
550			}
551			}
552			}
553		✗	C.facets.connect();
554			}
555			}
556		✗	}
557
558			/**
559			* \brief Tests done on chart before parameterization
560			* \details A chart cannot be parameterized if it has no
561			* border. It will not be parameterized if it has too
562			* many facets
563			* \param[in] chart the chart to be tested
564			* \retval true if the chart is going to be parameterized
565			* \retval false otherwise
566			*/
567		✗	bool precheck_chart(const Mesh& chart) {
568			bool has_borders = false;
569		✗	for(index_t c: chart.facet_corners) {
570		✗	if(chart.facet_corners.adjacent_facet(c) == NO_INDEX) {
571			has_borders = true;
572			break;
573			}
574			}
575		✗	if(!has_borders) {
576		✗	if(verbose_) {
577		✗	Logger::out("MAM") << "precheck !OK (chart has no border)"
578			<< std::endl;
579			}
580		✗	return false;
581			}
582		✗	if(chart.facets.nb() > max_chart_size_) {
583		✗	if(verbose_) {
584		✗	Logger::out("MAM") << "precheck !OK (chart too large)"
585			<< std::endl;
586			}
587		✗	return false;
588			}
589		✗	if(verbose_) {
590		✗	Logger::out("MAM") << "precheck OK" << std::endl;
591			}
592			return true;
593			}
594
595			/**
596			* \brief Compute U,V coordinates in chart
597			* \details U,V coordinates are stored in the "tex_coord" vertex
598			* attribute
599			* \param[in,out] chart the chart to be parameterized
600			*/
601		✗	bool parameterize_chart(Mesh& chart) {
602		✗	if(chart.facets.nb() == 1) {
603		✗	mesh_parameterize_by_projection(chart);
604		✗	return true;
605			}
606		✗	switch(chart_parameterizer_) {
607		✗	case PARAM_PROJECTION:
608		✗	mesh_parameterize_by_projection(chart);
609		✗	break;
610		✗	case PARAM_LSCM:
611		✗	mesh_compute_LSCM(chart, "tex_coord", false, "", verbose_);
612		✗	break;
613		✗	case PARAM_SPECTRAL_LSCM:
614		✗	mesh_compute_LSCM(chart, "tex_coord", true, "", verbose_);
615		✗	break;
616		✗	case PARAM_ABF:
617		✗	mesh_compute_ABF_plus_plus(chart, "tex_coord", verbose_);
618		✗	break;
619			}
620			return true;
621			}
622
623		✗	bool postcheck_chart(Mesh& chart) {
624		✗	bool OK = validator_.chart_is_valid(chart);
625
626			// If a small chart has a problem, then try
627			// simply to project it.
628		✗	if(!OK && chart.facets.nb() <= 10) {
629		✗	mesh_parameterize_by_projection(chart);
630			// Some single-facet charts may fail to be validated if
631			// they are too skinny (filling ratio will be too bad),
632			// so we force accept if there is a single facet.
633		✗	OK = (chart.facets.nb() == 1) ||
634		✗	validator_.chart_is_valid(chart);
635			}
636		✗	return OK;
637			}
638
639			/**
640			* \brief Copies texture coordinates of a chart to the main mesh.
641			* \details Texture coordinates are taken from the "tex_coord" vertex
642			* attribute of \p chart and written into the "tex_coord" facet corner
643			* attribute of mesh_, using the "corner_id" vertex attribute of
644			* \p chart that points towards the facet corners in mesh_.
645			*/
646		✗	void commit_chart(Mesh& chart) {
647			Attribute<index_t> C_corner(
648		✗	chart.facet_corners.attributes(),"corner_id"
649			);
650			Attribute<double> C_tex_coord(
651		✗	chart.vertices.attributes(),"tex_coord"
652			);
653			Attribute<double> M_tex_coord(
654		✗	mesh_.facet_corners.attributes(), "tex_coord"
655			);
656		✗	for(index_t c: chart.facet_corners) {
657			index_t v = chart.facet_corners.vertex(c);
658		✗	index_t mesh_c = C_corner[c];
659		✗	M_tex_coord[2*mesh_c ] = C_tex_coord[2*v ];
660		✗	M_tex_coord[2*mesh_c+1] = C_tex_coord[2*v+1];
661			}
662		✗	}
663
664			private:
665			Mesh& mesh_;
666			ChartParameterizer chart_parameterizer_;
667			ParamValidator validator_;
668			double hard_angles_threshold_; // in radians
669			Attribute<double> tex_coord_;
670			index_t max_chart_size_;
671			Mesh chart_as_mesh_;
672			bool verbose_;
673			};
674
675			/**
676			* \brief Tests whether two facets are on the same chart
677			* \details Two facets are on the same chart if their texture
678			* coordinates match along the edge they are adjacent to
679			* \param[in] mesh a reference to the mesh
680			* \param[in] f1 a facet of the mesh
681			* \param[in] e1 an edge of \p f1
682			* \param[in] tex_coord a reference to the facet corners tex coords
683			*/
684		✗	bool is_same_chart(
685			const Mesh& mesh,
686			index_t f1, index_t e1, const Attribute<double>& tex_coord
687			) {
688		✗	index_t c11 = mesh.facets.corners_begin(f1)+e1;
689			index_t c12 = mesh.facets.next_corner_around_facet(f1,c11);
690			index_t f2 = mesh.facets.adjacent(f1,e1);
691		✗	geo_assert(f2 != NO_INDEX);
692		✗	index_t e2 = mesh.facets.find_adjacent(f2,f1);
693		✗	geo_assert(e2 != NO_INDEX);
694		✗	index_t c21 = mesh.facets.corners_begin(f2)+e2;
695			index_t c22 = mesh.facets.next_corner_around_facet(f2,c21);
696
697			return
698		✗	(tex_coord[2*c11 ] == tex_coord[2*c22 ]) &&
699		✗	(tex_coord[2*c11+1] == tex_coord[2*c22+1]) &&
700		✗	(tex_coord[2*c12 ] == tex_coord[2*c21 ]) &&
701		✗	(tex_coord[2*c12+1] == tex_coord[2*c21+1]) ;
702
703			}
704
705			}
706
707			namespace GEO {
708
709		✗	void mesh_make_atlas(
710			Mesh& mesh, double hard_angles_threshold, // in degrees
711			ChartParameterizer param,
712			ChartPacker pack,
713			bool verbose
714			) {
715		✗	AtlasMaker atlas(mesh);
716		✗	atlas.set_hard_angles_threshold(
717		✗	hard_angles_threshold * M_PI / 180.0
718			);
719			atlas.set_chart_parameterizer(param);
720			atlas.set_verbose(verbose);
721		✗	atlas.make_atlas();
722		✗	mesh_get_charts(mesh);
723		✗	switch(pack) {
724			case PACK_NONE:
725			break;
726		✗	case PACK_TETRIS:
727		✗	pack_atlas_using_tetris_packer(mesh);
728			break;
729		✗	case PACK_XATLAS:
730		✗	pack_atlas_only_normalize_charts(mesh);
731		✗	pack_atlas_using_xatlas(mesh);
732			break;
733			}
734		✗	}
735
736		✗	index_t mesh_get_charts(Mesh& mesh) {
737		✗	Attribute<index_t> chart(mesh.facets.attributes(),"chart");
738			Attribute<double> tex_coord;
739		✗	tex_coord.bind_if_is_defined(
740		✗	mesh.facet_corners.attributes(), "tex_coord"
741			);
742			if(!tex_coord.is_bound()) {
743		✗	Logger::err("Chart") << "mesh does not have facet corner tex coords"
744			<< std::endl;
745		✗	return 0;
746			}
747		✗	if(tex_coord.dimension() != 2) {
748		✗	Logger::err("Chart") << "facet corner tex coords not of dimension 2"
749			<< std::endl;
750		✗	return 0;
751			}
752			chart.fill(NO_INDEX);
753			std::stack<index_t> S;
754			index_t current_chart = 0;
755		✗	for(index_t f : mesh.facets) {
756		✗	if(chart[f] == NO_INDEX) {
757		✗	chart[f] = current_chart;
758			S.push(f);
759		✗	while(!S.empty()) {
760		✗	index_t f1 = S.top();
761			S.pop();
762		✗	for(index_t e=0; e<mesh.facets.nb_vertices(f1); ++e) {
763		✗	index_t f2 = mesh.facets.adjacent(f1,e);
764			if(
765		✗	f2 != NO_INDEX &&
766		✗	chart[f2] == NO_INDEX &&
767		✗	is_same_chart(mesh,f1,e,tex_coord)
768			) {
769		✗	chart[f2] = current_chart;
770			S.push(f2);
771			}
772			}
773			}
774		✗	current_chart++;
775			}
776			}
777			return current_chart;
778			}
779
780			}
781