Эффективное удаление скрытой поверхности объекта-пространства

Question

У меня следующая проблема: мне нужно сгенерировать 2d виды 3d модели. При обычных обстоятельствах это, конечно, было бы тривиально: просто выведите все на экран, используя алгоритм художника или подобную технику. К сожалению, вывод должен быть двухмерной геометрией, чтобы его можно было отправлять в пакеты САПР. Это означает, что удаление скрытой поверхности должно выполняться на уровне вектора, а не на уровне пикселей, что делает большинство стандартных методов (алгоритм художника, z-буфер и т. Д.) Непригодными для использования.

Самым распространенным методом, который я обнаружил при удалении скрытой поверхности в объектном пространстве, является использование дерева BSP, которое в теории работает просто отлично. Я реализовал это, но производительность даже не была приемлемой, что неудивительно, учитывая сложность O (n ² ). Тестовая сцена, которую я использую, имеет около 4800 треугольников после отбраковки задней поверхности, но я ожидаю, что алгоритм должен будет обрабатывать сцены примерно в 5 или 10 раз больше этого числа, что быстро становится довольно большим, когда вам нужно выровнять его. (Отсутствие) скорости нашей библиотеки геометрии точно не помогает.

С тех пор я пробовал разные способы решения этой проблемы с производительностью, в основном основанный на идее разделения треугольников на более мелкие группы, чтобы уменьшить влияние O (n ² ), такие как октавы (более половины многоугольников были сохранены в корневом узле) и разделение проецируемой на 2d сцены в сетке 10x10, чтобы уменьшить количество треугольников на квадрат (работает, но уменьшение пересечений полигонов перевешивается необходимостью повторения процесс в 100 раз).

Сегодня у меня был еще один путь - проецировать все треугольники в 2D и посмотреть, какие из них пересекаются, сначала проверив, перекрывают ли ограничивающие квадраты, а затем проверив каждое пересечение ребер (3x3 = 9) для каждой комбинации двух многоугольников. Для пересечения линии я обошел библиотеку геометрии, используя алгоритм, описанный здесь . В общей сложности выполняется около 11,6 миллиона пересечений линий, что занимает около 30 секунд, что все еще слишком долго (я бы сказал, что абсолютное максимальное время выполнения будет около 5 секунд), не говоря уже о том, что это только часть алгоритма.

У меня заканчиваются идеи о том, как решить эту проблему с производительностью, и я надеялся, что у кого-нибудь из вас найдутся хорошие идеи для лучшего алгоритма. Все те, о которых я могу думать, все O (n ² ).

Answer 1

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

Answer 2

Я бы использовал модифицированный алгоритм Брезенхэма, где вы вычисляете для линии все пересеченные пиксели (возможно, этот алгоритм имеет название btw). Полный метод будет тогда:

1. Создание пространственного индекса n x m (с отсортированным списком полигонов на сетку), где n и m достаточно велики (скажем, 1000x1000 ячеек).
2. Для каждого спроецированного многоугольника используйте «модифицированный алгоритм Брезенхэма» выше, чтобы добавить многоугольник ко всем ячейкам, которые он пересекает.
3. Создайте набор пар потенциальных пересечений полигонов, просматривая все пары в каждой ячейке.
4. Выполните правильный реальный тест пересечения, только для потенциальных пар, найденных на предыдущем шаге.

Шаг 3 должен убедиться, что вы максимально сократили количество потенциальных пересечений. Шаг 2 - O (n) и должен быть достаточно быстрым для маленьких полигонов (небольшое количество пересеченных ячеек).

Вы можете даже динамически изменять размер сетки пространственного индекса, просматривая предыдущие результаты и / или эвристику, основываясь на количестве общих полигонов, среднем размере полигонов и т. Д. *