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

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

F(x,y,z)=0,

часто встречаемых в математике, физике, технике.

Поскольку в приложениях в основном интересуются описанием поверхности, этот алгоритм работает в пространстве изображения. Главная идея данного метода заключается в сведении трехмерной задачи к двумерной путем пересечения исходной поверхности последовательностью параллельных секущих плоскостей, имеющих постоянное значение координат x, y, или z (рис.18).

Если полученные кривые спроецировать на плоскость z=0, то можно сформулировать идею алгоритма удаления невидимых участков исходной поверхности. Алгоритм сначала упорядочивает плоскости z=const по возрастанию расстояния до них от точки наблюдения. Затем в каждой плоскости, начиная с ближней к точке наблюдения, строится кривая, лежащая на ней, т.е. для каждого значения координаты x в пространстве изображения определяется соответствующее значение y.

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

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

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

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

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

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

В алгоритме Робертса требуется, чтобы все изображаемые тела или объекты были выпуклыми. Невыпуклые тела должны быть разбиты на выпуклые части. Требования выпуклости являются принципиальным ограничением алгоритма Робертса.

Алгоритм Робертса делится на три этапа:

1. каждое тело анализируется индивидуально с целью удаления нелицевых (невидимых) плоскостей;

2. проверяется экранирование оставшихся в каждом теле ребер всеми другими телами с целью обнаружения их невидимых отрезков;

3. вычисляются отрезки, образующие новые ребра при протыкании телами друг друга.

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