CUGL 2.3
Cornell University Game Library

#include <CUEarclipTriangulator.h>
Public Member Functions  
EarclipTriangulator ()  
EarclipTriangulator (const std::vector< Vec2 > &points)  
EarclipTriangulator (const Path2 &path)  
~EarclipTriangulator ()  
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  reset () 
void  clear () 
void  calculate () 
std::vector< Uint32 >  getTriangulation () const 
size_t  getTriangulation (std::vector< Uint32 > &buffer) const 
Poly2  getPolygon () const 
Poly2 *  getPolygon (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 class is an implementation of the the ear clipping algorithm to triangulate polygons. This algorithm supports complex polygons, namely those with interior holes (but not selfcrossings). All triangles produced are guaranteed to be counterclockwise.
The running time of this algorithm is O(n^2), making it one of the slower triangulation methods available. However, it has very low overhead, making it better than DelaunayTriangulator
in some cases. In addition, it is guaranteed to make better (e.g. not thin) triangles than MonotoneTriangulator
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 in several different ways.
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 midcalculation.
cugl::EarclipTriangulator::EarclipTriangulator  (  ) 
Creates a triangulator with no vertex data.
cugl::EarclipTriangulator::EarclipTriangulator  (  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::EarclipTriangulator::EarclipTriangulator  (  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::EarclipTriangulator::~EarclipTriangulator  (  ) 
Deletes this triangulator, releasing all resources.
void cugl::EarclipTriangulator::addHole  (  const Path2 &  path  ) 
Adds the given hole to the triangulation.
The hole path should be a closed path with no selfcrossings. 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..n1, 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::EarclipTriangulator::addHole  (  const std::vector< Vec2 > &  points  ) 
Adds the given hole to the triangulation.
The hole is assumed to be a closed path with no selfcrossings. 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..n1, 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::EarclipTriangulator::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 selfcrossings. 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..n1, 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::EarclipTriangulator::calculate  (  ) 
Performs a triangulation of the current vertex data.
void cugl::EarclipTriangulator::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 will be lost as well.
Poly2 cugl::EarclipTriangulator::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.
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.
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::EarclipTriangulator::getTriangulation  (  )  const 
Returns a list of indices representing the triangulation.
The indices represent positions in the original vertex list, which included holes as well. Positions are ordered as follows: first the exterior hull, and then all holes in order.
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::EarclipTriangulator::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 
void cugl::EarclipTriangulator::reset  (  ) 
Clears all internal data, but still maintains the initial vertex data.
This method also retains any holes. It only clears the triangulation results.
void cugl::EarclipTriangulator::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 counterclockwise 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. You will need to readd any lost data and reperform the calculation.
path  The vertices to triangulate 
void cugl::EarclipTriangulator::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 counterclockwise 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. You will need to readd any lost data and reperform the calculation.
points  The vertices to triangulate 
void cugl::EarclipTriangulator::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 counterclockwise 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. You will need to readd any lost data and reperform the calculation.
points  The vertices to triangulate 
size  The number of vertices 