Например, твой GPU умеет рисовать только треугольники...

что дальше с этим хозяйством делать?

Рисовать

Для чего оно применяется?

GPU умеет только треугольники рисовать.

Рисовать

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

Да, это, я имел ввиду триангуляцию, не на уровне железа, а на прикладном уровне )

Тебе это не нужно.

Если ты хочешь закрасить полигон, то для треугольника расчёты гораздо проще.

++

// а еще я не понял, зачем ТС хочет военно-испытательный полигон триангулировать: геодезией занялся что ли?

через 3 точки можно провести плоскость - факт. через 4 - не факт.

Для чего оно применяется?

Триангуляция Делоне и её применение

Да, кстати, как раз закрасить полигон мне и нужно. Так же в полигоне может быть несколько «дыр». К тому же закрашивать нужно не только сплошным цветом, но и паттерном. Но разве для заливки полигона не применяют специальные алгоритмы(типа построчного или с затравкой?)

Кстати,

а ты что: нашел нормальную библиотеку триангуляции Делоне? Ато libqhull — какой-то ад!

Что ты называешь "полигоном"? Многоугольник что ли?

Если он с дырками, ты его без триангуляции не зальешь, да.

Нет, я нашёл только алгоритм ))) у меня сейчас задача «обработать» полигон. На первом этапе пока нужно сделать заливку. Ну и копаясь по форумам и статьям, увидел, что много где упоминается это слово «триангуляция». Погуглил, оказывается это разбиение полигона на треугольники, но непонятно стало, зачем?. Одно дело, если он применяется на уровне железа(раз GPU может только в треугольниках рисовать, мол проще и всё такое), но на прикладном уровне зачем её использовать? Вот и хотел выяснить )

Вот, услышал одно применение - заливка полигона, уже понятней :)

Про другое — отрисовка поверхности трехмерной фигуры — тебе уже говорили. Т.е., скажем, есть у тебя набор точек, принадлежащих "кривой" поверхности и ты ее хочешь отрисовать. Если у тебя равномерная координатная сетка, проблем нет (я такой алгоритм в своей fitsview реализовал): проходишься туда-сюда, рисуя в нечетных проходах треугольники (TRIANLE_STRIP) по часовой, а в четных — против часовой стрелки. Если у тебя N точек по вертикали, то нужно будет сделать всего (N-1) проходов. А вот если точки неравномерно расположены, то тут уже жопа: или интерполируй на равномерную сетку (но тут все равно придется триангулировать, если только не пользуешься интерполяцией ортонормированными полиномами), или сразу триангулируй и отстраивай треугольниками.

Для построчной закраски треугольника очень просто посчитать правую и левую границу строки, а для более сложной формы нужно что-то более хитрое.

Т.е по сути чтобы залить полигон с «дырами» нужно: 1. Триангулировать этот полигон, т.е разбить его на треугольники 2. В цикле перебрать эти треугольники и залить каждый так?

Может быть можно и по другому, но так точно можно.

нашел нормальную библиотеку триангуляции Делоне?

Вроде в gwyddion есть алгоритм: http://gwyddion.net/documentation/libgwyprocess/GwyTriangulation.php

Смотря как выглядит твоя процедура заливки. Если у тебя плоская bitmap-фигура с фиксированным размером пикселя, то ты просто обрисовываешь ее края, а потом при помощи несложного алгоритма заливки "закрашиваешь" внутренности.

Надо будет посмотреть, как вернусь к задачам триангуляции. Мне просто не нравится, что подавляющее большинство библиотек писаны на C++, поэтому с ними работать невозможно. Ну или на крайняк приходится писать обертку. Геморно.

Gwyddion в третьей/четвёртой версии переходит на единые либы libgwy/libgwyui и стандартный для третьего GTK набор биндингов.

Да, у меня просто 2D полигон, представленный списком вершин. Также в нём есть список «дыр», который представляет из себя список тех же самых полигонов. И вот такую фигурку мне надо залить, причём двумя способами - сплошным цветом и паттерном(в клеточку) :)

Ну и красьте себе построчно на здоровье, не лезте в эти дебри.

GPU умеет рисовать только треугольники. Соединение N (> 3) точек в плоскую фигуру может быть неоднозначным. Да и фигура может получиться неплоской.

На прикладном уровне в трехмерном пространстве по множеству точек ты не получишь многоугольник, так как точки не будут лежать на плоскости.

а еще я не понял, зачем ТС хочет военно-испытательный полигон триангулировать

Трансклюкировать

Странный вопрос, учитывая что треугольник это наипростейшная фигура в 3D, из которой можно создавать любые объёмые объекты. Проще же аппаратно реализовать быструю работу с универсальным треугольником чем что-либо иное.

простейший случай поверхности - треугольник, вот разные сложные поверхности и сводят к ним.

это как растровые изображения разбиваются на пикселы, чтобы с ними можно было работать.

например есть набор точек на плоскости, для каждой известна высота. чтобы из этого облака точек построить модель поверхности, надо произвести триангуляцию и каждый треугольник представить как 3мерную грань получившейся 3мерной фигуры - модели поверхности.

Большинство алгоритмов заливки рассчитано на выпуклые многоугольники. Треугольники всегда выпуклые.

лолшто http://www.gamedev.ru/code/forum/?id=182831

Это тоже моё, решил параллельно другой источник попытать :)

а ты что: нашел нормальную библиотеку триангуляции Делоне? Ато libqhull — какой-то ад!

Например тут http://mathgl.sourceforge.net/doc_ru/Global-functions.html#triangulation

MathGL-то к чему? Это же библиотека для построения всяких графиков. А не библиотека для вычислений!

MathGL-то к чему? Это же библиотека для построения всяких графиков. А не библиотека для вычислений!

Вычисления там тоже есть. В частности, есть и триангуляция.

При решении дифф. уравнений еще используется. В геодезии. В общем везде, где нужно аппроксимировать какие-то поверхности.