Алгоритм Робертса. Экранизация отрезков другими телами

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

А

Решение задачи экранирования отрезков используют параметрическую запись

P(t) = P1 + (P2 – P1)*t.

Решение задачи экранирования отрезков используют параметрическую запись

P(t) = P1 + (P2 – P1)*t.

В векторной форме это выражение имеет вид:

W = f + d*t,

где W = P(t);

f = P1;

d = (P2 – P1).

Отрезок может быть полностью экранированным или частично. В последнем случае необходимо найти t при котором

происходит переход отрезка из видимой части в невидимую.

Для решения этой задачи строится параметрическая плоскость. С этой целью проводится вектор из точки P(t) до

точки наблюдателя.

R(α) = g* α.

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

Q(α,t) = W + R = f + d*t + g* α.

Конкретные значения α и t определяют некоторую точку плоскости, в которой находятся указанные вектора, а все

множество значений этих параметров – плоскость в целом. Значения параметра α положительны, т.к. они определяют расстояние между точкой наблюдателя и точкой P(t).

 

Алгоритм Робертса. Определение сопряжения тел

Линии сопряжения определяются нахождением точек протыкания ребер одного тела через грани другого. Это выполняется поиском решения для hj при значении α =0. Затем точки протыкания соединяются отрезками. Для этого каждая точка протыкания соединяется со всеми остальными. После этого решается задача экранирования этих отрезков данными телами и удаления невидимых частей. В процессе решения этой

задачи система из равно j *(j-1)/2 уравнений дополняется еще тремя: t = 0, t = 1 и α =0.

Алгоритм Z-буфера

Z-буфер — массив, в котором сохраняются значения расстояния до точки наблюдения (глубина) для каждого пиксела растрового изображения. Используется в алгоритмах создания изображений трехмерных объектов с удалением невидимых точек.

Алгоритм предложен Эдом Кэтмулом и представляет собой обобщение буфера кадра. Обычный буфер кадра хранит коды цвета для каждого пиксела в пространстве изображения. Идея алгоритма состоит в том, чтобы для каждого пиксела дополнительно хранить еще и координату Z или глубину. При занесении очередного пиксела в буфер кадра значение его Z-координаты сравнивается с Z-координатой пиксела, который уже находится в буфере. Если Z-координата нового пиксела больше, чем координата старого, т.е. он ближе к наблюдателю, то атрибуты нового пиксела и его Z-координата заносятся в буфер, если нет, то ни чего не делается.

Этот алгоритм наиболее простой из всех алгоритмов удаления невидимых поверхностей, но требует большого объема памяти. Данные о глубине для реалистичности изображения обычно достаточно иметь с разрядностью порядка 20 бит. В этом случае при изображении нормального телевизионного размера в 768×576 пикселов для хранения Z-координат необходим объем памяти порядка 1 Мбайта. Суммарный объем памяти при 3 байтах для значений RGB составит более 2.3 Мбайта.

Время работы алгоритма не зависит от сложности сцены. Многоугольники, составляющие сцену, могут обрабатываться в произвольном порядке. Для сокращения затрат времени нелицевые многоугольники могут быть удалены. По сути дела алгоритм с Z-буфером - некоторая модификация уже рассмотренного алгоритма заливки многоугольника. Если используется построчный алгоритм заливки, то легко сделать пошаговое вычисление Z-координаты очередного пиксела, дополнительно храня Z-координаты его вершин и вычисляя приращение dz Z-координаты при перемещении вдоль X на dx, равное 1. Если известно уравнение плоскости, в которой лежит обрабатываемый многоугольник, то можно обойтись без хранения Z-координат вершин. Пусть уравнение плоскости имеет вид:

A·x+B·y+C·z+D= 0.

Тогда при C не равном нулю

z = -(A·x + B·y+D)/C

Найдем приращение Z-координаты пиксела при шаге по X на dx, помня, что Y очередной обрабатываемой строки - константа.

dz = -(A·(x+dx) + D)/C + (A·x + D)/C = -A·dx/C

но dx = 1, поэтому

dz = -A/C.

Основной недостаток алгоритма с Z-буфером - дополнительные затраты памяти. Для их уменьшения можно разбивать изображение на несколько прямоугольников или полос. В пределе можно использовать Z-буфер в виде одной строки. Понятно, что это приведет к увеличению времени, так как каждый прямоугольник будет обрабатываться столько раз, на сколько областей разбито пространство изображения. Уменьшение затрат времени в этом случае может быть обеспечено предварительной сортировкой многоугольников на плоскости.

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

Общая схема алгоритма с Z-буфером:

 Инициализировать кадровый и Z-буфера. Кадровый буфер закрашивается фоном. Z-буфер закрашивается минимальным значением Z.

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

 Выполнить, если это было предусмотрено, усреднение изображения с понижением разрешения.