Geogram  Version 1.9.1
A programming library of geometric algorithms
GEO::ParallelDelaunay3d Class Reference

Multithreaded implementation of Delaunay in 3d. More...

#include <geogram/delaunay/parallel_delaunay_3d.h>

Inheritance diagram for GEO::ParallelDelaunay3d:
GEO::Delaunay GEO::Counted

Public Member Functions

 ParallelDelaunay3d (coord_index_t dimension=3)
 Constructs a new ParallelDelaunay3d. More...
 
void set_vertices (index_t nb_vertices, const double *vertices) override
 Sets the vertices of this Delaunay, and recomputes the cells. More...
 
index_t nearest_vertex (const double *p) const override
 Computes the nearest vertex from a query point. More...
 
void set_BRIO_levels (const vector< index_t > &levels) override
 Specifies the bounds of each level to be used when hierarchic ordering is specified from outside. More...
 
- Public Member Functions inherited from GEO::Delaunay
coord_index_t dimension () const
 Gets the dimension of this Delaunay. More...
 
index_t cell_size () const
 Gets the number of vertices in each cell. More...
 
void set_reorder (bool x)
 Specifies whether vertices should be reordered. More...
 
const double * vertices_ptr () const
 Gets a pointer to the array of vertices. More...
 
const double * vertex_ptr (index_t i) const
 Gets a pointer to a vertex by its global index. More...
 
index_t nb_vertices () const
 Gets the number of vertices. More...
 
virtual bool supports_constraints () const
 Tests whether constraints are supported by this Delaunay. More...
 
virtual void set_constraints (const Mesh *mesh)
 Defines the constraints. More...
 
void set_refine (bool x)
 Specifies whether the mesh should be refined. More...
 
bool get_refine () const
 Tests whether mesh refinement is selected. More...
 
void set_quality (double qual)
 Specifies the desired quality for mesh elements when refinement is enabled (. More...
 
const Meshconstraints () const
 Gets the constraints. More...
 
index_t nb_cells () const
 Gets the number of cells. More...
 
index_t nb_finite_cells () const
 Gets the number of finite cells. More...
 
const signed_index_tcell_to_v () const
 Gets a pointer to the cell-to-vertex incidence array. More...
 
const signed_index_tcell_to_cell () const
 Gets a pointer to the cell-to-cell adjacency array. More...
 
signed_index_t cell_vertex (index_t c, index_t lv) const
 Gets a vertex index by cell index and local vertex index. More...
 
signed_index_t cell_adjacent (index_t c, index_t lf) const
 Gets an adjacent cell index by cell index and local facet index. More...
 
bool cell_is_infinite (index_t c) const
 Tests whether a cell is infinite. More...
 
bool cell_is_finite (index_t c) const
 Tests whether a cell is finite. More...
 
index_t index (index_t c, signed_index_t v) const
 Retrieves a local vertex index from cell index and global vertex index. More...
 
index_t adjacent_index (index_t c1, index_t c2) const
 Retrieves a local facet index from two adacent cell global indices. More...
 
signed_index_t vertex_cell (index_t v) const
 Gets an incident cell index by a vertex index. More...
 
signed_index_t next_around_vertex (index_t c, index_t lv) const
 Traverses the list of cells incident to a vertex. More...
 
void get_neighbors (index_t v, vector< index_t > &neighbors) const
 Gets the one-ring neighbors of vertex v. More...
 
void save_histogram (std::ostream &out) const
 Saves the histogram of vertex degree (can be visualized with gnuplot). More...
 
bool stores_neighbors () const
 Tests whether neighbors are stored. More...
 
void set_stores_neighbors (bool x)
 Specifies whether neighbors should be stored. More...
 
bool stores_cicl () const
 Tests whether incident tetrahedra lists are stored. More...
 
void set_stores_cicl (bool x)
 Specifies whether incident tetrahedra lists should be stored. More...
 
bool keeps_infinite () const
 Tests whether infinite elements are kept. More...
 
void set_keeps_infinite (bool x)
 Sets whether infinite elements should be kept. More...
 
bool thread_safe () const
 Tests whether thread-safe mode is active. More...
 
void set_thread_safe (bool x)
 Specifies whether thread-safe mode should be used. More...
 
void set_default_nb_neighbors (index_t x)
 Sets the default number of stored neighbors. More...
 
index_t default_nb_neighbors () const
 Gets the default number of stored neighbors. More...
 
void clear_neighbors ()
 Frees all memory used for neighbors storage.
 
void set_keep_regions (bool x)
 Specifies whether all internal regions should be kept. More...
 
virtual index_t region (index_t t) const
 Gets the region id associated with a tetrahedron. More...
 
virtual void store_neighbors_CB (index_t i)
 Stores the neighbors of a vertex. 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...
 

Friends

class Delaunay3dThread
 

Additional Inherited Members

- Static Public Member Functions inherited from GEO::Delaunay
static Delaunaycreate (coord_index_t dim, const std::string &name="default")
 Creates a Delaunay triangulation of the specified dimension. More...
 
static void initialize ()
 This function needs to be called once before using the Delaunay class. 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 inherited from GEO::Delaunay
 Delaunay (coord_index_t dimension)
 Creates a new Delaunay triangulation. More...
 
 ~Delaunay () override
 Delaunay destructor.
 
virtual void get_neighbors_internal (index_t v, vector< index_t > &neighbors) const
 Internal implementation for get_neighbors (with vector). More...
 
virtual void set_arrays (index_t nb_cells, const signed_index_t *cell_to_v, const signed_index_t *cell_to_cell)
 Sets the arrays that represent the combinatorics of this Delaunay. More...
 
virtual void update_v_to_cell ()
 Stores for each vertex v a cell incident to v.
 
virtual void update_cicl ()
 Updates the circular incident cell lists. More...
 
virtual void update_neighbors ()
 Computes the stored neighbor lists.
 
void set_next_around_vertex (index_t c1, index_t lv, index_t c2)
 Sets the circular incident edge list. More...
 
void set_dimension (coord_index_t dim)
 Sets the dimension of this Delaunay. More...
 
- Protected Member Functions inherited from GEO::Counted
 Counted ()
 Creates a reference counted object. More...
 
virtual ~Counted ()
 Destroys a reference counted object. More...
 
- Protected Attributes inherited from GEO::Delaunay
coord_index_t dimension_
 
index_t vertex_stride_
 
index_t cell_size_
 
index_t cell_v_stride_
 
index_t cell_neigh_stride_
 
const double * vertices_
 
index_t nb_vertices_
 
index_t nb_cells_
 
const signed_index_tcell_to_v_
 
const signed_index_tcell_to_cell_
 
vector< signed_index_tv_to_cell_
 
vector< signed_index_tcicl_
 
bool is_locked_
 
PackedArrays neighbors_
 
bool store_neighbors_
 
index_t default_nb_neighbors_
 
bool do_reorder_
 If true, uses BRIO reordering (in some implementations)
 
const Meshconstraints_
 
bool refine_
 
double quality_
 
bool store_cicl_
 It true, circular incident tet lists are stored.
 
bool keep_infinite_
 If true, infinite vertex and infinite simplices are kept.
 
index_t nb_finite_cells_
 If keep_infinite_ is true, then finite cells are 0..nb_finite_cells_-1 and infinite cells are nb_finite_cells_ ... nb_cells_.
 
bool keep_regions_
 

Detailed Description

Multithreaded implementation of Delaunay in 3d.

This class is based on ideas and a prototype implementation by Alain Filbois. This class also uses concepts inspired by two triangulation softwares, CGAL and tetgen, described in the following references. This package follows the idea used in CGAL of traversing the cavity from inside, since it traverses less tetrahedra than when traversing from outside.

  • Jean-Daniel Boissonnat, Olivier Devillers, Monique Teillaud, and Mariette Yvinec. Triangulations in CGAL. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 11–18, 2000.
  • Hang Si, Constrained Delaunay tetrahedral mesh generation and refinement. Finite elements in Analysis and Design, 46 (1-2):33–46, 2010.

Note that the algorithm here does not support vertex deletion nor degenerate input with all coplanar or all colinear points (use CGAL instead if you have these requirements).

The core algorithm used in both this code, CGAL and tetgen was independently and simultaneously discovered by Bowyer and Watson:

  • Adrian Bowyer, "Computing Dirichlet tessellations", Comput. J., vol. 24, no 2, 1981, p. 162-166
  • David F. Watson, "Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes", Comput. J., vol. 24, no 2, 1981, p. 167-172

The spatial reordering method, that dramatically increases the performances, also used in this code, CGAL and tetgen was introduced in the following references. The second one is a smart implementation based on the std::nth_element() function of the STL, that inspired the compute_BRIO_ordering() function of this package.

  • Nina Amenta, Sunghee Choi and Gunter Rote, "Incremental constructions con brio", ACM Symposium on Computational Geometry 2003.
  • Christophe Delage and Olivier Devillers. Spatial Sorting. In CGAL User and Reference Manual. CGAL Editorial Board, 3.9 edition, 2011

The locate() function is based on the following two references. The first one randomizes the choice of the next tetrahedron. The second one uses an inexact locate() function to initialize the exact one (it is called "structural filtering"). The first idea is used in both CGAL and tetgen, and the second one is used in CGAL.

  • Walking in a triangulation, O Devillers, S Pion, M Teillaud 17th Annual Symposium on Computational geometry, 106-114
  • Stefan Funke , Kurt Mehlhorn and Stefan Naher, "Structural filtering, a paradigm for efficient and exact geometric programs", 1999

Definition at line 106 of file parallel_delaunay_3d.h.

Constructor & Destructor Documentation

◆ ParallelDelaunay3d()

GEO::ParallelDelaunay3d::ParallelDelaunay3d ( coord_index_t  dimension = 3)

Constructs a new ParallelDelaunay3d.

Parameters
[in]dimensiondimension of the triangulation (3 or 4). If dimension = 4, this creates a regular triangulation (dual of a power diagram). In this case:
  • the input points are 4d points, were the fourth coordinate of point \( i \) is \( \sqrt{W - w_i} \) where \( W \) is the maximum of the weights of all the points and \d$ w_i $ is the weight associated with vertex \( i \).
  • the constructed combinatorics is a tetrahedralized volume (3d and not 4d although dimension() returns 4). This tetrahedralized volume corresponds to the regular triangulation of the weighted points.

Member Function Documentation

◆ nearest_vertex()

index_t GEO::ParallelDelaunay3d::nearest_vertex ( const double *  p) const
overridevirtual

Computes the nearest vertex from a query point.

Parameters
[in]pquery point
Returns
the index of the nearest vertex

Reimplemented from GEO::Delaunay.

◆ set_BRIO_levels()

void GEO::ParallelDelaunay3d::set_BRIO_levels ( const vector< index_t > &  levels)
overridevirtual

Specifies the bounds of each level to be used when hierarchic ordering is specified from outside.

This function is used by some implementation when set_reorder(false) was called.

Parameters
[in]levelsspecifies the bounds of each level used by the hierarchical index. First level has indices between levels[0] ... levels[1].

Reimplemented from GEO::Delaunay.

◆ set_vertices()

void GEO::ParallelDelaunay3d::set_vertices ( index_t  nb_vertices,
const double *  vertices 
)
overridevirtual

Sets the vertices of this Delaunay, and recomputes the cells.

Parameters
[in]nb_verticesnumber of vertices
[in]verticesa pointer to the coordinates of the vertices, as a contiguous array of doubles

Reimplemented from GEO::Delaunay.


The documentation for this class was generated from the following file: