Geogram
Version 1.9.1
A programming library of geometric algorithms
|
Computes a Restricted Voronoi Diagram (RVD). More...
#include <geogram/voronoi/RVD.h>
Public Types | |
enum | RDTMode { RDT_SEEDS_ALWAYS =0 , RDT_MULTINERVE =1 , RDT_RVC_CENTROIDS =2 , RDT_PREFER_SEEDS =4 , RDT_SELECT_NEAREST =8 , RDT_PROJECT_ON_SURFACE =16 , RDT_DONT_REPAIR =32 } |
Determines the operating mode of compute_RDT(). More... | |
Public Member Functions | |
coord_index_t | dimension () const |
Gets the dimension used by this RestrictedVoronoiDiagram. | |
Delaunay * | delaunay () |
Gets the Delaunay triangulation. | |
virtual void | set_delaunay (Delaunay *delaunay) |
Sets the Delaunay triangulation. | |
bool | volumetric () const |
Tests whether volumetric mode is used. | |
virtual void | set_volumetric (bool x)=0 |
Sets volumetric mode. More... | |
bool | compute_initial_sampling (double *p, index_t nb_points, bool verbose=false) |
Computes a random initial sampling in nD. More... | |
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. More... | |
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. More... | |
virtual void | compute_centroids_on_surface (double *mg, double *m)=0 |
Computes the centroids and masses of the Voronoi cells restricted to the surface. More... | |
virtual void | compute_centroids_in_volume (double *mg, double *m)=0 |
Computes the centroids and masses of the Voronoi cells restricted to the volume. More... | |
void | compute_centroids (double *mg, double *m) |
Computes the centroids and masses of the restricted Voronoi cells. More... | |
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. More... | |
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. More... | |
void | compute_CVT_func_grad (double &f, double *g) |
Computes the value and gradient of Lloyd's function (quantization noise power). More... | |
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. More... | |
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. More... | |
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. More... | |
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. More... | |
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. More... | |
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. More... | |
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. More... | |
virtual void | compute_RVC (index_t i, Mesh &M, Mesh &result, bool copy_symbolic_info=false)=0 |
Computes a restricted Voronoi cell. More... | |
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 (volumetric mode only). More... | |
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 mode only). More... | |
virtual void | set_check_SR (bool x)=0 |
Specifies whether the "radius of security" criterion should be enforced. | |
virtual void | set_exact_predicates (bool x)=0 |
Specifies whether exact predicates should be used. | |
virtual bool | exact_predicates () const =0 |
Tests whether exact predicates are used. | |
virtual void | create_threads ()=0 |
Partitions the mesh and creates local storage for multithreaded implementation. | |
virtual void | delete_threads ()=0 |
Deletes all the local storage associated with the threads. | |
virtual void | set_facets_range (index_t facets_begin, index_t facets_end)=0 |
Restricts surfacic computations to a part of the input mesh. More... | |
virtual void | set_tetrahedra_range (index_t tets_begin, index_t tets_end)=0 |
Restricts volumetric computations to a part of the input mesh. More... | |
const vec3 & | R3_embedding (index_t v) const |
Gets the mapping in R3 of a point. More... | |
Mesh * | mesh () |
Gets the input mesh. | |
virtual GEOGen::PointAllocator * | point_allocator ()=0 |
Gets the PointAllocator. More... | |
Public Member Functions inherited from GEO::Counted | |
void | ref () const |
Increments the reference count. More... | |
void | unref () const |
Decrements the reference count. More... | |
bool | is_shared () const |
Check if the object is shared. More... | |
int | nb_refs () const |
Gets the number of references that point to this object. More... | |
Static Public Member Functions | |
static RestrictedVoronoiDiagram * | create (Delaunay *delaunay, Mesh *mesh, const double *R3_embedding, index_t R3_embedding_stride) |
Creates a RestrictedVoronoiDiagram. More... | |
static RestrictedVoronoiDiagram * | create (Delaunay *delaunay, Mesh *mesh) |
Creates a RestrictedVoronoiDiagram. More... | |
static RestrictedVoronoiDiagram * | create (Delaunay *delaunay, Mesh *mesh, const vector< vec3 > &R3_embedding) |
Creates a RestrictedVoronoiDiagram. More... | |
Static Public Member Functions inherited from GEO::Counted | |
static void | ref (const Counted *counted) |
Increments the reference count. More... | |
static void | unref (const Counted *counted) |
Decrements the reference count. More... | |
Protected Member Functions | |
RestrictedVoronoiDiagram (Delaunay *delaunay, Mesh *mesh, const double *R3_embedding, index_t R3_embedding_stride) | |
This constructor is never called directly. More... | |
~RestrictedVoronoiDiagram () override | |
RestrictedVoronoiDiagram destructor. | |
Protected Member Functions inherited from GEO::Counted | |
Counted () | |
Creates a reference counted object. More... | |
virtual | ~Counted () |
Destroys a reference counted object. More... | |
Protected Attributes | |
coord_index_t | dimension_ |
Delaunay * | delaunay_ |
Mesh * | mesh_ |
const double * | R3_embedding_base_ |
index_t | R3_embedding_stride_ |
bool | has_weights_ |
Attribute< double > | vertex_weight_ |
signed_index_t | facets_begin_ |
signed_index_t | facets_end_ |
signed_index_t | tets_begin_ |
signed_index_t | tets_end_ |
bool | volumetric_ |
Computes a Restricted Voronoi Diagram (RVD).
A Restricted Voronoi Diagram is the intersection between a surface mesh and a Voronoi diagram, possibly embedded in high-dimensional space. This class is used (mostly) by CentroidalVoronoiTesselation (CVT), that distributes points uniformly over a surface. This class does all the geometric work for CVT.
Determines the operating mode of compute_RDT().
The flags can be combined with the 'bitwise or' (|) operator.
Enumerator | |
---|---|
RDT_SEEDS_ALWAYS | Always use Delaunay seeds as vertex geometry. |
RDT_MULTINERVE | If set, the dual of the connected components of the restricted Voronoi diagram is computed. |
RDT_RVC_CENTROIDS | If set, the vertices are generated at the centroids of the restricted Voronoi cells, instead of using the seeds. |
RDT_PREFER_SEEDS | If set, the seeds are used whenever possible, i.e. whenever a restricted Voronoi cell has a single connected component. |
RDT_SELECT_NEAREST | If set, then the algorithm selects among the seed and the restricted voronoi cell centroid the one that is nearest to the surface. Important: before using this mode, the surface mesh needs to be reordered with Morton order (see GEO::mesh_reorder). |
RDT_PROJECT_ON_SURFACE | If set, then all the vertices are projected onto the surface. Important: before using this mode, the surface mesh needs to be reordered with Morton order (see GEO::mesh_reorder). |
RDT_DONT_REPAIR | If set, the generated mesh is not repaired. As a result, triangles may be not properly oriented. |
|
protected |
This constructor is never called directly.
Use one of the three versions of create() instead.
|
inline |
Computes the centroids and masses of the restricted Voronoi cells.
Depending on the volumetric() flag, the Voronoi cells are restricted to the surface (facets of the mesh) or to the volume (tetrahedra of the mesh). This function is used by Lloyd relaxation in CentroidalVoronoiTesselation.
[out] | mg | (size = dimension()*delaunay()->nb_vertices()) : stores for each point the mass times the centroid of the restricted voronoi cell. |
[out] | m | (size = delaunay()->nb_vertices()) : stores for each point the mass of the restricted voronoi cell. |
|
pure virtual |
Computes the centroids and masses of the Voronoi cells restricted to the volume.
This function is used by Lloyd relaxation in CentroidalVoronoiTesselation.
[out] | mg | (size = dimension()*delaunay()->nb_vertices()) : stores for each point the mass times the centroid of the restricted voronoi cell. |
[out] | m | (size = delaunay()->nb_vertices()) : stores for each point the mass of the restricted voronoi cell. |
|
pure virtual |
Computes the centroids and masses of the Voronoi cells restricted to the surface.
This function is used by Lloyd relaxation in CentroidalVoronoiTesselation.
[out] | mg | (size = dimension()*delaunay()->nb_vertices()) : stores for each point the mass times the centroid of the restricted voronoi cell. |
[out] | m | (size = delaunay()->nb_vertices()) : stores for each point the mass of the restricted voronoi cell. |
|
inline |
Computes the value and gradient of Lloyd's function (quantization noise power).
Does computations either on the surface (triangles of the mesh) or in the volume (tetrahedra of the mesh), depending on the volumetric() flag. This function is used by Newton optimization in CentroidalVoronoiTesselation.
[out] | f | the computed value of the quantization noise power. |
[out] | g | (size = dimension()*delaunay()->nb_vertices()) : the gradient of the quantization noise power. |
|
pure virtual |
Computes the value and gradient of Lloyd's function (quantization noise power) in the volume.
This function is used by Newton optimization in CentroidalVoronoiTesselation.
[out] | f | the computed value of the quantization noise power. |
[out] | g | (size = dimension()*delaunay()->nb_vertices()) : the gradient of the quantization noise power. |
|
pure virtual |
Computes the value and gradient of Lloyd's function (quantization noise power) on the surface.
This function is used by Newton optimization in CentroidalVoronoiTesselation.
[out] | f | the computed value of the quantization noise power. |
[out] | g | (size = dimension()*delaunay()->nb_vertices()) : the gradient of the quantization noise power. |
|
inline |
Computes a random initial sampling in nD.
Depending on the value of the volumetric() flag, this functions samples either the triangles or the tetrahedra of the mesh. The coordinates of the computed points are stored in array p
which must be large enough to contain dimension()*nb_points
point coordinates.
[out] | p | stores the computed points. |
[in] | nb_points | number of points to compute |
[in] | verbose | if set, display message |
|
pure virtual |
Computes a random initial sampling of the volume in nD.
This function is used to initialize a CentroidalVoronoiTesselation. The coordinates of the computed points are stored in array p
which must be large enough to contain dimension()*nb_points
point coordinates.
[out] | p | stores the computed points |
[in] | nb_points | number of points to compute |
[in] | verbose | if set, display message |
|
pure virtual |
Computes a random initial sampling of the surface in nD.
This function is used to initialize a CentroidalVoronoiTesselation. The coordinates of the computed points are stored in array p
which must be large enough to contain dimension()*nb_points
point coordinates.
[out] | p | stores the computed points |
[in] | nb_points | number of points to compute |
[in] | verbose | if set, display message |
|
pure virtual |
Computes the value and gradient of an objective function over Voronoi cells decomposed into simplices.
This function is used by Newton optimization in CentroidalVoronoiTesselation.
[out] | f | the value of the objective function |
[out] | g | the gradient of the objective function |
[in,out] | F | the object that computes the objective function and its gradients over a simplex. The contribution of each simplex is added to the gradient referenced by F . |
void GEO::RestrictedVoronoiDiagram::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.
[out] | RDT | the computed restricted Delaunay triangulation |
[in] | mode | specifies how vertices geometry is generated in surfacic mode (seeds or restricted Voronoi cells centroids) |
[in] | seed_is_locked | if set, specifies which seed is locked (size = delaunay()->nb_vertices()). Locked seeds are not replaced with the restricted Voronoi cell centroid |
[in] | AABB | used if one of (RDT_RVC_PROJECT_ON_SURFACE, RDT_SELECT_NEAREST) is set in mode . If needed but not specified, then a temporary one is created. |
|
pure virtual |
Computes the restricted Delaunay triangulation.
[out] | simplices | the indices of all triangles vertices (or tetrahedra vertices in volumetric mode) |
[out] | embedding | the nD embedding of all vertices |
[in] | mode | specifies how vertices geometry is generated in surfacic mode (seeds or restricted Voronoi cells centroids) |
[in] | seed_is_locked | if set, specifies which seed is locked (size = delaunay()->nb_vertices()). Locked seeds are not replaced with the restricted Voronoi cell centroid. |
[in] | AABB | used if one of (RDT_RVC_PROJECT_ON_SURFACE, RDT_SELECT_NEAREST) is set in mode . If needed but not specified, then a temporary one is created. |
|
pure virtual |
Computes a restricted Voronoi cell.
A restricted Voronoi cell is the intersection between a Voronoi cell and a mesh.
[in] | i | the index of the Voronoi cell |
[in] | M | the mesh the Voronoi cell will be restricted to. All its vertices should be of degree 3 (i.e., incident to exactly three facets). In volumetric mode, the surfacic part of the mesh corresponds to the boundary of a volume. In surfacic mode, the mesh is a set of polygonal facets. |
[out] | result | on exit, contains the intersection of the Voronoi cell i and the mesh M |
[in] | copy_symbolic_info | if true, symbolic information is copied. An attribute "id" is attached to the facets. The value of id[f] is either 1 + the index of the Voronoi vertex that generated with i the bisector that created the facet, or -1-g if the facet was an original facet of mesh M , where g is the index of the original facet in M . |
|
pure virtual |
Computes the restricted Voronoi diagram and stores it in a mesh.
[out] | M | the computed restricted Voronoi diagram |
[in] | dim | if different from 0, use only the first dim coordinates |
[in] | cell_borders_only | in volumetric mode, computes only the surfacic borders of the volumetric cells (for visualization purpose) |
[in] | integration_simplices | in volumetric mode, if set, the generated tetrahedra systematically have the Voronoi seed as the first vertex. As a consequence, the mesh is not necessarily geometrically correct (it may have inverted elements), but it is algebraically correct (the sum of signed volumes corresponds the the total volume of each cell). |
|
inlinestatic |
Creates a RestrictedVoronoiDiagram.
The dimension is determined by mesh->dimension()
. The first three coordinates of each vertex are supposed to be x,y,z. (if it is not the case, use create(Delaunay*,Mesh*,const double*, index_t) or create(Delaunay*,Mesh*,const vector<vec3>&) instead).
[in] | delaunay | the Delaunay triangulation that defines the Voronoi diagram. |
[in] | mesh | the mesh that restricts the Voronoi diagram |
|
static |
Creates a RestrictedVoronoiDiagram.
The dimension is determined by mesh->dimension()
.
[in] | delaunay | the Delaunay triangulation that defines the Voronoi diagram. |
[in] | mesh | the mesh that restricts the Voronoi diagram |
[in] | R3_embedding | gives for each vertex its mapping in 3D space. |
[in] | R3_embedding_stride | gives the stride between two consecutive vertices in R3_embedding |
|
inlinestatic |
Creates a RestrictedVoronoiDiagram.
Use this function if the nD coordinates of each mesh vertex are completely unrelated with x,y,z. The dimension is determined by mesh->dimension()
.
[in] | delaunay | the Delaunay triangulation that defines the Voronoi diagram. |
[in] | mesh | the mesh that restricts the Voronoi diagram |
[in] | R3_embedding | gives for each vertex its mapping in 3D space. |
|
pure virtual |
Invokes a user callback for each intersection polygon of the restricted Voronoi diagram (surfacic mode only).
Each intersection polygon is defined as the intersection between a Voronoi cell and a triangle.
[in] | callback | the set of user callbacks, as an instance of a class derived from RVDPolygonCallback. |
[in] | symbolic | if true, generate symbolic information in the vertices |
[in] | connected_comp_priority | if true, generate polyhedron intersections associated with the same Voronoi seed in order. |
[in] | parallel | if true, tentatively parallelize computation. |
|
pure virtual |
Invokes a user callback for each intersection polyhedron of the restricted Voronoi diagram (volumetric mode only).
Each intersection polyhedron is defined as the intersection between a Voronoi cell and a tetrahedron.
[in] | callback | the set of user callbacks, as an instance of a class derived from RVDPolyhedronCallback. |
[in] | symbolic | if true, generate symbolic information in the vertices |
[in] | connected_comp_priority | if true, generate polyhedron intersections associated with the same Voronoi seed in order. |
[in] | parallel | if true, tentatively parallelize computation. |
|
pure virtual |
Gets the PointAllocator.
|
pure virtual |
Computes the projection of points onto the surface in nD space.
[in] | nb_points | number of points to projects |
[in] | points | array of the coordinates of the points to project. Must contain at least dimension()*nb_points coordinates. |
[out] | nearest | (size=nb_points) the computed projections mapped to 3D space. |
[in] | do_project | if set, the input points are moved and projected onto the surface, else only the 3D projections are computed, without changing the input. |
|
inline |
Computes the projection of points onto the surface in nD space.
[in] | nb_points | number of points to projects |
[in] | points | array of the coordinates of the points to project. Must contain at least dimension()*nb_points coordinates. |
[out] | nearest | the computed projections mapped to 3D space. |
[in] | do_project | if set, the input points are moved and projected onto the surface, else only the 3D projections are computed, without changing the input. |
|
inline |
Computes the projection of points onto the surface in nD space.
[in] | nb_points | number of points to projects |
[in] | points | array of the coordinates of the points to project. Must contain at least dimension()*nb_points coordinates. |
[out] | nearest | the computed projections mapped to 3D space. |
[in] | do_project | if set, the input points are moved and projected onto the surface, else only the 3D projections are computed, without changing the input. |
|
pure virtual |
Restricts surfacic computations to a part of the input mesh.
The part of the input mesh should be specified as a contiguous range of facet indices.
[in] | facets_begin | first facet in the range |
[in] | facets_end | one past last facet in the range |
|
pure virtual |
Restricts volumetric computations to a part of the input mesh.
The part of the input mesh should be specified as a contiguous range of tetrahedra indices.
[in] | tets_begin | first tetrahedron in the range |
[in] | tets_end | one past last tetrahedron in the range |
|
pure virtual |
Sets volumetric mode.
[in] | x | if true, volumetric mode is used, otherwise surfacic mode is used. |