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

 

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

 

.

 

Подобные функции возникают во многих приложениях в математике, технике, естественных науках.

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

Рис. 12.9

 

На рисунке показаны параллельные плоскости с . Функция сводится к последовательности кривых, лежащих в каждой из этих параллельных плоскостей, например, к последовательности:

 

,

 

где на каждой из заданных параллельных плоскостей.

 

Поверхность теперь складывается из последовательности кривых, лежащих в каждой из этих плоскостей (см. рис.).

 

 

Рис. 12.10

 

При проецировании кривых на плоскость z=0 (см. рис. 12.10) становится ясна идея алгоритма.

· В начале происходит упорядочивание плоскостей по возрастанию расстояния до них от точки наблюдения.

· Для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней, то есть для каждого значения x в пространстве изображения определяется соответствующее y.

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

 

 

Рис. 12.11

 

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

Фактически этот алгоритм работает каждый раз с одной линией.

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

 

Это математически элегантный алгоритм.

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

Трудоемкость — .

Это в сочетании с распространением растровых дисплеев привело к снижению интереса к этому алгоритму. Но математические методы, используемые в нем, просты, мощны и точны. В последующем введение предварительной сортировки по z снижает трудоемкость.

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

 

.

 

В матричной форме: , или

 

— представляет собой плоскость.

 

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

 

.

 

Каждый столбец содержит коэффициенты одной плоскости. Любая точка пространства в однородных координатах:

 

.

 

Если точка S лежит на плоскости, то

 

.

 

Если точка S не лежит на плоскости, то знак этого скалярного произведения показывает по какую сторону от плоскости расположена точка. Если точка внутри тела — знак «+», если вне — «–».

Если точка S не лежит на плоскости, то знак этого скалярного произведения показывает по какую сторону от плоскости расположена точка (точка внутри тела — знак «+», точка вне тела — знак «–»).

 






Дата добавления: 2016-07-18; просмотров: 1804; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2022 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.025 сек.