Алгоритм робертса
Он относится к алгоритмам объектного типа.
Л.Г.Робертс был аспирантом Линкольновской лаборатории МИТ, работал по теме «Техническое зрение роботов». Опубликовал описание алгоритма в 1963-1964 гг. в изданиях МИТ.
ОГРАНИЧЕНИЯ АЛГОРИТМА РОБЕРТСА
Чтобы алгоритм Робертса работает корректно, необходимо выполнение следующих предварительных условий:
|
1. Тело ограничено ПЛОСКОСТЯМИ. 2. Тело ВЫПУКЛО. 3. Нормали всех граней направлены ВНУТРЬ ТЕЛА.
|
«Матрица тела»
Робертс предложил описывать выпуклый объект матрицей
a, b, c, d – коэффициенты уравнений плоскостей граней тела.
Эти коэффициенты соответствуют исходному состоянию сцены в видеоконвейере, т.е. плоскости описаны в ОБЪЕКТНОЙ (исходной) СИСТЕМЕ КООРДИНАТ.
Учет видового преобразования
Проблема: грань в объектной СК имеет параметры a, b, c, d.
Произведено ВИДОВОЕ ПРЕОБРАЗОВАНИЕ с матрицей М (координаты вершин выражены в СК наблюдателя).
КАКИЕ ПАРАМЕТРЫ a’, b’, c’, d’ БУДЕТ ИМЕТЬ ТА ЖЕ ГРАНЬ В СИСТЕМЕ КООРДИНАТ НАБЛЮДАТЕЛЯ?
Выведем соотношение, которое позволит это вычислить.
В объектных координатах произвольная грань описывается матрицей
,
а принадлежащая ей вершина имеет
однородные координаты
Раз вершина принадлежит грани, то ее координаты удовлетворяют уравнению плоскости грани:
Та же вершина в координатах наблюдателя описывается матрицей
,
а грань, которой она принадлежит:
Факт принадлежности вершины грани существует по-прежнему, поэтому справедливо
Нам известна матрица видового преобразования М, поэтому
Приравнивая (2) и (1) и подставляя (3) в (2), получаем:
Сокращая V, приходим к соотношению
Решаем его относительно Fe:
(4)
Итак, чтобы получить уравнение плоскости в СК наблюдателя, необходимо произвести обращение матрицы видового преобразования и воспользоваться формулой (4).
ТАК КТО ЖЕ ВСЕ-ТАКИ НЕВИДИМ?!.
Вернемся к исходной проблеме, которую решает алгоритм Робертса. Расчетная схема объекта и луча зрения имеет вид:
Видно, что орт k луча зрения составляет разные углы с нормалями к граням. Нетрудно сообразить, что с учетом выпуклости объекта невидимыми гранями являются те, нормали которых составляют тупой угол с k.
Для формализации этого условия рассмотрим скалярное произведение
Итак, при α>90° cos α < 0, значит с< 0.
Итак, по Робертсу критерием невидимости грани является отрицательность значения с в столбце матрицы тела, который описывает эту грань.
Пример
Алгоритм z-буфера
Опубликован Кэтмулом в 1975 г.
Этот алгоритм относится к категории экранных. Идея алгоритма Z-буфера состоит в следующем.
В оперативной памяти, кроме буфера кадра, создается еще одна матрица. У нее число строк и столбцов равно числу строк и столбцов пикселов буфера кадра.Ячейки матрицы и пикселы буфера кадра попарно соответствуют друг другу. Но в ячейке этой матрицы будет храниться значение глубины (координаты Ze) точки, цвет которой изображен в соответствующем пикселе буфера кадра. Эта матрица и называется «Z-буфер»ю
Алгоритм заполнения z-буфера
Плоскости граней объектов сцены перебираются по очереди. Луч-проектор проводится через центр буфера кадра до рассматриваемой плоскости. В пиксел кадра записывается цвет точки плоскости, а в соответствующую ячейку Z-буфера – глубина этой точки.
Тонкость состоит в том, что при закраске новых плоскостей в пиксел кадра заносится новый цвет ТОЛЬКО В ТОМ СЛУЧАЕ, если НОВАЯ ГЛУБИНА ТОЧКИ МЕНЬШЕ той, что уже содержится в ячейке Z-буфера. Соответственно новая меньшая глубина переписывается в ячейке Z-буфера. Формально на псевдокоде можно записать такой цикл:
Для каждого пиксела[x,y] буфера кадра
Begin
If Z[x,y] < zbuf[x,y] then begin
Цвет[x,y] := ЦветТочкиСцены[x,y];
zbuf[x,y] := Z[x,y];
end;
End;
Для большей ясности рассмотрим работу алгоритма Z-буфера на плоской модели.