 |
CUGL 2.1
Cornell University Game Library
|
|
CUGL 2.1
Cornell University Game Library
|
#include <CUDelaunayTriangulator.h>
Public Member Functions | |
| DelaunayTriangulator () | |
| DelaunayTriangulator (const std::vector< Vec2 > &points) | |
| DelaunayTriangulator (const Path2 &path) | |
| ~DelaunayTriangulator () | |
| void | set (const std::vector< Vec2 > &points) |
| void | set (const Vec2 *points, size_t size) |
| void | set (const Path2 &path) |
| void | addHole (const std::vector< Vec2 > &points) |
| void | addHole (const Vec2 *points, size_t size) |
| void | addHole (const Path2 &path) |
| void | addSteiner (Vec2 point) |
| void | reset () |
| void | clear () |
| void | calculate () |
| void | calculateDual () |
| std::vector< Uint32 > | getTriangulation () const |
| size_t | getTriangulation (std::vector< Uint32 > &buffer) const |
| Poly2 | getPolygon () const |
| Poly2 * | getPolygon (Poly2 *buffer) const |
| std::vector< Uint32 > | getMap () const |
| size_t | getMap (std::vector< Uint32 > &buffer) const |
| Poly2 | getMapPolygon () const |
| Poly2 * | getMapPolygon (Poly2 *buffer) const |
| std::vector< Poly2 > | getVoronoi () const |
| Poly2 | getVoronoiCell (size_t index) const |
| Poly2 * | getVoronoiCell (size_t index, Poly2 *buffer) const |
This class is a factory for producing solid Poly2 objects from a set of vertices.
For all but the simplist of shapes, it is important to have a triangulator that can divide up the polygon into triangles for drawing. This triangulator uses the poly2tri library to perform a Constrained Delaunay triangulation. This library supports complex polygons, namely those with interior holes (but not self-crossings). All triangles produced are guaranteed to be counter-clockwise.
Note that poly2tri uses a sweep-line algorithm described in
https://www.tandfonline.com/doi/abs/10.1080/13658810701492241
While most sweep-line algorithms have O(n^2) time, this algorithm experimentally outperforms an O(n log n) algorithm. However, no worst-case analysis on this algorithm is available.
Because the Voronoi diagram is the dual of the Delaunay triangulation, this factory can be used to extract this diagram. The Voronoi diagram can be extracted as either a single polygon (for each point) or a collection of polygons. Each polygon is a solid Poly2 representing a region.
As with all factories, the methods are broken up into three phases: initialization, calculation, and materialization. To use the factory, you first set the data (in this case a set of vertices or another Poly2) with the initialization methods. You then call the calculation method. Finally, you use the materialization methods to access the data. Unlike the other triangulators, you cannot simply get this triangulation as a set of indices. That is because the triangulation may have added additional vertices.
This division allows us to support multithreaded calculation if the data generation takes too long. However, note that this factory is not thread safe in that you cannot access data while it is still in mid-calculation.
| cugl::DelaunayTriangulator::DelaunayTriangulator | ( | ) |
Creates a triangulator with no vertex data.
| cugl::DelaunayTriangulator::DelaunayTriangulator | ( | const std::vector< Vec2 > & | points | ) |
Creates a triangulator with the given vertex data.
The vertices are assumed to be the outer hull, and do not include any holes (which may be specified later). The vertex data is copied. The triangulator does not retain any references to the original data.
| points | The vertices to triangulate |
| cugl::DelaunayTriangulator::DelaunayTriangulator | ( | const Path2 & | path | ) |
Creates a triangulator with the given vertex data.
The path is assumed to be the outer hull, and does not include any holes (which may be specified later). The vertex data is copied. The triangulator does not retain any references to the original data.
| path | The vertices to triangulate |
| cugl::DelaunayTriangulator::~DelaunayTriangulator | ( | ) |
Deletes this triangulator, releasing all resources.
| void cugl::DelaunayTriangulator::addHole | ( | const Path2 & | path | ) |
Adds the given hole to the triangulation.
The hole path should be a closed path with no self-crossings. In addition, it is assumed to be inside the polygon outer hull, with vertices ordered in clockwise traversal. If any of these is not true, the results are undefined.
The vertex data is copied. The triangulator does not retain any references to the original data. Hole points are added after the hull points, in order. That is, when the triangulation is computed, if the hull is size n, then the hull points are indices 0..n-1, while n is the index of a hole point.
Any holes added to the triangulator will be lost if the exterior polygon is changed via the set method.
| path | The hole path |
| void cugl::DelaunayTriangulator::addHole | ( | const std::vector< Vec2 > & | points | ) |
Adds the given hole to the triangulation.
The hole is assumed to be a closed path with no self-crossings. In addition, it is assumed to be inside the polygon outer hull, with vertices ordered in clockwise traversal. If any of these is not true, the results are undefined.
The vertex data is copied. The triangulator does not retain any references to the original data. Hole points are added after the hull points, in order. That is, when the triangulation is computed, if the hull is size n, then the hull points are indices 0..n-1, while n is the index of a hole point.
Any holes added to the triangulator will be lost if the exterior polygon is changed via the set method.
| points | The hole vertices |
| void cugl::DelaunayTriangulator::addHole | ( | const Vec2 * | points, |
| size_t | size | ||
| ) |
Adds the given hole to the triangulation.
The hole is assumed to be a closed path with no self-crossings. In addition, it is assumed to be inside the polygon outer hull, with vertices ordered in clockwise traversal. If any of these is not true, the results are undefined.
The vertex data is copied. The triangulator does not retain any references to the original data. Hole points are added after the hull points, in order. That is, when the triangulation is computed, if the hull is size n, then the hull points are indices 0..n-1, while n is the index of a hole point.
Any holes added to the triangulator will be lost if the exterior polygon is changed via the set method.
| points | The hole vertices |
| size | The number of vertices |
| void cugl::DelaunayTriangulator::addSteiner | ( | Vec2 | point | ) |
Adds the given Steiner point to the triangulation.
A Steiner point may be included in the triangulation results, but it does not have to be. Any Steiner points added to the triangulator will be lost if the exterior polygon is changed via the set method.
The vertex data is copied. The triangulator does not retain any references to the original data. Steiner points are added last. That is, when the triangulation is computed, the highest indices all refer to these points, in the order that they were provided.
| point | The Steiner point |
| void cugl::DelaunayTriangulator::calculate | ( | ) |
Performs a triangulation of the current vertex data.
This only calculates the triangulation. It does not compute the Voronoi dual.
| void cugl::DelaunayTriangulator::calculateDual | ( | ) |
Calculates the Voronoi diagram.
This will force a triangulation if one has not been computed already. In cases where triangles are missing to fully define the Voronoi diagram (such as on the boundary of the diagram), the missing triangles are interpolated.
| void cugl::DelaunayTriangulator::clear | ( | ) |
Clears all internal data, including the initial vertex data.
When this method is called, you will need to set a new vertices before calling calculate. In addition, any holes or Steiner points will be lost as well.
| std::vector<Uint32> cugl::DelaunayTriangulator::getMap | ( | ) | const |
Returns a list of indices representing the extended triangulation map.
The indices represent positions in the original vertex list, which included both holes and Steiner points. Positions are ordered as follows: first the exterior hull, then all holes in order, and finally the Steiner points. As these indices represent the extended triangulation, they may include triangles outside of the exterior hull.
The triangulator does not retain a reference to the returned list; it is safe to modify it. If the calculation is not yet performed, this method will return the empty list.
| size_t cugl::DelaunayTriangulator::getMap | ( | std::vector< Uint32 > & | buffer | ) | const |
Stores the extended triangulation map indices in the given buffer.
The indices represent positions in the original vertex list, which included both holes and Steiner points. Positions are ordered as follows: first the exterior hull, then all holes in order, and finally the Steiner points. As these indices represent the extended triangulation, they may include triangles outside of the exterior hull.
The indices will be appended to the provided vector. You should clear the vector first if you do not want to preserve the original data. If the calculation is not yet performed, this method will do nothing.
| buffer | The buffer to store the extended triangulation map |
| Poly2 cugl::DelaunayTriangulator::getMapPolygon | ( | ) | const |
Returns a polygon representing the extended triangulation map.
This polygon is the extended triangulation, which may include triangles outside of the polygon hull. It may or many not include any Steiner points that were specified.
The triangulator does not maintain references to this polygon and it is safe to modify it. If the calculation is not yet performed, this method will return the empty polygon.
Stores the extended triangulation map in the given buffer.
This polygon is the extended triangulation, which may include triangles outside of the polygon hull. It may or many not include any Steiner points that were specified.
This method will append the vertices to the given polygon. If the buffer is not empty, the indices will be adjusted accordingly. You should clear the buffer first if you do not want to preserve the original data.
If the calculation is not yet performed, this method will do nothing.
| buffer | The buffer to store the triangulated polygon |
| Poly2 cugl::DelaunayTriangulator::getPolygon | ( | ) | const |
Returns a polygon representing the triangulation.
This polygon is the proper triangulation, constrained to the interior of the polygon hull. It contains the vertices of the exterior polygon, as well as any holes. It may or many not include any Steiner points that were specified.
The triangulator does not maintain references to this polygon and it is safe to modify it. If the calculation is not yet performed, this method will return the empty polygon.
Stores the triangulation in the given buffer.
The polygon produced is the proper triangulation, constrained to the interior of the polygon hull. It contains the vertices of the exterior polygon, as well as any holes. It may or many not include any Steiner points that were specified.
This method will append the vertices to the given polygon. If the buffer is not empty, the indices will be adjusted accordingly. You should clear the buffer first if you do not want to preserve the original data.
If the calculation is not yet performed, this method will do nothing.
| buffer | The buffer to store the triangulated polygon |
| std::vector<Uint32> cugl::DelaunayTriangulator::getTriangulation | ( | ) | const |
Returns a list of indices representing the triangulation.
The indices represent positions in the original vertex list, which included both holes and Steiner points. Positions are ordered as follows: first the exterior hull, then all holes in order, and finally the Steiner points.
The triangulator does not retain a reference to the returned list; it is safe to modify it. If the calculation is not yet performed, this method will return the empty list.
| size_t cugl::DelaunayTriangulator::getTriangulation | ( | std::vector< Uint32 > & | buffer | ) | const |
Stores the triangulation indices in the given buffer.
The indices represent positions in the original vertex list, which included both holes and Steiner points. Positions are ordered as follows: first the exterior hull, then all holes in order, and finally the Steiner points.
The indices will be appended to the provided vector. You should clear the vector first if you do not want to preserve the original data. If the calculation is not yet performed, this method will do nothing.
| buffer | The buffer to store the triangulation indices |
| std::vector<Poly2> cugl::DelaunayTriangulator::getVoronoi | ( | ) | const |
Returns the Voronoi diagram as a list of polygons
Each polygon represents a single Voronoi cell. A Voronoi cell is a polygon whose vertices are the boundary of the cell. Each Voronoi cell corresponds to a vertex in the original triangulation.
The cells are returned in the same order as the vertices. For each cell, the Poly2 object is triangulated as a fan with the associated vertex point at its center.
If the Voronoi diagram is not calculated, this method will do nothing.
| Poly2 cugl::DelaunayTriangulator::getVoronoiCell | ( | size_t | index | ) | const |
Returns the Voronoi cell for the given index
A Voronoi cell is a polygon whose vertices are the boundary of the cell. The index corresponds to the vertex in the original triangulation. The returns Poly2 object is triangulated as a fan with the associated vertex point at its center.
If the Voronoi diagram is not calculated, this method will return an empty polygon
| index | The index of the vertex generating the cell |
Stores the Voronoi cell in the given buffer.
A Voronoi cell is a polygon whose vertices are the boundary of the cell. The index corresponds to the vertex in the original triangulation. The returns Poly2 object is triangulated as a fan with the associated vertex point at its center.
If the Voronoi diagram is not calculated, this method will do nothing.
| index | The index of the vertex generating the cell |
| buffer | The buffer to store the Voronoi cell |
| void cugl::DelaunayTriangulator::reset | ( | ) |
Clears all internal data, but still maintains the initial vertex data.
This method also retains any holes or Steiner points. It only clears the triangulation results.
| void cugl::DelaunayTriangulator::set | ( | const Path2 & | path | ) |
Sets the exterior vertex data for this triangulator.
The path is assumed to be the outer hull, and does not include any holes (which may be specified later). The path should define the hull in a counter-clockwise traversal.
The vertex data is copied. The triangulator does not retain any references to the original data. Hull points are added first. That is, when the triangulation is computed, the lowest indices all refer to these points, in the order that they were provided.
This method resets all interal data. The triangulation is lost, as well as any previously added holes or Steiner points. You will need to re-add any lost data and reperform the calucation.
| path | The vertices to triangulate |
| void cugl::DelaunayTriangulator::set | ( | const std::vector< Vec2 > & | points | ) |
Sets the exterior vertex data for this triangulator.
The vertices are assumed to be the outer hull, and do not include any holes (which may be specified later). The vertices should define the hull in a counter-clockwise traversal.
The vertex data is copied. The triangulator does not retain any references to the original data. Hull points are added first. That is, when the triangulation is computed, the lowest indices all refer to these points, in the order that they were provided.
This method resets all interal data. The triangulation is lost, as well as any previously added holes or Steiner points. You will need to re-add any lost data and reperform the calucation.
| points | The vertices to triangulate |
| void cugl::DelaunayTriangulator::set | ( | const Vec2 * | points, |
| size_t | size | ||
| ) |
Sets the exterior vertex data for this triangulator.
The vertices are assumed to be the outer hull, and do not include any holes (which may be specified later). The vertices should define the hull in a counter-clockwise traversal.
The vertex data is copied. The triangulator does not retain any references to the original data. Hull points are added first. That is, when the triangulation is computed, the lowest indices all refer to these points, in the order that they were provided.
This method resets all interal data. The triangulation is lost, as well as any previously added holes or Steiner points. You will need to re-add any lost data and reperform the calucation.
| points | The vertices to triangulate |
| size | The number of vertices |
1.8.16