I first came across the concept of SubDivision Surfaces in this excellent article on GamaSutra. After reading it I originally used the suggested Butterfly algorithm. It was really great for creating nice-looking curves and, as its an "interpolating" algo, you can guarantee that all the original vertices are in exactly the same places in the tesselated mesh. Unfortunately, it's not terribly good for creating crease or "sharp" edges (or at east, I don't think it is). So on the search continued. After looking at loop and even n-patches (neither or which gave satisfactory results), I came across the gem described above.
Unfortunately it's an approximating algo, meaning that the original verts may not be in the same spot after tesselation. Aside from that it had everything I wanted. It produces nice curves and handles crease edges and points very nicely. After including "hard" edges myself (edges that remain sharp, not forming a nice curve like the crease edges), I was pretty happy with the result. Here's another example of what it can do (remembering this is all programmer art):
The untesselated object has 29 faces (including triangles, quads and creases) and the tesselated one has 1856. That's after 3 levels of tesselation (each face becomes 4 faces per iteration of tesselation).
Currently I'm working on the scene-editor that allows me to place many of these objects together to create a scene or level. Eventually I'd like to work with an artist to create some nicer textures and low-poly characters. The long-term goal is to use this engine to make a 3d platformer.