[gs-devel] Re: A generalization of dev_proc(dev, fill_trapezoid)

Igor V. Melichev igor.melichev at artifex.com
Tue Feb 10 01:03:55 PST 2004


Ray,

Thank you for your answer.
I'll go ahead with the clean method.

Our implementation of gx_default_fill_trapezoid is clean.
The problem with banding happens due to a poor code in
fill_loop_by_trapezoids* (which now is generated from
the gxfilltr.h template).

Igor.

----- Original Message ----- 
From: "Ray Johnston" <ray.johnston at artifex.com>
To: "Igor V. Melichev" <igor.melichev at artifex.com>
Cc: <gs-devel at ghostscript.com>; "tech" <tech at artifex.com>; "Stefan Kemper"
<stefan.kemper at artifex.com>; "Henry Stiles" <henry.stiles at artifex.com>;
"Raph Levien" <raph.levien at artifex.com>
Sent: Monday, February 09, 2004 10:22 PM
Subject: [gs-devel] Re: A generalization of dev_proc(dev, fill_trapezoid)


> Igor,
>
> I agree that line quantization phase should *NOT* depend on the
> top and bottom of the clip. I'm surprised that such a fundamental
> flaw is in the trapezoid code. This does explain much of the
> reason that banded and non-banded rendering differs.
>
> To fix this correctly, I agree that the right and left edges
> need to be the "real" edge lines, so that right->start.y may
> be different to left->start.y, and similarly for the end points.
>
> A correct trapezoid algorithm shoule generate the same phase of
> steps along the edges, no matter what [ytop::ybot] range is
> specified.
>
> I am not aware of any customers or users that have implemented
> their own trapezoid filling, and I think we are safe 'clarifying'
> what a correct fill_trapezoid routine should do and clarifying
> that the edges may be lines that have differing start and end
> y coordinates.
>
> Thus my recommendation is to go ahead and correct the gx_default_
> fill_trapezoid function, and alter the code as desired to pass
> the actual edge lines so that phase can be handled correctly.
>
> Regards,
> Ray
> ______________________________________________________________________
>
> Igor V. Melichev wrote:
> > Developers,
> >
> > Our algorithm GX_FILL_TRAPEZOID (for filling a single trapezoid) has
some
> > important features, which I want to use in further versions
> > for a dramatic speeding up the shadings.
> > These features are not obvious and unfortunately they were not
> > explicitly documented (rather one could guess them).
> > To simplify the further development and to avoid possible confusions,
> > I'd like to discuss the related problems now.
> >
> > The features are :
> >
> > 1. The line quantization phase doesn't depend on
> >    the clipping specified with ybot, ytop.
> >
> > In other words, if two calls differ only with the clip interval [ybot,
> > ytop],
> > the parts of rasters generated within the intersection of the intervals
> > must be identical.
> >
> > More detailedly, if a trapezoid side is sloped,
> > the sloped boundary in the raster looks as stairs,
> > which have a period depending of the slope
> > (well, we don't consider irrational tangents due to machine precision).
> > The feature is the phase of stairs don't depend on ybot, ytop
> > (rather it does depend on left_.start.y, right->start.y).
> >
> > 2. right->start.y is not necessary equal to left->start.y, as well as
> >    right->end.y is not necessary equal to left->end.y .
> >
> > Before now one could assume that they must be equal because
> > all calls to GX_FILL_TRAPEZOID from the GS code do so.
> > We don't want to follow it in future.
> >
> > [The end of features.]
> >
> > One hard decision must be taken about assumptions done for
> > dev_proc(dev, fill_trapezoid) :
> >
> >
> >     We would like to require ALL IMPLEMENTATIONS to provide
> >     the features explained above.
> >
> >
> > Meanwhile I guess that the old code does not assume (2)
> > for some 3d party implementations. I think so because
> > gx_default_fill_triangle performs a division of a side of a triangle
> > rather than a simple clipping with ybot, ytop .
> > Actually I can't know whether this was done intentionally
> > or just due to an insufficient understanding of capabilities
> > of the current prototype of dev_proc(dev, fill_trapezoid),
> > or it's just a rudiment from an old prototype
> > before the repository was created.
> >
> > So now I want to get responses from users,
> > who implement dev_proc(dev, fill_trapezoid)
> > by own means in software or hardware level :
> >
> > 1. Do those algorithms provide the features (1) and (2) ?
> >    Exactly do you know a GS application,
> >    which defines a native fill_trapezoid algorithm,
> >    and which does not provide the features ?
> >
> > 2. Can those applications to be improved with
> >    providing the features (1) and (2)
> >    (For example, with replacing their native implementation with one
> >    supplied with Ghostscript) ?
> >    (I realize that the improvement is a new trouble,
> >    but the fast shadings worth it.)
> >
> > Thank you.
> >
> > Igor.
> >
> >
> >
> >
> >
> >
> >
>
> -- 
> Ray Johnston
> Director of Engineering                          Tel: (714) 484-0376
> Artifex Software Inc.                            Fax: (714) 220-1022
> ______________________________________________________________________
>
> _______________________________________________
> gs-devel mailing list
> gs-devel at ghostscript.com
> http://www.ghostscript.com/mailman/listinfo/gs-devel
>




More information about the gs-devel mailing list