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

МОСКОВСКИЙ ДЕПАРТАМЕНТ ОБРАЗОВАНИЯ

ЛИЦЕЙ №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.Анализ предметной области

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

Введение

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

ƒ (r, s, θ, φ),

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



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

Сбор данных

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

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

		

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

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

		

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

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

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

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

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

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



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

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

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

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

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



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

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

f*S1/(S1+S2+S3)

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



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



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

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





точ ки на примитиве

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

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



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



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



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

где:

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

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

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

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

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

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



Рендеринг

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



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

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

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

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

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

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

<v, f, другой символ – строка не анализируется> <число: v – формата float C++, f – целочисленного формата> <число: v – формата float C++, f – целочисленного формата> <число: v – формата float C++, f – целочисленного формата><символ перевода каретки (‘\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. Вычисление нормалей для треугольников и вершин

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

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

Для удобства хранения треугольников в текстурах выполняется следующая операция:

•Выбирается вид, при котором треугольник имеет максимальный размер

•Треугольник приводится к равнобедренному прямоугольному треугольнику одного из фиксированных размеров в зависимости от его размера (определяется в предыдущем пункте)



Рис. 13. Повторное квантование треугольлника



6. Проверка правильности вычислений на предыдущем этапе (проверка наличия всех *.mat-файлов, проверка правильности матриц в этих файлах и т. п.).

7. Вычисляет факторизацию:

	

Рис. 14. Формула факторизации для одного примитива

Число K в рамках алгоритма не превосходит 3. Подробнее о факторизации см. в пункте 2.2 главы 2. Текст процедуры см. в Приложении 1. 

Существует три способа факторизации: NMF (Non-negative matrix factorization), SVD (≡PCA (Principal component analysis)), FACTOR4 (нет описания, сходен с SVD). Отличаются они такими качествами как качество разложения (точность, количество шагов аппроксимации) и неотрицательность получаемых векторов (важно для тайлинга и рендеринга).

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



Рис. 15. Карты поверхности (слева) и карты вида (справа)

Карты поверхности слева, вида – справа. Карты поверхности также располагаются в текстурах согласно их размеру. См. пункт 5.

2.2.3.lfm_view – рендеринг

Полный рендеринг производится по следующей схеме:



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

Но эта схема не совсем верна. На самом деле рендеринг выглядит так (gi – карта поверхности, относящаяся к i-ому шагу аппроксимации, hi – карта вида, относящаяся к i-ому шагу аппроксимации):

ƒ∆ = g1+g1*h1+g2*h2+…+gK*hK, где K – количество шагов аппроксимации.




2.3	Методы анимации алгоритмов

2.3.1.Причины использования анимации алгоритмов

Термин "анимация алгоритмов" означает наглядное динамическое изображение, демонстрирующее функциональные шаги алгоритма. Цели методики, обозначаемой этим термином следующие: 

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

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



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

2.3.2.Методы анимации, используемые для анимации LFM

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

		изучение алгоритма решения задачи на фиксированных начальных данных (демонстрационная версия), 

		задание различных начальных данных и изучение их влияния на работу алгоритма и результаты решения

В пункте 3.4 подробно описан сценарий анимации с указанием вышеизложенных уровней взаимодействия.
3.	Описание хода работы

3.1	Выбор метода анимации

Существует 2 метода анимации алгоритма: включение блоков анимации в существующий текст реализации LFM и разработка собственной программы-демонстрации алгоритма.



		Включение блоков анимации в существующий текст реализации LFM

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



		Разработка собственной программы-демонстрации алгоритма

Главный минус разработки собственной программы – неполная интерактивность, а также недостоверность некоторых фрагментов. Однако разработка собственной программы дает возможность реализовать приемлемые вывод графики и текста и пользовательский интерфейс. Поэтому такая программа более наглядна для незнакомого с алгоритмом пользователя. Таким образом, был выбран метод создания собственной программы-демонстрации алгоритма.

3.4.	Перечень этапов алгоритма, подлежащих анимации

Одной из самых наглядных статей в силу наглядных изображений стала статья Роберта Ричмонда (Robert Richmond) с интернет-сайта Romulus 2 (см. Перечень источников). Поэтому было принято решение выбрать стадии алгоритма для анимации, опираясь на этот документ, в особенности – на изображения. Ниже приведен список этапов анимации с пояснениями и указанием степени интерактивности:



Рис. 17. Поле освещенности

Постепенно на экране появляются:

		Поверхность (треугольник)

		Точка на ней

		Камера

		Координаты на поверхности

		Вектор на камеру

		r, s

		θ, φ

Нет интерактивности.



Рис. 18. Разбиение на примитивы и декомпозиция ПО относительно них

Диалоговое окно – загрузить модель.

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

На треугольнике «отыгрывается» предыдущая анимация.



Рис. 19. Нормализация треугольника

Нормализация треугольника:

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





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

Первый рисунок в два этапа превращается в последний. Интерактивности нет, иначе придется вычислять триангуляцию Делоне.



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

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



Рис. 22. Факторизация матрицы освещенности

Показать несколько целочисленных (чтобы легко было устно посчитать) матриц, их разложить, возможно заполнение матриц пользователем. Показать «хорошую» матрицу и «плохую» матрицу.



Рис. 23. Triangle-centered декомпозиция

Программа показывает пример разрыва на границе треугольника. Аналогия: flat/Gouraud shading.



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

Исходная текстура раскладывается на 3, потом вновь становится исходной.



Рис. 25. Полный рендеринг одного треугольника

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




5.Описание программы-демонстрации

Программа позволяет перемещаться по шагам демонстрации в обоих направлениях. Кроме того, имеется возможность переместиться в начало анимации:



Рис. 26. Перемещение по шагам анимации

Программа может потребовать загрузить модель формата *.obj (созданную программой WrlLoader (Модель→Сохранить геометрию с нормалями, до этого выполнить команды Модель→Загрузить, Модель→Визуализировать в программе WrlLoader)). В этом случае надо выполнить команду меню Модель→Загрузить:



Рис. 27. Меню загрузки модели


В случае отсутствия некоторых файлов в директории программы она (программа) может потребовать указать путь к этому файлу:



Рис. 28. Ошибка загрузки файла

При показе трехмерных объектов программа выделяет мерцанием треугольник, с которым подразумевается дальнейшая работа (демонстрация на нем чего-либо):



Рис. 29. Работа с трехмерным объектом

Чтобы получше рассмотреть модель, Вы можете вращать её с помощью кнопок WSAD и приближать/удалять с помощью клавиш «=» и «-» соответственно.




Заключение

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

Из вышесказанного вытекают основные направления дальнейших исследований:

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

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

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


Литература

Э. Эйнджел. Интерактивная компьютерная графика. Вводный курс на базе OpenGL: Пер. с англ. – М.: Издательский дом "Вильямс", 2001.

М. Ву, Дж. Нейдер, Т. Девис, Д. Шрайнер. OpenGL. Официальное руководство программиста: Пер. с англ. – СПб: ООО «ДиаСофтЮП», 2002.

Интернет-сайт Sourceforge http://www.sourceforge.net/projects/openlf

	Интернет-сайт Romulus 2 

	http://www.romulus2.com/articles/guides/lfm/lfm1.htm




Благодарности

Автор также выражает благодарность следующим людям, без которых данная работа не была бы возможна: С. Молинову, А. Жиркову, А. Игнатенко и Д. Першакову, Вэй-Хао Чену (Wei-Chao Chen).


Приложение 1.

char basefname[256];

char outfname[256];



switch (lopts->decomposition_type)

{

case LFMfactor4Vertex:

cout<<"Calculating Factor4-Vertex\n"; cout.flush();

     sprintf(basefname, "%s\\trimat_#####.mat", lopts->location_textures.c_str());

        sprintf(outfname, "%s\\factor4_vert_#####.mat", lopts->directory.c_str());

        break;

     case LFMsvdVertex:

        cout<<"Calculating SVD-Vertex\n"; cout.flush();

        sprintf(basefname, "%s\\trimat_#####.mat", lopts->location_textures.c_str());

        sprintf(outfname, "%s\\svd_vert_#####.mat", lopts->directory.c_str());

        break;

    case LFMnmfVertex:

        cout<<"Calculating NMF-Vertex\n"; cout.flush();

        sprintf(basefname, "%s\\trimat_#####.mat", lopts->location_textures.c_str());

        sprintf(outfname, "%s\\nmf_vert_#####.mat", lopts->directory.c_str());

        break;

     default:

        return 1;

    }         

    LFMDecomp decomp(sdf, calibs, lopts, basefname, outfname);

    decomp.Init();

    decomp.run();





6