4

I am working on a control algorithm to be run on an embedded system. My programming language is C and the system will be pretty tightly constrained in terms of memory and processing power.

I have a few (in the order of about 10) reference points in three dimensional space. These are normally static, but will change once in a while. I would like to fit a spline surface so that it passes though all of these points, and then have a function which for a given input vector (x, z) returns distance y from the plane y = 0.

I think this is a problem that needs to be solved in two parts: 1) some new coefficients will be calculated whenever a reference point changes and 2) the coefficients are plugged into a function which returns y for a given (x, z). (Only 2 needs to happen 'real time'.)

I have researched on the net this a bit but am having a hard time with the math, and a lot of the material is specific to computer graphics. I am not even sure what type of spline I need; NURBS and Catmull-Rom both seem to be relevant. Lastly, regarding the shape of the edges of my spline: As my input vectors are from well bounded sensor readings, I don't really care what the spline does outside of that boundary.

I would be very grateful for some help or pointers to relevant material, and any snippets of pseudo code would be much appreciated.

calamity
  • 41
  • 3
  • Following up my own query with a bit more research: Catmull-Rom is good because it satisfies the requirements that the surface pass through each point and it is computationally light. The problem with it is that control points need to be constrained to a regular grid in the z=0 plane and there can't be any gaps, which is at odds with the requirement that the control points can be anywhere and I am not sure how many there will be. I wonder if there is a way to synthesize a control grid by doing inverse Catmull-Rom on my control points? – calamity Apr 22 '11 at 09:29
  • Have you looked at Bezier surfaces? When you say "distance from plane", do you mean "distance from surface", or "elevation from surface"? Does this paper help? http://www.waset.org/journals/waset/v65/v65-45.pdf – Jay Elston May 12 '11 at 14:48

1 Answers1

1

If you could somehow generate Bézier triangles whenever your reference points change, the smooth surface of those triangles is easy to calculate even with the constrained resources of your microcontroller -- it only requires repeated addition and division by two.

One way to generate Bézier triangles that pass through all your points is to use Delaunay triangulation on your reference points to find a bunch of triangles that cover your surface. Then use the corners of those triangles as the corners of your Bezier triangles, and arbitrary pick control points such that the edge between neighboring triangles is "smooth" (rather than "creased").

One possible way to pick these control points:

For each of the triangle corner points (i.e., each of your original reference points):

  • find all the triangle edges where one end at that corner point
  • find all the points "connected" to that corner point (at the other end of those edges)
  • fit a flat plane that goes through that corner point and least-mean-squares goes "near" the connected points
  • For each edge, pick a point 1/4 (or 1/3 or 1/10 or whatever) away from the given corner point towards the connected corner point. Forget that point after finding the nearest point on the plane to that point. Use the resulting point as one of the control points in the two triangles that border that edge.

That gives all but one of the control points for each Bezier triangle. For the remaining central control point of the Bezier triangle, perhaps simplest to use the geometric average (centroid) of the corner points.

David Cary
  • 5,250
  • 6
  • 53
  • 66