The polyhedron class proper. More...

#include <vtkVoronoiHull.h>

Collaboration diagram for vtkVoronoiHull:

Classes
struct	DeletionStack
	A homebrew stack with a preferred API. More...

struct	FaceOperation
	Keep track of points and faces currently being operated on. More...

struct	FaceProcessingArray
	Unique list of faces (by id) that require processing. More...

struct	PointProcessingArray
	Add points to be processed. More...

Public Types
using	vtkHullPointsArray = std::vector< vtkHullPoint >

using	vtkHullFacesArray = std::vector< vtkHullFace >

using	FacePointsArray = std::vector< int >

using	FaceScratchArray = std::vector< int >

using	InsertedEdgePointsArray = std::vector< vtkHullEdgeTuple >

Public Member Functions
	vtkVoronoiHull ()
	Constructor. More...

	vtkVoronoiHull (const vtkVoronoiHull &)
	vtkSMPTools require a proper operator= and copy constructor. More...

vtkVoronoiHull &	operator= (const vtkVoronoiHull &)

void	Initialize (vtkIdType genPtId, const double genPt[3], double bds[6])
	Method to initiate the construction of the polyhedron. More...

ClipIntersectionStatus	Clip (vtkIdType neiPtId, const double neiPt[3])
	Method to clip the current convex polyhedron/hull with a plane defined by a neighboring point. More...

double	GetCircumFlower2 ()
	Methods to determine whether a point x[3] is within the Voronoi flower, or Voronoi circumflower. More...

bool	InCircumFlower (double r2)

bool	InFlower (const double x[3])

void	UpdatePetals (double cf2)

vtkDoubleArray *	GetPetals ()

void	MapPoints ()
	Used to produce debugging output (e.g., generate vtkPolyData). More...

void	ProduceFacePolyData (vtkPolyData pd, vtkHullFace face)
	Produce a vtkPolyData from the current polyhedron and one specified face. More...

void	ProducePolyData (vtkPolyData *pd)
	Produce a vtkPolyData from the current polyhedron. More...

void	BumpNormal (int bumpNum, double normal[3], double bumpNormal[3])

void	BumpOrigin (int bumpNum, double origin[3], double bumpOrigin[3])

vtkIdType	AddNewPoint (double x, double y, double z)
	Methods to add and delete polyhedron points. More...

vtkIdType	AddNewPoint (double x[3])

void	DeletePoint (vtkIdType ptId)

void	SetPointFaces (vtkIdType pId, vtkIdType f0, vtkIdType f1, vtkIdType f2)

int	AddNewFace (vtkIdType npts, vtkIdType neiPtId)
	Methods to create, modify, and delete polyhedron faces. More...

vtkHullFace *	GetFace (int faceId)

void	AddFacePoint (vtkHullFace *face, vtkIdType ptId)
	Add a point id defining the current face. More...

void	AddNthFacePoint (vtkHullFace *face, int idx, vtkIdType ptId)
	Add the nth point id defining the current face. More...

int	GetFacePoint (vtkHullFace *face, int ptNum)
	Return the nth point id defining the current face. More...

void	RebuildFacePoints (vtkHullFace *face, FaceScratchArray &idsBuffer)
	After clipping, rebuild the face. More...

int	EvaluateFace (vtkHullFace *face, int &startIdx, int &numKeptPts)
	After a face clipping operation, characterize the face, and provide information for subsequent processing. More...

void	DeleteFace (int faceId, int startIdx, int numKeptPts)
	Delete a face from the polyhedron. More...

void	RebuildFace (int faceId, int startIdx, int numKeptPts)
	Rebuild a convex, intersected face after a clipping operation. More...

int	IntersectFaceEdge (int faceId, int p0, int p1)
	Given two point ids that form the edge of a polyhedron face, intersect the edge to produce a new intersection point. More...

void	AllocatePointIds (int npts, vtkHullFace &face)
	Internal memory operation to allocate space when adding new points (due to a reabuild) which define a face. More...

Public Attributes
vtkIdType	PtId

double	X [3]

vtkIdType	NumClips

double	PruneTolerance

vtkVoronoiRandom01Range	Bumper

vtkIdType	NumPts

vtkHullPointsArray	Points

vtkIdType	NumFaces

vtkHullFacesArray	Faces

Protected Member Functions
void	ComputeCircumFlower ()

void	Clear ()
	Empty out the polyhedron: clear memory but leave allocation intact. More...

ClipIntersectionStatus	IntersectWithPlane (double origin[3], double normal[3], vtkIdType neiPtId)
	The core geometric intersection operation. More...

Protected Attributes
FacePointsArray	FacePoints
	Internal data members. More...

int	MIN_POINTIDS_ALLOC = 10

DeletionStack	DeletedPoints

DeletionStack	DeletedFaces

PointProcessingArray	InProcessPoints

FaceProcessingArray	InProcessFaces

InsertedEdgePointsArray	InsertedEdgePoints

FaceScratchArray	FaceIdsBuffer

bool	RecomputeCircumFlower

bool	RecomputePetals

double	CircumFlower2

double	MinRadius2

double	MaxRadius2

std::vector< vtkHullPoint * >	SortP

vtkSmartPointer< vtkDoubleArray >	Petals

Detailed Description

The polyhedron class proper.

provide core 3D Voronoi hull generation capabilities

Since it is a supporting class, it is lightweight and not a subclass of vtkObject.

This lightweight, supporting class is used to generate a convex polyhedron from repeated half-space clipping operations (i.e., generate a Voronoi hull). It also keeps track of the Voronoi flower and circumflower (aka, the radius of security). These are used to determine whether a clipping operation will intersect the current polyhedron.

The algorithm proceeds as follows. A generating point is placed within an initial, convex bounding box (i.e., this is the starting Voronoi hull). The hull is then repeatedly clipped by planes positioned at the halfway points between neighboring points, with each plane's normal pointing in the direction of the edge connecting the generator point to the neighboring point.

The Voronoi hull class is represented by points and faces. Each point refers to the faces that intersected to produce it; each face refers to the points that define it. Because these operations are dynamic, i.e., points and faces are created, modified, and deleted frequently, a simple, built-in memory management system is used to reduce the performance impact of repeated allocations and deletions. Also note that, because of this dynamic processing, some of the points and faces may not be valid–make sure that only points/faces whose ProcessingStatus are labeled "Valid" are used.

Tolerancing capabilities are built into this class. The relative "PruneTolerance" is used to discard clipping nicks–that is, clipping planes that barely intersect (i.e., graze) the hull. By pruning (or discarding) small hull facets, the numerical stability of the hull generation process is significantly improved. Note that the PruneTolerance is relative, it is multiplied by a representative length of the hull; therefore it is adaptive to hull size.

See also: vtkVoronoiCore3D vtkVoronoi3D vtkGeneralizedSurfaceNets3D vtkVoronoiTile vtkVoronoiCore2D vtkVoronoiFlower2D

Tests:: vtkVoronoiHull (Tests)

Definition at line 226 of file vtkVoronoiHull.h.

Member Typedef Documentation

using vtkVoronoiHull::vtkHullPointsArray = std::vector<vtkHullPoint>

Definition at line 230 of file vtkVoronoiHull.h.

using vtkVoronoiHull::vtkHullFacesArray = std::vector<vtkHullFace>

Definition at line 231 of file vtkVoronoiHull.h.

using vtkVoronoiHull::FacePointsArray = std::vector<int>

Definition at line 232 of file vtkVoronoiHull.h.

using vtkVoronoiHull::FaceScratchArray = std::vector<int>

Definition at line 233 of file vtkVoronoiHull.h.

using vtkVoronoiHull::InsertedEdgePointsArray = std::vector<vtkHullEdgeTuple>

Definition at line 234 of file vtkVoronoiHull.h.

Constructor & Destructor Documentation

vtkVoronoiHull::vtkVoronoiHull ( )

inline

Constructor.

After instantiation, for each new point to process, make sure to initialize the polyhedron with Initialize().

Definition at line 240 of file vtkVoronoiHull.h.

vtkVoronoiHull::vtkVoronoiHull ( const vtkVoronoiHull & )

inline

vtkSMPTools require a proper operator= and copy constructor.

Definition at line 270 of file vtkVoronoiHull.h.

Member Function Documentation

vtkVoronoiHull& vtkVoronoiHull::operator= ( const vtkVoronoiHull & )

inline

Definition at line 297 of file vtkVoronoiHull.h.

void vtkVoronoiHull::Initialize	(	vtkIdType	genPtId,
		const double	genPt[3],
		double	bds[6]
	)

Method to initiate the construction of the polyhedron.

Define the generator point id and its position, and an initial bounding box in which to place the generator point.

ClipIntersectionStatus vtkVoronoiHull::Clip	(	vtkIdType	neiPtId,
		const double	neiPt[3]
	)

Method to clip the current convex polyhedron/hull with a plane defined by a neighboring point.

The neighbor id and its position must not be coincident with the current generator point. This method does not take into account the Voronoi circumflower and flower. The method returns a clip intersection status.

double vtkVoronoiHull::GetCircumFlower2 ( )

inline

Methods to determine whether a point x[3] is within the Voronoi flower, or Voronoi circumflower.

(The Voronoi flower is the union of all Delaunay spheres located at the hull points. The Voronoi circumflower is the 2*radius of the largest Delaunay sphere.) These methods can be used to cull points which do not intersect the hull.

Definition at line 322 of file vtkVoronoiHull.h.

bool vtkVoronoiHull::InCircumFlower ( double r2 )

inline

Definition at line 323 of file vtkVoronoiHull.h.

bool vtkVoronoiHull::InFlower ( const double x[3] )

inline

Definition at line 792 of file vtkVoronoiHull.h.

void vtkVoronoiHull::UpdatePetals ( double cf2 )

inline

Definition at line 830 of file vtkVoronoiHull.h.

vtkDoubleArray* vtkVoronoiHull::GetPetals ( )

inline

Definition at line 335 of file vtkVoronoiHull.h.

void vtkVoronoiHull::MapPoints ( )

inline

Used to produce debugging output (e.g., generate vtkPolyData).

It numbers (i.e., maps) the points to global point ids.

Definition at line 811 of file vtkVoronoiHull.h.

void vtkVoronoiHull::ProduceFacePolyData	(	vtkPolyData *	pd,
		vtkHullFace *	face
	)

Produce a vtkPolyData from the current polyhedron and one specified face.

This is typically for debugging purposes.

void vtkVoronoiHull::ProducePolyData ( vtkPolyData * pd )

Produce a vtkPolyData from the current polyhedron.

This is typically for debugging purposes.

void vtkVoronoiHull::BumpNormal	(	int	bumpNum,
		double	normal[3],
		double	bumpNormal[3]
	)

void vtkVoronoiHull::BumpOrigin	(	int	bumpNum,
		double	origin[3],
		double	bumpOrigin[3]
	)

vtkIdType vtkVoronoiHull::AddNewPoint	(	double	x,
		double	y,
		double	z
	)

inline

Methods to add and delete polyhedron points.

Definition at line 632 of file vtkVoronoiHull.h.

vtkIdType vtkVoronoiHull::AddNewPoint ( double x[3] )

inline

Definition at line 487 of file vtkVoronoiHull.h.

void vtkVoronoiHull::DeletePoint ( vtkIdType ptId )

inline

Definition at line 654 of file vtkVoronoiHull.h.

void vtkVoronoiHull::SetPointFaces	(	vtkIdType	pId,
		vtkIdType	f0,
		vtkIdType	f1,
		vtkIdType	f2
	)

inline

Definition at line 624 of file vtkVoronoiHull.h.

int vtkVoronoiHull::AddNewFace	(	vtkIdType	npts,
		vtkIdType	neiPtId
	)

inline

Methods to create, modify, and delete polyhedron faces.

Definition at line 668 of file vtkVoronoiHull.h.

vtkHullFace* vtkVoronoiHull::GetFace ( int faceId )

inline

Definition at line 495 of file vtkVoronoiHull.h.

void vtkVoronoiHull::AddFacePoint	(	vtkHullFace *	face,
		vtkIdType	ptId
	)

inline

Add a point id defining the current face.

This method is called after AddNewFace().

Definition at line 500 of file vtkVoronoiHull.h.

void vtkVoronoiHull::AddNthFacePoint	(	vtkHullFace *	face,
		int	idx,
		vtkIdType	ptId
	)

inline

Add the nth point id defining the current face.

This method is called after AddNewFace().

Definition at line 508 of file vtkVoronoiHull.h.

int vtkVoronoiHull::GetFacePoint	(	vtkHullFace *	face,
		int	ptNum
	)

inline

Return the nth point id defining the current face.

Definition at line 515 of file vtkVoronoiHull.h.

void vtkVoronoiHull::RebuildFacePoints	(	vtkHullFace *	face,
		FaceScratchArray &	idsBuffer
	)

inline

After clipping, rebuild the face.

Definition at line 743 of file vtkVoronoiHull.h.

int vtkVoronoiHull::EvaluateFace	(	vtkHullFace *	face,
		int &	startIdx,
		int &	numKeptPts
	)

inline

After a face clipping operation, characterize the face, and provide information for subsequent processing.

The method returns the number of edge intersections; i.e. returns ==0 if the face should be deleted (all points outside of the clip plane); returns ==2 if a convex clip is to be performed; and >2 if a degenerate, non-convex clip is identified. In most situations, convex clips are performed, and the method arguments startIdx and numKeptPts are returned (identifying the points of the face which are interior to the clip). When a non-convex clip is identified, special treatment is necessary to address numerical degeneracies. (Note: faces are never entirely inside the clip half space because they have been tagged as InProcess, meaning they are attached to an outside point.)

Definition at line 690 of file vtkVoronoiHull.h.

void vtkVoronoiHull::DeleteFace	(	int	faceId,
		int	startIdx,
		int	numKeptPts
	)

inline

Delete a face from the polyhedron.

To avoid memory thrashing (i.e., avoid new/delete), the face is simply marked deleted, and the deleted face (and associated memory) will be reused in the future. This method is called when all points defining the face are evaluated outside after a clip operation.

Definition at line 762 of file vtkVoronoiHull.h.

void vtkVoronoiHull::RebuildFace	(	int	faceId,
		int	startIdx,
		int	numKeptPts
	)

Rebuild a convex, intersected face after a clipping operation.

The parameters startIdx and numKeptPts define a portion of the face loop (i.e., the points that form the face) that, together with the two new clip points, form the rebuilt, modified face. This method should only be invoked on convex faces with exactly two edge intersections.

int vtkVoronoiHull::IntersectFaceEdge	(	int	faceId,
		int	p0,
		int	p1
	)

Given two point ids that form the edge of a polyhedron face, intersect the edge to produce a new intersection point.

The id of the intersection point is returned.

void vtkVoronoiHull::AllocatePointIds	(	int	npts,
		vtkHullFace &	face
	)

inline

Internal memory operation to allocate space when adding new points (due to a reabuild) which define a face.

Definition at line 726 of file vtkVoronoiHull.h.

void vtkVoronoiHull::ComputeCircumFlower ( )

inlineprotected

Definition at line 770 of file vtkVoronoiHull.h.

void vtkVoronoiHull::Clear ( )

inlineprotected

Empty out the polyhedron: clear memory but leave allocation intact.

Definition at line 603 of file vtkVoronoiHull.h.

ClipIntersectionStatus vtkVoronoiHull::IntersectWithPlane	(	double	origin[3],
		double	normal[3],
		vtkIdType	neiPtId
	)

protected

The core geometric intersection operation.

The method returns a clip intersection status.

Member Data Documentation

vtkIdType vtkVoronoiHull::PtId

Definition at line 368 of file vtkVoronoiHull.h.

double vtkVoronoiHull::X[3]

Definition at line 369 of file vtkVoronoiHull.h.

vtkIdType vtkVoronoiHull::NumClips

Definition at line 370 of file vtkVoronoiHull.h.

double vtkVoronoiHull::PruneTolerance

Definition at line 371 of file vtkVoronoiHull.h.

vtkVoronoiRandom01Range vtkVoronoiHull::Bumper

Definition at line 374 of file vtkVoronoiHull.h.

vtkIdType vtkVoronoiHull::NumPts

Definition at line 379 of file vtkVoronoiHull.h.

vtkHullPointsArray vtkVoronoiHull::Points

Definition at line 380 of file vtkVoronoiHull.h.

vtkIdType vtkVoronoiHull::NumFaces

Definition at line 381 of file vtkVoronoiHull.h.

vtkHullFacesArray vtkVoronoiHull::Faces

Definition at line 382 of file vtkVoronoiHull.h.

FacePointsArray vtkVoronoiHull::FacePoints

protected

Internal data members.

Definition at line 573 of file vtkVoronoiHull.h.

int vtkVoronoiHull::MIN_POINTIDS_ALLOC = 10

protected

Definition at line 574 of file vtkVoronoiHull.h.

DeletionStack vtkVoronoiHull::DeletedPoints

protected

Definition at line 578 of file vtkVoronoiHull.h.

DeletionStack vtkVoronoiHull::DeletedFaces

protected

Definition at line 579 of file vtkVoronoiHull.h.

PointProcessingArray vtkVoronoiHull::InProcessPoints

protected

Definition at line 582 of file vtkVoronoiHull.h.

FaceProcessingArray vtkVoronoiHull::InProcessFaces

protected

Definition at line 583 of file vtkVoronoiHull.h.

InsertedEdgePointsArray vtkVoronoiHull::InsertedEdgePoints

protected

Definition at line 584 of file vtkVoronoiHull.h.

FaceScratchArray vtkVoronoiHull::FaceIdsBuffer

protected

Definition at line 585 of file vtkVoronoiHull.h.

bool vtkVoronoiHull::RecomputeCircumFlower

protected

Definition at line 590 of file vtkVoronoiHull.h.

bool vtkVoronoiHull::RecomputePetals

protected

Definition at line 591 of file vtkVoronoiHull.h.

double vtkVoronoiHull::CircumFlower2

protected

Definition at line 592 of file vtkVoronoiHull.h.

double vtkVoronoiHull::MinRadius2

protected

Definition at line 593 of file vtkVoronoiHull.h.

double vtkVoronoiHull::MaxRadius2

protected

Definition at line 594 of file vtkVoronoiHull.h.

std::vector<vtkHullPoint*> vtkVoronoiHull::SortP

protected

Definition at line 595 of file vtkVoronoiHull.h.

vtkSmartPointer<vtkDoubleArray> vtkVoronoiHull::Petals

protected

Definition at line 596 of file vtkVoronoiHull.h.

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

Filters/Meshing/vtkVoronoiHull.h

Classes

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation