Аппаратная графическая подсистема в будущем

⇐ ПредыдущаяСтр 8 из 17Следующая ⇒

Итоги:

o Динамическое распределение ресурсов

o Большой массив одинаковых по возможностям процессоров

o Общий коммутатор

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

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

o Память, работающая напрямую с такими шинами

o Устройства вывода с общими периферийными интерфейсами, а также беспроводными интерфейсами

o Фокусировка на качестве (а не на разрешении или кадровой частоте изображения)

32. Представление пространственных форм. Полигональные сетки.(км)

Во многих приложениях машинной графики возникает потребность в представлении трехмерных форм. Необходимость описывать пространственные объекты появляется в двух ситуациях.

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

Во-вторых, такая необходимость возникает в задачах автоматизированного проектирования. В этом случае нет заранее существующей модели исследуемого объекта: конструктор, руководствуясь, возможно, лишь приблизительным эскизом, «создает» пространственную форму, действуя в интерактивном режиме. Используемое представление должно быть удобно для работы в режиме диалога, чтобы поверхность можно было легко привести к желаемой форме.

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

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

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

Альтернатива: параметрические бикубические куски описывают координаты точек на искривленной поверхности с помощью трех уравнений (по одному для х, у и z). Каждое из уравнений имеет две переменные (два параметра), причем показатели степени при них не выше третьей (отсюда название бикубический). Границами кусков являются параметрические кубические кривые. Для представления поверхности с заданной точностью требуется значительно меньшее число бикубических кусков, чем при аппроксимации полигональной сеткой. Однако алгоритмы для работы с бикубическими объектами существенно сложнее алгоритмов, имеющих дело с многоугольниками.

Полигональные сетки

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

Для оценки этих представлений используются следующие критерии:

· Объем требуемой памяти.

· Простота:

o идентификации ребер, инцидентных вершине.

o идентификации многоугольников, которым принадлежит данное ребро.

o процедуры поиска вершин, образующих ребро.

o определения всех ребер, образующих многоугольник.

o получения изображения полигональной сетки.

o обнаружения ошибок в представлении (например, отсутствие ребра, вершины или многоугольника).

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

33. Формы задания: явная, указатели в список вершин, явное задание ребер.

Явное задание многоугольников.

Каждый многоугольник можно представить в виде списка координат его вершин:

P=((x1, y1, z1), (x2, y2, z2), .... (xn, yn, zn));

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

Рис. Многоугольники с общей вершиной А.

Например, поиск всех многоугольников, которые имеют общую вершину, требует сравнения троек координат одного многоугольника с тройками координат всех остальных многоугольников. Наиболее эффективный способ выполнить такое сравнение состоит в сортировке всех N координатных троек: для этого потребуется в лучшем случае Nlog2N сравнений. Но и тогда существует опасность, что одна и та же вершина вследствие ошибок округления может в разных многоугольниках иметь различные значения координат, поэтому правильное соответствие может быть никогда не найдено.

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

Задание многоугольников с помощью указателей в список вершин.

При использовании этого представления каждый узел полигональной сетки запоминается лишь один раз в списке вершин:

V=((x1, y1, z1), .... (xn, yn, zn));

Многоугольник определяется списком указателей (или индексов) в списке вершин. Многоугольник, составленный из вершин 3, 5, 7 и 10 этого списка, представляется как Р=(3, 5, 7, 10).

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

Явное задание ребер.

В этом представлении имеется список вершин V, однако будем рассматривать теперь многоугольник не как список указателей на список вершин, а как совокупность указателей на элементы списка ребер, в котором ребра встречаются лишь один раз. Каждое ребро в списке ребер указывает на две вершины в списке вершин, определяющие это ребро, а также на один или два многоугольника, которым это ребро принадлежит. Таким образом, мы описываем многоугольник как P=(E1, ..., Еn), а ребро как E=(V1, V2, P1, Р2). Если ребро принадлежит только одному многоугольнику, то либо P1, либо P2 — пусто. На рисунке приведен пример такого представления:

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

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

E=(V1, V2, P1, P2, ..., Pn);

34 Параметрические кубические кривые.(км)

Выделяют три основных вида задания функции:

1) явный вид задания функции. - явное выражение для y, которое позволяет вычислять y при любом значении x. Уравнение прямой линии y=2x+3 – пример явного задания функции.

2) неявный вид задания функции. f(x, y)=0 - неявное задание функции от х и у. Пример неявного задания функции - уравнение окружности с радиусом r=1. Чтобы в этом случае получить явный вид задания функции, уравнение надо разбить на два:

для верхней половины окружности получим , для нижней -

3) параметрический вид задания функции. В параметрическом виде задания функции х и у являются равноправными и представляются в виде функций от вспомогательного параметра t, то есть x = x(t), y = y (t). Параметрический вид, например, для уравнения окружности с радиусом r=1 будет записываться следующим образом:

, где t лежит в интервале 0 < t < 2П

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

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

Параметрической кубической кривой является кривая, в которой х, y и z — многочлены третьего порядка (т. е. кубические) относительно некоторого параметра t. Так как мы рассматриваем конечные отрезки кривой, то без потери общности можем ограничить диапазон изменения параметра и считать .

Следовательно:

x(t)=a_xt³+ b_xt²+ c_xt+ d_x

y(t)=a_yt³+ b_yt²+ c_yt+ d_y (2)

z(t)=a_zt³+ b_zt²+ c_zt+ d_z

Производные функций x(t), y(t) и z(t) по параметру t имеют один и тот же вид. Например:

(3)

Три производные определяют касательный вектор. Тангенсы углов наклона кривой задаются как отношения компонент этого вектора:

(4)

Углы наклона не зависят от длины касательного вектора. Если умножить производные на k, получим:

(5)

(6)

При поиске способов определения a_x, b_x, c_x и d_x ниже мы будем иметь дело только с производными от x(t). Для y(t) и z(t) производные и окончательные формулы аналогичны формулам для x(t) и мы их не будем приводить.

Почему мы рассматриваем именно кубические кривые? Потому что для сегментов кривой не существует представления более низкого порядка, которое обеспечивало бы в точке соединения кривых друг с другом непрерывность положения и наклона сегментов и в то же время гарантировало бы, что концевые точки сегмента кривой проходят через заданные точки. Отметим, что наша основная цель — описать кривую с помощью последовательности сегментов кривой, например, так, как изображено на рисунке (в точке соединения сегменты кривой и их касательные векторы равны):

Рис. Два сегмента кривой, связанные между собой.

Ниже для описания непрерывности мы будем пользоваться общим обозначением С⁽ⁱ⁾: говорят, что кривые С⁽⁰⁾ непрерывны, если они не имеют разрывов, и кривые С⁽¹⁾ непрерывны, если, кроме того, непрерывны их касательные. В общем случае С⁽ⁱ⁾-непрерывность означает, что непрерывны функция и ее первые i производные.

Параметрический кубический многочлен с четырьмя коэффициентами является параметрической кривой наиболее низкой степени, которая при соответствующем выборе коэффициентов может удовлетворять четырем условиям (положению каждого из концов сегмента и касательным векторам в них). Можно использовать также параметрическое представление и более высокого уровня, однако в этом случае появляется волнистость и возникают осцилляции. Кубический многочлен является, кроме того, параметрической функцией наиболее низкой степени, с помощью которой можно представить неплоскую кривую, необходимую для описания пространственных кривых.

Мы подробно рассмотрим только три из многих способов описания параметрических бикубических кривых:

· метод Эрмита - задаются положения конечных точек кривой и касательные векторы в них;

· метод Безье - задается положение конечных точек кривой, а для неявного задания касательных в этих точках используются две другие точки, обычно лежащие не на кривой;

· метод В-сплайнов - конечные точки не лежат на кривой, в результате чего как первая, так и вторая производные оказываются непрерывными на концах сегмента.

Мы убедимся, что каждая из этих трех форм описания кривой имеет свои достоинства и недостатки.

35. Параметрические кубические кривые: форма Эрмита.

Найдем выражение для кубической кривой в форме Эрмита, если известны концевые точки и касательные векторы к кривой в этих точках. Зададим точки Р₁ и Р₄ и касательные векторы R₁ и R₄ (точкам присваиваются индексы 1 и 4, а не 1 и 2 для совместимости с выражениями, которые используются при построении кривых методами Безье и В-сплайнов). Требуется найти коэффициенты а_x, b_x, c_x и d_x из выражения (2), удовлетворяющие условиям:

х(0)=P_1x, х(1)=P_4x, х’(0)=R_1x, х’(1)=R_4x; (7)

мы используем индекс х для ссылки на x-компоненты точек и касательных векторов.

Переписывая выражение для х(t), получаем:

(8)

или (9)

или x(t)=TCx; (10)

где Т представляет собой вектор-строку степени t, а С_х — вектор-столбец коэффициентов x(t).

Запишем условия (7), используя уравнение (9):

x(0)=Р_1x=[0 0 0 1]С_x;

x(1)=Р_4x=[1 1 1 1]С_x; (11)

Чтобы записать выражение для ограничений на касательные векторы, продифференцируем сначала выражение (9) по t и получим:

x'(t)=[3t² 2t 1 0]С_x; (12)

Тогда:

x'(0)=R_1x=[0 0 1 0] С_x; (13)

x'(1)=R_4x=[3 2 1 0] С_x; (14)

Выражения (11), (13) и (14) можно объединить в одно матричное уравнение:

(15)

С_x— получается нахождением обратной матрицы:

(16)

Здесь через М_h обозначена эрмитова матрица, а через G_h — геометрический вектор Эрмита. Подставляя этот результат в выражение (10), получим:

x(t)=TM_hG_hx; (17)

Аналогично:

y(t)= TM_hG_hy; (18)

z(t)= TM_hG_hz; (19)

Уравнение для x(t), y(t) и z(t) часто записывают в виде:

P(t)=TM_hG_h; (20)

Если заданы P₁, P₄, R₁ и R₄, можно определить x(t), y(t) и z(t) для и найти все точки на сегменте кубической кривой от P₁ до Р₄, у которого касательный вектор в начальной точке равен R₁, а в конечной — R₄.

Найдем произведение ТМ_h:

ТМ_h = [(2t³—3t² + 1) (—2t³ + 3t²) (t³—2t² +1) (t³—t²)]; (21)

Умножая это выражение справа на G_hx, получим:

x(t)=TM_hG_hx=P_1x(2t³-3t²+1)+ P_4x(-2t³+Зt²)+R_1x(t³—2t²+t)+R_4x(t³-t²); (22)

Четыре функции переменной t в произведении ТМ_h часто называют функциями сопряжения, так как с помощью первых двух функций сопрягаются точки P₁ и Р₄, а посредством двух других — векторы R₁ и R₄, в результате чего получается «сглаженное» объединение x(t).

Ниже на рисунке приведены эрмитовы кривые. Их геометрические матрицы отличаются друг от друга только длиной касательного вектора. Чем больше длина вектора, тем сильнее кривая «вытягивается» в направлении, задаваемом этим вектором до того, как он начнет перемещаться к противоположному концу сегмента. Во всех случаях касательные к кривым имеют в концевых точках одно и то же направление.

Далее показан другой ряд эрмитовых кривых — длина касательного вектора остается неизменной, а изменяется направление.

Так же приведены две эрмитовы кубические кривые, имеющие общую конечную точку. Геометрические векторы, с помощью которых достигается С⁽¹⁾-непрерывность, следующие:

и (23)

Вытянутость кривой вправо обеспечивается тем, что

36. Параметрические кубические кривые: форма Безье, В-сплайнов.

Форма Безье

Форма описания кубической кривой, предложенная Безье, очень близка к эрмитовой форме, однако отличается от нее заданием касательных векторов в конечных точках. В форме Безье используются четыре точки:

Касательные векторы в конечных точках задаются отрезками P₁P₂ и Р₃Р₄. В частности, касательные векторы R₁ и R₄ эрмитовой формы определялись таким образом, чтобы соответствовать четырем точкам Безье P₁, P₂, и Р₃, Р₄:

R1=3(P₂-P₁)=P'(0), R4=3(P₄-P₃)=P'(1);

Поэтому соотношение между геометрической матрицей Эрмита G_h, и геометрической матрицей Безье G_b записывается следующим образом:

(24)

Подставляя в выражение (17), найдем:

x(t)=TM_hG_hx= TM_hM_hbG_bx; (25)

Обозначив произведение M_hM_hb через Мь, получим выражение x(t)=TM_bG_bx, которое имеет теперь форму Безье. Матрица Мь, полученная из произведения M_hM_hb, есть:

(26)

На рисунке ниже приведены две кривые Безье, имеющие общую конечную точку. С⁽¹⁾-непрерывность в этой точке гарантируется в том случае, когда.

Форма Безье благодаря двум своим свойствам используется в машинной графике чаще, чем эрмитова форма.

Во-первых, потому, что геометрическая матрица (в случае четырех точек) интуитивно привлекательна в интерактивном режиме, так как, перемещая точки с помощью локатора, можно легко привести кривую к желаемой форме. В случае эрмитовой формы касательные векторы должны задаваться в явном виде; в режиме диалога их определять труднее, да и само понятие незнакомо некоторым пользователям. Однако если касательный вектор известен, то привести кривую в соответствие с ним легче при использовании эрмитовой формы.

Во-вторых, четыре управляющие точки определяют выпуклый многоугольник (выпуклую оболочку), внутри которого находится кривая Безье. Выпуклая оболочка оказывается полезной при отсечении кривой по окну или видимому объему. Вместо того чтобы сразу проводить отсечение кривой, мы сначала проверим ее выпуклую оболочку и только в том случае, если она пересекает окно или видимый объем, возникает необходимость в проверке самой кривой.

Форма B-сплайнов

Кривая, представленная в виде кубического В-сплайна, в общем случае может проходить через любые управляющие точки, однако она непрерывна и, кроме того, непрерывностью изменения обладают ее касательный вектор и кривизна (т. е. первая и вторая производные кривой непрерывны в конечных точках) в отличие от форм Эрмита и Безье, у которых в конечных точках непрерывны лишь первые производные (но которые проходят через управляющие точки). Таким образом, можно утверждать, что форма B-сплайнов «более гладкая», чем другие формы.

Термин сплайны происходит от длинных гибких металлических реек, с помощью которых чертежники размечают поверхности самолетов и кораблей. B-сплайн описывается следующей формулой:

X(t)=TM_sG_sx; (27)

где:

(28)

При аппроксимации управляющих точек P₁, Р₂, …, Р_п последовательностью В-сплайнов мы будем применять между каждой парой соседних точек геометрические матрицы. Для аппроксимации в интервале, близком к точкам Р_i и P_i+1, используется:

2 i n-2 (29)

На рисунке показана аппроксимация нескольких точек с помощью В-сплайнов, Поскольку точки 5, 6 и 7 имеют одинаковое значение координаты х, кривая проходит через точку, значение х которой совпадает со значением этой координаты точки 6.

Свойство выпуклой оболочки кривых Безье также справедливо и для кривых в форме B-сплайнов: выпуклая оболочка кривой в приближенном интервале P_i – _Pi+1 та же, что и четырех управляющих точек, используемых для генерации кривой: P_i-1, P_i, _Pi+1, P_i+2.

37. Параметрические кубические поверхности: форма Эрмита, Безье и В-сплайов.

Перейдем теперь от кубических кривых к бикубическим поверхностям, задаваемым кубическими уравнениями от двух переменных s и t. Изменяя оба параметра от 0 до 1, можно определить все точки на куске поверхности. Если одному из параметров присвоить постоянное значение, а другой — изменять в диапазоне 0 – 1, то в результате получим кубическую кривую. Так же как и в случае кривых, мы будем рассматривать только уравнение для х:

х(s, t) = a₁₁s³t³ + a₁₂s³t ² + a₁₃s³t +a₁₄s³ +

a₂₁s²t³ + a₂₂s²t² + a₂₃s²t + a₂₄s² +

a₃₁st³+ a₃₂st²+ a₃₃st + a₃₄s +

a₄₁t³+ a₄₂t² + a₄₃t + a₄₄ (1)

Запишем его в более удобной форме:

x(s, t)=SC_xT^T; (2)

где S=[s³ s² s 1], T=[t³ t² t 1], a T^T обозначает транспонированную матрицу Т. Эта запись называется алгебраической формой представления, так как С_x задает коэффициенты бикубического многочлена.

Существуют также и С_у и С_z, которые определяют коэффициенты y(s, t) и z(s, t).

Форма Эрмита

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

Уравнение кривой в форме Эрмита имеет вид

x(s)=SM_hG_hx; (3)

От параметра t:

(4)

где P_1x(t) и P_4x(t) – описывают х – компоненты начальной и конечной точек кривой, задаваемой параметром s. Для каждого t определяются две конечные точки.

R_1x(t) и R_4x(t) – описывают касательные векторы в конечных точках кубической кривой, построенной в зависимости от s.

Пусть каждая из кривых задается в виде эрмитовых кривых.

(5)

Четыре кубических многочлена можно представить в виде вектор-строки:

(6)

Используя свойство (ABC)^T=C^TB^TA^T имеем:

(7)

Получим:

(8)

Аналогично для y(s, t) и z(s, t).

Как определить Q_x, Q_y, Q_z c помощью точек и углов наклона? [выкладки пропускаем]

(9)

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

Форма Безье

Уравнения для кусков Безье выводятся также, как и для бикубических кусков Эрмита:

(10)

Геометрическая матрица P состоит из 16 управляющих точек. Поверхности Безье используются часто при интерактивном проектировании: управляющие точки позволяют легко изменить форму куска поверхности.

Форма В-сплайнов

(11)

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

38. Методы создания реалистических изображений

Для создания реалистичных изображений трехмерных объектов используются следующие способы:

· удаление скрытых поверхностей и линий

· закраска видимых поверхностей (освещение)

· фактурирование (текстурирование)

Тезисы:

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

39. Удаление скрытых линий (HSR). Тезисы.

В целом алгоритмы удаления невидимых линий можно разделить на 2 класса:

· алгоритмы отсечения в пространстве изображения (картинном пространстве);

· алгоритмы отсечения в пространстве объекта.

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

Для N таких точек число проверок пропорционально n*K, (разрешение 250000< К< 4000000)

Для второго класса каждая из n граней сравнивается с оставшимися (n-1) гранями. Число проверок пропорционально n².

Тезис 1: Удаление скрытых поверхностей должно проводиться в трехмерном пространстве до проецирования на плоскость, при котором теряется информация о третьей координате, необходимая для проведения сравнений по глубине.

Тезис 2: Сравнение по глубине можно свести к следующему вопросу: закрывает ли одна из двух заданных точек P₁=(x₁, y₁, z₁) и P₂=(x₂, y₂, z₂) другую? Этот вопрос эквивалентен следующему: лежат ли точки P₁ и P₂ на одном и том же проекторе? Если да, то, сравнивая их координаты z₁ и z₂ можно определить, какая точка ближе к наблюдателю.

При параллельном проецировании проекторы параллельны оси z, а при центральном проецировании выходят из начала координат. При параллельном проецировании точки лежат на одном проекторе, если: x₁=x₂ и y₁=y₂, а при центральном если: x₁/z₁=x₂/z₂, y₁/z₁=y₂/z₂.

C объектами для упрощения сравнений по глубине можно связать экранные оболочки (прямоугольник минимального размера, в который полностью помещается объект).

Если проекции оболочек на плоскость xy не пересекаются, то сами многоугольники не пересекаются. Если оболочки пересекаются, то может быть 2 варианта: пересекаются и оболочки и многоугольники, пересекаются оболочки, а многоугольники не пересекаются.

40. HSR: алгоритм сортировки по глубине.

Здесь применяется простой подход, состоящий из 3-х шагов:

1. Упорядочение всех многоугольников в соответствии с их наибольшими z-координатами.

2. Разрешение всех неопределенностей, которые возникают при перекрытии z-оболочек.

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

Основная идея состоит в упорядочении многоугольников в соответствии с их удаленностью от точки зрения, а также в размещении этих многоугольников в буфере регенерации в порядке убывания расстояния. Ближайший многоугольник преобразуется в растровую форму последним и закрывает более отдаленные (Рис. 2).

1) 2) 3)

Рассмотрим виды неопределенностей, связанные с перекрытием z-оболочек (Рис. 3.): Р сравнивается с каждой гранью Q (Рис. 1.). Пусть P – многоугольник с большей z-координатой. Q следует за ним, z-оболочки перекрываются. Разрешить неопределенности можно последовательностью из 5 тестов. Тесты следуют в порядке увеличения сложности. Как только получим утвердительный ответ, многоугольник P преобразуется в растровую форму.

1. x-оболочки многоугольников не перекрываются, поэтому сами многоугольники тоже не перекрываются.

2. y-оболочки многоугольников не перекрываются, поэтому сами многоугольники тоже не перекрываются.

3. P целиком лежит с той стороны от плоскости Q, которая дальше от точки зрения. Необходимо построить уравнение плоскости, в которой лежит Q, в него подставляем точки, лежащие на многоугольнике P. Если результат < 0, точка лежит за плоскостью, если > 0 перед плоскостью.

4. Q целиком находится с той стороны от плоскости P, которая ближе к точке зрения.

5. Проекции многоугольников на плоскость xy (экран) не перекрываются. Необходимо попарно сравнивать ребра двух многоугольников, проверяя, пересекаются их проекции или нет.

Если в первых пяти тестах ответ отрицательный, отсюда следует, что Р действительно закрывает Q и в списке многоугольников их нужно поменять местами.

Чтобы избежать зацикливания в тесте, вводятся ограничения:

· многоугольник, перенесенный в конец списка, не может подвергаться повторному перемещению;

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

Один из недостатков метода - многие многоугольники рисуются бесполезно (могут быть полностью закрашены более верхними многоугольниками).

41. HSR: алгоритм z-буфера. (км)

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

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

Время работы алгоритма не зависит от сложности сцены. Многоугольники, составляющие сцену, могут обрабатываться в произвольном порядке. Для сокращения затрат времени нелицевые многоугольники могут быть удалены.

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

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

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

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

⇐ Предыдущая 3 4 5 6 789 10 11 12 Следующая ⇒