Non-flat non-convex polygons

I’m writing an application that allows user-defined polygons to be inserted into a GL view. These polygons are not necessarily flat, and not necessarily convex, and we want to accommodate as many kinds as we can. The non-flat’s aren’t much of a problem - we just let GL do whatever it wants.

To cope with the non-convex we run the polygons through the GLU tesselation mechanism. However it seems that the tesselation system breaks down for non-flat polygons. Does anyone know of a way round this?