Как просто разбить грань фигуры на полигоны (триангуляция)?

Question

[plxel]

Добрый день. Стоит задача нарисовать трехмерную фигуру (куб, например), используя полигональную модель. Какой есть самый простой способ разбить грань на полигоны (треугольники)? При этом хотелось бы, чтобы число полигонов можно было бы изменять.
Предположу, что после разбиения, необходимо будет иметь доступ к каждому отдельному полигону для раскрашивания, соответственно, надо хранить все координаты полигонов.

Answer 1

[Сергей Протько]

en.wikipedia.org/wiki/Delaunay_triangulation

реализация алгоритма.
triangle.codeplex.com
miconvexhull.codeplex.com

Answer 2

[Ярослав Астафьев]

Почитайте Skiena, Algorithm Design Manual
Там эта тема затрагивается довольно подробно. И проводится сравнительный анализ разных триангуляций

Answer 3

[Станислав Макаров]

Если используете OpenGL, рассмотрите алгоритмы, имеющиеся в библиотеке GLU - там есть достаточно качественный алгоритм тесселяции, поддерживающий сложные поверхности, в том числе с отверстиями. Т.е. вы передаете контуры поверхности: внешний и контуры дырок, алгоритм вам возвращает полигоны для отрисовки. Когда-то мне удалось применить его даже в паре с DirectX, т.к. времени на свою реализацию не было.
Один из многих туториалов: www.glprogramming.com/red/chapter11.html

Comments

[plxel]

спасибо за ответ. Никаких дополнительных библиотек я не использую, реализую полностью с нуля, в целях ознакомления, поэтому нужно просто разобраться как разбить грань на N треугольников..