 |
Графика и обработка изображений. Фракталы.
Aлгоритм Робертса - изображение многогранников без невидимых линий.
Алгоритм Робертса может быть с успехом применен для изображения множества выпуклых многогранников на одной сцене в виде проволочной модели с удаленными невидимыми линиями. Метод непригоден непосредственно для передачи падающих теней и других сложных визуальных эффектов. Рассмотрим основные идеи метода на примере одиночного выпуклого многогранника.
Модель объекта
Объект-многогранник, состоящий из N граней, описывается матрицей Т размера 4хN, каждый n-й столбец которой содержит описание n-й (n=[1,N]) плоскости AnХ+BnY+CnZ+Dn=0 в объектной системе координат XYZ:
| A1... An ... AN |
T=| B1... Bn ... BN |
| C1... Cn ... CN |
| D1... Dn ... DN |
Минимальное число граней К=4 наблюдается у тетраэдра.
Важное требование к модели объекта в алгоритме Робертса заключается в достижении такой формы (знака) в функции каждой плоскости fn(X,Y,Z) = AnХ+BnY+CnZ+Dn , при которой справедливо fn(Xвн,Yвн,Zвн) ≥ 0 для любой точки (Xвн,Yвн,Zвн), заведомо принадлежащей телу многогранника.
Достижение этого условия осуществляется путем опытной проверки знака функции относительно внутренней точки, в качестве которой может выступать точка со средним геометрическим положением относительно всех вершин многогранника. Формально правило формирования "положительной" грани может быть представлено в виде
fn+(X,Y,Z)=fn(X,Y,Z) sign fn(Xвн,Yвн,Zвн),
где fn - функция, описывающая n-ю грань с априори неизвестным знаком
относительно внутренней точки; fn+ - та же функция, но с положительным
значением. При достижении "положительности" всех граней автоматически
достигается ориентация нормали
Nn= iAn+jBn+kCn
к любой из граней внутрь фигуры.
Кроме параметров уравнений граней необходимо знать координаты вершин каждой грани. Вершины могут быть заданы или вычислены из матрицы Т путем определения общих решений каждой плоскости со всеми остальными. В любом случае для каждой n-й грани должна быть составлена матрица К-числа вершин:
| X1 Y1 Z1 1 |
Vn = | : : : : |
| Xk Yk Zk 1 |
Синтез изображения
Не все грани, входящие в состав объекта, будут видны наблюдателю. Невидимой будет та, нормаль N к которой ориентирована в ту же сторону, что и вектор R, направленный от объекта в сторону наблюдателя, т. е. при выполнении условия неотрицательности скалярного произведения NR> 0.
| x1 y1 z1 1 |
| : : : : | = VnM
| xk yk zk 1 |
Область внутри такой фигуры закрашивается соответствующим значением интенсивности, для вычисления которой и определения факта затененности телом самого многогранника вычисляют скалярное произведение нормального вектора N и вектора S, нацеленного из объекта на источник света. Грань освещена при отрицательности скалярного произведения, а величина освещенности выбирается пропорциональной значению cos a = -S N / (|S||N|). Соответственно грань находится в тени при условии SN > 0. Таким образом, алгоритм Робертса очень простыми действиями достигает успешного построения изображений отдельных выпуклых многогранных объектов.
Основным недостатком метода, определившим ограниченность его распространения, являются неспособность без привлечения других подходо в реализовать падающие тени,, невозможность передачи зеркальных эффектов и преломления света и, наконец, строгая ориентация метода только на выпуклые многогранники .
В модификациях алгоритма Робертса, ориентированных на изображение множества выпуклых объектов. Алгоритм выполняется в три этапа. На первом этапе алгоритм Робертса используется в классическом виде для удаления нелицевых (невидимых) граней каждого объекта в отдельности. На втором этапе каждое из множества оставшихся ребер оценивается на экранирование всеми другими телами. Наконец, на третьем этапе определяют отрезки, которые образуют новые ребра при протыкании телами друг друга. Несложно развить этот подход для закрашивания видимых граней, однако проблема падающих теней остается открытой.
Ниже приводится эффективная реализация алгоритма Робертса.
Этот алгоритм делится на три этапа. На первом этапе каждое тело анализируется индивидуально с целью удаления нелицевых плоскостей. На втором этапе проверяется экранирование оставшихся в каждом теле ребер всеми другими телами с целью обнаружения их невидимых отрезков. На третьем этапе вычисляются отрезки, которые образуют новые ребра при протыкании телами друг друга. В данном алгоритме предполагается, что тела состоят из плоских полигональных граней, которые в свою очередь состоят из ребер, а ребра - из отдельных вершин. Все вершины, ребра и грани связаны с конкретным телом.
Удаление нелицевых плоскостей
Для каждого тела в сцене:
Сформировать многоугольники граней и ребра, исходя из
списка вершин тела.
Вычислить уравнение плоскости для каждой полигональной
грани тела.
Проверить знак уравнения плоскости:
Взять любую точку внутри тела, например усреднив
координаты его вершин.
Вычислить скалярное произведение уравнения плоскости и
точки внутри тела.
Если это скалярное произведение < О, то изменить знак
уравнения этой плоскости.
Сформировать матрицу тела.
Умножить ее слева на матрицу, обратную матрице видового
преобразования, включающего перспективу.
Вычислить и запомнить габариты прямоугольной объемлющей
оболочки преобразованного объема: Xmax, Xmin, Ymax, Ymin.
Определить нелицевые плоскости:
Вычислить скалярное произведение пробной точки, лежащей
в бесконечности, на преобразованную матрицу тела.
Если это скалярное произведение < О, то плоскость невидима.
Удалить весь многоугольник, лежащий в этой плоскости.
Это избавляет от необходимости отдельно рассматривать
невидимые линии, образуемые пересечением пар невидимых
плоскостей.
Удаление из каждого тела тех ребер, которые экранируются всеми
остальными телами в сцене:
Если задано только одно тело, то алгоритм завершается.
Сформировать приоритетный список этих тел:
Провести сортировку по z. Сортировка производится по
максимальным значениям координаты z, вершин преобразованных
тел. Первым в упорядоченном списке и обладающим наибольшим
приоритетом будет то тело, у которого минимальное среди
максимальных значений z. В используемой правой системе
координат это тело будет самым удаленным от точки наблюдения,
расположенной в бесконечности на оси z.
Для каждого тела из приоритетного списка:
Проверить экранирование всех лицевых ребер всеми другими
телами сцены. Тело, ребра которого проверяются, называется
пробным объектом, а тело, относительно которого в настоящий
момент производится проверка, называется пробным телом.
Естественно, что нужно проверять экранирование пробного
объекта только теми пробными телами, у которых ниже приоритеты.
Провести проверки экранирования для прямоугольных объемлющих
оболочек пробного объекта и пробного тела:
Если Xmin(пробное тело) > Xmax(пробный объект) или
Xmax(пробное тело) < Xmin(пробный объект) или
Ymin(пробное тело) > Ymax(пробный объект) или
Ymax(пробное тело) < Ymin(пробный объект),
то пробное тело не может экранировать ни одного ребра
пробного объекта. Перейти к следующему пробному телу.
В противном случае:
Провести предварительные проверки протыкания, чтобы увидеть,
не протыкается ли пробное тело пробным объектом и существует ли
возможность частичного экранирования первого последним.
Сравнить максимальное значение z у пробного объекта с
минимальным значением z у пробного тела.
Если Zmax(пробный объект) < Zmin(пробное тело), то
протыкание невозможно. Перейти к следующему телу.
В противном случае:
Проверить видимое протыкание.
Если Zmax(пробный объект) > Zmax(пробное тело), то
пробный объект может проткнуть переднюю грань
пробного тела.
Установить флаг видимого протыкания для последующего
использования. Занести проткнутое тело в список протыканий.
Если Xmax(пробный объект) > Xmin(пробное тело) или
Xmin(пробный объект) < Xmax(пробное тело),
то пробный объект может проткнуть бок пробного тела.
Установить флаг видимого протыкания для последующего
использования. Занести тело в список протыканий.
Если Ymax(пробный объект) > Ymin(пробное тело) или
Ymin(пробный объект) < Ymax(пробное тело),
то пробный объект может проткнуть верх или низ пробного тела.
Установить флаг видимого протыкания для последуюшего
использования. Занести проткнутое тело в список протыканий.
Если список протыканий пуст, то устанавливать флаг
протыкания не надо.
Провести проверки экранирования ребер:
Вычислить s и d для ребра.
Вычислить р, q, w для каждой плоскости, несущей грань
пробного тела.
Проверка полной видимости. Если ребро полностью видимо,
то перейти к следующему ребру.
Сформировать уравнения hj = О и решить их, объединяя
попарно и включив в систему уравнения границ t = 0 и
t = 1. Если установлен флаг видимого протыкания, то в
систему надо включить и уравнение границы а = 0.
Запомнить точки протыкания. В противном случае
границу a = О не учитывать.
Для каждой пары (t, а), являющейся решением, проверить
выполнение условий О <= t <= 1, а >= 0 и hj > 0
для всех других плоскостей. Если эти условия выполнены,
то найти Tmax_min и Tmin_max.
Вычислить видимые участки отрезков и сохранить их
для последующей проверки экранирования телами с
более низкими приоритетами.
Определить видимые отрезки, связывающие точки протыкания:
Если флаг видимого протыкания не установлен, перейти к
процедуре визуализации.
Если точек протыкания не обнаружено, перейти к процедуре
визуализации.
Сформировать все возможные ребра, соединяющие точки
протыкания, для пар тел, связанных отношением протыкания.
Проверить экранирование всех соединяющих ребер обоими
телами, связанными отношением протыкания.
Проверить экранирование оставшихся соединяющих ребер
всеми прочими телами сцены. Запомнить видимые отрезки.
Визуализировать оставшиеся видимые отрезки ребер.
Заметим, что этот алгоритм можно реализовать и с обратным списком приоритетов. Оценки по времени продемонстрировали почти линейно зависящий от числа брусков рост, причем последнее число достигало 1152 .
Вверх по странице, к оглавлению и навигации.