All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
GQ_PolyDelaunay Class Reference

#include <GQ_PolyDelaunay.h>

Public Types


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.


  • 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 109 of file GQ_PolyDelaunay.h.

Member Typedef Documentation

typedef GQ_PolyDelaunayImpl::gqEdgeQueue GQ_PolyDelaunay::gqEdgeQueue

Definition at line 117 of file GQ_PolyDelaunay.h.

typedef GQ_PolyDelaunayImpl::gqFaceQueue GQ_PolyDelaunay::gqFaceQueue

Definition at line 115 of file GQ_PolyDelaunay.h.

typedef GQ_PolyDelaunayImpl::gqGBEdgeGroup GQ_PolyDelaunay::gqGBEdgeGroup

Definition at line 116 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 114 of file GQ_PolyDelaunay.h.

Constructor & Destructor Documentation

GQ_PolyDelaunay::GQ_PolyDelaunay ( GU_Detail gdp)
virtual GQ_PolyDelaunay::~GQ_PolyDelaunay ( )

Member Function Documentation

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

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

Definition at line 142 of file GQ_PolyDelaunay.h.

void GQ_PolyDelaunay::enableRefinement ( bool  enabled)

Allow refinement.

Definition at line 151 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)

Definition at line 148 of file GQ_PolyDelaunay.h.

void GQ_PolyDelaunay::setConstraintNewPointGroupName ( const UT_String name)

Definition at line 146 of file GQ_PolyDelaunay.h.

void GQ_PolyDelaunay::setKeepBoundingTriangle ( bool  value)

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

Definition at line 134 of file GQ_PolyDelaunay.h.

void GQ_PolyDelaunay::setMaxArea ( fpreal  maxArea)

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 158 of file GQ_PolyDelaunay.h.

void GQ_PolyDelaunay::setMaxNewPoints ( int  maxNewPoints)

Definition at line 153 of file GQ_PolyDelaunay.h.

void GQ_PolyDelaunay::setMinAngle ( fpreal  minAngle)

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

Definition at line 129 of file GQ_PolyDelaunay.h.

void GQ_PolyDelaunay::setRemoveOutsideConstraints ( bool  value)

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

Definition at line 138 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: