WebSVN – Kolibri OS – Blame – /contrib/sdk/sources/freetype/src/base/ftbbox.c

Rev	Author	Line No.	Line
4349	Serge	1	/***************************************************************************/
		2	/* */
		3	/* ftbbox.c */
		4	/* */
		5	/* FreeType bbox computation (body). */
		6	/* */
		7	/* Copyright 1996-2002, 2004, 2006, 2010, 2013 by */
		8	/* David Turner, Robert Wilhelm, and Werner Lemberg. */
		9	/* */
		10	/* This file is part of the FreeType project, and may only be used */
		11	/* modified and distributed under the terms of the FreeType project */
		12	/* license, LICENSE.TXT. By continuing to use, modify, or distribute */
		13	/* this file you indicate that you have read the license and */
		14	/* understand and accept it fully. */
		15	/* */
		16	/***************************************************************************/
		17
		18
		19	/*************************************************************************/
		20	/* */
		21	/* This component has a _single_ role: to compute exact outline bounding */
		22	/* boxes. */
		23	/* */
		24	/*************************************************************************/
		25
		26
		27	#include
		28	#include FT_INTERNAL_DEBUG_H
		29
		30	#include FT_BBOX_H
		31	#include FT_IMAGE_H
		32	#include FT_OUTLINE_H
		33	#include FT_INTERNAL_CALC_H
		34	#include FT_INTERNAL_OBJECTS_H
		35
		36
		37	typedef struct TBBox_Rec_
		38	{
		39	FT_Vector last;
		40	FT_BBox bbox;
		41
		42	} TBBox_Rec;
		43
		44
		45	/*************************************************************************/
		46	/* */
		47	/* */
		48	/* BBox_Move_To */
		49	/* */
		50	/* */
		51	/* This function is used as a `move_to' and `line_to' emitter during */
		52	/* FT_Outline_Decompose(). It simply records the destination point */
		53	/* in `user->last'; no further computations are necessary since we */
		54	/* use the cbox as the starting bbox which must be refined. */
		55	/* */
		56	/* */
		57	/* to :: A pointer to the destination vector. */
		58	/* */
		59	/* */
		60	/* user :: A pointer to the current walk context. */
		61	/* */
		62	/* */
		63	/* Always 0. Needed for the interface only. */
		64	/* */
		65	static int
		66	BBox_Move_To( FT_Vector* to,
		67	TBBox_Rec* user )
		68	{
		69	user->last = *to;
		70
		71	return 0;
		72	}
		73
		74
		75	#define CHECK_X( p, bbox ) \
		76	( p->x < bbox.xMin \|\| p->x > bbox.xMax )
		77
		78	#define CHECK_Y( p, bbox ) \
		79	( p->y < bbox.yMin \|\| p->y > bbox.yMax )
		80
		81
		82	/*************************************************************************/
		83	/* */
		84	/* */
		85	/* BBox_Conic_Check */
		86	/* */
		87	/* */
		88	/* Finds the extrema of a 1-dimensional conic Bezier curve and update */
		89	/* a bounding range. This version uses direct computation, as it */
		90	/* doesn't need square roots. */
		91	/* */
		92	/* */
		93	/* y1 :: The start coordinate. */
		94	/* */
		95	/* y2 :: The coordinate of the control point. */
		96	/* */
		97	/* y3 :: The end coordinate. */
		98	/* */
		99	/* */
		100	/* min :: The address of the current minimum. */
		101	/* */
		102	/* max :: The address of the current maximum. */
		103	/* */
		104	static void
		105	BBox_Conic_Check( FT_Pos y1,
		106	FT_Pos y2,
		107	FT_Pos y3,
		108	FT_Pos* min,
		109	FT_Pos* max )
		110	{
		111	if ( y1 <= y3 && y2 == y1 ) /* flat arc */
		112	goto Suite;
		113
		114	if ( y1 < y3 )
		115	{
		116	if ( y2 >= y1 && y2 <= y3 ) /* ascending arc */
		117	goto Suite;
		118	}
		119	else
		120	{
		121	if ( y2 >= y3 && y2 <= y1 ) /* descending arc */
		122	{
		123	y2 = y1;
		124	y1 = y3;
		125	y3 = y2;
		126	goto Suite;
		127	}
		128	}
		129
		130	y1 = y3 = y1 - FT_MulDiv( y2 - y1, y2 - y1, y1 - 2*y2 + y3 );
		131
		132	Suite:
		133	if ( y1 < min ) min = y1;
		134	if ( y3 > max ) max = y3;
		135	}
		136
		137
		138	/*************************************************************************/
		139	/* */
		140	/* */
		141	/* BBox_Conic_To */
		142	/* */
		143	/* */
		144	/* This function is used as a `conic_to' emitter during */
		145	/* FT_Outline_Decompose(). It checks a conic Bezier curve with the */
		146	/* current bounding box, and computes its extrema if necessary to */
		147	/* update it. */
		148	/* */
		149	/* */
		150	/* control :: A pointer to a control point. */
		151	/* */
		152	/* to :: A pointer to the destination vector. */
		153	/* */
		154	/* */
		155	/* user :: The address of the current walk context. */
		156	/* */
		157	/* */
		158	/* Always 0. Needed for the interface only. */
		159	/* */
		160	/* */
		161	/* In the case of a non-monotonous arc, we compute directly the */
		162	/* extremum coordinates, as it is sufficiently fast. */
		163	/* */
		164	static int
		165	BBox_Conic_To( FT_Vector* control,
		166	FT_Vector* to,
		167	TBBox_Rec* user )
		168	{
		169	/* we don't need to check `to' since it is always an `on' point, thus */
		170	/* within the bbox */
		171
		172	if ( CHECK_X( control, user->bbox ) )
		173	BBox_Conic_Check( user->last.x,
		174	control->x,
		175	to->x,
		176	&user->bbox.xMin,
		177	&user->bbox.xMax );
		178
		179	if ( CHECK_Y( control, user->bbox ) )
		180	BBox_Conic_Check( user->last.y,
		181	control->y,
		182	to->y,
		183	&user->bbox.yMin,
		184	&user->bbox.yMax );
		185
		186	user->last = *to;
		187
		188	return 0;
		189	}
		190
		191
		192	/*************************************************************************/
		193	/* */
		194	/* */
		195	/* BBox_Cubic_Check */
		196	/* */
		197	/* */
		198	/* Finds the extrema of a 1-dimensional cubic Bezier curve and */
		199	/* updates a bounding range. This version uses splitting because we */
		200	/* don't want to use square roots and extra accuracy. */
		201	/* */
		202	/* */
		203	/* p1 :: The start coordinate. */
		204	/* */
		205	/* p2 :: The coordinate of the first control point. */
		206	/* */
		207	/* p3 :: The coordinate of the second control point. */
		208	/* */
		209	/* p4 :: The end coordinate. */
		210	/* */
		211	/* */
		212	/* min :: The address of the current minimum. */
		213	/* */
		214	/* max :: The address of the current maximum. */
		215	/* */
		216
		217	#if 0
		218
		219	static void
		220	BBox_Cubic_Check( FT_Pos p1,
		221	FT_Pos p2,
		222	FT_Pos p3,
		223	FT_Pos p4,
		224	FT_Pos* min,
		225	FT_Pos* max )
		226	{
		227	FT_Pos q1, q2, q3, q4;
		228
		229
		230	q1 = p1;
		231	q2 = p2;
		232	q3 = p3;
		233	q4 = p4;
		234
		235	/* for a conic segment to possibly reach new maximum */
		236	/* one of its off-points must be above the current value */
		237	while ( q2 > max \|\| q3 > max )
		238	{
		239	/* determine which half contains the maximum and split */
		240	if ( q1 + q2 > q3 + q4 ) /* first half */
		241	{
		242	q4 = q4 + q3;
		243	q3 = q3 + q2;
		244	q2 = q2 + q1;
		245	q4 = q4 + q3;
		246	q3 = q3 + q2;
		247	q4 = ( q4 + q3 ) / 8;
		248	q3 = q3 / 4;
		249	q2 = q2 / 2;
		250	}
		251	else /* second half */
		252	{
		253	q1 = q1 + q2;
		254	q2 = q2 + q3;
		255	q3 = q3 + q4;
		256	q1 = q1 + q2;
		257	q2 = q2 + q3;
		258	q1 = ( q1 + q2 ) / 8;
		259	q2 = q2 / 4;
		260	q3 = q3 / 2;
		261	}
		262
		263	/* check if either end reached the maximum */
		264	if ( q1 == q2 && q1 >= q3 )
		265	{
		266	*max = q1;
		267	break;
		268	}
		269	if ( q3 == q4 && q2 <= q4 )
		270	{
		271	*max = q4;
		272	break;
		273	}
		274	}
		275
		276	q1 = p1;
		277	q2 = p2;
		278	q3 = p3;
		279	q4 = p4;
		280
		281	/* for a conic segment to possibly reach new minimum */
		282	/* one of its off-points must be below the current value */
		283	while ( q2 < min \|\| q3 < min )
		284	{
		285	/* determine which half contains the minimum and split */
		286	if ( q1 + q2 < q3 + q4 ) /* first half */
		287	{
		288	q4 = q4 + q3;
		289	q3 = q3 + q2;
		290	q2 = q2 + q1;
		291	q4 = q4 + q3;
		292	q3 = q3 + q2;
		293	q4 = ( q4 + q3 ) / 8;
		294	q3 = q3 / 4;
		295	q2 = q2 / 2;
		296	}
		297	else /* second half */
		298	{
		299	q1 = q1 + q2;
		300	q2 = q2 + q3;
		301	q3 = q3 + q4;
		302	q1 = q1 + q2;
		303	q2 = q2 + q3;
		304	q1 = ( q1 + q2 ) / 8;
		305	q2 = q2 / 4;
		306	q3 = q3 / 2;
		307	}
		308
		309	/* check if either end reached the minimum */
		310	if ( q1 == q2 && q1 <= q3 )
		311	{
		312	*min = q1;
		313	break;
		314	}
		315	if ( q3 == q4 && q2 >= q4 )
		316	{
		317	*min = q4;
		318	break;
		319	}
		320	}
		321	}
		322
		323	#else
		324
		325	static void
		326	test_cubic_extrema( FT_Pos y1,
		327	FT_Pos y2,
		328	FT_Pos y3,
		329	FT_Pos y4,
		330	FT_Fixed u,
		331	FT_Pos* min,
		332	FT_Pos* max )
		333	{
		334	/* FT_Pos a = y4 - 3y3 + 3y2 - y1; */
		335	FT_Pos b = y3 - 2*y2 + y1;
		336	FT_Pos c = y2 - y1;
		337	FT_Pos d = y1;
		338	FT_Pos y;
		339	FT_Fixed uu;
		340
		341	FT_UNUSED ( y4 );
		342
		343
		344	/* The polynomial is */
		345	/* */
		346	/* P(x) = ax^3 + 3bx^2 + 3cx + d , /
		347	/* */
		348	/* dP/dx = 3ax^2 + 6bx + 3c . */
		349	/* */
		350	/* However, we also have */
		351	/* */
		352	/* dP/dx(u) = 0 , */
		353	/* */
		354	/* which implies by subtraction that */
		355	/* */
		356	/* P(u) = bu^2 + 2cu + d . */
		357
		358	if ( u > 0 && u < 0x10000L )
		359	{
		360	uu = FT_MulFix( u, u );
		361	y = d + FT_MulFix( c, 2*u ) + FT_MulFix( b, uu );
		362
		363	if ( y < min ) min = y;
		364	if ( y > max ) max = y;
		365	}
		366	}
		367
		368
		369	static void
		370	BBox_Cubic_Check( FT_Pos y1,
		371	FT_Pos y2,
		372	FT_Pos y3,
		373	FT_Pos y4,
		374	FT_Pos* min,
		375	FT_Pos* max )
		376	{
		377	/* always compare first and last points */
		378	if ( y1 < min ) min = y1;
		379	else if ( y1 > max ) max = y1;
		380
		381	if ( y4 < min ) min = y4;
		382	else if ( y4 > max ) max = y4;
		383
		384	/* now, try to see if there are split points here */
		385	if ( y1 <= y4 )
		386	{
		387	/* flat or ascending arc test */
		388	if ( y1 <= y2 && y2 <= y4 && y1 <= y3 && y3 <= y4 )
		389	return;
		390	}
		391	else /* y1 > y4 */
		392	{
		393	/* descending arc test */
		394	if ( y1 >= y2 && y2 >= y4 && y1 >= y3 && y3 >= y4 )
		395	return;
		396	}
		397
		398	/* There are some split points. Find them. */
		399	/* We already made sure that a, b, and c below cannot be all zero. */
		400	{
		401	FT_Pos a = y4 - 3y3 + 3y2 - y1;
		402	FT_Pos b = y3 - 2*y2 + y1;
		403	FT_Pos c = y2 - y1;
		404	FT_Pos d;
		405	FT_Fixed t;
		406	FT_Int shift;
		407
		408
		409	/* We need to solve `ax^2+2bx+c' here, without floating points! */
		410	/* The trick is to normalize to a different representation in order */
		411	/* to use our 16.16 fixed-point routines. */
		412	/* */
		413	/* We compute FT_MulFix(b,b) and FT_MulFix(a,c) after normalization. */
		414	/* These values must fit into a single 16.16 value. */
		415	/* */
		416	/* We normalize a, b, and c to `8.16' fixed-point values to ensure */
		417	/* that their product is held in a `16.16' value including the sign. */
		418	/* Necessarily, we need to shift `a', `b', and `c' so that the most */
		419	/* significant bit of their absolute values is at position 22. */
		420	/* */
		421	/* This also means that we are using 23 bits of precision to compute */
		422	/* the zeros, independently of the range of the original polynomial */
		423	/* coefficients. */
		424	/* */
		425	/* This algorithm should ensure reasonably accurate values for the */
		426	/* zeros. Note that they are only expressed with 16 bits when */
		427	/* computing the extrema (the zeros need to be in 0..1 exclusive */
		428	/* to be considered part of the arc). */
		429
		430	shift = FT_MSB( FT_ABS( a ) \| FT_ABS( b ) \| FT_ABS( c ) );
		431
		432	if ( shift > 22 )
		433	{
		434	shift -= 22;
		435
		436	/* this loses some bits of precision, but we use 23 of them */
		437	/* for the computation anyway */
		438	a >>= shift;
		439	b >>= shift;
		440	c >>= shift;
		441	}
		442	else
		443	{
		444	shift = 22 - shift;
		445
		446	a <<= shift;
		447	b <<= shift;
		448	c <<= shift;
		449	}
		450
		451	/* handle a == 0 */
		452	if ( a == 0 )
		453	{
		454	if ( b != 0 )
		455	{
		456	t = - FT_DivFix( c, b ) / 2;
		457	test_cubic_extrema( y1, y2, y3, y4, t, min, max );
		458	}
		459	}
		460	else
		461	{
		462	/* solve the equation now */
		463	d = FT_MulFix( b, b ) - FT_MulFix( a, c );
		464	if ( d < 0 )
		465	return;
		466
		467	if ( d == 0 )
		468	{
		469	/* there is a single split point at -b/a */
		470	t = - FT_DivFix( b, a );
		471	test_cubic_extrema( y1, y2, y3, y4, t, min, max );
		472	}
		473	else
		474	{
		475	/* there are two solutions; we need to filter them */
		476	d = FT_SqrtFixed( (FT_Int32)d );
		477	t = - FT_DivFix( b - d, a );
		478	test_cubic_extrema( y1, y2, y3, y4, t, min, max );
		479
		480	t = - FT_DivFix( b + d, a );
		481	test_cubic_extrema( y1, y2, y3, y4, t, min, max );
		482	}
		483	}
		484	}
		485	}
		486
		487	#endif
		488
		489
		490	/*************************************************************************/
		491	/* */
		492	/* */
		493	/* BBox_Cubic_To */
		494	/* */
		495	/* */
		496	/* This function is used as a `cubic_to' emitter during */
		497	/* FT_Outline_Decompose(). It checks a cubic Bezier curve with the */
		498	/* current bounding box, and computes its extrema if necessary to */
		499	/* update it. */
		500	/* */
		501	/* */
		502	/* control1 :: A pointer to the first control point. */
		503	/* */
		504	/* control2 :: A pointer to the second control point. */
		505	/* */
		506	/* to :: A pointer to the destination vector. */
		507	/* */
		508	/* */
		509	/* user :: The address of the current walk context. */
		510	/* */
		511	/* */
		512	/* Always 0. Needed for the interface only. */
		513	/* */
		514	/* */
		515	/* In the case of a non-monotonous arc, we don't compute directly */
		516	/* extremum coordinates, we subdivide instead. */
		517	/* */
		518	static int
		519	BBox_Cubic_To( FT_Vector* control1,
		520	FT_Vector* control2,
		521	FT_Vector* to,
		522	TBBox_Rec* user )
		523	{
		524	/* we don't need to check `to' since it is always an `on' point, thus */
		525	/* within the bbox */
		526
		527	if ( CHECK_X( control1, user->bbox ) \|\|
		528	CHECK_X( control2, user->bbox ) )
		529	BBox_Cubic_Check( user->last.x,
		530	control1->x,
		531	control2->x,
		532	to->x,
		533	&user->bbox.xMin,
		534	&user->bbox.xMax );
		535
		536	if ( CHECK_Y( control1, user->bbox ) \|\|
		537	CHECK_Y( control2, user->bbox ) )
		538	BBox_Cubic_Check( user->last.y,
		539	control1->y,
		540	control2->y,
		541	to->y,
		542	&user->bbox.yMin,
		543	&user->bbox.yMax );
		544
		545	user->last = *to;
		546
		547	return 0;
		548	}
		549
		550	FT_DEFINE_OUTLINE_FUNCS(bbox_interface,
		551	(FT_Outline_MoveTo_Func) BBox_Move_To,
		552	(FT_Outline_LineTo_Func) BBox_Move_To,
		553	(FT_Outline_ConicTo_Func)BBox_Conic_To,
		554	(FT_Outline_CubicTo_Func)BBox_Cubic_To,
		555	0, 0
		556	)
		557
		558	/* documentation is in ftbbox.h */
		559
		560	FT_EXPORT_DEF( FT_Error )
		561	FT_Outline_Get_BBox( FT_Outline* outline,
		562	FT_BBox *abbox )
		563	{
		564	FT_BBox cbox;
		565	FT_BBox bbox;
		566	FT_Vector* vec;
		567	FT_UShort n;
		568
		569
		570	if ( !abbox )
		571	return FT_THROW( Invalid_Argument );
		572
		573	if ( !outline )
		574	return FT_THROW( Invalid_Outline );
		575
		576	/* if outline is empty, return (0,0,0,0) */
		577	if ( outline->n_points == 0 \|\| outline->n_contours <= 0 )
		578	{
		579	abbox->xMin = abbox->xMax = 0;
		580	abbox->yMin = abbox->yMax = 0;
		581	return 0;
		582	}
		583
		584	/* We compute the control box as well as the bounding box of */
		585	/* all `on' points in the outline. Then, if the two boxes */
		586	/* coincide, we exit immediately. */
		587
		588	vec = outline->points;
		589	bbox.xMin = bbox.xMax = cbox.xMin = cbox.xMax = vec->x;
		590	bbox.yMin = bbox.yMax = cbox.yMin = cbox.yMax = vec->y;
		591	vec++;
		592
		593	for ( n = 1; n < outline->n_points; n++ )
		594	{
		595	FT_Pos x = vec->x;
		596	FT_Pos y = vec->y;
		597
		598
		599	/* update control box */
		600	if ( x < cbox.xMin ) cbox.xMin = x;
		601	if ( x > cbox.xMax ) cbox.xMax = x;
		602
		603	if ( y < cbox.yMin ) cbox.yMin = y;
		604	if ( y > cbox.yMax ) cbox.yMax = y;
		605
		606	if ( FT_CURVE_TAG( outline->tags[n] ) == FT_CURVE_TAG_ON )
		607	{
		608	/* update bbox for `on' points only */
		609	if ( x < bbox.xMin ) bbox.xMin = x;
		610	if ( x > bbox.xMax ) bbox.xMax = x;
		611
		612	if ( y < bbox.yMin ) bbox.yMin = y;
		613	if ( y > bbox.yMax ) bbox.yMax = y;
		614	}
		615
		616	vec++;
		617	}
		618
		619	/* test two boxes for equality */
		620	if ( cbox.xMin < bbox.xMin \|\| cbox.xMax > bbox.xMax \|\|
		621	cbox.yMin < bbox.yMin \|\| cbox.yMax > bbox.yMax )
		622	{
		623	/* the two boxes are different, now walk over the outline to */
		624	/* get the Bezier arc extrema. */
		625
		626	FT_Error error;
		627	TBBox_Rec user;
		628
		629	#ifdef FT_CONFIG_OPTION_PIC
		630	FT_Outline_Funcs bbox_interface;
		631	Init_Class_bbox_interface(&bbox_interface);
		632	#endif
		633
		634	user.bbox = bbox;
		635
		636	error = FT_Outline_Decompose( outline, &bbox_interface, &user );
		637	if ( error )
		638	return error;
		639
		640	*abbox = user.bbox;
		641	}
		642	else
		643	*abbox = bbox;
		644
		645	return FT_Err_Ok;
		646	}
		647
		648
		649	/* END */

Subversion Repositories Kolibri OS

(root)/contrib/sdk/sources/freetype/src/base/ftbbox.c – Rev 8031