Здравствуйте, ЫфВ, Вы писали:

ЫфВ>Пока что создаем сетку вышеописанным способом, а затем применяем QEM алгоритм упрощения полигнальной сетки. Все еще ожидаются умные предложения =)

Я, к сожалению, не могу прямо ответить на ваш вопрос. Я не эксперт в триангуляции, но думаю, что ваш метод не оптимален. Почему "средняя кривизна"? Видимо нужны экстремумы. У вас же не поверхность 9-го порядка, надеюсь?

С nurbs в комп. графике, например, люди массово работают лет 15, я так думаю.

1. Гуглится кое-что по "nurbs tesselation algorith", например, (subdivision, triangulation). Можно поискать вокруг.
2. Есть опенсорсный 3d-моделер Блендер (blender.org), умеющий nurbs. На sourceforge есть вещи для работы с nurbs и subdiv'ами. Можно поискать опенсорсные nurbs-софты/библиотеки.
3. Ранее были дорогие и немногочисленные библиотеки для работы с nurbs. Сейчас наверняка есть доступные. Это уже в играх используется.
4. что-то есть в OpenGL 1.3.
5. Поищите исходники здесь & здесь.

Может быть ошибаюсь (с nurbs имел дело давно), но не исключено, что вы изобретаете велосипед