D-алгоритмы виртуальной реальности.

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

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

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

1) высота пола;

2) высота потолка;

3) набор базовых текстур для пола, потолка и боковых граней.

Каждая точка на плоской схеме объектного пространства соответствует вертикальной линии, которая пронизывает объекты сцены, при этом может получаться 3 вида пересечений:

1) две точки;

2) отрезок, при прохождении линии внутри стены;

3) два отрезка при попадании на стык двух стен.

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

всегда по одну сторону от отрезка (рис.7.5).

При этом могут существовать двусторонние отрезки,для которых сектор может

располагаться как слева, так и справа. У нас это отрезок 1-4 или 4-1. С каждой стороной сектора связано текстура, обеспечивающая реалистичное отображение вертикальных сторон. При этом различают 3 вида текстуры, накладываемые на вертикальные поверхности (рис.7.6).

 

1) основные, для заполнения основных стен.

2) нижние текстуры, для заполнения промежутков, соединяющих

полы разного уровня.

3) верхние, позволяющие заполнить расстояние между потолка-

ми разного уровня.

Перед выполнением процедуры рендеринга все секторы преобразуются в выпуклые области по секторам. Кроме того, осуществляется сортировка в порядке удаления от наблюдателя (FTB - процедура).

При построении разбиений и упорядочивания секторов используется 1 из вариантов BSP-дерева

Конец 64 вопроса.
65.3D-алгоритмы виртуальной реальности. Методы порталов и иерархических подсцен.

От 2,5D-алгоритмов данная группа отличается тем, что позволяет обеспечивать следующие возможности:

1) полная 3D-мерность, то есть поддержка шести степеней свободы, реалистичность освещения;

2) поддержка 3D-объектов и новых методов анимации;

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

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

• статические объекты;

• динамические объекты.

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

являются листьями BSP-дерева. Построенное один раз BSP-дерево может неоднократно использоваться в ходе моделирования виртуальной реальности, обеспечивая проход по вершинам в любом направлении. В отличие от 2,5D-алгоритмов, в данном случае для каждого элемента сцены задается параллелепипед. Внутри параллелепипеда присутствует

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

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

из этой области. Данный список носит название списка потенциально видимых граней (Potentially Visible Set - PVS). Использование PVS требует определенных затрат на предварительных этапах работы алгоритмов. Однако, затем присутствие этого списка обеспечивает эффективную работу в реальном времени. Существует множество алгоритмов,которые поддерживают PVS. Для удаления невидимых граней может

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

Метод порталов

Метод порталов позволяет осуществлять построение виртуальной реальности «на лету». Исходная сцена по методу порталов разбивается на множество выпуклых областей. Места соединения между собой, через которые можно видеть область друг из друга, называются порталами. При построении PVS в первую очередь в него заносятся все грани текущей области. На следующем шаге рассматриваются порталы (окна, двери), соединяющие текущую область с соседними. Например, для области А таким порталом является портал 2-31(рис.7.12).

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

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

Метод иерархических подсцен

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

подсцена описывается структурой данных, включающей:

1) описание самой подсцены;

2) описание и характеристики метода визуализации.

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

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

При помощи данного метода можно эффективно реализовать алго-

ритмы визуализации универсального характера, ориентированные на

применение в различных областях и использующие достаточно разно-

родные объекты.

 

Конец 65 вопроса.
66. Текстурирование объектов

Операции наложения текстур на грани моделируемых объектов являются одной из наиболее часто встречаемых операций визуализации 3D-сцен. Алгоритмы наложения текcтур можно классифицировать в зависимости от:

1) вида граней;

2) ориентации граней на экране.

В зависимости от вида граней различают:

1) алгоритмы, ориентированные на текстуризацию полигональных сеток;

2) алгоритмы, ориентированные на текстуризацию сложных поверхностей.

В зависимости от ориентации граней различают алгоритмы, предназначенные для:

1) текстуризации вертикальных граней;

2) текстуризации горизонтальных граней;

3) текстуризации произвольно ориентированных граней.

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

На практике используются нормированные координаты грани, то есть U и V лежат в пределах [0;1]. Чтобы получить индексы для отображаемой текстуры следует произвести элементарные преобразования координат. Конец 66 вопроса.