knutm@ifi.uio.no (Knut Moerken) (06/06/90)
In article <1304@chinacat.Unicom.COM>, woody@chinacat.Unicom.COM (Woody Baker @ Eagle Signal) writes: |> |> Yes. Consider any set of control points and end points for a single spline. |> The subdivision method of generating the points that are used to draw the |> spline, basicaly moves the control points closer and closer to the actual |> curve, and creates more and more of them. Eventualy, when you have done |> some arbitrary number of iterations, you can consider that the generated |> points define (for any single point) an endpoint and control point that |> lay on the same physical spot. You then draw a series of straight lines |> between the generated points and bingo, you have a spline. Since you |> are moving the points closer and closer to the final line, it seems to me |> that you could take the final line, divide it up into segments that are |> an even power of 2 or whatever, and then start moving points backward, and |> reducing the number of points until you got back to only 2 end points and |> 2 control points, at which point you should have your original control and |> end points back. |> |> Whew!. |> |> My question, is can the subdivision method be reversed? |> |> Cheers |> Woody |> |> The subdivision process can be reversed. It is not difficult to see that the points generated by the subdivision depends linearly on the original control points, that is if c is the vector with the original control points and d the refined ones then we have (1) d=Ac for a suitable matrix A. If c is an n-vector and d is an m-vector then A is an mxn matrix and in subdivision m>n so A has (many) more rows than columns. The matrix A can be generated by standard algorithms. (For example to compute column no. i of A, just subdivide the spline with c(i)=1 and c(j)=0 if j#i. Once you have the matrix A it is standard linear algebra to get from d to c for example via least squares approximation. This has the nice feature of giving back c if (1) holds exactly (modulo round-off), otherwise it will give an approximation with few coefficients (knots) to a spline with many coefficients (knots). It should be mentioned that it is in fact possible to use the subdivision algorithm directly to find c from d. For those familiar with the Oslo-algorithm: Suppose you use the Oslo algorithm to do the subdivision, i.e., to compute d from a given c. If you interchange the role of the two knot vectors (original and refined) and run the Oslo algorithm again with d as original control points you end up with c!! This has been noticed recently by several authors (Goldman, Lyche, Morken, Strom, Ramshaw) but I don't know of an easily available and understandable reference as of this date. The first four authors above will publish some papers regarding this in a forthcoming book from SIAM. I have talked about splines here although the original posting was about Bezier curves. Since Bezier curves are just a special case of spline curves the same applies. If you consider the case of a single cubic Bezier curve the matrix A only has 4 rows. In the description above it was assumed that the matrix A could be generated, i.e., that both the refined and original knot vectors were known. In general all that is given is a set of points and what is wanted is a spline with few knots that approximates the points well. I hope I can be forgiven for mentioning my own work, but together with Tom Lyche I have published a paper describing an algorithm for doing just this. The problem we consider is: Given a spline f with knot vector t and a tolerance e, find a new (short) knot vector s and an approximation g to f such that the error |f-g| is less than e. The idea is to remove as many knots as possible from f without changing it more than the tolerance e. This algorithm can be used to find an approximation to a set of points. First connect the points with straight lines. The resulting curve is a linear spline with simple knots at the points. Then rewrite this linear spline as a cubic spline by making all interior knots triple. Finally, select a tolerance and remove as many knots as possible from this spline. This is all written up in A data reduction strategy for splines with applications to the approximation of functions and data, by T. Lyche and K. Morken, IMA Journal of Numerical Analysis (1988) 8, pp. 185-208. See also (by the same authors) Knot removal for parametric B-spline curves in CAGD (1987) 4, pp. 217-230. Knut Morken Institutt for informatikk University of Oslo Norway email: knutm@ifi.uio.no