// gameswf_shape.cpp	-- Thatcher Ulrich <tu@tulrich.com> 2003// This source code has been donated to the Public Domain.  Do// whatever you want with it.// Quadratic bezier outline shapes, the basis for most SWF rendering.#include "gameswf_shape.h"#include "gameswf_impl.h"#include "gameswf_log.h"#include "gameswf_render.h"#include "gameswf_stream.h"#include "gameswf_tesselate.h"#include "base/tu_file.h"#include <float.h>#define DEBUG_DISPLAY_SHAPE_PATHS#ifdef DEBUG_DISPLAY_SHAPE_PATHS	// For debugging only!	bool	gameswf_debug_show_paths = false;#endif // DEBUG_DISPLAY_SHAPE_PATHSnamespace gameswf{	static float	s_curve_max_pixel_error = 1.0f;	void	set_curve_max_pixel_error(float pixel_error)	{		s_curve_max_pixel_error = fclamp(pixel_error, 1e-6f, 1e6f);	}	float	get_curve_max_pixel_error()	{		return s_curve_max_pixel_error;	}	//	// edge	//	edge::edge()		:		m_cx(0), m_cy(0),		m_ax(0), m_ay(0)	{}	edge::edge(float cx, float cy, float ax, float ay)		:		m_cx(cx), m_cy(cy),		m_ax(ax), m_ay(ay)	{	}	void	edge::tesselate_curve() const	// Send this segment to the tesselator.	{		tesselate::add_curve_segment(m_cx, m_cy, m_ax, m_ay);	}	bool	edge::is_straight() const	{		return m_cx == m_ax && m_cy == m_ay;	}	//	// path	//	path::path()		:		m_new_shape(false)	{		reset(0, 0, 0, 0, 0);	}	path::path(float ax, float ay, int fill0, int fill1, int line)	{		reset(ax, ay, fill0, fill1, line);	}	void	path::reset(float ax, float ay, int fill0, int fill1, int line)	// Reset all our members to the given values, and clear our edge list.	{		m_ax = ax;		m_ay = ay;		m_fill0 = fill0;		m_fill1 = fill1;		m_line = line;		m_edges.resize(0);		assert(is_empty());	}	bool	path::is_empty() const	// Return true if we have no edges.	{		return m_edges.size() == 0;	}	bool	path::point_test(float x, float y)	// Point-in-shape test.  Return true if the query point is on the filled	// interior of this shape.	{		if (m_edges.size() <= 0)		{			return false;		}		if (m_fill0 < 0)		{			// No interior fill.						// @@ This isn't quite right due to some paths			// doing double-duty with both fill0 and fill1			// styles.			// TODO: get rid of this stupid fill0/fill1			// business -- a path should always be			// counterclockwise and have one fill.  For			// input paths with fill1, generate a separate			// reversed path with fill set to fill1.			// Group all paths with the same fill into a			// path group; do the point_test on the whole			// group.			return false;		}		// Shoot a horizontal ray from (x,y) to the right, and		// count the number of edge crossings.  An even number		// of crossings means the point is outside; an odd		// number means it's inside.		float x0 = m_ax;		float y0 = m_ay;		int ray_crossings = 0;		for (int i = 0, n = m_edges.size(); i < n; i++)		{			const edge& e = m_edges[i];			float x1 = e.m_ax;			float y1 = e.m_ay;			if (e.is_straight()) {				// Straight-line case.								// See if (x0,y0)-(x1,y1) crosses (x,y)-(infinity,y)							// Does the segment straddle the horizontal ray?				bool cross_up = (y0 < y && y1 >= y);				bool cross_down = (!cross_up) && (y0 > y && y1 <= y);				if (cross_up || cross_down)				{					// Straddles.									// Is the crossing point to the right of x?					float dy = y1 - y0;					// x_intercept = x0 + (x1 - x0) * (y - y0) / dy;					float x_intercept_times_dy = x0 * dy + (x1 - x0) * (y - y0);					float x_times_dy = x * dy;					// text x_intercept > x									// factor out the division; two cases depending on sign of dy					if (cross_up)					{						assert(dy > 0);						if (x_intercept_times_dy > x * dy)						{							ray_crossings++;						}					}					else					{						// dy is negative; reverse the inequality test						assert(dy < 0);						if (x_intercept_times_dy < x * dy)						{							ray_crossings++;						}					}				}			}			else			{				// Curve case.				float cx = e.m_cx;				float cy = e.m_cy;				// Find whether & where the curve crosses y				if ((y0 < y && y1 < y && cy < y)				    || (y0 > y && y1 > y && cy > y))				{					// All above or all below -- no possibility of crossing.				}				else if (x0 < x && x1 < x && cx < x)				{					// All to the left -- no possibility of crossing to the right.				}				else				{					// Find points where the curve crosses y.					// Quadratic bezier is:					//					// p = (1-t)^2 * a0 + 2t(1-t) * c + t^2 * a1					//					// We need to solve for x at y.										// Use the quadratic formula.					// Numerical Recipes suggests this variation:					// q = -0.5 [b +sgn(b) sqrt(b^2 - 4ac)]					// x1 = q/a;  x2 = c/q;					float A = y1 + y0 - 2 * cy;					float B = 2 * (cy - y0);					float C = y0 - y;					float rad = B * B - 4 * A * C;					if (rad < 0)					{						// No real solutions.					}					else					{						float q;						float sqrt_rad = sqrtf(rad);						if (B < 0) {							q = -0.5f * (B - sqrt_rad);						} else {							q = -0.5f * (B + sqrt_rad);						}						// The old-school way.						// float t0 = (-B + sqrt_rad) / (2 * A);						// float t1 = (-B - sqrt_rad) / (2 * A);						if (A != 0)						{							float t0 = q / A;							if (t0 >= 0 && t0 < 1) {								float x_at_t0 =									x0 + 2 * (cx - x0) * t0 + (x1 + x0 - 2 * cx) * t0 * t0;								if (x_at_t0 > x) {									ray_crossings++;								}							}						}						if (q != 0)						{							float t1 = C / q;							if (t1 >= 0 && t1 < 1) {								float x_at_t1 =									x0 + 2 * (cx - x0) * t1 + (x1 + x0 - 2 * cx) * t1 * t1;								if (x_at_t1 > x) {									ray_crossings++;								}							}						}					}				}			}			x0 = x1;			y0 = y1;		}		if (ray_crossings & 1)		{			// Odd number of ray crossings means the point			// is inside the poly.			return true;		}		return false;	}	void	path::tesselate() const	// Push this path into the tesselator.	{		tesselate::begin_path(			m_fill0 - 1,			m_fill1 - 1,			m_line - 1,			m_ax, m_ay);		for (int i = 0; i < m_edges.size(); i++)		{			m_edges[i].tesselate_curve();		}		tesselate::end_path();	}	// Utility.	void	write_coord_array(tu_file* out, const array<Sint16>& pt_array)	// Dump the given coordinate array into the given stream.	{		int	n = pt_array.size();		out->write_le32(n);		for (int i = 0; i < n; i++)		{			out->write_le16((Uint16) pt_array[i]);		}	}	void	read_coord_array(tu_file* in, array<Sint16>* pt_array)	// Read the coordinate array data from the stream into *pt_array.	{		int	n = in->read_le32();		pt_array->resize(n);		for (int i = 0; i < n; i ++)		{			(*pt_array)[i] = (Sint16) in->read_le16();		}	}	//	// mesh	//		mesh::mesh()	{	}	void	mesh::set_tri_strip(const point pts[], int count)	{		m_triangle_strip.resize(count * 2);	// 2 coords per point				// convert to ints.		for (int i = 0; i < count; i++)		{			m_triangle_strip[i * 2] = Sint16(pts[i].m_x);			m_triangle_strip[i * 2 + 1] = Sint16(pts[i].m_y);		}//		m_triangle_strip.resize(count);//		memcpy(&m_triangle_strip[0], &pts[0], count * sizeof(point));	}	void	mesh::display(const base_fill_style& style, float ratio) const	{		// pass mesh to renderer.		if (m_triangle_strip.size() > 0)		{			style.apply(0, ratio);			render::draw_mesh_strip(&m_triangle_strip[0], m_triangle_strip.size() >> 1);		}	}	void	mesh::output_cached_data(tu_file* out)	// Dump our data to *out.	{		write_coord_array(out, m_triangle_strip);	}		void	mesh::input_cached_data(tu_file* in)	// Slurp our data from *out.	{		read_coord_array(in, &m_triangle_strip);	}	//	// line_strip	//	line_strip::line_strip()	// Default constructor, for array<>.		:		m_style(-1)	{}	line_strip::line_strip(int style, const point coords[], int coord_count)	// Construct the line strip (polyline) made up of the given sequence of points.		:		m_style(style)	{		assert(style >= 0);		assert(coords != NULL);		assert(coord_count > 1);//		m_coords.resize(coord_count);//		memcpy(&m_coords[0], coords, coord_count * sizeof(coords[0]));		m_coords.resize(coord_count * 2);	// 2 coords per vert				// convert to ints.		for (int i = 0; i < coord_count; i++)		{			m_coords[i * 2] = Sint16(coords[i].m_x);			m_coords[i * 2 + 1] = Sint16(coords[i].m_y);		}	}	void	line_strip::display(const base_line_style& style, float ratio) const	// Render this line strip in the given style.	{		assert(m_coords.size() > 1);		assert((m_coords.size() & 1) == 0);		style.apply(ratio);		render::draw_line_strip(&m_coords[0], m_coords.size() >> 1);	}	void	line_strip::output_cached_data(tu_file* out)	// Dump our data to *out.	{		out->write_le32(m_style);		write_coord_array(out, m_coords);	}		void	line_strip::input_cached_data(tu_file* in)	// Slurp our data from *out.	{		m_style = in->read_le32();		read_coord_array(in, &m_coords);	}	// Utility: very simple greedy tri-stripper.  Useful for	// stripping the stacks of trapezoids that come out of our	// tesselator.	struct tri_stripper	{		// A set of strips; we'll join them together into one		// strip during the flush.		array< array<point> >	m_strips;		int	m_last_strip_used;		tri_stripper()			: m_last_strip_used(-1)		{		}		void	add_trapezoid(const point& l0, const point& r0, const point& l1, const point& r1)		// Add two triangles to our strip.		{			// See if we can attach this mini-strip to an existing strip.			if (l0.bitwise_equal(r0) == false)			{				// Check the next strip first; trapezoids will				// tend to arrive in rotating order through				// the active strips.				assert(m_last_strip_used >= -1 && m_last_strip_used < m_strips.size());				int i = m_last_strip_used + 1, n = m_strips.size();				for ( ; i < n; i++)				{					array<point>&	str = m_strips[i];					assert(str.size() >= 3);	// should have at least one tri already.									int	last = str.size() - 1;					if (str[last - 1].bitwise_equal(l0) && str[last].bitwise_equal(r0))					{						// Can join these tris to this strip.						str.push_back(l1);						str.push_back(r1);