gameswf_tesselate.cpp

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

// gameswf_tesselate.cpp	-- Thatcher Ulrich <[e-mail]> 2003

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

// 2D shape tesselator.  Actually a "trapezoidizer".  Takes line/curve
// segments with a style index, and outputs trapezoids.
//
// Comments on tesselation strategies:
//
// Current method basically works but has some problems.  It's slow,
// it generates lots of triangles where the poly edges are curvy, and
// occasionally it makes a leak around very thin shapes.
//
// Shewchuk's constrained delaunay triangulator: not appropriate for
// rendering; it's big thing is making roundish triangles, at the
// expense of triangle count.  That's the right tradeoff for FEA
// (Shewchuk's main target application), but the wrong tradeoff for
// rendering; we don't have any particular problem with skinny
// triangles.
//
// Something like "A Fast Trapezoidation Technique For Planar
// Polygons".  The key improvement there is to only cut from a
// vertex/event to the nearest adjacent edges, instead of slicing
// across the entire set of active edges.  This sounds good.
//
// Or, "FIST: Fast Industrial-Strength Triangulation of Polygons" by
// Martin Held.  This looks good; application is rasterization.  The
// funny thing here is that they explicitly deal with holes by
// inserting zero-area bridge edges to connect the holes with the
// outer boundary, to make one continuous poly.  This seems a little
// hacky and possibly tricky.
//
// Or, just optimize what we've got.  I took a quick look at the cairo
// project's trapezoider -- it's very similar to ours but seems to do
// its work in-place without resizing the edge list constantly, so it
// should be pretty quick.  They do some high-precision integer voodoo
// in their intercept calculation that I don't 100% understand.
//
//
// Findings re SWF polygons:
//
// (Based on experiments with Flash MX 2004; old movies seem to obey
// these rules as well, as far as I can tell):
//
// * no intersecting edges -- if you make intersections in the tool
// (even by stretching curve segments around), the tool inserts verts
// automatically.
//
// * left-fill and right-fill seem to be randomly selected.
//
// * individual paths (i.e. segment paths with a consistent set of
// fill styles) are not closed
//
// * there's no odd-even insanity; the tool cleans up the poly if you
// try to make self-intersections and flips and such.
//
// * if you duplicate the paths with two fill styles (so every path
// has just one fill style), and reverse the right-fill paths so they
// make left-fill paths, and then join open verts of the same fill
// style, you will be left with a set of non-intersecting closed polys
// with a consistent winding.  I.e. fairly well-behaved.  They may
// have holes though.
//
// Current outlook: Any of "A Fast Trapezoidation", "FIST", or
// cairo-style should work.  FIST will make the fewest tris (since it
// doesn't add any verts).  Current method can be optimized as well --
// can remove intersection checks (they're probably just harmful).
//
// FIST will probably be the most impervious to leaks, since it
// rationally deals with self-intersection by just overlapping parts
// of the tesselated poly.


#include "gameswf_tesselate.h"
#include "gameswf_types.h"
#include "base/utility.h"
#include "base/container.h"
#include <stdlib.h>


namespace gameswf
{
namespace tesselate
{
	// Curve subdivision error tolerance.
	static float	s_tolerance = 1.0f;
	static trapezoid_accepter*	s_accepter = NULL;

	struct fill_segment
	{
		point	m_begin;
		point	m_end;
		int	m_left_style, m_right_style, m_line_style;

		fill_segment() {}

		fill_segment(
			const point& a,
			const point& b,
			int left_style,
			int right_style,
			int line_style)
			:
			m_begin(a),
			m_end(b),
			m_left_style(left_style),
			m_right_style(right_style),
			m_line_style(line_style)
		{
			// For rasterization, we want to ensure that
			// the segment always points towards positive
			// y...
			if (m_begin.m_y > m_end.m_y)
			{
				flip();
			}
		}

		void	flip()
		// Exchange end points, and reverse fill sides.
		{
			swap(&m_begin, &m_end);

			// swap fill styles...
			swap(&m_left_style, &m_right_style);
		}

		float	get_height() const
		// Return segment height.
		{
			assert(m_end.m_y >= m_begin.m_y);

			return m_end.m_y - m_begin.m_y;
		}
	};


	// More Renderer state.
	static array<fill_segment>	s_current_segments;	// @@ should not dynamically resize this thing!
	static array<point>	s_current_path;			// @@ should not dynamically resize this thing!
	static point	s_last_point;
	static int	s_current_left_style;
	static int	s_current_right_style;
	static int	s_current_line_style;
	static bool	s_shape_has_line;	// flag to let us skip the line rendering if no line styles were set when defining the shape.
	static bool	s_shape_has_fill;	// flag to let us skip the fill rendering if no fill styles were set when defining the shape.


	static void	peel_off_and_emit(int i0, int i1, float y0, float y1);


	void	begin_shape(trapezoid_accepter* accepter, float curve_error_tolerance)
	{
		assert(accepter);
		s_accepter = accepter;

		// ensure we're not already in a shape or path.
		// make sure our shape state is cleared out.
		assert(s_current_segments.size() == 0);
		s_current_segments.resize(0);

		assert(s_current_path.size() == 0);
		s_current_path.resize(0);

		assert(curve_error_tolerance > 0);
		if (curve_error_tolerance > 0)
		{
			s_tolerance = curve_error_tolerance;
		}
		else
		{
			s_tolerance = 1.0f;
		}

		s_current_line_style = -1;
		s_current_left_style = -1;
		s_current_right_style = -1;
		s_shape_has_fill = false;
		s_shape_has_line = false;
	}


	static int	compare_segment_y(const void* a, const void* b)
	// For sorting segments by m_begin.m_y, and then by height.
	{
		const fill_segment*	A = (const fill_segment*) a;
		const fill_segment*	B = (const fill_segment*) b;

		const float	ay0 = A->m_begin.m_y;
		const float	by0 = B->m_begin.m_y;

		if (ay0 < by0)
		{
			return -1;
		}
		else if (ay0 == by0)
		{
			const float	ah = A->get_height();
			const float	bh = B->get_height();

			if (ah < bh)
			{
				return -1;
			}
			else if (ah == bh)
			{
				return 0;
			}
			else
			{
				return 1;
			}
		}
		else
		{
			return 1;
		}
	}


	static int	compare_segment_x(const void* a, const void* b)
	// For sorting segments by m_begin.m_x, and then by m_end.m_x.
	{
		const fill_segment*	A = (const fill_segment*) a;
		const fill_segment*	B = (const fill_segment*) b;

		const float	ax0 = A->m_begin.m_x;
		const float	bx0 = B->m_begin.m_x;

		if (ax0 < bx0)
		{
			return -1;
		}
		else if (ax0 == bx0)
		{
			const float	ax1 = A->m_end.m_x;
			const float	bx1 = B->m_end.m_x;

			if (ax1 < bx1)
			{
				return -1;
			}
			else if (ax1 == bx1)
			{
				return 0;
			}
			else
			{
				return 1;
			}
		}
		else
		{
			return 1;
		}
	}


	void	output_current_segments()
	// Draw our shapes and lines, then clear the segment list.
	{
		if (s_shape_has_fill)
		{
			//
			// Output the trapezoids making up the filled shape.
			//

			// sort by begining y (smaller first), then by height (shorter first)
			qsort(
				&s_current_segments[0],
				s_current_segments.size(),
				sizeof(s_current_segments[0]),
				compare_segment_y);
		
			int	base = 0;
			while (base < s_current_segments.size())
			{
				float	ytop = s_current_segments[base].m_begin.m_y;
				int	next_base = base + 1;
				for (;;)
				{
					if (next_base == s_current_segments.size()
					    || s_current_segments[next_base].m_begin.m_y > ytop)
					{
						break;
					}
					next_base++;
				}

				// sort this first part again by y
				qsort(
					&s_current_segments[base],
					next_base - base,
					sizeof(s_current_segments[0]),
					compare_segment_y);

				// s_current_segments[base] through s_current_segments[next_base - 1] is all the segs that start at ytop
				if (next_base >= s_current_segments.size()
				    || s_current_segments[base].m_end.m_y <= s_current_segments[next_base].m_begin.m_y)
				{
					// No segments start between ytop and
					// [base].m_end.m_y, so we can peel
					// off that whole interval and render
					// it right away.
					float	ybottom = s_current_segments[base].m_end.m_y;
					peel_off_and_emit(base, next_base, ytop, ybottom);

					while (base < s_current_segments.size()
					       && s_current_segments[base].m_end.m_y <= ybottom)
					{
						base++;
					}
				}
				else
				{
					float	ybottom = s_current_segments[next_base].m_begin.m_y;
					assert(ybottom > ytop);
					peel_off_and_emit(base, next_base, ytop, ybottom);

					// don't update base; it's still active.
				}
			}
		}
		
		s_current_segments.release();
	}


	void	peel_off_and_emit(int i0, int i1, float y0, float y1)
	// Clip the interval [y0, y1] off of the segments from
	// s_current_segments[i0 through (i1-1)] and emit the clipped
	// trapezoids.  Modifies the values in s_current_segments.
	{
		assert(i0 < i1);

		if (y0 == y1)
		{
			// Don't bother doing any work...
			return;
		}

		// Peel off first.
		array<fill_segment>	slab;	// @@ make this use static storage
		for (int i = i0; i < i1; i++)
		{
			fill_segment*	f = &s_current_segments[i];
			assert(f->m_begin.m_y == y0);
			assert(f->m_end.m_y >= y1);

			float	dy = f->m_end.m_y - f->m_begin.m_y;
			float	t = 1.0f;
			if (dy > 0)
			{
				t = (y1 - f->m_begin.m_y) / dy;
			}
			point	intersection;
			intersection.m_y = y1;
			intersection.m_x = f->m_begin.m_x + (f->m_end.m_x - f->m_begin.m_x) * t;

			// Peel off.
			slab.push_back(*f);
			slab.back().m_end = intersection;

			// Modify segment.
			s_current_segments[i].m_begin = intersection;
		}

		// Sort by x.
		qsort(&slab[0], slab.size(), sizeof(slab[0]), compare_segment_x);

		// Emit the trapezoids in this slab.
		if (slab.size() > 0
		    && slab[0].m_left_style == -1
		    && slab[0].m_right_style >= 0)
		{
			// Reverse sense of polygon fill!  Right fill style is in charge.
			for (int i = 0; i < slab.size() - 1; i++)
			{
				if (slab[i].m_right_style >= 0)
				{
					trapezoid	tr;
					tr.m_y0 = slab[i].m_begin.m_y;
					tr.m_y1 = slab[i].m_end.m_y;
					tr.m_lx0 = slab[i].m_begin.m_x;
					tr.m_lx1 = slab[i].m_end.m_x;
					tr.m_rx0 = slab[i + 1].m_begin.m_x;
					tr.m_rx1 = slab[i + 1].m_end.m_x;
					s_accepter->accept_trapezoid(slab[i].m_right_style, tr);
				}
			}
		}
		else
		{
			for (int i = 0; i < slab.size() - 1; i++)
			{
				if (slab[i].m_left_style >= 0)
				{
					trapezoid	tr;
					tr.m_y0 = slab[i].m_begin.m_y;
					tr.m_y1 = slab[i].m_end.m_y;
					tr.m_lx0 = slab[i].m_begin.m_x;
					tr.m_lx1 = slab[i].m_end.m_x;
					tr.m_rx0 = slab[i + 1].m_begin.m_x;
					tr.m_rx1 = slab[i + 1].m_end.m_x;
					s_accepter->accept_trapezoid(slab[i].m_left_style, tr);
				}
			}
		}
	}


	void	end_shape()
	{
		output_current_segments();

		s_accepter = NULL;

		s_current_path.release();
	}


	void	begin_path(int style_left, int style_right, int line_style, float ax, float ay)
	// This call begins recording a sequence of segments, which
	// all share the same fill & line styles.  Add segments to the
	// shape using add_curve_segment() or add_line_segment(), and
	// call end_path() when you're done with this sequence.
	//
	// Pass in -1 for styles that you want to disable.  Otherwise pass in
	// the integral ID of the style for filling, to the left or right.
	{
		s_current_left_style = style_left;
		s_current_right_style = style_right;
		s_current_line_style = line_style;

		s_last_point.m_x = ax;
		s_last_point.m_y = ay;

		assert(s_current_path.size() == 0);
		s_current_path.resize(0);

		s_current_path.push_back(s_last_point);

		if (style_left != -1 || style_right != -1)
		{
			s_shape_has_fill = true;
		}

		if (line_style != -1)
		{
			s_shape_has_line = true;
		}
	}


	void	add_line_segment(float ax, float ay)
	// Add a line running from the previous anchor point to the
	// given new anchor point.
	{
		point	p(ax, ay);

		// s_current_segments is used for filling shapes.
		s_current_segments.push_back(
			fill_segment(
				s_last_point,
				p,
				s_current_left_style,
				s_current_right_style,
				s_current_line_style));

		s_last_point = p;

		s_current_path.push_back(p);
	}


	static void	curve(float p0x, float p0y, float p1x, float p1y, float p2x, float p2y)
	// Recursive routine to generate bezier curve within tolerance.
	{
#ifndef NDEBUG
		static int	recursion_count = 0;
		recursion_count++;
		if (recursion_count > 500)
		{
			assert(0);	// probably a bug!
		}
#endif // not NDEBUG

		// @@ use struct point in here?

		// Midpoint on line between two endpoints.
		float	midx = (p0x + p2x) * 0.5f;
		float	midy = (p0y + p2y) * 0.5f;

		// Midpoint on the curve.
		float	qx = (midx + p1x) * 0.5f;
		float	qy = (midy + p1y) * 0.5f;

		float	dist = fabsf(midx - qx) + fabsf(midy - qy);

		if (dist < s_tolerance)
		{
			// Emit edge.
//			add_line_segment(qx, qy);
			add_line_segment(p2x, p2y);
		}
		else
		{
			// Error is too large; subdivide.
			curve(p0x, p0y, (p0x + p1x) * 0.5f, (p0y + p1y) * 0.5f, qx, qy);
			curve(qx, qy, (p1x + p2x) * 0.5f, (p1y + p2y) * 0.5f, p2x, p2y);
		}

#ifndef NDEBUG
		recursion_count--;
#endif // not NDEBUG
	}

	
	void	add_curve_segment(float cx, float cy, float ax, float ay)
	// Add a curve segment to the shape.  The curve segment is a
	// quadratic bezier, running from the previous anchor point to
	// the given new anchor point (ax, ay), with (cx, cy) acting
	// as the control point in between.
	{
		// Subdivide, and add line segments...
		curve(s_last_point.m_x, s_last_point.m_y, cx, cy, ax, ay);
	}


	void	end_path()
	// Mark the end of a set of edges that all use the same styles.
	{
		if (s_current_line_style >= 0 && s_current_path.size() > 1)
		{
			//
			// Emit our line.
			//
			s_accepter->accept_line_strip(s_current_line_style, &s_current_path[0], s_current_path.size());
		}

		s_current_path.resize(0);
	}


}	// end namespace tesselate
};	// end namespace gameswf


// Local Variables:
// mode: C++
// c-basic-offset: 8 
// tab-width: 8
// indent-tabs-mode: t
// End: