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

Идея

Данный алгоритм предназначен для построения поверхности, заданных неявным уравнением F(x,y,z)=0.

Предположим, имеется кусок некоторой заданной поверхности и от нас требуется изобразить её на экране.

Наблюдатель располагается на положительной части оси z и смотрит на начало координат.

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

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

Основные этапы алгоритма

1. Рассматриваемая поверхность рассекается плоскостями, перпендикулярными оси Z. В каждом отсечении получается кривая. Эта кривая описывается уравнением y=f(x,z=const) или x=Q(y,z=const).

2. Полученные кривые можно проецировать на плоскость x_0 y (то есть на плоскость z=0) и изобразить видимые части каждой кривой.

Изображение строится начиная с кривой, полученной в ближайшем к наблюдателю сечении.

Кривая, полученная в сечении ближайшей плоскостью, является видимой.

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

Начиная с третьей кривой понадобится решать задачу определения видимости точек кривой.

Решение задачи определения видимости точек кривой

Поставленная задача решается в пространстве изображения.

Берётся третья кривая и потребуется изображать те участки кривой, которые будут являться видимыми.

Участок кривой будет видим в том случае, если эта кривая располагается выше верхней кривой, либо ниже нижней кривой.

Для того, чтобы решить поставленную задачу, потребуется вычислить функцию в очередной точке, расположенной на кривой, и сравнить значение вычисленной координаты y с значением y_max и y_min для раннее рассмотренных кривых. В том случае, если y_тек>y_max, очередная точка, расположенная на текущей рассматриваемой кривой, будет являться видимой. Также в случае, если y_тек<y_min, то очередная точка, расположенная на текущей рассматриваемой кривой, будет являться видимой. Если точка видима, то она высвечивается, невидима – не высвечивается.

Следует заметить, что в данном алгоритме формируются два горизонта: нижний и верхний. Верхний горизонт – видимые участки кривых с наибольшим значением ординат. Нижний горизонт – видимые участки кривых с наименьшим значением ординат.

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

Так, верхним горизонтом можно называть участки кривых с наибольшим значением ординат, а нижним горизонтом – участки кривых с минимальным значением ординат.

Также верхним горизонтом можно назвать массив максимальных значений ординат, а нижним – массив минимальных значений ординат.

Работа алгоритма сводится к вычислению значения y(x,z=const) и сравнению y(x,z=const)>y_max (x): если y(x,z=const)>y_max, то y_max=y(x,z=const). В противном случае надо проверить y(x,z=const)<y_min, то y_min (x)=y(x,z=const). Эта процедура называется поддержанием горизонта. Точка будет невидима в том случае, если y_min<y(x,z=const)<y_max, то есть если точка расположена между двумя горизонтами.

Поиск точек пересечения кривых на интервалах

Рассмотрим следующий пример:

На рисунке зелёным цветом обозначены некоторые определённые горизонты.

Обрабатывая некоторую кривую, найдём следующие точки, ей соответствующие (обозначены синим цветом):

В решении задачи фигурирует следующее правило:

Если очередная точка невидима, то мы её не соединяем с предыдущей точкой. В ином случае – соединяем с предыдущей точкой. Как итог, будем иметь следующее (голубым цветом обозначена видимая часть отрезка):

Таким образом, предоставим на рассмотрение два ошибочных случая.

В первом случае видимый участок кривой объявляется невидимым, а во втором – невидимый участок кривой объявляется видимым.

Для того, чтобы избавиться от такого недостатка и сократить и упростить вычисления, с учётом того, что delta x достаточно мало, а также предполагая, что поверхности, а следовательно, и получаемые кривые, достаточно гладкие, на текущем интервале будем аппроксимировать кривую отрезком.

На рисунке кривая, что больше, - предыдущая, а малая – текущая.

От нас требуется вычислить тангенс угла наклона каждой прямой, которая аппроксимирует эти две кривые

Улучшение качества изображения поверхности

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

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

Указанные рёбра можно соответственно назвать левым боковым и правым боковым.

Также следует отметить, что изображение можно улучшить дополнительным рассечением поверхности секущей плоскостью, перпендикулярной ещё одной оси координат. Но в данном случае нельзя построить сначала кривые, построенные в одной серии отсечении, а далее построить кривые, полученные во второй серии отсечений – построение должно происходить одновременно в каждой серии.

Недостаток алгоритма

Рассмотрим следующую ситуацию:

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

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

Алгоритм

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

1. Обработать левое боковое ребро. Если точка является первой точкой кривой и лежит на первой кривой, то запомнить её (P). Если точка принадлежит не первой кривой, то соединить её с точкой P и запомнить в качестве новой точки P.

2. Для каждой точки текущей кривой выполнить следующие действия: Определить видимость точки (если y(x)>y_max (x) или y(x)<y_min (x))

• Если видимость кривой изменилась, то найти точку пересечения кривой с горизонтом.

• Если текущая точка невидима, то изобразить участок кривой от предыдущей точки до точки пересечения

• Если текущая точка видима, то изобразить участок кривой от точки пересечений до текущей точки

• Если текущий сегмент кривой видим, то изобразить его полностью и заполнить массивы верхнего и нижнего горизонтов.

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

Насчёт обработки боковых рёбер:

Q - переменная, хранящая крайнюю точку предыдущей кривой
P - первая (для левого бокового ребра) или последняя 
(для правого бокового ребра) точка текущей кривой

Если текущая кривая не первая:
    Изобразить ребро (P; Q)
Q = P

Почему вот за это мне не дали по лицу - я не знаю

Следующий вопрос: 25. Задача удаления невидимых линий и поверхностей. Ее значение в машинной графике. Классификация алгоритмов по способу выбора системы координат (объектное пространство, пространство изображений).

Предыдущий вопрос: 23. Определение факта выпуклости трехмерных тел. Разбиение тела на выпуклые многогранники.