Я ищу алгоритм или библиотеку (лучше), чтобы разбивать многоугольник на треугольники. Я буду использовать эти треугольники в приложении Direct3D. Каковы наилучшие доступные варианты?
Вот что я нашел до сих пор:
Я был бы очень рад некоторым мнениям людей, имеющих опыт в этой области.
Изменить: это двумерный многоугольник.
Джонатан Шевчук Библиотека треугольников феноменальна; Я использовал его для автоматизации триангуляции в прошлом. Вы можете попросить его попытаться избежать маленьких/узких треугольников и т.д., Поэтому вы придумываете "хорошие" триангуляции вместо любой триангуляции.
Чтобы предоставить вам еще несколько вариантов библиотек:
Polyboolean. Я никогда не пробовал этот, но выглядит многообещающим: http://www.complex-a5.ru/polyboolean/index.html
Общий полигон Clipper. На практике это очень хорошо работает и делает триангуляцию, а также отсечения и отверстия: http://www.cs.man.ac.uk/~toby/alan/software/
Мои личные рекомендации: используйте тесселяцию из GLU (OpenGL Utility Library). Код является твердым, более быстрым, чем GPC, и генерирует меньше треугольников. Вам не нужна инициализированная OpenGL-Handle или что-то подобное, чтобы использовать lib.
Если вам не нравится идея включать системные библиотеки OpenGL в приложение DirectX, также есть решение: просто скачайте код реализации SGI OpenGL и снимите с него триангулятор. Он просто использует имена OpenGL-Typedef и ручку, полную перечислений. Это. Вы можете извлечь код и создать автономную библиотеку через час или два.
В общем, мой совет будет заключаться в том, чтобы использовать что-то, что alreay работает, и не начинайте писать свою собственную триангуляцию.
Возникает соблазн опрокинуться, если вы прочитали об алгоритме обрезки уха или развертки, но факт в том, что алгоритмы вычислительной геометрии невероятно трудно писать так, что они работают стабильно, никогда не сбой и всегда возвращаются значимый результат. Числовые ошибки округления будут накапливаться и убивать вас в конце.
Я написал алгоритм триангуляции в C для компании, с которой я работаю. Получение основного алгоритма работы заняло два дня. Получение работы со всеми видами дегенерированных входных данных заняло еще два года (я не работал на нем полный рабочий день, но, поверьте, я потратил на это больше времени, чем следовало бы).
У CGAL есть необходимый инструмент: Ограниченные триангуляции
Вы можете просто предоставить границы своего многоугольника (включая границы отверстий) в качестве ограничений (лучше всего, чтобы вы вставляли все вершины, а затем указывали ограничения как пары вершинных_handles).
Затем вы можете пометить треугольники триангуляции любым алгоритмом обхода: начать с треугольника, инцидентного бесконечной вершине, и пометить его как находящуюся снаружи, и каждый раз, когда вы пересекаете ограничение, переключитесь на противоположный тег (внутри, если вы ранее отмечали треугольники как аутсайдеры, снаружи, если раньше вы отмечали треугольники как инсайдеры).
Я нашел библиотеку poly2tri именно тем, что мне нужно для триангуляции. Он создает намного более чистую сетку, чем другие библиотеки, которые я пробовал (в том числе libtess), а также поддерживает дыры. Он был преобразован в кучу языков. Лицензия Новая BSD, поэтому вы можете использовать ее в любом проекте.
Вы можете добавить отверстия относительно легко самостоятельно. В основном триангуляция к выпуклой оболочке входных точек в соответствии с CGAL, а затем удалить любой треугольник, стимул которого лежит внутри любого из дырочных многоугольников (или вне любой из внешних границ). При работе с большим количеством отверстий в большом наборе данных методы маскировки могут использоваться для значительного ускорения этого процесса.
edit: общим расширением этого метода является сорняк слабых треугольников на корпусе, где самый длинный край или наименьший внутренний угол превышает заданное значение. Это создаст более вогнутый корпус.
Это общая проблема в анализе конечных элементов. Он называется "автоматическая генерация сетки". Google нашел этот сайт со ссылками на коммерческое и программное обеспечение с открытым исходным кодом. Обычно они предполагают, что начальная геометрия САПР начинается.
попробуйте libtess2
https://code.google.com/p/libtess2/downloads/list
на основе оригинального тезисатора SGI GLU (с либеральным лицензированием). Решает некоторые проблемы с управлением памятью вокруг большого количества небольших mallocs.
Другой вариант (с очень гибкой лицензией) заключается в переносе алгоритма из VTK:
Этот алгоритм работает достаточно хорошо. Использование этого напрямую возможно, но требует ссылок на VTK, у которых может быть больше накладных расходов, чем вы хотите (хотя у него много других приятных функций).
Он поддерживает ограничения (дыры/границы/и т.д.), а также триангулирует поверхность, которая не обязательно находится в плоскости XY. Он также поддерживает некоторые функции, которые я еще не видел в других местах (см. Примечания по значениям Alpha).
Я реализовал трехмерный полигон triangulator на С#, используя метод обрезки уха. Он прост в использовании, поддерживает дыры, численно устойчив и поддерживает произвольные (не самопересекающиеся) выпуклые/невыпуклые многоугольники.