gnuplot-beta

[RFC] Gradient fill options

[Ethan M. <merritt@u.washington.edu>]

I have requested that the next major release of libgd include a
gradient-fill routine.  The proposed mechanism is
   gdImageShadedTriangle(gdImagePtr image, gdPoint *vertex, int *color);
That is, a filled triangle with interpolation of three separate colors
specified for the three vertices.  Filled quadrangles are easily
produced by splitting each one into 2 triangles.

This would allow us to support gradient fill for the PNG/JPEG terminal.

My primary thought is to allow a PM3D shading mode that provides
smooth coloring.  

Are there other uses?  The colorbar?

Your thoughts and suggestions are welcome.


-- 
Ethan A Merritt					Courier Deliveries: 1959 NE Pacific	
Dept of Biochemistry    M/S 357742
Health Sciences Building
University of Washington - Seattle

Re: [RFC] Gradient fill options

[<HBB...@t-...>]

Ethan Merritt wrote:
>    gdImageShadedTriangle(gdImagePtr image, gdPoint *vertex, int *color);

> That is, a filled triangle with interpolation of three separate colors
> specified for the three vertices. 

Interpolation is quite a tricky business in color space, because there's 
no clear-cut idea what the curve to draw between two given points in 
colour space should be.  To properly specify an interpolation mechanism, 
one needs to specify at least the coordinate system in which the 
interpolated surface in color-space is supposed to be flat.

PM3D has such flexibility in principle, so if this new feature for libgd 
is to do us any good it should have it, too.

Re: [RFC] Gradient fill options

[Ethan M. <merritt@u.washington.edu>]

On Friday 02 February 2007 12:38, Hans-Bernhard Br=F6ker wrote:
> Ethan Merritt wrote:
> >    gdImageShadedTriangle(gdImagePtr image, gdPoint *vertex, int *color);
>=20
> > That is, a filled triangle with interpolation of three separate colors
> > specified for the three vertices.=20
>=20
> Interpolation is quite a tricky business in color space, because there's=
=20
> no clear-cut idea what the curve to draw between two given points in=20
> colour space should be.  To properly specify an interpolation mechanism,=
=20
> one needs to specify at least the coordinate system in which the=20
> interpolated surface in color-space is supposed to be flat.

That is an interesting point.

I noted out in my feature request for libgd that it was unclear what
sort of interpolation could be done with an indexed colormap. The usual
shading interpolation routines assume either RGB or CMY colorspace.
But I think you've answered that question.  The gnuplot PM3D grey
scale palette routines define a single scale within which interpolation
of the index value does make sense.  The question then becomes, is
this linear ordering of index values maintained internally in libgd?

We define colors 1->N sequentially using=20
     for(i=3D0;i<N;i++) png_smooth_color[i] =3D gdImageColorAllocate(...)
Does this yield N successive color indices in libgd? I don't know.
If so, interpolation using the color index stored for each
vertex should approximate the PM3D colors that would have been
assigned for each pixel.

Of course, for small changes across the face of the triangle
RGB interpolation is probably OK anyhow.  The results will only be=20
dramatically incorrect if the vertex values are so different that
they bracket a quite different color range on the PM3D color axis.
That can certainly happen, but it would mean that the grid
sampling is so course that important feature are likely to be
missed no matter what coloring scheme we use.

This is a general problem with interpolation schemes.
If the values assigned to the vertices are roughly the same,=20
but the "true" value in the middle of the face is different,
you won't get there by interpolation.

We should have plenty of time for testing, discussion, and
feedback. Gnuplot is headed for an imminent 4.2 release;
libgd for an imminant 2.0.34 release.  Any work on coordinating
treatment of gradient-fill can proceed at leisure with an eye
to much more distant major release targets (4.4/5.0 and 2.1).


=2D-=20
Ethan A Merritt					Courier Deliveries: 1959 NE Pacific=09
Dept of Biochemistry    M/S 357742
Health Sciences Building
University of Washington - Seattle

Re: [RFC] Gradient fill options

[<HBB...@t-...>]

Ethan Merritt wrote:

> I noted out in my feature request for libgd that it was unclear what
> sort of interpolation could be done with an indexed colormap. The usual
> shading interpolation routines assume either RGB or CMY colorspace.
> But I think you've answered that question.  The gnuplot PM3D grey
> scale palette routines define a single scale within which interpolation
> of the index value does make sense.  

... for pm3d it does.  But the same need not apply for GD at large.

PM3D doesn't interpolate colours, it interpolates indices, i.e. it 
interpolates along a polyline through colour space.  The idea being that 
all resulting colours should still be on that polyline.

To give an example, from an RGB palette defined like this:

0.0: blue
0.5: white
1.0: red

all colours interpolated by pm3d would currently be pure blue or red at 
various levels of saturation.  A triangle with these three values at its 
corners would have a pure white streak all along the edge from the white 
corner to the center of the opposite edge.

Actual colour interpolation would yield all kinds of violet with pure 
white only around the original white vertex.

Re: [RFC] Gradient fill options

[Pierre <pie...@gm...>]

Hi,

On 2/2/07, Hans-Bernhard Br=F6ker <HBB...@t-...> wrote:
> Ethan Merritt wrote:
>
> > I noted out in my feature request for libgd that it was unclear what
> > sort of interpolation could be done with an indexed colormap. The usual
> > shading interpolation routines assume either RGB or CMY colorspace.
> > But I think you've answered that question.  The gnuplot PM3D grey
> > scale palette routines define a single scale within which interpolation
> > of the index value does make sense.
>
> ... for pm3d it does.  But the same need not apply for GD at large.
>
> PM3D doesn't interpolate colours, it interpolates indices, i.e. it
> interpolates along a polyline through colour space.  The idea being that
> all resulting colours should still be on that polyline.
>
> To give an example, from an RGB palette defined like this:
>
> 0.0: blue
> 0.5: white
> 1.0: red
>
> all colours interpolated by pm3d would currently be pure blue or red at
> various levels of saturation.  A triangle with these three values at its
> corners would have a pure white streak all along the edge from the white
> corner to the center of the opposite edge.
>
> Actual colour interpolation would yield all kinds of violet with pure
> white only around the original white vertex.

I'm not sure to understand the notion of palette in your example.
Which and how many colors do you have in the palette when you start to
render a given triangle?

About GD in general, it supports indexed colors, it is what we define
as palette based image (created by gdImageCreate). The indexes are
sequentially incremented:

> for(i=3D0;i<N;i++) png_smooth_color[i] =3D gdImageColorAllocate(...)

it will create a color from the last existing index.

About what Dan said later (sorry, I subscribed only this morning)
> I assume you are interested only in linear interpolation and not higher o=
rder
> approaches like 2D splines.

I wrote a sample code including the new shaded triangle function in
Ethan's request:

http://bugs.libgd.org/?do=3Ddetails&task_id=3D39

It uses a linear interpolation. Only true color images are supported
now (no palette, "unlimited" colors). I did not test all cases but the
colors on the edges seem to match (see the attached images, a
quadrilateral rendered using two triangles).

> Does gdlib have indexed colormaps?

Yes, see above :)

> If not, a gradient triangle fill shouldn't
> be too difficult to implement.  If we know the resolution of the PNG/JPEG
> then it should be straightforward.

In GD (or any other bitmap based library), the rendering is resolution
independent. It is pixel based. The DPI is  meta information to help
other applications to know the size in inches but the image itself
remains the same.

I have a question about the usage of indexed colors, as I understand
the need of an indexed intensity palette (well known method for
VGA-like devices for example). Is there a reason to keep using them
instead of a true color image?

True color image are faster to render and the image can be saved as
indexed PNG (if size matters). It makes little sense to use indexed
colors if JPEG is the target. JPEG output are true color.

Feel free to post comment in the issues tracker, our mailing lists or
here (privately too but I prefer to keep the process as open as
possible). As Ethan said, we have plenty of time to define our
respective needs.

Thanks for your feedbacks,

--Pierre

Re: [RFC] Gradient fill options

[<HBB...@t-...>]

Pierre wrote:
> On 2/2/07, Hans-Bernhard Bröker <HBB...@t-...> wrote:
>> To give an example, from an RGB palette defined like this:
>>
>> 0.0: blue
>> 0.5: white
>> 1.0: red

> I'm not sure to understand the notion of palette in your example.

It's a (principally) continuous mapping from a numeric value (the number 
being displayed) to a colour.  In the case above, it consists of two 
linear paths, one from blue to white, the second from white to red.  The 
idea is to turn a data parameter into a colour, a.k.a. "false-colour 
diagram".  It's how altitude is often displayed on geographical maps 
(green lowlands, brown hills, white peaks, blue ocean).

> Which and how many colors do you have in the palette when you start to
> render a given triangle?

As many as the output terminal can supply --- potentially infinite. 
This "palette" is a data visualization thing, not the like-named 
property of paletted image file formats like GIF.  You may want to call 
our thing a "color map" or even a "false-color map" to distinguish the two.

Re: [RFC] Gradient fill options

[Pierre <pie...@gm...>]

On 2/3/07, Hans-Bernhard Br=F6ker <HBB...@t-...> wrote:
> Pierre wrote:
> > On 2/2/07, Hans-Bernhard Br=F6ker <HBB...@t-...> wrote:
> >> To give an example, from an RGB palette defined like this:
> >>
> >> 0.0: blue
> >> 0.5: white
> >> 1.0: red
>
> > I'm not sure to understand the notion of palette in your example.
>
> It's a (principally) continuous mapping from a numeric value (the number
> being displayed) to a colour.  In the case above, it consists of two
> linear paths, one from blue to white, the second from white to red.  The
> idea is to turn a data parameter into a colour, a.k.a. "false-colour
> diagram".  It's how altitude is often displayed on geographical maps
> (green lowlands, brown hills, white peaks, blue ocean).

Thanks for the explanation.

I think the shaded triangle in #39
(http://bugs.libgd.org/?do=3Ddetails&task_id=3D39) should work.

You can keep your mapping and pass the color value of each vertex.
Within a triangle the colors will be inside your range (linear
interpolation from c1 to c2 between two edges).

I put a meaningless example here: http://blog.thepimp.net/misc/gdshading/

The color stop points are in the comments, it is something like a
range -0.25..1.0 used "black blue red yellow".

The results has no special value (besides being a nice shading effect
;), but it may help to see how gdShadedTriangle works and what should
be done to match your needs.

--Pierre

Re: [RFC] Gradient fill options

[Daniel J S. <dan...@ie...>]

Pierre wrote:

> I put a meaningless example here: http://blog.thepimp.net/misc/gdshading/
> 
> The color stop points are in the comments, it is something like a
> range -0.25..1.0 used "black blue red yellow".
> 
> The results has no special value (besides being a nice shading effect
> ;),

psychedelic

> but it may help to see how gdShadedTriangle works and what should
> be done to match your needs.

I've looked through the code a bit and your examples.  (What command does one need to compile this program?)  I'd have to think about your approach to be certain about the result.  You've broken the thing down into a series of one dimensional linearities, first along the sides of the triangle to get a color, and then across the x dimension to further interpolate between those two.  Seems logical, but it may be open for rounding problems.

Another thing that makes me wonder a bit (and this may be a visual effect), is that I look at your gouraud3.png example:

http://bugs.libgd.org/?getfile=25

and imagine looking at just one of the triangles, with blue in one corner, red in another, green in the third.  Somehow it appears that they aren't blending together the way I would think.  Would it be possible to generate a fairly big equilateral triangle, say,

	x0 = 10; y0 = 10;
	x1 = 310; y1 = 10;
	x2 = 160; y2 = 270;

so that we'd expect a nice symmetrical blending of the components?

I'll offer up an alternative construction, not that I'm suggesting a change, but just for the sake of brainstorming.  If one thinks in terms of a single color component, it can be imagined as a two dimensional plane in three dimensional space (x and y are two dimensions, c the color a third dimension).  Generalizing the z = m x + b idea for a line, we have three points for which we want a plane to pass through.  Let w be a two dimensional vector, b a constant.  Color is then

c = w' * [x y]' + b

i.e., if we know w and b, we can find any color value on that plane from the above formula.  Given triplets (x_1, y_1, c_1), (x_2, y_2, c_2), (x_3, y_3, c_3), define matrix:

A =

| x_1  y_1  1 |  
| x_2  y_2  1 |  
| x_3  y_3  1 |  

and vector c = [c_1 c_2 c_3]' and vector d = [w b]'.  Then

A d = c

and solving for d gives

d = inv(A) c

I wrote a 3D inverse routine the other day.  Ultimately, this approach wouldn't mean much less code because of the inversion, but its advantage might be a little more precision, not sure.

Anyway, I'd be interested in the equilateral "color triangle".

Dan

Re: [RFC] Gradient fill options

[<HBB...@t-...>]

Daniel J Sebald wrote:
> I've looked through the code a bit and your examples.  (What command 
> does one need to compile this program?)  I'd have to think about your 
> approach to be certain about the result.  You've broken the thing down 
> into a series of one dimensional linearities, first along the sides of 
> the triangle to get a color, and then across the x dimension to further 
> interpolate between those two.  Seems logical, but it may be open for 
> rounding problems.

And, more importantly, it's a bit biased, which tends to turn into a 
robustness problem.  The bias lies in the arbitrary choice of one vertex 
to be shared by the two first interpolations.

It can be better to go via barycentric coordinates.  It's effectively a 
method to find three numbers s, t, and u such that:

	s+t+u=1
	s*A + t*B + u*C = X  for the point, and its colour.

I.e. you solve the equation for s,t,u given a point X, then substitute 
them into the equation to find the target colour.

Re: [RFC] Gradient fill options

[Daniel J S. <dan...@ie...>]

Ethan Merritt wrote:
> On Friday 02 February 2007 12:38, Hans-Bernhard Bröker wrote:
> 
>>Ethan Merritt wrote:
>>
>>>   gdImageShadedTriangle(gdImagePtr image, gdPoint *vertex, int *color);
>>
>>>That is, a filled triangle with interpolation of three separate colors
>>>specified for the three vertices. 
>>
>>Interpolation is quite a tricky business in color space, because there's 
>>no clear-cut idea what the curve to draw between two given points in 
>>colour space should be.  To properly specify an interpolation mechanism, 
>>one needs to specify at least the coordinate system in which the 
>>interpolated surface in color-space is supposed to be flat.
> 
> 
> That is an interesting point.
> 
> I noted out in my feature request for libgd that it was unclear what
> sort of interpolation could be done with an indexed colormap. The usual
> shading interpolation routines assume either RGB or CMY colorspace.
> But I think you've answered that question.  The gnuplot PM3D grey
> scale palette routines define a single scale within which interpolation
> of the index value does make sense.  The question then becomes, is
> this linear ordering of index values maintained internally in libgd?

I assume you are interested only in linear interpolation and not higher order approaches like 2D splines.  Does gdlib have indexed colormaps?  If not, a gradient triangle fill shouldn't be too difficult to implement.  If we know the resolution of the PNG/JPEG then it should be straightforward.

For this hidden surface thing I was messing around with I wrote some short routines to construct a 2D hyperplane in three dimensions given three points, then simply do a matrix multiply for all the points within the triangle, that gives the interpolated value.  Then take that value and lookup the value in the indexed colormap.  Then place that value in the PNG/JPEG image with some type of gdImage() routine (I assume).

Dan

Re: [RFC] Gradient fill options

[Pierre <pie...@gm...>]

On 2/2/07, Ethan Merritt <merritt@u.washington.edu> wrote:
> On Friday 02 February 2007 12:38, Hans-Bernhard Br=F6ker wrote:
> > Ethan Merritt wrote:
> > >    gdImageShadedTriangle(gdImagePtr image, gdPoint *vertex, int *colo=
r);
> >
> > > That is, a filled triangle with interpolation of three separate color=
s
> > > specified for the three vertices.
> >
> > Interpolation is quite a tricky business in color space, because there'=
s
> > no clear-cut idea what the curve to draw between two given points in
> > colour space should be.  To properly specify an interpolation mechanism=
,
> > one needs to specify at least the coordinate system in which the
> > interpolated surface in color-space is supposed to be flat.
>
> That is an interesting point.
>
> I noted out in my feature request for libgd that it was unclear what
> sort of interpolation could be done with an indexed colormap. The usual
> shading interpolation routines assume either RGB or CMY colorspace.
> But I think you've answered that question.  The gnuplot PM3D grey
> scale palette routines define a single scale within which interpolation
> of the index value does make sense.  The question then becomes, is
> this linear ordering of index values maintained internally in libgd?
>
> We define colors 1->N sequentially using
>      for(i=3D0;i<N;i++) png_smooth_color[i] =3D gdImageColorAllocate(...)
> Does this yield N successive color indices in libgd? I don't know.

It does.

> We should have plenty of time for testing, discussion, and
> feedback. Gnuplot is headed for an imminent 4.2 release;
> libgd for an imminant 2.0.34 release.  Any work on coordinating
> treatment of gradient-fill can proceed at leisure with an eye
> to much more distant major release targets (4.4/5.0 and 2.1).

I added a sample code in your report. It is a first shot but seems to work =
well.

--Pierre

Re: [RFC] Gradient fill options

[Pierre <pie...@gm...>]

On 2/4/07, Daniel J Sebald <dan...@ie...> wrote:
> Pierre wrote:
>
> > I put a meaningless example here: http://blog.thepimp.net/misc/gdshading/
> >
> > The color stop points are in the comments, it is something like a
> > range -0.25..1.0 used "black blue red yellow".
> >
> > The results has no special value (besides being a nice shading effect
> > ;),
>
> psychedelic
>
> > but it may help to see how gdShadedTriangle works and what should
> > be done to match your needs.
>
> I've looked through the code a bit and your examples.  (What command does one need to compile this program?)

gcc colormap.c -o colormap -I/path/to/usr/include -L/path/to/usr/lib -lgd

or if you use 2.0.34RC2 or  CVS version of libgd you can simply add
something like (CMake must installed, see README.TESTING):

add_executable(colormap "colormap.c")
target_link_libraries(colormap  ${GD_LIB})

at the end of the CMakeLists.txt.

> I'd have to think about your approach to be certain about the result.  You've broken the thing down into a series of one dimensional linearities, first along the sides of the triangle to get a color, and then across the x dimension to further interpolate between those two.  Seems logical, but it may be open for rounding problems.

yes, it is a linear interpolation between the two edges of each scan
line. I use the following doc to implement it:

http://tfpsly.free.fr/Docs/3dIca/3dica3.htm

> Another thing that makes me wonder a bit (and this may be a visual effect), is that I look at your gouraud3.png example:
>
> http://bugs.libgd.org/?getfile=25
>
> and imagine looking at just one of the triangles, with blue in one corner, red in another, green in the third.  Somehow it appears that they aren't blending together the way I would think.  Would it be possible to generate a fairly big equilateral triangle, say,
>
>         x0 = 10; y0 = 10;
>         x1 = 310; y1 = 10;
>         x2 = 160; y2 = 270;
>
> so that we'd expect a nice symmetrical blending of the components?

Yes, there is maybe a rounding problem as the precision is limited by
the fixed point arithmetic), but it is relatively easy to solve by
increasing the precision. I like fixed point arithmetic because it is
fast (in embedded systems too).

> I'll offer up an alternative construction, not that I'm suggesting a change,

There is absolutely no problem to suggest changes. My current
implementation is only a proposal as I used it for some basic 3D
rendering and I was happy with the quality and speed.

> but just for the sake of brainstorming.  If one thinks in terms of a single color component, it can be imagined as a two dimensional plane in three dimensional space (x and y are two dimensions, c the color a third dimension).  Generalizing the z = m x + b idea for a line, we have three points for which we want a plane to pass through.  Let w be a two dimensional vector, b a constant.  Color is then
>
> c = w' * [x y]' + b
>
> i.e., if we know w and b, we can find any color value on that plane from the above formula.  Given triplets (x_1, y_1, c_1), (x_2, y_2, c_2), (x_3, y_3, c_3), define matrix:
>
> A =
>
> | x_1  y_1  1 |
> | x_2  y_2  1 |
> | x_3  y_3  1 |
>
> and vector c = [c_1 c_2 c_3]' and vector d = [w b]'.  Then
>
> A d = c
>
> and solving for d gives
>
> d = inv(A) c
>
> I wrote a 3D inverse routine the other day.  Ultimately, this approach wouldn't mean much less code because of the inversion, but its advantage might be a little more precision, not sure.

I'm not sure either. However this solution is elegant, if you have an
implementation already (even without the gd part), I can try to
provide it as a separate patch/example. It will help to run tests
against a serie of cases.

> Anyway, I'd be interested in the equilateral "color triangle".

Please find it here (Example 2): http://blog.thepimp.net/misc/gdshading/

--Pierre

Re: [RFC] Gradient fill options

[Daniel J S. <dan...@ie...>]

Pierre wrote:

>> Anyway, I'd be interested in the equilateral "color triangle".
> 
> 
> Please find it here (Example 2): http://blog.thepimp.net/misc/gdshading/

That looks good.  All portions have a blended, semicircular appearance.  The previous examples choice of points resulted in something slightly different.

Yes, fixed-point is good so long as resolution is kept high.  Stay with that approach.

Dan

Re: [RFC] Gradient fill options

[Daniel J S. <dan...@ie...>]

Hans-Bernhard Bröker wrote:
> Daniel J Sebald wrote:
> 
>>I've looked through the code a bit and your examples.  (What command 
>>does one need to compile this program?)  I'd have to think about your 
>>approach to be certain about the result.  You've broken the thing down 
>>into a series of one dimensional linearities, first along the sides of 
>>the triangle to get a color, and then across the x dimension to further 
>>interpolate between those two.  Seems logical, but it may be open for 
>>rounding problems.
> 
> 
> And, more importantly, it's a bit biased, which tends to turn into a 
> robustness problem.  The bias lies in the arbitrary choice of one vertex 
> to be shared by the two first interpolations.
> 
> It can be better to go via barycentric coordinates.  It's effectively a 
> method to find three numbers s, t, and u such that:
> 
> 	s+t+u=1
> 	s*A + t*B + u*C = X  for the point, and its colour.
> 
> I.e. you solve the equation for s,t,u given a point X, then substitute 
> them into the equation to find the target colour.

Interesting.  This results in matrix equations similar to what I sent previously:

s * x_1 + t * x_2 + u * x_3 = x
s * y_1 + t * y_2 + u * x_3 = y
s * 1   + t * 1   + u * 1   = 1

or

| x_1 x_2 x_3 |
| y_1 y_2 y_3 |
| 1   1   1   |

(call it Z) product with

[s t u]'

equals

[x y 1]'

so

[s t u]' = inv(Z) [x y 1]'

Since I doubt you'd want to compute the intermediate values s t u for each pixel inside the triangle

c = [c_1 c_2 c_3] * [s t u]'

 = [c_1 c_2 c_3] * inv(Z) * [x y 1]'

 = [w_1 w_2 b] * [x y 1]'

 = w' * [x y]' + b

Dan

Re: [RFC] Gradient fill options

[Pierre <pie...@gm...>]

Hi,

The code has added in the new playground module in libgd CVS:

http://cvs.php.net/viewvc.cgi/gd/playground/gdimageshadedtriangle/

This version contains the last patch from Daniel.

By the way, if you like to have CVS access, please let me know. I
think it may improve the testing process.

On 2/7/07, Daniel J Sebald <dan...@ie...> wrote:
> Hans-Bernhard Br=F6ker wrote:
> > Daniel J Sebald wrote:
> >
> >>I've looked through the code a bit and your examples.  (What command
> >>does one need to compile this program?)  I'd have to think about your
> >>approach to be certain about the result.  You've broken the thing down
> >>into a series of one dimensional linearities, first along the sides of
> >>the triangle to get a color, and then across the x dimension to further
> >>interpolate between those two.  Seems logical, but it may be open for
> >>rounding problems.
> >
> >
> > And, more importantly, it's a bit biased, which tends to turn into a
> > robustness problem.  The bias lies in the arbitrary choice of one verte=
x
> > to be shared by the two first interpolations.
> >
> > It can be better to go via barycentric coordinates.  It's effectively a
> > method to find three numbers s, t, and u such that:
> >
> >       s+t+u=3D1
> >       s*A + t*B + u*C =3D X  for the point, and its colour.
> >
> > I.e. you solve the equation for s,t,u given a point X, then substitute
> > them into the equation to find the target colour.
>
> Interesting.  This results in matrix equations similar to what I sent pre=
viously:

I'm not sure to understand why it is biased. Each vertex color is
known. The first vertex is the top left one, after they have been
sorted.

Or is it something you will do outside the function to define the
color at each vertex?

Is it about having a higher precision for the interpolation (instead
of the linear interpolation)?

Maybe an example result may help to see the differences and their
impacts in a real case. Maybe using an existing surface (one in your
test cases), we can then compare all results.

Pardon me if my questions are too obvious but I never looked so deeply
the rounding/precision problems. it is really a good thing as it
minimizes the risk of errors (no bad surprise after the releases).

--Pierre

Re: [RFC] Gradient fill options

[<HBB...@t-...>]

Pierre wrote:
>> > And, more importantly, it's a bit biased, which tends to turn into a
>> > robustness problem.  The bias lies in the arbitrary choice of one 
>> > vertex to be shared by the two first interpolations.

> I'm not sure to understand why it is biased. Each vertex color is
> known. The first vertex is the top left one, after they have been
> sorted.

The bias lies in picking the top left vertex as "the first".  Why should 
this be treated different from the other two?  It doesn't necessarily 
have to cause visible rounding/precision effects, but it can.

This can cause nasty effects like: the same triangle comes out subtly 
different if the scene is rendered upside down or rotated by 90 degress, 
even though the result should be exactly the same.    Other cases of the 
same issue can cause edges to be drawn differently if you switch the 
order of their vertices in the drawline() function call.

Re: [RFC] Gradient fill options

[Ethan M. <merritt@u.washington.edu>]

On Wednesday 07 February 2007 11:44, Hans-Bernhard Br=F6ker wrote:
> Pierre wrote:
>=20
> > I'm not sure to understand why it is biased. Each vertex color is
> > known. The first vertex is the top left one, after they have been
> > sorted.
>=20
> The bias lies in picking the top left vertex as "the first".=20
> This can cause nasty effects like: the same triangle comes out subtly=20
> different if the scene is rendered upside down or rotated by 90 degress,=
=20
> even though the result should be exactly the same.   =20

That is true, but the failure mode is usually harmless. If you rotate the
triangle in 3D its coloring may change very slightly, but if it is a
single facet of a larger surface this will probably not be noticed since
the adjacent triangles are similarly affected.

> the same issue can cause edges to be drawn differently if you switch the=
=20
> order of their vertices in the drawline() function call.

This is the more important issue, as I tried to point out before.
In rendering a tesselated surface, it is common that the same edge
will be traversed in different directions in the course of rendering
the two facets that it separates.  In order to assure smooth coloring
across the break, it is crucial that the direction of traversal not
affect the color assignment.


=2D-=20
Ethan A Merritt

Re: [RFC] Gradient fill options

[Pierre <pie...@gm...>]

On 2/7/07, Ethan Merritt <merritt@u.washington.edu> wrote:
> On Wednesday 07 February 2007 11:44, Hans-Bernhard Br=F6ker wrote:
> > Pierre wrote:
> >
> > > I'm not sure to understand why it is biased. Each vertex color is
> > > known. The first vertex is the top left one, after they have been
> > > sorted.
> >
> > The bias lies in picking the top left vertex as "the first".
> > This can cause nasty effects like: the same triangle comes out subtly
> > different if the scene is rendered upside down or rotated by 90 degress=
,
> > even though the result should be exactly the same.
>
> That is true, but the failure mode is usually harmless. If you rotate the
> triangle in 3D its coloring may change very slightly, but if it is a
> single facet of a larger surface this will probably not be noticed since
> the adjacent triangles are similarly affected.

I will add a custom version to test these cases using numerical
results (output the edges values to a file and compare them). We can
then see if the error is acceptable. As you say, I do not expect any
noticeable differences.

> > the same issue can cause edges to be drawn differently if you switch th=
e
> > order of their vertices in the drawline() function call.
>
> This is the more important issue, as I tried to point out before.
> In rendering a tesselated surface, it is common that the same edge
> will be traversed in different directions in the course of rendering
> the two facets that it separates.  In order to assure smooth coloring
> across the break, it is crucial that the direction of traversal not
> affect the color assignment.

The "psychedelic example shows a case where the same edge is shared
between different triangles. I did not see any artifacts.

It was expected as the slopes and delta are not affected by the
position of the vertex, it is alway V(n) - V(n-1), where n is the
first or not should not change the constant slopes and delta. If yes,
we will see it with the numerical tests (hopefully :).

--Pierre

Re: [RFC] Gradient fill options

[Pierre <pie...@gm...>]

On 2/7/07, Pierre <pie...@gm...> wrote:
> On 2/7/07, Ethan Merritt <merritt@u.washington.edu> wrote:
> > On Wednesday 07 February 2007 11:44, Hans-Bernhard Br=F6ker wrote:
> > > Pierre wrote:
> > >
> > > > I'm not sure to understand why it is biased. Each vertex color is
> > > > known. The first vertex is the top left one, after they have been
> > > > sorted.
> > >
> > > The bias lies in picking the top left vertex as "the first".
> > > This can cause nasty effects like: the same triangle comes out subtly
> > > different if the scene is rendered upside down or rotated by 90 degre=
ss,
> > > even though the result should be exactly the same.
> >
> > That is true, but the failure mode is usually harmless. If you rotate t=
he
> > triangle in 3D its coloring may change very slightly, but if it is a
> > single facet of a larger surface this will probably not be noticed sinc=
e
> > the adjacent triangles are similarly affected.
>
> I will add a custom version to test these cases using numerical
> results (output the edges values to a file and compare them). We can
> then see if the error is acceptable. As you say, I do not expect any
> noticeable differences.

By the way, any help is welcome. If someone volunteers to write these
tests, he will be more than welcome :)

--Pierre