triangulate_impl.h

一个开源的Flash 播放器,可以在Windows/Linux 上运行

// triangulate_impl.h	-- Thatcher Ulrich 2004

// This source code has been donated to the Public Domain.  Do
// whatever you want with it.

// Code to triangulate arbitrary 2D polygonal regions.
//
// Use the basic robust ear-clipping algorithm from "FIST: Fast
// Industrial-Strength Triangulation of Polygons" by Martin Held.
//
// NOTE: This code is based on the algorithm described in the FIST
// paper, but this is NOT the official FIST code written by Martin
// Held!  This code may not be as robust or as fast as FIST, and is
// certainly not as well tested.  Also, it deviates in some places
// from the algorithm as described in the FIST paper; I have tried to
// document those places in the code, along with my reasoning, but
// this code is not warranted in any way.
//
// In particular, the recovery_process is currently not as good as
// official FIST or even what's in the FIST paper.  This routine may
// do some ugly stuff with self-intersecting input.
//
// For information on obtaining the offical industrial-strength FIST
// code, see the FIST web page at:
// http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html


#include "base/utility.h"
#include "base/triangulate.h"
#include "base/tu_random.h"
#include "base/grid_index.h"

#define PROFILE_TRIANGULATE
#ifdef PROFILE_TRIANGULATE
#include "base/tu_timer.h"
#endif // PROFILE_TRIANGULATE


// Template this whole thing on coord_t, so sint16 and float versions
// can easily reuse the code.
//
// These templates are instantiated in triangulate_<type>.cpp files.
// They're in separate cpp files so the linker will discard code for
// unused types.


// convenience struct; this could use some public vec2 type, but often
// it's nicer for users if the external interface is smaller and more
// c-like, since they probably have their own vec2 that they prefer.
template<class coord_t>
struct vec2
{
	vec2() : x(0), y(0) {}
	vec2(coord_t _x, coord_t _y) : x(_x), y(_y) {}

	bool	operator==(const vec2<coord_t>& v) const
	{
		return x == v.x && y == v.y;
	}

//data:
	coord_t	x, y;
};


inline double	determinant_float(const vec2<float>& a, const vec2<float>& b, const vec2<float>& c)
{
	return (double(b.x) - double(a.x)) * (double(c.y) - double(a.y))
		- (double(b.y) - double(a.y)) * (double(c.x) - double(a.x));
}


inline sint64	determinant_sint32(const vec2<sint32>& a, const vec2<sint32>& b, const vec2<sint32>& c)
{
	return (sint64(b.x) - sint64(a.x)) * (sint64(c.y) - sint64(a.y))
		- (sint64(b.y) - sint64(a.y)) * (sint64(c.x) - sint64(a.x));
}


// Return {-1,0,1} if c is {to the right, on, to the left} of the
// directed edge defined by a->b.
template<class coord_t>
inline int	vertex_left_test(const vec2<coord_t>& a, const vec2<coord_t>& b, const vec2<coord_t>& c)
{
	compiler_assert(0);	// must specialize
	return -1;
}


template<>
inline int	vertex_left_test(const vec2<float>& a, const vec2<float>& b, const vec2<float>& c)
// Specialize for vec2<float>
{
	double	det = determinant_float(a, b, c);
	if (det > 0) return 1;
	else if (det < 0) return -1;
	else return 0;
}


template<>
inline int	vertex_left_test(const vec2<sint32>& a, const vec2<sint32>& b, const vec2<sint32>& c)
// Specialize for vec2<sint32>
{
	sint64	det = determinant_sint32(a, b, c);
	if (det > 0) return 1;
	else if (det < 0) return -1;
	else return 0;
}


template<class coord_t>
bool	vertex_in_ear(const vec2<coord_t>& v, const vec2<coord_t>& a, const vec2<coord_t>& b, const vec2<coord_t>& c)
// Return true if v is on or inside the ear (a,b,c).
// (a,b,c) must be in ccw order!
{
	assert(vertex_left_test(b, a, c) <= 0);	// check ccw order

	if (v == a || v == c)
	{
		// Special case; we don't care if v is coincident with a or c.
		return false;
	}

	// Include the triangle boundary in our test.
	bool	ab_in = vertex_left_test(a, b, v) >= 0;
	bool	bc_in = vertex_left_test(b, c, v) >= 0;
	bool	ca_in = vertex_left_test(c, a, v) >= 0;

	return ab_in && bc_in && ca_in;
}


template<class coord_t> struct poly;



inline int	remap_index_for_duped_verts(int index, int duped_v0, int duped_v1)
// Helper.  Return the new value of index, for the case of verts [duped_v0]
// and [duped_v1] being duplicated and subsequent verts being shifted up.
{
	assert(duped_v0 < duped_v1);
	if (index <= duped_v0)
	{
		// No shift.
		return index;
	}
	else if (index <= duped_v1)
	{
		// Shift up one.
		return index + 1;
	}
	else
	{
		// Shift up two.
		return index + 2;
	}
}


template<class coord_t>
struct poly_vert
{
	poly_vert() {}
	poly_vert(coord_t x, coord_t y, poly<coord_t>* owner, int my_index)
		:
		m_v(x, y),
		m_my_index(my_index),
		m_next(-1),
		m_prev(-1),
		m_convex_result(0),	// 1 (convex), 0 (colinear), -1 (reflex)
		m_is_ear(false),
		m_poly_owner(owner)
	{
	}

	void	remap(const array<int>& remap_table)
	{
		m_my_index = remap_table[m_my_index];
		m_next = remap_table[m_next];
		m_prev = remap_table[m_prev];
	}

	index_point<coord_t>	get_index_point() const { return index_point<coord_t>(m_v.x, m_v.y); }

//data:
	vec2<coord_t>	m_v;
	int	m_my_index;	// my index into sorted_verts array
	int	m_next;
	int	m_prev;
	int	m_convex_result;	// (@@ only need 2 bits)
	bool	m_is_ear;
	poly<coord_t>*	m_poly_owner;	 // needed?
};


template<class coord_t>
int	compare_vertices(const void* a, const void* b)
// For qsort.  Sort by x, then by y.
{
	const poly_vert<coord_t>* vert_a = (const poly_vert<coord_t>*) a;
	const poly_vert<coord_t>* vert_b = (const poly_vert<coord_t>*) b;

	if (vert_a->m_v.x < vert_b->m_v.x)
		return -1;
	else if (vert_a->m_v.x > vert_b->m_v.x)
		return 1;
	else
	{
		if (vert_a->m_v.y < vert_b->m_v.y)
			return -1;
		else if (vert_a->m_v.y > vert_b->m_v.y)
			return 1;
	}

	return 0;
}


template<class coord_t>
inline bool	edges_intersect_sub(const array<poly_vert<coord_t> >& sorted_verts, int e0v0, int e0v1, int e1v0, int e1v1)
// Return true if edge (e0v0,e0v1) intersects (e1v0,e1v1).
{
	// Need to specialize this on coord_t, in order to get it
	// correct and avoid overflow.
	compiler_assert(0);
	return -1;
}


template<>
inline bool	edges_intersect_sub(const array<poly_vert<float> >& sorted_verts, int e0v0i, int e0v1i, int e1v0i, int e1v1i)
// Return true if edge (e0v0,e0v1) intersects (e1v0,e1v1).
//
// Specialized for float.
{
	// If e1v0,e1v1 are on opposite sides of e0, and e0v0,e0v1 are
	// on opposite sides of e1, then the segments cross.  These
	// are all determinant checks.

	// The main degenerate case we need to watch out for is if
	// both segments are zero-length.
	//
	// If only one is degenerate, our tests are still OK.

	const vec2<float>&	e0v0 = sorted_verts[e0v0i].m_v;
	const vec2<float>&	e0v1 = sorted_verts[e0v1i].m_v;
	const vec2<float>&	e1v0 = sorted_verts[e1v0i].m_v;
	const vec2<float>&	e1v1 = sorted_verts[e1v1i].m_v;

	// Note: exact equality here.  I think the reason to use
	// epsilons would be underflow in case of very small
	// determinants.  Our determinants are doubles, so I think
	// we're good.
	if (e0v0.x == e0v1.x && e0v0.y == e0v1.y)
	{
		// e0 is zero length.
		if (e1v0.x == e1v1.x && e1v0.y == e1v1.y)
		{
			// Both edges are zero length.
			// They intersect only if they're coincident.
			return e0v0.x == e1v0.x && e0v0.y == e1v0.y;
		}
	}

	// See if e1 crosses line of e0.
	double	det10 = determinant_float(e0v0, e0v1, e1v0);
	double	det11 = determinant_float(e0v0, e0v1, e1v1);

	// Note: we do > 0, which means a vertex on a line counts as
	// intersecting.  In general, if one vert is on the other
	// segment, we have to go searching along the path in either
	// direction to see if it crosses or not, and it gets
	// complicated.  Better to treat it as intersection.

	if (det10 * det11 > 0)
	{
		// e1 doesn't cross the line of e0.
		return false;
	}

	// See if e0 crosses line of e1.
	double	det00 = determinant_float(e1v0, e1v1, e0v0);
	double	det01 = determinant_float(e1v0, e1v1, e0v1);

	if (det00 * det01 > 0)
	{
		// e0 doesn't cross the line of e1.
		return false;
	}

	// They both cross each other; the segments intersect.
	return true;
}


template<>
inline bool	edges_intersect_sub(const array<poly_vert<sint32> >& sorted_verts, int e0v0i, int e0v1i, int e1v0i, int e1v1i)
// Return true if edge (e0v0,e0v1) intersects (e1v0,e1v1).
//
// Specialized for sint32
{
	// If e1v0,e1v1 are on opposite sides of e0, and e0v0,e0v1 are
	// on opposite sides of e1, then the segments cross.  These
	// are all determinant checks.

	// The main degenerate case we need to watch out for is if
	// both segments are zero-length.
	//
	// If only one is degenerate, our tests are still OK.

	const vec2<sint32>&	e0v0 = sorted_verts[e0v0i].m_v;
	const vec2<sint32>&	e0v1 = sorted_verts[e0v1i].m_v;
	const vec2<sint32>&	e1v0 = sorted_verts[e1v0i].m_v;
	const vec2<sint32>&	e1v1 = sorted_verts[e1v1i].m_v;

	if (e0v0.x == e0v1.x && e0v0.y == e0v1.y)
	{
		// e0 is zero length.
		if (e1v0.x == e1v1.x && e1v0.y == e1v1.y)
		{
			// Both edges are zero length.  Treat them as
			// non-coincident (even if they're all on the
			// same point).
			return false;
		}
	}

	// See if e1 crosses line of e0.
	sint64	det10 = determinant_sint32(e0v0, e0v1, e1v0);
	sint64	det11 = determinant_sint32(e0v0, e0v1, e1v1);

	// Note: we do > 0, which means a vertex on a line counts as
	// intersecting.  In general, if one vert is on the other
	// segment, we have to go searching along the path in either
	// direction to see if it crosses or not, and it gets
	// complicated.  Better to treat it as intersection.

	if (det10 * det11 > 0)
	{
		// e1 doesn't cross the line of e0.
		return false;
	}

	// See if e0 crosses line of e1.
	sint64	det00 = determinant_sint32(e1v0, e1v1, e0v0);
	sint64	det01 = determinant_sint32(e1v0, e1v1, e0v1);

	if (det00 * det01 > 0)
	{
		// e0 doesn't cross the line of e1.
		return false;
	}

	// They both cross each other; the segments intersect.
	return true;
}


template<class coord_t>
bool	edges_intersect(const array<poly_vert<coord_t> >& sorted_verts, int e0v0, int e0v1, int e1v0, int e1v1)
// Return true if edge (e0v0,e0v1) intersects (e1v0,e1v1).
{
	// Deal with special case: edges that share exactly one vert.
	// We treat these as no intersection, even though technically
	// they share one point.
	//
	// We're not just comparing indices, because duped verts (for
	// bridges) might have different indices.
	//
	// @@ this needs review -- might be wrong.
	bool	coincident[2][2];
	coincident[0][0] = (sorted_verts[e0v0].m_v == sorted_verts[e1v0].m_v);
	coincident[0][1] = (sorted_verts[e0v0].m_v == sorted_verts[e1v1].m_v);
	coincident[1][0] = (sorted_verts[e0v1].m_v == sorted_verts[e1v0].m_v);
	coincident[1][1] = (sorted_verts[e0v1].m_v == sorted_verts[e1v1].m_v);
	if (coincident[0][0] && !coincident[1][1]) return false;
	if (coincident[1][0] && !coincident[0][1]) return false;
	if (coincident[0][1] && !coincident[1][0]) return false;
	if (coincident[1][1] && !coincident[0][0]) return false;

// @@ eh, I think we really want this to be an intersection
#if 0
	// Both verts identical: early out.
	//
	// Note: treat this as no intersection!  This is mainly useful
	// for things like coincident vertical bridge edges.
	if (coincident[0][0] && coincident[1][1]) return false;
	if (coincident[1][0] && coincident[0][1]) return false;
#endif // 0

	// Check for intersection.
	return edges_intersect_sub(sorted_verts, e0v0, e0v1, e1v0, e1v1);
}



template<class coord_t>
bool	is_convex_vert(const array<poly_vert<coord_t> >& sorted_verts, int vi)
// Return true if vert vi is convex.
{
	const poly_vert<coord_t>*	pvi = &(sorted_verts[vi]);
	const poly_vert<coord_t>*	pv_prev = &(sorted_verts[pvi->m_prev]);
	const poly_vert<coord_t>*	pv_next = &(sorted_verts[pvi->m_next]);

	return vertex_left_test<coord_t>(pv_prev->m_v, pvi->m_v, pv_next->m_v) > 0;
}


template<class coord_t>
struct poly
{
	typedef poly_vert<coord_t> vert_t;

	poly(/*@@ TODO array<vert_t>* sorted_verts*/)
		:
		// @@ TODO m_sorted_verts(sorted_verts),
		m_loop(-1),
		m_leftmost_vert(-1),
		m_vertex_count(0),
		m_ear_count(0),
		m_edge_index(NULL),
		m_reflex_point_index(NULL)
	{
	}

	~poly()
	{
		delete m_edge_index;
		m_edge_index = NULL;

		delete m_reflex_point_index;
		m_reflex_point_index = NULL;
	}

	bool	is_valid(const array<vert_t>& sorted_verts, bool check_consecutive_dupes = true) const;

	// init/prep
	void	append_vert(array<vert_t>* sorted_verts, int vert_index);
	void	remap(const array<int>& remap_table);
	void	remap_for_duped_verts(const array<vert_t>& sorted_verts, int v0, int v1);

	void	init_edge_index(const array<vert_t>& sorted_verts, index_box<coord_t>& bound_of_all_verts);
	int	find_valid_bridge_vert(const array<vert_t>& sorted_verts, int v1);
	void	update_connected_sub_poly(array<vert_t>* sorted_verts, int v_start, int v_stop);
	void	init_for_ear_clipping(array<vert_t>* sorted_verts);

	// Edges are indexed using their first vert (i.e. edge (v1,v2) is indexed using v1)
	void	add_edge(const array<vert_t>& sorted_verts, int vi);
	void	remove_edge(const array<vert_t>& sorted_verts, int vi);

	// tests/queries
	bool	any_edge_intersection(const array<vert_t>& sorted_verts, int external_vert, int v2);
	bool	vert_can_see_cone_a(const array<vert_t>& sorted_verts, int v, int cone_a_vert, int cone_b_vert);
	bool	vert_in_cone(const array<vert_t>& sorted_verts, int vert, int cone_v0, int cone_v1, int cone_v2);
	bool	vert_is_duplicated(const array<vert_t>& sorted_verts, int v0);
	bool	ear_contains_reflex_vertex(const array<vert_t>& sorted_verts, int v0, int v1, int v2);

	void	classify_vert(array<vert_t>* sorted_verts, int vi);
	void	dirty_vert(array<vert_t>* sorted_verts, int vi);

	int	get_vertex_count() const { return m_vertex_count; }
	int	get_ear_count() const { return m_ear_count; }
	int	get_next_ear(const array<vert_t>& sorted_verts, tu_random::generator* rg);
	int	remove_degenerate_chain(array<vert_t>* sorted_verts, int vi);
	void	emit_and_remove_ear(array<coord_t>* result, array<vert_t>* sorted_verts, int v0, int v1, int v2);
	bool	build_ear_list(array<vert_t>* sorted_verts, tu_random::generator* rg);

	void	invalidate(const array<vert_t>& sorted_verts);

//data:
//@@ TODO	array<vert_t>*	m_sorted_verts;
	int	m_loop;	// index of first vert
	int	m_leftmost_vert;
	int	m_vertex_count;
	int	m_ear_count;

	// edge search_index (for finding possibly intersecting edges during bridge finding)
	//
	// The payload stored is the index of the first vert in the edge.
	typedef grid_index_box<coord_t, int>	box_index_t;
	typedef typename box_index_t::iterator ib_iterator;
	grid_index_box<coord_t, int>*	m_edge_index;