GU_PolyDelaunay Class Reference

#include <GU_PolyDelaunay.h>

Public Types
enum	RemoveOutsidePolicy { REMOVE_NONE = 0, REMOVE_IF_OUT, REMOVE_IF_OUT_BUT_NOT_IN }

Public Member Functions
	GU_PolyDelaunay (GU_Detail *gdp, uint32 rand_seed=5678U)
virtual	~GU_PolyDelaunay ()
void	setPlane (const UT_Vector3 &normal, fpreal distance)
	Set the plane where triangulation happens. More...
bool	fitPlane (const GA_PointGroup *ptgrp=0, UT_Vector3 *out_normal=0, fpreal *out_distance=0, UT_Vector3 *out_center=0)
	Fit a plane to the input points. Returns true if it succeeded. More...
void	setRemoveDuplicatePoints (bool value)
void	setKeepBoundingTriangle (bool value)
void	setRemoveFromConvexHull (bool value)
void	setRemoveOutside (bool value, bool skip_if_also_inside=false)
void	allowConstraintSplit (bool enabled)
void	setConstraintSplitPointGroupName (const UT_String &name)
void	setConstraintSplitPointGroup (GA_PointGroup *new_pt_grp)
void	enableRefinement (bool enabled)
	Allow refinement. More...
void	setMaxNewPoints (int maxNewPoints)
	Cap the maximum allowed number of new ponts. More...
void	setRestorePositions (bool val)
void	setMaxArea (fpreal max_area)
void	setMinAngle (fpreal min_angle)
void	setMinEdgeLength (fpreal min_edge_length)
void	triangulate (const GA_PointGroup *point_group, const GA_PrimitiveGroup *constraint_prims, const GA_EdgeGroup *constraint_edges)
	Perform the triangulation. More...
void	copyTriangles (bool updatePointNormals=true, GA_PrimitiveGroup *out_grp=NULL)
const std::string	getWarningMessage ()
void	getBoundingSquareCorners (UT_Vector3 *corners)
bool	setPositionAttribute (const char *attrib)
void	getProjectedConstrainedEdges (UT_Array< UT_Vector3 > &endpoints)
void	getEnforcedEdges (GA_EdgeGroup &edge_group)
bool	hasNonEmptyDuplicatePointMap () const
void	getDuplicatePointMapForInput (UT_Map< GA_Offset, GA_Offset > &map) const
	Query how the triangulation consolidated duplicate points. More...
bool	hasConflictingConstraints () const
	Query whether the triangulation had conflicting constraints. More...

Detailed Description

Delaunay triangulation (and refinement) of a set of 2D points.

The Delaunay triangulation algorithm used is the randomized incremental algorithm, as presented in de Berg, van Kreveld, Overmars and Schwarzkopf. "Computational Geometry", 2nd edition, 1999, in turn adapated from: Guibas, Knuth and Sharir. "Randomized incremental construction of Delaunay and Voronoi diagrams." Algorithmica, 7:381-413, 1992.

Most ideas are present in the earlier paper: Guibas and Stolfi. "Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams", ACM Transactions on Graphics, 4(2):74-123, April 1985. except for the point location DAG.

Constraint enforcement is done through removal of edges that intersect constraints and retriangulating the resulting poligons. The code closely follows the appraoch of Shewchuk in his Triangle package.

After triangulation is complete, an optional Delaunay refinement process is applied. This follows Shewchuk. "Delaunay Refinement Algorithms for Triangular Mesh Generation". Computational Geometry: Theory and Applications 22(1-3):21-74, May 2002. http://www.cs.berkeley.edu/~jrs/papers/2dj.ps

A good resource for quick lookup is Shewchuk's presentation slides on this subject: http://www.cs.berkeley.edu/~jrs/papers/imrtalk.pdf

Definition at line 61 of file GU_PolyDelaunay.h.

Member Enumeration Documentation

enum GU_PolyDelaunay::RemoveOutsidePolicy

Enumerator
REMOVE_NONE
REMOVE_IF_OUT
REMOVE_IF_OUT_BUT_NOT_IN

Definition at line 90 of file GU_PolyDelaunay.h.

Constructor & Destructor Documentation

GU_PolyDelaunay::GU_PolyDelaunay ( GU_Detail *  gdp, uint32  rand_seed = 5678U  )

explicit

Some local typedefs for our helper classes to avoid having to fully qualify the names everywhere.

virtual GU_PolyDelaunay::~GU_PolyDelaunay ( )

virtual

Member Function Documentation

void GU_PolyDelaunay::allowConstraintSplit ( bool  enabled )

inline

Allow new points - e.g., constraint edges are split to maintain the Delaunay property.

Definition at line 108 of file GU_PolyDelaunay.h.

void GU_PolyDelaunay::copyTriangles	(	bool	updatePointNormals = true,
		GA_PrimitiveGroup *	out_grp = NULL
	)

void GU_PolyDelaunay::enableRefinement ( bool  enabled )

inline

Allow refinement.

Definition at line 120 of file GU_PolyDelaunay.h.

bool GU_PolyDelaunay::fitPlane	(	const GA_PointGroup *	ptgrp = 0,
		UT_Vector3 *	out_normal = 0,
		fpreal *	out_distance = 0,
		UT_Vector3 *	out_center = 0
	)

Fit a plane to the input points. Returns true if it succeeded.

void GU_PolyDelaunay::getBoundingSquareCorners

(

UT_Vector3 *

corners

)

void GU_PolyDelaunay::getDuplicatePointMapForInput

(

UT_Map< GA_Offset, GA_Offset > &

map

)

const

Query how the triangulation consolidated duplicate points.

void GU_PolyDelaunay::getEnforcedEdges

(

GA_EdgeGroup &

edge_group

)

void GU_PolyDelaunay::getProjectedConstrainedEdges

(

UT_Array< UT_Vector3 > &

endpoints

)

const std::string GU_PolyDelaunay::getWarningMessage ( )

inline

Definition at line 157 of file GU_PolyDelaunay.h.

bool GU_PolyDelaunay::hasConflictingConstraints ( ) const

inline

Query whether the triangulation had conflicting constraints.

Definition at line 178 of file GU_PolyDelaunay.h.

bool GU_PolyDelaunay::hasNonEmptyDuplicatePointMap ( ) const

inline

Query whether or not the triangulation consolidated some duplicate points.

Definition at line 170 of file GU_PolyDelaunay.h.

void GU_PolyDelaunay::setConstraintSplitPointGroup ( GA_PointGroup *  new_pt_grp )

inline

Definition at line 116 of file GU_PolyDelaunay.h.

void GU_PolyDelaunay::setConstraintSplitPointGroupName ( const UT_String &  name )

inline

Definition at line 113 of file GU_PolyDelaunay.h.

void GU_PolyDelaunay::setKeepBoundingTriangle ( bool  value )

inline

This one is mostly here for debugging - if enabled, we don't delete the bounding triangle that's added during construction.

Definition at line 87 of file GU_PolyDelaunay.h.

void GU_PolyDelaunay::setMaxArea

(

fpreal

max_area

)

Set refinement maximum area criterion. Any triangle with larger area than this is subdivided. To disable, set to <= 0.0.

void GU_PolyDelaunay::setMaxNewPoints ( int  maxNewPoints )

inline

Cap the maximum allowed number of new ponts.

Definition at line 124 of file GU_PolyDelaunay.h.

void GU_PolyDelaunay::setMinAngle

(

fpreal

min_angle

)

Set refinement minmum angle. Any triangle with an angle less than this is subdivided (modulo satisfying Miller-Pav-Walkington rule) The argument angle is in radians. To disable this test, set to <= 0.0.

IMPORTANT: Large minimum angle values drive the refinement to infinity, or until the maximum allowed number of points is reached. If minimum required angle is <= 21 degrees, the algorithm provably terminates. In practice, the algorithm almost always terminates for minimum angles of up to about 33 degrees. Beyond that, the algorithm almost surely goes on for ever or until it hits the set limit.

void GU_PolyDelaunay::setMinEdgeLength

(

fpreal

min_edge_length

)

void GU_PolyDelaunay::setPlane	(	const UT_Vector3 &	normal,
		fpreal	distance
	)

Set the plane where triangulation happens.

bool GU_PolyDelaunay::setPositionAttribute

(

const char *

attrib

)

void GU_PolyDelaunay::setRemoveDuplicatePoints ( bool  value )

inline

Definition at line 82 of file GU_PolyDelaunay.h.

void GU_PolyDelaunay::setRemoveFromConvexHull ( bool  value )

inline

Definition at line 97 of file GU_PolyDelaunay.h.

void GU_PolyDelaunay::setRemoveOutside	(	bool	value,
		bool	skip_if_also_inside = false
	)

If enabled, delete all edges that are outside the constrained edges.

void GU_PolyDelaunay::setRestorePositions ( bool  val )

inline

Whether to keep the triangulation on the projection plane or backproject it back to the original point positions

Definition at line 129 of file GU_PolyDelaunay.h.

void GU_PolyDelaunay::triangulate	(	const GA_PointGroup *	point_group,
		const GA_PrimitiveGroup *	constraint_prims,
		const GA_EdgeGroup *	constraint_edges
	)

Perform the triangulation.

---

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

• GU/GU_PolyDelaunay.h