Generalize the trapezoid fillling algorithm for curves, step 6.
"Igor V. Melichev" <[email protected]>
| Newsgroups | gmane.comp.printing.ghostscript.patches |
|---|---|
| Message-ID | <[email protected]> |
Not committed yet.
This patch includes changes of the step 5.
They to be removed after the step 5 is committed.
The log message of this patch doesn't reflect changes of step 5.
[Log message beg]
Generalize the trapezoid filling algorithm for curves, step 6.
DETAILS :
This change modifies a disabled code,
and includes a minor change to the enabled code,
which should be algorithmically equivalent.
In the enabled code factored out the new function add_y_line_aux.
This patch fixes the dropout problem in CURVED_TRAPEZOID_FILL 1.
The problem was unprocessed horizontal segments of curves.
Now we create a new temporary horizontal line for
each horizontal segment of a curve, and add it to the Y list.
Then it immediately goes to H list, and then processed and freed.
Due to the modification of the Y list during the main
trapezoid loop (which did not happen before) the cycle
commented with
/* Move newly active lines from y to x list. */
is improved with providing a consistency of local copies
of the Y list pointers.
Good tests for this stuff present in a.pdf .
With this patch with ppmraw 72dpi it renders equal to
with CURVED_TRAPEZOID_FILL 0 code.
EXPECTED DIFFERENCES :
None.
[Log message end]
Changes:
*** f:\casper\HEAD\gs\src\gx.h Thu Dec 4 14:09:44 2003
--- files\gs\src\gx.h Mon Dec 8 04:36:48 2003
***************
*** 33,36 ****
--- 33,38 ----
#define FLATTENED_CURVE_ITERATOR0_COMPATIBLE 1 /* Temporarily used for a
backward compatibility. */
#define CURVED_TRAPEZOID_FILL (FLATTENED_CURVE_ITERATOR & 0) /* old code =
0, new code = 1. */
+ #define CURVED_TRAPEZOID_FILL_SCANS_BACK /* Temporarily used for a
backward compatibility. */\
+ (CURVED_TRAPEZOID_FILL & FLATTENED_CURVE_ITERATOR0_COMPATIBLE & 1)
/* Define opaque types for the graphics state. */
*** f:\casper\HEAD\gs\src\gxfdrop.c Sun Dec 7 19:17:20 2003
--- files\gs\src\gxfdrop.c Sun Dec 7 19:18:02 2003
***************
*** 30,33 ****
--- 30,38 ----
#include "vdtrace.h"
+ #define INTERTRAP_STEM_BUG 0 /* We're not sure that 1 gives a
+ better painting with neighbour serifs.
+ Need more testing.
+ 0 is compatible to the old code. */
+
/*
* Rather some margins are placed in virtual memory,
***************
*** 504,513 ****
# else
if (sect[i].x0 > 0 && sect[i].x1 == fixed_1 && i + 1 < i1) {
hh = (i + 1 < i1 ? compute_padding(§[i + 1]) : -2);
/* We could cache hh.
* Delaying the optimization until the code is well tested.
*/
! } else if (sect[i].x0 == 0 && sect[i].x1 < fixed_1)
hh = h;
# endif
}
--- 509,549 ----
# else
if (sect[i].x0 > 0 && sect[i].x1 == fixed_1 && i + 1 < i1) {
+ # if INTERTRAP_STEM_BUG
+ int hhh = hh;
+ # endif
hh = (i + 1 < i1 ? compute_padding(§[i + 1]) : -2);
/* We could cache hh.
* Delaying the optimization until the code is well tested.
*/
! # if INTERTRAP_STEM_BUG
! /* A bug in the old code. */
! if (i > i0 && i + 1 < i1 && hh == -2 &&
! compute_padding(§[i - 1]) == -2) {
! /* It can be either a thin stem going from left to up or down
! (See 'r' in 01-001.ps in 'General', ppmraw, 72dpi),
! or a serif from the left.
! Since it is between 2 trapezoids, it is better to paint it
! against a dropout. */
! hh = hhh;
! }
! # endif
! } else if (sect[i].x0 == 0 && sect[i].x1 < fixed_1) {
! # if INTERTRAP_STEM_BUG
! int hhh = hh;
! # endif
hh = h;
+ # if INTERTRAP_STEM_BUG
+ /* A bug in the old code. */
+ if (i > i0 && i + 1 < i1 && hh == -2 &&
+ compute_padding(§[i - 1]) == -2) {
+ /* It can be either a thin stem going from right to up or down
+ (See 'r' in 01-001.ps in 'General', ppmraw, 72dpi),
+ or a serif from the right.
+ Since it is between 2 trapezoids, it is better to paint it.
+ against a dropout. */
+ DO_NOTHING;
+ }
+ # endif
+ }
# endif
}
*** f:\casper\HEAD\gs\src\gxfill.c Thu Dec 4 19:19:57 2003
--- files\gs\src\gxfill.c Mon Dec 8 04:21:17 2003
***************
*** 36,39 ****
--- 36,42 ----
# include "gzspotan.h" /* Only for gx_san_trap_store. */
#endif
+ #if CURVED_TRAPEZOID_FILL_SCANS_BACK
+ #include "memory_.h"
+ #endif
#include "vdtrace.h"
#include <assert.h>
***************
*** 801,842 ****
#if CURVED_TRAPEZOID_FILL
private void
! step_al(active_line *alp)
{
alp->more_flattened = gx_flattened_curve_iterator__next(&alp->fi);
/* Note that we can get alp->fi.ly0 == alp->fi.ly1
with the first or the last piece of the line. */
! alp->start.x = alp->fi.lx0;
! alp->start.y = alp->fi.ly0;
! #if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
! /* We can't provide a full compatibility because
! the new code flattens DIR_DOWN curves in the reverse direction.
! (Division points may be shifted due to the numeric errors
difference,
! and MERGE_COLLINEAR_SEGMENTS drops different points.)
! But this shouldn't cause a difference for monotonic curves. */
! if (alp->direction == DIR_UP && alp->first_flattened) {
! /* The old code isn't symmetric : it always yields the first point. */
! } else {
! /* fixme: optimize. */
while (alp->more_flattened) {
bool more;
- gx_flattened_curve_iterator fi = alp->fi;
! more = gx_flattened_curve_iterator__next(&fi);
! if (alp->direction == DIR_DOWN && !more) {
! /* The old code isn't symmetric : it always yields the last point. */
break;
! }
! if (!gx_check_nearly_collinear(&alp->start.x, &alp->start.y,
! &fi.lx0, &fi.ly0, &fi.lx1, &fi.ly1))
break;
alp->more_flattened = more;
alp->fi = fi;
}
}
alp->first_flattened = false;
! #endif
! alp->end.x = alp->fi.lx1;
! alp->end.y = alp->fi.ly1;
alp->diff.x = alp->end.x - alp->start.x;
alp->diff.y = alp->end.y - alp->start.y;
--- 804,873 ----
#if CURVED_TRAPEZOID_FILL
+
private void
! step_al(active_line *alp, bool move_iterator)
{
+ #if CURVED_TRAPEZOID_FILL_SCANS_BACK
+ bool forth = (alp->direction == DIR_UP || !alp->fi.curve);
+
+ if (move_iterator) {
+ if (forth)
alp->more_flattened = gx_flattened_curve_iterator__next(&alp->fi);
+ else
+ alp->more_flattened = gx_flattened_curve_iterator__prev(&alp->fi);
+ } else
+ vd_bar(alp->fi.lx0, alp->fi.ly0, alp->fi.lx1, alp->fi.ly1, 1, RGB(0, 0,
255));
+ #else
+ const bool forth = true;
+
+ alp->more_flattened = gx_flattened_curve_iterator__next(&alp->fi);
+ #endif
/* Note that we can get alp->fi.ly0 == alp->fi.ly1
with the first or the last piece of the line. */
! alp->start.x = (forth ? alp->fi.lx0 : alp->fi.lx1);
! alp->start.y = (forth ? alp->fi.ly0 : alp->fi.ly1);
! # if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
! if (move_iterator) {
! if (forth) {
! gx_flattened_curve_iterator fi = alp->fi;
!
while (alp->more_flattened) {
bool more;
! if (alp->first_flattened)
break;
! more = gx_flattened_curve_iterator__next(&fi);
! if (!more ||
! !gx_check_nearly_collinear(alp->start.x, alp->start.y,
! fi.lx0, fi.ly0, fi.lx1, fi.ly1))
break;
alp->more_flattened = more;
alp->fi = fi;
}
+ } else {
+ # if CURVED_TRAPEZOID_FILL_SCANS_BACK
+ while (alp->more_flattened &&
+ (alp->fi.i + 1) <= sizeof(alp->skip_points) * 8 &&
+ !(alp->skip_points[(alp->fi.i + 1) >> 3] & (1 << ((alp->fi.i + 1) &
7)))) {
+ alp->more_flattened = gx_flattened_curve_iterator__prev(&alp->fi);
+ }
+ /* CAUTION: if skip_points array is smaller than the
+ nomber of points, the flattening isn't equal to one
+ generated with the old code. The maximal necessary array
+ length is 128 = (1 << k_sample_max) / 8.
+ */
+ DO_NOTHING; /* Just a place for a debugger breakpoint. */
+ # else
+ /* We can't provide a full compatibility because
+ the new code flattens DIR_DOWN curves in the reverse direction.
+ The reason is the point filtering applied in
gx_subdivide_curve_rec.
+ That filtering is not reversible. */
+ # endif
}
alp->first_flattened = false;
! }
! # endif
! alp->end.x = (forth ? alp->fi.lx1 : alp->fi.lx0);
! alp->end.y = (forth ? alp->fi.ly1 : alp->fi.ly0);
alp->diff.x = alp->end.x - alp->start.x;
alp->diff.y = alp->end.y - alp->start.y;
***************
*** 849,855 ****
init_al(active_line *alp, const segment *s0, const segment *s1, fixed
fixed_flat)
{
/* Warning : p0 may be equal to &alp->end. */
! if ((alp->direction == DIR_UP ? s1 : s0)->type == s_curve) {
if (alp->direction == DIR_UP) {
int k = gx_curve_log2_samples(s0->pt.x, s0->pt.y, (curve_segment
*)s1, fixed_flat);
--- 880,891 ----
init_al(active_line *alp, const segment *s0, const segment *s1, fixed
fixed_flat)
{
+ const segment *ss = (alp->direction == DIR_UP ? s1 : s0);
/* Warning : p0 may be equal to &alp->end. */
+ bool curve = (ss != NULL && ss->type == s_curve);
! #if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
! alp->first_flattened = true;
! #endif
! if (curve) {
if (alp->direction == DIR_UP) {
int k = gx_curve_log2_samples(s0->pt.x, s0->pt.y, (curve_segment
*)s1, fixed_flat);
***************
*** 857,879 ****
assert(gx_flattened_curve_iterator__init(&alp->fi,
s0->pt.x, s0->pt.y, (curve_segment *)s1, k, false, 0));
} else {
int k = gx_curve_log2_samples(s1->pt.x, s1->pt.y, (curve_segment
*)s0, fixed_flat);
assert(gx_flattened_curve_iterator__init(&alp->fi,
s1->pt.x, s1->pt.y, (curve_segment *)s0, k, true, 0));
}
} else {
assert(gx_flattened_curve_iterator__init_line(&alp->fi,
! s0->pt.x, s0->pt.y, (line_segment *)s1, 0));
}
alp->pseg = s1;
- #if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
- alp->first_flattened = true;
- #endif
- step_al(alp);
}
#endif
-
/*
* Internal routine to test a segment and add it to the pending list if
--- 893,946 ----
assert(gx_flattened_curve_iterator__init(&alp->fi,
s0->pt.x, s0->pt.y, (curve_segment *)s1, k, false, 0));
+ step_al(alp, true);
} else {
int k = gx_curve_log2_samples(s1->pt.x, s1->pt.y, (curve_segment
*)s0, fixed_flat);
+ # if CURVED_TRAPEZOID_FILL_SCANS_BACK
+ bool more, first = true;
+ gx_flattened_curve_iterator fi;
+
+ memset(alp->skip_points, 0, sizeof(alp->skip_points));
+ assert(gx_flattened_curve_iterator__init(&alp->fi,
+ s1->pt.x, s1->pt.y, (curve_segment *)s0, k, false, 0));
+ alp->more_flattened = false;
+ do {
+ fixed x = alp->fi.lx1, y = alp->fi.ly1;
+
+ more = gx_flattened_curve_iterator__next(&alp->fi);
+ alp->more_flattened |= more;
+ if (!first) {
+ fi = alp->fi;
+ while (more) {
+ more = gx_flattened_curve_iterator__next(&fi);
+ if (!more) {
+ more = true;
+ break;
+ }
+ if (!gx_check_nearly_collinear(x, y, fi.lx0, fi.ly0, fi.lx1,
fi.ly1))
+ break;
+ alp->fi = fi;
+ }
+ }
+ if (alp->fi.i <= sizeof(alp->skip_points) * 8)
+ alp->skip_points[alp->fi.i >> 3] |= 1 << (alp->fi.i & 7);
+ first = false;
+ } while(more);
+ step_al(alp, false);
+ # else
assert(gx_flattened_curve_iterator__init(&alp->fi,
s1->pt.x, s1->pt.y, (curve_segment *)s0, k, true, 0));
+ step_al(alp, true);
+ # endif
}
} else {
assert(gx_flattened_curve_iterator__init_line(&alp->fi,
! s0->pt.x, s0->pt.y, s1->pt.x, s1->pt.y, 0));
! step_al(alp, true);
}
alp->pseg = s1;
}
#endif
/*
* Internal routine to test a segment and add it to the pending list if
***************
*** 881,887 ****
*/
private int
! add_y_line(const segment * prev_lp, const segment * lp, int dir, line_list
*ll)
{
- gs_fixed_point this, prev;
active_line *alp = ll->next_active;
fixed y_start;
--- 948,954 ----
*/
private int
! add_y_line_aux(const segment * prev_lp, const segment * lp,
! const gs_fixed_point *curr, const gs_fixed_point *prev, int dir,
line_list *ll)
{
active_line *alp = ll->next_active;
fixed y_start;
***************
*** 897,904 ****
} else
ll->next_active++;
- this.x = lp->pt.x;
- this.y = lp->pt.y;
- prev.x = prev_lp->pt.x;
- prev.y = prev_lp->pt.y;
# if CURVED_TRAPEZOID_FILL
alp->more_flattened = false;
--- 964,967 ----
***************
*** 906,910 ****
switch ((alp->direction = dir)) {
case DIR_UP:
! y_start = prev.y;
# if CURVED_TRAPEZOID_FILL
if (ll->fill_by_trapezoids)
--- 969,973 ----
switch ((alp->direction = dir)) {
case DIR_UP:
! y_start = prev->y;
# if CURVED_TRAPEZOID_FILL
if (ll->fill_by_trapezoids)
***************
*** 912,921 ****
else
# endif
! { SET_AL_POINTS(alp, prev, this);
alp->pseg = lp;
}
break;
case DIR_DOWN:
! y_start = this.y;
# if CURVED_TRAPEZOID_FILL
if (ll->fill_by_trapezoids)
--- 975,984 ----
else
# endif
! { SET_AL_POINTS(alp, *prev, *curr);
alp->pseg = lp;
}
break;
case DIR_DOWN:
! y_start = curr->y;
# if CURVED_TRAPEZOID_FILL
if (ll->fill_by_trapezoids)
***************
*** 923,934 ****
else
# endif
! { SET_AL_POINTS(alp, this, prev);
alp->pseg = prev_lp;
}
break;
case DIR_HORIZONTAL:
! y_start = this.y; /* = prev.y */
! alp->start = prev;
! alp->end = this;
/* Don't need to set dx or y_fast_max */
alp->pseg = prev_lp; /* may not need this either */
--- 986,997 ----
else
# endif
! { SET_AL_POINTS(alp, *curr, *prev);
alp->pseg = prev_lp;
}
break;
case DIR_HORIZONTAL:
! y_start = curr->y; /* = prev.y */
! alp->start = *prev;
! alp->end = *curr;
/* Don't need to set dx or y_fast_max */
alp->pseg = prev_lp; /* may not need this either */
***************
*** 976,979 ****
--- 1039,1048 ----
return 0;
}
+ private int
+ add_y_line(const segment * prev_lp, const segment * lp, int dir, line_list
*ll)
+ {
+ return add_y_line_aux(prev_lp, lp, &lp->pt, &prev_lp->pt, dir, ll);
+ }
+
/* ---------------- Filling loop utilities ---------------- */
***************
*** 1251,1255 ****
if (alp->end.y == y1)
if (alp->more_flattened)
! step_al(alp);
}
# endif
--- 1320,1324 ----
if (alp->end.y == y1)
if (alp->more_flattened)
! step_al(alp, true);
}
# endif
***************
*** 1267,1270 ****
--- 1336,1363 ----
}
+ #if CURVED_TRAPEZOID_FILL
+ /* Process horizontal segment of curves. */
+ private int
+ process_h_segments(line_list *ll, fixed y)
+ {
+ active_line *alp;
+ int code, inserted = 0;
+
+ for (alp = ll->x_list; alp != 0; alp = alp->next) {
+ if (alp->more_flattened/* HACK */ && alp->start.y == y && alp->end.y ==
y) {
+ code = add_y_line_aux(NULL, NULL, &alp->start, &alp->end,
DIR_HORIZONTAL, ll);
+ if (code < 0)
+ return code;
+ step_al(alp, true);
+ inserted = 1;
+ }
+ }
+ for (alp = ll->x_list; alp != 0; alp = alp->next)
+ assert(alp->pseg != NULL);
+ return inserted;
+ /* After this should call move_al_by_y and step to the next band. */
+ }
+ #endif
+
private int
loop_fill_trap(gx_device * dev, fixed fx0, fixed fw0, fixed fy0,
***************
*** 1631,1634 ****
--- 1724,1734 ----
active_line *ynext = yll->next; /* insert smashes next/prev links */
+ # if CURVED_TRAPEZOID_FILL
+ ll->y_list = ynext;
+ if (ll->y_line == yll)
+ ll->y_line = ynext;
+ if (ynext != NULL)
+ ynext->prev = NULL;
+ # endif
if (yll->direction == DIR_HORIZONTAL) {
if (!pseudo_rasterization) {
***************
*** 1689,1693 ****
if (alp->end.y < y1)
y1 = alp->end.y;
! #ifdef DEBUG
if (gs_debug_c('F')) {
dlprintf2("[F]before loop: y=%f y1=%f:\n",
--- 1789,1793 ----
if (alp->end.y < y1)
y1 = alp->end.y;
! # ifdef DEBUG
if (gs_debug_c('F')) {
dlprintf2("[F]before loop: y=%f y1=%f:\n",
***************
*** 1695,1699 ****
print_line_list(ll->x_list);
}
! #endif
/* Now look for line intersections before y1. */
covering_pixel_centers = COVERING_PIXEL_CENTERS(y, y1, adjust_below,
adjust_above);
--- 1795,1811 ----
print_line_list(ll->x_list);
}
! # endif
! # if CURVED_TRAPEZOID_FILL
! if (y == y1) {
! code = process_h_segments(ll, y);
! if (code < 0)
! return code;
! if (code > 0) {
! yll = ll->y_list; /* add_y_line_aux in process_h_segments changes it. */
! continue;
! }
!
! }
! # endif
/* Now look for line intersections before y1. */
covering_pixel_centers = COVERING_PIXEL_CENTERS(y, y1, adjust_below,
adjust_above);
***************
*** 1727,1730 ****
--- 1839,1844 ----
int code;
+ assert(y >= alp->start.y);
+
print_al("step", alp);
INCR(band_step);
***************
*** 1810,1817 ****
}
move_al_by_y(ll, y1);
- if (!CURVED_TRAPEZOID_FILL || y != y1) {
ll->h_list1 = ll->h_list0;
ll->h_list0 = 0;
- }
y = y1;
}
--- 1924,1929 ----
*** f:\casper\HEAD\gs\src\gxfill.h Thu Dec 4 14:09:44 2003
--- files\gs\src\gxfill.h Sun Dec 7 15:12:23 2003
***************
*** 84,87 ****
--- 84,95 ----
#if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
bool first_flattened;
+ #if CURVED_TRAPEZOID_FILL_SCANS_BACK
+ byte skip_points[128]; /* This huge thing is for testing purpose
only.
+ The length should be (1 << k_sample_max) bits.
+ 128 sholuld be fine.
+ With a smaller value the code is working,
+ but the result is not guaranteed to be
+ equal to the old code. */
+ #endif
#endif
#endif
*** f:\casper\HEAD\gs\src\gxpflat.c Thu Dec 4 19:19:57 2003
--- files\gs\src\gxpflat.c Mon Dec 8 03:38:22 2003
***************
*** 22,25 ****
--- 22,26 ----
#include "gzpath.h"
#include "vdtrace.h"
+ #include <assert.h>
/* Define whether to merge nearly collinear line segments when flattening
*/
***************
*** 547,555 ****
this->y3 = y0;
}
- # if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
# if CURVED_TRAPEZOID_FILL
this->reverse = reverse;
# endif
# endif
vd_curve(this->x0, this->y0, x1, y1, x2, y2, this->x3, this->y3, 0,
RGB(255, 255, 255));
this->k = k;
--- 548,560 ----
this->y3 = y0;
}
# if CURVED_TRAPEZOID_FILL
+ # if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
+ # if CURVED_TRAPEZOID_FILL_SCANS_BACK
+ this->curve = true;
+ # else
this->reverse = reverse;
# endif
# endif
+ # endif
vd_curve(this->x0, this->y0, x1, y1, x2, y2, this->x3, this->y3, 0,
RGB(255, 255, 255));
this->k = k;
***************
*** 625,645 ****
bool
gx_flattened_curve_iterator__init_line(gx_flattened_curve_iterator *this,
! fixed x0, fixed y0, const line_segment *pc, segment_notes notes)
{
this->x0 = this->lx0 = this->lx1 = x0;
this->y0 = this->ly0 = this->ly1 = y0;
! this->x3 = pc->pt.x;
! this->y3 = pc->pt.y;
! this->k = 1;
this->i = 1;
return true;
}
#define coord_near(v, ptv) (!( ((v) ^ (ptv)) & float2fixed(-0.5) ))
/* Move to the next segment and store it to this->lx0, this->ly0,
this->lx1, this->ly1 .
! * Return false iff it's a last segment.
* Note : The number of generated segments can be samller than 2^k
! * due to the empty segment skipping.
* Note : It can generate collinear segments.
*/
--- 630,674 ----
bool
gx_flattened_curve_iterator__init_line(gx_flattened_curve_iterator *this,
! fixed x0, fixed y0, fixed x1, fixed y1, segment_notes notes)
{
this->x0 = this->lx0 = this->lx1 = x0;
this->y0 = this->ly0 = this->ly1 = y0;
! this->x3 = x1;
! this->y3 = y1;
! this->k = 0;
this->i = 1;
+ # if CURVED_TRAPEZOID_FILL
+ # if CURVED_TRAPEZOID_FILL_SCANS_BACK
+ this->curve = false;
+ # endif
+ # endif
return true;
}
+ #ifdef DEBUG
+ private inline void
+ gx_flattened_curve_iterator__print_state(gx_flattened_curve_iterator
*this)
+ {
+ if (!gs_debug_c('3'))
+ return;
+ dlprintf4("[3]dx=%f+%d, dy=%f+%d\n",
+ fixed2float(this->idx), this->rdx,
+ fixed2float(this->idy), this->rdy);
+ dlprintf4(" d2x=%f+%d, d2y=%f+%d\n",
+ fixed2float(this->id2x), this->rd2x,
+ fixed2float(this->id2y), this->rd2y);
+ dlprintf4(" d3x=%f+%d, d3y=%f+%d\n",
+ fixed2float(this->id3x), this->rd3x,
+ fixed2float(this->id3y), this->rd3y);
+ }
+ #endif
+
+
#define coord_near(v, ptv) (!( ((v) ^ (ptv)) & float2fixed(-0.5) ))
/* Move to the next segment and store it to this->lx0, this->ly0,
this->lx1, this->ly1 .
! * Return true iff there exist more segments.
* Note : The number of generated segments can be samller than 2^k
! * due to the small segment skipping.
* Note : It can generate collinear segments.
*/
***************
*** 686,690 ****
this->ly0 = this->ly1;
/* Fast check for N == 3, a common special case for small characters.
*/
! if (this->k == 1) {
if (--this->i == 0)
goto last;
--- 715,719 ----
this->ly0 = this->ly1;
/* Fast check for N == 3, a common special case for small characters.
*/
! if (this->k <= 1) {
if (--this->i == 0)
goto last;
***************
*** 700,705 ****
fixed2float(x), fixed2float(y), x, y);
if (
! # if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
! # if CURVED_TRAPEZOID_FILL
this->reverse ? ((x ^ this->x3) | (y ^ this->y3)) & float2fixed(-0.5)
: ((x ^ this->x0) | (y ^ this->y0)) & float2fixed(-0.5)
--- 729,734 ----
fixed2float(x), fixed2float(y), x, y);
if (
! # if FLATTENED_CURVE_ITERATOR0_COMPATIBLE ||
CURVED_TRAPEZOID_FILL_SCANS_BACK
! # if CURVED_TRAPEZOID_FILL && !CURVED_TRAPEZOID_FILL_SCANS_BACK
this->reverse ? ((x ^ this->x3) | (y ^ this->y3)) & float2fixed(-0.5)
: ((x ^ this->x0) | (y ^ this->y0)) & float2fixed(-0.5)
***************
*** 724,738 ****
break; /* don't bother with last accum */
# ifdef DEBUG
! if (gs_debug_c('3')) {
! dlprintf4("[3]dx=%f+%d, dy=%f+%d\n",
! fixed2float(this->idx), this->rdx,
! fixed2float(this->idy), this->rdy);
! dlprintf4(" d2x=%f+%d, d2y=%f+%d\n",
! fixed2float(this->id2x), this->rd2x,
! fixed2float(this->id2y), this->rd2y);
! dlprintf4(" d3x=%f+%d, d3y=%f+%d\n",
! fixed2float(this->id3x), this->rd3x,
! fixed2float(this->id3y), this->rd3y);
! }
# endif
# define accum(i, r, di, dr, rmask)\
--- 753,757 ----
break; /* don't bother with last accum */
# ifdef DEBUG
! gx_flattened_curve_iterator__print_state(this);
# endif
# define accum(i, r, di, dr, rmask)\
***************
*** 742,747 ****
accum(y, this->ry, this->idy, this->rdy, this->rmask);
accum(this->idx, this->rdx, this->id2x, this->rd2x, this->rmask);
- accum(this->id2x, this->rd2x, this->id3x, this->rd3x, this->rmask);
accum(this->idy, this->rdy, this->id2y, this->rd2y, this->rmask);
accum(this->id2y, this->rd2y, this->id3y, this->rd3y, this->rmask);
if_debug5('3', "[3]%s x=%g, y=%g x=%d y=%d\n",
--- 761,766 ----
accum(y, this->ry, this->idy, this->rdy, this->rmask);
accum(this->idx, this->rdx, this->id2x, this->rd2x, this->rmask);
accum(this->idy, this->rdy, this->id2y, this->rd2y, this->rmask);
+ accum(this->id2x, this->rd2x, this->id3x, this->rd3x, this->rmask);
accum(this->id2y, this->rd2y, this->id3y, this->rd3y, this->rmask);
if_debug5('3', "[3]%s x=%g, y=%g x=%d y=%d\n",
***************
*** 750,754 ****
fixed2float(x), fixed2float(y), x, y);
if (!coord_near(x, this->lx0) || !coord_near(y, this->ly0))
! break; /* X coordinates are within a half-pixel. */
}
# undef accum
--- 769,773 ----
fixed2float(x), fixed2float(y), x, y);
if (!coord_near(x, this->lx0) || !coord_near(y, this->ly0))
! break; /* X coordinates are not within a half-pixel. */
}
# undef accum
***************
*** 756,763 ****
--- 775,790 ----
this->lx1 = x;
this->ly1 = y;
+ # if FLATTENED_CURVE_ITERATOR0_COMPATIBLE &&
CURVED_TRAPEZOID_FILL_SCANS_BACK
+ this->x = x;
+ this->y = y;
+ # endif
vd_bar(this->lx0, this->ly0, this->lx1, this->ly1, 1, RGB(0, 255,
0));
return true;
}
}
+ # if FLATTENED_CURVE_ITERATOR0_COMPATIBLE &&
CURVED_TRAPEZOID_FILL_SCANS_BACK
+ this->x = x;
+ this->y = y;
+ # endif
last:
this->lx1 = this->x3;
***************
*** 769,772 ****
--- 796,879 ----
}
+ #if CURVED_TRAPEZOID_FILL_SCANS_BACK
+ /* Move back to the previous segment and store it to this->lx0, this->ly0,
this->lx1, this->ly1 .
+ * This only works for states reached with
gx_flattened_curve_iterator__next.
+ * Return true iff there exist more segments.
+ * Note : The number of generated segments can be samller than 2^k
+ * due to the small segment skipping.
+ * Note : It can generate collinear segments.
+ */
+ bool
+ gx_flattened_curve_iterator__prev(gx_flattened_curve_iterator *this)
+ {
+ fixed x, y;
+ bool last; /* i.e. the first one in the forth order. */
+
+ assert(this->i < 1 << this->k);
+ this->lx1 = this->lx0;
+ this->ly1 = this->ly0;
+ if (this->k <= 1) {
+ /* If k==0, we have a single segment, return it.
+ If k==1 && i < 2, return the last segment.
+ Otherwise must not pass here.
+ We caould allow to pass here with this->i == 1 << this->k,
+ but we want to check the assertion about the last segment below.
+ */
+ this->i++;
+ this->lx0 = this->x0;
+ this->ly0 = this->y0;
+ vd_bar(this->lx0, this->ly0, this->lx1, this->ly1, 1, RGB(0, 0, 255));
+ return false;
+ }
+ x = this->x;
+ y = this->y;
+ for(;;) {
+ # define unaccum(i, r, di, dr, rmask)\
+ if ( r < dr ) r += rmask + 1 - dr, i -= di + 1;\
+ else r -= dr, i -= di
+ unaccum(this->id2x, this->rd2x, this->id3x, this->rd3x, this->rmask);
+ unaccum(this->id2y, this->rd2y, this->id3y, this->rd3y, this->rmask);
+ unaccum(this->idx, this->rdx, this->id2x, this->rd2x, this->rmask);
+ unaccum(this->idy, this->rdy, this->id2y, this->rd2y, this->rmask);
+ unaccum(x, this->rx, this->idx, this->rdx, this->rmask);
+ unaccum(y, this->ry, this->idy, this->rdy, this->rmask);
+ this->i++;
+ # undef unaccum
+ # ifdef DEBUG
+ if_debug5('3', "[3]%s x=%g, y=%g x=%d y=%d\n",
+ (((x ^ this->lx1) | (y ^ this->ly1)) & float2fixed(-0.5) ?
+ "add" : "skip"),
+ fixed2float(x), fixed2float(y), x, y);
+ gx_flattened_curve_iterator__print_state(this);
+ # endif
+ last = (this->i == (1 << this->k) - 1);
+ if (last)
+ break;
+ # if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
+ break;
+ # else
+ if (!coord_near(x, this->lx1) || !coord_near(y, this->ly1)) {
+ /* X coordinates are not within a half-pixel. */
+ break;
+ }
+ # endif
+ }
+ this->lx0 = this->x = x;
+ this->ly0 = this->y = y;
+ vd_bar(this->lx0, this->ly0, this->lx1, this->ly1, 1, RGB(0, 0, 255));
+ if (last)
+ assert(this->lx0 == this->x0 && this->ly0 == this->y0);
+ return !last;
+ }
+
+ # if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
+ bool
+ gx_flattened_check_near(fixed x0, fixed y0, fixed x1, fixed y1)
+ {
+ return coord_near(x0, x1) && coord_near(y0, y1);
+ }
+ #endif
+ #endif /* CURVED_TRAPEZOID_FILL_SCANS_BACK */
+
#define max_points 50 /* arbitrary */
***************
*** 814,832 ****
*/
private inline bool
! gx_check_nearly_collinear_inline(fixed *x0, fixed *y0, fixed *x1, fixed
*y1, fixed *x2, fixed *y2)
{
#if MERGE_COLLINEAR_SEGMENTS
/* fixme: optimise: don't check the coordinate order for monotonic
curves. */
# define coords_in_order(v0, v1, v2) ( (((v1) - (v0)) ^ ((v2) - (v1)))
>= 0 )
! if (coord_near(*x2, *x1)) { /* X coordinates are within a half-pixel.
*/
! if (coord_near(*x2, *x0) &&
! coords_in_order(*x0, *x1, *x2) &&
! coords_in_order(*y0, *y1, *y2))
return true;
}
! if (coord_near(*y2, *y1)) { /* Y coordinates are within a half-pixel.
*/
! if (coord_near(*y2, *y0) &&
! coords_in_order(*x0, *x1, *x2) &&
! coords_in_order(*y0, *y1, *y2))
return true;
}
--- 921,939 ----
*/
private inline bool
! gx_check_nearly_collinear_inline(fixed x0, fixed y0, fixed x1, fixed y1,
fixed x2, fixed y2)
{
#if MERGE_COLLINEAR_SEGMENTS
/* fixme: optimise: don't check the coordinate order for monotonic
curves. */
# define coords_in_order(v0, v1, v2) ( (((v1) - (v0)) ^ ((v2) - (v1)))
>= 0 )
! if (coord_near(x2, x1)) { /* X coordinates are within a half-pixel. */
! if (coord_near(x2, x0) &&
! coords_in_order(x0, x1, x2) &&
! coords_in_order(y0, y1, y2))
return true;
}
! if (coord_near(y2, y1)) { /* Y coordinates are within a half-pixel. */
! if (coord_near(y2, y0) &&
! coords_in_order(x0, x1, x2) &&
! coords_in_order(y0, y1, y2))
return true;
}
***************
*** 838,842 ****
#if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
bool
! gx_check_nearly_collinear(fixed *x0, fixed *y0, fixed *x1, fixed *y1,
fixed *x2, fixed *y2)
{
return gx_check_nearly_collinear_inline(x0, y0, x1, y1, x2, y2);
--- 945,949 ----
#if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
bool
! gx_check_nearly_collinear(fixed x0, fixed y0, fixed x1, fixed y1, fixed
x2, fixed y2)
{
return gx_check_nearly_collinear_inline(x0, y0, x1, y1, x2, y2);
***************
*** 875,880 ****
not_last = gx_flattened_curve_iterator__next(this);
if (ppt > points + 1 && (!FLATTENED_CURVE_ITERATOR0_COMPATIBLE ||
not_last))
! if (gx_check_nearly_collinear_inline(&ppt[-2].x, &ppt[-2].y,
! &ppt[-1].x, &ppt[-1].y, &this->lx1, &this->ly1))
--ppt; /* remove middle point */
if (!FLATTENED_CURVE_ITERATOR0_COMPATIBLE || !not_last) {
--- 982,987 ----
not_last = gx_flattened_curve_iterator__next(this);
if (ppt > points + 1 && (!FLATTENED_CURVE_ITERATOR0_COMPATIBLE ||
not_last))
! if (gx_check_nearly_collinear_inline(ppt[-2].x, ppt[-2].y,
! ppt[-1].x, ppt[-1].y, this->lx1, this->ly1))
--ppt; /* remove middle point */
if (!FLATTENED_CURVE_ITERATOR0_COMPATIBLE || !not_last) {
*** f:\casper\HEAD\gs\src\gzpath.h Thu Dec 4 19:19:57 2003
--- files\gs\src\gzpath.h Mon Dec 8 03:38:39 2003
***************
*** 169,173 ****
int gx_subdivide_curve(gx_path *, int, curve_segment *, segment_notes);
#if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
! bool gx_check_nearly_collinear(fixed *x0, fixed *y0, fixed *x1, fixed *y1,
fixed *x2, fixed *y2);
#endif
--- 169,173 ----
int gx_subdivide_curve(gx_path *, int, curve_segment *, segment_notes);
#if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
! bool gx_check_nearly_collinear(fixed x0, fixed y0, fixed x1, fixed y1,
fixed x2, fixed y2);
#endif
***************
*** 411,420 ****
uint rx, ry, rdx, rdy, rd2x, rd2y, rd3x, rd3y; /* R */
segment_notes notes;
! #if CURVED_TRAPEZOID_FILL
#if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
bool reverse;
#endif
#endif
- /* public : */
fixed lx0, ly0, lx1, ly1;
};
--- 411,423 ----
uint rx, ry, rdx, rdy, rd2x, rd2y, rd3x, rd3y; /* R */
segment_notes notes;
! /* public : */
#if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
+ #if CURVED_TRAPEZOID_FILL_SCANS_BACK
+ fixed x, y;
+ bool curve;
+ #else
bool reverse;
#endif
#endif
fixed lx0, ly0, lx1, ly1;
};
***************
*** 423,428 ****
fixed x0, fixed y0, const curve_segment *pc, int k, bool reverse,
segment_notes notes);
bool gx_flattened_curve_iterator__init_line(gx_flattened_curve_iterator
*this,
! fixed x0, fixed y0, const line_segment *pc, segment_notes notes);
bool gx_flattened_curve_iterator__next(gx_flattened_curve_iterator *this);
bool curve_coeffs_ranged(fixed x0, fixed x1, fixed x2, fixed x3,
--- 426,435 ----
fixed x0, fixed y0, const curve_segment *pc, int k, bool reverse,
segment_notes notes);
bool gx_flattened_curve_iterator__init_line(gx_flattened_curve_iterator
*this,
! fixed x0, fixed y0, fixed x1, fixed y1, segment_notes notes);
bool gx_flattened_curve_iterator__next(gx_flattened_curve_iterator *this);
+ #if CURVED_TRAPEZOID_FILL_SCANS_BACK
+ bool gx_flattened_curve_iterator__prev(gx_flattened_curve_iterator *this);
+ bool gx_flattened_check_near(fixed x0, fixed y0, fixed x1, fixed y1);
+ #endif
bool curve_coeffs_ranged(fixed x0, fixed x1, fixed x2, fixed x3,