Компьютерная графика - Алгоритм сканирования линии в 3D (удаление скрытых поверхностей)

Опубликовано: 30 Ноября, 2021

Этот алгоритм основан на методе пространства изображений и концепции когерентности. Как следует из названия, алгоритм Scan-line позволяет обрабатывать по одной строке за раз, а не обрабатывать один пиксель (точку на растровом изображении) за раз. Алгоритм работает следующим образом:

  1. Здесь каждая точка, в которой линия сканирования пересекает поверхности многоугольника, исследуется (обрабатывается) слева направо и в этом процессе.
  2. Расчет глубины (при обнаружении перекрывающихся поверхностей) выполняется для определения скрытой области (видимой поверхности) полигонов, которая находится ближе к плоскости просмотра.
  3. Как только видимые поверхности (скрытые поверхности) идентифицированы, соответствующие значения интенсивности цвета обновляются в буфере обновления (буфер кадра) тогда и только тогда, когда установлен флаг соответствующей поверхности.
  4. Этот алгоритм эффективно работает с одной или несколькими полигональными поверхностями, и этот алгоритм является просто расширением алгоритма сканирования линии для заливки полигонов.

Структура данных, используемая алгоритмом сканирования строки

Алгоритм сканирования строк использует следующую структуру данных:

1. Таблица списка ребер (список): Этот список поддерживает запись всех ребер, сохраняя их координаты конечных точек. Выбранная x-координата, Y-координата которой = Y min.

Рисунок 1

2. Таблица активных ребер (список): Эта таблица содержит все те ребра многоугольника, которые пересекаются (пересекаются) текущей линией сканирования. Края отбрасываются в таблицу в отсортированном порядке (значение x увеличивается).

Рис.2.

3. Таблица многоугольников (список): этот список состоит из:

  • Идентификатор многоугольника.
  • Плоское уравнение.
  • Информация о цвете поверхности.
  • Флаг поверхности (вкл. / Выкл.)].

Давайте поймем больше на примере, показанном ниже на рисунке 4:

Рис.4

Здесь даны два перекрывающихся многоугольника, которые пересекаются тремя линиями развертки S 1 , S 2 , S 3 соответственно. Итак, что произойдет, если применить алгоритм Scan-line для определения скрытой поверхности (видимой поверхности)?

1. Сначала изучите строку сканирования (S 1 ), у которой,

  • Таблица активных границ (Aet) содержит: [AD, BC, RS, PQ] и
  • Флаг установлен в положение «включено» для поверхности (S 1 ) и поверхности (S 2 ), а флаг установлен в положение «выключено» для области между BX и RX, поскольку это внешняя область поверхности многоугольника и не должна проецироваться при просмотре. -port (устройства отображения), сейчас
  • Сбросьте интенсивность цвета соответствующих поверхностей в буфер кадра (буфер обновления).

2. Затем обработайте строку сканирования (S 2 ), у которой,

  • Таблица активных границ (Aet) содержит: [AD, BC, RS, PQ] и
  • Флаг установлен на «включено» для поверхности (ABCD) и поверхности (PQRS),
  • Обе поверхности многоугольников перекрывают друг друга, поэтому для этой области перекрытия, какую из поверхностной интенсивности следует учитывать? Итак, чтобы ответить, это вычисляет глубину (Z min ) как поверхности (S 1 ), так и поверхности (S 2 ). этой перекрывающейся части, затем
  • Если глубина (S 1 )> глубина (S 2 ), тогда флаг поверхности S 1 = «on» и интенсивность поверхности S 1 будет считаться иначе S 2 , теперь
  • Отбросьте интенсивность цвета соответствующих поверхностей, для которых установлен флаг, в буфер кадра (буфер обновления).

3. Как Линия сканирования (S 3 ) проходит через ту же часть, откуда проходит линия сканирования (S 2 ), S 3 также имеет те же компоненты активной краевой таблицы (Aet), что и S 2 , и нет необходимости вычислять глубину (S1) и глубину (S2) снова, так что S 3 может воспользоваться концепцией когерентности.

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

Алгоритм сканирования строки

  • Инициализируйте таблицу Edge со всеми ребрами с соответствующими конечными точками.
  • Инициализировать активную таблицу краев со всеми краями, которые пересекаются текущей строкой развертки в отсортированном порядке (в порядке возрастания x)
  • Инициализируйте таблицу многоугольников с помощью [Идентификатор многоугольника, уравнение плоскости, информация о цвете поверхности, флаг поверхности (вкл. / Выкл.)].
  • Теперь повторите следующие шаги для всех строк развертки:
    • Введите соответствующие значения в список активных кромок в отсортированном порядке, используя координату Y в качестве значения.
    • Отсканируйте многоугольник до тех пор, пока флаг не будет включен, используя и сделайте color_intensity = background color.
    • Когда флаг одного многоугольника = « включен», тогда интенсивность цвета соответствующей поверхности многоугольника (S i) будет вставлена в буфер кадра (буфер обновления).
    • Когда два или более поверхностных полигона перекрываются и их Flag = «on», тогда узнайте глубину соответствующей области поверхностей полигонов и установите Color_intensity = min [глубина (S1), глубина (S2)].
    • Используйте концепцию когерентности для остальных плоскостей.

Вниманию читателя! Не прекращайте учиться сейчас. Ознакомьтесь со всеми важными концепциями теории CS для собеседований по SDE с помощью курса теории CS по доступной для студентов цене и будьте готовы к отрасли.