[Gs-code-review] Fix for SF bug "[ #228714 ] ShadingType 1 can mis-identify the function as constant" - improved

[Igor V. Melichev]

Raph,

> From: Raph Levien [raph at levien.com]
> Sent: 25 ????? 2001 ?. 01:09
> To: Igor V. Melichev
> Cc: code review
> Subject: Re: [Gs-code-review] Fix for SF bug "[ #228714 ] ShadingType 1
> can mis-identify the function as constant" - improved

First I need to say, that I have several bugs assigned to me now.
Therefore I cannot spend much time for this subject.

> 1. Analyze the function to find monotonic intervals, smooth intervals,
> and discontinuities. The shading could then, in principle, be reduced
> to a series of Gouraud triangle meshes (i.e. Type 4 shadings), each
> bounded on the outside by the outline of discontinuities.

I would prefer to convert it into quadrangle intervals of constant color.
For sampled functions this may be done analytically.
Also quadrangles match better to device interface
(rather it contains fill_triangle, for most devices it
actually reduces to fill_rectangle).

> 2. Evaluate the function for each pixel in device space, but "tune" the
> function evaluation logic to be fast.

This is only acceptable for PS calculator functions.
Do you have any ideas how to compute derivatives for
PS calculator ?

> One technique I've thought of for fast bulk function evaluation is to
> use a similar bytecode interpretation technique as now, but applied to
> vectors of multiple inputs at the same time.

At this moment I am unable to understand what do you mean saying
"bytecode interpretation" here. I did not read GS code about
computing function objects.

> I'm not sure which of these two techniques is better.

> 1. Reduce shading to Gouraud triangle mesh, using input color space.

You replace a simple thing with a complex one.
Type 1 has simple coordinate transform and complex color function.
It is simple to divide in device space, using contiguity intervals
and analytical derivatives. Cells has no self-intersections, twists, etc.

Coons and tensors have complex (curve) coordinate transformation and simple
(linear) user color function. It is easier to divide user color function
first.
Then we get smaller tensor meshes of constant color. Convert the constant
color
to device color, and fill mesh with regular 'fill'.

I believe that these 2 things are very differ3ent and should not mix
in one algorithm.

Triangle is degenerate Coons, right ?

> Under this regime, it is no longer
> possible to think of the abstract interface of a function as merely
> a mapping from input to output.

I would like to add contiguity/monotonity intervals to the
interface. Derivatives would be very useful also.

> > Actually about twice number of pixels. If we know monotonic intervals,
> > we could restrict it additionally with inverse of color gradient.
>
> I didn't quite understand this. Are you saying that the depth is
> bounded by the number of pixels, or the log of the number of pixels? In
> the latter case, recursion depth is not a concern.

My tree has all leafs on same level.
The number of leafs is determined by size of minimal regions
in device space. Now cut-off is hypot(dx,dy) < 0.7 .
This means that cut-off happens between 0.7 < hypot(dx,dy) < 0.35 .
The number of minimal regions N is between S/0.7^2 and S/0.35^2
where S is number of pixels covered by shading (ignoring clip !).
The depth of tree is about log2(N).

> Please commit the patch you proposed.

Done.

Igor.