[pic]

а индексы c и p соответствуют текущей и предшествующей кривым. Полученный результат показан на рис. 3.6,b. Теперь алгоритм излагается более формально.

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

Если на участке от предыдущего (xn) до текущего (xn+k) значения x видимость кривой изменяется, то вычисляется точка пересечения (xi).

Если на участке от xn до xn+k сегмент кривой полностью видим, то он изображается целиком; если он стал невидимым, то изображается фрагмент от xn до xi; если же он стал видимым, то изображается фрагмент от xi до xn+k.

Заполнить массивы верхнего и нижнего плавающих горизонтов.

Изложенный алгоритм приводит к некоторым дефектам, когда кривая, лежащая в одной из более удаленных от точки наблюдения плоскостей, появляется слева или справа из-под множества кривых, лежащих в плоскостях, которые ближе к указанной точке наблюдения. Этот эффект продемонстрирован на рис. 3.7, где уже обработанные плоскости n - 1 и n расположены ближе к точке наблюдения. На рисунке показано, что получается при обработке плоскости n + 1. После обработки кривых n - 1 и n верхний горизонт для значений x = 0 и 1 равен начальному значению у; для значений x от 2 до 17 он равен ординатам кривой n; а для значений 18, 19, 20 - ординатам кривой n
- 1. Нижний горизонт для значений x = 0 и 1 равен начальному значению у; для значений x = 2, 3, 4 – ординатам кривой n; а для значений x от 5 до 20
- ординатам кривой n - 1. При обработке текущей кривой (n + 1) алгоритм объявляет ее видимой при x = 4. Это показано сплошной линией на рис. 3.7.
Аналогичный эффект возникает и справа при x = 18. Такой эффект приводит к появлению зазубренных боковых ребер. Проблема с зазубренностью боковых ребер решается включением в массивы верхнего и нижнего горизонтов ординат, соответствующих штриховым линиям на рис. 3.7. Это можно выполнить эффективно, создав ложные боковые ребра. Приведем алгоритм, реализующий эту идею для обеих ребер.

Обработка левого бокового ребра:

Если Pn является первой точкой на первой кривой, то запомним Pn в качестве Pn(1 и закончим заполнение. В противном случае создадим ребро, соединяющее Pn и Pn(1.

Занесем в массивы верхнего и нижнего горизонтов ординаты этого ребра и запомним Pn в качестве Pn(1.

Обработка правого бокового ребра:

Если Pn является последней точкой на первой кривой, то запомним Pn в качестве Pn(1 и закончим заполнение. В противном случае создадим ребро, соединяющее Pn и Pn(1.

Занесем в массивы верхнего и нижнего горизонтов ординаты этого ребра и запомним Pn в качестве Pn(1.

Теперь полный алгоритм выглядит так:

Для каждой плоскости z = const.

Обработать левое боковое ребро.

Для каждой точки, лежащей на кривой из текущей плоскости:

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

Если на сегменте от предыдущего (xn) до текущего (xn+k) значения x видимость кривой изменяется, то вычисляется пересечение (xi).

Если на участке от xn до (xn+k) сегмент кривой полностью видим, то он изображается целиком; если он cтал невидимым, то изображается его кусок от xn до xi; если же он стал видимым, то изображается его кусок от xi до xn+k.

Заполнить массивы верхнего и нижнего плавающих горизонтов.

Обработать правое боковое ребро.

Если функция содержит очень острые участки (пики), то приведенный алгоритм может дать некорректные результаты. Во избежании этого если встречаются узкие участки, то функцию следует вычислять в большем числе точек.

На рис. 3.8 показан типичный результат работы алгоритма плавающего горизонта. Запись этого алгоритма приводиться ниже.

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

Гэкран – разрешение экрана в горизонтальном направлении
Вэкран – разрешение экрана в вертикальном направлении
Верх – массив, содержащий координаты верхнего горизонта
Низ – массив, содержащий координаты нижнего горизонта
Y – текущее значение функции y = f ( x, z ) при z = const
Тфлаг – флаг видимости для текущей точки
Пфлаг – флаг видимости для предыдущей точки, равный

0 = невидима

1 = видима и выше верхнего горизонта

-1 = видима и ниже нижнего горизонта
Draw – графическая команда, которая чертит видимую линию между точками, заданными их координатами.
Xmin, Xmax – минимальная и максимальная абсциссы функции
Xшаг – шаг приращения вдоль оси x
Zmin, Zmax – минимальная и максимальная аппликата функции
Zшаг – шаг между плоскостями z = const
Dimension Верх (Гэкран), Низ (Гэкран) инициализация переменных
Xлевое = (1; Yлевое = (1; Xправое = (1; Yправое = (1 инициализация массивов горизонтов
Верх = 0
Низ = Вэкран
Вычисление функции на каждой плоскости z = const, начиная с ближайшей к наблюдателю плоскости Zmax for z = Zmax to Zmin step ( Zшаг инициализация предыдущих значений по x и y: Xпред и Yпред

Xпред = Xmin

Yпред = f (Xmin, z) если используется видовое преобразование, то его нужно применить к

Xпред, Yпред, z в данной точке обработка левого бокового ребра call Обрребра (Xпред, Yпред, Xлев, Yлев; Верх, Низ) call Видимость (Xпред, Yпред, Верх, Низ; Пфлаг) для каждой точки на кривой, лежащей в плоскости z = const for x = Xmin to Xmax step Xшаг y = f (x, z) если используется видовое преобразование, то его нужно применить к данной точке проверка видимости текущей точки и заполнение соответствующего массива горизонта call Видимость (x, y, Верх, Низ; Тфлаг) if Тфлаг = Пфлаг then if (Тфлаг = 1) or (Тфлаг = (1) then

Draw (Xпред, Yпред, x, y) call Горизонт (Xпред, Yпред, x, y; Верх, Низ) end if если видимость изменилась, то вычисляется пересечение и заполняется массив горизонта else if Тфлаг = 0 then if Пфлаг = 1 then call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi) else call Пересечение (Xпред, Yпред, x, y, Низ; Xi, Yi) end if

Draw (Xпред, Yпред, Xi, Yi) сall Горизонт (Xпред, Yпред, Xi, Yi, Верх, Низ) else if Тфлаг = 1 then if Пфлаг = 0 then call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

Draw (Xi, Yi, x, y) сall Горизонт (Xi, Yi, x, y; Верх, Низ) else call Пересечение (Xпред, Yпред, x, y, Низ; Xi, Yi)

Draw (Xпред, Yпред, Xi, Yi) call Горизонт (Xпред, Yпред, Xi, Yi; Верх, Низ) call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

Draw (Xi, Yi, x, y) call Горизонт (Xi, Yi, x, y; Верх, Низ) end if else if Пфлаг = 0 then call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

Draw (Xi, Yi, x, y) call Горизонт (Xi, Yi, x, y; Верх, Низ) else call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

Draw (Xпред, Yпред, Xi, Yi) call Горизонт (Xпред, Yпред, Xi, Yi; Верх, Низ) call Пересечение (Xпред, Yпред, x, y, Низ; Xi, Yi)

Draw (Xi, Yi, x, y) call Горизонт (Xi, Yi, x, y; Верх, Низ) end if end if end if end if вновь инициализировать Пфлаг, Xпред, Yпред

Пфлаг = Тфлаг

Xпред = x

Yпред = y next x обработка правого концевого ребра call Обрребра (x, y, Xправ, Yправ; Верх, Низ) next z finish

подпрограмма обработки бокового ребра
Subroutine Обрребра (x, y, Xребра, Yребра; Верх, Низ) если Xребра = (1, то встречена первая кривая и ребро не создаётся if Xребра = (1 then 1 call Горизонт (Xребра, Yребра, x, y; Верх, Низ)
1 Xребра = x

Yребра = y return подпрограмма определения видимости точки
Subroutine Видимость (x, y, Верх, Низ; Тфлаг) видимость точки определяется по отношению к верхнему и нижнему плавающим горизонтам. Если точка лежит на самом горизонте, то она считается видимой.

Тфлаг = 0, если точка невидима

= 1, если она видима и выше верхнего горизонта

= (1, если она видима и ниже нижнего горизонта x считается целой if (y < Верх (x)) and (y > Низ (x)) then Тфлаг = 0 if y ( Верх (x) then Тфлаг = 1 if y ( Низ (x) then Тфлаг = (1 return

подпрограмма заполнения массивов плавающих горизонтов
Subroutine Горизонт (X1, Y1, X2, Y2; Верх, Низ)

Эта программа использует линейную интерполяцию для заполнения массивов горизонтов между X1 и X2

Max (a, b) – определяет большее из a и b

Min (a, b) – определяет меньшее из a и b проверка вертикальности наклона if (X2 ( X1) = 0 then

Верх (X2) = Max (Верх (X2), Y2)

Низ (X2) = Min (Низ (X2), Y2) else

Наклон = (Y2 ( Y1)/(X2 ( X1) for x = X1 to X2 step 1 y = Наклон * (x ( X1) + Y1

Верх (x) = Max (Верх (x), y)

Низ (x) = Min (Низ (x), y) next x end if return

подпрограмма вычисления пересечения текущей кривой с горизонтом
Subroutine Пересечение (X1, Y1, X2, Y2, Массив; Xi, Yi)

Эта процедура вычисляет пересечение двух отрезков прямых

Массив содержит информацию о соответствующем горизонте

Sign – функция принимающая значения (1, 0, 1, если знак её аргумента

0 соответственно проверка бесконечности наклона if (X2 – X1) = 0 then

Xi = X2

Yi = Массив (X2) else вычисление пересечения обход начинается с самой левой используемой точки пересечение считается обнаруженным, когда изменяется знак разности значений y

Наклон = (Y2 – Y1)/(X2 – X1)

Ysign = Sign (Y1 + Наклон ( Массив (X1 + 1))

Csign = Ysign

Yi = Y1 + Наклон

Xi = X1 + 1 while Csign = Ysign

Yi = Y1 + Наклон

Xi = X1 + 1

Csign = Sign (Yi - Массив (Xi)) end while выбирается ближайшее целое число if |Yi ( Наклон ( Массив (X1 – 1)| ( |Yi ( Наклон ( Массив (X1)| then

Yi = Y1 – Наклон

Xi = X1 – 1 end if end if return

В приведенных выше алгоритме и примере функция у = f (x, z) рассматривалась только при z = const. Часто бывает удобно вычерчивать кривые, полагая постоянными как z, так и x. При этом возникает эффект перекрестной штриховки. На первый взгляд может показаться, что перекрестную штриховку можно получить путем наложения двух результатов, образованных плоскостями z = const и x = const. Однако это не так. Верный результат получается при обработке тех кривых из числа лежащих в плоскостях z = const и x = const, которые ближе всего к горизонтальным при обычном порядке их следования. Однако после обработки каждой кривой, самой близкой к горизонтальной, необходимо обрабатывать участки кривых, лежащих в ортогональных ей плоскостях, которые находятся между указанной кривой и кривой, следующей за ней. Разумеется, при обработке обеих последовательностей кривых нужно использовать одни и те же массивы верхнего и нижнего плавающих горизонтов. Если используется перекрестная штриховка, то не надо формировать левое и правое боковые ребра.

2. Алгоритм Робертса

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9