triangulate_impl.h

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

		{
			if (sorted_verts[m_loop].m_is_ear)
			{
				random_skip--;
			}
			m_loop = sorted_verts[m_loop].m_next;
		}

		assert(is_valid(sorted_verts));
	}
#endif // RANDOMIZE

	assert(sorted_verts[next_ear].m_is_ear == true);

	return next_ear;
}


template<class coord_t>
void	poly<coord_t>::emit_and_remove_ear(
	array<coord_t>* result,
	array<vert_t>* sorted_verts,
	int v0,
	int v1,
	int v2)
// Push the ear triangle into the output; remove the triangle
// (i.e. vertex v1) from this poly.
{
	assert(is_valid(*sorted_verts));
	assert(m_vertex_count >= 3);

	poly_vert<coord_t>*	pv0 = &(*sorted_verts)[v0];
	poly_vert<coord_t>*	pv1 = &(*sorted_verts)[v1];
	poly_vert<coord_t>*	pv2 = &(*sorted_verts)[v2];

	assert((*sorted_verts)[v1].m_is_ear);

	if (m_loop == v1)
	{
		// Change m_loop, since we're about to lose it.
		m_loop = v0;
	}

	// Make sure m_leftmost_vert is dead; we don't need it now.
	m_leftmost_vert = -1;

	if (vertex_left_test(pv0->m_v, pv1->m_v, pv2->m_v) == 0)
	{
		// Degenerate triangle!  Don't emit it.
		assert(0);	// This should have already been removed by remove_degenerate_chain().
	}
	else
	{
		// emit the vertex list for the triangle.
		result->push_back(pv0->m_v.x);
		result->push_back(pv0->m_v.y);
		result->push_back(pv1->m_v.x);
		result->push_back(pv1->m_v.y);
		result->push_back(pv2->m_v.x);
		result->push_back(pv2->m_v.y);
	}

	// Unlink v1.

	if (pv1->m_convex_result < 0)
	{
		// Vert was reflex (can happen due to e.g. recovery).
		// Remove from reflex vert index.
		assert(m_reflex_point_index);
		ip_iterator it = m_reflex_point_index->find(index_point<coord_t>(pv1->m_v.x, pv1->m_v.y), v1);
		assert(it.at_end() == false);

		m_reflex_point_index->remove(&(*it));
	}

	assert(pv0->m_poly_owner == this);
	assert(pv1->m_poly_owner == this);
	assert(pv2->m_poly_owner == this);

	pv0->m_next = v2;
	pv2->m_prev = v0;

	pv1->m_next = -1;
	pv1->m_prev = -1;
	pv1->m_poly_owner = NULL;

	// We lost v1.
	m_vertex_count--;
	m_ear_count--;

	if (pv0->m_v == pv2->m_v)
	{
		// remove_degenerate_chain() should have taken care of
		// this before we got here.
		assert(0);
	}

	// ear status of v0 and v2 could have changed now.
	dirty_vert(sorted_verts, v0);
	dirty_vert(sorted_verts, v2);

	// Big huge performance boost: recheck these local verts now;
	// often we'll clip them right away.
	//
	// @@ what happens if v0 or v2 are now degenerate???
	classify_vert(sorted_verts, v0);	
	classify_vert(sorted_verts, v2);

	assert(is_valid(*sorted_verts));
}


template<class coord_t>
int	poly<coord_t>::remove_degenerate_chain(array<vert_t>* sorted_verts, int vi)
// Remove the degenerate ear at vi, and any degenerate ear formed as
// we remove the previous one.
//
// Return the index of a vertex just prior to the chain we've removed.
{
	assert(m_leftmost_vert == -1);

	int	retval = vi;

	for (;;)
	{
		assert(is_valid(*sorted_verts, false /* don't check for dupes yet */));

		poly_vert<coord_t>*	pv1 = &(*sorted_verts)[vi];
		poly_vert<coord_t>*	pv0 = &(*sorted_verts)[pv1->m_prev];
		poly_vert<coord_t>*	pv2 = &(*sorted_verts)[pv1->m_next];

		if (m_loop == vi)
		{
			// Change m_loop, since we're about to lose it.
			m_loop = pv0->m_my_index;
		}

		// Unlink vi.

		assert(pv0->m_poly_owner == this);
		assert(pv1->m_poly_owner == this);
		assert(pv2->m_poly_owner == this);

		pv0->m_next = pv2->m_my_index;
		pv2->m_prev = pv0->m_my_index;

		pv1->m_next = -1;
		pv1->m_prev = -1;
		pv1->m_poly_owner = NULL;

		if (pv1->m_convex_result < 0)
		{
			// vi was reflex, remove it from index
			assert(m_reflex_point_index);
			ip_iterator	it =
				m_reflex_point_index->find(index_point<coord_t>(pv1->m_v.x, pv1->m_v.y), vi);
			assert(it.at_end() == false);

			m_reflex_point_index->remove(&(*it));
		}

		if (pv1->m_is_ear)
		{
			m_ear_count--;
		}

		// We lost vi.
		m_vertex_count--;

		assert(is_valid(*sorted_verts, false /* don't check for dupes yet */));

		if (m_vertex_count < 3)
		{
			retval = pv0->m_my_index;
			break;
		}

		// If we've created another degenerate, then remove it as well.
		if (pv0->m_v == pv2->m_v)
		{
			// We've created a dupe in the chain, remove it now.
			vi = pv0->m_my_index;
		}
		else if (vertex_left_test((*sorted_verts)[pv0->m_prev].m_v, pv0->m_v, pv2->m_v) == 0)
		{
			// More degenerate.
			vi = pv0->m_my_index;
		}
		else if (vertex_left_test(pv0->m_v, pv2->m_v, (*sorted_verts)[pv2->m_next].m_v) == 0)
		{
			// More degenerate.
			vi = pv2->m_my_index;
		}
		else
		{
			// ear/reflex status of pv0 & pv2 may have changed.
			dirty_vert(sorted_verts, pv0->m_my_index);
			dirty_vert(sorted_verts, pv2->m_my_index);

			retval = pv0->m_my_index;

			break;
		}
	}

	assert(is_valid(*sorted_verts, true /* do check for dupes; there shouldn't be any! */));

	return retval;
}


template<class coord_t>
void	poly<coord_t>::update_connected_sub_poly(array<vert_t>* sorted_verts, int v_first_in_subloop, int v_first_after_subloop)
// Given the beginning and end of a sub-loop that has just been linked
// into our loop, update the verts on the sub-loop to have the correct
// owner, update our m_leftmost_vert and our m_vert_count.
{
	assert(v_first_in_subloop != v_first_after_subloop);

	int	vi = v_first_in_subloop;
	do
	{
		vert_t*	pv = &(*sorted_verts)[vi];

		pv->m_poly_owner = this;
		m_vertex_count++;

		// Update leftmost vert.
		if (pv->m_my_index < m_leftmost_vert)
		{
			m_leftmost_vert = pv->m_my_index;
		}

		// Insert new edge into the edge index.
		add_edge(*sorted_verts, vi);

		vi = pv->m_next;
	}
	while (vi != v_first_after_subloop);

	assert(is_valid(*sorted_verts));
}



template<class coord_t>
void	poly<coord_t>::init_edge_index(const array<vert_t>& sorted_verts, index_box<coord_t>& bound_of_all_verts)
// Initialize our edge-search structure, for quickly finding possible
// intersecting edges (when constructing bridges to join polys).
{
	assert(is_valid(sorted_verts));
	assert(m_edge_index == NULL);

	// Compute grid density.
	int	x_cells = 1;
	int	y_cells = 1;
	if (sorted_verts.size() > 0)
	{
		const float	GRID_SCALE = sqrtf(0.5f);
		coord_t	width = bound_of_all_verts.get_width();
		coord_t	height = bound_of_all_verts.get_height();
		float	area = float(width) * float(height);
		if (area > 0)
		{
			float	sqrt_n = sqrt((float) sorted_verts.size());
			float	w = width * width / area * GRID_SCALE;
			float	h = height * height / area * GRID_SCALE;
			x_cells = int(w * sqrt_n);
			y_cells = int(h * sqrt_n);
		}
		else
		{
			// Zero area.
			if (width > 0)
			{
				x_cells = int(GRID_SCALE * GRID_SCALE * sorted_verts.size());
			}
			else
			{
				y_cells = int(GRID_SCALE * GRID_SCALE * sorted_verts.size());
			}
		}
		x_cells = iclamp(x_cells, 1, 256);
		y_cells = iclamp(y_cells, 1, 256);
	}
	
	m_edge_index = new grid_index_box<coord_t, int>(bound_of_all_verts, x_cells, y_cells);

	// Insert current edges into the index.
	int	vi = m_loop;
	for (;;)
	{
		add_edge(sorted_verts, vi);

		vi = sorted_verts[vi].m_next;
		if (vi == m_loop)
		{
			break;
		}
	}

	assert(is_valid(sorted_verts));
}


template<class coord_t>
void	poly<coord_t>::init_for_ear_clipping(array<vert_t>* sorted_verts)
// Classify all verts for convexity.
//
// Initialize our point-search structure, for quickly finding reflex
// verts within a potential ear.
{
	assert(is_valid(*sorted_verts));

	// Kill m_leftmost_vert; don't need it once all the polys are
	// joined together into one loop.
	m_leftmost_vert = -1;

	// Kill edge index; we don't need it for ear clipping.
	delete m_edge_index;
	m_edge_index = NULL;

	int	reflex_vert_count = 0;

	bool	bound_inited = false;
	index_box<coord_t>	reflex_bound(index_point<coord_t>(0, 0), index_point<coord_t>(0, 0));

	int	vi = m_loop;
	for (;;)
	{
		// Classify vi as reflex/convex.
		vert_t*	pvi = &(*sorted_verts)[vi];
		pvi->m_convex_result =
			vertex_left_test<coord_t>((*sorted_verts)[pvi->m_prev].m_v, pvi->m_v, (*sorted_verts)[pvi->m_next].m_v);
		
		if (pvi->m_convex_result < 0)
		{
			reflex_vert_count++;

			// Update bounds.
			index_point<coord_t>	location(pvi->m_v.x, pvi->m_v.y);
			if (bound_inited == false)
			{
				bound_inited = true;
				reflex_bound = index_box<coord_t>(location, location);
			}
			else
			{
				reflex_bound.expand_to_enclose(location);
			}
		}

		vi = (*sorted_verts)[vi].m_next;
		if (vi == m_loop)
		{
			break;
		}
	}

	// Compute grid density.  FIST recommends w * sqrt(N) * h *
	// sqrt(N), where w*h is between 0.5 and 2.  (N is the reflex
	// vert count.)
	int	x_cells = 1;
	int	y_cells = 1;
	if (reflex_vert_count > 0)
	{
		const float	GRID_SCALE = sqrtf(0.5f);
		coord_t	width = reflex_bound.get_width();
		coord_t	height = reflex_bound.get_height();
		float	area = float(width) * float(height);
		if (area > 0)
		{
			float	sqrt_n = sqrt((float) reflex_vert_count);
			float	w = width * width / area * GRID_SCALE;
			float	h = height * height / area * GRID_SCALE;
			x_cells = int(w * sqrt_n);
			y_cells = int(h * sqrt_n);
		}
		else
		{
			// Zero area.
			if (width > 0)
			{
				x_cells = int(GRID_SCALE * GRID_SCALE * reflex_vert_count);
			}
			else
			{
				y_cells = int(GRID_SCALE * GRID_SCALE * reflex_vert_count);
			}
		}
		x_cells = iclamp(x_cells, 1, 256);
		y_cells = iclamp(y_cells, 1, 256);
	}
	
	m_reflex_point_index = new grid_index_point<coord_t, int>(reflex_bound, x_cells, y_cells);

	// Insert reflex verts into the index.
	vi = m_loop;
	for (;;)
	{
		vert_t*	pvi = &(*sorted_verts)[vi];
		if (pvi->m_convex_result < 0)
		{
			// Reflex.  Insert it.
			m_reflex_point_index->add(index_point<coord_t>(pvi->m_v.x, pvi->m_v.y), vi);
		}

		vi = (*sorted_verts)[vi].m_next;
		if (vi == m_loop)
		{
			break;
		}
	}

	assert(is_valid(*sorted_verts));
}


template<class coord_t>
void	poly<coord_t>::add_edge(const array<vert_t>& sorted_verts, int vi)
// Insert the edge (vi, vi->m_next) into the index.
{
	index_box<coord_t>	ib(sorted_verts[vi].get_index_point());
	ib.expand_to_enclose(sorted_verts[sorted_verts[vi].m_next].get_index_point());

	assert(m_edge_index);

	// Make sure edge isn't already in the index.
	assert(m_edge_index->find_payload_from_point(sorted_verts[vi].get_index_point(), vi) == NULL);

	m_edge_index->add(ib, vi);
}


template<class coord_t>
void	poly<coord_t>::remove_edge(const array<vert_t>& sorted_verts, int vi)
// Remove the edge (vi, vi->m_next) from the index.
{
	assert(m_edge_index);

 	grid_entry_box<coord_t, int>*	entry = m_edge_index->find_payload_from_point(sorted_verts[vi].get_index_point(), vi);
 	assert(entry);

 	m_edge_index->remove(entry);
}


template<class coord_t>
bool	poly<coord_t>::vert_can_see_cone_a(const array<vert_t>& sorted_verts, int v, int cone_a_vert, int cone_b_vert)
// Return true if v can see cone_a_vert, without logically crossing cone_b.
// cone_a_vert and cone_b_vert are coincident.
{
	assert(sorted_verts[cone_a_vert].m_v == sorted_verts[cone_b_vert].m_v);
	
	// @@ Thought: Would it be more robust to know whether v is
	// part of a ccw or cw loop, and then decide based on the
	// relative insideness/outsideness of v w/r/t the cones?

	// Analyze the two cones, to see if the segment
	// (v,cone_a_vert) is blocked by cone_b_vert.  Since
	// cone_a_vert and cone_b_vert are coincident, we need to
	// figure out the relationship among v and the cones.

	// Sort the cones so that they're in convex order.
	const vert_t*	pa = &sorted_verts[cone_a_vert];
	vec2<coord_t>	cone_a[3] = { sorted_verts[pa->m_prev].m_v, pa->m_v, sorted_verts[pa->m_next].m_v };
	if (vertex_left_test(cone_a[0], cone_a[1], cone_a[2]) < 0)
	{
		swap(&cone_a[0], &cone_a[2]);
	}

	const vert_t*	pb = &sorted_verts[cone_b_vert];
	vec2<coord_t>	cone_b[3] = { sorted_verts[pb->m_prev].m_v, pb->m_v, sorted_verts[pb->m_next].m_v };
	if (vertex_left_test(cone_b[0], cone_b[1], cone_b[2]) < 0)
	{
		swap(&cone_b[0], &cone_b[2]);
	}

	// Characterize the cones w/r/t each other.
	int	a_in_b_sum = 0;
	a_in_b_sum += vertex_left_test(cone_b[0], cone_b[1], cone_a[0]);
	a_in_b_sum += vertex_left_test(cone_b[1], cone_b[2], cone_a[0]);
	a_in_b_sum += vertex_left_test(cone_b[0], cone_b[1], cone_a[2]);