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

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.

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

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

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

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).

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

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

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.

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.

vtkHullFace *	GetFace (int faceId)

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

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

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

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

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

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

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

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.

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

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.

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

Protected Attributes
FacePointsArray	FacePoints
	Internal data members.

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

◆ vtkHullPointsArray

using vtkVoronoiHull::vtkHullPointsArray

Initial value:

std::vector<vtkHullPoint>

Definition at line 229 of file vtkVoronoiHull.h.

◆ vtkHullFacesArray

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

Definition at line 231 of file vtkVoronoiHull.h.

◆ FacePointsArray

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

Definition at line 232 of file vtkVoronoiHull.h.

◆ FaceScratchArray

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

Definition at line 233 of file vtkVoronoiHull.h.

◆ InsertedEdgePointsArray

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

Definition at line 234 of file vtkVoronoiHull.h.

Constructor & Destructor Documentation

◆ vtkVoronoiHull()

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.

Member Function Documentation

◆ Initialize()

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.

◆ Clip()

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.

◆ GetCircumFlower2()

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 290 of file vtkVoronoiHull.h.

◆ InCircumFlower()

bool vtkVoronoiHull::InCircumFlower ( double r2 )

inline

Definition at line 291 of file vtkVoronoiHull.h.

◆ InFlower()

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

inline

Definition at line 760 of file vtkVoronoiHull.h.

◆ UpdatePetals()

void vtkVoronoiHull::UpdatePetals ( double cf2 )

inline

Definition at line 798 of file vtkVoronoiHull.h.

◆ GetPetals()

vtkDoubleArray * vtkVoronoiHull::GetPetals ( )

inline

Definition at line 303 of file vtkVoronoiHull.h.

◆ MapPoints()

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 779 of file vtkVoronoiHull.h.

◆ ProduceFacePolyData()

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

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

This is typically for debugging purposes.

◆ ProducePolyData()

void vtkVoronoiHull::ProducePolyData ( vtkPolyData * pd )

Produce a vtkPolyData from the current polyhedron.

This is typically for debugging purposes.

◆ BumpNormal()

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

◆ BumpOrigin()

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

◆ AddNewPoint() [1/2]

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

inline

Methods to add and delete polyhedron points.

Definition at line 600 of file vtkVoronoiHull.h.

◆ AddNewPoint() [2/2]

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

inline

Definition at line 455 of file vtkVoronoiHull.h.

◆ DeletePoint()

void vtkVoronoiHull::DeletePoint ( vtkIdType ptId )

inline

Definition at line 622 of file vtkVoronoiHull.h.

◆ SetPointFaces()

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

inline

Definition at line 592 of file vtkVoronoiHull.h.

◆ AddNewFace()

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

inline

Methods to create, modify, and delete polyhedron faces.

Definition at line 636 of file vtkVoronoiHull.h.

◆ GetFace()

vtkHullFace * vtkVoronoiHull::GetFace ( int faceId )

inline

Definition at line 463 of file vtkVoronoiHull.h.

◆ AddFacePoint()

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 468 of file vtkVoronoiHull.h.

◆ AddNthFacePoint()

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 476 of file vtkVoronoiHull.h.

◆ GetFacePoint()

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

inline

Return the nth point id defining the current face.

Definition at line 483 of file vtkVoronoiHull.h.

◆ RebuildFacePoints()

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

inline

After clipping, rebuild the face.

Definition at line 711 of file vtkVoronoiHull.h.

◆ EvaluateFace()

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 658 of file vtkVoronoiHull.h.

◆ DeleteFace()

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 730 of file vtkVoronoiHull.h.

◆ RebuildFace()

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.

◆ IntersectFaceEdge()

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.

◆ AllocatePointIds()

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 694 of file vtkVoronoiHull.h.

◆ ComputeCircumFlower()

void vtkVoronoiHull::ComputeCircumFlower ( )

inlineprotected

Definition at line 738 of file vtkVoronoiHull.h.

◆ Clear()

void vtkVoronoiHull::Clear ( )

inlineprotected

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

Definition at line 571 of file vtkVoronoiHull.h.

◆ IntersectWithPlane()

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

◆ PtId

vtkIdType vtkVoronoiHull::PtId

Definition at line 336 of file vtkVoronoiHull.h.

◆ X

double vtkVoronoiHull::X[3]

Definition at line 337 of file vtkVoronoiHull.h.

◆ NumClips

vtkIdType vtkVoronoiHull::NumClips

Definition at line 338 of file vtkVoronoiHull.h.

◆ PruneTolerance

double vtkVoronoiHull::PruneTolerance

Definition at line 339 of file vtkVoronoiHull.h.

◆ Bumper

vtkVoronoiRandom01Range vtkVoronoiHull::Bumper

Definition at line 342 of file vtkVoronoiHull.h.

◆ NumPts

vtkIdType vtkVoronoiHull::NumPts

Definition at line 347 of file vtkVoronoiHull.h.

◆ Points

vtkHullPointsArray vtkVoronoiHull::Points

Definition at line 348 of file vtkVoronoiHull.h.

◆ NumFaces

vtkIdType vtkVoronoiHull::NumFaces

Definition at line 349 of file vtkVoronoiHull.h.

◆ Faces

vtkHullFacesArray vtkVoronoiHull::Faces

Definition at line 350 of file vtkVoronoiHull.h.

◆ FacePoints

FacePointsArray vtkVoronoiHull::FacePoints

protected

Internal data members.

Definition at line 541 of file vtkVoronoiHull.h.

◆ MIN_POINTIDS_ALLOC

int vtkVoronoiHull::MIN_POINTIDS_ALLOC = 10

protected

Definition at line 542 of file vtkVoronoiHull.h.

◆ DeletedPoints

DeletionStack vtkVoronoiHull::DeletedPoints

protected

Definition at line 546 of file vtkVoronoiHull.h.

◆ DeletedFaces

DeletionStack vtkVoronoiHull::DeletedFaces

protected

Definition at line 547 of file vtkVoronoiHull.h.

◆ InProcessPoints

PointProcessingArray vtkVoronoiHull::InProcessPoints

protected

Definition at line 550 of file vtkVoronoiHull.h.

◆ InProcessFaces

FaceProcessingArray vtkVoronoiHull::InProcessFaces

protected

Definition at line 551 of file vtkVoronoiHull.h.

◆ InsertedEdgePoints

InsertedEdgePointsArray vtkVoronoiHull::InsertedEdgePoints

protected

Definition at line 552 of file vtkVoronoiHull.h.

◆ FaceIdsBuffer

FaceScratchArray vtkVoronoiHull::FaceIdsBuffer

protected

Definition at line 553 of file vtkVoronoiHull.h.

◆ RecomputeCircumFlower

bool vtkVoronoiHull::RecomputeCircumFlower

protected

Definition at line 558 of file vtkVoronoiHull.h.

◆ RecomputePetals

bool vtkVoronoiHull::RecomputePetals

protected

Definition at line 559 of file vtkVoronoiHull.h.

◆ CircumFlower2

double vtkVoronoiHull::CircumFlower2

protected

Definition at line 560 of file vtkVoronoiHull.h.

◆ MinRadius2

double vtkVoronoiHull::MinRadius2

protected

Definition at line 561 of file vtkVoronoiHull.h.

◆ MaxRadius2

double vtkVoronoiHull::MaxRadius2

protected

Definition at line 562 of file vtkVoronoiHull.h.

◆ SortP

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

protected

Definition at line 563 of file vtkVoronoiHull.h.

◆ Petals

vtkSmartPointer<vtkDoubleArray> vtkVoronoiHull::Petals

protected

Definition at line 564 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

◆ vtkHullPointsArray

◆ vtkHullFacesArray

◆ FacePointsArray

◆ FaceScratchArray

◆ InsertedEdgePointsArray

Constructor & Destructor Documentation

◆ vtkVoronoiHull()

Member Function Documentation

◆ Initialize()

◆ Clip()

◆ GetCircumFlower2()

◆ InCircumFlower()

◆ InFlower()

◆ UpdatePetals()

◆ GetPetals()

◆ MapPoints()

◆ ProduceFacePolyData()

◆ ProducePolyData()

◆ BumpNormal()

◆ BumpOrigin()

◆ AddNewPoint() [1/2]

◆ AddNewPoint() [2/2]

◆ DeletePoint()

◆ SetPointFaces()

◆ AddNewFace()

◆ GetFace()

◆ AddFacePoint()

◆ AddNthFacePoint()

◆ GetFacePoint()

◆ RebuildFacePoints()

◆ EvaluateFace()

◆ DeleteFace()

◆ RebuildFace()

◆ IntersectFaceEdge()

◆ AllocatePointIds()

◆ ComputeCircumFlower()

◆ Clear()

◆ IntersectWithPlane()

Member Data Documentation

◆ PtId

◆ X

◆ NumClips

◆ PruneTolerance

◆ Bumper

◆ NumPts

◆ Points

◆ NumFaces

◆ Faces

◆ FacePoints

◆ MIN_POINTIDS_ALLOC

◆ DeletedPoints

◆ DeletedFaces

◆ InProcessPoints

◆ InProcessFaces

◆ InsertedEdgePoints

◆ FaceIdsBuffer

◆ RecomputeCircumFlower

◆ RecomputePetals

◆ CircumFlower2

◆ MinRadius2

◆ MaxRadius2

◆ SortP

◆ Petals