triangulate_impl.h

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

		int	original_index = m_sorted_verts[new_index].m_my_index;
		vert_remap[original_index] = new_index;
	}
	{for (int i = 0, n = m_sorted_verts.size(); i < n; i++)
	{
		m_sorted_verts[i].remap(vert_remap);
	}}
	{for (int i = 0, n = m_polys.size(); i < n; i++)
	{
		m_polys[i]->remap(vert_remap);
		assert(m_polys[i]->is_valid(m_sorted_verts));
	}}
}


template<class coord_t>
void	poly_env<coord_t>::join_paths_into_one_poly()
// Use zero-area bridges to connect separate polys & islands into one
// big continuous poly.
{
	// Connect separate paths with bridge edges, into one big path.
	//
	// Bridges are zero-area regions that connect a vert on each
	// of two paths.
	if (m_polys.size() > 1)
	{
		// Sort polys in order of each poly's leftmost vert.
		qsort(&m_polys[0], m_polys.size(), sizeof(m_polys[0]), compare_polys_by_leftmost_vert<coord_t>);
		assert(m_polys.size() <= 1
		       || compare_polys_by_leftmost_vert<coord_t>((void*) &m_polys[0], (void*) &m_polys[1]) == -1);

		// assume that the enclosing boundary is the leftmost
		// path; this is true if the regions are valid and
		// don't intersect.
		poly<coord_t>*	full_poly = m_polys[0];

		full_poly->init_edge_index(m_sorted_verts, m_bound);

		// Iterate from left to right
		while (m_polys.size() > 1)
		{
			int	v1 = m_polys[1]->m_leftmost_vert;

			//     find v2 in full_poly, such that:
			//       v2 is to the left of v1,
			//       and v1-v2 seg doesn't intersect any other edges

			//     // (note that since v1 is next-most-leftmost, v1-v2 can't
			//     // hit anything in p, or any paths further down the list,
			//     // it can only hit edges in full_poly) (need to think
			//     // about equality cases)
			//
			int	v2 = full_poly->find_valid_bridge_vert(m_sorted_verts, v1);

			//     once we've found v1 & v2, we use it to make a bridge,
			//     inserting p into full_poly
			//
			assert(m_sorted_verts[v2].m_poly_owner == m_polys[0]);
			assert(m_sorted_verts[v1].m_poly_owner == m_polys[1]);
			join_paths_with_bridge(full_poly, m_polys[1], v2, v1);

			// Drop the joined poly.
			delete m_polys[1];
			m_polys.remove(1);
		}
	}

	m_polys[0]->init_for_ear_clipping(&m_sorted_verts);

	assert(m_polys.size() == 1);
	// assert(all verts in m_sorted_verts have m_polys[0] as their owner);
}


template<class coord_t>
void	poly_env<coord_t>::join_paths_with_bridge(
	poly<coord_t>* main_poly,
	poly<coord_t>* sub_poly,
	int vert_on_main_poly,
	int vert_on_sub_poly)
// Absorb the sub-poly into the main poly, using a zero-area bridge
// between the two given verts.
{
	assert(vert_on_main_poly != vert_on_sub_poly);
	assert(main_poly != NULL);
	assert(sub_poly != NULL);
	assert(main_poly != sub_poly);
	assert(main_poly == m_sorted_verts[vert_on_main_poly].m_poly_owner);
	assert(sub_poly == m_sorted_verts[vert_on_sub_poly].m_poly_owner);

	if (m_sorted_verts[vert_on_main_poly].m_v == m_sorted_verts[vert_on_sub_poly].m_v)
	{
		// Special case: verts to join are coincident.  We
		// don't actually need to make a bridge with new
		// verts; we only need to adjust the links and do
		// fixup.
		poly_vert<coord_t>*	pv_main = &m_sorted_verts[vert_on_main_poly];
		poly_vert<coord_t>*	pv_sub = &m_sorted_verts[vert_on_sub_poly];

		int	main_next = pv_main->m_next;

		// Remove the edge we're about to break.
		main_poly->remove_edge(m_sorted_verts, vert_on_main_poly);

		pv_main->m_next = pv_sub->m_next;
		m_sorted_verts[pv_main->m_next].m_prev = vert_on_main_poly;

		pv_sub->m_next = main_next;
		m_sorted_verts[main_next].m_prev = vert_on_sub_poly;

		// Add edge that connects to sub poly.
		main_poly->add_edge(m_sorted_verts, vert_on_main_poly);

		// Fixup sub poly so it's now properly a part of the main poly.
		main_poly->update_connected_sub_poly(&m_sorted_verts, pv_main->m_next, main_next);
		sub_poly->invalidate(m_sorted_verts);

		return;
	}

	// Normal case, need to dupe verts and create zero-area bridge.
	dupe_two_verts(vert_on_main_poly, vert_on_sub_poly);

	// Fixup the old indices to account for the new dupes.
	if (vert_on_sub_poly < vert_on_main_poly)
	{
		vert_on_main_poly++;
	}
	else
	{
		vert_on_sub_poly++;
	}

	poly_vert<coord_t>*	pv_main = &m_sorted_verts[vert_on_main_poly];
	poly_vert<coord_t>*	pv_sub = &m_sorted_verts[vert_on_sub_poly];
	poly_vert<coord_t>*	pv_main2 = &m_sorted_verts[vert_on_main_poly + 1];
	poly_vert<coord_t>*	pv_sub2 = &m_sorted_verts[vert_on_sub_poly + 1];

	// Remove the edge we're about to break.
	main_poly->remove_edge(m_sorted_verts, vert_on_main_poly);

	// Link the loops together.
	pv_main2->m_next = pv_main->m_next;
	pv_main2->m_prev = vert_on_sub_poly + 1;	// (pv_sub2)
	m_sorted_verts[pv_main2->m_next].m_prev = pv_main2->m_my_index;

	pv_sub2->m_prev = pv_sub->m_prev;
	pv_sub2->m_next = vert_on_main_poly + 1;	// (pv_main2)
	m_sorted_verts[pv_sub2->m_prev].m_next = pv_sub2->m_my_index;

	pv_main->m_next = vert_on_sub_poly;		// (pv_sub)
	pv_sub->m_prev = vert_on_main_poly;		// (pv_main)

	// Add edge that connects to sub poly.
	main_poly->add_edge(m_sorted_verts, vert_on_main_poly);

	// Fixup sub poly so it's now properly a part of the main poly.
	main_poly->update_connected_sub_poly(&m_sorted_verts, vert_on_sub_poly, pv_main2->m_next);
	sub_poly->invalidate(m_sorted_verts);

	assert(pv_main->m_poly_owner->is_valid(m_sorted_verts));
}


template<class coord_t>
void	poly_env<coord_t>::dupe_two_verts(int v0, int v1)
// Duplicate the two indexed verts, remapping polys & verts as necessary.
{
	// Order the verts.
	if (v0 > v1)
	{
		swap(&v0, &v1);
	}
	assert(v0 < v1);

	// Duplicate verts.
	poly_vert<coord_t>	v0_copy = m_sorted_verts[v0];
	poly_vert<coord_t>	v1_copy = m_sorted_verts[v1];

	// @@ This stuff can be costly!  E.g. lots of separate little
	// polys that need bridges, with a high total vert count.

	// Slower, clearer code to insert the two new verts.  This
	// ends up moving the data between ((v1+1), end) twice.
	if (0) {
		// Insert v1 first, so v0 doesn't get moved.
		m_sorted_verts.insert(v1 + 1, v1_copy);
		m_sorted_verts.insert(v0 + 1, v0_copy);
	}
	else
	// Faster, more obfuscated code to insert the two new verts.
	//
	// NOTE: I tried doing this in one pass, with a complicated
	// explicit move & remap in the same pass.  It was much
	// slower!  (VC7, Win2K.)  memmove() must be magical?
	{
		// Make room.
		m_sorted_verts.resize(m_sorted_verts.size() + 2);

		// Move the two subsegments.
		memmove(&m_sorted_verts[v1 + 3], &m_sorted_verts[v1 + 1], sizeof(m_sorted_verts[0]) * (m_sorted_verts.size() - 3 - v1));
		memmove(&m_sorted_verts[v0 + 2], &m_sorted_verts[v0 + 1], sizeof(m_sorted_verts[0]) * (v1 - v0));

		// Insert the new duplicate verts.
		m_sorted_verts[v0 + 1] = v0_copy;
		m_sorted_verts[v1 + 2] = v1_copy;
	}

	// Remap the indices within the verts.
	for (int i = 0, n = m_sorted_verts.size(); i < n; i++)
	{
		m_sorted_verts[i].m_my_index = i;
		m_sorted_verts[i].m_next = remap_index_for_duped_verts(m_sorted_verts[i].m_next, v0, v1);
		m_sorted_verts[i].m_prev = remap_index_for_duped_verts(m_sorted_verts[i].m_prev, v0, v1);
	}

	// Remap the polys.
	{for (int i = 0, n = m_polys.size(); i < n; i++)
	{
		m_polys[i]->remap_for_duped_verts(m_sorted_verts, v0, v1);

		assert(m_polys[i]->is_valid(m_sorted_verts));
	}}
}


//
// Helpers.
//


template<class coord_t>
static void	recovery_process(
	array<poly<coord_t>*>* polys,	// polys waiting to be processed
	poly<coord_t>* P,	// current poly
	array<poly_vert<coord_t> >* sorted_verts,
	tu_random::generator* rg);


template<class coord_t>
inline void	debug_emit_poly_loop(
	array<coord_t>* result,
	const array<poly_vert<coord_t> >& sorted_verts,
	poly<coord_t>* P)
// Fill *result with a poly loop representing P.
{
	result->resize(0);	// clear existing junk.

	int	first_vert = P->m_loop;
	int	vi = first_vert;
	do
	{
		result->push_back(sorted_verts[vi].m_v.x);
		result->push_back(sorted_verts[vi].m_v.y);
		vi = sorted_verts[vi].m_next;
	}
	while (vi != first_vert);

	// Loop back to beginning, and pad to a multiple of 3 coords.
	do
	{
		result->push_back(sorted_verts[vi].m_v.x);
		result->push_back(sorted_verts[vi].m_v.y);
	}
	while (result->size() % 6);
}


template<class coord_t>
static void compute_triangulation(
	array<coord_t>* result,
	int path_count,
	const array<coord_t> paths[],
	int debug_halt_step,
	array<coord_t>* debug_remaining_loop)
// Compute triangulation.
//
// The debug_ args are optional; they're for terminating early and
// returning the remaining loop to be triangulated.
{
	if (path_count <= 0)
	{
		// Empty paths --> no triangles to emit.
		return;
	}

#ifdef PROFILE_TRIANGULATE
	uint64	start_ticks = tu_timer::get_profile_ticks();
#endif // PROFILE_TRIANGULATE

	// Local generator, for some parts of the algo that need random numbers.
	tu_random::generator	rand_gen;

	// Poly environment; most of the state of the algo.
	poly_env<coord_t>	penv;

	penv.init(path_count, paths);

	penv.join_paths_into_one_poly();

	result->reserve(2 * 3 * penv.get_estimated_triangle_count());

	int	input_vert_count = 0;
	if (penv.m_polys.size() > 0)
	{
		input_vert_count = penv.m_polys[0]->get_vertex_count();
	}

#ifdef PROFILE_TRIANGULATE
	uint64	join_ticks = tu_timer::get_profile_ticks();
	fprintf(stderr, "join poly = %1.6f sec\n", tu_timer::profile_ticks_to_seconds(join_ticks - start_ticks));
#endif // PROFILE_TRIANGULATE

// Debugging only: dump coords of joined poly.
//#define DUMP_JOINED_POLY
#ifdef DUMP_JOINED_POLY
	{
		int	first_vert = penv.m_polys[0]->m_loop;
		int	vi = first_vert;
		do
		{
			printf("%f, %f\n", penv.m_sorted_verts[vi].m_v.x, penv.m_sorted_verts[vi].m_v.y);
			vi = penv.m_sorted_verts[vi].m_next;
		}
		while (vi != first_vert);
	}
#endif

// Debugging only: just emit our joined poly, without triangulating.
//#define EMIT_JOINED_POLY
#ifdef EMIT_JOINED_POLY
	{
		int	first_vert = penv.m_polys[0]->m_loop;
		int	vi = first_vert;
		do
		{
			result->push_back(penv.m_sorted_verts[vi].m_v.x);
			result->push_back(penv.m_sorted_verts[vi].m_v.y);
			vi = penv.m_sorted_verts[vi].m_next;
		}
		while (vi != first_vert);

		// Loop back to beginning, and pad to a multiple of 3 coords.
		do
		{
			result->push_back(penv.m_sorted_verts[vi].m_v.x);
			result->push_back(penv.m_sorted_verts[vi].m_v.y);
		}
		while (result->size() % 6);
	}

	return;
#endif // EMIT_JOINED_POLY

	// ear-clip, adapted from FIST paper:
	//
	//   list<poly> L;
	//   L.insert(full_poly)
	//   while L not empty:
	//     P = L.pop()
	//     Q = priority queue of ears of P
	//     while P.vert_count > 3 do:
	//       if Q not empty:
	//         e = Q.pop
	//         emit e
	//         update P by deleting e
	//       else if an ear was clipped in previous pass then:
	//         Q = priority queue of ears of P (i.e. reexamine P)
	//       else
	//         // we're stuck
	//         recovery_process()	// do something drastic to make the next move
	//     emit last 3 verts of P as the final triangle

	while (penv.m_polys.size())
	{
		poly<coord_t>*	P = penv.m_polys.back();
		penv.m_polys.pop_back();

		P->build_ear_list(&penv.m_sorted_verts, &rand_gen);

		bool	ear_was_clipped = false;
		while (P->get_vertex_count() > 3)
		{
			if (P->get_ear_count() > 0)
			{
				// Clip the next ear from Q.
				int	v1 = P->get_next_ear(penv.m_sorted_verts, &rand_gen);
				int	v0 = penv.m_sorted_verts[v1].m_prev;
				int	v2 = penv.m_sorted_verts[v1].m_next;

				P->emit_and_remove_ear(result, &penv.m_sorted_verts, v0, v1, v2);
				ear_was_clipped = true;

				// For debugging -- terminate early if the debug counter hits zero.
				debug_halt_step--;
				if (debug_halt_step == 0) {
					if (debug_remaining_loop) {
						debug_emit_poly_loop(debug_remaining_loop, penv.m_sorted_verts, P);
					}
					return;
				}
			}
			else if (ear_was_clipped == true)
			{
				// Re-examine P for new ears.
				ear_was_clipped = P->build_ear_list(&penv.m_sorted_verts, &rand_gen);
			}
			else
			{
				// No valid ears; we're in trouble so try some fallbacks.

#if 1
				// xxx hack for debugging: show the state of P when we hit the recovery process.
				debug_emit_poly_loop(result, penv.m_sorted_verts, P);
				return;
#endif

				recovery_process(&penv.m_polys, P, &penv.m_sorted_verts, &rand_gen);
				ear_was_clipped = false;
			}
		}

		if (P->get_vertex_count() == 3)
		{
			// Emit the final triangle.
			if (penv.m_sorted_verts[P->m_loop].m_is_ear == false)
			{
				// Force an arbitrary vert to be an ear.
				penv.m_sorted_verts[P->m_loop].m_is_ear = true;
				P->m_ear_count++;
			}
			P->emit_and_remove_ear(
				result,
				&penv.m_sorted_verts,
				penv.m_sorted_verts[P->m_loop].m_prev,
				P->m_loop,
				penv.m_sorted_verts[P->m_loop].m_next);
		}
		delete P;
	}
	
#ifdef PROFILE_TRIANGULATE
	uint64	clip_ticks = tu_timer::get_profile_ticks();
	fprintf(stderr, "clip poly = %1.6f sec\n", tu_timer::profile_ticks_to_seconds(clip_ticks - join_ticks));
	fprintf(stderr, "total for poly = %1.6f sec\n", tu_timer::profile_ticks_to_seconds(clip_ticks - start_ticks));
	fprintf(stderr, "vert count = %d, verts clipped / sec = %f\n",
		input_vert_count,
		input_vert_count / tu_timer::profile_ticks_to_seconds(clip_ticks - join_ticks));
#endif // PROFILE_TRIANGULATE

	assert(penv.m_polys.size() == 0);
	// assert(for all penv.m_sorted_verts: owning poly == NULL);

	assert((result->size() % 6) == 0);
}


template<class coord_t>
void	recovery_process(
	array<poly<coord_t>*>* polys,
	poly<coord_t>* P,
	array<poly_vert<coord_t> >* sorted_verts,
	tu_random::generator* rg)
{
	// recovery_process:
	//   if two edges in P, e[i-1] and e[i+1] intersect:
	//     insert two tris incident on e[i-1] & e[i+1] as ears into Q
	//   else if P can be split with a valid diagonal:
	//     P = one side
	//     L += the other side
	//     Q = ears of P
	//   else if P has any convex vertex:
	//     pick a random convex vert and add it to Q
	//   else
	//     pick a random vert and add it to Q

	// Case 1: two edges, e[i-1] and e[i+1], intersect; we insert
	// the overlapping ears into Q and resume.
	{for (int vi = (*sorted_verts)[P->m_loop].m_next; vi != P->m_loop; vi = (*sorted_verts)[vi].m_next)
	{
		int	ev0 = vi;
		int	ev1 = (*sort