How to render a smooth path given a set of data points?

Question

Hi,

I've been puzzling over path rendering for the past couple of days without any real solution.

By path rendering I mean given a set of x,y data points (at varying distance) to draw a dashed line (or in my case a rotated quad) of fixed length at regular intervals between the give data set points to create a smooth path.

If you have flight control for the iPhone I'm trying to create a similar effect to the path rendering in that game.

Here's my problem. If the width of the graphic + the gap is not devisable exactly in to the distance between the 2 dataset points I am then left with an overlap or underlap. My only solution to this is either

1) Take the overlap/underlap point to be the end point of the next data set point and then draw from there to the following point.

2) Always draw under the final endpoint and start a fresh from the next data point.

Neither of these solutions are ideal and both have problems.

Does anyone have a better solution?

Any help would be much appreciated.

The following screen illustrates what I'm trying to create : http://www.firemint.com/flightcontrol/screenshots-peaceful.html

The thick dotted line.

Update:

Hi I tried rendering via curves, I calculated a cubic curve (via 4 control points). However the problem is one of interpolation. Given 0 and 1 I can step through any 2 points. However I want to step through the entire path (multiple control points). The problem is that some control points will be a different distance apart, and thus steping through at a constant stepping increment (say 0.2) will produce irregular results. I realise in order to correctly step through the entire path I'd need to calculate the length of the entire curve ... question is how do I do that? ... or is there another way?

Cheers Rich

Answer 1

Are you completely restricted to fixed-size quads? The ideal solution is to truncate the last quad to the correct size.

If you are restricted, you could do a couple things. If you're drawing dashed lines you can vary the distance of the dashes in order to make sure you never end up with partial quads on the endpoints. This might be visually distracting as the distance would adjust based on the length of the segment.

edit:

Ah, the picture helps. I assume since this is on the iPhone that you're getting a series of points from which drawing lines between them produces an acceptable curve. If this is the case using splines/curve primitives is probably overkill. I would probably approach drawing lines as shown simply by drawing quads at every data point that is a given distance from the last data point.

The algorithm would be something like:

1. Draw quad on the first data point (rotated appropriately)
2. Traverse the point list until you're at least X distance from the last point
3. Lerp between the current point and the last visited point to find the exact center to place the next quad.
4. Draw the quad (rotated appropriately)
5. Go to step 2
6. If you have a partial point for the last quad draw it as normal (this will give a better visual than truncating it).

For fun, to lerp between two points by some distance D that is less than the distance between the two points (this is probably more simple in the 2D case but I like to work generally):

vector v = point2 - point1;
normalize(v);
v *= D;
finalPoint = point1 + v;

Answer 2

You might want to have a look at Bezier curves or hermite curves they are not that hard to calculate and you get nice soft curves.

Answer 3

You should probably check out Bézier curves and Splines algorithms.

Answer 4

There's a CoreGraphics function called "CGPathAddQuadCurveToPoint" that's used for drawing smooth paths. An example on how to use it is on GitHub.