Московский департамент образования лицей №1533 (информационных технологий) (стр. 2 из 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). Отличаются они такими качествами как качество разложения (точность, количество шагов аппроксимации) и неотрицательность получаемых векторов (важно для тайлинга и рендеринга).
8. Для удобства рендеринга карты поверхности и карты вида собираются в текстуры. В одной текстуре находятся карты одного вида, относящиеся к одному шагу аппроксимации.
Рис. 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 и разработка собственной программы-демонстрации алгоритма.
3.2 Включение блоков анимации в существующий текст реализации LFM
Анимацию можно было бы осуществить посредством включения кода анимации в программу lfm_view и lfm_process. Этот метод хорош тем, что он позволяет свести к минимуму приближения и упрощения, т. к. можно использовать функциональность исходной программы. Кроме того, сохраняется порядок и общая логика реализации алгоритма. Однако этот метод неприемлем вследствие того, что программа lfm_process представляет из себя Win32-приложение и не поддерживает MFC. Следовательно, было бы очень сложно реализовать вывод графики, текста и приемлемый пользовательский интерфейс.
3.3 Разработка собственной программы-демонстрации алгоритма
Главный минус разработки собственной программы – неполная интерактивность, а также недостоверность некоторых фрагментов. Однако разработка собственной программы дает возможность реализовать приемлемые вывод графики и текста и пользовательский интерфейс. Поэтому такая программа более наглядна для незнакомого с алгоритмом пользователя. Таким образом, был выбран метод создания собственной программы-демонстрации алгоритма.
3.4. Перечень этапов алгоритма, подлежащих анимации
Одной из самых наглядных статей в силу наглядных изображений стала статья Роберта Ричмонда (Robert Richmond) с интернет-сайта Romulus 2 (см. Перечень источников). Поэтому было принято решение выбрать стадии алгоритма для анимации, опираясь на этот документ, в особенности – на изображения. Ниже приведен список этапов анимации с пояснениями и указанием степени интерактивности:
Рис. 17. Поле освещенности
Постепенно на экране появляются:
1. Поверхность (треугольник)
2. Точка на ней
3. Камера
4. Координаты на поверхности
5. Вектор на камеру
6. r, s
7. θ, φ
Нет интерактивности.
Рис. 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. Она позволяет пользователю самому задавать различные начальные данные и изучать их влияние на работу алгоритма, а также изучать алгоритм на фиксированных начальных данных (демонстрационная версия). Однако необходима возможность изучения алгоритма на трехмерных моделях и последующая его оценка.