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

[Tom Kacvinsky]

Just a quick question:  are we guaranteed that 32 iterations will be enough?
I know the code works for the rasterizer, but I am sure there is a Type 1,
CID, or CFF font out there that has cubic Bezier curves that will trip up the
32 iteration maximum.

Moreover, if we decide to stick with the iterative process, shouldn't we put a
restraint on the number of iterations allowed to make sure we don't go past the
end of the array?

Tom

On Mon, 23 Apr 2001, Tom Kacvinsky wrote:

> I just checked the math: 32*3 + 1 should allow for the first iteration + 31
> subsequent interations, for a total of 32 iterations.
>
> It is nice to know that the code works, provided there is enough arc stack.  I
> was tripping out on that one!
>
> Tom
>
> On Mon, 23 Apr 2001, David Turner wrote:
>
> > Hi Tom,
> >
> > >
> > > Werner, or me?  Yes, the arc stack can overflow...  There are only 33
> > > slots open in the arc stack, which, according to the code, means we can
> > > only go through 9 iterations:
> > >
> > >   33 slots available
> > >
> > >   4 slots taken for the first iteration
> > >   3 slots taken for each subsequent iteration
> > >
> > >   33 = 3(number of subsequent iterations) + 4
> > >   number of subsequent iterations = 9
> > >
> >
> > Waow, it seems that's a silly mistake from me, because what I had in mind 
> > when
> > writing this code was allowing 32 iterations, not 32 slots !!
> >
> > So changing the size to 32*3+1 should be ok, though we sure need to check by
> > hand that the "+1" is not too small..
> >
> > > Now, Werner posted a statement from Richard Kinch that a Bezier cubic can 
> > > be
> > > split into monotonic cubic Beziers (or at least that is what I thought was
> > > said), but there are some arcs which, when split in such a fashion, result
> > > in o(n) (is that supposed to be O(n)?) sub arcs, where n is the width or
> > > height of the orignal curve's bbox (cbox?).  That could be a *lot* of
> > > subarcs, or at least more than 9 iterations allows for.
> > >
> > > > One obvious solution is to simply limit the stack growth manually
> > > > though :-)
> > > >
> > > > Note that the same algorithm is used by the rasterizers (in theory),
> > > > and these have never shown any kind of problem with the bezier stack..
> > > >
> > >
> > > Well, that is interesting.  Isn't the cbox good enough for the 
> > > rasterizers?
> > >
> >
> > Interestingly, the smooth rasterizer uses a stack of 32*3 slots, while the
> > monochrome one uses a stack of 2*32+1 (I'm sure this dates to the time were 
> > it
> > only supported quadratic beziers !!)
> >
> > I'll fix both.., plus the Cubic_Check function..
> >
>
>
> _______________________________________________
> Devel mailing list
> address@hidden
> http://www.freetype.org/mailman/listinfo/devel
>