31. Алгоритм Вейлера Азертона удаления невидимых линий и поверхностей. - p1xelse/CG GitHub Wiki

Внимание! Сначала этот вопрос был рассмотрен, пока не были найдены видеоархивы лекций Курова. Куруш написал ответ на этот вопрос, используя Роджерса и глубины своего сознания. Потом мы посмотрели лекции Курова и перенесли их сюда. Какую версию использовать - решать вам.

Алгоритм – попытка минимизировать количество шагов в алгоритме Варнока путем разбиения окна вдоль границ многоугольника.

1. Предварительная сортировка по глубине (для формирования списка приблизительных приоритетов). если наблюдаем из z=+oo, то первым рассмотрим тот многоугольник, который имеет вершину с максимальной координатой z (ближе всего к нам). Удобно сортировать по Zmax
2. Отсечение по границе ближайшего к наблюдателю многоугольника, называемое сортировкой многоугольников на плоскости, или xy-сортировка (в качестве отсекателя используется копия первого многоугольника из списка приблизельных приоритетов. отсекаться будут все многоугольники в этом списке, включая первый). Используется алгоритм отсечения Вейлера-Азертона. На выходе формируется 2 списка – внутренний (для каждого отсекаемого многоугольника та часть, которая оказывается внутри отсекателя) и внешний (оставшаяся часть)).
3. Удаление мноугольников внутреннего списка, которые экранируются отсекателем (все вершины имеют zmax не больше, чем zmin отсекателя). Если все многоугольники были экранированы - продолжим работу с внешним списком.
4. Если глубина многоугольника из внутреннего списка больше, чем Zmin отсекателя, то такой многоугольник частично экранирует отсекатель. Нужно рекурсивно разделить плоскость, используя многоугольник, нарушивший порядок в качестве отсекателя (нужно использовать копию исходного, а не остаток после предыдущего отсечения). Отсечению подлежат всe многоугольники из внутреннего списка, включая предыдущий отсекатель.
5. По окончанию отсечения или рекурсивного разбиения изображаются многоугольники из внутреннего списка (те, которые остались после удаления всех экранируемых на каждом шаге многоугольников – остаются только отсекающие многоугольники)
6. Работа продолжается с внешним списком (шаги 1-5)

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

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

Этот алгоритм справляется с циклическим прерыванием многоугольников (часть многоугольников лежит позади другого, а часть спереди).

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

Рассмотрим первый случай - самый простой, когда ближайший многоугольник без вопросов экранирует второй многоугольник.

Многоугольник A будет первым в приоритетном списке:

Отсекаем по границам A:

Мы хотим установить факт расположения многоугольника A перед многоугольником B1, то есть быть уверенными в том, что многоугольник B1 ни в коем случае не может закрывать многоугольник A: ZminA > ZmaxB1.

Изображается многоугольник A, так как B1 не может экранировать A, и многоугольник B2 (он один в списке внешних многоугольников)

Случай, когда частично многоугольник B будет экранировать многоугольник A, хотя многоугольник A будет располагаться перед B.

1. Сортировка (A ближе B)

   

2. Отсечение по границам многоугольника A.

   

   Будем считать, что ZmaxB1 > ZminA. Простейшая проверка не позволяет нам убедиться в том, что многоугольник A экранирует многоугольник B1. Есть подозрение, что многоугольник B1 частично экранирует A. В этом случае заново проводим отсечение, но в качестве отсекателя выбираем многоугольник, который нарушает это неравенство, который, возможно, загораживает от наблюдателя ближайший к нему многоугольник.

3. Отсечение по границам многоугольника B

   

   Списка внутренних многоугольников. Для каждой вершины i от 1 до 4 глубина многоугольника B1 больше глубины многоугольника A1: ZiB1 > ZiA1. Изображается многоугольник B1.

   Список внешних многоугольников. A2 и B2 являются внешними по отношению друг к другу многоугольниками. Изображаются A2 и B2.

Циклическое перекрывание многоугольников, когда часть многоугольников лежит позади другого, а часть спереди.

1. Проводим отсечение по границам А:

   

   Поскольку условие ZmaxB > ZmaxA не выполняется. B может "экранировать" A, решить задачу мы еще не можем, а значит выполняем отсечение еще раз.

2. Проводим отсечение по границам B:

   Список внутренних многоугольников:

   

   Здесь сопоставляются глубины многоугольников в вершинах:

   ZijA1 < ZijB1  -> изображается B1
   ZijA2 > ZijB2  -> изображается A2

Список внешних многоугольников:

A3 и B3 внешние – изображаются оба

Если многоугольник пересекают друг друга, то надо разбить один из них на два линей пересечения плоскостей присущих этим многоугольникам.

Алгоритм: