#include <GQ_PolyDelaunay.h>
Classes | |
| struct | gqJournal |
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. | |
| bool | fitPlane (const GB_PointGroup *pointGroup=0, UT_Vector3 *outNormal=0, fpreal *outDistance=0) |
| Fit a plane to the input points. Returns true if it succeeded. | |
| void | setRemoveDuplicatePoints (bool value) |
| void | setKeepBoundingTriangle (bool value) |
| void | setRemoveOutsideConstraints (bool value) |
| void | enableNewConstraintPoints (bool enabled) |
| void | setConstraintNewPointGroupName (const UT_String &name) |
| void | enableRefinement (bool enabled) |
| Allow refinement. | |
| void | setMaxNewPoints (int maxNewPoints) |
| void | setMaxArea (fpreal maxArea) |
| void | setMinAngle (fpreal minAngle) |
| void | triangulate (const GB_PointGroup *pointGroup, const GB_PrimitiveGroup *constrainedPrimGroup) |
| void | buildGeometry (bool updatePointNormals=true) |
| UT_Vector2 | make2D (const UT_Vector4 &pos) const |
| Project 3D point onto plane. | |
| UT_Vector4 | make3D (const UT_Vector2 &pos) const |
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 GB_Edge class unconventionally here. Constraint edges are stored as GB_Edges in a GB_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 GB_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 114 of file GQ_PolyDelaunay.h.
| GQ_PolyDelaunay::GQ_PolyDelaunay | ( | GU_Detail * | gdp | ) | [explicit] |
| virtual GQ_PolyDelaunay::~GQ_PolyDelaunay | ( | ) | [virtual] |
| void GQ_PolyDelaunay::buildGeometry | ( | bool | updatePointNormals = true |
) |
| void GQ_PolyDelaunay::enableNewConstraintPoints | ( | bool | enabled | ) | [inline] |
Allow new points - e.g., constraint edges are split to maintain the Delaunay property.
Definition at line 140 of file GQ_PolyDelaunay.h.
| void GQ_PolyDelaunay::enableRefinement | ( | bool | enabled | ) | [inline] |
| bool GQ_PolyDelaunay::fitPlane | ( | const GB_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::setConstraintNewPointGroupName | ( | const UT_String & | name | ) | [inline] |
Definition at line 142 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 132 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 152 of file GQ_PolyDelaunay.h.
| void GQ_PolyDelaunay::setMaxNewPoints | ( | int | maxNewPoints | ) | [inline] |
Definition at line 147 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 161 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 127 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 136 of file GQ_PolyDelaunay.h.
| void GQ_PolyDelaunay::triangulate | ( | const GB_PointGroup * | pointGroup, | |
| const GB_PrimitiveGroup * | constrainedPrimGroup | |||
| ) |
1.5.9