// gameswf_fontlib.cpp	-- Thatcher Ulrich <tu@tulrich.com> 2003// This source code has been donated to the Public Domain.  Do// whatever you want with it.// A module to take care of all of gameswf's loaded fonts.#include "base/container.h"#include "base/tu_file.h"#include "gameswf.h"#include "gameswf_font.h"#include "gameswf_impl.h"#include "gameswf_log.h"#include "gameswf_render.h"#include "gameswf_shape.h"#include "gameswf_styles.h"#include "gameswf_tesselate.h"#include "gameswf_render.h"namespace gameswf{namespace fontlib{	array< smart_ptr<font> >	s_fonts;	// Size (in TWIPS) of the box that the glyph should	// stay within.	static float	s_rendering_box = 1536.0f;	// this *should* be 1024, but some glyphs in some fonts exceed it!	// The nominal size of the final antialiased glyphs stored in	// the texture.  This parameter controls how large the very	// largest glyphs will be in the texture; most glyphs will be	// considerably smaller.  This is also the parameter that	// controls the tradeoff between texture RAM usage and	// sharpness of large text.	static int	s_glyph_nominal_size =// You can override the default rendered glyph size in// compatibility_include.h, to trade off memory vs. niceness of large// glyphs.  You can also override this at run-time via// gameswf::fontlib::set_nominal_glyph_pixel_size()#ifndef GAMESWF_FONT_NOMINAL_GLYPH_SIZE_DEFAULT	96#else	GAMESWF_FONT_NOMINAL_GLYPH_SIZE_DEFAULT#endif	;	static const int	OVERSAMPLE_BITS = 2;	static const int	OVERSAMPLE_FACTOR = (1 << OVERSAMPLE_BITS);	// The dimensions of the textures that the glyphs get packed into.	static const int	GLYPH_CACHE_TEXTURE_SIZE = 256;	// How much space to leave around the individual glyph image.	// This should be at least 1.  The bigger it is, the smoother	// the boundaries of minified text will be, but the more	// texture space is wasted.	const int PAD_PIXELS = 3;	// The raw non-antialiased render size for glyphs.	static int	s_glyph_render_size = s_glyph_nominal_size << OVERSAMPLE_BITS;		void	set_nominal_glyph_pixel_size(int pixel_size)	{		static const int	MIN_SIZE = 4;		static const int	MAX_SIZE = GLYPH_CACHE_TEXTURE_SIZE / 2;		if (pixel_size < MIN_SIZE)		{			log_error("set_nominal_glyph_pixel_size(%d) too small, clamping to %d\n",				  pixel_size,				  MIN_SIZE);			pixel_size = MIN_SIZE;		}		else if (pixel_size > MAX_SIZE)		{			log_error("set_nominal_glyph_pixel_size(%d) too large, clamping to %d\n",				  pixel_size,				  MAX_SIZE);			pixel_size = MAX_SIZE;		}		s_glyph_nominal_size = pixel_size;		s_glyph_render_size = s_glyph_nominal_size << OVERSAMPLE_BITS;	}	//	// State for the glyph packer.	//	static Uint8*	s_render_buffer = NULL;	static matrix	s_render_matrix;	static Uint8*	s_current_cache_image = NULL;	// for setting the bitmap_info after they're packed.	struct pending_glyph_info	{		font*	m_source_font;		int	m_glyph_index;		texture_glyph	m_texture_glyph;		pending_glyph_info()			:			m_source_font(NULL),			m_glyph_index(-1)		{		}		pending_glyph_info(font* f, int gi, const texture_glyph& tg)			:			m_source_font(f),			m_glyph_index(gi),			m_texture_glyph(tg)		{		}	};	static array< pending_glyph_info >	s_pending_glyphs;	// Integer-bounded 2D rectangle.	struct recti	{		int	m_x_min, m_x_max, m_y_min, m_y_max;		recti(int x0 = 0, int x1 = 0, int y0 = 0, int y1 = 0)			:			m_x_min(x0),			m_x_max(x1),			m_y_min(y0),			m_y_max(y1)		{		}		bool	is_valid() const		{			return m_x_min <= m_x_max				&& m_y_min <= m_y_max;		}		bool	intersects(const recti& r) const		// Return true if r touches *this.		{			if (m_x_min >= r.m_x_max			    || m_x_max <= r.m_x_min			    || m_y_min >= r.m_y_max			    || m_y_max <= r.m_y_min)			{				// disjoint.				return false;			}			return true;		}		bool	contains(int x, int y) const		// Return true if (x,y) is inside *this.		{			return x >= m_x_min				&& x < m_x_max				&& y >= m_y_min				&& y < m_y_max;		}	};	// Rects already on the texture.	static array<recti>	s_covered_rects;	// 2d integer point.	struct pointi	{		int	m_x, m_y;		pointi(int x = 0, int y = 0)			:			m_x(x),			m_y(y)		{		}		bool	operator<(const pointi& p) const		// For sorting anchor points.		{			return imin(m_x, m_y) < imin(p.m_x, p.m_y);		}	};	// Candidates for upper-left corner of a new rectangle.  Use	// lower-left and upper-right of previously placed rects.	static array<pointi>	s_anchor_points;	static bool	s_saving = false;	static bool	s_save_dummy_bitmaps = false;	static tu_file*	s_file = NULL;	static void	ensure_cache_image_available()	{		if (s_pending_glyphs.size() == 0)		{			// Set up a cache.			if (s_current_cache_image == NULL)			{				s_current_cache_image = new Uint8[GLYPH_CACHE_TEXTURE_SIZE * GLYPH_CACHE_TEXTURE_SIZE];			}			memset(s_current_cache_image, 0, GLYPH_CACHE_TEXTURE_SIZE * GLYPH_CACHE_TEXTURE_SIZE);			// Initialize the coverage data.			s_covered_rects.resize(0);			s_anchor_points.resize(0);			s_anchor_points.push_back(pointi(0, 0));	// seed w/ upper-left of texture.		}	}	void	finish_current_texture(movie_definition_sub* owner)	{		if (s_pending_glyphs.size() == 0)		{			return;		}#if 0		//xxxxxx debug hack -- dump image data to a file		static int	s_seq = 0;		char buffer[100];		sprintf(buffer, "dump%02d.ppm", s_seq);		s_seq++;		FILE*	fp = fopen(buffer, "wb");		if (fp)		{			fprintf(fp, "P6\n%d %d\n255\n", GLYPH_CACHE_TEXTURE_SIZE, GLYPH_CACHE_TEXTURE_SIZE);			for (int i = 0; i < GLYPH_CACHE_TEXTURE_SIZE * GLYPH_CACHE_TEXTURE_SIZE; i++)			{				fputc(s_current_cache_image[i], fp);				fputc(s_current_cache_image[i], fp);				fputc(s_current_cache_image[i], fp);			}			fclose(fp);		}		//xxxxxx#endif // 0		if (s_saving)		// HACK!!!		{			if (s_save_dummy_bitmaps)			{				// Save a mini placeholder bitmap.				s_file->write_le16(1);				s_file->write_le16(1);				s_file->write_byte(0);			}			else			{				int w = GLYPH_CACHE_TEXTURE_SIZE;				int h = GLYPH_CACHE_TEXTURE_SIZE;				// save bitmap size				s_file->write_le16(w);				s_file->write_le16(h);				// save bitmap contents				s_file->write_bytes(s_current_cache_image, w*h);			}		}		smart_ptr<bitmap_info>	bi;		if (owner->get_create_bitmaps() == DO_NOT_LOAD_BITMAPS)		{			bi = render::create_bitmap_info_empty();		}		else		{			bi = render::create_bitmap_info_alpha(				GLYPH_CACHE_TEXTURE_SIZE,				GLYPH_CACHE_TEXTURE_SIZE,				s_current_cache_image);		}		owner->add_bitmap_info(bi.get_ptr());		// Push finished glyphs into their respective fonts.		for (int i = 0, n = s_pending_glyphs.size(); i < n; i++)		{			pending_glyph_info*	pgi = &s_pending_glyphs[i];			assert(pgi->m_glyph_index != -1);			assert(pgi->m_source_font != NULL);			pgi->m_texture_glyph.set_bitmap_info(bi.get_ptr());			pgi->m_source_font->add_texture_glyph(pgi->m_glyph_index, pgi->m_texture_glyph);			//s_pending_glyphs[i]->set_bitmap_info(bi.get_ptr());		}		s_pending_glyphs.clear();	}	bool	is_rect_available(const recti& r)	// Return true if the given rect can be packed into the	// currently active texture.	{		assert(r.is_valid());		assert(r.m_x_min >= 0);		assert(r.m_y_min >= 0);		if (r.m_x_max > GLYPH_CACHE_TEXTURE_SIZE		    || r.m_y_max > GLYPH_CACHE_TEXTURE_SIZE)		{			// Rect overflows the texture bounds.			return false;		}		// Check against existing rects.		for (int i = 0, n = s_covered_rects.size(); i < n; i++)		{			if (r.intersects(s_covered_rects[i]))			{				return false;			}		}		// Spot appears to be open.		return true;	}	void	add_cover_rect(const recti& r)	// Add the given rect to our list.  Eliminate any anchor	// points that are disqualified by this new rect.	{		s_covered_rects.push_back(r);		for (int i = 0; i < s_anchor_points.size(); i++)		{			const pointi&	p = s_anchor_points[i];			if (r.contains(p.m_x, p.m_y))			{				// Eliminate this point from consideration.				s_anchor_points.remove(i);				i--;			}		}	}	void	add_anchor_point(const pointi& p)	// Add point to our list of anchors.  Keep the list sorted.	{		// Add it to end, since we expect new points to be		// relatively greater than existing points.		s_anchor_points.push_back(p);		// Insertion sort -- bubble down into correct spot.		for (int i = s_anchor_points.size() - 2; i >= 0; i--)		{			if (s_anchor_points[i + 1] < s_anchor_points[i])			{				swap(&(s_anchor_points[i]), &(s_anchor_points[i + 1]));			}			else			{				// Done bubbling down.				break;			}		}	}	bool	pack_rectangle(int* px, int* py, int width, int height)	// Find a spot for the rectangle in the current cache image.	// Return true if there's a spot; false if there's no room.	{		// Nice algo, due to JARE:		//		// * keep a list of "candidate points"; initialize it with {0,0}		//		// * each time we add a rect, add its lower-left and		// upper-right as candidate points.		//		// * search the candidate points only, when looking		// for a good spot.  If we find a good one, also try		// scanning left or up as well; sometimes this can		// close some open space.		//		// * when we use a candidate point, remove it from the list.		// Consider candidate spots.		for (int i = 0, n = s_anchor_points.size(); i < n; i++)		{			const pointi&	p = s_anchor_points[i];			recti	r(p.m_x, p.m_x + width, p.m_y, p.m_y + height);			// Is this spot any good?			if (is_rect_available(r))			{				// Good spot.  Scan left to see if we can tighten it up.				while (r.m_x_min > 0)				{					recti	r2(r.m_x_min - 1, r.m_x_min - 1 + width, r.m_y_min, r.m_y_min + height);					if (is_rect_available(r2))					{						// Shift left.						r = r2;					}					else					{						// Not clear; stop scanning.						break;					}				}				// Mark our covered rect; remove newly covered anchors.				add_cover_rect(r);				// Found our desired spot.  Add new				// candidate points to the anchor list.				add_anchor_point(pointi(r.m_x_min, r.m_y_max));	// lower-left				add_anchor_point(pointi(r.m_x_max, r.m_y_min));	// upper-right				*px = r.m_x_min;				*py = r.m_y_min;				return true;			}		}		// Couldn't find a good spot.		return false;	}	// This is for keeping track of our rendered glyphs, before	// packing them into textures and registering with the font.	struct rendered_glyph_info	{		font*	m_source_font;		int	m_glyph_index;		image::alpha*	m_image;		unsigned int	m_image_hash;		float	m_offset_x;		float	m_offset_y;		rendered_glyph_info()			:			m_source_font(0),			m_glyph_index(0),			m_image(0),			m_image_hash(0),			m_offset_x(0),			m_offset_y(0)		{		}	};	static void	software_trapezoid(		float y0, float y1,		float xl0, float xl1,		float xr0, float xr1)	// Fill the specified trapezoid in the software output buffer.	{		assert(s_render_buffer);