RE: [ft-devel] a satisfactory fix for the cubic spline bug

2010-08-31 Thread David Bevan

Rather than piecemeal reinventing of the wheel, I would have thought that FT 
should implement a mathematically rigorous flattener. The following might be a 
good place to start:

http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-ready%20CISST02%202.pdf

Or:

http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/bezier%20cccg04%20paper.pdf

Naively, I had assumed that this sort of issue would have been resolved 
properly back in the pre-history of FT, since it is obviously of critical 
importance for correct output.

Since it apparently hasn't been, we can make use of the latest research.

David %^


 -Original Message-
 From: freetype-devel-bounces+david.bevan=pb@nongnu.org
 [mailto:freetype-devel-bounces+david.bevan=pb@nongnu.org] On Behalf Of
 Graham Asher
 Sent: 30 August 2010 10:59
 To: freetype-devel
 Subject: [ft-devel] a satisfactory fix for the cubic spline bug
 
 I thought about this overnight and realised that we can slightly modify
 the existing heuristic to get a much simpler fix. Instead of trying to
 find points on the curve or trying to measure the distance from a point
 to a straight line, we adapt the earlier idea, used in existing FreeType
 code, of finding the maximum coordinate difference (that is, whichever
 is greater of dx and dy):
 
 * existing method: use max coordinate difference between middle of
 spline, found by bisection, and middle of straight line
 
 * new method: use max coordinate difference between either of the two
 control points and the middle of the straight line
 
 This yields the following code (start of gray_render_cubic), which
 works, fixes the bug, and is probably faster, because it is certainly
 simpler. I don't think I'll go any further than this.
 
   static int
   gray_render_cubic( RAS_ARG_ FT_Vector*  control1,
   FT_Vector*  control2,
   FT_Vector*  to )
   {
 int top, level;
 int*levels;
 FT_Vector*  arc;
 int error = 0;
 
 /*
 Find the furthest distance of a coordinate of a control point from the
 midpoint of the line.
 */
 int dx1, dy1, dx2, dy2;
 int midx = (DOWNSCALE(ras.x) + to-x) / 2;
 int midy = (DOWNSCALE(ras.y) + to-y) / 2;
 dx1 = control1-x - midx; if (dx1  0) dx1 = -dx1;
 dy1 = control1-y - midy; if (dy1  0) dy1 = -dy1;
 dx2 = control2-x - midx; if (dx2  0) dx2 = -dx2;
 dy2 = control2-y - midy; if (dy2  0) dy2 = -dy2;
 if (dx1  dy1)
 dx1 = dy1;
 if (dx1  dx2)
 dx1 = dx2;
 if (dx1  dy2)
 dx1 = dy2;
 
 if (dx1 = ras.cubic_level)
 return gray_render_line( RAS_VAR_ to-x, to-y );
 
 level = 1;
 dx1 /= ras.cubic_level;
 while ( dx1  0 )
 {
   dx1 = 2;
   level++;
 }
 
 
 Graham
 
 
 ___
 Freetype-devel mailing list
 Freetype-devel@nongnu.org
 http://lists.nongnu.org/mailman/listinfo/freetype-devel


___
Freetype-devel mailing list
Freetype-devel@nongnu.org
http://lists.nongnu.org/mailman/listinfo/freetype-devel


Re: [ft-devel] a satisfactory fix for the cubic spline bug

2010-08-31 Thread GRAHAM ASHER
David,

Thank you very much for the citations, which are very interesting, but I don't 
think anybody is proposing reinventing anything - least of all me. The problem 
here is not whether there are known rigorous methods of determining the 
flatness 
of a curve. We are looking for a very fast heuristic that reduces the number of 
bisections of a cubic spline to the minimum in most cases, and behaves 
reasonably in other cases; in that it never reduces the number of bisections 
below the minimum, or produces far too many.

Any system that always results in at least as many bisections as the minimum 
number required to flatten the curve to satisfy our definition of flatness, and 
does not enter an infinite loop, will give correct output.We know how to do the 
job correctly; the problem is doing it fast.

After looking at the papers you cite for a short while my impression is that 
they cannot easily be used without floating-point arithmetic, which is not used 
in FreeType (and that policy certainly won't be relaxed for a while, I am 
sure). 
Fixed-point is never a satisfactory substitute where multiplication and 
squaring 
of coordinates is used, because it can easily lead to overflows of the need for 
elaborate work-arounds for overflows. Methods relying on the cubic spline 
formula will inevitably require cubes of coordinates. FreeType works in 64ths 
of 
pixels, so in signed 32-bit arithmetic we are restricted to a maximum 
coordinate 
size of sqrt(2^31) = 1290 64ths, or 20 pixels, which makes it impossible. The 
method described in the first paper you cite requires as a starting point the 
distance of the control points from the straight line, which needs squares and 
square roots, posing more problems for integer overflow and speed.

If you can code up a better fix than mine, using one of the algorithms you 
cite, 
I will be very happy to withdraw my suggestion in favour of yours. I think an 
insuperable difficulty will be the possibility of overflow and the speed of the 
code. I hope to be proved wrong!

Best regards,

Graham




- Original Message 
From: David Bevan david.be...@pb.com
To: freetype-devel freetype-devel@nongnu.org
Sent: Tuesday, 31 August, 2010 9:14:36
Subject: RE: [ft-devel] a satisfactory fix for the cubic spline bug


Rather than piecemeal reinventing of the wheel, I would have thought that FT 
should implement a mathematically rigorous flattener. The following might be a 
good place to start:

http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-ready%20CISST02%202.pdf


Or:

http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/bezier%20cccg04%20paper.pdf


Naively, I had assumed that this sort of issue would have been resolved 
properly 
back in the pre-history of FT, since it is obviously of critical importance for 
correct output.

Since it apparently hasn't been, we can make use of the latest research.

David %^


 -Original Message-
 From: freetype-devel-bounces+david.bevan=pb@nongnu.org
 [mailto:freetype-devel-bounces+david.bevan=pb@nongnu.org] On Behalf Of
 Graham Asher
 Sent: 30 August 2010 10:59
 To: freetype-devel
 Subject: [ft-devel] a satisfactory fix for the cubic spline bug
 
 I thought about this overnight and realised that we can slightly modify
 the existing heuristic to get a much simpler fix. Instead of trying to
 find points on the curve or trying to measure the distance from a point
 to a straight line, we adapt the earlier idea, used in existing FreeType
 code, of finding the maximum coordinate difference (that is, whichever
 is greater of dx and dy):
 
 * existing method: use max coordinate difference between middle of
 spline, found by bisection, and middle of straight line
 
 * new method: use max coordinate difference between either of the two
 control points and the middle of the straight line
 
 This yields the following code (start of gray_render_cubic), which
 works, fixes the bug, and is probably faster, because it is certainly
 simpler. I don't think I'll go any further than this.
 
   static int
   gray_render_cubic( RAS_ARG_ FT_Vector*  control1,
   FT_Vector*  control2,
   FT_Vector*  to )
   {
 int top, level;
 int*levels;
 FT_Vector*  arc;
 int error = 0;
 
 /*
 Find the furthest distance of a coordinate of a control point from the
 midpoint of the line.
 */
 int dx1, dy1, dx2, dy2;
 int midx = (DOWNSCALE(ras.x) + to-x) / 2;
 int midy = (DOWNSCALE(ras.y) + to-y) / 2;
 dx1 = control1-x - midx; if (dx1  0) dx1 = -dx1;
 dy1 = control1-y - midy; if (dy1  0) dy1 = -dy1;
 dx2 = control2-x - midx; if (dx2  0) dx2 = -dx2;
 dy2 = control2-y - midy; if (dy2  0) dy2 = -dy2;
 if (dx1  dy1)
 dx1 = dy1;
 if (dx1  dx2)
 dx1 = dx2;
 if (dx1  dy2)
 dx1 = dy2;
 
 if (dx1 = ras.cubic_level)
 return gray_render_line( RAS_VAR_ to-x, to-y 

Re: [ft-devel] a satisfactory fix for the cubic spline bug

2010-08-31 Thread Werner LEMBERG

 Naively, I had assumed that this sort of issue would have been
 resolved properly back in the pre-history of FT, since it is
 obviously of critical importance for correct output.

Well, Graham tries to make FreeType faster than the originally used
(and working) algorithm.

 Since it apparently hasn't been, we can make use of the latest
 research.

Thanks!  I'm waiting for Graham's comments :-)


Werner

___
Freetype-devel mailing list
Freetype-devel@nongnu.org
http://lists.nongnu.org/mailman/listinfo/freetype-devel


Re: [ft-devel] a satisfactory fix for the cubic spline bug

2010-08-31 Thread GRAHAM ASHER
Correction: for we are restricted to a maximum coordinate 
size of sqrt(2^31) read we are restricted to a maximum coordinate 
size of the cube root of 2^31


- Original Message 
From: GRAHAM ASHER graham.as...@btinternet.com
To: David Bevan david.be...@pb.com; freetype-devel freetype-devel@nongnu.org
Sent: Tuesday, 31 August, 2010 12:18:45
Subject: Re: [ft-devel] a satisfactory fix for the cubic spline bug

David,

Thank you very much for the citations, which are very interesting, but I don't 
think anybody is proposing reinventing anything - least of all me. The problem 
here is not whether there are known rigorous methods of determining the 
flatness 

of a curve. We are looking for a very fast heuristic that reduces the number of 
bisections of a cubic spline to the minimum in most cases, and behaves 
reasonably in other cases; in that it never reduces the number of bisections 
below the minimum, or produces far too many.

Any system that always results in at least as many bisections as the minimum 
number required to flatten the curve to satisfy our definition of flatness, and 
does not enter an infinite loop, will give correct output.We know how to do the 
job correctly; the problem is doing it fast.

After looking at the papers you cite for a short while my impression is that 
they cannot easily be used without floating-point arithmetic, which is not used 
in FreeType (and that policy certainly won't be relaxed for a while, I am 
sure). 

Fixed-point is never a satisfactory substitute where multiplication and 
squaring 

of coordinates is used, because it can easily lead to overflows of the need for 
elaborate work-arounds for overflows. Methods relying on the cubic spline 
formula will inevitably require cubes of coordinates. FreeType works in 64ths 
of 

pixels, so in signed 32-bit arithmetic we are restricted to a maximum 
coordinate 

size of sqrt(2^31) = 1290 64ths, or 20 pixels, which makes it impossible. The 
method described in the first paper you cite requires as a starting point the 
distance of the control points from the straight line, which needs squares and 
square roots, posing more problems for integer overflow and speed.

If you can code up a better fix than mine, using one of the algorithms you 
cite, 

I will be very happy to withdraw my suggestion in favour of yours. I think an 
insuperable difficulty will be the possibility of overflow and the speed of the 
code. I hope to be proved wrong!

Best regards,

Graham




- Original Message 
From: David Bevan david.be...@pb.com
To: freetype-devel freetype-devel@nongnu.org
Sent: Tuesday, 31 August, 2010 9:14:36
Subject: RE: [ft-devel] a satisfactory fix for the cubic spline bug


Rather than piecemeal reinventing of the wheel, I would have thought that FT 
should implement a mathematically rigorous flattener. The following might be a 
good place to start:

http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-ready%20CISST02%202.pdf



Or:

http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/bezier%20cccg04%20paper.pdf



Naively, I had assumed that this sort of issue would have been resolved 
properly 

back in the pre-history of FT, since it is obviously of critical importance for 
correct output.

Since it apparently hasn't been, we can make use of the latest research.

David %^


 -Original Message-
 From: freetype-devel-bounces+david.bevan=pb@nongnu.org
 [mailto:freetype-devel-bounces+david.bevan=pb@nongnu.org] On Behalf Of
 Graham Asher
 Sent: 30 August 2010 10:59
 To: freetype-devel
 Subject: [ft-devel] a satisfactory fix for the cubic spline bug
 
 I thought about this overnight and realised that we can slightly modify
 the existing heuristic to get a much simpler fix. Instead of trying to
 find points on the curve or trying to measure the distance from a point
 to a straight line, we adapt the earlier idea, used in existing FreeType
 code, of finding the maximum coordinate difference (that is, whichever
 is greater of dx and dy):
 
 * existing method: use max coordinate difference between middle of
 spline, found by bisection, and middle of straight line
 
 * new method: use max coordinate difference between either of the two
 control points and the middle of the straight line
 
 This yields the following code (start of gray_render_cubic), which
 works, fixes the bug, and is probably faster, because it is certainly
 simpler. I don't think I'll go any further than this.
 
   static int
   gray_render_cubic( RAS_ARG_ FT_Vector*  control1,
   FT_Vector*  control2,
   FT_Vector*  to )
   {
 int top, level;
 int*levels;
 FT_Vector*  arc;
 int error = 0;
 
 /*
 Find the furthest distance of a coordinate of a control point from the
 midpoint of the line.
 */
 int dx1, dy1, dx2, dy2;
 int midx = (DOWNSCALE(ras.x) + to-x) / 2;
 int midy = (DOWNSCALE(ras.y) + 

RE: [ft-devel] a satisfactory fix for the cubic spline bug

2010-08-31 Thread David Bevan
Graham/Werner,



Perhaps I have misunderstood something. If so, I apologize.



I hadn't been following this closely until I noticed an email saying that the 
curve flattening algorithm failed under some circumstances. That seemed very 
shocking to me. I would have presumed that the flattening algorithm would be 
defined in a mathematically rigorous manner and hence would be known to always 
work (bar any 'typos' in the code).



Checking through the ft-devel archive suggests that the beginning of this issue 
was the message of 7th June, which starts, I have discovered a possible 
inefficiency in gray_render_cubic in ftsmooth.c. Removing it (by means of what 
I admit is a hack based on a limited understanding of the code) gives a vast 
speedup with no apparent loss of quality.



For something as critical as the curve flattening, I wouldn't consider a hack 
of any sort appropriate. I haven't followed the message trail in detail but my 
understanding is that some version of this hack was accepted into the source 
and was subsequently shown to be incorrect. Fixes are now being proposed to the 
hack, and this is being done by someone who states that they are somewhat 
ignorant of the mathematics of cubic splines.



If I was managing this project, I would certainly consider this an unacceptable 
approach / sequence of events. Better to keep the inefficiency than (a) break 
the functionality, and (b) end up with code that is not obviously correct.





I didn't respond to the following query earlier:


If there are any good mathematicians out there (better than me at this, which 
sets quite a low bar), please confirm that no point on a cubic spline curve 
with both control points on the same side of the straight line from start to 
end can be further from the line than the curve's midpoint as defined by 
bisection of the curve.

A simple continuity/smoothness argument shows that the maximum deviation of a 
cubic spline is not always at the curve's midpoint: If with the control points 
on either side, the maximal deviation can be elsewhere, and a smooth movement 
of the control points leads to a smooth change in the curve then the position 
of the maximal deviation moves smoothly too (and hence is in fact hardly ever 
actually at the mid-point).




I don't have time to investigate this in detail for a while, but might be able 
to do so sometime next week.



David %^



P.S. I have a degree in mathematics from Oxford University.





 -Original Message-

 From: GRAHAM ASHER [mailto:graham.as...@btinternet.com]

 Sent: 31 August 2010 12:19

 To: David Bevan; freetype-devel

 Subject: Re: [ft-devel] a satisfactory fix for the cubic spline bug



 David,



 Thank you very much for the citations, which are very interesting, but I

 don't

 think anybody is proposing reinventing anything - least of all me. The

 problem

 here is not whether there are known rigorous methods of determining the

 flatness

 of a curve. We are looking for a very fast heuristic that reduces the

 number of

 bisections of a cubic spline to the minimum in most cases, and behaves

 reasonably in other cases; in that it never reduces the number of

 bisections

 below the minimum, or produces far too many.



 Any system that always results in at least as many bisections as the

 minimum

 number required to flatten the curve to satisfy our definition of

 flatness, and

 does not enter an infinite loop, will give correct output.We know how to

 do the

 job correctly; the problem is doing it fast.



 After looking at the papers you cite for a short while my impression is

 that

 they cannot easily be used without floating-point arithmetic, which is not

 used

 in FreeType (and that policy certainly won't be relaxed for a while, I am

 sure).

 Fixed-point is never a satisfactory substitute where multiplication and

 squaring

 of coordinates is used, because it can easily lead to overflows of the

 need for

 elaborate work-arounds for overflows. Methods relying on the cubic spline

 formula will inevitably require cubes of coordinates. FreeType works in

 64ths of

 pixels, so in signed 32-bit arithmetic we are restricted to a maximum

 coordinate

 size of sqrt(2^31) = 1290 64ths, or 20 pixels, which makes it impossible.

 The

 method described in the first paper you cite requires as a starting point

 the

 distance of the control points from the straight line, which needs squares

 and

 square roots, posing more problems for integer overflow and speed.



 If you can code up a better fix than mine, using one of the algorithms you

 cite,

 I will be very happy to withdraw my suggestion in favour of yours. I think

 an

 insuperable difficulty will be the possibility of overflow and the speed

 of the

 code. I hope to be proved wrong!



 Best regards,



 Graham









 - Original Message 

 From: David Bevan david.be...@pb.com

 To: freetype-devel freetype-devel@nongnu.org

 Sent: Tuesday, 31 August, 2010 

Re: [ft-devel] a satisfactory fix for the cubic spline bug

2010-08-31 Thread Werner LEMBERG

 If I was managing this project, I would certainly consider this an
 unacceptable approach / sequence of events.

Usually, I'm quite conservative, and Graham has provided a lot of
useful additions to the FreeType code.  I trust him to fix that in due
course.

 Better to keep the inefficiency than (a) break the functionality,
 and (b) end up with code that is not obviously correct.

Uh, oh, you are extremely exaggerating.  This is not helpful.  Until
the bug report we weren't aware of problems, and Graham's change is in
since two months already, and the code is probably run by millions of
people...

It's easy to revert if no satisfying solution can be found.

Thanks for offering help, though.


Werner

___
Freetype-devel mailing list
Freetype-devel@nongnu.org
http://lists.nongnu.org/mailman/listinfo/freetype-devel


Re: [ft-devel] a satisfactory fix for the cubic spline bug

2010-08-31 Thread GRAHAM ASHER
David,

some points on what I think is a rather severe disquisition on your part:

(i) You over-react to my use of the word 'hack', which was light-hearted and 
self-deprecatory. Yes, my original fix was incorrect, and I have now found one 
that I am satisfied is correct. This is a normal process in software 
development.

Unfortunately nobody understands FreeType fully any more. This is a bad 
situation, but somewhat mitigated by the number of eyes on the problem, and the 
number of users willing to test the code. A full suite of regression tests, 
isolating each module and algorithm, would be great. If you do end up with some 
time, please consider writing some.

I did not check in the fix. I merely proposed it, hoping for comments and 
improvements. I am very busy and any help is welcome.

(ii) The error in gray_render_cubic was gross. It didn't cause a slight 
inefficiency; it resulted in a very great number of unnecessary bisections.

(iii) Although there are provably correct mathematical algorithms, converting 
them to provably correct computer programs is non-trivial - in fact, impossible 
outside small toy problems. Your statement Better to keep the inefficiency 
than 
(a) break the functionality, and (b) end up with code that is not obviously 
correct. is laudable, but substantive code that is obviously correct doesn't 
exist in this world.

(iv) The phrase Fixes are now being proposed to the hack, and this is being 
done by someone who states that they are somewhat ignorant of the mathematics 
of 
cubic splines. is strange. Why the passive voice and the use of someone? 
It's 
still me, and my name appears on the e-mails. I have been working on and off 
with cubic splines since about 1986. No, my degree is not in mathematics, but I 
am not ignorant of these matters.

(v) Congratulations on your degree. I hope you have time to use your 
mathematical knowledge to help with this problem.

(vi) Out of interest, please give an example, with coordinates, of a cubic 
spline with both control points on the same side of the straight line from 
start 
to end, for which the midpoint of the curve, as defined by bisection, is not 
the 
point of maximum deviation.

Best regards,

Graham





From: David Bevan david.be...@pb.com
To: GRAHAM ASHER graham.as...@btinternet.com; freetype-devel 
freetype-devel@nongnu.org
Sent: Tuesday, 31 August, 2010 14:01:43
Subject: RE: [ft-devel] a satisfactory fix for the cubic spline bug

 
Graham/Werner,
 
Perhaps I have misunderstood something. If so, I apologize.
 
I hadn't been following this closely until I noticed an email saying that the 
curve flattening algorithm failed under some circumstances. That seemed very 
shocking to me. I would have presumed that the flattening algorithm would be 
defined in a mathematically rigorous manner and hence would be known to always 
work (bar any 'typos' in the code).
 
Checking through the ft-devel archive suggests that the beginning of this issue 
was the message of 7th June, which starts, I have discovered a possible 
inefficiency in gray_render_cubic in ftsmooth.c. Removing it (by means of what 
I 
admit is a hack based on a limited understanding of the code) gives a vast 
speedup with no apparent loss of quality.
 
For something as critical as the curve flattening, I wouldn't consider a hack 
of any sort appropriate. I haven't followed the message trail in detail but my 
understanding is that some version of this hack was accepted into the source 
and 
was subsequently shown to be incorrect. Fixes are now being proposed to the 
hack, and this is being done by someone who states that they are somewhat 
ignorant of the mathematics of cubic splines.
 
If I was managing this project, I would certainly consider this an unacceptable 
approach / sequence of events. Better to keep the inefficiency than (a) break 
the functionality, and (b) end up with code that is not obviously correct.
 
 
I didn't respond to the following query earlier:
 
If there are any good mathematicians out there (better than me at this, which 
sets quite a low bar), please confirm that no point on a cubic spline curve 
with 
both control points on the same side of the straight line from start to end can 
be further from the line than the curve's midpoint as defined by bisection of 
the curve.
 
A simple continuity/smoothness argument shows that the maximum deviation of a 
cubic spline is not always at the curve's midpoint: If with the control points 
on either side, the maximal deviation can be elsewhere, and a smooth movement 
of 
the control points leads to a smooth change in the curve then the position of 
the maximal deviation moves smoothly too (and hence is in fact hardly ever 
actually at the mid-point).
 
 
I don't have time to investigate this in detail for a while, but might be able 
to do so sometime next week.
 
David %^
 
P.S. I have a degree in mathematics from Oxford University.
 
 
 -Original Message-
 

Re: [ft-devel] a satisfactory fix for the cubic spline bug

2010-08-31 Thread GRAHAM ASHER
And putting this equation into more standard quadratic form I get

d_norm(v) = 0.072(v^2) + 0.229v + 0.449

which yields 0.75 as expected for v = 1, so it looks as though I have the right 
equation here.

Graham





From: GRAHAM ASHER graham.as...@btinternet.com
To: David Bevan david.be...@pb.com
Sent: Tuesday, 31 August, 2010 17:07:52
Subject: Re: [ft-devel] a satisfactory fix for the cubic spline bug


Can you give the workings? The equation I think you mean is this one:

0.07200(v + 3.180556)v + 0.449000,

so when I substitute 0.1 for v I get

0.07200(0.1 + 3.180556)0.1 + 0.449000

which gives 0.47262, and multiplying that by 50, the maximum deviation of a 
control point, gives 23.631, not your y value, so obviously I'm missing 
something; 


Thanks,

Graham





From: David Bevan david.be...@pb.com
To: GRAHAM ASHER graham.as...@btinternet.com
Sent: Tuesday, 31 August, 2010 16:20:08
Subject: RE: [ft-devel] a satisfactory fix for the cubic spline bug

 


 
From:GRAHAM ASHER [mailto:graham.as...@btinternet.com] 
Sent: 31 August 2010 15:56
To: David Bevan
Subject: Re: [ft-devel] a satisfactory fix for the cubic spline bug
 
Midpoint as defined by bisection is the point you get when you split a cubic 
spline into two by the bisection method (as used by FreeType in 
gray_split_cubic). It is defined as the midpoint of the line between the two 
midpoints of the lines between the three midpoints of the lines between the 
four 
control points, taken in order. It is of course a point on the curve.

So that’s the point t = 0.5 in the parametric equation — found using de 
Casteljau’s algorithm.
 
Your example gives a midpoint of (31.25, 20.625). Applying the midpoint method 
again (hastily) to the left-hand curve seems to yield a y coordinate of 
21.84375, so if my arithmetic is correct your example is a good one.

Using the equation in Hain’s paper (p.4; with v=0.1), the maximum deviation 
tmax 
in my example is at 0.3503928884, which is the point (16.26529900, 23.37564709).
 
David %^
 
Thanks,

Graham
 


 
From:David Bevan david.be...@pb.com
To: GRAHAM ASHER graham.as...@btinternet.com
Sent: Tuesday, 31 August, 2010 15:20:59
Subject: RE: [ft-devel] a satisfactory fix for the cubic spline bug


 
From:GRAHAM ASHER [mailto:graham.as...@btinternet.com] 
Sent: 31 August 2010 15:01
To: David Bevan; freetype-devel
Subject: Re: [ft-devel] a satisfactory fix for the cubic spline bug
 
David,
(vi) Out of interest, please give an example, with coordinates, of a cubic 
spline with both control points on the same side of the straight line from 
start 
to end, for which the midpoint of the curve, as defined by bisection, is not 
the 
point of maximum deviation.
I expect that something like the following would be an example:
 
P0: 0,0
P1: 0,50
P2: 50,5
P3, 100,0
 
But to be sure I’d need to know what you mean by “midpoint as defined by 
bisection”? Is it t = 0.5 in the parametric equation, the point perpendicular 
to 
the midpoint of the chord, or something else?
 
David %^___
Freetype-devel mailing list
Freetype-devel@nongnu.org
http://lists.nongnu.org/mailman/listinfo/freetype-devel


Re: [ft-devel] a satisfactory fix for the cubic spline bug

2010-08-31 Thread James Cloos
 GA == GRAHAM ASHER graham.as...@btinternet.com writes:

GA Some reasons this hasn't made very many waves;

GA 1. My impression is that nearly all actual fonts are TrueType these
GA days.  TrueType does't use cubic splines. It uses quadratics only.

Cubic fonts remain an important sector, especially for print and for
display of work intended for print.

That notwithstanding:

GA 2. Font designers very rarely use 'exciting' cubic splines. Splines
GA with control points on both sides of the line hardly ever occur in
GA glyphs, and I would expect self-crossing curves never to occur.

That, on the other hand, is very true.  In fact, and IIRC, Adobe
actively promotes those objective to font designers, to ensure that
the fonts work well with their software, including both their desktop
software and their PS/PDF engines.

GA We must of course be correct for all curves, but we need optimise
GA heavily only for the common case where p0, p1, p2 and p3 have
GA r-coordinates (using Hain's notation) in that order, and
GA s-coordinates with the same sign.

Consequent to your second point, that is also true.

-JimC
-- 
James Cloos cl...@jhcloos.com OpenPGP: 1024D/ED7DAEA6

___
Freetype-devel mailing list
Freetype-devel@nongnu.org
http://lists.nongnu.org/mailman/listinfo/freetype-devel