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

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

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

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

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

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

Рисунок 1

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

Рис.2.

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

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

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

Рис.4

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

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

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

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

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

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

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

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

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

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