1 // Copyright (c) 2016 GeometryFactory (France).
2 // All rights reserved.
3 //
4 // This file is part of CGAL (www.cgal.org).
5 //
6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Surface_mesh_parameterization/include/CGAL/Surface_mesh_parameterization/internal/validity.h $
7 // $Id: validity.h bdd4efe 2021-01-15T10:06:56+01:00 Sébastien Loriot
8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 // Author(s) : Mael Rouxel-Labbé
11
12 #ifndef CGAL_SURFACE_MESH_PARAMETERIZATION_INTERNAL_VALIDITY_H
13 #define CGAL_SURFACE_MESH_PARAMETERIZATION_INTERNAL_VALIDITY_H
14
15 #include <CGAL/license/Surface_mesh_parameterization.h>
16
17 #include <CGAL/Surface_mesh_parameterization/internal/Containers_filler.h>
18 #include <CGAL/Surface_mesh_parameterization/internal/kernel_traits.h>
19
20 #include <CGAL/Bbox_2.h>
21 #include <CGAL/box_intersection_d.h>
22
23 #include <CGAL/boost/graph/properties.h>
24 #include <CGAL/Kernel/global_functions.h>
25 #include <CGAL/intersections.h>
26 #include <CGAL/Polygon_mesh_processing/connected_components.h>
27
28 #include <boost/iterator/function_output_iterator.hpp>
29
30 #include <vector>
31
32 namespace CGAL {
33
34 namespace Surface_mesh_parameterization {
35
36 namespace internal {
37
38 template<typename TriangleMesh, typename VertexUVMap>
has_flips(const TriangleMesh & mesh,typename boost::graph_traits<TriangleMesh>::halfedge_descriptor bhd,const VertexUVMap uvmap)39 bool has_flips(const TriangleMesh& mesh,
40 typename boost::graph_traits<TriangleMesh>::halfedge_descriptor bhd,
41 const VertexUVMap uvmap)
42 {
43 typedef typename boost::graph_traits<TriangleMesh>::vertex_descriptor vertex_descriptor;
44 typedef typename boost::graph_traits<TriangleMesh>::halfedge_descriptor halfedge_descriptor;
45 typedef typename boost::graph_traits<TriangleMesh>::face_descriptor face_descriptor;
46
47 // Kernel subtypes:
48 typedef typename internal::Kernel_traits<TriangleMesh>::Kernel Kernel;
49 typedef typename Kernel::Point_2 Point_2;
50 typedef typename Kernel::Point_3 Point_3;
51 typedef typename Kernel::Vector_3 Vector_3;
52
53 // Fill containers
54 boost::unordered_set<vertex_descriptor> vertices;
55 std::vector<face_descriptor> faces;
56
57 internal::Containers_filler<TriangleMesh> fc(mesh, vertices, &faces);
58 Polygon_mesh_processing::connected_component(
59 face(opposite(bhd, mesh), mesh),
60 mesh,
61 boost::make_function_output_iterator(fc));
62
63 Vector_3 first_triangle_normal(0., 0., 0.);
64 bool is_normal_set = false;
65
66 for(face_descriptor fd : faces) {
67 // Get 3 vertices of the facet
68 halfedge_descriptor hd = halfedge(fd, mesh);
69 vertex_descriptor vd0 = target(hd, mesh);
70 vertex_descriptor vd1 = target(next(hd, mesh), mesh);
71 vertex_descriptor vd2 = source(hd, mesh);
72
73 // Get the 3 vertices position in 2D
74 const Point_2& p0 = get(uvmap, vd0);
75 const Point_2& p1 = get(uvmap, vd1);
76 const Point_2& p2 = get(uvmap, vd2);
77
78 // Compute the facet normal
79 Point_3 p0_3D(p0.x(), p0.y(), 0.);
80 Point_3 p1_3D(p1.x(), p1.y(), 0.);
81 Point_3 p2_3D(p2.x(), p2.y(), 0.);
82 Vector_3 v01_3D = p1_3D - p0_3D;
83 Vector_3 v02_3D = p2_3D - p0_3D;
84 Vector_3 normal = CGAL::cross_product(v01_3D, v02_3D);
85
86 // Check that all normals are oriented the same way
87 if (!is_normal_set) {
88 first_triangle_normal = normal;
89 is_normal_set = true;
90 } else {
91 if (first_triangle_normal * normal < 0)
92 return true;
93 }
94 }
95 return false;
96 }
97
98 template <typename TriangleMesh, typename VertexUVMap>
99 class Intersect_facets
100 {
101 typedef typename boost::graph_traits<TriangleMesh>::vertex_descriptor vertex_descriptor;
102 typedef typename boost::graph_traits<TriangleMesh>::halfedge_descriptor halfedge_descriptor;
103 typedef typename boost::graph_traits<TriangleMesh>::face_descriptor face_descriptor;
104
105 // Kernel subtypes:
106 typedef typename internal::Kernel_traits<TriangleMesh>::Kernel Kernel;
107 typedef typename Kernel::Point_2 Point_2;
108 typedef typename Kernel::Segment_2 Segment_2;
109 typedef typename Kernel::Triangle_2 Triangle_2;
110 typedef typename Kernel::FT NT;
111
112 typename Kernel::Construct_segment_2 segment_functor;
113 typename Kernel::Construct_triangle_2 triangle_functor;
114 typename Kernel::Do_intersect_2 do_intersect_2_functor;
115
116 typedef CGAL::Box_intersection_d::ID_FROM_BOX_ADDRESS Box_policy;
117 typedef CGAL::Box_intersection_d::Box_with_info_d<NT, 2, face_descriptor, Box_policy> Box;
118
119 const TriangleMesh& mesh;
120 const VertexUVMap uvmap;
121 unsigned int& self_intersection_counter;
122
123 public:
number_of_self_intersections()124 unsigned int number_of_self_intersections() const { return self_intersection_counter; }
125
126 // callback functor that reports all truly intersecting triangles
operator()127 void operator()(const Box* a, const Box* b) const
128 {
129 // Boxes intersect, need to check if there is actually an intersection
130 // and if it is not a subface of the faces
131 halfedge_descriptor h = halfedge(a->info(), mesh);
132 halfedge_descriptor g = halfedge(b->info(), mesh);
133
134 // check for shared egde
135 if(face(opposite(h, mesh), mesh) == b->info() ||
136 face(opposite(prev(h, mesh), mesh), mesh) == b->info() ||
137 face(opposite(next(h, mesh), mesh), mesh) == b->info()) {
138 // shared edge
139
140 // intersection if the orientations are not identical
141 if(CGAL::orientation(get(uvmap, target(h, mesh)),
142 get(uvmap, target(next(h, mesh), mesh)),
143 get(uvmap, source(h, mesh))) !=
144 CGAL::orientation(get(uvmap, target(g, mesh)),
145 get(uvmap, target(next(g, mesh), mesh)),
146 get(uvmap, source(g, mesh)))) {
147 ++self_intersection_counter;
148 }
149 return;
150 }
151
152 // check for shared vertex --> possible intersection
153 halfedge_descriptor hd;
154
155 if(target(h, mesh) == target(g, mesh))
156 hd = g;
157 if(target(h, mesh) == target(next(g, mesh), mesh))
158 hd = next(g, mesh);
159 if(target(h, mesh) == target(next(next(g, mesh), mesh), mesh))
160 hd = next(next(g, mesh), mesh);
161
162 if(target(h, mesh) == target(g, mesh))
163 hd = g;
164 if(target(h, mesh) == target(next(g, mesh), mesh))
165 hd = next(g, mesh);
166 if(target(h, mesh) == target(next(next(g, mesh), mesh), mesh))
167 hd = next(next(g, mesh), mesh);
168
169 if(hd == halfedge_descriptor()) {
170 h = next(h, mesh);
171 if(target(h, mesh) == target(g, mesh))
172 hd = g;
173 if(target(h, mesh) == target(next(g, mesh), mesh))
174 hd = next(g, mesh);
175 if(target(h, mesh) == target(next(next(g, mesh), mesh), mesh))
176 hd = next(next(g, mesh), mesh);
177 if(hd == halfedge_descriptor()) {
178 h = next(h, mesh);
179 if(target(h, mesh) == target(g, mesh))
180 hd = g;
181 if(target(h, mesh) == target(next(g, mesh), mesh))
182 hd = next(g, mesh);
183 if(target(h, mesh) == target(next(next(g, mesh), mesh), mesh))
184 hd = next(next(g, mesh), mesh);
185 }
186 }
187
188 if(hd != halfedge_descriptor()) {
189 // shared vertex
190 CGAL_assertion(target(h, mesh) == target(hd, mesh));
191
192 // geometric check if the opposite segments intersect the triangles
193 Triangle_2 t1 = triangle_functor(get(uvmap, target(h, mesh)),
194 get(uvmap, target(next(h, mesh), mesh)),
195 get(uvmap, target(next(next(h, mesh), mesh), mesh)));
196 Triangle_2 t2 = triangle_functor(get(uvmap, target(hd, mesh)),
197 get(uvmap, target(next(hd, mesh), mesh)),
198 get(uvmap, target(next(next(hd, mesh), mesh), mesh)));
199
200 Segment_2 s1 = segment_functor(get(uvmap, target(next(h, mesh), mesh)),
201 get(uvmap, target(next(next(h, mesh), mesh), mesh)));
202 Segment_2 s2 = segment_functor(get(uvmap, target(next(hd, mesh), mesh)),
203 get(uvmap, target(next(next(hd, mesh), mesh), mesh)));
204
205 if(do_intersect_2_functor(t1, s2)) {
206 ++self_intersection_counter;
207 } else if(do_intersect_2_functor(t2, s1)) {
208 ++self_intersection_counter;
209 }
210 return;
211 }
212
213 // check for geometric intersection
214 Triangle_2 t1 = triangle_functor(get(uvmap, target(h, mesh)),
215 get(uvmap, target(next(h, mesh), mesh)),
216 get(uvmap, target(next(next(h, mesh), mesh), mesh)));
217 Triangle_2 t2 = triangle_functor(get(uvmap, target(g, mesh)),
218 get(uvmap, target(next(g, mesh), mesh)),
219 get(uvmap, target(next(next(g, mesh), mesh), mesh)));
220 if(do_intersect_2_functor(t1, t2)) {
221 ++self_intersection_counter;
222 }
223 }
224
Intersect_facets(const TriangleMesh & mesh_,const VertexUVMap uvmap_,unsigned int & counter)225 Intersect_facets(const TriangleMesh& mesh_,
226 const VertexUVMap uvmap_,
227 unsigned int& counter)
228 :
229 mesh(mesh_),
230 uvmap(uvmap_),
231 self_intersection_counter(counter)
232 { }
233 };
234
235 /// returns whether the 3D -> 2D mapping is one-to-one.
236 /// This function is stronger than "has_flips()" because the parameterized
237 /// surface can loop over itself without creating any flips.
238 template <typename TriangleMesh,
239 typename Faces_Container,
240 typename VertexUVMap>
is_one_to_one_mapping(const TriangleMesh & mesh,const Faces_Container & faces,const VertexUVMap uvmap)241 bool is_one_to_one_mapping(const TriangleMesh& mesh,
242 const Faces_Container& faces,
243 const VertexUVMap uvmap)
244 {
245 typedef typename boost::graph_traits<TriangleMesh>::vertex_descriptor vertex_descriptor;
246 typedef typename boost::graph_traits<TriangleMesh>::halfedge_descriptor halfedge_descriptor;
247 typedef typename boost::graph_traits<TriangleMesh>::face_descriptor face_descriptor;
248
249 // Kernel subtypes:
250 typedef typename internal::Kernel_traits<TriangleMesh>::Kernel Kernel;
251 typedef typename Kernel::FT NT;
252 typedef typename Kernel::Point_2 Point_2;
253
254 typedef CGAL::Box_intersection_d::ID_FROM_BOX_ADDRESS Box_policy;
255 typedef CGAL::Box_intersection_d::Box_with_info_d<NT, 2, face_descriptor, Box_policy> Box;
256
257 // Create the corresponding vector of bounding boxes
258 std::vector<Box> boxes;
259
260 for(face_descriptor fd : faces) {
261 halfedge_descriptor hd = halfedge(fd, mesh);
262 vertex_descriptor vd0 = target(hd, mesh);
263 vertex_descriptor vd1 = target(next(hd, mesh), mesh);
264 vertex_descriptor vd2 = source(hd, mesh);
265
266 // Get the 3 vertices position in 2D
267 const Point_2& p0 = get(uvmap, vd0);
268 const Point_2& p1 = get(uvmap, vd1);
269 const Point_2& p2 = get(uvmap, vd2);
270
271 Bbox_2 b = p0.bbox();
272 b += p1.bbox();
273 b += p2.bbox();
274
275 boxes.push_back(Box(b, fd));
276 }
277
278 std::vector<const Box*> boxes_ptr;
279 boxes_ptr.reserve(boxes.size());
280
281 for(Box& b : boxes)
282 boxes_ptr.push_back(&b);
283
284 // Run the self intersection algorithm with all defaults
285 unsigned int counter = 0;
286 Intersect_facets<TriangleMesh, VertexUVMap> intersect_facets(mesh, uvmap, counter);
287 std::ptrdiff_t cutoff = 2000;
288 CGAL::box_self_intersection_d(boxes_ptr.begin(), boxes_ptr.end(), intersect_facets, cutoff);
289 return (counter == 0);
290 }
291
292 template <typename TriangleMesh,
293 typename VertexUVMap>
is_one_to_one_mapping(const TriangleMesh & mesh,typename boost::graph_traits<TriangleMesh>::halfedge_descriptor bhd,const VertexUVMap uvmap)294 bool is_one_to_one_mapping(const TriangleMesh& mesh,
295 typename boost::graph_traits<TriangleMesh>::halfedge_descriptor bhd,
296 const VertexUVMap uvmap)
297 {
298 typedef typename boost::graph_traits<TriangleMesh>::vertex_descriptor vertex_descriptor;
299 typedef typename boost::graph_traits<TriangleMesh>::face_descriptor face_descriptor;
300
301 boost::unordered_set<vertex_descriptor> vertices;
302 std::vector<face_descriptor> faces;
303
304 internal::Containers_filler<TriangleMesh> fc(mesh, vertices, &faces);
305 Polygon_mesh_processing::connected_component(
306 face(opposite(bhd, mesh), mesh),
307 mesh,
308 boost::make_function_output_iterator(fc));
309
310 return is_one_to_one_mapping(mesh, faces, uvmap);
311 }
312
313 } // namespace internal
314
315 } // namespace Surface_mesh_parameterization
316
317 } // namespace CGAL
318
319 #endif // CGAL_SURFACE_MESH_PARAMETERIZATION_INTERNAL_VALIDITY_H
320