Алгоритм плавающего горизонта | MetodPro.ru

Реклама на сайте

Алгоритм плавающего горизонта


Алгоритм плавающего горизонта чаще всего используется для удаления невидимых линий трехмерного представления функций, описывающих поверхность в виде: F(x, у, z) = 0

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

Алгоритм обычно работает в пространстве изображения.

Главная идея метода заключается в сведении трехмерной задачи к двумерной путем пересечения исходной поверхности последовательностью параллельных секущих плоскостей, имеющих постоянные значения координат х, у или z.

 

На рисунке 1 приведен пример, где указанные параллельные плоскости определяются постоянными значениями z. Функция F(x, у, z) = 0 сводится к последовательности кривых, лежащих в каждой из этих параллельных плоскостей, например к последовательности функций вида у = f(x, z) где z постоянно на каждой из заданных параллельных плоскостей.

Итак, поверхность теперь складывается из последовательности кривых, лежащих в каждой из этих плоскостей, как показано на рисунке 3. Здесь предполагается, что полученные кривые являются однозначными функциями независимых переменных.

 

 

Если спроецировать полученные кривые на плоскость z=0, как показано на следующем рисунке, то сразу становится ясна идея алгоритма удаления невидимых участков исходной поверхности.

Алгоритм сначала упорядочивает плоскости z = const по возрастанию расстояния до них от точки наблюдения. Затем для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней, т. е. для каждого значения координаты х в пространстве изображения определяется соответствующее значение у.

Алгоритм удаления невидимой линии заключается в следующем:

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

Невидимые участки показаны пунктиром на рисунке 3.

Реализация данного алгоритма достаточно проста. Для хранения максимальных значений у при каждом значении х используется массив, длина которого равна числу различимых точек (разрешению) по оси х в пространстве изображения. Значения, хранящиеся в этом массиве, представляют собой текущие значения “горизонта”. Поэтому по мере рисования каждой очередной кривой этот горизонт “всплывает”. Фактически этот алгоритм удаления невидимых линий работает каждый раз с одной линией.

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

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

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

 

Ньюэл М., Ньюэл Р.и Санча

При реализации всех обсуждавшихся алгоритмов удаления невидимых линий и поверхностей устанавливались приоритеты, т. е. глубины объектов сцены или их расстояния от точки наблюдения. Алгоритмы, использующие список приоритетов, пытаются получить преимущество посредством предварительной сортировки по глубине или приоритету.
Цель такой сортировки состоит в том, чтобы получить окончательный список элементов сцены, упорядоченных по приоритету глубины, основанному на расстоянии от точки наблюдения. Если такой список окончателен, то никакие два элемента не будут взаимно перекрывать друг друга. Тогда можно записать все элементы в буфер кадра поочередно, начиная с элемента, наиболее удаленного от точки наблюдения. Более близкие к наблюдателю элементы будут затирать информацию о более далеких элементах в буфере кадра

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


Рис 1. Установление приоритетов для многоугольников.

Для простой сцены, вроде той, что показана на рис. 1, а, окончательный список приоритетов можно получить непосредственно. Например, эти многоугольники можно упорядочить по их максимальному или минимальному значению координаты z. Однако уже для сцены, показанной на рис.1, b, окончательный список приоритетов по глубине невозможно получить простой сортировкой по z. Если Р и Q с рис. 1, b упорядочены по минимальному значению координаты z (zmin), окажется, что P в списке приоритетов по глубине будет стоять перед Q. Если их записать в буфер кадра в таком порядке, то получится, что Q частично экранирует Р. Однако фактически Р частично экранирует Q. Правильный порядок в списке приоритетов будет тогда, когда Р и Q поменяются местами.

Другие трудности показаны на рис. 2. Здесь многоугольники циклически перекрывают друг друга. На рис. 2, а Р находится впереди Q, который лежит впереди R, который, в свою очередь, находится впереди Р. На рис. 2, b Р экранирует Q, a Q экранирует Р. Аналогичное циклическое экранирование возникает при протыкании многоугольников.

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

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



Методические пособия

  • Системы автоматизированного проектирования
  • Социология молодёжи
  • Общая социология
  • Криптография
  • Проектирование трансляторов
  • Компьютерная графика
  • Моделирование систем
  • Информационная безопасность
  • Теория вычислительных процессов
  • Логические основы искусственного интелекта
  • Проектирование распределённых информационных систем