Tessellator Class Reference

Tessellator subdivides concave planar polygons, polygons with holes, or polygons with intersecting edges into triangles or simple contours. More...

#include <easy3d/algo/tessellator.h>

Classes
struct	Vertex
	A vertex carries both xyz coordinates and its attributes (e.g., color, texcoord). More...

Public Types
enum	WindingRule {   WINDING_ODD = 100130 , WINDING_NONZERO = 100131 , WINDING_POSITIVE = 100132 , WINDING_NEGATIVE = 100133 ,   WINDING_ABS_GEQ_TWO = 100134 }
	The winding rule (default rule is ODD, modify if needed)

Public Member Functions
	Tessellator ()
	Constructor.
	~Tessellator ()
	Destructor.
void	set_boundary_only (bool b)
	Set the working mode of the tessellator.
void	set_winding_rule (WindingRule rule)
	Set the winding rule. The new rule will be effective until being changed by calling this function again.
void	begin_polygon (const vec3 &normal)
	Begin the tessellation of a complex polygon.
void	begin_polygon ()
	Begin the tessellation of a complex polygon.
void	begin_contour ()
	Begin a contour of a complex polygon (a polygon may have multiple contours).
void	add_vertex (const Vertex &data)
	Add a vertex of a contour to the tessellator.
void	add_vertex (const float *data, unsigned int size, int idx=0)
	Add a vertex of a contour to the tessellator.
void	add_vertex (const vec3 &xyz, int idx=0)
	Add a vertex of a contour to the tessellator.
void	add_vertex (const vec3 &xyz, const vec2 &t, int idx=0)
	Add a vertex of a contour to the tessellator.
void	add_vertex (const vec3 &xyz, const vec3 &v1, int idx=0)
	Add a vertex of a contour to the tessellator.
void	add_vertex (const vec3 &xyz, const vec3 &v1, const vec2 &t, int idx=0)
	Add a vertex of a contour to the tessellator.
void	add_vertex (const vec3 &xyz, const vec3 &v1, const vec3 &v2, int idx=0)
	Add a vertex of a contour to the tessellator.
void	add_vertex (const vec3 &xyz, const vec3 &v1, const vec3 &v2, const vec2 &t, int idx=0)
	Add a vertex of a contour to the tessellator.
void	end_contour ()
	Finish the current contour of a polygon.
void	end_polygon ()
	Finish the current polygon.
const std::vector< Vertex * > &	vertices () const
	The list of vertices in the result.
const std::vector< std::vector< unsigned int > > &	elements () const
	The list of elements (triangle or contour) created over many calls. Each element is represented by its vertex indices.
unsigned int	num_elements_in_polygon () const
	The number of elements (triangle or contour) in the last polygon.
void	reset ()
	Clear all recorded data (triangle list and vertices) and restart index counter.

Detailed Description

Tessellator subdivides concave planar polygons, polygons with holes, or polygons with intersecting edges into triangles or simple contours.

This implementation is also able to keep track of the unique vertices and respective indices, which allows to take advantage of the element buffer for efficient rendering (i.e., avoid sending vertices with the same geometry to the GPU). Typical applications:

• Tessellate concave polygons, polygons with holes, or polygons with intersecting edges;
• Generate buffer data for rendering;
• Triangulate non-triangle surfaces;
• Stitch patches of a triangle meshes;
• CSG operations

  See also

• csg::tessellate(std::vector<Polygon2> &polygons, Tessellator::WindingRule rule);
• csg::union_of(std::vector<Polygon2> &polygons);
• csg::intersection_of(const Polygon2& polygon_a, const Polygon2& polygon_b, std::vector<Polygon2> &result);
• csg::difference_of(const Polygon2& polygon_a, const Polygon2& polygon_b, std::vector<Polygon2> &result).

Examples

Tutorial_601_Tessellator/main.cpp.

Member Function Documentation

add_vertex() [1/8]

void add_vertex	(	const float *	data,
		unsigned int	size,
		int	idx = 0 )

Add a vertex of a contour to the tessellator.

Parameters

data	The vertex data.
size	The size of the vertex data array.
idx	The index of this vertex. Providing a non-negative index allows to map a resulting vertex to the original vertex. Any new vertex generated in the tessellation will have a negative index -1.

add_vertex() [2/8]

void add_vertex	(	const vec3 &	xyz,
		const vec2 &	t,
		int	idx = 0 )

Add a vertex of a contour to the tessellator.

Parameters

xyz	The xyz coordinates of the vertex.
t	The texture coordinates of the vertex.
idx	The index of this vertex. Providing a non-negative index allows to map a resulting vertex to the original vertex. Any new vertex generated in the tessellation will have a negative index -1.

add_vertex() [3/8]

void add_vertex	(	const vec3 &	xyz,
		const vec3 &	v1,
		const vec2 &	t,
		int	idx = 0 )

Add a vertex of a contour to the tessellator.

Parameters

xyz	The xyz coordinates of the vertex.
v1	The first vertex property.
t	The texture coordinates of the vertex.
idx	The index of this vertex. Providing a non-negative index allows to map a resulting vertex to the original vertex. Any new vertex generated in the tessellation will have a negative index -1.

add_vertex() [4/8]

void add_vertex	(	const vec3 &	xyz,
		const vec3 &	v1,
		const vec3 &	v2,
		const vec2 &	t,
		int	idx = 0 )

Add a vertex of a contour to the tessellator.

Parameters

xyz	The xyz coordinates of the vertex.
v1	The first vertex property.
v2	The second vertex property.
t	The texture coordinates of the vertex.
idx	The index of this vertex. Providing a non-negative index allows to map a resulting vertex to the original vertex. Any new vertex generated in the tessellation will have a negative index -1.

add_vertex() [5/8]

void add_vertex	(	const vec3 &	xyz,
		const vec3 &	v1,
		const vec3 &	v2,
		int	idx = 0 )

Add a vertex of a contour to the tessellator.

Parameters

xyz	The xyz coordinates of the vertex.
v1	The first vertex property.
v2	The second vertex property.
idx	The index of this vertex. Providing a non-negative index allows to map a resulting vertex to the original vertex. Any new vertex generated in the tessellation will have a negative index -1.

add_vertex() [6/8]

void add_vertex	(	const vec3 &	xyz,
		const vec3 &	v1,
		int	idx = 0 )

Add a vertex of a contour to the tessellator.

Parameters

xyz	The xyz coordinates of the vertex.
v1	The first vertex property.
idx	The index of this vertex. Providing a non-negative index allows to map a resulting vertex to the original vertex. Any new vertex generated in the tessellation will have a negative index -1.

add_vertex() [7/8]

void add_vertex	(	const vec3 &	xyz,
		int	idx = 0 )

Add a vertex of a contour to the tessellator.

Parameters

xyz	The xyz coordinates of the vertex.
idx	The index of this vertex. Providing a non-negative index allows to map a resulting vertex to the original vertex. Any new vertex generated in the tessellation will have a negative index -1.

add_vertex() [8/8]

void add_vertex

(

const Vertex &

data

)

Add a vertex of a contour to the tessellator.

Parameters

data	The vertex data.

begin_polygon() [1/2]

void begin_polygon

(

)

Begin the tessellation of a complex polygon.

This function does not provide the polygon normal and let the tessellator decide.

begin_polygon() [2/2]

void begin_polygon

(

const vec3 &

normal

)

Begin the tessellation of a complex polygon.

This function lets the user supply the polygon normal if known (to improve robustness or to achieve a specific tessellation purpose like CSG). All input data is projected into a plane perpendicular to the normal before tesselation. All output triangles are oriented CCW with respect to the normal. If the supplied normal is (0,0,0) (the default value), the normal is determined as follows. The direction of the normal, up to its sign, is found by fitting a plane to the vertices, without regard to how the vertices are connected. It is expected that the input data lies approximately in plane; otherwise projection perpendicular to the computed normal may substantially change the geometry. The sign of the normal is chosen so that the sum of the signed areas of all input contours is non-negative (where a CCW contour has positive area).

Attention

The supplied normal persists until it is changed by another call to this function.

elements()

const std::vector< std::vector< unsigned int > > & elements ( ) const

inline

The list of elements (triangle or contour) created over many calls. Each element is represented by its vertex indices.

Returns

The list of elements.

num_elements_in_polygon()

unsigned int num_elements_in_polygon ( ) const

inline

The number of elements (triangle or contour) in the last polygon.

Returns

The number of elements in the last polygon.

Note

Must be used after call to end_polygon() and before the next call to begin_polygon().

reset()

void reset

(

)

Clear all recorded data (triangle list and vertices) and restart index counter.

---

This function is useful if you want to selectively stitch faces/components. In this case, call reset() before you process each set. Then for each set, you collect the vertices and vertex indices of the triangles.

set_boundary_only()

void set_boundary_only

(

bool

b

)

Set the working mode of the tessellator.

The tessellator has two working modes and this function sets its working mode. The two working modes:

• Filled polygons: complex polygons are tessellated into filled polygons;
• Boundary only: complex polygons are tessellated into simple line loops separating the polygon interior and exterior.

  Parameters

  b	True for the boundary only mode and false for the filled polygons mode.

set_winding_rule()

void set_winding_rule

(

WindingRule

rule

)

Set the winding rule. The new rule will be effective until being changed by calling this function again.

Parameters

rule	The winding rule to set.

With the winding rules, complex CSG operations can be implemented:

• UNION: Draw all input contours as a single polygon. The winding number of each resulting region is the number of original polygons that cover it. The union can be extracted by using the WINDING_NONZERO or WINDING_POSITIVE winding rules. Note that with the WINDING_NONZERO winding rule, we would get the same result if all contour orientations were reversed.
• INTERSECTION: This only works for two contours at a time. Draw a single polygon using two contours. Extract the result using WINDING_ABS_GEQ_TWO.
• DIFFERENCE: Suppose you want to compute A diff (B union C union D). Draw a single polygon consisting of the unmodified contours from A, followed by the contours of B, C, and D, with their vertex order reversed. To extract the result, use the WINDING_POSITIVE winding rule. (If B, C, and D are the result of a BOUNDARY_ONLY operation, an alternative to reversing the vertex order is to reverse the sign of the supplied normal. See begin_polygon(). Explanation of the winding rule can be found here: https://www.glprogramming.com/red/chapter11.html

vertices()

const std::vector< Tessellator::Vertex * > & vertices

(

)

const

The list of vertices in the result.

---

Returns

The list of vertices.

---

The documentation for this class was generated from the following files:

• G:/3_code/Easy3D/easy3d/algo/tessellator.h
• G:/3_code/Easy3D/easy3d/algo/tessellator.cpp