CellGPU: DelaunayLoc Class Reference

CellGPU 0.8.0

GPU-accelerated simulations of cells

A CPU-based class for locally constructing the Delaunay triangulation of part of a point set. More...

#include <DelaunayLoc.h>

Public Member Functions
	DelaunayLoc (std::vector< Dscalar2 > &points, gpubox &bx)
	constructor via a vector of Dscalar2 objects

	DelaunayLoc (std::vector< Dscalar > &points, gpubox &bx)
	constructor via a vector of scalars, {x1,y1,x2,y2,...}

void	setPoints (ArrayHandle< Dscalar2 > &points, int N)
	Set points by passing an ArrayHandle. More...

void	setPoints (GPUArray< Dscalar2 > &points)
	Set points via a GPUarray of Dscalar2's. More...

void	setPoints (std::vector< Dscalar2 > &points)
	Set points via a vector of Dscalar2's.

void	setPoints (std::vector< Dscalar > &points)
	Set the points via a vector of Dscalar's.

void	setBox (gpubox &bx)
	Set the box. More...

void	setBox (BoxPtr bx)

void	setCellSize (Dscalar cs)
	Set the box.

void	initialize (Dscalar csize)
	Set the cell size of the underlying grid. More...

void	getPolygon (int i, vector< int > &P0, vector< Dscalar2 > &P1)
	Find the indices of an enclosing polygon of vertex i. More...

void	getOneRingCandidate (int i, vector< int > &DTringIdx, vector< Dscalar2 > &DTring)
	Find a candidate set of possible points in the 1-ring of vertex i. More...

void	reduceOneRing (int i, vector< int > &DTringIdx, vector< Dscalar2 > &DTring)
	If the candidate 1-ring is large, try to reduce it before triangulating the whole thing. More...

void	triangulatePoint (int i, vector< int > &neighbors, DelaunayCell &DCell, bool timing=false)
	Return the neighbors of vertex i, sorted in CW order, along with a voronoi cell with calculated geometric properties. More...

void	getNeighbors (int i, vector< int > &neighbors)
	Just get the neighbors of vertex i, sorted in clockwise order. Calculated by the DelaunayNP class. More...

bool	getNeighborsCGAL (int i, vector< int > &neighbors)
	Just get the neighbors of vertex i, sorted in clockwise order. Calculated by the DelaunayCGAL class. More...

bool	testPointTriangulation (int i, vector< int > &neighbors, bool timing=false)
	Test whether the passed list of neighbors are the Delaunay neighbors of vertex i. More...

void	testTriangulation (vector< int > &ccs, vector< bool > &points, bool timing=false)
	Given a vector of circumcircle indices, label particles that are part of non-empty circumcircles. More...

virtual gpubox &	returnBox ()
	return the gpubox

void	printTriangulation (int maxprint)
	output part of triangulation to screen for debugging purposes More...

void	writeTriangulation (ofstream &outfile)
	write triangulation to text file More...

void	printPoint (int i)
	print the location of a point to the screen...for debugging.

void	testDel (int numpts, int tmax, double err, bool verbose)
	simple testing function More...

Public Attributes
int	cellschecked
	Collect some statistics about the functioning of the oneRing algorithms.

int	candidates

triangulation	DT
	A public variable that stores the triangulation as sets of (i,j,k) vertices when this class is used to generate the entire triangulation of the periodic point set.

Dscalar	polytiming
	Various aids for timing functions.

Dscalar	ringcandtiming

Dscalar	reducedtiming

Dscalar	tritiming

Dscalar	tritesttiming

Dscalar	geotiming

Dscalar	totaltiming

Protected Attributes
std::vector< Dscalar2 >	pts
	vector of points to triangulate

int	nV
	number of vertices

bool	triangulated
	has a triangulation been performed?

Dscalar	cellsize
	Sets how fine a grid to use in the cell list.

BoxPtr	Box
	A box to calculate relative distances in a periodic domain.

vector< int >	DTringIdxCGAL
	A vector of Delaunay neighbor indicies that can be repeatedly re-written.

vector< Dscalar2 >	DTringCGAL

cellListGPU	cList
	A cell list for speeding up the calculation of the candidate 1-ring.

Detailed Description

A CPU-based class for locally constructing the Delaunay triangulation of part of a point set.

One of the workhorse engines of the hybrid scheme, DelaunayLoc provides methods for finding the Delaunay neighbors of a given point by doing only local calculations. This is done by calculating the candidate 1-ring of vertex i – a set of points for which the set of Delaunay neighbors of i is a strict subset – by calculating points contained in the circumcircles of a set of points that form a bounding polygon around i. This can be used to completely construct a DT of the entire point set in the periodic domain (by calling either DelaunayNP or DelaunayCGAL to go from the candidate 1-ring to the actual list of neighbors), or to locally repair a part of a triangulation that has become non-Delaunay. This function operates strictly on the CPU

Member Function Documentation

◆ setPoints() [1/2]

void DelaunayLoc::setPoints	(	ArrayHandle< Dscalar2 > &	points,
		int	N
	)

Set points by passing an ArrayHandle.

Parameters

points	ArrayHandle of Dscalar2's that has already accessed a GPUArray containing the new desired points
N	the number of cells that the ArrayHandle knows about

References cellsize, ArrayHandle< T >::data, nV, pts, and triangulated.

Referenced by voronoiModelBase::resetDelLocPoints(), and setPoints().

◆ setPoints() [2/2]

void DelaunayLoc::setPoints ( GPUArray< Dscalar2 > & points )

Set points via a GPUarray of Dscalar2's.

Parameters

points a GPUArray of Dscalar2's with the new desired points

References cellsize, ArrayHandle< T >::data, GPUArray< T >::getNumElements(), access_location::host, nV, pts, access_mode::read, setPoints(), and triangulated.

◆ setBox()

void DelaunayLoc::setBox ( gpubox & bx )

Set the box.

Parameters

bx	a gpubox that the DelaunayLoc object should use in internal computations

References Box.

◆ initialize()

void DelaunayLoc::initialize ( Dscalar csize )

Set the cell size of the underlying grid.

Initialize various things, based on a given cell size for the underlying grid

Parameters

csize the size of the grid boxes to use for the internal cell list

Precondition: the internal box is already set, and the points are already set

Postcondition: points are sorted into cells

Referenced by voronoiModelBase::resetDelLocPoints().

◆ getPolygon()

void DelaunayLoc::getPolygon	(	int	i,
		vector< int > &	P0,
		vector< Dscalar2 > &	P1
	)

Find the indices of an enclosing polygon of vertex i.

This routine uses the cell list to look for particles that form a quadrilateral surrounding cell i. The search proceeds by looking in concentric shells of nearby cells until a particle from every quadrant around cell i is found.

Parameters

i	the index of the cell in question
P0	a reference to the indices of cells that form the enclosing polygon
P1	a reference to the positions of the cells forming the enclosing polygon relative to cell i

Referenced by getOneRingCandidate().

◆ getOneRingCandidate()

void DelaunayLoc::getOneRingCandidate	(	int	i,
		vector< int > &	DTringIdx,
		vector< Dscalar2 > &	DTring
	)

Find a candidate set of possible points in the 1-ring of vertex i.

The main workhorse of the class. First find a set of cells that forms a polygon around cell i, then find all particles in the circumcircles formed by cell i and any two consecutive members of the polygon

Parameters

i	the cell to get the candidate 1-ring of
DTringIdx	a reference to a vector of cell indices that will make up the candidate 1-ring
DTring	a reference to a vector of relative cell positions that will make up the candidate 1-ring

Postcondition: DTringIdx and DTring contain cells, of which the Delaunay neighbors of cell i are a strict subset

References getPolygon().

Referenced by getNeighbors(), getNeighborsCGAL(), and triangulatePoint().

◆ reduceOneRing()

void DelaunayLoc::reduceOneRing	(	int	i,
		vector< int > &	DTringIdx,
		vector< Dscalar2 > &	DTring
	)

If the candidate 1-ring is large, try to reduce it before triangulating the whole thing.

A simple algorithm to try to reduce the size of the candidate 1-ring. This exploits the fact that getPolygon doesn't try very hard to find a "good" enclosing polygon for cell i, choosing a different set of cells to form the polygon might lead to a smaller candidate 1-ring. This then reduces the computational cost of going from the candidate 1-ring to the true set of Delaunay neighbors. This matters a lot for analyzing random point sets, but if the cells are pretty regular this routine will almost never be called.

Parameters

i	the cell to get the candidate 1-ring of
DTringIdx	a reference to a vector of cell indices that will make up the candidate 1-ring
DTring	a reference to a vector of relative cell positions that will make up the candidate 1-ring subset

◆ triangulatePoint()

void DelaunayLoc::triangulatePoint	(	int	i,
		vector< int > &	neighbors,
		DelaunayCell &	DCell,
		bool	timing = `false`
	)

Return the neighbors of vertex i, sorted in CW order, along with a voronoi cell with calculated geometric properties.

Similar to getNeighbors above, this uses the DelaunayNP class to ge the Delaunay neighbors of cell i, and also calculates geometric properties of the Voronoi cell that results. Useful for debugging and testing. its true set of delaunay neighbors.

Parameters

i	the cell in question
neighbors	a reference to a vector of cell indices that are the Delaunay neighbors of i
DCell	a reference to the Voronoi cell of point i, with some geometric propertie of it calculated.
timing	keep track of some timing info if true

Postcondition: neighbors is sorted so that the indices refer to the Delaunay neighbors in CCW order

References DelaunayNP::DT, triangulation::getNeighbors(), getOneRingCandidate(), DelaunayNP::mapi, DelaunayCell::setSize(), and DelaunayNP::triangulate().

◆ getNeighbors()

void DelaunayLoc::getNeighbors	(	int	i,
		vector< int > &	neighbors
	)

Just get the neighbors of vertex i, sorted in clockwise order. Calculated by the DelaunayNP class.

If CGAL is unavailable, call the DelaunayNP class to go from the candidate 1-ring of cell i to its true set of delaunay neighbors.

Parameters

i	the cell in question
neighbors	a reference to a vector of cell indices that are the Delaunay neighbors of i

Postcondition: neighbors is sorted so that the indices refer to the Delaunay neighbors in CCW order

References DelaunayNP::DT, triangulation::getNeighbors(), getOneRingCandidate(), DelaunayNP::mapi, DelaunayCell::setSize(), and DelaunayNP::triangulate().

Referenced by voronoiModelBase::fullTriangulation().

◆ getNeighborsCGAL()

bool DelaunayLoc::getNeighborsCGAL	(	int	i,
		vector< int > &	neighbors
	)

Just get the neighbors of vertex i, sorted in clockwise order. Calculated by the DelaunayCGAL class.

call the CGAL library (for non-periodic 2D Delaunay triangulations) through the DelaunayCGAL class to go from the candidate 1-ring of cell i to its true set of delaunay neighbors.

Parameters

i	the cell in question
neighbors	a reference to a vector of cell indices that are the Delaunay neighbors of i

Postcondition: neighbors is sorted so that the indices refer to the Delaunay neighbors in CCW order

References DTringCGAL, DTringIdxCGAL, and getOneRingCandidate().

◆ testPointTriangulation()

bool DelaunayLoc::testPointTriangulation	(	int	i,
		vector< int > &	neighbors,
		bool	timing = `false`
	)

Test whether the passed list of neighbors are the Delaunay neighbors of vertex i.

Given a cell index and a propsed set of neighbors in CCW order, see if all circumcenters are empty.

Parameters

i	the target cell
neighbors	the set of proposed neighbors
timing	keep track of some timing info

Referenced by voronoiModelBase::testTriangulationCPU().

◆ testTriangulation()

void DelaunayLoc::testTriangulation	(	vector< int > &	ccs,
		vector< bool > &	points,
		bool	timing = `false`
	)

Given a vector of circumcircle indices, label particles that are part of non-empty circumcircles.

Test all circumcircles to see if they are empty, and flag particles for retriangulation if needed.

Parameters

ccs	a vector of length (3*numberOfCircumcircles)
points	a vector of bools, where if true that point needs its neighbors re-triangulated
timing	keep track of timing info if true

◆ printTriangulation()

void DelaunayLoc::printTriangulation ( int maxprint )

output part of triangulation to screen for debugging purposes

A utility function for testing and debugging

Parameters

maxprint the maximum number of points to print info for

References DT, triangulation::nTriangles, nV, pts, triangulation::triangles, and triangulated.

◆ writeTriangulation()

void DelaunayLoc::writeTriangulation ( ofstream & outfile )

write triangulation to text file

A utility function for testing and debugging

Parameters

outfile the ofstream to write triangulation data to

References DT, triangulation::nEdges, triangulation::nTriangles, nV, pts, and triangulation::triangles.

◆ testDel()

void DelaunayLoc::testDel	(	int	numpts,
		int	tmax,
		double	err,
		bool	verbose
	)

simple testing function

A utility function to test and time several routines in this class

Parameters

numpts	The number of points for which to perform tests
tmax	the number of times each function will be called, for averaging timing info
err	detect changes by moving points by some amount
verbose	if true output even more timing info

References nV.

Member Data Documentation

◆ DTringCGAL

vector<Dscalar2> DelaunayLoc::DTringCGAL

protected

A vector of Delaunay neighbors that can be repeatedly re-written

Referenced by getNeighborsCGAL().

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

Public Member Functions

Public Attributes

Protected Attributes

Detailed Description

Member Function Documentation

◆ setPoints() [1/2]

◆ setPoints() [2/2]

◆ setBox()

◆ initialize()

◆ getPolygon()

◆ getOneRingCandidate()

◆ reduceOneRing()

◆ triangulatePoint()

◆ getNeighbors()

◆ getNeighborsCGAL()

◆ testPointTriangulation()

◆ testTriangulation()

◆ printTriangulation()

◆ writeTriangulation()

◆ testDel()

Member Data Documentation

◆ DTringCGAL