========================================================================= The templated, core Voronoi class. More...

#include <vtkVoronoiCore2D.h>

Inheritance diagram for vtkVoronoiCore2D< TCompositor, TClassifier >:

Collaboration diagram for vtkVoronoiCore2D< TCompositor, TClassifier >:

Classes
struct	ProduceWheelsAndSpokes
	Produce the global adjacency graph / wheels and spokes data structure. More...

struct	TopologicalMerge
	Functor class used to topologically merge (nearly) coincident points. More...

Public Member Functions
vtkVoronoiAdjacencyGraph &	GetAdjacencyGraph ()
	Obtain the adjacency graph (wheel & spokes data structure).

	vtkVoronoiCore2D (vtkAlgorithm filter, vtkVoronoiBatchManager &batcher, vtkStaticPointLocator2D loc, vtkPoints inPts, double padding, vtkIdType maxClips, bool validate, double pruneTol, TCompositor comp, TClassifier *c)
	Constructor.

vtkIdType	GetNumberOfPoints ()
	Convenience methods to retrieve the number of input points, and the raw double* points array.

const double *	GetPoints ()


int	GetNumberOfThreads ()
	Access the local thread data produced by execution of the filter.

vtkVoronoi2DLocalData< TCompositor, TClassifier > *	GetThreadData (int threadNum)
	Access the local thread data produced by execution of the filter.


int	GetMaximumNumberOfPoints ()
	Obtain information about the execution of the Voronoi algorithm.

int	GetNumberOfPrunes ()
	Obtain information about the execution of the Voronoi algorithm.


void	Initialize ()
	Core vtkSMPTools methods to process tiles in parallel, and produce thread local output data.

void	operator() (vtkIdType batchId, vtkIdType endBatchId)
	Core vtkSMPTools methods to process tiles in parallel, and produce thread local output data.

void	Reduce ()
	Core vtkSMPTools methods to process tiles in parallel, and produce thread local output data.

Static Public Member Functions
static std::unique_ptr< vtkVoronoiCore2D< TCompositor, TClassifier > >	Execute (vtkAlgorithm filter, unsigned int batchSize, vtkStaticPointLocator2D loc, vtkPoints inPts, double padding, vtkIdType maxClips, bool validate, double pruneTol, TCompositor comp, TClassifier *cl)
	A factory method to conveniently instantiate and execute the algorithm.

Public Attributes
TCompositor	Compositor
	The compositor enables this vtkVoronoiCore2D templated class to be used in different applications.

TClassifier	Classifier
	This templated class is used to extend the API of this vtkVoronoiCore2D class, to implement the spoke classification process, to clone copies in multiple threads, and to initialize the classification instances.

vtkVoronoiBatchManager	Batcher
	Controls processing of batches of generating points.

ThreadMapType< TCompositor, TClassifier >	ThreadMap

vtkVoronoiAdjacencyGraph	Graph
	This is used to create the spokes and wheels adjacency graph used to validate the tessellation and produce a Delaunay triangulation.

vtkAlgorithm *	Filter
	Used for controlling filter abort and accessing filter information.

Detailed Description

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>
class vtkVoronoiCore2D< TCompositor, TClassifier >

========================================================================= The templated, core Voronoi class.

provide core 2D Voronoi tessellation capabilities

It is a lightweight supporting class (i.e., not a subclass of vtkObject) meant to be used by specialized algorithms requiring Voronoi and/or Delaunay capabilities.

Note: the template argument TCompositor is used to control what information is extracted during tessellation. Different using filters will define and extract information relevant to their application needs. This is accomplished by defining different compositing classes. TClassifier is used to classify the spokes connecting neighborhood points, which to the the dual property, classifies the tile edges.

The Voronoi tessellation is a common computational tool used in a variety of applications ranging from triangulating points, mesh generation, surface reconstruction, materials analysis, and contouring (surface nets). It can also be the basis for computing its dual construct, the Delaunay triangulation, also used in wide-ranging applications with significant impacts. This templated class provides core 2D Voronoi tessellation capabilities, including implementation of fast parallel algorithms, which can be used by other classes to create specialized Voronoi-based algorithms.

The Voronoi tessellation is a tiling of space, where each Voronoi n-dimensional tile (in 2D, a convex polygon) represents the region nearest to one of the input points. Under the hood, the vtkVoronoiCore2D class depends on the vtkVoronoiTile class to construct tiles. The vtkVoronoiCore2D provides a framework for parallel, SMP shared memory algorithms, which can be specialized to meet the needs of algorithms requiring Voronoi and/or Delaunay-based capabilities. Specialization of the algorithm is via a TCompositor template argument, which controls what information is extracted from each tile as it is processed, and how the information is combined (during a compositing process) to produce output. A second template parameter, TClassifier, is used to classify the spokes, i.e., connections between neighboring points. (Because of the dual nature of the Voronoi and Delaunay constructs, these spokes correspond to the tile edges of edge adjacent polygons.)

Publications are in preparation to describe the algorithm. Conceptually, the algorithm is meshless, meaning that each input point and its associated tile is processed independently. However, methods are provided to transform the output into a fully-connected, valid, conformal mesh if required. To summarize: in parallel, each (generating) input point is associated with an initial Voronoi tile, which is simply the bounding box of the input point set. A spatial locator is then used to identify neighboring points: each neighbor in turn generates a clipping plane positioned halfway between the generating point and the neighboring point, and orthogonal to the line connecting them. Clips are performed by evaluationg the vertices of the convex Voronoi tile as being on either side (inside,outside) of the clip line. If an intersection with the Voronoi tile is found, the portion of the tile "outside" the clip plane is discarded, resulting in a new convex, Voronoi tile. As each clip occurs, the Voronoi "Flower" error metric (the union of Delunay spheres) is compared to the extent of the region containing the neighboring clip points. The clip region (along with the points contained in it) is grown by careful expansion, When the Voronoi circumflower is contained within the clip region, the algorithm terminates and the Voronoi tile is output. Once complete, it is possible to construct the Delaunay triangulation from the Voronoi tessellation. Note that topological and geometric information can be used to generate a valid triangulation (e.g., merging coincident points and validating topology).

This class can also construct a Voronoi adjacency graph, composed of edges (the spokes) that connect each Voronoi tile generating point (the wheels) with their edge neighbors. The adjacency graph is a powerful data representation that captures proximal neighborhood information. It has many practical applications such as shortest path computation.

An implementation note: this class is implemented using a parallel algorithm. The output is invariant no matter what order the the threads execute, i.e., the construction of geometric primitives (Voronoi cells, adjacency graphs, etc.) is identical no matter the number of threads used, or execution order. Also, note the correspondance between input generating point of ptId and tileId, ptId produces tiles of tileId, where ptId == tileId. This means for debugging purposes, picking output primitives with POINT_IDS enabled provides a means to select the original generating points.

This class is templated, enabling specialized capabilities depending on the using algorithm / filter. Using templating, it is possible to extract different information from each Voronoi tile as it is constructed, compositing this information later to produce different types of output.

Warning: Coincident input points are discarded. The Voronoi tessellation requires unique input points.; This approach implements an embarrassingly parallel, meshless algorithm. At the core of the algorithm a locator is used to determine points close to a specified position. Currently, a vtkStaticPointLocator2D is used because it is both threaded (when constructed) and supports thread-safe queries. While other locators could be used in principal, they must support thread-safe operations. This is done by defining and implementing an iterator that enables traversal of neighborhood points surrounding each generating point.; This class has been threaded with vtkSMPTools. Using TBB or other non-sequential type (set in the CMake variable VTK_SMP_IMPLEMENTATION_TYPE) may improve performance significantly. For example, in recent benchmarks using a 48-thread desktop, one million points can be processed in well under one second elapsed time.

See also: vtkVoronoiTile vtkVoronoiFlower2D vtkVoronoiHull vtkVoronoi3D vtkGeneralizedSurfaceNets3D

Tests:: vtkVoronoiCore2D (Tests)

Definition at line 246 of file vtkVoronoiCore2D.h.

Constructor & Destructor Documentation

◆ vtkVoronoiCore2D()

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

vtkVoronoiCore2D< TCompositor, TClassifier >::vtkVoronoiCore2D	(	vtkAlgorithm *	filter,
		vtkVoronoiBatchManager &	batcher,
		vtkStaticPointLocator2D *	loc,
		vtkPoints *	inPts,
		double	padding,
		vtkIdType	maxClips,
		bool	validate,
		double	pruneTol,
		TCompositor *	comp,
		TClassifier *	c )

Constructor.

This is typically not directly invoked by the user. The Execute() method is preferred.

Member Function Documentation

◆ Execute()

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

static std::unique_ptr< vtkVoronoiCore2D< TCompositor, TClassifier > > vtkVoronoiCore2D< TCompositor, TClassifier >::Execute	(	vtkAlgorithm *	filter,
		unsigned int	batchSize,
		vtkStaticPointLocator2D *	loc,
		vtkPoints *	inPts,
		double	padding,
		vtkIdType	maxClips,
		bool	validate,
		double	pruneTol,
		TCompositor *	comp,
		TClassifier *	cl )

static

A factory method to conveniently instantiate and execute the algorithm.

This class should be executed using this Execute() method. It returns a unique pointer to an instance of the VoronoiCore2D algorithm. After execution, methods on the instance can be invoked to retrieve relevant information. Note also that a Voronoi compositor should also be provided to this Execute() method. It will contain output as well. Input to the method includes the input (double) points, a prebuilt static point locator, the initial tile bounds padding, a limit on the number of clips each tile can perform, and an optional VTK filter (for controlling execution abort). An optional (non-null) compositor and/or classifier can be provided which is used to initialize the compositors and/or classifiers in the various threads (for example, providing region ids). Finally, methods to control degenerate edges (i.e., validation / spoke pruning and tolerance) are provided.

◆ GetNumberOfThreads()

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

int vtkVoronoiCore2D< TCompositor, TClassifier >::GetNumberOfThreads ( )

inline

Access the local thread data produced by execution of the filter.

This includes the compositing data. The data is only available after the Execute() method has been invoked.

Definition at line 275 of file vtkVoronoiCore2D.h.

◆ GetThreadData()

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

vtkVoronoi2DLocalData< TCompositor, TClassifier > * vtkVoronoiCore2D< TCompositor, TClassifier >::GetThreadData ( int threadNum )

inline

Access the local thread data produced by execution of the filter.

This includes the compositing data. The data is only available after the Execute() method has been invoked.

Definition at line 276 of file vtkVoronoiCore2D.h.

◆ GetMaximumNumberOfPoints()

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

int vtkVoronoiCore2D< TCompositor, TClassifier >::GetMaximumNumberOfPoints ( )

inline

Obtain information about the execution of the Voronoi algorithm.

This includes the maximum number of edges found in any tile; the maximum number of points found in any tile; and the number of prunes performed to remove degeneracies.

Definition at line 289 of file vtkVoronoiCore2D.h.

◆ GetNumberOfPrunes()

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

int vtkVoronoiCore2D< TCompositor, TClassifier >::GetNumberOfPrunes ( )

inline

Obtain information about the execution of the Voronoi algorithm.

This includes the maximum number of edges found in any tile; the maximum number of points found in any tile; and the number of prunes performed to remove degeneracies.

Definition at line 290 of file vtkVoronoiCore2D.h.

◆ GetAdjacencyGraph()

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

vtkVoronoiAdjacencyGraph & vtkVoronoiCore2D< TCompositor, TClassifier >::GetAdjacencyGraph ( )

inline

Obtain the adjacency graph (wheel & spokes data structure).

This is constructed during algorithm execution.

Definition at line 297 of file vtkVoronoiCore2D.h.

◆ Initialize()

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

void vtkVoronoiCore2D< TCompositor, TClassifier >::Initialize ( )

Core vtkSMPTools methods to process tiles in parallel, and produce thread local output data.

Other compositing data is captured as well. Note that the threading occurs over batches of points. (Note: this is left public for access by vtkSMPTools. These are generally not invoked directly by the user.)

◆ operator()()

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

void vtkVoronoiCore2D< TCompositor, TClassifier >::operator()	(	vtkIdType	batchId,
		vtkIdType	endBatchId )

Core vtkSMPTools methods to process tiles in parallel, and produce thread local output data.

Other compositing data is captured as well. Note that the threading occurs over batches of points. (Note: this is left public for access by vtkSMPTools. These are generally not invoked directly by the user.)

◆ Reduce()

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

void vtkVoronoiCore2D< TCompositor, TClassifier >::Reduce ( )

Core vtkSMPTools methods to process tiles in parallel, and produce thread local output data.

Other compositing data is captured as well. Note that the threading occurs over batches of points. (Note: this is left public for access by vtkSMPTools. These are generally not invoked directly by the user.)

◆ GetNumberOfPoints()

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

vtkIdType vtkVoronoiCore2D< TCompositor, TClassifier >::GetNumberOfPoints ( )

inline

Convenience methods to retrieve the number of input points, and the raw double* points array.

Invoke this only after execution.

Definition at line 354 of file vtkVoronoiCore2D.h.

◆ GetPoints()

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

const double * vtkVoronoiCore2D< TCompositor, TClassifier >::GetPoints ( )

inline

Definition at line 355 of file vtkVoronoiCore2D.h.

Member Data Documentation

◆ Compositor

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

TCompositor vtkVoronoiCore2D< TCompositor, TClassifier >::Compositor

The compositor enables this vtkVoronoiCore2D templated class to be used in different applications.

It supports parallel gather/compute of specified information on a tile-by-tile basis, which can then combined/composited to produce output. Users of this class must define their own compositor.

Definition at line 327 of file vtkVoronoiCore2D.h.

◆ Classifier

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

TClassifier vtkVoronoiCore2D< TCompositor, TClassifier >::Classifier

This templated class is used to extend the API of this vtkVoronoiCore2D class, to implement the spoke classification process, to clone copies in multiple threads, and to initialize the classification instances.

Definition at line 334 of file vtkVoronoiCore2D.h.

◆ Batcher

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

vtkVoronoiBatchManager vtkVoronoiCore2D< TCompositor, TClassifier >::Batcher

Controls processing of batches of generating points.

Thread local data is is available after generating the tiles.

Definition at line 340 of file vtkVoronoiCore2D.h.

◆ ThreadMap

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

ThreadMapType<TCompositor, TClassifier> vtkVoronoiCore2D< TCompositor, TClassifier >::ThreadMap

Definition at line 341 of file vtkVoronoiCore2D.h.

◆ Graph

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

vtkVoronoiAdjacencyGraph vtkVoronoiCore2D< TCompositor, TClassifier >::Graph

This is used to create the spokes and wheels adjacency graph used to validate the tessellation and produce a Delaunay triangulation.

Note that if an "empty" classifier is used, the adjacency graph is empty.

Definition at line 348 of file vtkVoronoiCore2D.h.

◆ Filter

template<class TCompositor, class TClassifier = vtkVoronoiClassifier2D>

vtkAlgorithm* vtkVoronoiCore2D< TCompositor, TClassifier >::Filter

Used for controlling filter abort and accessing filter information.

If nullptr, then filter abort checking is disabled.

Definition at line 361 of file vtkVoronoiCore2D.h.

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

Filters/Meshing/vtkVoronoiCore2D.h

Classes

Public Member Functions

Static Public Member Functions

Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ vtkVoronoiCore2D()

Member Function Documentation

◆ Execute()

◆ GetNumberOfThreads()

◆ GetThreadData()

◆ GetMaximumNumberOfPoints()

◆ GetNumberOfPrunes()

◆ GetAdjacencyGraph()

◆ Initialize()

◆ operator()()

◆ Reduce()

◆ GetNumberOfPoints()

◆ GetPoints()

Member Data Documentation

◆ Compositor

◆ Classifier

◆ Batcher

◆ ThreadMap

◆ Graph

◆ Filter