Московский департамент образования лицей №1533 (информационных технологий) (стр. 1 из 3)

МОСКОВСКИЙ ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ ЛИЦЕЙ №1533 (ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ)

ВЫПУСКНАЯ РАБОТА

(специальность "Прикладное программирование")

учащегося

группы П-11.1 Сикачева Петра Петровича

Демонстрация алгоритма LFM с применением техники анимации алгоритма

Руководитель:	Завриев Н. К.
Консультанты:	Гиглавый А. В.

Москва – 2003

Содержание

	стр.
Введение ………………………………………………………….….	3
1.Постановка задачи…………………………………………………	5
2.Анализ предметной области………………………………………	7
2.1.Структура алгоритма…………….………………………..	7
2.2.Этапы программы lfm_process и программы lfm_view...	12
2.2.1.Входные данные…………………………………...	12
2.2.2.lfm_process – вычисление видимости, повторное квантование, декомпозиция, аппроксимация, тайлинг..	13
2.2.3.lfm_view – рендеринг……………………………...	15
2.3.Методы анимации алгоритмов…………………………...	16
2.3.1.Причины использования анимации алгоритмов…	16
2.3.2.Методы анимации, используемые для анимации LFM……………………………………………………….	16
3.Описание хода работы……………………………………………..	18
3.1.Выбор метода анимации………………………………….	18
3.2.Включение блоков анимации в существующий текст реализации LFM………………………………………………	18
3.3.Разработка собственной программы-демонстрации алгоритма……………………………………………………...	18
3.4.Перечень этапов алгоритма, подлежащих анимации…..	18
4.Описание программы-демонстрации……………………………..	24
Заключение……………………………………………………………	27
Перечень информационных источников…………………………...	28
Благодарности…………………………………………………….….	29
Приложение 1………………………………………………………...	30

Введение

Алгоритм LFM предназначен для эффективного отображения и аппаратно-ускоренной визуализации полей освещенности на поверхности объектов, то есть для освещения их при интерактивном количестве кадров в секунду (interactive frame rates). Этот алгоритм предназначен для рендеринга моделей реального мира, имеющих сложную поверхность: с макро- и микронеровностями. Сам алгоритм был реализован фирмой Intel®, заказчик решил использовать его в курсе «Алгоритмы и численные методы», читаемого в Лицее, как пример достаточно сложного алгоритма из области трехмерной графики.

Алгоритм LFM занимает следующее положение в иерархии графических алгоритмов (дерево неполное):

Рис. 1. Положение LFM в дереве графических алгоритмов

1.Постановка задачи

Целью дипломной работы является создание наглядной и удобной в использовании программы-демонстрации алгоритма. В ходе работы были выявлены следующие задачи:

· создание программы-конвертора, переводящей трехмерные модели в более удобный формат;

· создание демонстрационной программы, которая поддерживает как стандартный вывод графики и текста, так и вывод трехмерных моделей;

· подготовка основы для дальнейшего исследования алгоритма, состоящего в:

- поддержке работы алгоритма с библиотекой трехмерных моделей;

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

Диаграмма распределения частей работы:

Рис. 2. Схема распределения работы

2.Анализ предметной области

2.1 Структура алгоритма

1. Введение

Поле освещенности (далее – ПО) – это функция от 4-х переменных, которая определяется самостоятельно для каждого примитива поверхности:

ƒ (r, s, θ, φ),

где r, s описывают положение точки на поверхности, а θ, φ - возвышение и азимут виртуальной камеры.

Рис. 3. Параметры функции поля освещенности

2. Сбор данных

Для алгоритма нужны следующие данные:

· данные о форме объекта: сканирование геометрии модели

Рис. 4. Сбор информации о геометрии

· данные о цвете/освещенности поверхности под разными углами (информация о поле освещенности): получение 200-400 фотографий модели посредством ручной фотокамеры

Рис. 5. Сбор информации об освещенности

· Соотнесение фотографий и геометрии с помощью специальных файлов

3. Определение видимости для треугольников

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

4. Повторное квантование данных

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

Рис. 6. Триангуляция по Делоне

Слева – исходные виды на полусфере видов, в центре – триангуляция исходных видов по Делоне, справа – вычисление промежуточных видов посредством интерполяции и смешения (blending).

5. Декомпозиция поля освещенности

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

Каждая текстура, соответствующая данному виду и данному треугольнику раскладывается на три текстуры, каждая из которых «приписывается» вершинам треугольника; в сумме они равны исходной текстуре.

Рис. 7. Декомпозиция поля освещенности

Пусть цвет (ПО) в данной точке – f. Тогда цвет этой точке на текстуре, соответствующей вершине V1 будет:

f*S1/(S1+S2+S3)

Аналогично для текстур, соответствующих вершинам V1 и V2.

Рис. 8. Барицентрические веса

6. Аппроксимация

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

Рис. 9. Матрица освещенности для одного треугольника

Полученная матрица факторизуется – раскладывается в сумму нескольких произведений (в рамках LFM – не более 3).

Рис. 10. Аппроксимация посредством факторизации

Итак, формула ƒ (r, s, θ, φ) теперь выглядит следующим образом:

Рис. 11. Формула факторизации

где:

Pi – текущий примитив

gk – карта поверхности шага аппроксимации k

hk – карта вида шага аппроксимации k

r, s – текстурные координаты

θ, φ – возвышение и азимут виртуальной камеры

N – количество шагов аппроксимации

7. Рендеринг

Схема рендеринга одного треугольника:

Рис. 12. Схема рендеринга

2.2 Этапы программы lfm_process и программы lfm_view

2.2.1.Входные данные

· Данные о геометрии модели

Для этой цели служит специальный файл с расширением .obj.

Описание формата:

<v, f, другой символ – строка не анализируется> <число: v – формата float C++, f – целочисленного формата> <число: v – формата float C++, f – целочисленного формата> <число: v – формата float C++, f – целочисленного формата><символ перевода каретки (‘&bsol;n’ в C++)>

Если буква – ‘v’, последующие три числа – координаты вершины; если буква – ‘f’, последующие три числа – три индекса массива вершин, три вершины данного треугольника.

· Данные о поле освещенности

Файл в формате .bmp.

· Соотнесение геометрии и данных о ПО

Файл калибрации в формате .txt.

Описание формата:

-

2.2.2.lfm_process – вычисление видимости, повторное квантование, декомпозиция, аппроксимация, тайлинг

Главный алгоритм программы (помимо всяческих инициализаций/очистки и проверок) выглядит следующим образом:

1. ReadCalibFile();

2. ParseSDF();

3. GenVerInfo();

4. CalcVisibility();

5. ResampleLF();

6. CheckResampling();

7. CalcDecomp();

8. TileToImage();

1. Чтение файлов калибрации и их переписывание в один файл

2. Анализ файла .obj

3. Вычисление нормалей для треугольников и вершин