31. Алгоритм Вейлера Азертона удаления невидимых линий и поверхностей. - chrislvt/CG GitHub Wiki
Внимание! Сначала этот вопрос был рассмотрен, пока не были найдены видеоархивы лекций Курова. Куруш написал ответ на этот вопрос, используя Роджерса и глубины своего сознания. Потом мы посмотрели лекции Курова и перенесли их сюда. Какую версию использовать - решать вам.
Алгоритм – попытка минимизировать количество шагов в алгоритме Варнока путем разбиения окна вдоль границ многоугольника.
- Предварительная сортировка по глубине (для формирования списка приблизительных приоритетов). если наблюдаем из z=+oo, то первым рассмотрим тот многоугольник, который имеет вершину с максимальной координатой z (ближе всего к нам). Удобно сортировать по Zmax
- Отсечение по границе ближайшего к наблюдателю многоугольника, называемое сортировкой многоугольников на плоскости, или xy-сортировка (в качестве отсекателя используется копия первого многоугольника из списка приблизельных приоритетов. отсекаться будут все многоугольники в этом списке, включая первый). Используется алгоритм отсечения Вейлера-Азертона. На выходе формируется 2 списка – внутренний (для каждого отсекаемого многоугольника та часть, которая оказывается внутри отсекателя) и внешний (оставшаяся часть)).
- Удаление мноугольников внутреннего списка, которые экранируются отсекателем (все вершины имеют zmax не больше, чем zmin отсекателя). Если все многоугольники были экранированы - продолжим работу с внешним списком.
- Если глубина многоугольника из внутреннего списка больше, чем Zmin отсекателя, то такой многоугольник частично экранирует отсекатель. Нужно рекурсивно разделить плоскость, используя многоугольник, нарушивший порядок в качестве отсекателя (нужно использовать копию исходного, а не остаток после предыдущего отсечения). Отсечению подлежат всe многоугольники из внутреннего списка, включая предыдущий отсекатель.
- По окончанию отсечения или рекурсивного разбиения изображаются многоугольники из внутреннего списка (те, которые остались после удаления всех экранируемых на каждом шаге многоугольников – остаются только отсекающие многоугольники)
- Работа продолжается с внешним списком (шаги 1-5)
Примечание. Если многоугольник циклически перекрывается с отсекающим (лежит как спереди, так и сзади него), нет необходимости в рекурсивном разбиении, т.к. все лишнее уже было удалено прежде. для избежания таких циклов храним список многоугольников, по которым мы уже отсекали. если при запросе отсечения по многоугольнику мы нашли его в списке - был найден циклически перекрывающийся многоугольник и разбивать ничего не надо.
Алгоритм решения задачи удаления целиком базируется на алгоритме отсечения тех же авторов. Работа будет вестись с проекциями многоугольников. Алгоритм отсечения позволяет найти как внутренние, так и внешние отсечения, что важно.
Этот алгоритм справляется с циклическим прерыванием многоугольников (часть многоугольников лежит позади другого, а часть спереди).
Если многоугольники протыкаются, то придется один из многоугольников разбить на два линией пересечения этих многоугольников.
Рассмотрим первый случай - самый простой, когда ближайший многоугольник без вопросов экранирует второй многоугольник.
Многоугольник A будет первым в приоритетном списке:
Отсекаем по границам A:
Мы хотим установить факт расположения многоугольника A перед многоугольником B1, то есть быть уверенными в том, что многоугольник B1 ни в коем случае не может закрывать многоугольник A: ZminA > ZmaxB1.
Изображается многоугольник A, так как B1 не может экранировать A, и многоугольник B2 (он один в списке внешних многоугольников)
Случай, когда частично многоугольник B будет экранировать многоугольник A, хотя многоугольник A будет располагаться перед B.
-
Сортировка (A ближе B)
-
Отсечение по границам многоугольника A.
Будем считать, что ZmaxB1 > ZminA. Простейшая проверка не позволяет нам убедиться в том, что многоугольник A экранирует многоугольник B1. Есть подозрение, что многоугольник B1 частично экранирует A. В этом случае заново проводим отсечение, но в качестве отсекателя выбираем многоугольник, который нарушает это неравенство, который, возможно, загораживает от наблюдателя ближайший к нему многоугольник.
-
Отсечение по границам многоугольника B
Списка внутренних многоугольников. Для каждой вершины i от 1 до 4 глубина многоугольника B1 больше глубины многоугольника A1: ZiB1 > ZiA1. Изображается многоугольник B1.
Список внешних многоугольников. A2 и B2 являются внешними по отношению друг к другу многоугольниками. Изображаются A2 и B2.
Циклическое перекрывание многоугольников, когда часть многоугольников лежит позади другого, а часть спереди.
-
Проводим отсечение по границам А:
Поскольку условие ZmaxB > ZmaxA не выполняется. B может "экранировать" A, решить задачу мы еще не можем, а значит выполняем отсечение еще раз.
-
Проводим отсечение по границам B:
Список внутренних многоугольников:
Здесь сопоставляются глубины многоугольников в вершинах:
ZijA1 < ZijB1 -> изображается B1
ZijA2 > ZijB2 -> изображается A2
Список внешних многоугольников:
A3 и B3 внешние – изображаются оба
Если многоугольник пересекают друг друга, то надо разбить один из них на два линей пересечения плоскостей присущих этим многоугольникам.
Алгоритм: