Разработка компьютерных игр
Можно ли говорить о том, что скоро игры приблизятся по реальности "картинки" к обычному кино? Да. Можно ли сказать о том, что компьютерные и видеоигры частично заменят кино в сфере шоу-бизнеса? Опять же, да. А можно ли сказать, что игры — это новое поколение после кино? Трижды да. На этом и остановимся.
Кстати, достаточно интересно поступили разработчики из Blizzard, сделав из Starcraft 2 трилогию, каждая часть которой будет выходить отдельно. И хотя на всевозможных форумах можно найти и недовольные высказывания, но все же большей частью все восхищены глобальностью поведения великой компании. Ведь ее продукты в рамках геймдева всегда были эпохальными и во многом определяли дальнейшее движение этого рынка. На данный момент меняется сама концепция представления игр как таковых. То есть они становятся больше не программными, а медийными продуктами.
Ну, а мы возвращаемся к нашим реалиям, то есть изложению основ…
В прошлом материале мы сказали о том, что Direct3D как бы заботится о разработчиках, взяв на свои плечи множество рутинных задач. И это так. Например, мы начали говорить о поверхностях, ключевых буферах и так далее. А вообще можно поинтересоваться, где все это хранится физически и как? Здесь вроде бы все понятно: видеопамять, системная память, память AGP, но каким образом идет распределение ресурсов между ними? Где и как это можно указать? Причем и разрабатываем-то мы не для одного компьютера с конкретным и известным видеоадаптером, а для множества РС-совместимых. На самом деле вопрос решается достаточно тривиально, в стиле объектноориентированного подхода. Вернее, того подхода, который нам прививает общение с Direct3D. Все ответы можно найти, открыв Help к DirectX SDK и набрав ключевое слово поиска "D3DPOOL". D3DPOOL подразумевает перечисление констант, которые указывают на варианты (методы) использования пулов памяти. Смотрим листинг-содержание:
typedef enum D3DPOOL
{
D3DPOOL_DEFAULT = 0,
D3DPOOL_MANAGED = 1,
D3DPOOL_SYSTEMMEM = 2,
D3DPOOL_SCRATCH = 3,
D3DPOOL_FORCE_DWORD = 0x7fffffff,
} D3DPOOL, *LPD3DPOOL;
Теперь рассмотрим все подробнее. Для начала скажем одну важную вещь: эффективное управление памятью выражается в ограничении общего количества операций по ее выделению. Именно поэтому выгодно объединять схожие объекты в группы для выделения большего объема пространства. Таким образом, формируются пулы данных, которые являются не чем иным, как контейнерами для множественных объектов. Direct3D предлагает свою организацию работы с ними, причем в этом случае он не только помогает в силу автоматизации, но и позволяет избежать ошибок неопытным специалистам.
D3DPOOL_DEFAULT — Direct3D размещает тот или иной ресурс только в ту область памяти, которая по умолчанию для него (этого ресурса) предназначена. Этот метод требует освобождения выделенных ресурсов перед сбросом устройства Direct3D. Он уместен далеко не для всех случаев, и, как говорится в той же документации, большинство приложений вместо него используют следующий вариант.
D3DPOOL_MANAGED является более совершенным, и в данном случае работа идет уже с управляемым пулом памяти Direct3D. При необходимости данные могут перемещаться по различным областям, к тому же, в системной памяти хранится резервная копия ресурса. При необходимости доступа и внесения изменений работа идет именно в ней, после чего обновляются данные в видеопамяти. Метод позволяет выполнять сброс устройства без предварительного принудительного освобождения управляемой памяти.
Название D3DPOOL_SYSTEMMEM говорит само за себя, а именно: ресурс хранится в системной памяти, но с учетом всех налагаемых графическим устройством ограничений. Созданные ресурсы не требуется освобождать перед сбросом устройства.
Вариант D3DPOOL_ SCRATCH подразумевает все то же хранение в системной памяти, но уже без учета этих ограничений, причем ресурсы данного типа недоступны для устройства Direct3D, но их можно создавать, блокировать и копировать.
Более подробно на этих вопросах мы остановимся позже, то есть вы должны просто представить, где все может создаваться, храниться, изменяться и т.п., а сегодня мы поговорим по другой теме.
Допустим, вы отображаете сферу на каком-либо фоне (или даже рисуете окружность в 2D-пакете). Вроде бы самый примитивный случай, стандартная операция… для нас, но не для машины, которой нужно объяснить, что находится спереди, а что позади, что отображать, а что — нет. Для нас понятие "перекрытия" ближним предметом дальнего естественно. В программах 3D-проектирования, равно как и в Direct3D, при визуализации сцен предусмотрены специальные технологические решения по определению дальности предметов и выделению видимых областей. Ведь мы говорим не только о предмете и фоне, а о сценах с множеством объектов.
Z-буферизация
В Direct3D под эти цели выделяется отдельный буфер глубины (depth buffer). По существу, он подразумевает хранение окончательного отображения поверхности с уже готовыми вариантами расчетов по оси Z. При этом мы говорим о вычислениях для каждого пикселя, который является результатом сравнения всех пикселей, ему соотвествующих по оси Z, и за окончательное значение принимается тот, который расположен наиболее близко к камере. Поскольку мы говорим об оси Z, то часто применяется термин Z-буферизации (z-buffering). При этом не совсем верно называть z-буфером конкретно буфер глубины, хотя это достаточно условное ограничение. Какова причина сказанного? Именно в DirectX 9 (в 10-й этого нет) вы можете встретить специальные форматы для буфера глубины — они интересны в рассмотрении, хотя бы для того, чтобы вы себе представляли, как примерно работает визуализация. Стоит сказать, что этот формат указывает на точность сравнения. Итак:
• D3DFMT_D32 — 32-разрядный z-буфер глубины.
• D3DFMT_D15S1 — 16-разрядный z-буфер, в котором 15 бит зарезервировано для глубины, и 1 бит — для трафарета.
• D3DFMT_D24S8 — 32-разрядный z-буфер, в котором 24 бита зарезервировано для глубины, и 8 бит — для трафарета.
• D3DFMT_D24X8 — 32-разрядный z-буфер, в котором 24 бита зарезервировано для глубины.
• D3DFMT_D24X4S4 — 32-разрядный z-буфер, в котором 24 бита зарезервировано для глубины, и 4 бита — для трафарета.
То есть на самом деле принято разделять буфер глубины (depth buffer) и буфер трафарета (stencil buffer). Последний подразумевает под собой достаточно простую операцию, а его название говорит само за себя.
Как происходит z-буферизация?
По существу сначала идет тривиальное движение по пунктам:
1. Заполняем буфер поверхности фоновым цветом.
2. Заполняем Z-буфер (далее Zб) минимальным значением z (глубины).
3. Преобразуем изображаемые объекты в растровую форму.
Потом наступает следующий черед вычислений для каждого объекта в отдельности:
1. Вычисляем для каждого пикселя образа z(x, y).
2. Если z(x,y) > Zб(x,y), то присваиваем Zб(x,y) значение z(x,y). Все.
Вроде бы все просто, но ответьте на вопрос: много ли вы видели в играх под Direct3D прозрачных и полупрозрачных элементов?
Работа с вершинами
Как мы уже много раз говорили ранее, основными кирпичиками трехмерных моделей являются вершины, которые соединяются между собой по полигональным примитивам — треугольникам. По существу, вершины — это конкретные точки, правда, в рамках Direct3D их формат предусматривает наличие множества дополнительной информации, о чем мы также подробно говорили. Давайте сейчас представим ситуацию, когда нам нужно создать изображение четырехугольника. Нетрудно догадаться, что он будет представляться четырьмя уникальными вершинами и, соответственно, двумя треугольниками, часть из которых имеют общие вершины. Для того, чтобы показать, каким образом модель разбита на треугольники, проще всего оперировать индексами. То есть на самом деле должно быть два списка: вершин и индексов. Например:
Vertex vertexList[4] = {v0, v1, v2, v3};
WORD indexList[6] = {0, 1, 2,
// треугольник 0
0, 2, 3};
// треугольник 1
То есть здесь все становится более очевидным. Обратите внимание на порядок задания вершин при указании треугольников — на самом деле он очень важен — именуется порядком обхода (winding order). Пример с прямоугольником тривиален, но если вы, например, представите куб, то у вас будет уже восемь уникальных вершин, но при этом сама фигура разбивается на 12 треугольников. То есть чем сложнее структура, тем более удобна система индексов. Мало того, если мы начнем отображать куб в трехмерном виде и сделаем визуализацию, то те грани, у которых порядок обхода вершин идет по часовой стрелке, окажутся видимыми, а те, у которых против часовой — невидимыми. Ведь, как понятно, при повороте треугольника на 180 градусов его порядок обхода вершин будет меняться на противоположный. Часть граней направлены на камеру, а другая часть — от нее. Это очень важно при операции удаления невидимых поверхностей. Например, фигура повернулась, а что это значит для нас? Некоторые грани стали видны, а другие, наоборот, "спрятались". Причем в рамках удаления невидимых поверхностей применимы два термина: фронтальный полигон (front facing polygon) и обратный полигон (back spa-cing polygon).
Конвейер визуализации
Итак, наконец, мы подошли к списку операций, характеризующих процесс рендеринга (визуализации). Идет все поэтапно, в нашем списке сверху вниз:
• Локальное пространство. Моделирование каждого объекта в его системе координат.
• Мировое пространство. Сборка множества моделей в рамках мировой системы координат.
• Преобразование в пространство вида. Переход к системе координат, связанной с видом проекции (расположению виртуальной камеры — она становится началом координат, причем ось Z становится прямо направленной от зрителя).
• Удаление невидимых поверхностей. Это то, о чем сказано в конце предыдущего подраздела.
• Освещение.
• Отсечение в рамках видимой области экрана. То есть убираются те треугольники, которые находятся вне поля видимости виртуальной камеры, а те, через которые проходит граница зоны видимости, разбиваются на части (видимую и невидимую).
• Переход от 3D-представления к 2D. Эта операция называется проекцией (projection).
• Преобразование порта просмотра, а именно переход в систему координат вывода на экран. Например, если у вас не полноэкранный режим, а оконный либо предусмотрена специальная клиентская область.
• Растеризация, то есть закрашивание двухмерных треугольников.
Значимая часть перечисленных пунктов предусматривают матричные преобразования — особенно это касается всех изменений сеток координат, перехода от 3D к 2D и т.д. Большинство сложных вычислений Direct3D берет на себя — вернее, он берет на себя управление этими процессами, а на самом деле львиная доля работы возлагается на плечи графического адаптера. Как вы могли заметить, сама алгоритмическая структура расположена к как можно большему удержанию картины в трехмерном представлении. При этом всего получается четыре системы координат:
• Локальная (объекта).
• Мировая (глобальная).
• Камеры (обзора).
• Экрана.
Часть операций визуализации, реализуемых за счет алгоритмической структуры Direct3D и непосредственно графического адаптера, являются закрытыми для программиста. В принципе, в этом есть определенный смысл. Главное — чтобы работало:). Хотя на некоторых моментах имеет смысл остановиться отдельно — для того, чтобы вы понимали: предложения Direct3D не единственны в своем роде.
Два подхода
Вообще в рамках отсечения невидимых поверхностей существует два ключевых подхода. Один подразумевает анализ объектов в рамках трехмерной сцены, разделяя грани по принципу лицевая/нелицевая, второй вычисляет пиксели по дальности с отображением ближнего. Первый подход позволяет значительно упростить расчеты, поскольку отсекается огромное количество граней, некоторые из них дробятся, второй удобен при дальнейших расчетах.
Первый…
Если говорить о гранях, то вариант указания вершин по часовой стрелке и отсечение тех, у кого они начинают следовать против часовой — самый простой и топорный метод. На самом деле есть более сложные методологические реализации, например, с вычислением нормалей граней. Если они направлены к зрителю, то угол каждой из них к обратной оси просмотра является острым, а если от зрителя, то тупым. Данный метод достаточно часто используется в системах визуализации, например, в той же OpenGL и в очень многих графических 3D-пакетах, причем не важно, из каких многоугольников составлены полигоны.
Еще один метод уже предусматривает триангуляцию (разбиение граней на треугольники), после чего создается список новых треугольных граней и список ребер. Затем все анализируется по специальной методике: те ребра или грани, которые экранируются самим телом, являются невидимыми, причем тест достаточно простой в описании (если одна или обе смежные грани обращены своей внешней поверхностью к наблюдателю, то ребро является видимым) и элегантен с математической точки зрения (вычисление скалярного произведения координат наблюдателя на вектор внешней нормали грани). По существу это примерно то же самое, что было описано перед этим. Данный алгоритм называется алгоритмом Робертса и впервые был представлен в 1963 году.
Второй…
Что касается пиксельного подхода к определению дальности, то алгоритм z-буферизации, который был впервые предложен Кэтмулом в 1975 г., не является самым оптимальным с точки зрения расчетов, но он предельно прост, поэтому и используется. Есть алгоритм Варнака (1968), в рамках которого предусмотрено дробление экрана на четыре равные части, после чего происходит следующее сравнение:
1. Выделенная часть экрана полностью перекрывается проекцией ближайшей грани.
2. Выделенная часть экрана не накрывается проекцией ни одной из граней.
3. Ни первое, ни второе условия не выполняются.
Причем данные три пункта уже оптимизированы программистами, в классическом представлении их шесть. Алгоритм достаточно интересен. В первом случае выделенная часть экрана закрашивается цветом грани, во втором случае цветом фона, в третьем случае эта часть опять дробится на четыре равных, и дальнейшие сравнения происходят по тому же принципу. Дробление может производиться вплоть до одного пикселя. На самом деле, это удобно.
В 1977 году алгоритм Варнака попытались оптимизировать Вейлер и Айзертон с применением сортировки по глубине. Данный метод интересен только с той точки зрения, что в 1974 году его обобщил все тот же Кэтмул для изображения гладких бикубических поверхностей, и сейчас он применяется для отображения сплайновых поверхностей. Впрочем, арсенал Direct3D не позволяет работать со сплайнами, поэтому данный вопрос интересен только с точки зрения моделирования в профессиональных графических 3D-пакетах.
Есть и еще один очень интересный метод, который называется алгоритмом построчного сканирования, предложенный в 1967 г. Уайли, Ромни, Эвансом и Эрдалом. Кстати, возможно, именно он придет на смену z-буферизации в силу простоты представления и уникальности, а может, и смешается с z-буферизацией.
Да, и объяснять его не сложно. Трехмерная сцена построчно сканируется с точки зрения виртуальной камеры, так, как бы это делал лазерный сканер. То есть в этом случае нам не нужно досконально обрабатывать трехмерную сцену. К сожалению, данный метод был достаточно плохо развит впоследствии, хотя дает огромные перспективы. Ведь на самом деле не нужно анализировать ситуацию с границами экрана (сканируемые строки имеют конкретную длину), трехмерное представление ближайшего окружения также будет упрощено, и при нормальном продвижении (так, как лично я его вижу в идеале) отпадет необходимость даже в отсечении невидимых поверхностей. На сегодня мы имеем другие стандарты.
Есть и еще несколько уникальных алгоритмов, сейчас представляющих большей частью теоретический интерес. Но многое из вышеизложенного вполне может использоваться в алгоритмах визуализации для 3D-пакетов.
Алгоритмы, схожие с тем, что предложил Варнак, используются не только в этой сфере, есть очень схожие методы поиска по карте с использованием квадра- и октодеревьев. С ними вы можете встретиться при самостоятельном написании игрового движка.
Тестовое задание: на базе вышеизложенного и собственных знаний попробуйте ответить на вопрос: каким образом происходит визуализация прозрачных и полупрозрачных объектов?
Продолжение следует
Кристофер, christopher@tut.by
Кстати, достаточно интересно поступили разработчики из Blizzard, сделав из Starcraft 2 трилогию, каждая часть которой будет выходить отдельно. И хотя на всевозможных форумах можно найти и недовольные высказывания, но все же большей частью все восхищены глобальностью поведения великой компании. Ведь ее продукты в рамках геймдева всегда были эпохальными и во многом определяли дальнейшее движение этого рынка. На данный момент меняется сама концепция представления игр как таковых. То есть они становятся больше не программными, а медийными продуктами.
Ну, а мы возвращаемся к нашим реалиям, то есть изложению основ…
В прошлом материале мы сказали о том, что Direct3D как бы заботится о разработчиках, взяв на свои плечи множество рутинных задач. И это так. Например, мы начали говорить о поверхностях, ключевых буферах и так далее. А вообще можно поинтересоваться, где все это хранится физически и как? Здесь вроде бы все понятно: видеопамять, системная память, память AGP, но каким образом идет распределение ресурсов между ними? Где и как это можно указать? Причем и разрабатываем-то мы не для одного компьютера с конкретным и известным видеоадаптером, а для множества РС-совместимых. На самом деле вопрос решается достаточно тривиально, в стиле объектноориентированного подхода. Вернее, того подхода, который нам прививает общение с Direct3D. Все ответы можно найти, открыв Help к DirectX SDK и набрав ключевое слово поиска "D3DPOOL". D3DPOOL подразумевает перечисление констант, которые указывают на варианты (методы) использования пулов памяти. Смотрим листинг-содержание:
typedef enum D3DPOOL
{
D3DPOOL_DEFAULT = 0,
D3DPOOL_MANAGED = 1,
D3DPOOL_SYSTEMMEM = 2,
D3DPOOL_SCRATCH = 3,
D3DPOOL_FORCE_DWORD = 0x7fffffff,
} D3DPOOL, *LPD3DPOOL;
Теперь рассмотрим все подробнее. Для начала скажем одну важную вещь: эффективное управление памятью выражается в ограничении общего количества операций по ее выделению. Именно поэтому выгодно объединять схожие объекты в группы для выделения большего объема пространства. Таким образом, формируются пулы данных, которые являются не чем иным, как контейнерами для множественных объектов. Direct3D предлагает свою организацию работы с ними, причем в этом случае он не только помогает в силу автоматизации, но и позволяет избежать ошибок неопытным специалистам.
D3DPOOL_DEFAULT — Direct3D размещает тот или иной ресурс только в ту область памяти, которая по умолчанию для него (этого ресурса) предназначена. Этот метод требует освобождения выделенных ресурсов перед сбросом устройства Direct3D. Он уместен далеко не для всех случаев, и, как говорится в той же документации, большинство приложений вместо него используют следующий вариант.
D3DPOOL_MANAGED является более совершенным, и в данном случае работа идет уже с управляемым пулом памяти Direct3D. При необходимости данные могут перемещаться по различным областям, к тому же, в системной памяти хранится резервная копия ресурса. При необходимости доступа и внесения изменений работа идет именно в ней, после чего обновляются данные в видеопамяти. Метод позволяет выполнять сброс устройства без предварительного принудительного освобождения управляемой памяти.
Название D3DPOOL_SYSTEMMEM говорит само за себя, а именно: ресурс хранится в системной памяти, но с учетом всех налагаемых графическим устройством ограничений. Созданные ресурсы не требуется освобождать перед сбросом устройства.
Вариант D3DPOOL_ SCRATCH подразумевает все то же хранение в системной памяти, но уже без учета этих ограничений, причем ресурсы данного типа недоступны для устройства Direct3D, но их можно создавать, блокировать и копировать.
Более подробно на этих вопросах мы остановимся позже, то есть вы должны просто представить, где все может создаваться, храниться, изменяться и т.п., а сегодня мы поговорим по другой теме.
Допустим, вы отображаете сферу на каком-либо фоне (или даже рисуете окружность в 2D-пакете). Вроде бы самый примитивный случай, стандартная операция… для нас, но не для машины, которой нужно объяснить, что находится спереди, а что позади, что отображать, а что — нет. Для нас понятие "перекрытия" ближним предметом дальнего естественно. В программах 3D-проектирования, равно как и в Direct3D, при визуализации сцен предусмотрены специальные технологические решения по определению дальности предметов и выделению видимых областей. Ведь мы говорим не только о предмете и фоне, а о сценах с множеством объектов.
Z-буферизация
• D3DFMT_D32 — 32-разрядный z-буфер глубины.
• D3DFMT_D15S1 — 16-разрядный z-буфер, в котором 15 бит зарезервировано для глубины, и 1 бит — для трафарета.
• D3DFMT_D24S8 — 32-разрядный z-буфер, в котором 24 бита зарезервировано для глубины, и 8 бит — для трафарета.
• D3DFMT_D24X8 — 32-разрядный z-буфер, в котором 24 бита зарезервировано для глубины.
• D3DFMT_D24X4S4 — 32-разрядный z-буфер, в котором 24 бита зарезервировано для глубины, и 4 бита — для трафарета.
То есть на самом деле принято разделять буфер глубины (depth buffer) и буфер трафарета (stencil buffer). Последний подразумевает под собой достаточно простую операцию, а его название говорит само за себя.
Как происходит z-буферизация?
По существу сначала идет тривиальное движение по пунктам:
1. Заполняем буфер поверхности фоновым цветом.
2. Заполняем Z-буфер (далее Zб) минимальным значением z (глубины).
3. Преобразуем изображаемые объекты в растровую форму.
Потом наступает следующий черед вычислений для каждого объекта в отдельности:
1. Вычисляем для каждого пикселя образа z(x, y).
2. Если z(x,y) > Zб(x,y), то присваиваем Zб(x,y) значение z(x,y). Все.
Вроде бы все просто, но ответьте на вопрос: много ли вы видели в играх под Direct3D прозрачных и полупрозрачных элементов?
Работа с вершинами
Vertex vertexList[4] = {v0, v1, v2, v3};
WORD indexList[6] = {0, 1, 2,
// треугольник 0
0, 2, 3};
// треугольник 1
То есть здесь все становится более очевидным. Обратите внимание на порядок задания вершин при указании треугольников — на самом деле он очень важен — именуется порядком обхода (winding order). Пример с прямоугольником тривиален, но если вы, например, представите куб, то у вас будет уже восемь уникальных вершин, но при этом сама фигура разбивается на 12 треугольников. То есть чем сложнее структура, тем более удобна система индексов. Мало того, если мы начнем отображать куб в трехмерном виде и сделаем визуализацию, то те грани, у которых порядок обхода вершин идет по часовой стрелке, окажутся видимыми, а те, у которых против часовой — невидимыми. Ведь, как понятно, при повороте треугольника на 180 градусов его порядок обхода вершин будет меняться на противоположный. Часть граней направлены на камеру, а другая часть — от нее. Это очень важно при операции удаления невидимых поверхностей. Например, фигура повернулась, а что это значит для нас? Некоторые грани стали видны, а другие, наоборот, "спрятались". Причем в рамках удаления невидимых поверхностей применимы два термина: фронтальный полигон (front facing polygon) и обратный полигон (back spa-cing polygon).
Конвейер визуализации
Итак, наконец, мы подошли к списку операций, характеризующих процесс рендеринга (визуализации). Идет все поэтапно, в нашем списке сверху вниз:
• Локальное пространство. Моделирование каждого объекта в его системе координат.
• Мировое пространство. Сборка множества моделей в рамках мировой системы координат.
• Преобразование в пространство вида. Переход к системе координат, связанной с видом проекции (расположению виртуальной камеры — она становится началом координат, причем ось Z становится прямо направленной от зрителя).
• Удаление невидимых поверхностей. Это то, о чем сказано в конце предыдущего подраздела.
• Освещение.
• Отсечение в рамках видимой области экрана. То есть убираются те треугольники, которые находятся вне поля видимости виртуальной камеры, а те, через которые проходит граница зоны видимости, разбиваются на части (видимую и невидимую).
• Переход от 3D-представления к 2D. Эта операция называется проекцией (projection).
• Преобразование порта просмотра, а именно переход в систему координат вывода на экран. Например, если у вас не полноэкранный режим, а оконный либо предусмотрена специальная клиентская область.
• Растеризация, то есть закрашивание двухмерных треугольников.
Значимая часть перечисленных пунктов предусматривают матричные преобразования — особенно это касается всех изменений сеток координат, перехода от 3D к 2D и т.д. Большинство сложных вычислений Direct3D берет на себя — вернее, он берет на себя управление этими процессами, а на самом деле львиная доля работы возлагается на плечи графического адаптера. Как вы могли заметить, сама алгоритмическая структура расположена к как можно большему удержанию картины в трехмерном представлении. При этом всего получается четыре системы координат:
• Локальная (объекта).
• Мировая (глобальная).
• Камеры (обзора).
• Экрана.
Часть операций визуализации, реализуемых за счет алгоритмической структуры Direct3D и непосредственно графического адаптера, являются закрытыми для программиста. В принципе, в этом есть определенный смысл. Главное — чтобы работало:). Хотя на некоторых моментах имеет смысл остановиться отдельно — для того, чтобы вы понимали: предложения Direct3D не единственны в своем роде.
Два подхода
Вообще в рамках отсечения невидимых поверхностей существует два ключевых подхода. Один подразумевает анализ объектов в рамках трехмерной сцены, разделяя грани по принципу лицевая/нелицевая, второй вычисляет пиксели по дальности с отображением ближнего. Первый подход позволяет значительно упростить расчеты, поскольку отсекается огромное количество граней, некоторые из них дробятся, второй удобен при дальнейших расчетах.
Первый…
Если говорить о гранях, то вариант указания вершин по часовой стрелке и отсечение тех, у кого они начинают следовать против часовой — самый простой и топорный метод. На самом деле есть более сложные методологические реализации, например, с вычислением нормалей граней. Если они направлены к зрителю, то угол каждой из них к обратной оси просмотра является острым, а если от зрителя, то тупым. Данный метод достаточно часто используется в системах визуализации, например, в той же OpenGL и в очень многих графических 3D-пакетах, причем не важно, из каких многоугольников составлены полигоны.
Еще один метод уже предусматривает триангуляцию (разбиение граней на треугольники), после чего создается список новых треугольных граней и список ребер. Затем все анализируется по специальной методике: те ребра или грани, которые экранируются самим телом, являются невидимыми, причем тест достаточно простой в описании (если одна или обе смежные грани обращены своей внешней поверхностью к наблюдателю, то ребро является видимым) и элегантен с математической точки зрения (вычисление скалярного произведения координат наблюдателя на вектор внешней нормали грани). По существу это примерно то же самое, что было описано перед этим. Данный алгоритм называется алгоритмом Робертса и впервые был представлен в 1963 году.
Второй…
Что касается пиксельного подхода к определению дальности, то алгоритм z-буферизации, который был впервые предложен Кэтмулом в 1975 г., не является самым оптимальным с точки зрения расчетов, но он предельно прост, поэтому и используется. Есть алгоритм Варнака (1968), в рамках которого предусмотрено дробление экрана на четыре равные части, после чего происходит следующее сравнение:
1. Выделенная часть экрана полностью перекрывается проекцией ближайшей грани.
2. Выделенная часть экрана не накрывается проекцией ни одной из граней.
3. Ни первое, ни второе условия не выполняются.
Причем данные три пункта уже оптимизированы программистами, в классическом представлении их шесть. Алгоритм достаточно интересен. В первом случае выделенная часть экрана закрашивается цветом грани, во втором случае цветом фона, в третьем случае эта часть опять дробится на четыре равных, и дальнейшие сравнения происходят по тому же принципу. Дробление может производиться вплоть до одного пикселя. На самом деле, это удобно.
В 1977 году алгоритм Варнака попытались оптимизировать Вейлер и Айзертон с применением сортировки по глубине. Данный метод интересен только с той точки зрения, что в 1974 году его обобщил все тот же Кэтмул для изображения гладких бикубических поверхностей, и сейчас он применяется для отображения сплайновых поверхностей. Впрочем, арсенал Direct3D не позволяет работать со сплайнами, поэтому данный вопрос интересен только с точки зрения моделирования в профессиональных графических 3D-пакетах.
Есть и еще один очень интересный метод, который называется алгоритмом построчного сканирования, предложенный в 1967 г. Уайли, Ромни, Эвансом и Эрдалом. Кстати, возможно, именно он придет на смену z-буферизации в силу простоты представления и уникальности, а может, и смешается с z-буферизацией.
Да, и объяснять его не сложно. Трехмерная сцена построчно сканируется с точки зрения виртуальной камеры, так, как бы это делал лазерный сканер. То есть в этом случае нам не нужно досконально обрабатывать трехмерную сцену. К сожалению, данный метод был достаточно плохо развит впоследствии, хотя дает огромные перспективы. Ведь на самом деле не нужно анализировать ситуацию с границами экрана (сканируемые строки имеют конкретную длину), трехмерное представление ближайшего окружения также будет упрощено, и при нормальном продвижении (так, как лично я его вижу в идеале) отпадет необходимость даже в отсечении невидимых поверхностей. На сегодня мы имеем другие стандарты.
Есть и еще несколько уникальных алгоритмов, сейчас представляющих большей частью теоретический интерес. Но многое из вышеизложенного вполне может использоваться в алгоритмах визуализации для 3D-пакетов.
Алгоритмы, схожие с тем, что предложил Варнак, используются не только в этой сфере, есть очень схожие методы поиска по карте с использованием квадра- и октодеревьев. С ними вы можете встретиться при самостоятельном написании игрового движка.
Тестовое задание: на базе вышеизложенного и собственных знаний попробуйте ответить на вопрос: каким образом происходит визуализация прозрачных и полупрозрачных объектов?
Продолжение следует
Кристофер, christopher@tut.by
Компьютерная газета. Статья была опубликована в номере 46 за 2008 год в рубрике технологии
