1 // Copyright (c) 2017 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/Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/random_perturbation.h $
7 // $Id: random_perturbation.h 10ba347 2020-10-02T15:20:53+02:00 Sebastien Loriot
8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 //
11 // Author(s)     : Jane Tournois
12 
13 #ifndef CGAL_POLYGON_MESH_PROCESSING_RANDOM_PERTURBATION_H
14 #define CGAL_POLYGON_MESH_PROCESSING_RANDOM_PERTURBATION_H
15 
16 #include <CGAL/license/Polygon_mesh_processing/meshing_hole_filling.h>
17 
18 #include <CGAL/disable_warnings.h>
19 
20 #include <CGAL/Polygon_mesh_processing/internal/Isotropic_remeshing/remesh_impl.h>
21 
22 #include <CGAL/Polygon_mesh_processing/internal/named_function_params.h>
23 #include <CGAL/Polygon_mesh_processing/internal/named_params_helper.h>
24 
25 #include <CGAL/AABB_tree.h>
26 #include <CGAL/AABB_traits.h>
27 #include <CGAL/AABB_face_graph_triangle_primitive.h>
28 
29 #include <CGAL/Random.h>
30 
31 
32 #ifdef CGAL_PMP_RANDOM_PERTURBATION_VERBOSE
33 #include <CGAL/Timer.h>
34 #endif
35 
36 namespace CGAL {
37 
38 namespace Polygon_mesh_processing {
39 
40 namespace internal {
41 
42   template<typename GT, typename RNG>
construct_random_vector_3(const double & max_size,RNG & rng,const GT & gt)43   typename GT::Vector_3 construct_random_vector_3(const double& max_size,
44                                                   RNG& rng,
45                                                   const GT& gt)
46   {
47     typedef typename GT::FT FT;
48     typename GT::Construct_vector_3 vec = gt.construct_vector_3_object();
49 
50     return vec(FT(rng.get_double(-max_size, max_size)),
51                FT(rng.get_double(-max_size, max_size)),
52                FT(rng.get_double(-max_size, max_size)));
53   }
54 
55   template<typename GT, typename VertexRange,
56            typename PM, typename VCMap, typename VPMap, typename RNG>
random_perturbation_impl(VertexRange vrange,PM & tmesh,const double & max_size,VCMap vcmap,VPMap vpmap,bool do_project,RNG & rng,const GT & gt)57   void random_perturbation_impl(VertexRange vrange,
58                                 PM& tmesh,
59                                 const double& max_size,
60                                 VCMap vcmap,
61                                 VPMap vpmap,
62                                 bool do_project,
63                                 RNG& rng,
64                                 const GT& gt)
65   {
66     typedef typename boost::graph_traits<PM>::vertex_descriptor vertex_descriptor;
67     typedef typename GT::Point_3    Point_3;
68 
69     typedef CGAL::AABB_face_graph_triangle_primitive<PM> Primitive;
70     typedef CGAL::AABB_traits<GT, Primitive> Traits;
71     typedef CGAL::AABB_tree<Traits> Tree;
72 
73     Tree tree;
74     if(do_project)
75     {
76       tree.rebuild(faces(tmesh).first, faces(tmesh).second, tmesh);
77     }
78     typename GT::Construct_translated_point_3 translate
79       = gt.construct_translated_point_3_object();
80 
81     for(vertex_descriptor v : vrange)
82     {
83       if (!get(vcmap, v) && !is_border(v, tmesh))
84       {
85         const Point_3& p = get(vpmap, v);
86         const Point_3 np = translate(p, construct_random_vector_3<GT>(max_size, rng, gt));
87 
88         if (do_project)
89           put(vpmap, v, tree.closest_point(np)); //project on input surface
90         else
91           put(vpmap, v, np);
92       }
93     }
94   }
95 
96 } //end namespace internal
97 
98 /*!
99 * \ingroup PMP_meshing_grp
100 * @brief randomly perturbs the locations of vertices of a triangulated surface mesh.
101 * By default, the vertices are re-projected onto the input surface after perturbation.
102 * Note that no geometric checks are done after the perturbation
103 * (face orientation might become incorrect and self-intersections might be introduced).
104 *
105 * @tparam VertexRange model of `Range`, holding
106 *         vertices of type `boost::graph_traits<TriangleMesh>::%vertex_descriptor`.
107 *         Its iterator type is `ForwardIterator`.
108 * @tparam TriangleMesh model of `MutableFaceGraph`.
109 * @tparam NamedParameters a sequence of \ref bgl_namedparameters "Named Parameters"
110 *
111 * @param vertices the range of vertices to be perturbed
112 * @param tmesh the triangulated surface mesh
113 * @param perturbation_max_size the maximal length of moves that can be applied to
114 *        vertices of `tmesh`.
115 * @param np an optional sequence of \ref bgl_namedparameters "Named Parameters" among the ones listed below
116 *
117 * \cgalNamedParamsBegin
118 *   \cgalParamNBegin{vertex_point_map}
119 *     \cgalParamDescription{a property map associating points to the vertices of `tmesh`}
120 *     \cgalParamType{a class model of `ReadWritePropertyMap` with `boost::graph_traits<TriangleMesh>::%vertex_descriptor`
121 *                    as key type and `%Point_3` as value type}
122 *     \cgalParamDefault{`boost::get(CGAL::vertex_point, tmesh)`}
123 *   \cgalParamNEnd
124 *
125 *   \cgalParamNBegin{geom_traits}
126 *     \cgalParamDescription{an instance of a geometric traits class}
127 *     \cgalParamType{a class model of `Kernel`}
128 *     \cgalParamDefault{a \cgal Kernel deduced from the point type, using `CGAL::Kernel_traits`}
129 *     \cgalParamExtra{The geometric traits class must be compatible with the vertex point type.}
130 *   \cgalParamNEnd
131 *
132 *   \cgalParamNBegin{vertex_is_constrained_map}
133 *     \cgalParamDescription{a property map containing the constrained-or-not status of each vertex of `tmesh`}
134 *     \cgalParamType{a class model of `ReadWritePropertyMap` with `boost::graph_traits<TriangleMesh>::%vertex_descriptor`
135 *                    as key type and `bool` as value type. It must be default constructible.}
136 *     \cgalParamDefault{a default property map where no vertex is constrained}
137 *     \cgalParamExtra{A constrained vertex cannot be modified at all during perturbation}
138 *   \cgalParamNEnd
139 *
140 *   \cgalParamNBegin{do_project}
141 *     \cgalParamDescription{indicates whether vertices are reprojected on the input surface
142 *                           after their coordinates random perturbation}
143 *     \cgalParamType{Boolean}
144 *     \cgalParamDefault{`true`}
145 *   \cgalParamNEnd
146 *
147 *   \cgalParamNBegin{random_seed}
148 *     \cgalParamDescription{a value to seed the random number generator, and make the perturbation deterministic}
149 *     \cgalParamType{unsigned int}
150 *     \cgalParamDefault{`unsigned int(-1)`}
151 *   \cgalParamNEnd
152 * \cgalNamedParamsEnd
153 *
154 */
155 template<typename VertexRange, typename TriangleMesh, typename NamedParameters>
random_perturbation(VertexRange vertices,TriangleMesh & tmesh,const double & perturbation_max_size,const NamedParameters & np)156 void random_perturbation(VertexRange vertices
157                        , TriangleMesh& tmesh
158                        , const double& perturbation_max_size
159                        , const NamedParameters& np)
160 {
161   typedef TriangleMesh PM;
162   using parameters::get_parameter;
163   using parameters::choose_parameter;
164 
165   typedef typename boost::graph_traits<PM>::vertex_descriptor vertex_descriptor;
166 
167 #ifdef CGAL_PMP_RANDOM_PERTURBATION_VERBOSE
168   std::cout << std::endl;
169   CGAL::Timer t;
170   std::cout << "Random perturbation (max size = "<< perturbation_max_size<<")...";
171   std::cout.flush();
172   t.start();
173 #endif
174 
175   typedef typename GetGeomTraits<PM, NamedParameters>::type GT;
176   GT gt = choose_parameter<GT>(get_parameter(np, internal_np::geom_traits));
177 
178   typedef typename GetVertexPointMap<PM, NamedParameters>::type VPMap;
179   VPMap vpmap = choose_parameter(get_parameter(np, internal_np::vertex_point),
180                                  get_property_map(vertex_point, tmesh));
181 
182   typedef typename internal_np::Lookup_named_param_def <
183       internal_np::vertex_is_constrained_t,
184       NamedParameters,
185       Static_boolean_property_map<vertex_descriptor, false> // default
186     > ::type VCMap;
187   VCMap vcmap = choose_parameter(get_parameter(np, internal_np::vertex_is_constrained),
188                                  Static_boolean_property_map<vertex_descriptor, false>());
189 
190   unsigned int seed = choose_parameter(get_parameter(np, internal_np::random_seed), -1);
191   bool do_project = choose_parameter(get_parameter(np, internal_np::do_project), true);
192 
193   CGAL::Random rng = (seed == unsigned(-1)) ? CGAL::Random() : CGAL::Random(seed);
194 
195   internal::random_perturbation_impl(vertices,
196           tmesh,
197           perturbation_max_size,
198           vcmap,
199           vpmap,
200           do_project,
201           rng,
202           gt);
203 
204 #ifdef CGAL_PMP_RANDOM_PERTURBATION_VERBOSE
205   t.stop();
206   std::cout << "Perturbation done (";
207   std::cout << t.time() << " sec )." << std::endl;
208 #endif
209 }
210 
211 /*!
212 * \ingroup PMP_meshing_grp
213 * @brief same as above, but all non-border vertices of `tmesh` are perturbed.
214 */
215 template<typename TriangleMesh, typename NamedParameters>
random_perturbation(TriangleMesh & tmesh,const double & perturbation_max_size,const NamedParameters & np)216 void random_perturbation(TriangleMesh& tmesh
217                        , const double& perturbation_max_size
218                        , const NamedParameters& np)
219 {
220   random_perturbation(vertices(tmesh), tmesh, perturbation_max_size, np);
221 }
222 
223 template<typename VertexRange, typename TriangleMesh>
random_perturbation(VertexRange vertices,TriangleMesh & tmesh,const double & perturbation_max_size)224 void random_perturbation(VertexRange vertices
225                        , TriangleMesh& tmesh
226                        , const double& perturbation_max_size)
227 {
228   random_perturbation(vertices, tmesh, perturbation_max_size,
229                       parameters::all_default());
230 }
231 
232 template<typename TriangleMesh>
random_perturbation(TriangleMesh & tmesh,const double & perturbation_max_size)233 void random_perturbation(TriangleMesh& tmesh
234                        , const double& perturbation_max_size)
235 {
236   random_perturbation(tmesh,
237                       perturbation_max_size,
238                       parameters::all_default());
239 }
240 
241 } //end namespace Polygon_mesh_processing
242 } //end namespace CGAL
243 
244 #include <CGAL/enable_warnings.h>
245 
246 #endif //CGAL_POLYGON_MESH_PROCESSING_RANDOM_PERTURBATION_H
247