When to stop the subdivision while rendering a bezier.
Antoon Pardon
I also know the general principle for when to stop.
However I have trouble translating this principle
into a condition usable in an algorithm.
Searching the net hasn't brought much usefull results
either. e.g. one webpage suggested to just draw
the line p0 p3, when p0, p1, p2 and p3 were sufficiently
colinear, which IMO would go wrong if the four points would
be on a line in the following order: p1, p0, p3, p2.
So can someone help me with the general condition?
--
Antoon Pardon
Hans-Bernhard Broeker
> Searching the net hasn't brought much usefull results
> either. e.g. one webpage suggested to just draw the line p0 p3, when
> p0, p1, p2 and p3 were sufficiently colinear, which IMO would go
> wrong if the four points would be on a line in the following order:
> p1, p0, p3, p2.
Depends on how you decide to measure collinearity... If you go by
angles, the latter case won't come out as "sufficiently collinear" to
begin with.
--
Hans-Bernhard Broeker (bro...@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
Stephen H. Westin
> I'm rather familiar with how to draw a bezier curve.
> I also know the general principle for when to stop.
> However I have trouble translating this principle
> into a condition usable in an algorithm.
>
> Searching the net hasn't brought much usefull results
> either. e.g. one webpage suggested to just draw
> the line p0 p3, when p0, p1, p2 and p3 were sufficiently
> colinear, which IMO would go wrong if the four points would
> be on a line in the following order: p1, p0, p3, p2.
Well, yes, that's a pathological case.
> So can someone help me with the general condition?
Another choice would be to subdivide until each segment is a pixel or
less in length. Overkill, but safe. Or detect pathological cases and
treat them separately. The case you present has a second derivative
that vanishes, doesn't it? You could probably detect that. Or just be
careful when the control points are (nearly) colinear.
--
-Stephen H. Westin
Any information or opinions in this message are mine: they do not
represent the position of Cornell University or any of its sponsors.
Gernot Hoffmann
I don´t think your curve is something special, concerning the
rendering.
The collinearity of control points is not useful as a criterion.
Important is the device resolution (monitor or printer pixel).
Quoted from the help text in PSALter (Quite.com), a PostScript Editor/
Interpreter (probably similar in the PostScript Lang. Reference
Manual):
"The setflat operator sets the 'flatness' value in the graphics state.
This controls how accurately curves are converted to straight lines.
The value num gives a number of pixels 'error' which is allowed, that
is the maximum distance between the curve, and the straight line which
approximates it."
The question is only how to check this fast.
Best regards --Gernot Hoffmann
Just d' FAQs
wrote:
>I'm rather familiar with how to draw a bezier curve.
>I also know the general principle for when to stop.
>However I have trouble translating this principle
>into a condition usable in an algorithm.
>
>Searching the net hasn't brought much usefull results
>either. e.g. one webpage suggested to just draw
>the line p0 p3, when p0, p1, p2 and p3 were sufficiently
>colinear, which IMO would go wrong if the four points would
>be on a line in the following order: p1, p0, p3, p2.
Out of curiosity I had a look to see what GhostScript does. Turns out
the strategy is to precompute the number of segments so the control
points can be computed cheaply with a DDA rather than subdivision.
Still, you might be interested in the following comment:
gxpflat.c
---------
* Copyright (C) 1997, 1998 Aladdin Enterprises. All rights reserved.
[snip]
* To calculate how many points to sample along a path in order to
* approximate it to the desired degree of flatness, we define
* dist((x,y)) = abs(x) + abs(y);
* then the number of points we need is
* N = 1 + sqrt(3/4 * D / flatness),
* where
* D = max(dist(p0 - 2*p1 + p2), dist(p1 - 2*p2 + p3)).
* Since we are going to use a power of 2 for the number of intervals,
* we can avoid the square root by letting
* N = 1 + 2^(ceiling(log2(3/4 * D / flatness) / 2)).
* (Reference: DEC Paris Research Laboratory report #1, May 1989.)
The cited report, available here
<ftp://ftp.digital.com/pub/DEC/PRL/research-reports/PRL-RR-1.pdf>
describes itself as
"a revised and extended version of the paper entitled ‘Incremental
Computation of Planar Maps’, by the same authors, published in the
SIGGRAPH’89 Conference Proceedings."
Other measures of flatness include these from Sequin's course notes:
o Control polygon length minus chord length.
o Sum of absolute value of turning angle between control segments.
o Sum of absolute distance of control points from chord.
I've seen others, also; but these suggestions should get you unstuck.
The "chord" mentioned is the line from first to last control point.
Roger Willcocks
news:a815dbcf.03090...@posting.google.com...
> Antoon Pardon <apa...@forel.vub.ac.be> wrote in message
news:<slrnblgobh....@trout.vub.ac.be>...
> > I'm rather familiar with how to draw a bezier curve.
> > I also know the general principle for when to stop.
> > However I have trouble translating this principle
> > into a condition usable in an algorithm.
> "The setflat operator sets the 'flatness' value in the graphics state.
> This controls how accurately curves are converted to straight lines.
> The value num gives a number of pixels 'error' which is allowed, that
> is the maximum distance between the curve, and the straight line which
> approximates it."
>
> The question is only how to check this fast.
>
> Best regards --Gernot Hoffmann
By calculating the error as the distance between each point on the Bezier
and the corresponding point at the same 't' value on a straight line between
the endpoints, you can eliminate the p1 p0 p3 p2 problem.
See the 'flatten' routine in http://www.rops.org/sourcecode/ygcurve.c.html
(from the sourcecode for the RoPS Postscript interpreter) for an
implementation of this idea.
From the comments:
--snip--
Flattening A Bezier Curve
The points on a Bezier curve are given by
xc = (1-t)^3 P0x + 3t(1-t)^2 P1x + 3t^2(1-t) P2x + t^3 P3x ; t =
0..1
yc = ...
A straight line
xl = (1-t) P0x + t P3x
yl = ...
is obtained by setting
Q0x = P0x; Q1x = (2P0x + P3x) / 3; Q2x = (2P3x + P0x) / 3; Q3x = P3x
Hence the error in x due to using the line rather than the curve is
Ex = xc - xl = 3t(1-t)^2 (Q1x - P1x) + 3t^2(1-t) (Q2x - P2x)
Or
Ax = 3 (Q1x - P1x), Bx = 3 (Q2x - P2x)
Ex = t (1-t) { (1-t) Ax + t Bx }
And the distance between corresponding points on the curve and the line
is given by
F^2 = Ex^2 + Ey^2
= t^2 (1-t)^2 [ { (1-t) Ax + t Bx }^2 + { (1-t) Ay + t By }^2 ]
Now, in the range t = 0..1
max ( t^2 (1-t)^2 ) == 1/16
max { (1-t) Ax + t Bx }^2 == max ( Ax^2, Bx^2 )
max { (1-t) Ay + t By }^2 == max ( Ay^2, By^2 )
Yielding an upper bound for F^2
--snip--
This maximum error estimation can be used to decide whether another
subdivision is required.
--
Roger
www.rops.org
Toby Thain
> On 5 Sep 2003 10:12:01 GMT, Antoon Pardon <apa...@forel.vub.ac.be>
> wrote:
> >I'm rather familiar with how to draw a bezier curve.
> >I also know the general principle for when to stop.
> >However I have trouble translating this principle
> >into a condition usable in an algorithm.
> >
> >Searching the net hasn't brought much usefull results
> >either. e.g. one webpage suggested to just draw
> >the line p0 p3, when p0, p1, p2 and p3 were sufficiently
> >colinear, which IMO would go wrong if the four points would
> >be on a line in the following order: p1, p0, p3, p2.
>
> Out of curiosity I had a look to see what GhostScript does. Turns out
> the strategy is to precompute the number of segments
Admittedly I haven't studied the GS source in question (later,
later...) but this seems like a very bad idea. You couldn't be
suggesting that GS estimates the number of segments and then steps t
by 1/n?! This would lose both the efficiency and fidelity of adaptive
subdivision.
>
> Other measures of flatness include these from Sequin's course notes:
>
> o Control polygon length minus chord length.
> o Sum of absolute value of turning angle between control segments.
> o Sum of absolute distance of control points from chord.
I've experimented quite a bit with Bézier drawing and the test which I
currently use is to check square of perpendicular distances (dot
product) between start point (p0) and first control point (p1), and
end point (p3) and second control point (p2). If both of these
distances are less than a certain threshold (e.g. flatness squared),
*and* both control points are on the same side of the line joining p0
and p3, then simply draw a straight line; otherwise subdivide. (Code
available on request.)
Recently, I've experimented with a Bresenham-inspired method which
subdivides until p0 and p3 quantise to the same pixel (and then sets
that pixel). I haven't analysed just how much slower this is than
decomposition into line segments, but it does eliminate any hint of
stepping! (Code available.)
Another place to look for sophisticated Bézier curve rasterising
methods is in Knuth's METAFONT. He generalised his algorithms to work
with polygonal brushes and was very careful about the quality of scan
conversion. Like PostScript, METAFONT uses cubic Béziers as its path
primitive.
Toby
Just d' FAQs
wrote:
>> Out of curiosity I had a look to see what GhostScript does. Turns out
>> the strategy is to precompute the number of segments
>>...
>
>Admittedly I haven't studied the GS source in question (later,
>later...) but this seems like a very bad idea. You couldn't be
>suggesting that GS estimates the number of segments and then steps t
>by 1/n?! This would lose both the efficiency and fidelity of adaptive
>subdivision.
Yes, a single calculation determines a suitable power of two. Only
profiling would reveal if this is preferable, and I believe GS has
been carefully optimized.
If you think this cannot win, you may not properly appreciate the
overhead of adaptive subdivision. The GS approach makes one fairly
simple calculation to find the number of steps, then uses forward
differences to efficiently generate just the necessary points. An
adaptive approach must test repeatedly, an extra cost. Subdivision is
more expensive than forward differencing, and generates four wasted
inner control points each time the cubic is split, two for each half.
(If a curve segment is flat a line is drawn between the two outer
control points, so generating inner points is wasteful.)
Forward differencing for a cubic looks like this:
P := P + d1
d1 := d1 + d2
d2 := d2 + d3
The quantities are 2D vectors, but that's still only 6 adds per
*final* control point.
No fidelity is lost, because the necessary number of segments will be
generated to meet the flatness requested. However more segments may be
created than with an adaptive recursion that can isolate curvature.
Again, profiling performance on typical data is the best arbiter, but
I find it completely plausible that GhostScript has chosen wisely.
Toby Thain
> On 21 Sep 2003 06:16:37 -0700, to...@telegraphics.com.au (Toby Thain)
> wrote:
> >> Out of curiosity I had a look to see what GhostScript does. Turns out
> >> the strategy is to precompute the number of segments
> >>...
> >
> >Admittedly I haven't studied the GS source in question (later,
> >later...) but this seems like a very bad idea. You couldn't be
> >suggesting that GS estimates the number of segments and then steps t
> >by 1/n?! This would lose both the efficiency and fidelity of adaptive
> >subdivision.
>
> Yes, a single calculation determines a suitable power of two. Only
> profiling would reveal if this is preferable, and I believe GS has
> been carefully optimized.
>
> If you think this cannot win, you may not properly appreciate the
> more expensive than forward differencing, and generates four wasted
> inner control points each time the cubic is split, two for each half.
> (If a curve segment is flat a line is drawn between the two outer
You make a good point about some redundant computations...
>
> No fidelity is lost, because the necessary number of segments will be
> generated to meet the flatness requested. However more segments may be
> created than with an adaptive recursion that can isolate curvature.
...but to really prove it, as you say, testing on real data would be
needed. Having long admired the recursive method for its adaptability
and elegance, I was shocked that anyone would take a stepwise
approach.
But perhaps you're right: real world PostScript curves may not gain
much from adaptation to local curvature; the very frequent cases of
curved paths I suppose are circles and character glyphs, and both of
those would seem to work OK with fixed size steps.
>
> Again, profiling performance on typical data is the best arbiter, but
> I find it completely plausible that GhostScript has chosen wisely.
I admit the possibility. Perhaps a GhostScript expert can enlighten
us.
Toby
Stephen H. Westin
<snip>
> ...but to really prove it, as you say, testing on real data would be
> needed. Having long admired the recursive method for its adaptability
> and elegance, I was shocked that anyone would take a stepwise
> approach.
>
> But perhaps you're right: real world PostScript curves may not gain
> much from adaptation to local curvature; the very frequent cases of
> curved paths I suppose are circles and character glyphs, and both of
> those would seem to work OK with fixed size steps.
It's more than that. Modern machines tend to slow down horribly on
conditional branches, due to pipelining and prefetch issues. So
executing a loop (especially if it can be unrolled effectively) a few
extra times, or even twice or four times as often as needed, might
well be faster than an "efficient" adaptive approach.
<snip>
Toby Thain
> to...@telegraphics.com.au (Toby Thain) writes:
>
> <snip>
>
> > ...but to really prove it, as you say, testing on real data would be
> > needed. Having long admired the recursive method for its adaptability
> > and elegance, I was shocked that anyone would take a stepwise
> > approach.
> >
> > But perhaps you're right: real world PostScript curves may not gain
> > much from adaptation to local curvature; the very frequent cases of
> > curved paths I suppose are circles and character glyphs, and both of
> > those would seem to work OK with fixed size steps.
>
> It's more than that. Modern machines tend to slow down horribly on
> conditional branches, due to pipelining and prefetch issues. So
> executing a loop (especially if it can be unrolled effectively) a few
> extra times, or even twice or four times as often as needed, might
> well be faster than an "efficient" adaptive approach.
Adaptive might win if it's necessary to generate a minimum number of
line segments - for example, converting to a particular polygonal
format for permanent storage or transmission, or if subsequent
processing steps are more efficient with fewer segments. (Recursive
subdivision is very good at producing the minimum needed within a
tolerance.)
Scan converting a PostScript path is after all only one application of
Bézier flattening.
T
>
> <snip>