Re: [Devel] Problems with bbox code and cubic bezier curves

[Tom Kacvinsky]

Hi,

>
> I wanted to use FT_Outline_Get_BBox for arbitrary Bezier curves. If Type1 spec
> has such a restriction then stack overflow may never occur (is there a proof
> for this?). Does TT and all other supported and will-be-supported fonts have
> the same restriction. If yes than this should be documented in the source code
> or header files.
>

It is not a restriction, it is a recommendation of the Type 1 specification.
That is the problem:  the recommendations do not have to be followed. :(

And now that I think about it, the recommendation is that extreme points be
start/end points for arcs.  There can be other start/end points, not necessarily
placed at extrema.

Before I speak anymore, let me say that I do not have a mathematical proof that
following Adobe's guidelines are guaranteed to make the algorithm work without
too many iterations.  But the general idea is this: placing end/start points at
extreme points breaks the contours into monotonic arcs (whether these monotonic
arcs are further subdivided with other start/end points does not matter, because
if the "parent" arc is monotonic so are the subarcs).  Thus, the algorithm
should never get into the splitting code, because we fall into one of the
monotonic cases.

I am not sure if the TT specification has the same kind of recommendations for
quadratic bezier curves.

Those are the only two arcs that FT supports: cubic and quadratic bezier curves.

Anyway, the code should accomodate arcs that don't have "nice" properties.

I'll take a look at the font sample(s) you provided.

>
> Here is my original 'bug'-report (proto.cpp is using OS stack which may also
> be overflowed, but allows for more than 32 iterations):
>
> > Subject: Re: FT_Outline_Get_BBox
> > Date: Fri, 03 Nov 2000 12:28:49 -0800
> > From: Ivan Nincic <address@hidden>
> >
> > BBox_Cubic_Check is crashing for many curves because of the small stack size
> > (33).
> >
> > Here is an example :
> > MoveTo: 408.9111, 535.3164
> > CurveTo :455.8887, 634.396, -37.8765, 786.2207, 164.6074, 535.3164
> >
> > Attached is the sample PDF file.
> >
> > Does anybody know what would be the largest stack size given an arbitrary
> > Bezier curve?
> >
> > I will look into this ... If the stack is too large we should probably look
> > at some other algorithm.
> >
> >
> > > I have couple of questions related to FT_Outline_Get_BBox.c
> > >
> > > 1)
> > >
> > >  if ( y1 == y4 ) {
> > >    if ( y1 == y2 && y1 == y3 ) {     /* Flat */
> > >      y4 = y1;                        // 236
> > >      goto Test;
> > >    }
> > >  }
> > >
> > > Is the assignment on line 236 some kind of coding style or is it
> > > redundant?
> >
> > Redundant :-)  I've fixed it.
> >
> > > 2)
> > >
> > > BBox_Cubic_To() and BBox_Conic_To() callback never update the user->last
> > > point (as BBox_Move_To() does). Does this mean that two consecutive
> > > Beziers may have a wrong bbox ?
> >
> > It's a bug also.
> >
> > Thanks for the report.
>