I would like to triangulate between two sets of polygons. One set is always inside the other, in fact, the outer polygons are created as offsets from the original set. Triangulation would be easy if they were on the same plane, but I would like to add depth by moving the outer polygon to a parallel but different plane. The usual method for triangulation that I use (glu tesselator) does not work. Is there an alternative that would?
You are saying that you have a triangulation method that works in 2D. Fine. Put both of your contours on the same plane z = 0, do the 2D triangulation, then set z coordinate of the vertices of the outer contour to the value you need. As you said, move the outer contour to the parallel plane.
Why this approach doesn't suit you?
Yes, you may end up with some horizontal triangles, which have all three vertices with the same z coordinate. If you used a "true" 3D triangulation you also may end up with same horizontal triangles. It all depends on the shape of the contour and algorithm.
If it is not acceptable to have such horizontal triangles you can add a second pass to try to eliminate them:
Find a horizontal triangle. Two of its edges would belong to either original inner or original outer contour. The third edge would "short-circuit" the vertices of the original contour. Find another triangle that has the same edge as the "third" edge described above. The pair of these triangles form a rhombus. There are only two ways to triangulate the rhombus. The one that you've got is not acceptable, so just re-triangulate the rhombus in a different way.
It is hard to explain this without drawings.