ФизМатШкола № 30
 

ФизМатШкола № 30
ГРУППА КОМПЬЮТЕРНОЙ ГРАФИКИ
ФИЗИКО-МАТЕМАТИЧЕСКОГО ЛИЦЕЯ № 30

Computer Graphics Support Group
of 30 Phys-Math Lyceum

Tough Dynamics Zone

Авторы:
1.Гриднев МаксимGridnev Maxim10-1 класс
2.Дошина ТатьянаDoshina Tatiana10-1 класс
3.Зенцев ФедорZentsev Fedor11-5 класс
4.Корытько ВикторKoryt;ko Victor11-5 класс
5.Машинский ЛеонидMashinsky Leonid10-1 класс
6.Петрова ТатьянаPetrova Tat'jana10-3 класс
7.Чихиркин СергейChihirkin Sergey11-4 класс
8.Чуринов АндрейChurinov Andrey10-1 класс

Научный руководитель проекта: Галинский Виталий Александрович

Presentation

Аннотация

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

Введение и постановка задачи

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

Система изначально базируется на полигональном представлении трехмерных объектов. Это связано с оптимизацией вывода таких данных современными видеоускорителями [1,2]. При необходимости построения сложных фигур производится их декомпозиция на полигональные объекты. Для удобства разработки система разбита на несколько составных частей. При этом используется объектно-ориентированные методы программирования, что позволяет создавать конечные приложения на основе модулей - объектов - анимации, отложенного вывода, различных подсистем.

Представление и сериализация данных

Все геометрические объекты хранятся виде примитивов, каждый из которых может состоять из линий, точек, треугольников, которые могут быть заданы различными способами (полоса - triangle strip, веер - triangle fan, список - triangle list) или сетки треугольников (grid). Все примитивы задаются массивом вершин, их нормалями и индексов этих вершин, по которым строится вершинный буфер (параметры которого также хранятся в примитиве). Помимо этого каждый примитив хранит указатели на свои текстуры, материал, формат вершин (в нем описывается, какие параметры хранит каждая вершина, например, координаты в пространстве и текстурные координаты).

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

Была реализована система сериализации, оснащенная интерфейсом чтения/записи данных (нами был разработан специальный формат *.tdz, базирующийся на распространенном подходе представления информации в виде порций - chunks [3] - с префиксной нотацией описание содержимого). Система имеет универсальный характер, ее отличает возможность записи различных типов данных (источники света, примитивы, иерархии примитивов, система столкновений объектов и т. д.), различаемых лишь префиксами. Такой подход позволяет сохранить в файл, как всю сцену, так и отдельные ее части и в случае необходимости восстановить сохраненные данные произвольным образом (например, загрузить отдельный примитив, идентифицировав его по имени).

Также имеется возможность преобразования файлов формата RTG (Real Time Game geometry representation files), который поддерживается некоторыми популярными системами моделирования , во внутренний формат системы.

Управление текстурированием

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

Оптимальной стала загрузка текстур из внутреннего формата текстур DirectDraw (DirectDraw Surface *.dds). Различные способы наложения текстур (мультитекстурирование) производятся с помощью средств Direct3D [2]. Система оснащена средствами управления собственными данными и их сериализацией (непосредственно текстурных данных, режимов наложения и прочих текстурных параметров).

Иерархическое моделирование

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

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

Работа с деревом примитивов осуществляется по следующей схеме:

  • Выбор узла.
  • Проведение преобразований над этим узлом и его "детьми".
  • Окончание работы с узлом.

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

Обеспечение ввода с различных устройств

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

Смысл системы состоит в регистрации пользовательских переменных, где переменную заставляют указывать на то изменение состояния указанного устройства ввода, необходимое пользователю, а также приведение ее к нужному диапазону. Интерфейс с низкоуровневыми устройствами ввода осуществляется посредством интерфейса DirectInput8.0 [4].

Анимации и синхронизации по времени

Для удобства разработчика была создана система высокоуровнего моделирования на основе процедурной анимации.

Единицей анимации является объект анимации. Он обладает несколькими свойствами: реагирование на изменение времени и собственного вывода. Также, каждый объект имеет свой приоритет обработки и вывода.

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

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

Обнаружение столкновений объектов

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

Система определения столкновений состоит из нескольких частей:

  • Накапливание информации о треугольниках в режиме последовательного добавления каждого треугольника. На этом этапе не происходит никакого подсчета.
  • Разработчик сообщает о конце потока информации. При этом:
    • система производит подсчет необходимых дополнительных параметров для каждого зарегистрированного треугольника;
    • определяет для каждого зарегистрированного треугольника список вокселей, содержащих его;
    • выделяет память единожды для своих нужд - во-первых, на треугольники и их дополнительные параметры, во-вторых, на воксельную сетку;
    • наконец, все треугольники распределяются по вокселям.
  • В процессе работы приложения пользователь может опросить систему определения столкновений о положении луча или отрезка с геометрией. Пересечение ищется с помощью адаптивного алгоритма Брезенхема [1]. Он состоит в том, что вначале определяется воксель, в котором находится начало луча или отрезка и далее по направлению луча или отрезка определяются воксели. Находясь в каком-то вокселе, система ищет пересечение с каждым треугольником, который помечен, что он находится в данном вокселе. Найдя ближайшее пересечение, система выдаёт ответ.

Подсистема обеспечения звукового сопровождения

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

Звуковой менеджер содержит хранилище звуковых примитивов, созданного во избежание хранения одной и той же информации несколько раз. Каждый звуковой примитив представляет собой объект, созданный для максимально удобного применения различных звуков в программе, содержащий методы проигрыша, такие, как воспроизведение, повтор, пауза, распределение звука на колонках и др. Для взаимодействия с аппаратурой звуковоспроизведения используется интерфейс DirectSound 8.0 [5].

Моделирование и анимация различных эффектов

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

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

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

Заключение

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

Литература

  • Блинова Т.А., Порев В.Н., "Компьютерная графика", Корона Принт ЮНИОР, 2006
  • Frank D. Luna. "Introduction to 3D Game Programming with DirectX 9.0". Wordware Publishing, Inc., 2003
  • Д.Мюррей, У. ван Райпер. "Энциклопедия форматов графических файлов", К.: Издательская группа BHV, 1997
  • Дэвид Конгер, "Физика для разработчиков компьютерных игр", М.: БИНОМ. Лаборатория Знаний, 2007
  • МакКаски М. "Звук в играх: Технологии программирования: Учебно-справочное пособие", М: Кудиц-Образ, 2004.
  • David S. Ebert (ed.), F. Kenton Musgrave, Darwyn Peachey, Ken Perlin, Steven Worley. "Texturing and Modeling. A Procedural Approach", AP Professional, Academic Press, 1994.
  • Рик Пэрент. "Компьютерная анимация". М: Кудиц-Образ, 2004.
  • Дональд Э. Кнут, "Искусство программирования. Том 2. Получисленные алгоритмы", К: Вильямс, 2000
ФМЛ № 30
 
Сайт Физико-математического лицея № 30, Санкт-Петербург, Россия