1 /* Copyright (C) 1997, 1998 Aladdin Enterprises. All rights reserved.
2
3 This software is provided AS-IS with no warranty, either express or
4 implied.
5
6 This software is distributed under license and may not be copied,
7 modified or distributed except as expressly authorized under the terms
8 of the license contained in the file LICENSE in this distribution.
9
10 For more information about licensing, please refer to
11 http://www.ghostscript.com/licensing/. For information on
12 commercial licensing, go to http://www.artifex.com/licensing/ or
13 contact Artifex Software, Inc., 101 Lucas Valley Road #110,
14 San Rafael, CA 94903, U.S.A., +1(415)492-9861.
15 */
16
17 /* $Id: gxpflat.c,v 1.45 2005/08/10 19:36:11 igor Exp $ */
18 /* Path flattening algorithms */
19 #include "string_.h"
20 #include "gx.h"
21 #include "gxarith.h"
22 #include "gxfixed.h"
23 #include "gzpath.h"
24 #include "memory_.h"
25 #include "vdtrace.h"
26 #include <assert.h>
27
28 /* ---------------- Curve flattening ---------------- */
29
30 /*
31 * To calculate how many points to sample along a path in order to
32 * approximate it to the desired degree of flatness, we define
33 * dist((x,y)) = abs(x) + abs(y);
34 * then the number of points we need is
35 * N = 1 + sqrt(3/4 * D / flatness),
36 * where
37 * D = max(dist(p0 - 2*p1 + p2), dist(p1 - 2*p2 + p3)).
38 * Since we are going to use a power of 2 for the number of intervals,
39 * we can avoid the square root by letting
40 * N = 1 + 2^(ceiling(log2(3/4 * D / flatness) / 2)).
41 * (Reference: DEC Paris Research Laboratory report #1, May 1989.)
42 *
43 * We treat two cases specially. First, if the curve is very
44 * short, we halve the flatness, to avoid turning short shallow curves
45 * into short straight lines. Second, if the curve forms part of a
46 * character (indicated by flatness = 0), we let
47 * N = 1 + 2 * max(abs(x3-x0), abs(y3-y0)).
48 * This is probably too conservative, but it produces good results.
49 */
50 int
gx_curve_log2_samples(fixed x0,fixed y0,const curve_segment * pc,fixed fixed_flat)51 gx_curve_log2_samples(fixed x0, fixed y0, const curve_segment * pc,
52 fixed fixed_flat)
53 {
54 fixed
55 x03 = pc->pt.x - x0,
56 y03 = pc->pt.y - y0;
57 int k;
58
59 if (x03 < 0)
60 x03 = -x03;
61 if (y03 < 0)
62 y03 = -y03;
63 if ((x03 | y03) < int2fixed(16))
64 fixed_flat >>= 1;
65 if (fixed_flat == 0) { /* Use the conservative method. */
66 fixed m = max(x03, y03);
67
68 for (k = 1; m > fixed_1;)
69 k++, m >>= 1;
70 } else {
71 const fixed
72 x12 = pc->p1.x - pc->p2.x, y12 = pc->p1.y - pc->p2.y,
73 dx0 = x0 - pc->p1.x - x12, dy0 = y0 - pc->p1.y - y12,
74 dx1 = x12 - pc->p2.x + pc->pt.x, dy1 = y12 - pc->p2.y + pc->pt.y,
75 adx0 = any_abs(dx0), ady0 = any_abs(dy0),
76 adx1 = any_abs(dx1), ady1 = any_abs(dy1);
77 fixed
78 d = max(adx0, adx1) + max(ady0, ady1);
79 /*
80 * The following statement is split up to work around a
81 * bug in the gcc 2.7.2 optimizer on H-P RISC systems.
82 */
83 uint qtmp = d - (d >> 2) /* 3/4 * D */ +fixed_flat - 1;
84 uint q = qtmp / fixed_flat;
85
86 if_debug6('2', "[2]d01=%g,%g d12=%g,%g d23=%g,%g\n",
87 fixed2float(pc->p1.x - x0), fixed2float(pc->p1.y - y0),
88 fixed2float(-x12), fixed2float(-y12),
89 fixed2float(pc->pt.x - pc->p2.x), fixed2float(pc->pt.y - pc->p2.y));
90 if_debug2('2', " D=%f, flat=%f,",
91 fixed2float(d), fixed2float(fixed_flat));
92 /* Now we want to set k = ceiling(log2(q) / 2). */
93 for (k = 0; q > 1;)
94 k++, q = (q + 3) >> 2;
95 if_debug1('2', " k=%d\n", k);
96 }
97 return k;
98 }
99
100 /*
101 * Split a curve segment into two pieces at the (parametric) midpoint.
102 * Algorithm is from "The Beta2-split: A special case of the Beta-spline
103 * Curve and Surface Representation," B. A. Barsky and A. D. DeRose, IEEE,
104 * 1985, courtesy of Crispin Goswell.
105 */
106 private void
split_curve_midpoint(fixed x0,fixed y0,const curve_segment * pc,curve_segment * pc1,curve_segment * pc2)107 split_curve_midpoint(fixed x0, fixed y0, const curve_segment * pc,
108 curve_segment * pc1, curve_segment * pc2)
109 { /*
110 * We have to define midpoint carefully to avoid overflow.
111 * (If it overflows, something really pathological is going
112 * on, but we could get infinite recursion that way....)
113 */
114 #define midpoint(a,b)\
115 (arith_rshift_1(a) + arith_rshift_1(b) + (((a) | (b)) & 1))
116 fixed x12 = midpoint(pc->p1.x, pc->p2.x);
117 fixed y12 = midpoint(pc->p1.y, pc->p2.y);
118
119 /*
120 * pc1 or pc2 may be the same as pc, so we must be a little careful
121 * about the order in which we store the results.
122 */
123 pc1->p1.x = midpoint(x0, pc->p1.x);
124 pc1->p1.y = midpoint(y0, pc->p1.y);
125 pc2->p2.x = midpoint(pc->p2.x, pc->pt.x);
126 pc2->p2.y = midpoint(pc->p2.y, pc->pt.y);
127 pc1->p2.x = midpoint(pc1->p1.x, x12);
128 pc1->p2.y = midpoint(pc1->p1.y, y12);
129 pc2->p1.x = midpoint(x12, pc2->p2.x);
130 pc2->p1.y = midpoint(y12, pc2->p2.y);
131 if (pc2 != pc)
132 pc2->pt.x = pc->pt.x,
133 pc2->pt.y = pc->pt.y;
134 pc1->pt.x = midpoint(pc1->p2.x, pc2->p1.x);
135 pc1->pt.y = midpoint(pc1->p2.y, pc2->p1.y);
136 #undef midpoint
137 }
138
139 private inline void
print_points(const gs_fixed_point * points,int count)140 print_points(const gs_fixed_point *points, int count)
141 {
142 #ifdef DEBUG
143 int i;
144
145 if (!gs_debug_c('3'))
146 return;
147 for (i = 0; i < count; i++)
148 if_debug2('3', "[3]out x=%d y=%d\n", points[i].x, points[i].y);
149 #endif
150 }
151
152
153 bool
curve_coeffs_ranged(fixed x0,fixed x1,fixed x2,fixed x3,fixed y0,fixed y1,fixed y2,fixed y3,fixed * ax,fixed * bx,fixed * cx,fixed * ay,fixed * by,fixed * cy,int k)154 curve_coeffs_ranged(fixed x0, fixed x1, fixed x2, fixed x3,
155 fixed y0, fixed y1, fixed y2, fixed y3,
156 fixed *ax, fixed *bx, fixed *cx,
157 fixed *ay, fixed *by, fixed *cy,
158 int k)
159 {
160 fixed x01, x12, y01, y12;
161
162 curve_points_to_coefficients(x0, x1, x2, x3,
163 *ax, *bx, *cx, x01, x12);
164 curve_points_to_coefficients(y0, y1, y2, y3,
165 *ay, *by, *cy, y01, y12);
166 # define max_fast (max_fixed / 6)
167 # define min_fast (-max_fast)
168 # define in_range(v) (v < max_fast && v > min_fast)
169 if (k > k_sample_max ||
170 !in_range(*ax) || !in_range(*ay) ||
171 !in_range(*bx) || !in_range(*by) ||
172 !in_range(*cx) || !in_range(*cy)
173 )
174 return false;
175 #undef max_fast
176 #undef min_fast
177 #undef in_range
178 return true;
179 }
180
181 /* Initialize the iterator.
182 Momotonic curves with non-zero length are only allowed.
183 */
184 bool
gx_flattened_iterator__init(gx_flattened_iterator * this,fixed x0,fixed y0,const curve_segment * pc,int k)185 gx_flattened_iterator__init(gx_flattened_iterator *this,
186 fixed x0, fixed y0, const curve_segment *pc, int k)
187 {
188 /* Note : Immediately after the ininialization it keeps an invalid (zero length) segment. */
189 fixed x1, y1, x2, y2;
190 const int k2 = k << 1, k3 = k2 + k;
191 fixed bx2, by2, ax6, ay6;
192
193 x1 = pc->p1.x;
194 y1 = pc->p1.y;
195 x2 = pc->p2.x;
196 y2 = pc->p2.y;
197 this->x0 = this->lx0 = this->lx1 = x0;
198 this->y0 = this->ly0 = this->ly1 = y0;
199 this->x3 = pc->pt.x;
200 this->y3 = pc->pt.y;
201 if (!curve_coeffs_ranged(this->x0, x1, x2, this->x3,
202 this->y0, y1, y2, this->y3,
203 &this->ax, &this->bx, &this->cx,
204 &this->ay, &this->by, &this->cy, k))
205 return false;
206 this->curve = true;
207 vd_curve(this->x0, this->y0, x1, y1, x2, y2, this->x3, this->y3, 0, RGB(255, 255, 255));
208 this->k = k;
209 # ifdef DEBUG
210 if (gs_debug_c('3')) {
211 dlprintf4("[3]x0=%f y0=%f x1=%f y1=%f\n",
212 fixed2float(this->x0), fixed2float(this->y0),
213 fixed2float(x1), fixed2float(y1));
214 dlprintf5(" x2=%f y2=%f x3=%f y3=%f k=%d\n",
215 fixed2float(x2), fixed2float(y2),
216 fixed2float(this->x3), fixed2float(this->y3), this->k);
217 }
218 # endif
219 if (k == -1) {
220 /* A special hook for gx_subdivide_curve_rec.
221 Only checked the range.
222 Returning with no initialization. */
223 return true;
224 }
225 this->rmask = (1 << k3) - 1;
226 this->i = (1 << k);
227 this->rx = this->ry = 0;
228 if_debug6('3', "[3]ax=%f bx=%f cx=%f\n ay=%f by=%f cy=%f\n",
229 fixed2float(this->ax), fixed2float(this->bx), fixed2float(this->cx),
230 fixed2float(this->ay), fixed2float(this->by), fixed2float(this->cy));
231 bx2 = this->bx << 1;
232 by2 = this->by << 1;
233 ax6 = ((this->ax << 1) + this->ax) << 1;
234 ay6 = ((this->ay << 1) + this->ay) << 1;
235 this->idx = arith_rshift(this->cx, this->k);
236 this->idy = arith_rshift(this->cy, this->k);
237 this->rdx = ((uint)this->cx << k2) & this->rmask;
238 this->rdy = ((uint)this->cy << k2) & this->rmask;
239 /* bx/y terms */
240 this->id2x = arith_rshift(bx2, k2);
241 this->id2y = arith_rshift(by2, k2);
242 this->rd2x = ((uint)bx2 << this->k) & this->rmask;
243 this->rd2y = ((uint)by2 << this->k) & this->rmask;
244 # define adjust_rem(r, q, rmask) if ( r > rmask ) q ++, r &= rmask
245 /* We can compute all the remainders as ints, */
246 /* because we know they don't exceed M. */
247 /* cx/y terms */
248 this->idx += arith_rshift_1(this->id2x);
249 this->idy += arith_rshift_1(this->id2y);
250 this->rdx += ((uint)this->bx << this->k) & this->rmask,
251 this->rdy += ((uint)this->by << this->k) & this->rmask;
252 adjust_rem(this->rdx, this->idx, this->rmask);
253 adjust_rem(this->rdy, this->idy, this->rmask);
254 /* ax/y terms */
255 this->idx += arith_rshift(this->ax, k3);
256 this->idy += arith_rshift(this->ay, k3);
257 this->rdx += (uint)this->ax & this->rmask;
258 this->rdy += (uint)this->ay & this->rmask;
259 adjust_rem(this->rdx, this->idx, this->rmask);
260 adjust_rem(this->rdy, this->idy, this->rmask);
261 this->id2x += this->id3x = arith_rshift(ax6, k3);
262 this->id2y += this->id3y = arith_rshift(ay6, k3);
263 this->rd2x += this->rd3x = (uint)ax6 & this->rmask,
264 this->rd2y += this->rd3y = (uint)ay6 & this->rmask;
265 adjust_rem(this->rd2x, this->id2x, this->rmask);
266 adjust_rem(this->rd2y, this->id2y, this->rmask);
267 # undef adjust_rem
268 return true;
269 }
270
271 private inline bool
check_diff_overflow(fixed v0,fixed v1)272 check_diff_overflow(fixed v0, fixed v1)
273 {
274 if (v0 < v1) {
275 if (v1 - v0 < 0)
276 return true;
277 } else {
278 if (v0 - v1 < 0)
279 return true;
280 }
281 return false;
282 }
283
284 /* Initialize the iterator with a line. */
285 bool
gx_flattened_iterator__init_line(gx_flattened_iterator * this,fixed x0,fixed y0,fixed x1,fixed y1)286 gx_flattened_iterator__init_line(gx_flattened_iterator *this,
287 fixed x0, fixed y0, fixed x1, fixed y1)
288 {
289 bool ox = check_diff_overflow(x0, x1);
290 bool oy = check_diff_overflow(y0, y1);
291
292 this->x0 = this->lx0 = this->lx1 = x0;
293 this->y0 = this->ly0 = this->ly1 = y0;
294 this->x3 = x1;
295 this->y3 = y1;
296 if (ox || oy) {
297 /* Subdivide a long line into 2 segments, because the filling algorithm
298 and the stroking algorithm need to compute differences
299 of coordinates of end points. */
300 /* Note : the result of subdivision may be not strongly colinear. */
301 this->ax = this->bx = 0;
302 this->ay = this->by = 0;
303 this->cx = (ox ? (x1 >> 1) - (x0 >> 1) : (x1 - x0) / 2);
304 this->cy = (oy ? (y1 >> 1) - (y0 >> 1) : (y1 - y0) / 2);
305 this->k = 1;
306 this->i = 2;
307 } else {
308 this->k = 0;
309 this->i = 1;
310 }
311 this->curve = false;
312 return true;
313 }
314
315 #ifdef DEBUG
316 private inline void
gx_flattened_iterator__print_state(gx_flattened_iterator * this)317 gx_flattened_iterator__print_state(gx_flattened_iterator *this)
318 {
319 if (!gs_debug_c('3'))
320 return;
321 dlprintf4("[3]dx=%f+%d, dy=%f+%d\n",
322 fixed2float(this->idx), this->rdx,
323 fixed2float(this->idy), this->rdy);
324 dlprintf4(" d2x=%f+%d, d2y=%f+%d\n",
325 fixed2float(this->id2x), this->rd2x,
326 fixed2float(this->id2y), this->rd2y);
327 dlprintf4(" d3x=%f+%d, d3y=%f+%d\n",
328 fixed2float(this->id3x), this->rd3x,
329 fixed2float(this->id3y), this->rd3y);
330 }
331 #endif
332
333 /* Move to the next segment and store it to this->lx0, this->ly0, this->lx1, this->ly1 .
334 * Return true iff there exist more segments.
335 */
336 bool
gx_flattened_iterator__next(gx_flattened_iterator * this)337 gx_flattened_iterator__next(gx_flattened_iterator *this)
338 {
339 /*
340 * We can compute successive values by finite differences,
341 * using the formulas:
342 x(t) =
343 a*t^3 + b*t^2 + c*t + d =>
344 dx(t) = x(t+e)-x(t) =
345 a*(3*t^2*e + 3*t*e^2 + e^3) + b*(2*t*e + e^2) + c*e =
346 (3*a*e)*t^2 + (3*a*e^2 + 2*b*e)*t + (a*e^3 + b*e^2 + c*e) =>
347 d2x(t) = dx(t+e)-dx(t) =
348 (3*a*e)*(2*t*e + e^2) + (3*a*e^2 + 2*b*e)*e =
349 (6*a*e^2)*t + (6*a*e^3 + 2*b*e^2) =>
350 d3x(t) = d2x(t+e)-d2x(t) =
351 6*a*e^3;
352 x(0) = d, dx(0) = (a*e^3 + b*e^2 + c*e),
353 d2x(0) = 6*a*e^3 + 2*b*e^2;
354 * In these formulas, e = 1/2^k; of course, there are separate
355 * computations for the x and y values.
356 *
357 * There is a tradeoff in doing the above computation in fixed
358 * point. If we separate out the constant term (d) and require that
359 * all the other values fit in a long, then on a 32-bit machine with
360 * 12 bits of fraction in a fixed, k = 4 implies a maximum curve
361 * size of 128 pixels; anything larger requires subdividing the
362 * curve. On the other hand, doing the computations in explicit
363 * double precision slows down the loop by a factor of 3 or so. We
364
365 * found to our surprise that the latter is actually faster, because
366 * the additional subdivisions cost more than the slower loop.
367 *
368 * We represent each quantity as I+R/M, where I is an "integer" and
369 * the "remainder" R lies in the range 0 <= R < M=2^(3*k). Note
370 * that R may temporarily exceed M; for this reason, we require that
371 * M have at least one free high-order bit. To reduce the number of
372 * variables, we don't actually compute M, only M-1 (rmask). */
373 fixed x = this->lx1, y = this->ly1;
374
375 this->lx0 = this->lx1;
376 this->ly0 = this->ly1;
377 /* Fast check for N == 3, a common special case for small characters. */
378 if (this->k <= 1) {
379 --this->i;
380 if (this->i == 0)
381 goto last;
382 # define poly2(a,b,c) arith_rshift_1(arith_rshift_1(arith_rshift_1(a) + b) + c)
383 x += poly2(this->ax, this->bx, this->cx);
384 y += poly2(this->ay, this->by, this->cy);
385 # undef poly2
386 if_debug2('3', "[3]dx=%f, dy=%f\n",
387 fixed2float(x - this->x0), fixed2float(y - this->y0));
388 if_debug5('3', "[3]%s x=%g, y=%g x=%d y=%d\n",
389 (((x ^ this->x0) | (y ^ this->y0)) & float2fixed(-0.5) ?
390 "add" : "skip"),
391 fixed2float(x), fixed2float(y), x, y);
392 this->lx1 = x, this->ly1 = y;
393 vd_bar(this->lx0, this->ly0, this->lx1, this->ly1, 1, RGB(0, 255, 0));
394 return true;
395 } else {
396 --this->i;
397 if (this->i == 0)
398 goto last; /* don't bother with last accum */
399 # ifdef DEBUG
400 gx_flattened_iterator__print_state(this);
401 # endif
402 # define accum(i, r, di, dr, rmask)\
403 if ( (r += dr) > rmask ) r &= rmask, i += di + 1;\
404 else i += di
405 accum(x, this->rx, this->idx, this->rdx, this->rmask);
406 accum(y, this->ry, this->idy, this->rdy, this->rmask);
407 accum(this->idx, this->rdx, this->id2x, this->rd2x, this->rmask);
408 accum(this->idy, this->rdy, this->id2y, this->rd2y, this->rmask);
409 accum(this->id2x, this->rd2x, this->id3x, this->rd3x, this->rmask);
410 accum(this->id2y, this->rd2y, this->id3y, this->rd3y, this->rmask);
411 if_debug5('3', "[3]%s x=%g, y=%g x=%d y=%d\n",
412 (((x ^ this->lx0) | (y ^ this->ly0)) & float2fixed(-0.5) ?
413 "add" : "skip"),
414 fixed2float(x), fixed2float(y), x, y);
415 # undef accum
416 this->lx1 = this->x = x;
417 this->ly1 = this->y = y;
418 vd_bar(this->lx0, this->ly0, this->lx1, this->ly1, 1, RGB(0, 255, 0));
419 return true;
420 }
421 last:
422 this->lx1 = this->x3;
423 this->ly1 = this->y3;
424 if_debug4('3', "[3]last x=%g, y=%g x=%d y=%d\n",
425 fixed2float(this->lx1), fixed2float(this->ly1), this->lx1, this->ly1);
426 vd_bar(this->lx0, this->ly0, this->lx1, this->ly1, 1, RGB(0, 255, 0));
427 return false;
428 }
429
430 private inline void
gx_flattened_iterator__unaccum(gx_flattened_iterator * this)431 gx_flattened_iterator__unaccum(gx_flattened_iterator *this)
432 {
433 # define unaccum(i, r, di, dr, rmask)\
434 if ( r < dr ) r += rmask + 1 - dr, i -= di + 1;\
435 else r -= dr, i -= di
436 unaccum(this->id2x, this->rd2x, this->id3x, this->rd3x, this->rmask);
437 unaccum(this->id2y, this->rd2y, this->id3y, this->rd3y, this->rmask);
438 unaccum(this->idx, this->rdx, this->id2x, this->rd2x, this->rmask);
439 unaccum(this->idy, this->rdy, this->id2y, this->rd2y, this->rmask);
440 unaccum(this->x, this->rx, this->idx, this->rdx, this->rmask);
441 unaccum(this->y, this->ry, this->idy, this->rdy, this->rmask);
442 # undef unaccum
443 }
444
445 /* Move back to the previous segment and store it to this->lx0, this->ly0, this->lx1, this->ly1 .
446 * This only works for states reached with gx_flattened_iterator__next.
447 * Return true iff there exist more segments.
448 */
449 bool
gx_flattened_iterator__prev(gx_flattened_iterator * this)450 gx_flattened_iterator__prev(gx_flattened_iterator *this)
451 {
452 bool last; /* i.e. the first one in the forth order. */
453
454 assert(this->i < 1 << this->k);
455 this->lx1 = this->lx0;
456 this->ly1 = this->ly0;
457 if (this->k <= 1) {
458 /* If k==0, we have a single segment, return it.
459 If k==1 && i < 2, return the last segment.
460 Otherwise must not pass here.
461 We caould allow to pass here with this->i == 1 << this->k,
462 but we want to check the assertion about the last segment below.
463 */
464 this->i++;
465 this->lx0 = this->x0;
466 this->ly0 = this->y0;
467 vd_bar(this->lx0, this->ly0, this->lx1, this->ly1, 1, RGB(0, 0, 255));
468 return false;
469 }
470 gx_flattened_iterator__unaccum(this);
471 this->i++;
472 # ifdef DEBUG
473 if_debug5('3', "[3]%s x=%g, y=%g x=%d y=%d\n",
474 (((this->x ^ this->lx1) | (this->y ^ this->ly1)) & float2fixed(-0.5) ?
475 "add" : "skip"),
476 fixed2float(this->x), fixed2float(this->y), this->x, this->y);
477 gx_flattened_iterator__print_state(this);
478 # endif
479 last = (this->i == (1 << this->k) - 1);
480 this->lx0 = this->x;
481 this->ly0 = this->y;
482 vd_bar(this->lx0, this->ly0, this->lx1, this->ly1, 1, RGB(0, 0, 255));
483 if (last)
484 assert(this->lx0 == this->x0 && this->ly0 == this->y0);
485 return !last;
486 }
487
488 /* Switching from the forward scanning to the backward scanning for the filtered1. */
489 void
gx_flattened_iterator__switch_to_backscan(gx_flattened_iterator * this,bool not_first)490 gx_flattened_iterator__switch_to_backscan(gx_flattened_iterator *this, bool not_first)
491 {
492 /* When scanning forth, the accumulator stands on the end of a segment,
493 except for the last segment.
494 When scanning back, the accumulator should stand on the beginning of a segment.
495 Asuuming that at least one forward step is done.
496 */
497 if (not_first)
498 if (this->i > 0 && this->k != 1 /* This case doesn't use the accumulator. */)
499 gx_flattened_iterator__unaccum(this);
500 }
501
502 #define max_points 50 /* arbitrary */
503
504 private int
generate_segments(gx_path * ppath,const gs_fixed_point * points,int count,segment_notes notes)505 generate_segments(gx_path * ppath, const gs_fixed_point *points,
506 int count, segment_notes notes)
507 {
508 /* vd_moveto(ppath->position.x, ppath->position.y); */
509 if (notes & sn_not_first) {
510 /* vd_lineto_multi(points, count); */
511 print_points(points, count);
512 return gx_path_add_lines_notes(ppath, points, count, notes);
513 } else {
514 int code;
515
516 /* vd_lineto(points[0].x, points[0].y); */
517 print_points(points, 1);
518 code = gx_path_add_line_notes(ppath, points[0].x, points[0].y, notes);
519 if (code < 0)
520 return code;
521 /* vd_lineto_multi(points + 1, count - 1); */
522 print_points(points + 1, count - 1);
523 return gx_path_add_lines_notes(ppath, points + 1, count - 1, notes | sn_not_first);
524 }
525 }
526
527 private int
gx_subdivide_curve_rec(gx_flattened_iterator * this,gx_path * ppath,int k,curve_segment * pc,segment_notes notes,gs_fixed_point * points)528 gx_subdivide_curve_rec(gx_flattened_iterator *this,
529 gx_path * ppath, int k, curve_segment * pc,
530 segment_notes notes, gs_fixed_point *points)
531 {
532 int code;
533
534 top :
535 if (!gx_flattened_iterator__init(this,
536 ppath->position.x, ppath->position.y, pc, k)) {
537 /* Curve is too long. Break into two pieces and recur. */
538 curve_segment cseg;
539
540 k--;
541 split_curve_midpoint(ppath->position.x, ppath->position.y, pc, &cseg, pc);
542 code = gx_subdivide_curve_rec(this, ppath, k, &cseg, notes, points);
543 if (code < 0)
544 return code;
545 notes |= sn_not_first;
546 goto top;
547 } else if (k == -1) {
548 /* fixme : Don't need to init the iterator. Just wanted to check in_range. */
549 return gx_path_add_curve_notes(ppath, pc->p1.x, pc->p1.y, pc->p2.x, pc->p2.y,
550 pc->pt.x, pc->pt.y, notes);
551 } else {
552 gs_fixed_point *ppt = points;
553 bool more;
554
555 for(;;) {
556 more = gx_flattened_iterator__next(this);
557 ppt->x = this->lx1;
558 ppt->y = this->ly1;
559 ppt++;
560 if (ppt == &points[max_points] || !more) {
561 gs_fixed_point *pe = (more ? ppt - 2 : ppt);
562
563 code = generate_segments(ppath, points, pe - points, notes);
564 if (code < 0)
565 return code;
566 if (!more)
567 return 0;
568 notes |= sn_not_first;
569 memcpy(points, pe, (char *)ppt - (char *)pe);
570 ppt = points + (ppt - pe);
571 }
572 }
573 }
574 }
575
576 #undef coord_near
577
578 /*
579 * Flatten a segment of the path by repeated sampling.
580 * 2^k is the number of lines to produce (i.e., the number of points - 1,
581 * including the endpoints); we require k >= 1.
582 * If k or any of the coefficient values are too large,
583 * use recursive subdivision to whittle them down.
584 */
585
586 int
gx_subdivide_curve(gx_path * ppath,int k,curve_segment * pc,segment_notes notes)587 gx_subdivide_curve(gx_path * ppath, int k, curve_segment * pc, segment_notes notes)
588 {
589 gs_fixed_point points[max_points + 1];
590 gx_flattened_iterator iter;
591
592 return gx_subdivide_curve_rec(&iter, ppath, k, pc, notes, points);
593 }
594
595 #undef max_points
596
597
598