Optimal polyline approx of a cubic bezier?
Fernando Cacciola
I suppose that the optimal polyline approximation (less deviation and
minimum number of segments) of a cubic bezier is one which uses the curve
curvature to decide subdivision points.
I guess the right algorithm for this would be to test the curve flatness,
and if it is not flat enough, find the parameter of maximum curvature,
subdivide and recurse.
But I have two questions:
1) What is a good flatness test? Would the difference between the control
polygon length and the chord length suffice? Or do I better averge squared
distances betwen P1,P2 and the chord P0->P3?
2) How do I efficiently find the parameter of maximum curvature?
TIA
Fernando Cacciola
Richard J Kinch
> 1) What is a good flatness test?
Distance of midpoint from midway between enpoints.
Just d' FAQs
<fernando...@hotmail.com> wrote:
>1) What is a good flatness test? Would the difference between the control
>polygon length and the chord length suffice? Or do I better averge squared
>distances betwen P1,P2 and the chord P0->P3?
If the controls exactly give a uniform line segment, P1* = (2P0+P3)/3,
and P2* = (P0+2P3)/3. Measure those two deviations with a cheap metric
like max or summed absolute coordinate distance: |x-x*|+|y-y*|. Hard
to fool this one, yet it costs less than your proposals.
>2) How do I efficiently find the parameter of maximum curvature?
If you want to do it exactly, you'll need a little calculus, a little
Bezier theory, and a little zero-finding.
The standard equation for curvature is given by equation (10) here:
<http://mathworld.wolfram.com/Curvature.html>
Take its derivative and equate to zero to find extrema (max, min, or
inflection). Check its second derivative to verify a maximum.
As for the Bezier theory, we know that the first derivative is given
by the curve whose control vectors are differences of adjacent control
points, times the degree. By induction we can find a derivative of any
order. Of course the third derivatives of a cubic are constant.
However, this forces us to find the zeros of a non-polynomial, and not
a pretty one either. If we are willing to ignore fluctuations in arc
length, we can approximate and simplify somewhat.
We rarely find it worthwhile to work this hard for an approximating
polyline. More commonly we just split at the parametric midpoint.
Fernando Cacciola
"Just d' FAQs" <nobod...@mac.com> escribió en el mensaje
news:ilggg0t88cijk8j8e...@4ax.com...
> On Wed, 28 Jul 2004 15:53:42 -0300, "Fernando Cacciola"
> <fernando...@hotmail.com> wrote:
> >1) What is a good flatness test? Would the difference between the control
> >polygon length and the chord length suffice? Or do I better averge
squared
> >distances betwen P1,P2 and the chord P0->P3?
>
> If the controls exactly give a uniform line segment, P1* = (2P0+P3)/3,
> and P2* = (P0+2P3)/3. Measure those two deviations with a cheap metric
> like max or summed absolute coordinate distance: |x-x*|+|y-y*|. Hard
> to fool this one, yet it costs less than your proposals.
>
> >2) How do I efficiently find the parameter of maximum curvature?
>
> If you want to do it exactly, you'll need a little calculus, a little
> Bezier theory, and a little zero-finding.
>
> The standard equation for curvature is given by equation (10) here:
>
> <http://mathworld.wolfram.com/Curvature.html>
>
Txs
> Take its derivative and equate to zero to find extrema (max, min, or
> inflection). Check its second derivative to verify a maximum.
>
> As for the Bezier theory, we know that the first derivative is given
> by the curve whose control vectors are differences of adjacent control
> points, times the degree. By induction we can find a derivative of any
> order. Of course the third derivatives of a cubic are constant.
>
OK
> However, this forces us to find the zeros of a non-polynomial, and not
> a pretty one either. If we are willing to ignore fluctuations in arc
> length, we can approximate and simplify somewhat.
>
Oh, I see
> We rarely find it worthwhile to work this hard for an approximating
> polyline. More commonly we just split at the parametric midpoint.
>
Ha, yes , I've seen this all the time..
The reason I wanted the 'optimal' subdivision is that I need to operate with
the curve, not just render it.
Specifically, I need the usual geometric queries (distance, intersections,
bbox)
But also I need arc-length parametrization because the framework needs to
deal with all sorts of lineal components with the same interface. To speed
things up, I need a polyline but also a lookup table relating arc-length and
polynomial parameters for fast conversion between the two forms.
I figured that an optimal approximation would take much more time upon
construction but it will make geometric queries more efficient afterwards,
and I also figured that queries against a fixed figure are much much more
frequent than construction and modification.
I'm also assuming that the gain in decreased number of segments (w.r.t to a
midpoint subdivision) will woth it... maybe I'm wrong here though....
Thanks
Fernando Cacciola
Fernando Cacciola
arc-length<->polynomial parameter mapping.
I was thinking about maintaining a lookup table to correlate the arc-length
parameter L of each polyline vertex with the correspoding bezier polynomial
parameter T.
L->T mapping would consist of a lookup for a segment i
such that L(i) < L < L(i+1)
followed by some interpolation along T(i)->T(i+1)
based on the ratio U = L / ( L(i+1)-L(i) )
Given
T = some_ipol(T(i),T(i+1),U)
being the polynomial parameter mapped from L
and
Segment[i](U) denoting the point along the segment i given by lineal
interpolation
the polyline approximation should be such that
{A} |Bezier(T) - Segment[i](U| < thres
were thres is some known value.
Suppose I resort to midpoint subdivision instead of curvature-based
subdivision...
do you think that linear interpolation (for approximating the T once the
segment is found) will be good enough?
By good enough I mean that the error will be bounded by some value directly
defined by the parameters of the flatness test
In other words, can I use midpoint subdivision and just adjust the flatness
test so as to satisfy (A)
TIA
Fernando Cacciola
SciSoft
Just d' FAQs
<fernando...@hotmail.com> wrote:
>In other words, can I use midpoint subdivision and just adjust the flatness
>test so as to satisfy (A)
Recall that the flatness test in my post will subdivide unless the
segment is a truly a good approximation to a uniform line segment. So,
yes, that should satisfy your needs.
Also note that even if you split at maximum curvature, that is still
only a heuristic to minimize pieces, and might make little -- if any
-- difference. And it can do badly if you need arc length, because a
segment can be straight without being arc length parameterized.
Another option is to first use binary subdivision, then merge segments
if together they are flat enough. Since arc length is of interest, we
should test flatness here by deviation of the center point from the
center of the end-to-end segment. As before, this ensures, not just a
line segment, but a *uniform* line segment.
Optimization is context-dependent, so if time and resources permit, go
ahead and try all methods before choosing a final solution.
Luiz Henrique de Figueiredo
See
M. Walter and A. Fournier
"Approximate Arc Length Parametrization"
Proceedings of SIBGRAPI'96, 143-150
http://www.visgraf.impa.br/sibgrapi96/trabs/abst/a14.html
http://www.visgraf.impa.br/sibgrapi96/trabs/pdf/a14.pdf
ftp://ftp.impa.br/pub/visgraf/sibgrapi96/trabs/a14.ps.gz
L. H. de Figueiredo
"Adaptive sampling of parametric curves"
in A. Paeth (ed.), Graphics Gems V, Academic Press, 1995, 173-178
ftp://ftp.icad.puc-rio.br/pub/lhf/doc/g5011.ps.gz
B. Guenter and R. Parent.
"Computing the arc length of parametric curves"
IEEE Computer Graphics and Applications, 10(3):72--78, May 1990.
Fernando Cacciola
> On Thu, 29 Jul 2004 16:23:20 -0300, "Fernando Cacciola"
> <fernando...@hotmail.com> wrote:
> >In other words, can I use midpoint subdivision and just adjust the
flatness
> >test so as to satisfy (A)
>
> Recall that the flatness test in my post will subdivide unless the
> segment is a truly a good approximation to a uniform line segment.
Yes, I noticed that... is like a speed-based rather than just geometric
flatness test.
> So, yes, that should satisfy your needs.
>
> Also note that even if you split at maximum curvature, that is still
> only a heuristic to minimize pieces, and might make little -- if any
> -- difference. And it can do badly if you need arc length, because a
> segment can be straight without being arc length parameterized.
>
Good point.
> Another option is to first use binary subdivision, then merge segments
> if together they are flat enough. Since arc length is of interest, we
> should test flatness here by deviation of the center point from the
> center of the end-to-end segment. As before, this ensures, not just a
> line segment, but a *uniform* line segment.
>
OK
> Optimization is context-dependent, so if time and resources permit, go
> ahead and try all methods before choosing a final solution.
>
Good idea!
Thanks,
Fernando Cacciola
Fernando Cacciola
"Luiz Henrique de Figueiredo" <l...@csgpwr1.uwaterloo.ca> escribió en el
mensaje news:cedd79$brm$1...@rumours.uwaterloo.ca...
Fernando Cacciola
SciSoft