Geogram  Version 1.9.1
A programming library of geometric algorithms
RVD.h
Go to the documentation of this file.
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>
48 #include <geogram/basic/counted.h>
50 
51 #include <vector>
52 
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 
89  class GEOGRAM_API RestrictedVoronoiDiagram : public Counted {
90  public:
104  Delaunay* delaunay, Mesh* mesh,
105  const double* R3_embedding, index_t R3_embedding_stride
106  );
107 
121  Delaunay* delaunay, Mesh* mesh
122  ) {
123  return create(
124  delaunay, mesh,
125  (mesh->vertices.nb() > 0) ? mesh->vertices.point_ptr(0) : nullptr,
126  mesh->vertices.dimension()
127  );
128  }
129 
143  Delaunay* delaunay, Mesh* mesh,
144  const vector<vec3>& R3_embedding
145  ) {
146  return create(delaunay, mesh, R3_embedding[0].data(), 3);
147  }
148 
153  return dimension_;
154  }
155 
160  return delaunay_;
161  }
162 
166  virtual void set_delaunay(Delaunay* delaunay);
167 
171  bool volumetric() const {
172  return volumetric_;
173  }
174 
180  virtual void set_volumetric(bool x) = 0;
181 
194  double* p, index_t nb_points, bool verbose = false
195  ) {
196  bool result = true;
197  if(volumetric()) {
198  result = compute_initial_sampling_in_volume(
199  p, nb_points, verbose
200  );
201  } else {
202  result = compute_initial_sampling_on_surface(
203  p, nb_points, verbose
204  );
205  }
206  return result;
207  }
208 
221  double* p, index_t nb_points, bool verbose
222  ) = 0;
223 
236  double* p, index_t nb_points, bool verbose
237  ) = 0;
238 
252  virtual void compute_centroids_on_surface(double* mg, double* m) = 0;
253 
267  virtual void compute_centroids_in_volume(double* mg, double* m) = 0;
268 
284  void compute_centroids(double* mg, double* m) {
285  if(volumetric()) {
286  compute_centroids_in_volume(mg, m);
287  } else {
288  compute_centroids_on_surface(mg, m);
289  }
290  }
291 
304  virtual void compute_CVT_func_grad_on_surface(double& f, double* g) = 0;
305 
318  virtual void compute_CVT_func_grad_in_volume(double& f, double* g) = 0;
319 
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 
356  double& f, double* g, IntegrationSimplex* F
357  )=0;
358 
373  index_t nb_points, double* points,
374  vec3* nearest, bool do_project = false
375  ) = 0;
376 
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 
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 
430  enum RDTMode {
431 
436  RDT_SEEDS_ALWAYS=0,
437 
443  RDT_MULTINERVE=1,
444 
450  RDT_RVC_CENTROIDS=2,
451 
457  RDT_PREFER_SEEDS=4,
458 
467  RDT_SELECT_NEAREST=8,
468 
476  RDT_PROJECT_ON_SURFACE=16,
477 
483  RDT_DONT_REPAIR=32
484  };
485 
486 
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 
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 
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 
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 
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 
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 
631  virtual void set_check_SR(bool x) = 0;
632 
637  virtual void set_exact_predicates(bool x) = 0;
638 
642  virtual bool exact_predicates() const = 0;
643 
648  virtual void create_threads() = 0;
649 
654  virtual void delete_threads() = 0;
655 
663  virtual void set_facets_range(
664  index_t facets_begin, index_t facets_end
665  ) = 0;
666 
674  virtual void set_tetrahedra_range(
675  index_t tets_begin, index_t tets_end
676  ) = 0;
677 
683  const vec3& R3_embedding(index_t v) const {
684  geo_debug_assert(v < mesh_->vertices.nb());
685  return *(const vec3*) (R3_embedding_base_ + v * R3_embedding_stride_);
686  }
687 
691  Mesh* mesh() {
692  return mesh_;
693  }
694 
702 
703  protected:
709  Delaunay* delaunay, Mesh* mesh,
710  const double* R3_embedding, index_t R3_embedding_stride
711  );
712 
717 
718  protected:
719  coord_index_t dimension_;
720  Delaunay* delaunay_;
721  Mesh* mesh_;
722  const double* R3_embedding_base_;
723  index_t R3_embedding_stride_;
724  bool has_weights_;
725  Attribute<double> vertex_weight_;
726  signed_index_t facets_begin_;
727  signed_index_t facets_end_;
728  signed_index_t tets_begin_;
729  signed_index_t tets_end_;
730  bool volumetric_;
731  };
732 
736 }
737 
738 #endif
#define geo_debug_assert(x)
Verifies that a condition is met.
Definition: assert.h:196
Generic mechanism for attributes.
An allocator for points that are created from intersections in GenericVoronoiDiagram.
Base class for Axis Aligned Bounding Box trees.
Definition: mesh_AABB.h:60
Base class for reference-counted objects.
Definition: counted.h:71
Abstract interface for Delaunay triangulation in Nd.
Definition: delaunay.h:71
Computes an objective function and its gradient over a restricted Voronoi diagram.
Axis Aligned Bounding Box tree of mesh facets in 3D.
Definition: mesh_AABB.h:383
index_t nb() const
Gets the number of (sub-)elements.
Definition: mesh.h:89
const double * point_ptr(index_t v) const
Gets a point.
Definition: mesh.h:455
index_t dimension() const
Gets the dimension of the vertices.
Definition: mesh.h:427
Represents a mesh.
Definition: mesh.h:2701
Baseclass for user functions called for each polygon of a surfacic restricted Voronoi diagram.
Definition: RVD_callback.h:153
Baseclass for user functions called for each polyhedron of a volumetric restricted Voronoi diagram.
Definition: RVD_callback.h:202
Computes a Restricted Voronoi Diagram (RVD).
Definition: RVD.h:89
RDTMode
Determines the operating mode of compute_RDT().
Definition: RVD.h:430
virtual void compute_CVT_func_grad_in_volume(double &f, double *g)=0
Computes the value and gradient of Lloyd's function (quantization noise power) in the volume.
virtual void for_each_polygon(RVDPolygonCallback &callback, bool symbolic=true, bool connected_comp_priority=true, bool parallel=false)=0
Invokes a user callback for each intersection polygon of the restricted Voronoi diagram (surfacic mod...
virtual void set_volumetric(bool x)=0
Sets volumetric mode.
virtual void set_check_SR(bool x)=0
Specifies whether the "radius of security" criterion should be enforced.
virtual void compute_centroids_in_volume(double *mg, double *m)=0
Computes the centroids and masses of the Voronoi cells restricted to the volume.
coord_index_t dimension() const
Gets the dimension used by this RestrictedVoronoiDiagram.
Definition: RVD.h:152
virtual void compute_RVD(Mesh &M, coord_index_t dim=0, bool cell_borders_only=false, bool integration_simplices=false)=0
Computes the restricted Voronoi diagram and stores it in a mesh.
virtual bool exact_predicates() const =0
Tests whether exact predicates are used.
virtual bool compute_initial_sampling_on_surface(double *p, index_t nb_points, bool verbose)=0
Computes a random initial sampling of the surface in nD.
virtual void set_exact_predicates(bool x)=0
Specifies whether exact predicates should be used.
virtual void set_delaunay(Delaunay *delaunay)
Sets the Delaunay triangulation.
virtual void create_threads()=0
Partitions the mesh and creates local storage for multithreaded implementation.
virtual void compute_RVC(index_t i, Mesh &M, Mesh &result, bool copy_symbolic_info=false)=0
Computes a restricted Voronoi cell.
virtual void for_each_polyhedron(RVDPolyhedronCallback &callback, bool symbolic=true, bool connected_comp_priority=true, bool parallel=false)=0
Invokes a user callback for each intersection polyhedron of the restricted Voronoi diagram (volumetri...
virtual void compute_integration_simplex_func_grad(double &f, double *g, IntegrationSimplex *F)=0
Computes the value and gradient of an objective function over Voronoi cells decomposed into simplices...
virtual bool compute_initial_sampling_in_volume(double *p, index_t nb_points, bool verbose)=0
Computes a random initial sampling of the volume in nD.
Delaunay * delaunay()
Gets the Delaunay triangulation.
Definition: RVD.h:159
static RestrictedVoronoiDiagram * create(Delaunay *delaunay, Mesh *mesh, const double *R3_embedding, index_t R3_embedding_stride)
Creates a RestrictedVoronoiDiagram.
virtual void compute_centroids_on_surface(double *mg, double *m)=0
Computes the centroids and masses of the Voronoi cells restricted to the surface.
virtual void delete_threads()=0
Deletes all the local storage associated with the threads.
const vec3 & R3_embedding(index_t v) const
Gets the mapping in R3 of a point.
Definition: RVD.h:683
void compute_RDT(Mesh &RDT, RDTMode mode=RDTMode(RDT_RVC_CENTROIDS|RDT_PREFER_SEEDS), const vector< bool > &seed_is_locked=vector< bool >(), MeshFacetsAABB *AABB=nullptr)
Computes the restricted Delaunay triangulation.
Mesh * mesh()
Gets the input mesh.
Definition: RVD.h:691
static RestrictedVoronoiDiagram * create(Delaunay *delaunay, Mesh *mesh, const vector< vec3 > &R3_embedding)
Creates a RestrictedVoronoiDiagram.
Definition: RVD.h:142
void compute_centroids(double *mg, double *m)
Computes the centroids and masses of the restricted Voronoi cells.
Definition: RVD.h:284
bool compute_initial_sampling(double *p, index_t nb_points, bool verbose=false)
Computes a random initial sampling in nD.
Definition: RVD.h:193
virtual void set_facets_range(index_t facets_begin, index_t facets_end)=0
Restricts surfacic computations to a part of the input mesh.
virtual void set_tetrahedra_range(index_t tets_begin, index_t tets_end)=0
Restricts volumetric computations to a part of the input mesh.
void compute_CVT_func_grad(double &f, double *g)
Computes the value and gradient of Lloyd's function (quantization noise power).
Definition: RVD.h:335
bool volumetric() const
Tests whether volumetric mode is used.
Definition: RVD.h:171
RestrictedVoronoiDiagram(Delaunay *delaunay, Mesh *mesh, const double *R3_embedding, index_t R3_embedding_stride)
This constructor is never called directly.
virtual void compute_CVT_func_grad_on_surface(double &f, double *g)=0
Computes the value and gradient of Lloyd's function (quantization noise power) on the surface.
void project_points_on_surface(index_t nb_points, double *points, vector< vec3 > &nearest, bool do_project=false)
Computes the projection of points onto the surface in nD space.
Definition: RVD.h:390
void project_points_on_surface(index_t nb_points, double *points, vector< double > &nearest, bool do_project=false)
Computes the projection of points onto the surface in nD space.
Definition: RVD.h:413
virtual void compute_RDT(vector< index_t > &simplices, vector< double > &embedding, RDTMode mode=RDTMode(RDT_RVC_CENTROIDS|RDT_PREFER_SEEDS), const vector< bool > &seed_is_locked=vector< bool >(), MeshFacetsAABB *AABB=nullptr)=0
Computes the restricted Delaunay triangulation.
static RestrictedVoronoiDiagram * create(Delaunay *delaunay, Mesh *mesh)
Creates a RestrictedVoronoiDiagram.
Definition: RVD.h:120
~RestrictedVoronoiDiagram() override
RestrictedVoronoiDiagram destructor.
virtual void project_points_on_surface(index_t nb_points, double *points, vec3 *nearest, bool do_project=false)=0
Computes the projection of points onto the surface in nD space.
virtual GEOGen::PointAllocator * point_allocator()=0
Gets the PointAllocator.
Specialization of vector for elements of type bool.
Definition: memory.h:795
Base class of reference-counted objects, to be used with smart pointers.
Common include file, providing basic definitions. Should be included before anything else by all head...
Geometric functions in 2d and 3d.
Classes for managing tuples of indices.
The class that represents a mesh.
Global Vorpaline namespace.
Definition: basic.h:55
void parallel(std::function< void()> f1, std::function< void()> f2)
Calls functions in parallel.
geo_signed_index_t signed_index_t
The type for storing and manipulating indices differences.
Definition: numeric.h:343
geo_index_t index_t
The type for storing and manipulating indices.
Definition: numeric.h:329
SmartPointer< RestrictedVoronoiDiagram > RestrictedVoronoiDiagram_var
Smart pointer to a RestrictedVoronoiDiagram object.
Definition: RVD.h:735
geo_coord_index_t coord_index_t
The type for storing coordinate indices, and iterating on the coordinates of a point.
Definition: numeric.h:363
Pointers with automatic reference counting.