GQ_PolyDelaunay Class Reference

#include <GQ_PolyDelaunay.h>

Public Types
typedef GQ_PolyDelaunayImpl::gqTriangleSplitNode	gqTriangleSplitNode
typedef GQ_PolyDelaunayImpl::gqFaceQueue	gqFaceQueue
typedef GQ_PolyDelaunayImpl::gqGBEdgeGroup	gqGBEdgeGroup
typedef GQ_PolyDelaunayImpl::gqEdgeQueue	gqEdgeQueue

Public Member Functions
	GQ_PolyDelaunay (GU_Detail *gdp)
virtual	~GQ_PolyDelaunay ()
void	setPlane (const UT_Vector3 &normal, fpreal distance)
	Set the plane where triangulation happens. More...
bool	fitPlane (const GA_PointGroup *pointGroup=0, UT_Vector3 *outNormal=0, fpreal *outDistance=0)
	Fit a plane to the input points. Returns true if it succeeded. More...
void	setRemoveDuplicatePoints (bool value)
void	setKeepBoundingTriangle (bool value)
void	setRemoveOutsideConstraints (bool value)
void	enableNewConstraintPoints (bool enabled)
void	setConstraintNewPointGroupName (const UT_String &name)
void	setConstraintNewPointGroup (GA_PointGroup *new_pt_grp)
void	enableRefinement (bool enabled)
	Allow refinement. More...
void	setMaxNewPoints (int maxNewPoints)
void	setMaxArea (fpreal maxArea)
void	setMinAngle (fpreal minAngle)
void	triangulate (const GA_PointGroup *pointGroup, const GA_PrimitiveGroup *constrainedPrimGroup)
void	buildGeometry (bool updatePointNormals=true, GA_PrimitiveGroup *out_grp=NULL)
UT_Vector2	make2D (const UT_Vector4 &pos) const
	Project 3D point onto plane. More...
UT_Vector4	make3D (const UT_Vector2 &pos) const

Detailed Description

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

The algorithm used is a randomized incremental algorithm, as presented in de Berg, van Kreveld, Overmars and Schwarzkopf. "Computational Geometry", 2nd edition, 1999.

It's adapted from: Guibas, Knuth and Sharir. "Randomized incremental construction of Delaunay and Voronoi diagrams." Algorithmica, 7:381-413, 1992.

Most of it follows 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 data structure for determining which triangle a point is in.

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

Shewchuk describes a number of algorithms; I've implemented the pseudocode from pages 47-48. I used the Terminator algorithm, using concentric circles instead of diametral lenses. I haven't implemented one part of his algorithm: the key "terminator" innovation, his splitPermitted routine.

A rough overview of the algorithm can be found at: http://www-2.cs.cmu.edu/~quake/tripaper/triangle3.html

Shewchuk's main inspiration is this paper:

Ruppert. "A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation", Journal of Algorithms 18(3):548-585, May 1995.

TODO: this could be extended to work with 3D points under a 2D parameterization (i.e., use texture co-ordinates instead of positions). I'm not sure how we would handle u-wrap or v-wrap, though... There's some discussion of this problem in Chew, L. Paul. Guaranteed-Quality Mesh Generation for Curved Surfaces. Proceedings of the 9th Annual Symposium on Computational Geometry, pages 274-280. ACM, May 1993.

Better yet, we could do what Shewchuk describes in section 7.1 of his paper: triangulate a set of 3D primitives independently, but keeping track of insertions on the boundaries that are shared by multiple primitives. Apparently, it would require a way of calculating geodesic distance between points on different primitives. I'm sure other changes to my algorithm would be required too.

Notes:

• We use the GA_Edge class unconventionally here. Constraint edges are stored as GA_Edges in a GA_EdgeGroup. The endpoint order matters: the region to the right of p0->p1 is in the "interior" of the constraint. The optional "primitive" member of the GA_Edge points to the constraint primitive. However, the primitive member will be null for constraints that have no holes (i.e., have no bridge edges). This signals that there is no need to remove triangles from the inside of the hole.

Definition at line 110 of file GQ_PolyDelaunay.h.

Member Typedef Documentation

typedef GQ_PolyDelaunayImpl::gqEdgeQueue GQ_PolyDelaunay::gqEdgeQueue

Definition at line 118 of file GQ_PolyDelaunay.h.

typedef GQ_PolyDelaunayImpl::gqFaceQueue GQ_PolyDelaunay::gqFaceQueue

Definition at line 116 of file GQ_PolyDelaunay.h.

typedef GQ_PolyDelaunayImpl::gqGBEdgeGroup GQ_PolyDelaunay::gqGBEdgeGroup

Definition at line 117 of file GQ_PolyDelaunay.h.

typedef GQ_PolyDelaunayImpl::gqTriangleSplitNode GQ_PolyDelaunay::gqTriangleSplitNode

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

Definition at line 115 of file GQ_PolyDelaunay.h.

Constructor & Destructor Documentation

GQ_PolyDelaunay::GQ_PolyDelaunay ( GU_Detail *  gdp )

explicit

virtual GQ_PolyDelaunay::~GQ_PolyDelaunay ( )

virtual

Member Function Documentation

void GQ_PolyDelaunay::buildGeometry	(	bool	updatePointNormals = true,
		GA_PrimitiveGroup *	out_grp = NULL
	)

void GQ_PolyDelaunay::enableNewConstraintPoints ( bool  enabled )

inline

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

Definition at line 143 of file GQ_PolyDelaunay.h.

void GQ_PolyDelaunay::enableRefinement ( bool  enabled )

inline

Allow refinement.

Definition at line 152 of file GQ_PolyDelaunay.h.

bool GQ_PolyDelaunay::fitPlane	(	const GA_PointGroup *	pointGroup = 0,
		UT_Vector3 *	outNormal = 0,
		fpreal *	outDistance = 0
	)

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

UT_Vector2 GQ_PolyDelaunay::make2D

(

const UT_Vector4 &

pos

)

const

Project 3D point onto plane.

UT_Vector4 GQ_PolyDelaunay::make3D

(

const UT_Vector2 &

pos

)

const

void GQ_PolyDelaunay::setConstraintNewPointGroup ( GA_PointGroup *  new_pt_grp )

inline

Definition at line 149 of file GQ_PolyDelaunay.h.

void GQ_PolyDelaunay::setConstraintNewPointGroupName ( const UT_String &  name )

inline

Definition at line 147 of file GQ_PolyDelaunay.h.

void GQ_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 135 of file GQ_PolyDelaunay.h.

void GQ_PolyDelaunay::setMaxArea ( fpreal  maxArea )

inline

Set refinement criteria. Any triangle that fails the maximum area test will be refined by inserting a new Steiner point. To disable this test, set to <= 0.

Definition at line 159 of file GQ_PolyDelaunay.h.

void GQ_PolyDelaunay::setMaxNewPoints ( int  maxNewPoints )

inline

Definition at line 154 of file GQ_PolyDelaunay.h.

void GQ_PolyDelaunay::setMinAngle ( fpreal  minAngle )

inline

Set refinement criteria. Any triangle that fails the minimum angle test will be refined by inserting a new Steiner point. To disable this test, set to <= 0.

Warning: high values can cause this to halt. Shewchuk says that there's a proof that it works for below 21 degrees, and he finds it works below 33, but he's had problems with higher values.

Definition at line 168 of file GQ_PolyDelaunay.h.

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

Set the plane where triangulation happens.

void GQ_PolyDelaunay::setRemoveDuplicatePoints ( bool  value )

inline

Definition at line 130 of file GQ_PolyDelaunay.h.

void GQ_PolyDelaunay::setRemoveOutsideConstraints ( bool  value )

inline

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

Definition at line 139 of file GQ_PolyDelaunay.h.

void GQ_PolyDelaunay::triangulate	(	const GA_PointGroup *	pointGroup,
		const GA_PrimitiveGroup *	constrainedPrimGroup
	)

---

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

• GQ/GQ_PolyDelaunay.h