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

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

Алгоритм разделения области основан на методе «разделяй и властвуй», при котором видимая (просматриваемая) область последовательно разделяется на меньшие и меньшие прямоугольники, пока не будет обнаружена упрощенная область. Рассмотрим приведенную ниже панель с окном, на которую будет проецироваться многоугольник:

Рисунок 1

Когда мы разделяем оконную панель на многоугольник, мы можем столкнуться со следующими случаями:

1. Окружающая поверхность: Это случай, когда поверхность смотрового полигона полностью окружает всю панель окна.

Рис.2.

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

3. Внутренняя (замкнутая) поверхность: В этом случае вся поверхность многоугольника вписана в оконную панель. Этот случай прямо противоположен первому (окружающая поверхность) случаю.

Рис.4

4. Внешняя (непересекающаяся) поверхность : В этом случае вся поверхность многоугольника полностью находится за оконной панелью.

Рис.5

Алгоритм:

1. Инициализируйте размер области просмотра или панели окна.
2. Включите все многоугольники и отсортируйте их по Z _min (значение глубины) относительно панели окна (порт просмотра).
3. Классифицируйте все многоугольники в соответствии с их случаями падения.
4. Теперь выполните тест обнаружения видимой поверхности (удаление скрытой поверхности):
   • Если у нас есть многоугольник, который полностью окружает панель окна, установите цвет области просмотра на соответствующий цвет многоугольника, который хранится в буфере кадра.
   • Если включенные в список многоугольники не пересекаются или полностью выходят за пределы панели окна, тогда в этом случае будет выбран цвет фона плоскости окна, а многоугольники будут проигнорированы.
   • Если многоугольник (-ы) содержится (вписаны) в оконную панель полностью, то раскрасьте многоугольник из соответствующего цвета, а остальную поверхность раскрасьте цветом фона.
   • Если многоугольник (-ы) и поверхности оконных панелей пересекаются (накладываются друг на друга), то необходимо учитывать следующие случаи:
     • Заполните перекрывающуюся область соответствующим цветом многоугольника, установленным в буфере кадра.
     • Если нам дано более одного многоугольника с перекрывающимися поверхностями относительно плоскости _{окна, то в этом случае мы сначала узнаем буфер глубины (Z min} ), чтобы найти поверхность многоугольника, которая находится ближе к окну. панель и заполнит перекрывающуюся область цветом того многоугольника, который имеет минимум (Z _min ).
5. Повторите все вышеперечисленные шаги для всех заданных полигонов, затем выйдите.

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