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

#include <geogram/delaunay/parallel_delaunay_3d.h>

Inheritance diagram for GEO::ParallelDelaunay3d:

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 Mesh *	constraints () 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_t *	cell_to_v () const
	Gets a pointer to the cell-to-vertex incidence array. More...

const signed_index_t *	cell_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 Delaunay *	create (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_t *	cell_to_v_

const signed_index_t *	cell_to_cell_

vector< signed_index_t >	v_to_cell_

vector< signed_index_t >	cicl_

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 Mesh *	constraints_

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_

Related Functions inherited from GEO::Delaunay
typedef SmartPointer< Delaunay >	Delaunay_var
	Smart pointer that refers to a Delaunay object.

typedef Factory1< Delaunay, coord_index_t >	DelaunayFactory
	Delaunay Factory. More...

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 108 of file parallel_delaunay_3d.h.

Constructor & Destructor Documentation

◆ ParallelDelaunay3d()

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

Constructs a new ParallelDelaunay3d.

Parameters

[in]

dimension

dimension 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] p query 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] levels specifies 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_vertices	number of vertices
[in]	vertices	a 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:

geogram/delaunay/parallel_delaunay_3d.h

Public Member Functions

Friends

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ ParallelDelaunay3d()

Member Function Documentation

◆ nearest_vertex()

◆ set_BRIO_levels()

◆ set_vertices()