Commit | Line | Data |
---|---|---|
10d9cc92 WJ |
1 | /* Copyright (C) 1989, 1992 Aladdin Enterprises. All rights reserved. |
2 | Distributed by Free Software Foundation, Inc. | |
3 | ||
4 | This file is part of Ghostscript. | |
5 | ||
6 | Ghostscript is distributed in the hope that it will be useful, but | |
7 | WITHOUT ANY WARRANTY. No author or distributor accepts responsibility | |
8 | to anyone for the consequences of using it or for whether it serves any | |
9 | particular purpose or works at all, unless he says so in writing. Refer | |
10 | to the Ghostscript General Public License for full details. | |
11 | ||
12 | Everyone is granted permission to copy, modify and redistribute | |
13 | Ghostscript, but only under the conditions described in the Ghostscript | |
14 | General Public License. A copy of this license is supposed to have been | |
15 | given to you along with Ghostscript so you can know your rights and | |
16 | responsibilities. It should be in a file named COPYING. Among other | |
17 | things, the copyright notice and this notice must be preserved on all | |
18 | copies. */ | |
19 | ||
20 | /* gxpath2.c */ | |
21 | /* Path tracing procedures for Ghostscript library */ | |
22 | #include "math_.h" | |
23 | #include "gx.h" | |
24 | #include "gserrors.h" | |
25 | #include "gxfixed.h" | |
26 | #include "gxarith.h" | |
27 | #include "gzpath.h" | |
28 | ||
29 | /* Forward declarations */ | |
30 | private int copy_path(P3(gx_path *, gx_path *, fixed)); | |
31 | private int flatten_recur(P8(gx_path *, | |
32 | fixed, fixed, fixed, fixed, fixed, fixed, fixed)); | |
33 | ||
34 | /* Read the current point of a path. */ | |
35 | int | |
36 | gx_path_current_point(gx_path *ppath, gs_fixed_point *ppt) | |
37 | { if ( !ppath->position_valid ) | |
38 | return_error(gs_error_nocurrentpoint); | |
39 | /* Copying the coordinates individually */ | |
40 | /* is much faster on a PC, and almost as fast on other machines.... */ | |
41 | ppt->x = ppath->position.x, ppt->y = ppath->position.y; | |
42 | return 0; | |
43 | } | |
44 | ||
45 | /* Read the bounding box of a path. */ | |
46 | int | |
47 | gx_path_bbox(gx_path *ppath, gs_fixed_rect *pbox) | |
48 | { if ( ppath->first_subpath == 0 ) | |
49 | { /* The path is empty, use the current point if any. */ | |
50 | gx_path_current_point(ppath, &pbox->p); | |
51 | return gx_path_current_point(ppath, &pbox->q); | |
52 | } | |
53 | /* The stored bounding box may not be up to date. */ | |
54 | /* Correct it now if necessary. */ | |
55 | if ( ppath->box_last == ppath->current_subpath->last ) | |
56 | { /* Box is up to date */ | |
57 | *pbox = ppath->bbox; | |
58 | } | |
59 | else | |
60 | { gs_fixed_rect box; | |
61 | register segment *pseg = ppath->box_last; | |
62 | if ( pseg == 0 ) /* box is uninitialized */ | |
63 | { pseg = (segment *)ppath->first_subpath; | |
64 | box.p.x = box.q.x = pseg->pt.x; | |
65 | box.p.y = box.q.y = pseg->pt.y; | |
66 | } | |
67 | else | |
68 | { box = ppath->bbox; | |
69 | pseg = pseg->next; | |
70 | } | |
71 | /* Macro for adjusting the bounding box when adding a point */ | |
72 | #define adjust_bbox(pt)\ | |
73 | if ( (pt).x < box.p.x ) box.p.x = (pt).x;\ | |
74 | else if ( (pt).x > box.q.x ) box.q.x = (pt).x;\ | |
75 | if ( (pt).y < box.p.y ) box.p.y = (pt).y;\ | |
76 | else if ( (pt).y > box.q.y ) box.q.y = (pt).y | |
77 | while ( pseg ) | |
78 | { switch ( pseg->type ) | |
79 | { | |
80 | case s_curve: | |
81 | #define pcurve ((curve_segment *)pseg) | |
82 | adjust_bbox(pcurve->p1); | |
83 | adjust_bbox(pcurve->p2); | |
84 | #undef pcurve | |
85 | /* falls through */ | |
86 | default: | |
87 | adjust_bbox(pseg->pt); | |
88 | } | |
89 | pseg = pseg->next; | |
90 | } | |
91 | #undef adjust_bbox | |
92 | ppath->bbox = box; | |
93 | ppath->box_last = ppath->current_subpath->last; | |
94 | *pbox = box; | |
95 | } | |
96 | return 0; | |
97 | } | |
98 | ||
99 | /* Test if a path has any curves. */ | |
100 | int | |
101 | gx_path_has_curves(gx_path *ppath) | |
102 | { return ppath->curve_count != 0; | |
103 | } | |
104 | ||
105 | /* Test if a path has any segments. */ | |
106 | int | |
107 | gx_path_is_void(gx_path *ppath) | |
108 | { return ppath->first_subpath == 0; | |
109 | } | |
110 | ||
111 | /* Test if a path is a rectangle. */ | |
112 | /* If so, return its bounding box. */ | |
113 | /* Note that this must recognize open as well as closed rectangles. */ | |
114 | int | |
115 | gx_path_is_rectangle(gx_path *ppath, gs_fixed_rect *pbox) | |
116 | { subpath *pseg0; | |
117 | segment *pseg1, *pseg2, *pseg3, *pseg4; | |
118 | if ( ppath->subpath_count == 1 && | |
119 | (pseg1 = (pseg0 = ppath->first_subpath)->next) != 0 && | |
120 | (pseg2 = pseg1->next) != 0 && | |
121 | (pseg3 = pseg2->next) != 0 && | |
122 | ((pseg4 = pseg3->next) == 0 || pseg4->type == s_line_close) && | |
123 | ppath->curve_count == 0 | |
124 | ) | |
125 | { fixed x0 = pseg0->pt.x, y0 = pseg0->pt.y; | |
126 | fixed x2 = pseg2->pt.x, y2 = pseg2->pt.y; | |
127 | if ( (x0 == pseg1->pt.x && pseg1->pt.y == y2 && | |
128 | x2 == pseg3->pt.x && pseg3->pt.y == y0) || | |
129 | (x0 == pseg3->pt.x && pseg3->pt.y == y2 && | |
130 | x2 == pseg1->pt.x && pseg1->pt.y == y0) | |
131 | ) | |
132 | { /* Path is a rectangle. Return bounding box. */ | |
133 | if ( x0 < x2 ) | |
134 | pbox->p.x = x0, pbox->q.x = x2; | |
135 | else | |
136 | pbox->p.x = x2, pbox->q.x = x0; | |
137 | if ( y0 < y2 ) | |
138 | pbox->p.y = y0, pbox->q.y = y2; | |
139 | else | |
140 | pbox->p.y = y2, pbox->q.y = y0; | |
141 | return 1; | |
142 | } | |
143 | } | |
144 | return 0; | |
145 | } | |
146 | ||
147 | /* Copy a path */ | |
148 | int | |
149 | gx_path_copy(gx_path *ppath_old, gx_path *ppath) | |
150 | { return copy_path(ppath_old, ppath, (fixed)0); | |
151 | } | |
152 | ||
153 | /* Translate an already-constructed path (in device space). */ | |
154 | /* Don't bother to translate the cbox. */ | |
155 | int | |
156 | gx_path_translate(gx_path *ppath, fixed dx, fixed dy) | |
157 | { segment *pseg; | |
158 | #define translate_xy(pt)\ | |
159 | pt.x += dx, pt.y += dy | |
160 | translate_xy(ppath->bbox.p); | |
161 | translate_xy(ppath->bbox.q); | |
162 | translate_xy(ppath->position); | |
163 | pseg = (segment *)(ppath->first_subpath); | |
164 | while ( pseg ) | |
165 | { switch ( pseg->type ) | |
166 | { | |
167 | case s_curve: | |
168 | { curve_segment *pc = (curve_segment *)pseg; | |
169 | translate_xy(pc->p1); | |
170 | translate_xy(pc->p2); | |
171 | } | |
172 | default: | |
173 | translate_xy(pseg->pt); | |
174 | } | |
175 | pseg = pseg->next; | |
176 | } | |
177 | return 0; | |
178 | } | |
179 | ||
180 | /* Flatten a path */ | |
181 | private fixed | |
182 | scale_flatness(floatp flatness) | |
183 | { /* See the flattening algorithm below for an explanation of */ | |
184 | /* the following computation. */ | |
185 | fixed scaled_flat = float2fixed(flatness); | |
186 | return (scaled_flat > int2fixed(100) ? int2fixed(100) : | |
187 | scaled_flat <= float2fixed(0.2) ? float2fixed(0.2) : | |
188 | scaled_flat); | |
189 | } | |
190 | int | |
191 | gx_path_flatten(gx_path *ppath_old, gx_path *ppath, floatp flatness) | |
192 | { return copy_path(ppath_old, ppath, scale_flatness(flatness)); | |
193 | } | |
194 | ||
195 | /* Add a flattened curve to a path. */ | |
196 | int | |
197 | gx_path_add_flattened_curve(gx_path *ppath, | |
198 | fixed x1, fixed y1, fixed x2, fixed y2, fixed x3, fixed y3, | |
199 | floatp flatness) | |
200 | { return flatten_recur(ppath, x1, y1, x2, y2, x3, y3, | |
201 | scale_flatness(flatness)); | |
202 | } | |
203 | ||
204 | /* Copy a path, optionally flattening it. */ | |
205 | /* If the copy fails, free the new path. */ | |
206 | private int | |
207 | copy_path(gx_path *ppath_old, gx_path *ppath, fixed scaled_flat) | |
208 | { gx_path old; | |
209 | segment *pseg; | |
210 | int code; | |
211 | #ifdef DEBUG | |
212 | if ( gs_debug['p'] ) | |
213 | gx_dump_path(ppath_old, "before copy_path"); | |
214 | #endif | |
215 | old = *ppath_old; | |
216 | gx_path_init(ppath, &ppath_old->memory_procs); | |
217 | pseg = (segment *)(old.first_subpath); | |
218 | while ( pseg ) | |
219 | { switch ( pseg->type ) | |
220 | { | |
221 | case s_start: | |
222 | code = gx_path_add_point(ppath, pseg->pt.x, pseg->pt.y); | |
223 | break; | |
224 | case s_curve: | |
225 | { curve_segment *pc = (curve_segment *)pseg; | |
226 | if ( scaled_flat == 0 ) /* don't flatten */ | |
227 | code = gx_path_add_curve(ppath, | |
228 | pc->p1.x, pc->p1.y, | |
229 | pc->p2.x, pc->p2.y, | |
230 | pc->pt.x, pc->pt.y); | |
231 | else | |
232 | code = flatten_recur(ppath, | |
233 | pc->p1.x, pc->p1.y, | |
234 | pc->p2.x, pc->p2.y, | |
235 | pc->pt.x, pc->pt.y, | |
236 | scaled_flat); | |
237 | break; | |
238 | } | |
239 | case s_line: | |
240 | code = gx_path_add_line(ppath, pseg->pt.x, pseg->pt.y); | |
241 | break; | |
242 | case s_line_close: | |
243 | code = gx_path_close_subpath(ppath); | |
244 | break; | |
245 | } | |
246 | if ( code ) | |
247 | { gx_path_release(ppath); | |
248 | if ( ppath == ppath_old ) *ppath_old = old; | |
249 | return code; | |
250 | } | |
251 | pseg = pseg->next; | |
252 | } | |
253 | ppath->position = old.position; /* restore current point */ | |
254 | #ifdef DEBUG | |
255 | if ( gs_debug['p'] ) | |
256 | gx_dump_path(ppath, "after copy_path"); | |
257 | #endif | |
258 | return 0; | |
259 | } | |
260 | /* Internal routine to flatten a curve. */ | |
261 | /* This calls itself recursively, using binary subdivision, */ | |
262 | /* until the approximation is good enough to satisfy the */ | |
263 | /* flatness requirement. The starting point is ppath->position, */ | |
264 | /* which gets updated as line segments are added. */ | |
265 | ||
266 | /* Table of f(i) = 256 * sqrt(1 + (i/64)^2). */ | |
267 | /* This is good to within 1% or better. */ | |
268 | #define sqrt_index_shift 6 /* scaling of index */ | |
269 | #define sqrt_value_shift 8 /* scaling of value */ | |
270 | private int scaled_sqrt_tab[65] = | |
271 | { 256, 256, 256, 256, 256, 256, 257, 257, | |
272 | 257, 258, 259, 259, 260, 261, 262, 262, | |
273 | 263, 264, 265, 267, 268, 269, 270, 272, | |
274 | 273, 274, 276, 277, 279, 281, 282, 284, | |
275 | 286, 288, 289, 291, 293, 295, 297, 299, | |
276 | 301, 304, 306, 308, 310, 312, 315, 317, | |
277 | 320, 322, 324, 327, 329, 332, 334, 337, | |
278 | 340, 342, 345, 348, 350, 353, 356, 359, | |
279 | 362 | |
280 | }; | |
281 | private int flatten_sample(P8(gx_path *, int, | |
282 | fixed, fixed, fixed, fixed, fixed, fixed)); | |
283 | ||
284 | private int | |
285 | flatten_recur(gx_path *ppath, | |
286 | fixed x1, fixed y1, fixed x2, fixed y2, fixed x3, fixed y3, | |
287 | fixed scaled_flat) | |
288 | { fixed | |
289 | x0 = ppath->position.x, | |
290 | y0 = ppath->position.y; | |
291 | top: | |
292 | #ifdef DEBUG | |
293 | if ( gs_debug['2'] ) | |
294 | dprintf4("[2]x0=%f y0=%f x1=%f y1=%f\n", | |
295 | fixed2float(x0), fixed2float(y0), | |
296 | fixed2float(x1), fixed2float(y1)), | |
297 | dprintf4(" x2=%f y2=%f x3=%f y3=%f\n", | |
298 | fixed2float(x2), fixed2float(y2), | |
299 | fixed2float(x3), fixed2float(y3)); | |
300 | #endif | |
301 | /* | |
302 | * Compute the maximum distance of the curve from | |
303 | * the line (x0,y0)->(x3,y3). We do this conservatively | |
304 | * by observing that the curve is enclosed by the | |
305 | * quadrilateral of its control points, so we simply | |
306 | * compute the distances of (x1,y1) and (x2,y2) | |
307 | * from the line. Letting dx = x3-x0 and dy = y3-y0, | |
308 | * the distance of (xp,yp) from the line is | |
309 | * abs(N)/sqrt(D), where N = dy*(xp-x0)-dx*(yp-y0) and | |
310 | * D = dx*dx+dy*dy; hence we want to test abs(N) <= sqrt(D)*F, | |
311 | * where F is the flatness parameter from the graphics state. | |
312 | * We can do this more efficiently by letting t=dy/dx, and | |
313 | * testing abs(N1) <= sqrt(D1)*f, where N1=t*(xp-x0)-(yp-y0) and | |
314 | * D1 = 1+t*t. If dx < dy, we swap x and y for this | |
315 | * computation. This guarantees abs(t) <= 1, which allows us to | |
316 | * compute sqrt(1+t*t) by table lookup on the high bits of abs(t). | |
317 | */ | |
318 | { fixed dx3 = x3 - x0; | |
319 | fixed adx3 = any_abs(dx3); | |
320 | fixed dy3 = y3 - y0; | |
321 | fixed ady3 = any_abs(dy3); | |
322 | /* We have to be quite careful to ensure that */ | |
323 | /* none of the multiplications will overflow. */ | |
324 | #define short_max 0x7ff0L | |
325 | #define reduce_3(ad3, maxv)\ | |
326 | while ( ad3 > maxv )\ | |
327 | adx3 >>= 1, ady3 >>= 1,\ | |
328 | dx3 = arith_rshift_1(dx3), dy3 = arith_rshift_1(dy3) | |
329 | #define reduce_d(d)\ | |
330 | for ( shift = 0; (d < 0 ? d < -short_max : d > short_max); shift++ )\ | |
331 | d = arith_rshift_1(d) | |
332 | if ( adx3 > ady3 ) | |
333 | { fixed d, dx, dy, dist; | |
334 | int shift; | |
335 | reduce_3(ady3, short_max); | |
336 | d = (scaled_sqrt_tab[(ady3 << sqrt_index_shift) / adx3] * scaled_flat) >> sqrt_value_shift; | |
337 | dx = x1 - x0, dy = y1 - y0; | |
338 | reduce_d(dx); | |
339 | if ( ((dist = ((dx * dy3 / dx3) << shift) - dy) < 0 ? | |
340 | -dist : dist) > d ) | |
341 | goto sub; /* not flat enough */ | |
342 | dx = x2 - x0, dy = y2 - y0; | |
343 | reduce_d(dx); | |
344 | if ( ((dist = ((dx * dy3 / dx3) << shift) - dy) < 0 ? | |
345 | -dist : dist) > d ) | |
346 | goto sub; /* not flat enough */ | |
347 | } | |
348 | else if ( ady3 != 0 ) | |
349 | { fixed d, dy, dx, dist; | |
350 | int shift; | |
351 | reduce_3(adx3, short_max); | |
352 | d = (scaled_sqrt_tab[(adx3 << sqrt_index_shift) / ady3] * scaled_flat) >> sqrt_value_shift; | |
353 | dy = y1 - y0, dx = x1 - x0; | |
354 | reduce_d(dy); | |
355 | if ( ((dist = ((dy * dx3 / dy3) << shift) - dx) < 0 ? | |
356 | -dist : dist) > d ) | |
357 | goto sub; /* not flat enough */ | |
358 | dy = y2 - y0, dx = x2 - x0; | |
359 | reduce_d(dy); | |
360 | if ( ((dist = ((dy * dx3 / dy3) << shift) - dx) < 0 ? | |
361 | -dist : dist) > d ) | |
362 | goto sub; /* not flat enough */ | |
363 | } | |
364 | else /* adx3 = ady3 = 0 */ | |
365 | { /* (x0,y0) is the same point as (x3,y3). */ | |
366 | /* This is an anomalous case. If the entire curve */ | |
367 | /* is a single point, stop now, otherwise subdivide. */ | |
368 | if ( x1 != x0 || y1 != y0 || x2 != x0 || y2 != y0 ) | |
369 | goto sub; | |
370 | } | |
371 | } | |
372 | /* Curve is flat enough. Add a line and exit. */ | |
373 | #ifdef DEBUG | |
374 | if ( gs_debug['2'] ) | |
375 | dprintf2("[2]\t*** x=%f, y=%f ***\n", | |
376 | fixed2float(x3), fixed2float(y3)); | |
377 | #endif | |
378 | return gx_path_add_line(ppath, x3, y3); | |
379 | ||
380 | /* Curve isn't flat enough. Break into two pieces and recur. */ | |
381 | /* Algorithm is from "The Beta2-split: A special case of the */ | |
382 | /* Beta-spline Curve and Surface Representation," B. A. Barsky */ | |
383 | /* and A. D. DeRose, IEEE, 1985, courtesy of Crispin Goswell. */ | |
384 | sub: | |
385 | /* We have to define midpoint carefully to avoid overflow. */ | |
386 | /* (If it overflows, something really pathological is going on, */ | |
387 | /* but we could get infinite recursion that way.... */ | |
388 | #define midpoint(a,b)\ | |
389 | (arith_rshift_1(a) + arith_rshift_1(b) + ((a) & (b) & 1)) | |
390 | { fixed x01 = midpoint(x0, x1), y01 = midpoint(y0, y1); | |
391 | fixed x12 = midpoint(x1, x2), y12 = midpoint(y1, y2); | |
392 | fixed x02 = midpoint(x01, x12), y02 = midpoint(y01, y12); | |
393 | int code; | |
394 | /* Update x/y1, x/y2, and x/y0 now for the second half. */ | |
395 | x2 = midpoint(x2, x3), y2 = midpoint(y2, y3); | |
396 | x1 = midpoint(x12, x2), y1 = midpoint(y12, y2); | |
397 | code = flatten_recur(ppath, x01, y01, x02, y02, | |
398 | (x0 = midpoint(x02, x1)), (y0 = midpoint(y02, y1)), | |
399 | scaled_flat); | |
400 | if ( code < 0 ) return code; | |
401 | } goto top; | |
402 | } | |
403 | ||
404 | /* Flatten a segment of the path by repeated sampling. */ | |
405 | /* For some reason, this produces better results, */ | |
406 | /* even though flatten_recur is careful to check the flatness.... */ | |
407 | /* n is the number of points to sample, including the endpoints; */ | |
408 | /* we require n >= 3. */ | |
409 | private int | |
410 | flatten_sample(gx_path *ppath, int n, | |
411 | fixed x1, fixed y1, fixed x2, fixed y2, fixed x3, fixed y3) | |
412 | { const fixed | |
413 | x0 = ppath->position.x, | |
414 | y0 = ppath->position.y; | |
415 | const fixed | |
416 | cx = 3 * (x1 - x0), | |
417 | bx = 3 * (x2 - x1) - cx, | |
418 | ax = x3 - bx - cx - x0; | |
419 | const fixed | |
420 | cy = 3 * (y1 - y0), | |
421 | by = 3 * (y2 - y1) - cy, | |
422 | ay = y3 - by - cy - y0; | |
423 | const float | |
424 | dt = 1.0 / (float)(n - 1); | |
425 | int i; | |
426 | ||
427 | for ( i = 1; i < n-1; i++ ) | |
428 | { const float t = dt * (float)(i); | |
429 | const fixed x = x0 + (fixed)(t*(cx + t*(bx + t*ax))); | |
430 | const fixed y = y0 + (fixed)(t*(cy + t*(by + t*ay))); | |
431 | int code; | |
432 | if ( 0 != (code = gx_path_add_line(ppath, x, y)) ) | |
433 | return code; | |
434 | } | |
435 | return gx_path_add_line(ppath, x3, y3); | |
436 | } | |
437 | ||
438 | /* Reverse a path. */ | |
439 | /* We know ppath != ppath_old. */ | |
440 | int | |
441 | gx_path_reverse(gx_path *ppath_old, gx_path *ppath) | |
442 | { subpath *psub = ppath_old->first_subpath; | |
443 | #ifdef DEBUG | |
444 | if ( gs_debug['p'] ) | |
445 | gx_dump_path(ppath_old, "before reversepath"); | |
446 | #endif | |
447 | gx_path_init(ppath, &ppath_old->memory_procs); | |
448 | nsp: while ( psub ) | |
449 | { segment *pseg = psub->last; | |
450 | segment *prev; | |
451 | int code = gx_path_add_point(ppath, pseg->pt.x, pseg->pt.y); | |
452 | if ( code < 0 ) | |
453 | { gx_path_release(ppath); | |
454 | return code; | |
455 | } | |
456 | for ( ; ; pseg = prev ) | |
457 | { prev = pseg->prev; | |
458 | switch ( pseg->type ) | |
459 | { | |
460 | case s_start: | |
461 | /* Finished subpath */ | |
462 | if ( psub->closed ) | |
463 | code = gx_path_close_subpath(ppath); | |
464 | psub = (subpath *)psub->last->next; | |
465 | goto nsp; | |
466 | case s_curve: | |
467 | { curve_segment *pc = (curve_segment *)pseg; | |
468 | code = gx_path_add_curve(ppath, | |
469 | pc->p2.x, pc->p2.y, | |
470 | pc->p1.x, pc->p1.y, | |
471 | prev->pt.x, prev->pt.y); | |
472 | break; | |
473 | } | |
474 | case s_line: | |
475 | case s_line_close: | |
476 | code = gx_path_add_line(ppath, prev->pt.x, prev->pt.y); | |
477 | break; | |
478 | } | |
479 | if ( code ) | |
480 | { gx_path_release(ppath); | |
481 | return code; | |
482 | } | |
483 | } | |
484 | } | |
485 | ppath->position = ppath_old->position; /* restore current point */ | |
486 | #ifdef DEBUG | |
487 | if ( gs_debug['p'] ) | |
488 | gx_dump_path(ppath, "after reversepath"); | |
489 | #endif | |
490 | return 0; | |
491 | } |