Удаление невидимых линий и поверхностей. Алгоритмы плавающего горизонта и Роберртса.

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

Рассмотрим задачупостроения графика функций двух переменных z=f(x,y) в виде сетки координатных линий x=const и y=const.

Заметим, что каждая линия семейства z=f(x,y_i) лежит в своей плоскости y=y_i, причем эти плоскости параллельны и, следовательно, не пересекаются. Поэтому при y_j>y_i линия z=f(x,y_j) не может закрывать линию z=f(x,y_i).

Тогда возможен следующий алгоритм построения графика функции z=f(x,y):

Линии рисуются в порядке удаления (возрастания по y) и при рисовании очередной линии рисуется только та ее часть, которая не закрывается ранее нарисованными линиями. Такой алгоритм называется методом плавающего горизонта.

Для определения частей линии z=f(x,y_k), которые не закрывают ранее нарисованные линии, вводятся линии горизонта или контурные линии.

Пусть проекцией линии z=f(x,y_k) на картинную плоскость является линия Y=Y_k(X), где (X,Y) – координаты на картинной плоскости. Контурные линии Y^k_max(X) и Y^k_min(X) определяются следующими соотношениями:

Y^k_max(X)=max Y_i(X), 
Y^k_min(X)=min Y_i(X), где 1<=k<=k-1

На экране рисуются только те части линии Y=Y_k(X), которые находятся выше линии Y^k_max(X) или ниже линии Y^k_min(X).

Одной из наиболее простых и эффективных реализации данного метода является растровая реализация, при которой в области задания вводится сетка

{ (x_j,y_j), i=1, , n_i }

и каждая из линий Y=Y_k(X) представляется в виде ломаной. Для рисования сегментов этой ломаной используется модифицированный алгоритм Брезенхейма, который перед выводом очередного пиксела сравнивает его ординату с верхней и нижними контурными линиями, представляющими в этом случае массивы значений ординат.

Алгоритм Робертса (1969 г.)

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

Алгоритм работает в объектной плоскости.

• Сначала удаляются из каждого тела те ребра или грани, которые экранируются самим телом.
• Затем каждое из видимых ребер каждого тела сравнивается с каждым из оставшихся тел для определения какая его часть экранируется этими телами.

Возможны следующие варианты:

1. грань не закрывает ребро;
2. грань полностью закрывает ребро (тогда она удаляется из списка ребер);
3. грань частично закрывает ребро (В этом случае ребро разбивается на несколько частей, из которых видимыми являются не более 2. Само ребро удаляется из списка, но в список добавляются его части не закрываемые гранью).

Если общее количество граней равно n, то время работы пропорционально n².

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

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

Реализация алгоритма Робертса

В алгоритме Робертса требуется, чтобы все изображаемые тела или объекты были выпуклые. Многогранное тело с плоскими гранями должно представляться набором пересекающихся плоскостей. Уравнение плоскости

ax₁+b₁+c₁z+d₁=0

Любое выпуклое твердое тело можно выразить матрицей тела, состоящей из коэффициентов уравнений плоскостей

Любая точка пространства представима в однородных координатах вектором [s]=[x,y,z,1]. Если точка s лежит на плоскости, то [s][P]^T ([P]^T - столбец [V]). Если же точка не лежит на плоскости, то знак этого скалярного произведения показывает по какую сторону от плоскости расположена эта точка.

Уравнение первой плоскости x₁=1/2 => x₁-1/2=0 => 2x₁-1=0.

Матрица тела для куба

Знаки плоскостей задаются произвольно. (Верно и 2x₁-1=0 и -2x₁+1=0). Необходимо матрицу тела проверить с помощью точки, лежащей, например, внутри, чтобы убедится, что знаки у координат всех плоскостей заданы верно.

Если знак скалярного произведения для какой-либо плоскости <0, то соответствующее уравнение плоскости следует умножить на –1.

Выберем точку внутри куба [ 1/4 1/4 1/4 1]. Скалярное произведение

Результаты для 1, 3, 5 уравнений <0, следовательно коэффициенты этих уравнений необходимо умножить на –1 для получения корректной матрицы.

Теперь определим грани объекта, которые не видны. Способ эквивалентен вычислению нормали к поверхности.

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

Если зритель находится в бесконечности (ось z направлена от наблюдателя), вектор такого наблюдения равен. [E]=[0, 0, -1, 0].

Фактически [E] представляет любую точку, лежащую на плоскости z=- . Т.е. любую точку типа [x, y, - ]. Поэтому, если скалярное произведение этого вектора на столбец в [V], соответствующий какой-либо плоскости <0, то [E] лежит по отрицательную сторону этой плоскости. Следовательно эти плоскости невидимы из любой точки наблюдения, лежащей в плосости - .

Отрицательное число в 6 столбце показывает, что грань с этим номером нелицевая. Нулевые результаты соответствуют плоскостям параллельным направлению взгляда.

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

Пример: Рассмотрим единичный куб с центром в начале координат, повернутый на 45 градусов вокруг оси y.

Преобразование матрицы тела получается умножением исходной матрицы V слева на матрицу обратную [R_y]. Для чистого поворота обратная матрица сводится к транспонированной.

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.