Некоторое время назад я спросил, как определить, когда лицо перекрывает другое. Совет был использовать Z-буфер.
Тем не менее, я не могу использовать Z-буфер в моем текущем проекте, и поэтому я хотел бы использовать алгоритм Painter. Я не имею ни малейшего понятия, когда поверхность находится позади или перед другой, хотя. Я пробовал множество методов, но все они терпят неудачу в крайних случаях, или они терпят неудачу даже в общих случаях.
Это список методов сортировки, которые я пробовал до сих пор:
- Расстояние до середины каждого лица
- Среднее расстояние до каждой вершины каждой грани
- Среднее значение z каждой вершины
- Наивысшее значение z вершин каждой грани и нарисуйте их первыми
- Наименьшее значение z вершин каждой грани и нарисуйте последние
Проблема в том, что лицо может быть ближе, но еще дальше. Все эти методы кажутся ненадежными.
Редактировать: Например, на следующем изображении поверхность с синей точкой в качестве средней точки закрашена поверх поверхности с красной точкой в качестве средней точки, потому что синяя точка ближе. Однако это происходит потому, что поверхность красной точки больше, а средняя точка находится дальше. Поверхность с красной точкой должна быть закрашена поверх голубой, потому что она ближе , а расстояние до средней точки говорит об обратном.
Что именно используется в алгоритме Painter для определения порядка, в котором объекты должны быть нарисованы?
Ответы:
Обычно расстояние средней точки многоугольника от камеры используется для z-сортировки. Алгоритм художника не может быть на 100% точным по своей природе. Всегда будут случаи, когда сортировка не удастся, независимо от того, какую контрольную точку вы используете.
Если вы хотите правильно выполнить z-сортировку с помощью алгоритма рисования, вам придется разрезать перекрывающиеся полигоны на более мелкие части (например, с помощью четырехугольного дерева) и отсортировать эти части по отдельности. Это может стать довольно тяжелым для процессора, хотя ..
Нашел этот файл Powerpoint, который хорошо иллюстрирует проблему ( PDF версия ).
источник
В таких случаях для меня это всегда работало с использованием bsp-деревьев. Разделите сцену, пока у вас не будет выпуклого набора многоугольников в узле bsp-дерева, и тогда вы сможете легко сортировать многоугольники внутри узлов. Обратите внимание, что сортировка полигонов из узла bsp-дерева кажется такой же проблемой, как вы описали выше, но есть условие, не столь очевидное - после построения bsp-дерева все проблемные случаи уже решены - в узле вы должны завершить с набором многоугольников, из которых должен пройти тест на выпуклость - если вы выберете плоскость из одного многоугольника из этого набора, все остальные многоугольники будут либо перед плоскостью, либо позади плоскости. Использование этой информации упрощает сортировку - функтор сортировки принимает 2 многоугольника - проверьте, в каком полупространстве находится 1-й многоугольник против 2-го многоугольника, а также проверьте расположение камеры против второго многоугольника.
Также обратите внимание, что тесты для определения стороны размещения камеры относительно полигонов и обхода bsp-дерева немного отличаются при работе с ортогональной и перспективной проекцией.
Если вы не можете позволить себе разделение входных полигонов, я думаю, вам не повезло.
источник