Generailze the trapezoid fillling algorithm for curves, step 2.
"Igor V. Melichev" <[email protected]>
| Newsgroups | gmane.comp.printing.ghostscript.patches |
|---|---|
| Message-ID | <[email protected]> |
[Log message beg] Generalize the trapezoid fillling algorithm for curves, step 2. DETAILS : 1. Factored out the function gx_check_nearly_collinear_inline. This change is algorithmically equivalent. 2. Improved the FLATTENED_CURVE_ITERATOR0_COMPATIBLE build. This change modifies a disabled code only. EXPECTED DIFFERENCES : None. [Log message end] _______________________________________________ gs-code-review mailing list [email protected] http://www.ghostscript.com/mailman/listinfo/gs-code-review
patch.txt
(text/plain, 8.7 KB)
Changes:
*** f:\casper\HEAD\gs\src\gx.h Tue Nov 25 11:34:07 2003
--- files\gs\src\gx.h Wed Dec 3 12:42:53 2003
***************
*** 31,34 ****
--- 31,35 ----
#define TT_GRID_FITTING (NEW_TT_INTERPRETER && 0) /* old code = 0, new code = 1. */
#define FLATTENED_CURVE_ITERATOR 1 /* Old code = 0, new code = 1. */
+ #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. */
*** f:\casper\HEAD\gs\src\gxfill.c Tue Nov 25 11:34:07 2003
--- files\gs\src\gxfill.c Wed Dec 3 17:25:52 2003
***************
*** 275,280 ****
--- 275,283 ----
gx_path_bbox(ppath, &ibox);
# define SMALL_CHARACTER 500
+ # if !CURVED_TRAPEZOID_FILL
lst.bbox_left = fixed2int(ibox.p.x - adjust.x - fixed_epsilon);
lst.bbox_width = fixed2int(fixed_ceiling(ibox.q.x + adjust.x)) - lst.bbox_left;
+ # endif
+ /* We assume (adjust.x | adjust.y) == 0 iff it's a character. */
pseudo_rasterization = ((adjust.x | adjust.y) == 0 &&
# if TT_GRID_FITTING
***************
*** 429,433 ****
# ifdef FILL_TRAPEZOIDS
/* Not filling curves is also possible. */
! if (fill_by_trapezoids && !CURVED_TRAPEZOID_FILL)
# endif
#endif
--- 432,444 ----
# ifdef FILL_TRAPEZOIDS
/* Not filling curves is also possible. */
! if (fill_by_trapezoids &&
! (!CURVED_TRAPEZOID_FILL || adjust.x || adjust.y
! || (pis->ctm.xx != 0 && pis->ctm.xy != 0)
! || (pis->ctm.yx != 0 && pis->ctm.yy != 0)
! /* Curve monotonization can give a platform dependent result
! due to the floating point arithmetics used.
! For a while we allow it only for unrotated characters,
! which should have monotonic curves only. */
! ))
# endif
#endif
***************
*** 479,482 ****
--- 490,498 ----
return code;
pfpath = &ffpath;
+ # if CURVED_TRAPEZOID_FILL
+ /* The path monotonization may have a numeric error,
+ which enhances the bbox in 1 device unit. */
+ gx_path_bbox(pfpath, &ibox);
+ # endif
}
#endif
***************
*** 494,498 ****
else
fill_loop = fill_loop_by_scan_lines;
! /* We assume (adjust.x | adjust.y) == 0 iff it's a character. */
if (lst.bbox_width > MAX_LOCAL_SECTION && lst.pseudo_rasterization) {
/*
--- 510,517 ----
else
fill_loop = fill_loop_by_scan_lines;
! # if CURVED_TRAPEZOID_FILL
! lst.bbox_left = fixed2int(ibox.p.x - adjust.x - fixed_epsilon);
! lst.bbox_width = fixed2int(fixed_ceiling(ibox.q.x + adjust.x)) - lst.bbox_left;
! # endif
if (lst.bbox_width > MAX_LOCAL_SECTION && lst.pseudo_rasterization) {
/*
***************
*** 631,635 ****
--- 650,659 ----
ll->margin_set1.sect = ll->local_section1;
ll->pseudo_rasterization = false;
+ # if CURVED_TRAPEZOID_FILL
+ ll->bbox_left = 0; /* stub */
+ ll->bbox_width = 0; /* stub */
+ # else
/* Do not initialize ll->bbox_left, ll->bbox_width - they were set in advance. */
+ # endif
INCR(fill);
}
***************
*** 784,787 ****
--- 808,838 ----
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.) */
+ if (alp->direction == DIR_UP && alp->first_flattened) {
+ /* The old code isn't symmetric : it always yields the first point. */
+ } else {
+ /* Poorly optimized because it's just for a testing purpose. */
+ 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;
***************
*** 815,818 ****
--- 866,872 ----
}
alp->pseg = s1;
+ #if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
+ alp->first_flattened = true;
+ #endif
step_al(alp);
}
*** f:\casper\HEAD\gs\src\gxfill.h Tue Nov 25 11:34:07 2003
--- files\gs\src\gxfill.h Wed Dec 3 14:05:37 2003
***************
*** 82,85 ****
--- 82,88 ----
gx_flattened_curve_iterator fi;
bool more_flattened;
+ #if FLATTENED_CURVE_ITERATOR0_COMPATIBLE
+ bool first_flattened;
+ #endif
#endif
/*
*** f:\casper\HEAD\gs\src\gxpflat.c Tue Nov 25 03:21:59 2003
--- files\gs\src\gxpflat.c Wed Dec 3 12:17:22 2003
***************
*** 481,486 ****
#else /* !FLATTENED_CURVE_ITERATOR */
- #define FLATTENED_CURVE_ITERATOR0_COMPATIBLE 1
-
#undef x1
#undef y1
--- 481,484 ----
***************
*** 792,795 ****
--- 790,829 ----
}
+ /*
+ * Check for nearly collinear segments --
+ * those where one coordinate of all three points
+ * (the two endpoints and the midpoint) lie within the same
+ * half-pixel and both coordinates are monotonic.
+ */
+ private inline bool
+ gx_check_nearly_collinear_inline(fixed *x0, fixed *y0, fixed *x1, fixed *y1, fixed *x2, fixed *y2)
+ {
+ #if MERGE_COLLINEAR_SEGMENTS
+ # 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;
+ }
+ # undef coords_in_order
+ #endif
+ return false;
+ }
+
+ #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);
+ }
+ #endif
+
private int
gx_subdivide_curve_rec(gx_flattened_curve_iterator *this,
***************
*** 822,853 ****
for(;;) {
not_last = gx_flattened_curve_iterator__next(this);
! # if MERGE_COLLINEAR_SEGMENTS
! /*
! * Merge nearly collinear
! * segments -- those where one coordinate of all three points
! * (the two endpoints and the midpoint) lie within the same
! * half-pixel and both coordinates are monotonic.
! */
! # define coords_in_order(v0, v1, v2) ( (((v1) - (v0)) ^ ((v2) - (v1))) >= 0 )
! /* Check for collinear segments. */
! if (ppt > points + 1 && (!FLATTENED_CURVE_ITERATOR0_COMPATIBLE || not_last)) {
! if (coord_near(this->lx1, ppt[-1].x)) { /* X coordinates are within a half-pixel. */
! if (coord_near(this->lx1, ppt[-2].x) &&
! coords_in_order(ppt[-2].x, ppt[-1].x, this->lx1) &&
! coords_in_order(ppt[-2].y, ppt[-1].y, this->ly1)
! ) {
! --ppt; /* remove middle point */
! }
! } else if (coord_near(this->ly1, ppt[-1].y)) { /* Y coordinates are within a half-pixel. */
! /* Check for collinear segments. */
! if (coord_near(this->ly1, ppt[-2].y) &&
! coords_in_order(ppt[-2].x, ppt[-1].x, this->lx1) &&
! coords_in_order(ppt[-2].y, ppt[-1].y, this->ly1)
! )
--ppt; /* remove middle point */
- }
- }
- # undef coords_in_order
- # endif
if (!FLATTENED_CURVE_ITERATOR0_COMPATIBLE || !not_last) {
/* With FLATTENED_CURVE_ITERATOR0_COMPATIBLE it may store points[max_points]
--- 856,863 ----
for(;;) {
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) {
/* With FLATTENED_CURVE_ITERATOR0_COMPATIBLE it may store points[max_points]
*** f:\casper\HEAD\gs\src\gzpath.h Tue Nov 25 03:21:59 2003
--- files\gs\src\gzpath.h Wed Dec 3 12:06:13 2003
***************
*** 168,171 ****
--- 168,174 ----
/* Flatten a partial curve by sampling (internal procedure). */
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
/* Initialize a cursor for rasterizing a monotonic curve. */