Thought.Log
Copyright (C) 1984 by Xerox Corporation. All rights reserved.
This file is a log of odds and ends of thoughts relating to the simplification of Beta-spline control polygons.
Some random mutterings:
The phenomenon that I am looking for may simply? be the following: finding the control polygon of a spline that has been repeatedly pushed through a low-pass filter. The high frequency changes should smooth out, decreasing local curvature, thus allowing more and more ~collinear control points to be removed. I think this method will give me the "scale-independence" that I want. I hope so. The method is, of course, an inversion of how one usually deals with splines. Didn't Brian say that he looked/solved that problem in his PhD thesis?
Hmmm, I can't find it.
Ahem, cough, let's see now...
Q(u) = V0*b0(u) + V1*b1(u) + V2*b2(u) + V3*b3(u)
or, longer notation:
x(u) = Vx0*b0(u) + Vx1*b1(u) + Vx2*b2(u) + Vx3*b3(u)
y(u) = Vy0*b0(u) + Vy1*b1(u) + Vy2*b2(u) + Vy3*b3(u)
ie., eight unknowns -> four Vx's, four Vy's.
Given the spline or an approximation of it, we know what x(0), y(0), x(1), and y(1) should be. We also know what the basis functions will output at u = 0 and u = 1, because we know what the bias and tension are at those points.
That was easy enough.
What we now need are two more points in 2-space on the spline that will give us a total of eight equations in eight unknowns.
The problem now stands as: How do we choose these next two points? It would be very nice if we never have to look directly at the splines that result from our machinations.
Possibilities:
1. Use u = .33 and u = .67
2. Use uniformily spaced points in geometric space. Approximated by chord length, I suppose.
3. Use some geometric property to determine points chosen. Like curvature. Hmmm....
Suggested algorithm #1:
1. Using a low-pass filter or neighborhood averaging of the control polygon, obtain an approximation of the spline as it will be.
2. From this, obtain an approximation of the curvature at each "control point" by d(angle)/d(chordlength)
3. Build a priority queue according to curvature.
4. Take out a point from previous control polygon according to the priority queue.
5. Using the averaged or filtered control polygon as an approximation of the spline curve, calculate the position of the remaining control points such that the resulting spline "fits" specified points of the filtered control polygon. These specified points are chosen again by degree of curvature or something. See above.
Questions for algorithm #1:
1. Is neighborhood averaging the best type of filter to use? How to deal with the end conditions?
2. If neighborhood averaging is used, what should the neighborhood be?
Possible solutions:
1a. Well, neighborhood averaging is certainly one of the easiest. End conditions (and middle conditions) could be dealt with based on the basis functions, ie. the weights for each control point that is used in a local average should be taken from the Beta-spline basis functions.
1b. On the other hand, since 1a is uncomfortably like taking the actual curve values, we could use simpler functions of the beta values and the parameter u.
2. Wahlll, ah'd say two points, three points or four points. Two points is reeeal simple. Three points can produce some anomalies (when the original control polygon is shaped like VVV, using three points can result in a new control polygon that is topologically a mirror image of the original). Four points addresses the approach proposed in 1a. All of them needs consider special end conditions, especially if we want to produce the same number of points as in the original control polygon.
Extensions and other remarks:
1. A neighborhood of two points might solve the entire problem. Just extend the segments on either end and you've got yourself a pretty darn good approximation of the original spline with one less control point in most cases.
2. It would be nice if subsequent splines were approximately the same arc length as the original spline.
Suggested algorithm #2:
1. Test first for ~collinear points, subject to some error metric.
2. Delete these first.
3. If no collinear points are available, use neighborhood averaging with a neighborhood of two points, extending the endpoints by same direction, to retain length of curve.
4. Go to step 1.
Questions for algorithm #2:
1. How do the new control points inherit the local beta values?
2. It looks pretty good, but it seems we should be able to do better. How? Could quadratic Beta-splines be used for fitting?
3. How to extend length of resulting spline so it is the same as the original? Is the length of the spline invariant with respect to the length of the control polygon?
Possible solutions:
1. Use weighted averages. Currently being used: p = p0 + t(p1 - p0), where t ranges from 0 to 1 and is defined by t = b1/(b0+b1). A problem with this solution is that if either b0 or b1 is zero, then t = 1 or 0, independent of the magnitude of the non-zero b.
Collinearity algorithm and derivation:
1. Given three points p0, p1, p2, where pi = (xi, yi), let x = ||x2 - x0||, y = ||y2 - y0||, a = ||x1 - x0||, b = ||y1 - y0||
2. Define an orthonormal basis (u v) by:
u = (x / ||(x, y)||, y / ||(x, y)||)
= (ux, uy),
v = (-uy, ux)
3. Note:
(ux uy) (u v) = (1 0)
4. And:
(a b) (u v) = (a*ux + b*uy, -a*uy + b*ux)
5. Then ndist = ||-a*uy + b*ux||/||(x, y)||
6. And the perpendicular distance from p1 to p0-p2, pdist = ndist*||(x, y)||.
7. Or, simplified, pdist = ||-a*uy + b*ux||
8. If pdist <= delta, for some chosen delta, then p0, p1, p2 are judged collinear.
Suggested algorithm #3:
1. Test for ~collinear points.
2. If they exist, remove the most collinear.
3. Else, use neighborhood averaging to weaken high frequency changes.
4. Go to step 1.
Questions for algorithm #3:
1. What are the best end conditions for neighborhood averaging? Want to preserve arc length.
2. If we include curvature tests, it seems that the two endpoints of the equi-curvature section should remain the same. What criteria should be used to fix the other control points? Preserve curvature or arclength/height?
Center of Osculating Circle algorithm:
1. Given four adjacent point vectors, p1, p2, p3, p4, let pa = p1-p2, pb = p3-p2, pc = p2-p3, pd = p4-p3 be the four vectors translated to the origin.
2. Let pe = pa + pb = p1 + p3 - 2*p2 and pf = pc + pd = p2 + p4 - 2*p3. If the segments pa and pb, pc and pd are of equal length, then pe should bisect the angle between pa and pb, and pf should bisect the angle between pc and pd.
3. Translate pe and pf back to the original local coordinate system by:
pg = pe + p2 = p1 + p3 - p2
ph = pf + p3 = p2 + p4 - p3
4. The intersection of the lines a = p2 + t*(pg - p2), b = p3 + t*(pg - p3), is the center of the osculating circle.
5. Solve for value of t by:
p2 + t*(pg - p2) = p3 + t*(ph - p3)
Rearranging and solving =>
t = (p2 - p3) / (-p1 + 3*p2 - 3*p3 + p4)
6. The x, y coordinates of the center of the osculating circle can be found by substituting back in for the equation for either a or b:
c.x = p2.x + t*(pg.x - p2.x)
c.y = p2.y + t*(pg.y - p2.y)
Closed Polygon Check algorithm:
1. Given two vectors, a and b, with a common tail on the polygon, let q be the angle between the two.
2. Let a = p - q
3. Then 2p/a = n, the number of vertices needed for a closed regular polygon.
4. If the number of equicurvature control points exceeds n, then the control polygon is starting to spiral.