Разработка демонстрационного комплекса для изучения алгоритмов загораживания
|
Аннотация 2
ВВЕДЕНИЕ 7
1 ОБЗОР И АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ 10
1.1 Описание проблемы 10
1.2 Существующие решения 10
1.3 Достоинства и недостатки существующих решений 10
1.4 Достоинство и недостатки нового решения 12
2 ТЕОРЕТИЧЕСКОЕ ОПИСАНИЕ ПРОГРАММЫ 13
2.1 Алгоритм Робертса 13
2.2 Алгоритм Аппеля 16
2.3 Метод сортировки по глубине 16
2.4 Метод Z-буфера 17
2.5 Метод построчного сканирования 22
3 Планирование 22
3.1 Платформа 23
3.2 Возможные варианты реализации 23
3.3 Обоснование среды реализации 23
3.4 Выбор и обоснование средств разработки 23
3.5 Архитектура системы 24
4 Основные алгоритмические решения 27
4.1 Блок-схемы 27
4.1.1 Алгоритм Робертса 28
4.1.2 Алгоритм Аппеля 29
4.1.3 Метод сортировки по глубине 30
4.1.4 Метод Z-буфера 31
4.1.5 Метод построчного сканирования 32
4.2 Визуализация 33
5 Результаты реализации 34
ЗАКЛЮЧЕНИЕ 41
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 42
ПРИЛОЖЕНИЕ А 45
ПРИЛОЖЕНИЕ Б 46
ПРИЛОЖЕНИЕ В 47
ПРИЛОЖЕНИЕ Г 54
ПРИЛОЖЕНИЕ Д 55
ВВЕДЕНИЕ 7
1 ОБЗОР И АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ 10
1.1 Описание проблемы 10
1.2 Существующие решения 10
1.3 Достоинства и недостатки существующих решений 10
1.4 Достоинство и недостатки нового решения 12
2 ТЕОРЕТИЧЕСКОЕ ОПИСАНИЕ ПРОГРАММЫ 13
2.1 Алгоритм Робертса 13
2.2 Алгоритм Аппеля 16
2.3 Метод сортировки по глубине 16
2.4 Метод Z-буфера 17
2.5 Метод построчного сканирования 22
3 Планирование 22
3.1 Платформа 23
3.2 Возможные варианты реализации 23
3.3 Обоснование среды реализации 23
3.4 Выбор и обоснование средств разработки 23
3.5 Архитектура системы 24
4 Основные алгоритмические решения 27
4.1 Блок-схемы 27
4.1.1 Алгоритм Робертса 28
4.1.2 Алгоритм Аппеля 29
4.1.3 Метод сортировки по глубине 30
4.1.4 Метод Z-буфера 31
4.1.5 Метод построчного сканирования 32
4.2 Визуализация 33
5 Результаты реализации 34
ЗАКЛЮЧЕНИЕ 41
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 42
ПРИЛОЖЕНИЕ А 45
ПРИЛОЖЕНИЕ Б 46
ПРИЛОЖЕНИЕ В 47
ПРИЛОЖЕНИЕ Г 54
ПРИЛОЖЕНИЕ Д 55
Задача удаления невидимых линий и поверхностей является одной из наиболее сложных в машинной графике. Алгоритмы удаления невидимых линий и поверхностей служат для определения линий ребер, поверхностей или объемов, которые видимы или невидимы для наблюдателя, находящегося в заданной точке пространства. Необходимость удаления невидимых линий, ребер, поверхностей или объемов проиллюстрирована рисунке 1На рисунке 1, а приведен типичный каркасный чертеж куба. Каркасный чертеж представляет трехмерный объект в виде штрихового изображения его ребер. Рисунке 1, а можно интерпретировать двояко: как вид куба сверху слева или снизу справа. Удаление тех линий или поверхностей, которые невидимы с соответствующей точки зрения, позволяют избавиться от неоднозначности. Результаты показаны на рисунке 1, би 1, в.
Сложность задачи удаления невидимых линий и поверхностей привела к появлению большого числа различных способов ее решения. Многие из них ориентированы на специализированные приложения. Наилучшего решения обшей задачи удаления невидимых линий и поверхностей не существует. Для моделирования процессов в реальном времени, например для авиатренажеров, требуются быстрые алгоритмы, которые могут порождать результаты с частотой видеогенерации 30 кадр/с. Для машинной мультипликации, например, требуются алгоритмы, которые могут генерировать сложные реалистические изображения, в которых представлены тени, прозрачность и фактура, учитывающие эффекты отражения и преломления цвета в мельчайших оттенках. Подобные алгоритмы работают медленно и зачастую на вычисления требуется несколько минут или даже часов. Строго говоря, учет эффектов прозрачности, фактуры, отражения и т. п. не входит в задачу удаления невидимых линий или поверхностей. Естественнее считать их частью процесса визуализации изображения. Однако многие из этих эффектов встроены в алгоритмы удаления невидимых поверхностей. Существует тесная взаимосвязь между скоростью работы алгоритма и детальностью его результата. Ни один из алгоритмов не может достигнуть хороших оценок для этих двух показателей одновременно. По мере создания все более быстрых алгоритмов можно строить все более детальные изображения. Реальные задачи, однако, всегда будут требовать учета еще большего количества деталей.
Все алгоритмы удаления невидимых линий (поверхностей) включают в себя сортировку. Порядок, в котором производится сортировка координат объектов, вообще говоря, не влияет на эффективность этих алгоритмов. Главная сортировка ведется по геометрическому расстоянию от тела, поверхности, ребра или точки до точки наблюдения. Основная идея, положенная в основу сортировки по расстоянию, заключается в том, что чем дальше расположен объект от точки наблюдения, тем больше вероятность, что он будет полностью или частично заслонен одним из объектов, более близких к точке наблюдения. После определения расстояний или приоритетов по глубине остается провести сортировку по горизонтали и по вертикали, чтобы выяснить, будет ли рассматриваемый объект действительно заслонен объектом, расположенным ближе к точке наблюдения. Эффективность любого алгоритма удаления невидимых линий или поверхностей в большой мере зависит от эффективности процесса сортировки. Для повышения эффективности сортировки используется также когерентность сцены, т. е. тенденция неизменяемости характеристик сцены в малом.
Алгоритмы удаления невидимых линий или поверхностей можно классифицировать по способу выбора системы координат или пространства, в котором они работают. Выделяют три класса алгоритмов удаления невидимых линий или поверхностей:
♦ алгоритмы, работающие в объектном пространстве.
♦ алгоритмы, работающие в пространстве изображения (экрана).
♦ алгоритмы, формирующие список приоритетов.
Алгоритмы, работающие в объектном пространстве, имеют дело с физической системой координат, в которой описаны эти объекты. При этом получаются весьма точные результаты, ограниченные лишь точностью вычислений. Полученные изображения можно свободно увеличивать во много раз. Алгоритмы, работающие в объектном пространстве, особенно полезны в тех приложениях, где необходима высокая точность.
Алгоритмы, работающие в пространстве изображения, имеют дело с системой координат того экрана, на котором объекты визуализируются. При этом точность вычислений ограничена разрешающей способностью экрана.
Результаты, полученные в пространстве изображения, а затем увеличенные во много раз, не будут соответствовать исходной сцене. Например, могут не совпасть концы отрезков. Алгоритмы, формирующие список приоритетов, работают попеременно в обеих упомянутых системах координат.
Объем вычислений для любого алгоритма, работающего в объектном пространстве и сравнивающего каждый объект сцены со всеми остальными объектами этой сцены, растет теоретически как квадрат числа объектов (n2). Аналогично, объем вычислений любого алгоритма, работающего в пространстве изображения и сравнивающего каждый объект сцены с позициями всех пикселей в системе координат экрана, растет теоретически, как n в степени N. Здесь n обозначает количество объектов (тел, плоскостей или ребер) в сцене, а N — число пикселей. Теоретически трудоемкость алгоритмов, работающих в объектном пространстве, меньше трудоемкости алгоритмов, работающих в пространстве изображения, при n
Сложность задачи удаления невидимых линий и поверхностей привела к появлению большого числа различных способов ее решения. Многие из них ориентированы на специализированные приложения. Наилучшего решения обшей задачи удаления невидимых линий и поверхностей не существует. Для моделирования процессов в реальном времени, например для авиатренажеров, требуются быстрые алгоритмы, которые могут порождать результаты с частотой видеогенерации 30 кадр/с. Для машинной мультипликации, например, требуются алгоритмы, которые могут генерировать сложные реалистические изображения, в которых представлены тени, прозрачность и фактура, учитывающие эффекты отражения и преломления цвета в мельчайших оттенках. Подобные алгоритмы работают медленно и зачастую на вычисления требуется несколько минут или даже часов. Строго говоря, учет эффектов прозрачности, фактуры, отражения и т. п. не входит в задачу удаления невидимых линий или поверхностей. Естественнее считать их частью процесса визуализации изображения. Однако многие из этих эффектов встроены в алгоритмы удаления невидимых поверхностей. Существует тесная взаимосвязь между скоростью работы алгоритма и детальностью его результата. Ни один из алгоритмов не может достигнуть хороших оценок для этих двух показателей одновременно. По мере создания все более быстрых алгоритмов можно строить все более детальные изображения. Реальные задачи, однако, всегда будут требовать учета еще большего количества деталей.
Все алгоритмы удаления невидимых линий (поверхностей) включают в себя сортировку. Порядок, в котором производится сортировка координат объектов, вообще говоря, не влияет на эффективность этих алгоритмов. Главная сортировка ведется по геометрическому расстоянию от тела, поверхности, ребра или точки до точки наблюдения. Основная идея, положенная в основу сортировки по расстоянию, заключается в том, что чем дальше расположен объект от точки наблюдения, тем больше вероятность, что он будет полностью или частично заслонен одним из объектов, более близких к точке наблюдения. После определения расстояний или приоритетов по глубине остается провести сортировку по горизонтали и по вертикали, чтобы выяснить, будет ли рассматриваемый объект действительно заслонен объектом, расположенным ближе к точке наблюдения. Эффективность любого алгоритма удаления невидимых линий или поверхностей в большой мере зависит от эффективности процесса сортировки. Для повышения эффективности сортировки используется также когерентность сцены, т. е. тенденция неизменяемости характеристик сцены в малом.
Алгоритмы удаления невидимых линий или поверхностей можно классифицировать по способу выбора системы координат или пространства, в котором они работают. Выделяют три класса алгоритмов удаления невидимых линий или поверхностей:
♦ алгоритмы, работающие в объектном пространстве.
♦ алгоритмы, работающие в пространстве изображения (экрана).
♦ алгоритмы, формирующие список приоритетов.
Алгоритмы, работающие в объектном пространстве, имеют дело с физической системой координат, в которой описаны эти объекты. При этом получаются весьма точные результаты, ограниченные лишь точностью вычислений. Полученные изображения можно свободно увеличивать во много раз. Алгоритмы, работающие в объектном пространстве, особенно полезны в тех приложениях, где необходима высокая точность.
Алгоритмы, работающие в пространстве изображения, имеют дело с системой координат того экрана, на котором объекты визуализируются. При этом точность вычислений ограничена разрешающей способностью экрана.
Результаты, полученные в пространстве изображения, а затем увеличенные во много раз, не будут соответствовать исходной сцене. Например, могут не совпасть концы отрезков. Алгоритмы, формирующие список приоритетов, работают попеременно в обеих упомянутых системах координат.
Объем вычислений для любого алгоритма, работающего в объектном пространстве и сравнивающего каждый объект сцены со всеми остальными объектами этой сцены, растет теоретически как квадрат числа объектов (n2). Аналогично, объем вычислений любого алгоритма, работающего в пространстве изображения и сравнивающего каждый объект сцены с позициями всех пикселей в системе координат экрана, растет теоретически, как n в степени N. Здесь n обозначает количество объектов (тел, плоскостей или ребер) в сцене, а N — число пикселей. Теоретически трудоемкость алгоритмов, работающих в объектном пространстве, меньше трудоемкости алгоритмов, работающих в пространстве изображения, при n
приложение - «Демонстрационный комплекс программ для изучения алгоритмов загораживания» для Windows 7 x32 SP1.
В ходе выполнения работы решены такие задачи, как:
1. обоснована актуальность разработки,
2. проведен обзор аналогов приложения;
3. выбраны инструменты разработки;
4. спроектирована программная система;
5. реализован демонстрационный комплекс программ.
В приложение были включены наиболее распространенные алгоритмы удаления невидимых линий и поверхностей:
- алгоритм Робертса;
- алгоритм Аппеля;
- метод сортировки по глубине;
- метод Z-буфера;
- метод построчного сканирования;
А также исправлены такие недостатки найденных аналогов, как:
• отсутствие пояснений,
• отсутствие наглядности построения,
• недостоверность алгоритмов.
На основании учебно-методического пособия Ярош Е.С «Методы и средства представления графической информации» разработаны исходные коды перечисленных выше алгоритмов. Для каждого алгоритма была реализована анимация построения с выводом выполняемого кода за счёт многопоточного программирования.
Кроме модуля визуализации разработаны модули:
• теоретический материал;
• графический материал - блок-схемы.
Модули используют данные из Ярош Е.С «Методы и средства представления графической информации».
Организована навигация по всему приложению и создан эргономичный интерфейс.
Демонстрационный комплекс программ написан на языке программирования C#. Для работы с графикой использовались внешние библиотеки - Drawing (.Net Framework). Разработка приложения закончена и передана заказчику.
Некоторые перспективы развития: данный продукт можно доработать до универсального учебного пособия по машинной графике, добавив многие другие темы для изучения и визуализации (например, закрашивание, отсечение отрезков, ит.д.).
В ходе выполнения работы решены такие задачи, как:
1. обоснована актуальность разработки,
2. проведен обзор аналогов приложения;
3. выбраны инструменты разработки;
4. спроектирована программная система;
5. реализован демонстрационный комплекс программ.
В приложение были включены наиболее распространенные алгоритмы удаления невидимых линий и поверхностей:
- алгоритм Робертса;
- алгоритм Аппеля;
- метод сортировки по глубине;
- метод Z-буфера;
- метод построчного сканирования;
А также исправлены такие недостатки найденных аналогов, как:
• отсутствие пояснений,
• отсутствие наглядности построения,
• недостоверность алгоритмов.
На основании учебно-методического пособия Ярош Е.С «Методы и средства представления графической информации» разработаны исходные коды перечисленных выше алгоритмов. Для каждого алгоритма была реализована анимация построения с выводом выполняемого кода за счёт многопоточного программирования.
Кроме модуля визуализации разработаны модули:
• теоретический материал;
• графический материал - блок-схемы.
Модули используют данные из Ярош Е.С «Методы и средства представления графической информации».
Организована навигация по всему приложению и создан эргономичный интерфейс.
Демонстрационный комплекс программ написан на языке программирования C#. Для работы с графикой использовались внешние библиотеки - Drawing (.Net Framework). Разработка приложения закончена и передана заказчику.
Некоторые перспективы развития: данный продукт можно доработать до универсального учебного пособия по машинной графике, добавив многие другие темы для изучения и визуализации (например, закрашивание, отсечение отрезков, ит.д.).
