| 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 | #ifndef GEOGRAM_VORONOI_RVD | ||
| 41 | #define GEOGRAM_VORONOI_RVD | ||
| 42 | |||
| 43 | #include <geogram/basic/common.h> | ||
| 44 | #include <geogram/mesh/index.h> | ||
| 45 | #include <geogram/mesh/mesh.h> | ||
| 46 | #include <geogram/basic/geometry.h> | ||
| 47 | #include <geogram/basic/smart_pointer.h> | ||
| 48 | #include <geogram/basic/counted.h> | ||
| 49 | #include <geogram/basic/attributes.h> | ||
| 50 | |||
| 51 | #include <vector> | ||
| 52 | |||
| 53 | /** | ||
| 54 | * \file geogram/voronoi/RVD.h | ||
| 55 | * \brief Class and functions to compute restricted Voronoi diagrams | ||
| 56 | * and extract information from them. | ||
| 57 | */ | ||
| 58 | |||
| 59 | |||
| 60 | namespace GEOGen { | ||
| 61 | class PointAllocator; | ||
| 62 | } | ||
| 63 | |||
| 64 | namespace GEO { | ||
| 65 | |||
| 66 | class Delaunay; | ||
| 67 | class Map; | ||
| 68 | class IntegrationSimplex; | ||
| 69 | class MeshFacetsAABB; | ||
| 70 | class RVDPolyhedronCallback; | ||
| 71 | class RVDPolygonCallback; | ||
| 72 | |||
| 73 | /** | ||
| 74 | * \brief Computes a Restricted Voronoi Diagram (RVD). | ||
| 75 | * | ||
| 76 | * \details A Restricted Voronoi Diagram is the intersection | ||
| 77 | * between a surface mesh and a Voronoi diagram, possibly | ||
| 78 | * embedded in high-dimensional space. This class is used | ||
| 79 | * (mostly) by CentroidalVoronoiTesselation (CVT), | ||
| 80 | * that distributes points uniformly over a surface. This | ||
| 81 | * class does all the geometric work for CVT. | ||
| 82 | * | ||
| 83 | * \note This class is mainly a wrapper around the generic implementation | ||
| 84 | * GEOGen::RestrictedVoronoiDiagram. | ||
| 85 | * | ||
| 86 | * \see CentroidalVoronoiTesselation | ||
| 87 | * \see GEOGen::RestrictedVoronoiDiagram | ||
| 88 | */ | ||
| 89 | class GEOGRAM_API RestrictedVoronoiDiagram : public Counted { | ||
| 90 | public: | ||
| 91 | /** | ||
| 92 | * \brief Creates a RestrictedVoronoiDiagram. | ||
| 93 | * | ||
| 94 | * \details The dimension is determined by \p mesh->dimension(). | ||
| 95 | * \param[in] delaunay the Delaunay triangulation that defines the | ||
| 96 | * Voronoi diagram. | ||
| 97 | * \param[in] mesh the mesh that restricts the Voronoi diagram | ||
| 98 | * \param[in] R3_embedding gives for each vertex | ||
| 99 | * its mapping in 3D space. | ||
| 100 | * \param[in] R3_embedding_stride gives the stride between | ||
| 101 | * two consecutive vertices in R3_embedding | ||
| 102 | */ | ||
| 103 | static RestrictedVoronoiDiagram* create( | ||
| 104 | Delaunay* delaunay, Mesh* mesh, | ||
| 105 | const double* R3_embedding, index_t R3_embedding_stride | ||
| 106 | ); | ||
| 107 | |||
| 108 | /** | ||
| 109 | * \brief Creates a RestrictedVoronoiDiagram. | ||
| 110 | * | ||
| 111 | * \details The dimension is determined by \p mesh->dimension(). | ||
| 112 | * The first three coordinates of each vertex are supposed to be x,y,z. | ||
| 113 | * (if it is not the case, use | ||
| 114 | * create(Delaunay*,Mesh*,const double*, index_t) or | ||
| 115 | * create(Delaunay*,Mesh*,const vector<vec3>&) instead). | ||
| 116 | * \param[in] delaunay the Delaunay triangulation that defines the | ||
| 117 | * Voronoi diagram. | ||
| 118 | * \param[in] mesh the mesh that restricts the Voronoi diagram | ||
| 119 | */ | ||
| 120 | 46 | static RestrictedVoronoiDiagram* create( | |
| 121 | Delaunay* delaunay, Mesh* mesh | ||
| 122 | ) { | ||
| 123 |
1/2✓ Branch 1 taken 46 times.
✗ Branch 2 not taken.
|
138 | return create( |
| 124 | delaunay, mesh, | ||
| 125 | 92 | (mesh->vertices.nb()>0) ? mesh->vertices.point_ptr(0) : nullptr, | |
| 126 | mesh->vertices.dimension() | ||
| 127 | 46 | ); | |
| 128 | } | ||
| 129 | |||
| 130 | /** | ||
| 131 | * \brief Creates a RestrictedVoronoiDiagram. | ||
| 132 | * | ||
| 133 | * \details Use this function if the nD coordinates of each mesh vertex | ||
| 134 | * are completely unrelated with x,y,z. | ||
| 135 | * The dimension is determined by \p mesh->dimension(). | ||
| 136 | * \param[in] delaunay the Delaunay triangulation that defines the | ||
| 137 | * Voronoi diagram. | ||
| 138 | * \param[in] mesh the mesh that restricts the Voronoi diagram | ||
| 139 | * \param[in] R3_embedding gives for each vertex its mapping | ||
| 140 | * in 3D space. | ||
| 141 | */ | ||
| 142 | ✗ | static RestrictedVoronoiDiagram* create( | |
| 143 | Delaunay* delaunay, Mesh* mesh, | ||
| 144 | const vector<vec3>& R3_embedding | ||
| 145 | ) { | ||
| 146 | ✗ | return create(delaunay, mesh, R3_embedding[0].data(), 3); | |
| 147 | } | ||
| 148 | |||
| 149 | /** | ||
| 150 | * \brief Gets the dimension used by this RestrictedVoronoiDiagram. | ||
| 151 | */ | ||
| 152 | ✗ | coord_index_t dimension() const { | |
| 153 | ✗ | return dimension_; | |
| 154 | } | ||
| 155 | |||
| 156 | /** | ||
| 157 | * \brief Gets the Delaunay triangulation. | ||
| 158 | */ | ||
| 159 | ✗ | Delaunay* delaunay() { | |
| 160 | ✗ | return delaunay_; | |
| 161 | } | ||
| 162 | |||
| 163 | /** | ||
| 164 | * \brief Sets the Delaunay triangulation. | ||
| 165 | */ | ||
| 166 | virtual void set_delaunay(Delaunay* delaunay); | ||
| 167 | |||
| 168 | /** | ||
| 169 | * \brief Tests whether volumetric mode is used. | ||
| 170 | */ | ||
| 171 | 2050 | bool volumetric() const { | |
| 172 | 2050 | return volumetric_; | |
| 173 | } | ||
| 174 | |||
| 175 | /** | ||
| 176 | * \brief Sets volumetric mode. | ||
| 177 | * \param[in] x if true, volumetric mode is used, otherwise | ||
| 178 | * surfacic mode is used. | ||
| 179 | */ | ||
| 180 | virtual void set_volumetric(bool x) = 0; | ||
| 181 | |||
| 182 | /** | ||
| 183 | * \brief Computes a random initial sampling in nD. | ||
| 184 | * \details Depending on the value of the volumetric() flag, | ||
| 185 | * this functions samples either the triangles or the tetrahedra | ||
| 186 | * of the mesh. The coordinates of the computed points are stored in | ||
| 187 | * array \p p which must be large enough to contain | ||
| 188 | * \c dimension()*nb_points point coordinates. | ||
| 189 | * \param[out] p stores the computed points. | ||
| 190 | * \param[in] nb_points number of points to compute | ||
| 191 | * \param[in] verbose if set, display message | ||
| 192 | */ | ||
| 193 | 10 | bool compute_initial_sampling( | |
| 194 | double* p, index_t nb_points, bool verbose = false | ||
| 195 | ) { | ||
| 196 | 10 | bool result = true; | |
| 197 |
2/2✓ Branch 1 taken 4 times.
✓ Branch 2 taken 6 times.
|
10 | if(volumetric()) { |
| 198 | 4 | result = compute_initial_sampling_in_volume( | |
| 199 | p, nb_points, verbose | ||
| 200 | ); | ||
| 201 | } else { | ||
| 202 | 6 | result = compute_initial_sampling_on_surface( | |
| 203 | p, nb_points, verbose | ||
| 204 | ); | ||
| 205 | } | ||
| 206 | 10 | return result; | |
| 207 | } | ||
| 208 | |||
| 209 | /** | ||
| 210 | * \brief Computes a random initial sampling of the surface in nD. | ||
| 211 | * | ||
| 212 | * \details This function is used to initialize | ||
| 213 | * a CentroidalVoronoiTesselation. The coordinates of the computed | ||
| 214 | * points are stored in array \p p which must be large enough to | ||
| 215 | * contain \c dimension()*nb_points point coordinates. | ||
| 216 | * \param[out] p stores the computed points | ||
| 217 | * \param[in] nb_points number of points to compute | ||
| 218 | * \param[in] verbose if set, display message | ||
| 219 | */ | ||
| 220 | virtual bool compute_initial_sampling_on_surface( | ||
| 221 | double* p, index_t nb_points, bool verbose | ||
| 222 | ) = 0; | ||
| 223 | |||
| 224 | /** | ||
| 225 | * \brief Computes a random initial sampling of the volume in nD. | ||
| 226 | * | ||
| 227 | * \details This function is used to initialize | ||
| 228 | * a CentroidalVoronoiTesselation. The coordinates of the computed | ||
| 229 | * points are stored in array \p p which must be large enough to | ||
| 230 | * contain \c dimension()*nb_points point coordinates. | ||
| 231 | * \param[out] p stores the computed points | ||
| 232 | * \param[in] nb_points number of points to compute | ||
| 233 | * \param[in] verbose if set, display message | ||
| 234 | */ | ||
| 235 | virtual bool compute_initial_sampling_in_volume( | ||
| 236 | double* p, index_t nb_points, bool verbose | ||
| 237 | ) = 0; | ||
| 238 | |||
| 239 | /** | ||
| 240 | * \brief Computes the centroids and masses | ||
| 241 | * of the Voronoi cells restricted to the surface. | ||
| 242 | * | ||
| 243 | * \details This function is used by Lloyd relaxation in | ||
| 244 | * CentroidalVoronoiTesselation. | ||
| 245 | * | ||
| 246 | * \param[out] mg (size = dimension()*delaunay()->nb_vertices()) : | ||
| 247 | * stores for each point the mass times the centroid of | ||
| 248 | * the restricted voronoi cell. | ||
| 249 | * \param[out] m (size = delaunay()->nb_vertices()) : | ||
| 250 | * stores for each point the mass of the restricted voronoi cell. | ||
| 251 | */ | ||
| 252 | virtual void compute_centroids_on_surface(double* mg, double* m) = 0; | ||
| 253 | |||
| 254 | /** | ||
| 255 | * \brief Computes the centroids and masses | ||
| 256 | * of the Voronoi cells restricted to the volume. | ||
| 257 | * | ||
| 258 | * \details This function is used by Lloyd relaxation in | ||
| 259 | * CentroidalVoronoiTesselation. | ||
| 260 | * | ||
| 261 | * \param[out] mg (size = dimension()*delaunay()->nb_vertices()) : | ||
| 262 | * stores for each point the mass times the centroid of | ||
| 263 | * the restricted voronoi cell. | ||
| 264 | * \param[out] m (size = delaunay()->nb_vertices()) : | ||
| 265 | * stores for each point the mass of the restricted voronoi cell. | ||
| 266 | */ | ||
| 267 | virtual void compute_centroids_in_volume(double* mg, double* m) = 0; | ||
| 268 | |||
| 269 | /** | ||
| 270 | * \brief Computes the centroids and masses | ||
| 271 | * of the restricted Voronoi cells. | ||
| 272 | * | ||
| 273 | * \details Depending on the volumetric() flag, the | ||
| 274 | * Voronoi cells are restricted to the surface (facets of the mesh) | ||
| 275 | * or to the volume (tetrahedra of the mesh). This function is used | ||
| 276 | * by Lloyd relaxation in CentroidalVoronoiTesselation. | ||
| 277 | * | ||
| 278 | * \param[out] mg (size = dimension()*delaunay()->nb_vertices()) : | ||
| 279 | * stores for each point the mass times the centroid of | ||
| 280 | * the restricted voronoi cell. | ||
| 281 | * \param[out] m (size = delaunay()->nb_vertices()) : | ||
| 282 | * stores for each point the mass of the restricted voronoi cell. | ||
| 283 | */ | ||
| 284 | 2000 | void compute_centroids(double* mg, double* m) { | |
| 285 |
2/2✓ Branch 1 taken 800 times.
✓ Branch 2 taken 1200 times.
|
2000 | if(volumetric()) { |
| 286 | 800 | compute_centroids_in_volume(mg, m); | |
| 287 | } else { | ||
| 288 | 1200 | compute_centroids_on_surface(mg, m); | |
| 289 | } | ||
| 290 | 2000 | } | |
| 291 | |||
| 292 | /** | ||
| 293 | * \brief Computes the value and gradient of | ||
| 294 | * Lloyd's function (quantization noise power) on | ||
| 295 | * the surface. | ||
| 296 | * | ||
| 297 | * \details This function is used by Newton optimization | ||
| 298 | * in CentroidalVoronoiTesselation. | ||
| 299 | * | ||
| 300 | * \param[out] f the computed value of the quantization noise power. | ||
| 301 | * \param[out] g (size = dimension()*delaunay()->nb_vertices()) : | ||
| 302 | * the gradient of the quantization noise power. | ||
| 303 | */ | ||
| 304 | virtual void compute_CVT_func_grad_on_surface(double& f, double* g) = 0; | ||
| 305 | |||
| 306 | /** | ||
| 307 | * \brief Computes the value and gradient of | ||
| 308 | * Lloyd's function (quantization noise power) in | ||
| 309 | * the volume. | ||
| 310 | * | ||
| 311 | * \details This function is used by Newton optimization | ||
| 312 | * in CentroidalVoronoiTesselation. | ||
| 313 | * | ||
| 314 | * \param[out] f the computed value of the quantization noise power. | ||
| 315 | * \param[out] g (size = dimension()*delaunay()->nb_vertices()) : | ||
| 316 | * the gradient of the quantization noise power. | ||
| 317 | */ | ||
| 318 | virtual void compute_CVT_func_grad_in_volume(double& f, double* g) = 0; | ||
| 319 | |||
| 320 | /** | ||
| 321 | * \brief Computes the value and gradient of | ||
| 322 | * Lloyd's function (quantization noise power). | ||
| 323 | * | ||
| 324 | * \details Does computations either on the | ||
| 325 | * surface (triangles of the mesh) or in the volume | ||
| 326 | * (tetrahedra of the mesh), depending on the | ||
| 327 | * volumetric() flag. | ||
| 328 | * This function is used by Newton optimization | ||
| 329 | * in CentroidalVoronoiTesselation. | ||
| 330 | * | ||
| 331 | * \param[out] f the computed value of the quantization noise power. | ||
| 332 | * \param[out] g (size = dimension()*delaunay()->nb_vertices()) : | ||
| 333 | * the gradient of the quantization noise power. | ||
| 334 | */ | ||
| 335 | ✗ | void compute_CVT_func_grad(double& f, double* g) { | |
| 336 | ✗ | if(volumetric()) { | |
| 337 | ✗ | compute_CVT_func_grad_in_volume(f, g); | |
| 338 | } else { | ||
| 339 | ✗ | compute_CVT_func_grad_on_surface(f, g); | |
| 340 | } | ||
| 341 | ✗ | } | |
| 342 | |||
| 343 | /** | ||
| 344 | * \brief Computes the value and gradient of | ||
| 345 | * an objective function over Voronoi cells decomposed | ||
| 346 | * into simplices. | ||
| 347 | * \details This function is used by Newton optimization | ||
| 348 | * in CentroidalVoronoiTesselation. | ||
| 349 | * \param[out] f the value of the objective function | ||
| 350 | * \param[out] g the gradient of the objective function | ||
| 351 | * \param[in,out] F the object that computes the objective function | ||
| 352 | * and its gradients over a simplex. The contribution of each simplex | ||
| 353 | * is added to the gradient referenced by \p F. | ||
| 354 | */ | ||
| 355 | virtual void compute_integration_simplex_func_grad( | ||
| 356 | double& f, double* g, IntegrationSimplex* F | ||
| 357 | )=0; | ||
| 358 | |||
| 359 | /** | ||
| 360 | * \brief Computes the projection of points onto the surface | ||
| 361 | * in nD space. | ||
| 362 | * \param[in] nb_points number of points to projects | ||
| 363 | * \param[in] points array of the coordinates of the points to | ||
| 364 | * project. Must contain at least \c dimension()*nb_points | ||
| 365 | * coordinates. | ||
| 366 | * \param[out] nearest (size=nb_points) the computed projections | ||
| 367 | * mapped to 3D space. | ||
| 368 | * \param[in] do_project if set, the input points are moved and | ||
| 369 | * projected onto the surface, else only the 3D projections | ||
| 370 | * are computed, without changing the input. | ||
| 371 | */ | ||
| 372 | virtual void project_points_on_surface( | ||
| 373 | index_t nb_points, double* points, | ||
| 374 | vec3* nearest, bool do_project = false | ||
| 375 | ) = 0; | ||
| 376 | |||
| 377 | /** | ||
| 378 | * \brief Computes the projection of points onto the surface | ||
| 379 | * in nD space. | ||
| 380 | * \param[in] nb_points number of points to projects | ||
| 381 | * \param[in] points array of the coordinates of the points to | ||
| 382 | * project. Must contain at least \c dimension()*nb_points | ||
| 383 | * coordinates. | ||
| 384 | * \param[out] nearest the computed projections | ||
| 385 | * mapped to 3D space. | ||
| 386 | * \param[in] do_project if set, the input points are moved and | ||
| 387 | * projected onto the surface, else only the 3D projections | ||
| 388 | * are computed, without changing the input. | ||
| 389 | */ | ||
| 390 | ✗ | void project_points_on_surface( | |
| 391 | index_t nb_points, double* points, | ||
| 392 | vector<vec3>& nearest, bool do_project = false | ||
| 393 | ) { | ||
| 394 | ✗ | nearest.resize(nb_points); | |
| 395 | ✗ | project_points_on_surface( | |
| 396 | ✗ | nb_points, points, &nearest[0], do_project | |
| 397 | ); | ||
| 398 | ✗ | } | |
| 399 | |||
| 400 | /** | ||
| 401 | * \brief Computes the projection of points onto the surface | ||
| 402 | * in nD space. | ||
| 403 | * \param[in] nb_points number of points to projects | ||
| 404 | * \param[in] points array of the coordinates of the points to | ||
| 405 | * project. Must contain at least \c dimension()*nb_points | ||
| 406 | * coordinates. | ||
| 407 | * \param[out] nearest the computed projections | ||
| 408 | * mapped to 3D space. | ||
| 409 | * \param[in] do_project if set, the input points are moved and | ||
| 410 | * projected onto the surface, else only the 3D projections | ||
| 411 | * are computed, without changing the input. | ||
| 412 | */ | ||
| 413 | ✗ | void project_points_on_surface( | |
| 414 | index_t nb_points, double* points, | ||
| 415 | vector<double>& nearest, bool do_project = false | ||
| 416 | ) { | ||
| 417 | ✗ | nearest.resize(nb_points * 3); | |
| 418 | ✗ | project_points_on_surface( | |
| 419 | ✗ | nb_points, points, (vec3*) (&nearest[0]), do_project | |
| 420 | ); | ||
| 421 | ✗ | } | |
| 422 | |||
| 423 | |||
| 424 | /** | ||
| 425 | * \brief Determines the operating mode of | ||
| 426 | * compute_RDT(). | ||
| 427 | * \details The flags can be combined with the | ||
| 428 | * 'bitwise or' (|) operator. | ||
| 429 | */ | ||
| 430 | enum RDTMode { | ||
| 431 | |||
| 432 | /** | ||
| 433 | * \brief Always use Delaunay seeds as | ||
| 434 | * vertex geometry. | ||
| 435 | */ | ||
| 436 | RDT_SEEDS_ALWAYS=0, | ||
| 437 | |||
| 438 | /** | ||
| 439 | * \brief If set, the dual of the connected | ||
| 440 | * components of the restricted Voronoi diagram | ||
| 441 | * is computed. | ||
| 442 | */ | ||
| 443 | RDT_MULTINERVE=1, | ||
| 444 | |||
| 445 | /** | ||
| 446 | * \brief If set, the vertices are generated | ||
| 447 | * at the centroids of the restricted Voronoi cells, | ||
| 448 | * instead of using the seeds. | ||
| 449 | */ | ||
| 450 | RDT_RVC_CENTROIDS=2, | ||
| 451 | |||
| 452 | /** | ||
| 453 | * \brief If set, the seeds are used whenever possible, | ||
| 454 | * i.e. whenever a restricted Voronoi cell has a single | ||
| 455 | * connected component. | ||
| 456 | */ | ||
| 457 | RDT_PREFER_SEEDS=4, | ||
| 458 | |||
| 459 | /** | ||
| 460 | * \brief If set, then the algorithm selects among the | ||
| 461 | * seed and the restricted voronoi cell centroid the | ||
| 462 | * one that is nearest to the surface. | ||
| 463 | * Important: before using this | ||
| 464 | * mode, the surface mesh needs to be reordered with | ||
| 465 | * Morton order (see GEO::mesh_reorder). | ||
| 466 | */ | ||
| 467 | RDT_SELECT_NEAREST=8, | ||
| 468 | |||
| 469 | /** | ||
| 470 | * \brief If set, then all the vertices are projected | ||
| 471 | * onto the surface. | ||
| 472 | * Important: before using this | ||
| 473 | * mode, the surface mesh needs to be reordered with | ||
| 474 | * Morton order (see GEO::mesh_reorder). | ||
| 475 | */ | ||
| 476 | RDT_PROJECT_ON_SURFACE=16, | ||
| 477 | |||
| 478 | /** | ||
| 479 | * \brief If set, the generated mesh is not repaired. | ||
| 480 | * As a result, triangles may be not properly | ||
| 481 | * oriented. | ||
| 482 | */ | ||
| 483 | RDT_DONT_REPAIR=32 | ||
| 484 | }; | ||
| 485 | |||
| 486 | |||
| 487 | /** | ||
| 488 | * \brief Computes the restricted Delaunay triangulation. | ||
| 489 | * | ||
| 490 | * \param[out] simplices the indices of all triangles vertices | ||
| 491 | * (or tetrahedra vertices in volumetric mode) | ||
| 492 | * \param[out] embedding the nD embedding of all vertices | ||
| 493 | * \param[in] mode specifies how vertices geometry is | ||
| 494 | * generated in surfacic mode (seeds or restricted Voronoi | ||
| 495 | * cells centroids) | ||
| 496 | * \param[in] seed_is_locked if set, specifies which seed | ||
| 497 | * is locked (size = delaunay()->nb_vertices()). Locked | ||
| 498 | * seeds are not replaced with the restricted Voronoi cell | ||
| 499 | * centroid. | ||
| 500 | * \param[in] AABB used if one of (RDT_RVC_PROJECT_ON_SURFACE, | ||
| 501 | * RDT_SELECT_NEAREST) is set in \p mode. If needed but not | ||
| 502 | * specified, then a temporary one is created. | ||
| 503 | */ | ||
| 504 | virtual void compute_RDT( | ||
| 505 | vector<index_t>& simplices, | ||
| 506 | vector<double>& embedding, | ||
| 507 | RDTMode mode = RDTMode(RDT_RVC_CENTROIDS | RDT_PREFER_SEEDS), | ||
| 508 | const vector<bool>& seed_is_locked = vector<bool>(), | ||
| 509 | MeshFacetsAABB* AABB = nullptr | ||
| 510 | ) = 0; | ||
| 511 | |||
| 512 | /** | ||
| 513 | * \brief Computes the restricted Delaunay triangulation. | ||
| 514 | * \param[out] RDT the computed restricted Delaunay triangulation | ||
| 515 | * \param[in] mode specifies how vertices geometry is | ||
| 516 | * generated in surfacic mode (seeds or restricted Voronoi | ||
| 517 | * cells centroids) | ||
| 518 | * \param[in] seed_is_locked if set, specifies which seed | ||
| 519 | * is locked (size = delaunay()->nb_vertices()). Locked | ||
| 520 | * seeds are not replaced with the restricted Voronoi cell | ||
| 521 | * centroid | ||
| 522 | * \param[in] AABB used if one of (RDT_RVC_PROJECT_ON_SURFACE, | ||
| 523 | * RDT_SELECT_NEAREST) is set in \p mode. If needed but not | ||
| 524 | * specified, then a temporary one is created. | ||
| 525 | */ | ||
| 526 | void compute_RDT( | ||
| 527 | Mesh& RDT, | ||
| 528 | RDTMode mode = RDTMode(RDT_RVC_CENTROIDS | RDT_PREFER_SEEDS), | ||
| 529 | const vector<bool>& seed_is_locked = vector<bool>(), | ||
| 530 | MeshFacetsAABB* AABB=nullptr | ||
| 531 | ); | ||
| 532 | |||
| 533 | /** | ||
| 534 | * \brief Computes the restricted Voronoi diagram and stores it | ||
| 535 | * in a mesh. | ||
| 536 | * \param[out] M the computed restricted Voronoi diagram | ||
| 537 | * \param[in] dim if different from 0, use only the | ||
| 538 | * first dim coordinates | ||
| 539 | * \param[in] cell_borders_only in volumetric mode, computes only | ||
| 540 | * the surfacic borders of the volumetric cells (for visualization | ||
| 541 | * purpose) | ||
| 542 | * \param[in] integration_simplices in volumetric mode, if set, | ||
| 543 | * the generated tetrahedra systematically have the Voronoi seed | ||
| 544 | * as the first vertex. As a consequence, the mesh is not necessarily | ||
| 545 | * geometrically correct (it may have inverted elements), but it is | ||
| 546 | * algebraically correct (the sum of signed volumes corresponds the | ||
| 547 | * the total volume of each cell). | ||
| 548 | */ | ||
| 549 | virtual void compute_RVD( | ||
| 550 | Mesh& M, | ||
| 551 | coord_index_t dim = 0, | ||
| 552 | bool cell_borders_only = false, | ||
| 553 | bool integration_simplices = false | ||
| 554 | ) = 0; | ||
| 555 | |||
| 556 | |||
| 557 | /** | ||
| 558 | * \brief Computes a restricted Voronoi cell. | ||
| 559 | * \details A restricted Voronoi cell is the intersection | ||
| 560 | * between a Voronoi cell and a mesh. | ||
| 561 | * \param[in] i the index of the Voronoi cell | ||
| 562 | * \param[in] M the mesh the Voronoi cell will be restricted to. | ||
| 563 | * All its vertices should be of degree 3 (i.e., incident to | ||
| 564 | * exactly three facets). | ||
| 565 | * In volumetric mode, the surfacic part of the mesh corresponds | ||
| 566 | * to the boundary of a volume. In surfacic mode, the mesh is | ||
| 567 | * a set of polygonal facets. | ||
| 568 | * \param[out] result on exit, contains the intersection of the Voronoi | ||
| 569 | * cell \p i and the mesh \p M | ||
| 570 | * \param[in] copy_symbolic_info if true, symbolic | ||
| 571 | * information is copied. An attribute "id" is attached | ||
| 572 | * to the facets. The value of id[f] is either 1 + the index of | ||
| 573 | * the Voronoi vertex that generated with \p i the bisector that | ||
| 574 | * created the facet, or -1-g if the facet was an original facet | ||
| 575 | * of mesh \p M, where g is the index of the original facet in \p M. | ||
| 576 | * \note For now, only volumetric mode is implemented. | ||
| 577 | */ | ||
| 578 | virtual void compute_RVC( | ||
| 579 | index_t i, | ||
| 580 | Mesh& M, | ||
| 581 | Mesh& result, | ||
| 582 | bool copy_symbolic_info=false | ||
| 583 | ) = 0; | ||
| 584 | |||
| 585 | |||
| 586 | /** | ||
| 587 | * \brief Invokes a user callback for each intersection polyhedron | ||
| 588 | * of the restricted Voronoi diagram (volumetric mode only). | ||
| 589 | * \details Each intersection polyhedron is defined as the intersection | ||
| 590 | * between a Voronoi cell and a tetrahedron. | ||
| 591 | * \param[in] callback the set of user callbacks, as an instance of a | ||
| 592 | * class derived from RVDPolyhedronCallback. | ||
| 593 | * \param[in] symbolic if true, generate symbolic information in the | ||
| 594 | * vertices | ||
| 595 | * \param[in] connected_comp_priority if true, generate polyhedron | ||
| 596 | * intersections associated with the same Voronoi seed in order. | ||
| 597 | * \param[in] parallel if true, tentatively parallelize computation. | ||
| 598 | */ | ||
| 599 | virtual void for_each_polyhedron( | ||
| 600 | RVDPolyhedronCallback& callback, | ||
| 601 | bool symbolic = true, | ||
| 602 | bool connected_comp_priority = true, | ||
| 603 | bool parallel = false | ||
| 604 | ) = 0; | ||
| 605 | |||
| 606 | /** | ||
| 607 | * \brief Invokes a user callback for each intersection polygon | ||
| 608 | * of the restricted Voronoi diagram (surfacic mode only). | ||
| 609 | * \details Each intersection polygon is defined as the intersection | ||
| 610 | * between a Voronoi cell and a triangle. | ||
| 611 | * \param[in] callback the set of user callbacks, as an instance of a | ||
| 612 | * class derived from RVDPolygonCallback. | ||
| 613 | * \param[in] symbolic if true, generate symbolic information in the | ||
| 614 | * vertices | ||
| 615 | * \param[in] connected_comp_priority if true, generate polyhedron | ||
| 616 | * intersections associated with the same Voronoi seed in order. | ||
| 617 | * \param[in] parallel if true, tentatively parallelize computation. | ||
| 618 | */ | ||
| 619 | virtual void for_each_polygon( | ||
| 620 | RVDPolygonCallback& callback, | ||
| 621 | bool symbolic = true, | ||
| 622 | bool connected_comp_priority = true, | ||
| 623 | bool parallel = false | ||
| 624 | ) = 0; | ||
| 625 | |||
| 626 | |||
| 627 | /** | ||
| 628 | * \brief Specifies whether the "radius of security" | ||
| 629 | * criterion should be enforced. | ||
| 630 | */ | ||
| 631 | virtual void set_check_SR(bool x) = 0; | ||
| 632 | |||
| 633 | /** | ||
| 634 | * \brief Specifies whether exact predicates should | ||
| 635 | * be used. | ||
| 636 | */ | ||
| 637 | virtual void set_exact_predicates(bool x) = 0; | ||
| 638 | |||
| 639 | /** | ||
| 640 | * \brief Tests whether exact predicates are used. | ||
| 641 | */ | ||
| 642 | virtual bool exact_predicates() const = 0; | ||
| 643 | |||
| 644 | /** | ||
| 645 | * \brief Partitions the mesh and creates | ||
| 646 | * local storage for multithreaded implementation. | ||
| 647 | */ | ||
| 648 | virtual void create_threads() = 0; | ||
| 649 | |||
| 650 | /** | ||
| 651 | * \brief Deletes all the local storage associated | ||
| 652 | * with the threads. | ||
| 653 | */ | ||
| 654 | virtual void delete_threads() = 0; | ||
| 655 | |||
| 656 | /** | ||
| 657 | * \brief Restricts surfacic computations to a part of the input mesh. | ||
| 658 | * \details The part of the input mesh should be specified as | ||
| 659 | * a contiguous range of facet indices. | ||
| 660 | * \param[in] facets_begin first facet in the range | ||
| 661 | * \param[in] facets_end one past last facet in the range | ||
| 662 | */ | ||
| 663 | virtual void set_facets_range( | ||
| 664 | index_t facets_begin, index_t facets_end | ||
| 665 | ) = 0; | ||
| 666 | |||
| 667 | /** | ||
| 668 | * \brief Restricts volumetric computations to a part of the input mesh. | ||
| 669 | * \details The part of the input mesh should be specified as | ||
| 670 | * a contiguous range of tetrahedra indices. | ||
| 671 | * \param[in] tets_begin first tetrahedron in the range | ||
| 672 | * \param[in] tets_end one past last tetrahedron in the range | ||
| 673 | */ | ||
| 674 | virtual void set_tetrahedra_range( | ||
| 675 | index_t tets_begin, index_t tets_end | ||
| 676 | ) = 0; | ||
| 677 | |||
| 678 | /** | ||
| 679 | * \brief Gets the mapping in R3 of a point. | ||
| 680 | * \param[in] v index of the point | ||
| 681 | * \return a const reference to the mapping in R3 of the point | ||
| 682 | */ | ||
| 683 | ✗ | const vec3& R3_embedding(index_t v) const { | |
| 684 | ✗ | geo_debug_assert(v < mesh_->vertices.nb()); | |
| 685 | return *reinterpret_cast<const vec3*>( | ||
| 686 | ✗ | R3_embedding_base_ + v * R3_embedding_stride_ | |
| 687 | ✗ | ); | |
| 688 | } | ||
| 689 | |||
| 690 | /** | ||
| 691 | * \brief Gets the input mesh. | ||
| 692 | */ | ||
| 693 | Mesh* mesh() { | ||
| 694 | return mesh_; | ||
| 695 | } | ||
| 696 | |||
| 697 | /** | ||
| 698 | * \brief Gets the PointAllocator. | ||
| 699 | * \return a pointer to the PointAllocator, used | ||
| 700 | * to create the new vertices generated by | ||
| 701 | * intersections. | ||
| 702 | */ | ||
| 703 | virtual GEOGen::PointAllocator* point_allocator() = 0; | ||
| 704 | |||
| 705 | protected: | ||
| 706 | /** | ||
| 707 | * \brief This constructor is never called directly. | ||
| 708 | * \details Use one of the three versions of create() instead. | ||
| 709 | */ | ||
| 710 | RestrictedVoronoiDiagram( | ||
| 711 | Delaunay* delaunay, Mesh* mesh, | ||
| 712 | const double* R3_embedding, index_t R3_embedding_stride | ||
| 713 | ); | ||
| 714 | |||
| 715 | /** | ||
| 716 | * \brief RestrictedVoronoiDiagram destructor | ||
| 717 | */ | ||
| 718 | ~RestrictedVoronoiDiagram() override; | ||
| 719 | |||
| 720 | protected: | ||
| 721 | coord_index_t dimension_; | ||
| 722 | Delaunay* delaunay_; | ||
| 723 | Mesh* mesh_; | ||
| 724 | const double* R3_embedding_base_; | ||
| 725 | index_t R3_embedding_stride_; | ||
| 726 | bool has_weights_; | ||
| 727 | Attribute<double> vertex_weight_; | ||
| 728 | index_t facets_begin_; | ||
| 729 | index_t facets_end_; | ||
| 730 | index_t tets_begin_; | ||
| 731 | index_t tets_end_; | ||
| 732 | bool volumetric_; | ||
| 733 | }; | ||
| 734 | |||
| 735 | /** \brief Smart pointer to a RestrictedVoronoiDiagram object */ | ||
| 736 | typedef SmartPointer<RestrictedVoronoiDiagram> | ||
| 737 | RestrictedVoronoiDiagram_var; | ||
| 738 | } | ||
| 739 | |||
| 740 | #endif | ||
| 741 |