z = const по возрастанию расстояния до них от точки наблюдения. Затем для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней. Алгоритм удаления невидимой линии заключается в следующем:

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

Реализация данного алгоритма достаточно проста. Для хранения максимальных значений y при каждом значении x используется массив, длина которого равна числу различимых точек (разрешению) по оси x в пространстве изображения. Значения, хранящиеся в этом массиве, представляют собой текущие значения «горизонта». Поэтому по мере рисования каждой очередной кривой этот горизонт «всплыва­ет». Фактически этот алгоритм удаления невидимых линий работает каждый раз с одной линией.

Алгоритм работает очень хорошо до тех пор, пока какая-нибудь очередная кривая не окажется ниже самой первой из кривых. Как показано на рис.3.4,а. Подобные кривые, естественно, видимы и представляют собой нижнюю сторону исходной поверхности. Однако алгоритм будет считать их невидимыми. Нижняя сторона по­верхности делается видимой, если модифицировать этот алгоритм, включив в него нижний горизонт, который опускается вниз по ходу работы алгоритма. Это реализуется при помощи второго массива, длина которого равна числу различимых точек по оси x в про­странстве изображения. Этот массив содержит наименьшие значе­ния y для каждого значения x. Алгоритм теперь становится таким:

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

Полученный результат показан на рис. 3.4, b.

В изложенном алгоритме предполагается, что значение функции, т. е. y, известно для каждого значения x в пространстве изо­бражения. Однако если для каждого значения x нельзя указать (вычислить) соответствующее ему значение у, то невозможно поддерживать массивы верхнего и нижнего плавающих горизонтов. В таком случае используется линейная интерполяция значений у между известными значениями для того, чтобы заполнить массивы верхнего и нижнего плавающих горизонтов, как показано на рис. 3.5. Если видимость кривой меняется, то метод с такой простой интер­поляцией не даст корректного результата. Этот эффект проиллюст­рирован рис. 3.6,а. Предполагая, что операция по заполнению мас­сивов проводится после проверки видимости, получаем, что при пе­реходе текущей кривой от видимого к невидимому состоянию (сег­мент АВ на рис. 3.6,а), точка (xn+k, yn+k ) объявляется невидимой. Тогда участок кривой между точками (xn, yn) и (xn+k, yn+k ) не изо­бражается и операция по заполнению массивов не производится. Об­разуется зазор между текущей и предыдущей кривыми Если на участке текущей кривой происходит переход от невидимого состоя­ния к видимому (сегмент CD на рис. 3.6,а), то точка (xm+k, ym+k ) объявляется видимой, а участок кривой между точками (xm, ym) и (xm+k, ym+k ) изображается и операция по заполнению массивов проводится. Поэтому изображается и невидимый кусок сегмента CD. Кроме того, массивы плавающих горизонтов не будут содер­жать точных значений у. А это может повлечь за собой дополни­тельные нежелательные эффекты для последующих кривы. Следо­вательно,

необходимо решать задачу о поиске точек пересечения сегментов текущей и предшествующей кривых.

Существует несколько методов получения точек пересечения кривых. На растровых дисплеях значение координаты x можно увеличивать на 1, начиная с xn или xm (рис. 3.6,а). Значение у, соответствующее текущему значению координаты х в пространстве изо­бражения, получается путем добавления к значению у, соответству­ющему предыдущему значению координаты x, вертикального приращения Dy вдоль заданной кривой. Затем определяется видимость новой точки с координатами (x + 1, y + Dy ). Если эта точка видима, то активируется связанный с ней пиксел. Если невидима, то пиксел не активируется, а x увеличивается на 1. Этот процесс про­должается до тех пор, пока не встретится xn+k или xm+k. Пересече­ния для растровых дисплеев определяются изложенным методом с достаточной точностью. Близкий и даже более элегантный метод определения пересечений основан на двоичном поиске.

Точное значение точки пересечения двух прямолинейных отрезков, которые интерполируют текущую и предшествующую кривые, между точками (xn, yn) и (xn+k, yn+k ) (рис. 3.6) задается формулами:

где

а индексы 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. Это можно выполнить эффективно, создав ложные боковые ребра. Приведем алгоритм, реализующий эту идею для обеих ребер.