Context Navigation

ftbbox.c

Last change on this file was 2, checked in by jglee, 11 years ago
first commit
File size: 24.9 KB

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

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: svn/trunk/zasc/freetype-2.3.9/ftbbox.c

Download in other formats: