Как отсортировать эти строки с помощью алгоритма художников?

Question

Скажите, что мне дан следующий график, и я нахожусь на eye1 .

Используя алгоритм художников, мы рисуем от задней части к передней. Поэтому, если бы мне пришлось сортировать следующие линии с помощью алгоритма рисования (например, от первого нарисованного до последнего), я бы подумал, что это C, A, E, D, B. То, что мы спотыкаемся, это нормальная поверхность для линий D иB. Так как нормаль B направлена ​​в сторону от eye1, а D - нет, значит ли это, что мы рисуем B перед D?
Спасибо всем!

Answer 1

Если выбрано заднее лицо (т.е. известно, что поверхность закрыта), вы вообще не рисуете B.

В противном случае направление нормали не играет роли.

Answer 2

Как отметил @ Ив-Дауст, если выбрано заднее лицо, вы, вероятно, можете отказаться от "B", но, учитывая, что в вашем примере нет замкнутой геометрии, мы предположим, что она должна быть нарисована.

Кроме того: Кстати, вы знали, что на SE есть сайт Computer Graphics , который обслуживает подобные вопросы?

Прошло уже несколько (кашель) десятилетий с тех пор, как я изучал это, но если вы собираетесь использовать алгоритм Ньюэлла, Ньюэлла и Санчи для выполнения упорядочивания для художников, тогда вы начнете с начальным списком объектов, отсортированных по дальности до максимума по максимальной глубине, то есть [C, A, E, D, B], но этот список будет нуждаться в переупорядочении.

Newell, Newell & Sancha работают как два эффекта, изменяющих список. Он начинается с установки 'P' во внешнем цикле как самого дальнего элемента в списке и затем шагов Q во внутреннем цикле через каждый из ближайших объектов, чтобы убедиться, что " P не скрывает Q». Он также поддерживает флаг «перемещен» для каждого объекта, чтобы справиться с хитрыми случаями.

Тест * P не скрывает Q , состоит из набора постепенно более дорогих под-тестов:

1. Если P & Q вообще не перекрываются в Z, P не затеняет Q. (Обратите внимание, что поскольку список должен быть отсортирован, вам не нужно проверять более поздние объекты)
2. Тест ограничивающего прямоугольника на экранном пространстве X & Y. Если нет перекрытия, P не может скрыть Q.
3. Плоская проверка P против Q (и это то, где приходит нормаль). Если все вершины P лежат позади плоскости Q, это не может скрыть. По сути, это набор вычислений точечных произведений.
4. Аналогично, если все вершины Q лежат в перед плоскости P, это не может затенить.
5. Сделайте полный тест P против Q, экран XY перекрытия. Это немного дорого, но если вы знаете, что есть общие ребра и т. Д., Вы можете сделать несколько коротких путей. В противном случае вам может понадобиться использовать алгоритм разделения плоскости / линии. Если перекрытия нет, P не может скрыть Q.

Если P не скрывает (все) Qs, вы можете нарисовать P и перейти к следующему пункту и перезапустить процесс.

Если OTOH, P скрывает Q, его необходимо переместить на после Q в списке. Вы также отмечаете, что оно было перемещено. Вы начинаете снова с (нового) «самого дальнего» элемента.

В вашем примере D & B в конечном итоге меняются местами.

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