Удаление невидимых линий и поверхностей с помощью алгоритма Варнока

Содержание.

Обоснование выбора языка программирования ……………….2
Требования к аппаратному обеспечению………………………..2
Основные принципы моделирования трёхмерных объектов....3
Алгоритм Варнока…………………………………………………….5
Описание возможностей программы…………………………….19
Интерфейс…………………………………………….………………21
6.1 Главное окно……………………………………………………21
6.2 Меню. ……………………………………………………………22
Листинг…………………………………………………………………58
Список литературы. …………………………………………………59

1. Обоснование выбора языка программирования.
Представленная курсовая работа разработана среде программирования Delphi 6 от Borland. Данный программный продукт предоставляет широкие возможности для создания прикладных программ под Widows, а также Delphi является наиболее удобной средой программирования, т.к. обладает интуитивно понятным интерфейсом, мощной палитрой средств для разработки пользовательского интерфейса. В тоже время, разработка взаимодействия программа - пользователь не требует больших временных затрат, что позволяет сосредоточить внимания на реализации требуемых алгоритмов.

2. Требования к аппаратному обеспечению системы.
ОС Windows 9x/NT/Me/2000/Xp.
Процессор не ниже Pentium 166 Mhz.
16 Mb Ram.
SVGA 800x600.
HDD Free Space = 300 kb

3. Основные принципы моделирования трёхмерных объектов.
Один из способов моделирования трёхмерных объектов - это описание всех поверхностей, составляющих границы объекта. В большинстве случаев объекты ограничены сложными кривыми поверхностями, для приближенного представления границ объекта можно использовать простые многоугольники. Многие простые тела, такие как, например, кубы естественным образом ограничиваются плоскостями, но даже объекты с кривыми границами, в частности цилиндр, конус или сфера, могут в достаточной мере адекватно, промоделированы большим числом плоских поверхностей.
Многоугольник определяется его вершинами. Каждая вершина – это трёхмерная точка в декартовой системе координат. Во время конструирования завершенной трёхмерной сцены может возникнуть необходимость поменять местоположение одного или нескольких объектов, повращать или изменить масштаб, для этого необходимо произвести трёхмерное преобразование координат.
Существует краткая математическая запись для выражения преобразования координат – матрично-векторное умножение. Трёхмерная точка представляется трёхэлементными векторами-столбцами.
“Масштабирование координат точки означает умножение каждой координаты на постоянную величину.
Масштабирование представляется следующей матрицей преобразования: , где K - фактор масштабирования.
Перенос относится к передвижению объекта в новую точку с сохранением ориентации. Для переноса трёхмерной точки необходимо прибавить соответствующие смещения к X, Y, Z-координатам для получения эффекта движения. Таким образом, перенос основан на сложении двух векторов. Перенос можно выразить как матричное умножение, но для этого необходим “математический костыль” – однородные координаты. К трехмерной координате следует добавить ещё одну со значением 1:
, где X, Y, Z – координаты точки. Это представление известно как точка в однородной системе координат. Согласно этому определению можно реализовать перенос умножением этого вектора на матрицу преобразования размером 4х4, чья последняя колонка содержит параметры переноса: Если умножить четырёхмерный вектор V на эту матрицу, то следующий результат, который представляет перенос: Фактически используя эти искусственные однородные координаты, можно выразить все преобразования последовательностью матричных умножений.
Вращение – самое сложное преобразование координат и самое важное, потому что даёт ощущуние объёмного изображения благодаря возможности увидеть объект со всех сторон. Матрицы преобразования при вращении:
- вокруг оси OX правой системы координат,
- вокруг оси OY правой системы координат,
- вокруг оси OZ правой системы координат, где  - угол поворота.”1
4. Алгоритм Варнока.2
Основные идеи, на которые опирается алгоритм Варнока, обладают большой общностью. Они основываются на гипотезе о способе обработки информации, содержащейся в сцене, глазом и мозгом человека. Эта гипотеза заключается в том, что тратится очень мало времени и усилий на обработку тех областей, которые содержат мало информации. Большая часть времени и труда затрачивается на области с высоким информационным содержимым. В качестве примера рассмотрим поверхность стола, на которой нет ничего, кроме вазы с фруктами. Для восприятия цвета, фактуры и других аналогичных характеристик всей поверхности стола много времени не нужно. Все внимание сосредоточивается на вазе с фруктами. В каком месте стола она расположена? Велика ли она? Из какого материала сделана: из дерева, керамики, пластика, стекла, металла? Каков цвет вазы: красный, синий, серебристый; тусклый или яркий и т. п.? Какие фрукты в ней лежат: персики, виноград, груши, бананы, яблоки? Каков цвет яблок: красный, желтый, зеленый? Есть ли у яблока хвостик? В каждом случае, по мере сужения сферы интереса, возрастает уровень требуемой детализации. Далее, если на определенном уровне детализации на конкретный вопрос нельзя ответить немедленно, то он откладывается на время для последующего рассмотрения. В алгоритме Варнока и его вариантах делается попытка извлечь преимущество из того факта, что большие области изображения однородны, например поверхность стола в приведенном выше примере. Такое свойство известно как когерентность, т. е. смежные области (пиксели) вдоль обеих осей х и у имеют тенденцию к однородности.
Поскольку алгоритм Варнока нацелен на обработку картинки, он работает в пространстве изображения. В пространстве изображения рассматривается окно и решается вопрос о том, пусто ли оно, или его содержимое достаточно просто для визуализации. Если это не так, то окно разбивается на фрагменты до тех пор, пока содержимое подокна не станет достаточно простым для визуализации или его размер не достигнет требуемого предела разрешения. В последнем случае информация, содержащаяся в окне, усредняется, и результат изображается с одинаковой интенсивностью или цветом. Устранение лестничного эффекта можно реализовать, доведя процесс разбиения до размеров, меньших, чем разрешение экрана на один пиксель, и усредняя атрибуты подпикселей, чтобы определить атрибуты самих пикселей.
Конкретная реализация алгоритма Варнока зависит от метода разбиения окна и от деталей критерия, используемого для того, чтобы решить, является ли содержимое окна достаточно простым. В оригинальной версии алгоритма Варнока каждое окно разбивалось на четыре одинаковых подокна.
На рис. 1 показан результат простейшей реализации алгоритма Варнока. Здесь окно, содержимое которого слишком сложно изображать, разбито на четыре одинаковых подокна. Окно, в котором что-то есть, подразбивается далее до тех пор, пока не будет достигнут предел разрешения экрана.

рис. №1 “Пример использования алгоритма Варнока”

На рис. 1, a показана сцена, состоящая из двух простых многоугольников. На рис. 1, b показан результат после удаления невидимых линий. Заметим, что горизонтальный прямоугольник частично экранирован вертикальным. На рис. 1, c и d показан процесс разбиения окон на экране с разрешением 256х256. Поскольку 256 = 2^8, требуется не более восьми шагов разбиения для достижения предела разрешения экрана. Пусть подокна рассматриваются в следующем порядке: нижнее левое, нижнее правое, верхнее левое, верхнее правое. Будем обозначать подокна цифрой и буквой,' цифра – это номер шага разбиения, а буква – номер квадранта. Тогда для окна 1а подокна 2а, 4а, 4с, 5а, 5b оказываются пустыми и изображаются с фоновой интенсивностью в процессе разбиения. Первым подокном, содержимое которого не пусто на уровне пикселей, оказывается 8а. Теперь необходимо решить вопрос о том, какой алгоритм желательно применить: удаления невидимых линий или удаления невидимых поверхностей. Если желательно применить алгоритм удаления невидимых линий, то пиксель, соответствующий подокну 8а, активируется, поскольку через него проходят видимые ребра. В результате получается изображение видимых ребер многоугольников в виде последовательности точек размером с пиксель каждая (рис. 1, е).
Следующее рассмотрение окна, помеченного как 8d на рис. 1, d, лучше всего проиллюстрирует различие между реализациями алгоритмов удаления невидимых линий и поверхностей. В случае удаления невидимых линий окно 8d размером с пиксель не содержит ребер ни одного многоугольника сцены. Следовательно, оно объявляется пустым и изображается с фоновой интенсивностью или цветом. Для алгоритма удаления невидимых поверхностей проверяется охват этого окна каждым многоугольником сцены. Если такой охват обнаружен, то среди охватывающих пиксель многоугольников выбирается ближайший к точке наблюдения на направлении наблюдения, проходящем через данный пиксель. Проверка проводится относительно центра пикселя. Затем этот пиксель изображается с интенсивностью или цветом ближайшего многоугольника. Если охватывающие многоугольники не найдены, то окно размером с пиксель пусто. Поэтому оно изображается с фоновым цветом или интенсивностью. Окно 8d охвачено вертикальным прямоугольником. Поэтому оно изображается с цветом или интенсивностью этого многоугольника. Соответствующий результат показан на рис. 1, f.
Возвратившись к рассмотрению окна 8а на рис. 1, d, покажем, как включить в алгоритм удаления невидимых поверхностей устранение лестничного эффекта. Разбиение этого окна дает четыре подокна с размерами, меньшими, чем размеры пикселя. Только одно из этих подокон – правое верхнее – охвачено многоугольником. Три других пусты. Усреднение результатов для этих четырех подпикселей показывает, что окно 8а размером с пиксель нужно изображать с интенсивностью, равной одной четверти интенсивности прямоугольника. Аналогично пиксель 8Ь следует высвечивать с интенсивностью, равной половине интенсивности прямоугольника. Конечно, окна размером с пиксель можно разбивать более одного раза, чтобы произвести взвешенное усреднение характеристик.
Процесс подразбиения порождает для подокон структуру данных, являющуюся деревом, которое показано на рис. 2 (В алгоритме Варнока впервые была реализована такая структура данных, как кватернарное дерево). Корнем этого дерева является визуализируемое окно. Каждый узел изображен прямоугольником, содержащим координаты левого нижнего угла и длину стороны подокна. Предположим, что подокна обрабатываются в следующем порядке: abcd, т. е. слева направо на каждом уровне разбиения в дереве. На рис. 2 показан активный путь по структуре данных дерева к окну 8а размером с пиксель. Активные узлы на каждом уровне изображены толстой линией. Рассмотрение рис. 1 и 2 показывает, что на каждом уровне все окна слева от активного узла пусты. Поэтому они должны были визуализироваться ранее с фоновым значением цвета или интенсивности. Все окна справа от активного узла на каждом уровне будут обработаны позднее, т. е. будут объявлены пустыми или будут подразделены при обходе дерева в обратном порядке.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию