Как получить точные результаты с помощью алгоритма Пейнтера?

14

Некоторое время назад я спросил, как определить, когда лицо перекрывает другое. Совет был использовать Z-буфер.

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

Это список методов сортировки, которые я пробовал до сих пор:

  • Расстояние до середины каждого лица
  • Среднее расстояние до каждой вершины каждой грани
  • Среднее значение z каждой вершины
  • Наивысшее значение z вершин каждой грани и нарисуйте их первыми
  • Наименьшее значение z вершин каждой грани и нарисуйте последние

Проблема в том, что лицо может быть ближе, но еще дальше. Все эти методы кажутся ненадежными.

Редактировать: Например, на следующем изображении поверхность с синей точкой в ​​качестве средней точки закрашена поверх поверхности с красной точкой в ​​качестве средней точки, потому что синяя точка ближе. Однако это происходит потому, что поверхность красной точки больше, а средняя точка находится дальше. Поверхность с красной точкой должна быть закрашена поверх голубой, потому что она ближе , а расстояние до средней точки говорит об обратном.

введите описание изображения здесь

Что именно используется в алгоритме Painter для определения порядка, в котором объекты должны быть нарисованы?

pimvdb
источник
1
Алгоритм живописцы просто рисунок с задом наперед.
Джонатан Коннелл
1
@ 3nixios: Да, очевидно, но каким образом я могу определить порядок «назад к фронту»?
pimvdb
1
Все ваши объекты, треугольники или вершины будут на определенном расстоянии от камеры, когда вы начнете рисовать. Реализация основного алгоритма (у вас получилось?) Состояла бы в том, чтобы определить это расстояние от камеры для каждого треугольника и нарисовать их в порядке, наиболее удаленном от ближайшего. Как только это будет сделано, вам нужно начать искать пересечения и разрезать ваши треугольники, а это совершенно другая игра с мячом . Почему вы уже не можете использовать Z-Buffer? : P
Джонатан Коннелл
@ 3nixios: Вы совершенно правы, но проблема, с которой я сталкиваюсь, заключается в расчете расстояния. Как я уже говорил, я пробовал несколько дистанционных методов, но все они не идеальны. Этот порядок является результатом сортировки по средней точке: i.imgur.com/AcfCm.png .
pimvdb
1
Все ли ваши полигоны на регулярной сетке такие? Если это так, то могут быть конкретные вещи, которые вы можете сделать, чтобы улучшить это.
CiscoIPPhone

Ответы:

14

Обычно расстояние средней точки многоугольника от камеры используется для z-сортировки. Алгоритм художника не может быть на 100% точным по своей природе. Всегда будут случаи, когда сортировка не удастся, независимо от того, какую контрольную точку вы используете.

Если вы хотите правильно выполнить z-сортировку с помощью алгоритма рисования, вам придется разрезать перекрывающиеся полигоны на более мелкие части (например, с помощью четырехугольного дерева) и отсортировать эти части по отдельности. Это может стать довольно тяжелым для процессора, хотя ..

Нашел этот файл Powerpoint, который хорошо иллюстрирует проблему ( PDF версия ).

bummzack
источник
Спасибо за это Powerpoint, он помог мне решить проблему.
pimvdb
Ссылка не работает. Кто-нибудь может найти копию?
Кивон
1
@Keavon Отредактировано. Я нашел рабочую ссылку для файла.
bummzack
1

В таких случаях для меня это всегда работало с использованием bsp-деревьев. Разделите сцену, пока у вас не будет выпуклого набора многоугольников в узле bsp-дерева, и тогда вы сможете легко сортировать многоугольники внутри узлов. Обратите внимание, что сортировка полигонов из узла bsp-дерева кажется такой же проблемой, как вы описали выше, но есть условие, не столь очевидное - после построения bsp-дерева все проблемные случаи уже решены - в узле вы должны завершить с набором многоугольников, из которых должен пройти тест на выпуклость - если вы выберете плоскость из одного многоугольника из этого набора, все остальные многоугольники будут либо перед плоскостью, либо позади плоскости. Использование этой информации упрощает сортировку - функтор сортировки принимает 2 многоугольника - проверьте, в каком полупространстве находится 1-й многоугольник против 2-го многоугольника, а также проверьте расположение камеры против второго многоугольника.

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

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

bishopnator
источник