[Gs-code-review] Bug #474544

[Dan Coby]

Igor,

>hyperrectangle.

I have never seen this word actually used.  We have already discussed
the hypercube issue and I see no reason to spend more time.


>You said they are "reasonable". I'm unable to guess, what assumptions
>did you use for the reasoning. In general, I think that a choice
>of the size without analyzing the function never gives a good result.
>For solving this problem I'd compute function values
>in some internal points and build an approximation -
>either a linear or 3d order spline.

I assume that you have not read the Adobe specification for a type 0
function.  It allows for both linear and 3rd order interpolation.  In
the color cube logic we are using the 3rd order.  Thus we are already
doing what you suggest.

There are several optimizations that are possible in the color cube
logic.  In an ideal world, in which we did not need to worry about
execution time or memory requirements, we would sample each dimension
with a very high resolution and simply use the results.  In the real
world it is impractical to sample a 10 dimensional function with 256
points per edge.  This would require 2**80 samples.  Thus it is not
always practical to collect as much data as is desired.  Please remember
that it is possible for there to be hundreds or thousands of colorspace
specifications within an image file.  The alternate tint transform
functions can be very large and very slow to execute.  We cannot simply
do whatever we want without consideration of time and space constraints.
The function determine_sampled_data_size simply represents my opinion of
what is a practical amount of data to collect.

The current color cube logic makes no effort to reduce the number of
sample points that are actually stored after they are sampled.  This
is not needed in the current requirement as a color cube interpolation
function.  This feature would be desired if the buildsampledfunction
framework is used to create a function which is stored in a PDF file
and minimum file size is desired.

The buildsampledfunction framework that I built can be improved in a
number of ways.  What I have created is a very reasonable and useful
starting point.  If someone wants to add an algorithm for dynamically
determining if the function (actually functions, since there can be
several outputs) is linear, or quadratic, or cubic in a certain
dimension, then they are welcome to do so.  This person needs to
remember that you cannot determine that a function is linear by simply
sampling three points.


Dan


-----Original Message-----
From: Igor V. Melichev [mailto:igor at artifex.com]
Sent: Wednesday, February 06, 2002 6:44 AM
To: Dan Coby; Gs-Code-Review
Subject: RE: [Gs-code-review] Bug #474544


Dan,

> From: Dan Coby [dan at artifex.com]
> Sent: 4 ??????  2002 ?. 09:11
> To: Igor V. Melichev; Gs-Code-Review
> Subject: RE: [Gs-code-review] Bug #474544


> >zfsample.c :
> >
> >1. valid_cube_size : I believe that 'cube' is an object that has same
size
> >in all dimentions. An argument of the function is an array of sizes.
> >Therefore the function hane doesn't correspond to the body.
> >
> >Possibly you coded a generalized function for further extensions.
> >Then please comment this, and rename 'cube' to something.
> >But if you assume a cube, the argument should be a single integer.
>
> Unfortunately I do not know of a better choice of words for this case.

hyperrectangle.

> The term hypercube is used even if the dimensions are not equal in
> size.  Probably because the other choices are even more awkward.

>From www.webster.com :

[beg quote]
Click on the Collegiate Thesaurus tab to look up the current word in the
thesaurus.

One entry found for hypercube.


Main Entry: hy·per·cube
Pronunciation: 'hI-p&r-"kyub
Function: noun
Date: 1909
1 : a geometric figure (as a tesseract) in Euclidean space of n dimensions
that is analogous to a cube in three dimensions
2 : a computer architecture in which each processor is connected to n others
based on analogy to a hypercube of n dimensions
[end quote]

[beg quote]
Main Entry: 1cube
Pronunciation: 'kyub
Function: noun
Etymology: Latin cubus, from Greek kybos die, cube
Date: 1551
1 a : the regular solid of six equal square sides -- see VOLUME table b :
something shaped like a cube <ice cube>
2 : the product got by taking a number three times as a factor
[end quote]

An usage of jargon would be fine if properly commented.


> >2. determine_sampled_data_size :
> >
> >I believe that it computes the integer part of Nth power root of
> >MAX_DATA_SIZE / sample_size / num_outputs.
> >Either it is not a cube at all, or it may be coded straight-forward,
> >inverting power(m,n) with iteration by size.
> >Also see (1) about 'Size' argumrnt.
> >As I noticed before, the iteration is easier to code and to understand
> >with 'for' loop.
>
> This is not what this function does.  A very simple test case makes
> this very obvious.  For num_inputs = num_ouputs = 1, sample_size = 16
> bits, this function returns a value of 512 in the Size array.  Your
> calculation would be 32,768.  You are off by a factor of 64.

Oops, really it computes a minimum of 2 things :
1. The integer part of Nth power root of MAX_DATA_SIZE / sample_size /
num_outputs
2. A constant taken from size_list.

> Perhaps you are getting confused because you keep trying to force the
> use of a "for" loop in this function.

No, the choice of 'for' or 'while' is irrelevant.
I did see that it's not a cube (see above), and
tried to interpret it in algebra.

Thinking more about it, I can't guess, where size_list values are taken
from.
You said they are "reasonable". I'm unable to guess, what assumptions
did you use for the reasoning. In general, I think that a choice
of the size without analyzing the function never gives a good result.
For solving this problem I'd compute function values
in some internal points and build an approximation -
either a linear or 3d order spline. Note that at once
we got a bug report about a similar problem - see
SF bug "[ #228714 ] ShadingType 1 can mis-identify the function as
constant",
http://www.ghostscript.com/pipermail/gs-code-review/2001-March/000372.html
and spent big efforts to fix it.

With high probability your implementation of determine_sampled_data_size
will re-open the bug #228714. For example, consider a 4-input function,
which is linear in 3 dimentions and needs 256 nodes in 4th dimension
- it requires 2x2x2x256 rectangle.

> >4. space char / tab char problems in lines 186-196, 464-478,
> >and possibly in other places.
>
> I do not see any visible problems.

I do see them before and after your last commit.

Igor.