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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Курсовик Удаление невидимых граней.Компьютерная графика и геометрия. Алгоритм Варнока.

Информация:

Тип работы: Курсовик. Добавлен: 7.2.2014. Сдан: 2012. Страниц: 38. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Содержание

Введение 3
1 Удаление невидимых граней 4
1.1 Метод трассировки лучей 4
1.2 Метод z-буфера 4
1.3 Алгоритмы упорядочения 8
1.3.1 Метод сортировки по глубине. Алгоритм художника 9
1.3.2 Метод двоичного разбиения пространства 12
1.3.3 Метод построчного сканирования 15
1.3.4 Алгоритм Варнока (Warnock) 20
2 Практическая часть 24
2.1 Назначение программы 24
2.2 Обоснование выбора языка программирования 24
2.3 Требования к аппаратному обеспечению системы 25
2.4 Структура программы 26
2.5 Инструкция пользователя 29
2.6 Пример выполнения программы 31
Заключение 33
Список использованной литературы 34
Приложение. Листинг программы 35


Введение
Основные идеи, на которые опирается алгоритм Варнока облада­ют большой общностью. Они основываются на гипотезе о способе об­работки информации, содержащейся в сцене, глазом и мозгом челове­ка. Эта гипотеза заключается в том, что тратится очень мало вре­мени и усилий на обработку тех областей, которые содержат мало информации. Большая часть времени и труда затрачивается на облас­ти с высоким информационным содержимым, в качестве примера расс­мотрим поверхность стола, на которой нет ничего, кроме вазы с фруктами. Для восприятия цвета, фактуры и других аналогичных ха­рактеристик всей поверхности стола много времени не нужно. Все внимание сосредоточивается на вазе с фруктами. В каком месте сто­ла она расположена? Велика ли она? Из какого материала сделана: из дерева, керамики, пластика, стекла, металла? Каков цвет вазы: красный, синий, серебристый; тусклый или яркий и т. п.? Какие фрукты в ней лежат: персики, виноград, груши, бананы, яблоки? Ка­ков цвет яблок: красный, желтый, зеленый? Есть ли у яблока хвос­тик? В каждом случае, по мере сужения сферы интереса, возрастает уровень требуемой детализации. Далее, если на определенном уровне детализации на конкретный вопрос нельзя ответить немедленно, то он откладывается на время для последующего рассмотрения. В алго­ритме Варнока и его вариантах делается попытка извлечь преиму­щество из того факта, что большие области изображения однородны, например поверхность стола в приведенном выше примере. Такое свойство известно как когерентность, т. е. смежные области (пик­селы) вдоль обеих осей X и Y имеют тенденцию к однородности.
Поскольку алгоритм Варнока нацелен на обработку картинки, он работает в пространстве изображения. В пространстве изображения рассматривается окно и решается вопрос о том, пусто ли оно или его содержимое достаточно просто для визуализации. Если это не так, то окно разбивается на фрагменты до тех пор, пока содержимое подокна не станет достаточно простым для визуализации или его размер не достигнет требуемого предела разрешения. В последнем случае информация, содержащаяся в окне, усредняется, и результат изображается с одинаковой интенсивностью или цветом.
Конкретная реализация алгоритма Варнока зависит от метода разбиения окна и от деталей критерия, используемого для того, чтобы решить, является ли содержимое окна достаточно простым. В оригинальной версии алгоритма Варнока каждое окно разбивалось на четыре одинаковых подокна.
1 Удаление невидимых граней
Задача удаления невидимых граней является заметно более сложной, чем задача удаления невидимых линий, хотя бы по общему объему возникающей информации. Если практически все методы, служащие для удаления невидимых линий, работают в объектном пространстве и дают точный результат, то для удаления невидимых поверхностей существует большое число методов, работающих только в картинной плоскости, а также смешанных методов.
1.1 Метод трассировки лучей
Наиболее естественным методом для определения видимости граней является метод трассировки лучей (вариант, используемый только для определения видимости, без отслеживания отраженных и преломленных лучей обычно называется ray casting), при котором для каждого пиксела картинной плоскости определяется ближайшая к нему грань, для чего через этот пиксел выпускается луч, находятся все точки его пересечения с гранями и среди них выбирается ближайшая.
Данный алгоритм можно представить следующим образом:
for all pixels for all objects compare z
Одним из преимуществ этого метода является простота, универсальность (он может легко работать не только с полигональными моделями; возможно использование Constructive Solid Geometry) и возможность совмещения определения видимости с расчетом цвета пиксела.
Еще одним несомненным плюсом метода является большое количество методов оптимизации, позволяющих работать с сотнями тысяч граней и обеспечивающих временные затраты порядка O(Clogn), где С - общее количество пикселов на экране, а n - общее количество объектов в сцене. Более того, существуют методы, обеспечивающие практическую независимость временных затрат от количества объектов.
1.2 Метод z-буфера
Одним из самых простых алгоритмов удаления невидимых граней и поверхностей является метод z-буфера (буфера глубины), где для каждого пиксела, как и в методе трассировки лучей, находится грань, ближайшая к нему вдоль направления проектирования, однако здесь циклы по пикселам и по объектам меняются местами: for all objects for all covered pixels compare z
Поставим в соответствие каждому пикселу (x, y) картинной плоскости кроме цвета c(x, у), хранящегося в видеопамяти, его расстояние до картинной плоскости вдоль направления проектирования z(x, у) (его глубину).
Массив глубин инициализируется +infinity.
Для вывода на картинную плоскость произвольной грани она переводится в растровое представление на картинной плоскости и затем для каждого пиксела этой грани находится его глубина. В случае, если эта глубина меньше значения глубины, хранящегося в z-буфере, пиксел рисуется и его глубина заносится в z-буфер.
Весьма эффективным является совмещение растровой развертки грани с выводом в z-буфер. При этом для вычисления глубины пикселов могут применяться инкрементальные методы, требующие всего нескольких сложений на пиксел.
Грань рисуется последовательно строка за строкой; для нахождения необходимых значений используется линейная интерполяция (рис. 1)



Рис. 1.
Фактически метод z-буфера осуществляет поразрядную сортировку по x и у, а затем сортировку по z, требуя всего одного сравнения для каждого пиксела каждой грани.
Метод z-буфера работает исключительно в пространстве картинной плоскости и не требует никакой предварительной обработки данных. Порядок, в котором грани выводятся на экран, не играет никакой роли.
Для экономии памяти можно отрисовывать не все изображение сразу, а рисовать по частям. Для этого картинная плоскость разбивается на части (обычно это горизонтальные полосы) и каждая такая часть обрабатывается независимо. Размер памяти под буфер определяется размером наибольшей из этих частей.
Большинство современных графических станций содержат в себе графические платы с аппаратной реализацией z-буфера, зачастую включая и аппаратную «растеризацию» (т.e. преобразование изображения из координатного представления в pacтровое) граней вместе с закрашиванием Гуро. Подобные карты обеспечивают очень высокую скорость рендеринга вплоть до нескольких миллионов граней в секунду.
Средние временные затраты составляют O(n), где n- общее количество граней.
Одним из основных недостатков z-буфера (помимо большого объема требуемой под буфер памяти) является избыточность вычислений: осуществляется вывод всех граней вне зависимости от того, видны они или нет. И если, например, данный пиксел накрывается десятью различными лицевыми гранями, то для каждого соответствующего пиксела каждой из этих десяти граней необходимо произвести расчет цвета. При использовании сложных моделей освещенности (например, модели Фонга) и текстур эти вычисления могут потребовать слишком больших временных затрат.
Рассмотрим в качестве примера модель здания с комнатами и всем, находящимся внутри их. Общее количество граней в подобной модели может составлять сотни тысяч и миллионы. Однако, находясь внутри одной из комнат этого здания, наблюдатель реально видит только весьма небольшую часть граней (несколько тысяч Поэтому вывод всех граней является непозволительной тратой времени.
Существует несколько модификаций метода z-буфера, позволяющих заметно сократить количество выводимых граней. Одним из наиболее мощных и элегантных является метод иерархического z-буфера.
Метод иерархического z-буфера использует сразу все три типа когерентности в сцене - в картинной плоскости (z-буфере), в пространстве объектов и временную когерентность.
Назовем грань скрытой (невидимой) по отношению к z-буферу, если для любого пиксела картинной плоскости, накрываемого этой гранью, глубина соответствующего пиксела грани не меньше значения в z-буфере. Ясно, что выводить скрытые грани не имеет смысла, так как они ничего не изменяют (они заведомо не являются видимыми).
Куб (прямоугольный параллелепипед) назовем скрытым по отношению к буферу, если все его лицевые грани являются скрытыми по отношению к этому буферу (рис. 2).
Опишем куб вокруг некоторой группы граней. Перед выводом граней, содержащихся внутри этого куба, стоит проверить, не является ли куб скрытым. Если он скрытый, то все грани, содержащиеся внутри его, можно сразу же отбрасывать.


Рис. 2.
Но даже если куб не является скрытым, часть граней, содержащихся внутри его, все равно может быть скрытой, и поэтому нужно разбить его на части и проверить каждую из частей на скрытость.
Предложенный подход приводит к следующему алгоритму.
Опишем куб вокруг всей сцены. Разобьем его на 8 равных частей. Каждую из частей, содержащую достаточно много граней, снова разобьем и т. д. Если число граней внутри частичного куба меньше заданного числа, то разбивать его нет смысла и он становится листом строящегося дерева. В результате получается восьмеричное дерево, где с каждым кубом связан список граней, содержащихся внутри его.
Вывод всей сцены можно представить следующим образом: очередной куб, начиная с корня дерева, проверяется на попадание в область видимости. Если куб в область видимости не попал, то ни одна грань из него не видна и мы его отбрасываем. В противном случае проверяем, не является ли этот куб скрытым. Скрытый куб также отбрасывается. В противном случае повторяем описанную процедуру для всех его восьми частей в порядке удаления - первым обрабатывается ближайший подкуб, последним - самый дальний. Для куба, являющегося листом, вместо вывода его частей просто выводим все содержащиеся в нем грани.
Такой подход опирается на когерентность в объектном пространстве и позволяет легко отбросить основную часть невидимых граней.
Для облегчения проверки грани на скрытость можно использовать z-пирамиду. Ее нижним уровнем является сам z-буфер. Для построения следующего уровня пикселы объединяются в группы по 4 (2?2) и из их глубин выбирается наибольшая. Таким образом, следующий уровень оказывается тоже буфером, но его размер уже будет меньше исходного в 2 раза по каждому измерению. Аналогично строятся и остальные уровни пирамиды до тех пор, пока мы не придем к уровню, состоящему из единственного пиксела, являющегося вершиной z-пирамиды (рис. 3).
Первым шагом проверки грани на скрытость будет сравнение ее минимальной глубины со значением в вершине z-пирамиды. Если минимальная глубина грани оказывается больше, то грань скрыта. В противном случае грань разбирается на 4 части и сравнение производится на следующем уровне пирамиды. Если ни на одном из промежуточных уровней скрытость грани установить не удалось, то осуществляется переход к последнему уровню, на котором грань растеризуется, и производится попиксельное сравнение с z-буфером. Наиболее простой является проверка на вершине пирамиды, наиболее трудоемкой - проверка в ее основании.


Рис. 3.
Применение z-пирамиды позволяет использовать когерентн........

Список использованной литературы
1. Зозулевич Д. И. Машинная графика в автоматизированном проектировании. - М.: Машиностроение, 1996. - 240 с.
2. Иванов В.П., Батраков А.С. Трехмерная компьютерная графика. -М.: Радио и связь, 1995. -213 с.
3. Культин Н. Основы программирования в Delphi 2006 для Windows. -М.: Сфера, 2006. -631 с.
4. Павлидис Т. Алгоритмы машинной графики и обработки изображений: Пер. с англ. -М.:Радио и связь, 1986. -400 с.
5. Роджерс Д. Алгоритмические основы машинной графики: Пер. с англ. -М.: Мир, 1989. -512 с.
6. Томпсон Н. Секреты программирования трехмерной графики для Windows 95: Пер. с англ. - СПб.: Питер, 1997. - 352 с.
7. Шикин А. В., Боресков Л. В. Компьютерная графика. Полигональные модели. -M.: ДИАЛОГ-МИФИ, 2001. -464 с.



Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.