All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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...

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 60 of file GU_PolyDelaunay.h.

Member Enumeration Documentation


Definition at line 89 of file GU_PolyDelaunay.h.

Constructor & Destructor Documentation

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

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

virtual GU_PolyDelaunay::~GU_PolyDelaunay ( )

Member Function Documentation

void GU_PolyDelaunay::allowConstraintSplit ( bool  enabled)

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

Definition at line 107 of file GU_PolyDelaunay.h.

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

Allow refinement.

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

Definition at line 156 of file GU_PolyDelaunay.h.

bool GU_PolyDelaunay::hasNonEmptyDuplicatePointMap ( ) const

Query whether or not the triangulation consolidated some duplicate points.

Definition at line 169 of file GU_PolyDelaunay.h.

void GU_PolyDelaunay::setConstraintSplitPointGroup ( GA_PointGroup new_pt_grp)

Definition at line 115 of file GU_PolyDelaunay.h.

void GU_PolyDelaunay::setConstraintSplitPointGroupName ( const UT_String name)

Definition at line 112 of file GU_PolyDelaunay.h.

void GU_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 86 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)

Cap the maximum allowed number of new ponts.

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

Definition at line 81 of file GU_PolyDelaunay.h.

void GU_PolyDelaunay::setRemoveFromConvexHull ( bool  value)

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

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

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