Non-Convex polygons

I am writing a GIS application that uses OpenGL
to display the data.
The biggest problem I have is tesselating
polygonal data. In the biggest case, I have
a shapefile of more than 200 shapes that
have on average 100 or so points each.

There is no pre-classification of the shapes;
I can’t screen out convex polygons. I
have tried using the “Red-book” method for
doing tesselation – even saving the results in
lits-- but its still slow as molasses.

I need a method that can both display shapes
at “full-extent” (maybe not full res) and
pretty decently at [not full] magnification.

Any help is appreciated

nvtristrip ?