parallel contour interpolation

I have several x y contours that each have an associated z coordinate. (Thus the xy contours are all parallel.) These contours are made from the edge of an internal slice at the specified z-coordinate of the 3-D polygon I want to render, which could be concave and the contours can have any number of points in them.

A web search has revealed that I might need to “join” two adjacent contours by a sequence of triangle strips, to create a “ribbon” between two contours. Key words are interpolation and triangulation.

How ever since the number of points in one contour does not have to be the same as the number of points in the other contour, the algorithm isn’t as simple as just making a triangle strip (since I may be left with extra points on one of the contours). Does anyone have any idea where I can find an algorithm for this problem?


Here’s a simple algorithm:

  1. Given contours A and B where |A| <= |B| (i e A has fewer or equal number verts to B). |Vector| means length of Vector. |Array| means cardinality (element count) of Array.

  2. Find the two verts Va and Vb where Va is on A and Vb is on B and there are no other verts Va’ and Vb’ such that |Va’ - Vb’| < |Va - Vb|. I e, the two closest verts between the two contours.

  3. Generate a new VertArray A’ such that |A’| = |B|, containing empty verts.

  4. Define the inverse upsampling factor k such that k = |A|/|B|.

  5. For each vertex index i in A, set A’[i] to A[floor(i*k)] – i e, do a zeroth-order interpolation “upsampling” from A to A’.

  6. Generate ribbon between A’ and B because they now have the same number of verts.

Extensions may include calculating the circumference of each of the outlines and choose next vertex value based on distance from start point along circumference in percentage of total, which would compensate for uneven distributions of sample points.