[cairo] Fwd: RE: [ft-devel] latest patch file for spline flattening

[Behdad Esfahbod]

Thought people may find the hypot() estimate useful here.

behdad

-------- Original Message --------
Subject: RE: [ft-devel] latest patch file for spline flattening
Date: Mon, 6 Sep 2010 07:04:14 -0400
From: David Bevan <david.bevan at pb.com>
To: Graham Asher <graham.asher at btinternet.com>
CC: freetype-devel <freetype-devel at nongnu.org>

Graham,

That's looking much closer to what I would have thought we needed; only
splitting the curve when required. However, your "fast heuristic" can be very
inaccurate.

Consider

  P0: 0,0
  P1: 5,5
  P2: 95,5
  P3: 100,0

The max deviation is 3.75 (0.75 * 5 since Hain's v == 1), but your heuristic
gives a value of 45 - twelve times too great.


Btw, I think that dx1, dy1, ... need to be of type TPos, not int.


On the issue of avoiding square roots, a little bit of algebra shows that it
is possible to estimate r = sqrt(dx^2 + dy^2) with a simple linear combination
of dx and dy.

For example, if an overestimate is required, and dx >= dy, you can use

  r_upperbound = dx + (sqrt(2) - 1) * dy

which overestimates by no more than 8.5%.

For integer arithmetic, sqrt(2) - 1 can be (over)estimated by 107/256.

For example, you could use this approximation to do something like this:

  dx1 = abs(control1->x - midx);
  dy1 = abs(control1->y - midy);
  if (dx1 >= dy1)
    dr1 = dx1 + (107 * dy1 + 255) >> 8;
  else
    dr1 = dy1 + (107 * dx1 + 255) >> 8;

  dx2 = abs(control2->x - midx);
  dy2 = abs(control2->y - midy);
  if (dx2 >= dy2)
    dr2 = dx2 + (107 * dy2 + 255) >> 8;
  else
    dr2 = dy2 + (107 * dx2 + 255) >> 8;

  /* deviation never exceeds 75% of control point dist */
  if (dr1 >= dr2)
    dev_max = (3 * dr1 + 3) >> 2;
  else
    dev_max = (3 * dr2 + 3) >> 2;

  if (dev_max <= FT_MAX_CURVE_DEVIATION)
    ...


Of course, this doesn't resolve the problem I mentioned above; for the example
curve, this gives dev_max a value of 36 - still nine times too great.


I hope to have something based a bit more closely on Hain's paper by the end
of tomorrow. I may use something like the square-root avoiding estimate above
to approximate his L value.


David %^>


> -----Original Message-----
> From: freetype-devel-bounces+david.bevan=pb.com at nongnu.org
> [mailto:freetype-devel-bounces+david.bevan=pb.com at nongnu.org] On Behalf Of
> Graham Asher
> Sent: 6 September 2010 11:10
> To: freetype-devel
> Subject: [ft-devel] latest patch file for spline flattening
> 
> Here's a new version of my spline flattening patch. (I would like to be
> able to push this to the git repository but am having authentication
> problems; Werner has been helping me, but no success so far, probably
> because of my ineptitude in these matters.).
> 
> The nub of the latest change is that I found that predicting the number
> of recursion levels is not reliable when splitting a cubic spline for
> flattening. A better way is to check the flatness inside the loop -
> using the fast heuristic of taking the maximum coordinate difference of
> a control point from the chord midpoint. This also makes the code
> simpler - and, surprisingly, faster, according to my benchmark; however,
> my benchmark is based on cartographic, not typographic, use, so will
> need confirmation.
> 
> The patch obviously still solves the bug involving s-shaped curves
> (control points on both sides of the chord).
> 
> Graham


_______________________________________________
Freetype-devel mailing list
Freetype-devel at nongnu.org
http://lists.nongnu.org/mailman/listinfo/freetype-devel