Удаление невидимых линий и поверхностей

 

Аннотация


В работе представлены теоретические основы машинной графики, необходимые для организации алгоритмов удаления невидимых линий и поверхностей. Согласно теоретическому алгоритму, была создана компьютерная программа. Программа разработана в среде программирования Borland Delphi 7, позволяет пользователю программы реализовать удаление невидимых линий и поверхностей путем Алгоритма "Плавающего горизонта" на трехмерных поверхностях.

алгоритм невидимый линия поверхность

Содержание


Цель работы

Введение

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

.1 Общий алгоритм(описание алгоритма)

. Структура программы

. Описание программы

. Инструкция пользователю

. Алгоритм реализации

. Описание программного продукта

.1 Аппаратно-программные средства

.2 Язык и среда программирования

Приложение


Цель работы


Заданием предполагается реализовать удаление невидимых линий и поверхностей путем Алгоритма "Плавающего горизонта".

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


Введение


Задача удаления невидимых линий и поверхностей является одной из наиболее сложных в машинной графике. Алгоритмы удаления невидимых линий и поверхностей служат для определения линий ребер, поверхностей или объемов, которые видимы или невидимы для наблюдателя, находящегося в заданной точке пространства.

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

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

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

Алгоритмы удаления невидимых линий или поверхностей можно классифицировать по способу выбора системы координат или пространства, в котором они работают. Алгоритмы, работающие в объектном пространстве, имеют дело с физической системой координат, в которой описаны эти объекты. При этом получаются весьма точные результаты, ограниченные, вообще говоря, лишь точностью вычислений. Полученные изображения можно свободно увеличивать во много раз. Алгоритмы, работающие в объектном пространстве, особенно полезны в тех приложениях, где необходима высокая точность. Алгоритмы же, работающие в пространстве изображения, имеют дело с системой координат того экрана, на котором объекты визуализируются. При этом точность вычислений ограничена разрешающей способностью экрана. Обычно разрешение экрана бывает довольно низким, типичный пример- 512x512 точек. Результаты, полученные в пространстве изображения, а затем увеличенные во много раз, не будут соответствовать исходной сцене. Например, могут не совпасть концы отрезков. Алгоритмы, формирующие список приоритетов, работают попеременно в обеих упомянутых системах координат.

Объем вычислений для любого алгоритма, работающего в объектном пространстве, и сравнивающего каждый объект сцены со всеми остальными объектами этой сцены, растет теоретически как квадрат числа объектов (n2).

Аналогично, объем вычислений любого алгоритма, работающего в пространстве изображения и сравнивающего каждый объект сцены с позициями всех пикселов в системе координат экрана, растет теоретически, как nN. Здесь п обозначает количество объектов (тел, плоскостей или ребер) в сцене, а N - число пикселов. Теоретически трудоемкость алгоритмов, работающих в объектном пространстве, меньше трудоемкости алгоритмов, работающих в пространстве изображения, при n<N. Поскольку N обычно равно (512)2, то теоретически большинство алгоритмов следует реализовывать в объектном пространстве. Однако на практике это не так. Дело в том, что алгоритмы, работающие в пространстве изображения, более эффективны потому, что для них легче воспользоваться преимуществом когерентности при растровой реализации.


1. Описание алгоритма удаления невидимых линий и поверхностей алгоритмом плавающего горизонта


1.1Общий алгоритм (Описание алгоритма)


Алгоритм плавающего горизонта чаше всего используется для удаления невидимых линий трехмерного представления функций, описывающих поверхность в виде:


F(x, у, z) = 0.


Подобные функции возникают во многих приложениях в математике, технике, естественных науках и других дисциплинах.

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




На рис.10.2 приведен пример, где указанные параллельные плоскости определяются постоянными значениями z. Функция F(x,у,z) = 0 сводится к последовательности кривых, лежащих в каждой из этих параллельных плоскостей, например к последовательности


у = f(x, z) или х = g (у, z)


где z постоянно на каждой из заданных параллельных плоскостей.

Итак, поверхность теперь складывается из последовательности кривых, лежащих в каждой из этих плоскостей, как показано на рис. 10.3. Здесь предполагается, что полученные кривые являются однозначными функциями независимых переменных. Если спроецировать полученные кривые на плоскость z=0, как показано на рис.10.4, то сразу становится ясна идея алгоритма удаления невидимых участков исходной поверхности. Алгоритм сначала упорядочивает плоскости z=const по возрастанию расстояния до них от точки наблюдения. Затем для каждой плоскости, начиная с ближайшей к точке наблюдения, строится кривая, лежащая на ней, т. е. для каждого значения координаты х в пространстве изображения определяется соответствующее значение y. Алгоритм удаления невидимой линии заключается в следующем:



Если на текущей плоскости при некотором заданном значении x соответствующее значение у на кривой больше значения y для всех предыдущих кривых при этом значении x, то текущая кривая видима в этой точке; в противном случае она невидима.

Невидимые участки показаны пунктиром на рис. 10.4. Реализация данного алгоритма достаточно проста. Для хранения максимальных значений y при каждом значении x используется массив, длина которого равна числу различимых точек (разрешению) по оси x в пространстве изображения. Значения, хранящиеся в этом массиве, представляют собой текущие значения "горизонта". Поэтому по мере рисования каждой очередной кривой этот горизонт "всплывает". Фактически этот алгоритм удаления невидимых линий работает каждый раз с одной линией. Алгоритм работает очень хорошо до тех пор, пока какая-нибудь очередная кривая не окажется ниже самой первой из кривых, как показано на рис. 10.5а.



Подобные кривые, естественно, видимы и представляют собой нижнюю сторону исходной поверхности, однако алгоритм будет считать их невидимыми. Нижняя сторона поверхности делается видимой, если модифицировать этот алгоритм, включив в него нижний горизонт, который опускается вниз по ходу работы алгоритма. Это реализуется при помощи второго массива, длина которого равна числу различимых точек по оси x в пространстве изображения. Этот массив содержит наименьшие значения y для каждого значения x. Алгоритм теперь становится таким:

Если на текущей плоскости при некотором заданном значении x соответствующее значение y на кривой больше максимума или меньше минимума по y для всех предыдущих кривых при этом x, то текущая кривая видима. В противном случае она невидима.

Полученный результат показан на рис.10.5b.

В изложенном алгоритме предполагается, что значение функции, т.е. y, известно для каждого значения x в пространстве изображения. Однако если для каждого значения х нельзя указать (вычислить) соответствующее ему значение y, то невозможно поддерживать массивы верхнего и нижнего плавающих горизонтов. В таком случае используется линейная интерполяция значений y между известными значениями для того, чтобы заполнить массивы верхнего и нижнего плавающих горизонтов, как показано на рис. 10.6. Если видимость кривой меняется, то метод с такой простой интерполяцией не даст корректного результата. Этот эффект проиллюстрирован рис. 10.7а. Предполагая, что операция по заполнению массивов проводится после проверки видимости, получаем, что при переходе текущей кривой от видимого к невидимому состоянию (сегмент AB на рис. 10.7а), точка (XN+K,YN+K) объявляется невидимой. Тогда участок кривой между точками (XN,YN) и (XN+K,YN+K) не изображается и операция по заполнению массивов не проводится. Образуется зазор между текущей и предыдущей кривыми. Если на участке текущей кривой происходит переход от невидимого состояния к видимому (сегмент CD на рис.10.7а), то точка (XM+K,YM+K) объявляется видимой, а участок кривой между точками (XM,YM) и (XM+K,YM+K) изображается и операция по заполнению массивов проводится. Поэтому изображается и невидимый кусок сегмента CD. Кроме того, массивы плавающих горизонтов не будут содержать точных значений y. А это может повлечь за собой дополнительные нежелательные эффекты для последующих кривых.



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

Существует несколько методов получения точек пересечения кривых. На растровых дисплеях значение координаты x можно увеличивать на 1, начиная с xn или xm (рис.10.7а). Значение y, соответствующее текущему значению координаты x в пространстве изображения, получается путем добавления к значению y, соответствующему предыдущему значению координаты x, вертикального приращения ?y вдоль заданной кривой. Затем определяется видимость новой точки с координатами (x+1,у + dy). Если эта точка видима, то активируется связанный с ней пиксел. Если невидима, то пиксел не активируется, а x увеличивается на 1. Этот процесс продолжается до тех пор, пока не встретится xn+k или xm+k. Пересечения для растровых дисплеев определяются изложенным методом с достаточной точностью.

Теперь алгоритм излагается более формально.

Если на текущей плоскости при некотором заданном значении x соответствующее значение у на кривой больше максимума или меньше минимума по y для всех предыдущих кривых при этом, то текущая кривая видима. В противном случае она невидима. Если на участке от предыдущего (xn) до текущего (xn+k) значения x видимость кривой изменяется, то вычисляется точка пересечения (xi). Если на участке от xn до xn+k сегмент кривой полностью видим, то он изображается целиком; если он стал невидимым, то изображается фрагмент от xn до xi; если же он стал видимым, то изображается фрагмент от xi до xn+k. Заполнить массивы верхнего и нижнего плавающих горизонтов.

Типичный результат работы алгоритма:



2. Структура программы


Программа в основном состоит из трех основных частей:

. Функция вычисления значения функции в данных точках.

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

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

Методы реализации:

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

Процедура получения значения функции

Передаваемые параметры: X, Z

На выходе: Y

Y=значение функции в точке (x,z)

Например: Х=1, Z=1, F(x)=У=x^2+z^2

Тогда при заданных значениях X и Z получим: Y = 2.

.Процедура расчета точек, которые необходимо вывести на экран для получения нужного изображения, заключается в том, что для получения точек, к координатам X,Y,Z применяется видовое преобразование. Т.е точка из трехмерного пространства переводится в двумерное (путем параллельного проецирования):

Перед визуализацией поверхности необходимо применить видовое преобразование. Поверхность сначала надо повернуть на 30 градусов относительно оси Y, затем на какой-либо угол относительно оси X. Результат проецируется на плоскость Z=0 из центра проекции, находящейся в бесконечности на оси +Z.

Т.е сначала получаются точки в трехмерном пространстве, а затем они проектируются на плоскость ХОУ таким образом:

Хэкрана=Хтрехмерный*cos(alfa)+Zтрехмерный*sin(alfa)

Yэкрана=Хтрехмерный *sin(alfa)*sin(beta)+Yтрехмерный*cos(beta)-Zтрехмерный*sin(beta)*cos(alfa)


. Интерфейсная часть реализовывается согласно потребностям пользователя в проделывании той или иной работы с поверхностью и её заданными границами определения.


3. Описание программы



Все возможные настройки можно определить путем нажатия на кнопку "Настройки". После появления окна можно производить манипуляции с параметрами программы. Окно настроек:



В программе имеется возможность сохранить результат работы алгоритма в BMP файл, что, на мой взгляд, является одним из её положительных качеств. (Например: преподавателю нужны графики трехмерных функций для проведения лекции).


4. Инструкция пользователю


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

Самым неудачным результатом работы программы может быть отсутствие изображения на экране. Это значит то, что не верно задан один из параметров.

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

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


5. Алгоритм реализации


Переменные:

Dx приращение по Х

Dz приращение по Z

Lengx длинна отрезка Х

Lengz длинна отрезка Z

x0,y0,z0,x1,y1,z1 пременные начала и конца по заданной координате.

Scaley коэффициент умножения по У

hor1 массив[0..кол-во точек по Х]

hor2 массив[0.. кол-во точек по Х]

i,ik переменные для организации внутрипрограммных циклов

alfa,beta переменные определяющие углы проецирования.

Функция fy(Параметры x,z) //Вызывается для расчета текущих значений

Начало

:=(cos(x*x-z*z+2)*20/(x*x-x+z*z+1));


Конец


procedure func3d(Параметры cu,cd - цвета горизонтов);

,z текущие координаты.

rx,ry преобразованные координаты.

rxt,ryt временные значения.

flag1,flag2 флаги.

Xv для перехода к следующей координате Х.

Начало

Присваиваем обоим флагам значение "Истина"

Присваиваем текущему Z Z Начальное.

Пока не обработали все Z делаем:

.1 присваиваем текущему Х значение Х начального.

.2 Пока не обработали все Х делаем:

.2.1Наращиваем xv.

.2.2Наращиваем Х на приращение по Х

.2.3 Вычислим промежуточные значения.rxt,ryt

.3.4 Производим над координатами операцию видового преобразования.

.3.5 Присваиваем обоим флагам значение "Истина"

.3.6 Обрабатываем первый горизонт: Если значение по У в данной точке х меньше чем для предыдущей Z, то запоминаем его в массив, и присваиваем флагу1 "Ложь"

.3.7 Обрабатываем второй горизонт: Если значение по У в данной точке х больше чем для предыдущей Z, то запоминаем его в массив, и присваиваем флагу2 "Ложь".

.3.8 Если флаг1 "Ложь" то вывести данную точку определенного цвета на экран.

.3.9 Если флаг2 "Ложь" то вывести данную точку другого цвета на экран.

Обработали все X конец цикла.

.4 Наращиваем Z на его приращение.

.5 Конец цикла по Z.

Конец процедуры.

Данная вставка используется для инициализации горизонтов:

i:=0 to 639 do hor1[i]:=0; верхний горизонт.i:=0 to 639 do hor2[i]:=480; нижний горизонт.


6. Описание программного продукта


6.1 Программно-аппаратные требования


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

Операционная система Windows XP/Vista/7

Видеоадаптер 8 МБ RAM

Оперативная память объемом 256 МБ

Клавиатура, мышь

2 МБ свободной памяти на жестком диске


.2 Язык и среда программирования


В данной работе, при описании алгоритма, был использован язык Delphi, как один из наиболее доступных и максимально подходящих для описания поставленной задачи. Использована программа Borland Delphi 7.


Приложение


Текст программы.

Unit1;

interface, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, ExtCtrls;Maxx=641;= class(TForm): TImage;: TButton;: TRadioButton;: TRadioButton;: TButton;: TButton;: TButton;: TButton;: TLabel;: TButton;Button1Click(Sender: TObject);FormCreate(Sender: TObject);Button2Click(Sender: TObject);Button3Click(Sender: TObject);Button5Click(Sender: TObject);Button4Click(Sender: TObject);Button6Click(Sender: TObject);

{ Private declarations }

{ Public declarations };: TForm1;,dz:real;,lengz:real;,y0,z0,x1,y1,z1:real;,scaley:real;,gm:integer;:array[0..Maxx]of integer;:array[0..Maxx]of integer;,ik:integer;,beta:real;Unit2, Unit3;

{$R *.dfm}fy(x,z:real):real;:=cos(x*x-z*z+2)*20/(x*x-x+z*z+1);;fy1(x,z:real):real;a:real;:=sqr(x-pi)+sqr(z-pi);:=(1/5)*sin(x)*cos(z)-(3/2)*cos(7*a/4)*exp(-a);;func3d(cu,cd:integer);x,z:real;,ry:integer;,ryt:real;,flag2:boolean;:integer;:=true;flag2:=true;:=z0;( z<z0+lengz) do:=x0;:=0;x<x0+lengx do(xv);:=x+dx;:=xv;:=(fy(x,z)*scaley);:=round(rxt*cos(alfa)+z*sin(alfa));:=round(rxt*sin(alfa)*sin(beta)+ryt*cos(beta)-z*sin(beta)*cos(alfa));:=true;:=true;(hor1[rx]<ry) then:=false;[rx]:=ry;;(hor2[rx]>ry) then:=false;[rx]:=ry;;(not(flag1))then.Image1.canvas.pixels[rx,round(form1.image1.height/2)-ry-round(Strtofloat(form2.Edit13.Text))]:=ClGreen;if(not(flag2)) then form1.Image1.canvas.pixels[rx,round(form1.image1.height/2)-ry-round(Strtofloat(form2.Edit13.Text))]:=ClBlue;;:=z+dz;;;func3d1(cu,cd:integer);x,z:real;,ry:integer;,ryt:real;,flag2:boolean;:integer;:=true;flag2:=true;:=z0;( z<z0+lengz) do:=x0;:=0;x<x0+lengx do(xv);:=x+dx;:=xv;:=(fy1(x,z)*scaley);:=round(rxt*cos(alfa)+z*sin(alfa));:=round(rxt*sin(alfa)*sin(beta)+ryt*cos(beta)-z*sin(beta)*cos(alfa));:=true;:=true;(hor1[rx]<ry) then:=false;[rx]:=ry;;(hor2[rx]>ry) then:=false;[rx]:=ry;;(not(flag1))then.Image1.canvas.pixels[rx,round(form1.image1.height/2)-ry-round(Strtofloat(form2.Edit13.Text))]:=ClGreen;if(not(flag2)) then form1.Image1.canvas.pixels[rx,round(form1.image1.height/2)-ry-round(Strtofloat(form2.Edit13.Text))]:=ClBlue;;:=z+dz;;;TForm1.Button1Click(Sender: TObject);.click;radiobutton2.checked thenform2 doradiobutton1.Checked then:=Pi/180*30;:=pi/180*15;;radiobutton2.Checked then:=Pi/180*45;:=pi/180*15;;radiobutton3.Checked then:=Pi/180*5;:=pi/180*45;;:=StrtoFloat(Edit5.text); //-6:=StrtoFloat(Edit6.text); //6:=x1-x0;:=lengx/Image1.Width;:=StrtoFloat(Edit7.text); //-6:=StrtoFloat(Edit8.text); //6:=z1-z0;:=StrtoFloat(Edit10.text); //0.05:=StrtoFloat(Edit12.text); //10;i:=0 to Maxx do hor1[i]:=0;i:=0 to Maxx do hor2[i]:=417;d(2,4);;radiobutton1.checked thenform2 doradiobutton1.Checked then:=Pi/180*30;:=pi/180*15;;radiobutton2.Checked then:=Pi/180*45;:=pi/180*15;;radiobutton3.Checked then:=Pi/180*5;:=pi/180*45;;:=StrtoFloat(Edit1.text); //0:=StrtoFloat(Edit2.text); //2pi:=x1-x0;:=lengx/Image1.Width;:=StrtoFloat(Edit3.text); //0:=StrtoFloat(Edit4.text); //4pi:=z1-z0;:=StrtoFloat(Edit9.text); //0.1:=StrtoFloat(Edit11.text); //80;i:=0 to Maxx do hor1[i]:=0;i:=0 to Maxx do hor2[i]:=417;d1(2,4);;;TForm1.FormCreate(Sender: TObject);x,y:integer;y:=0 to image1.Height dox:=0 to image1.Width do.Canvas.Pixels[x,y]:=clblack;;TForm1.Button2Click(Sender: TObject);x,y:integer;y:=0 to image1.Height dox:=0 to image1.Width do.Canvas.Pixels[x,y]:=clblack;;TForm1.Button3Click(Sender: TObject);.show;;TForm1.Button5Click(Sender: TObject);.Close;;TForm1.Button4Click(Sender: TObject);.showmodal;;TForm1.Button6Click(Sender: TObject);.Picture.Bitmap.SaveToFile('out.bmp');

end;.

unit Unit2;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls;= class(TForm): TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TRadioButton;: TRadioButton;: TRadioButton;: TLabel;: TButton;: TEdit;: TLabel;: TEdit;: TLabel;: TEdit;: TLabel;: TEdit;: TLabel;: TButton;: TEdit;: TLabel;: TLabel;Button1Click(Sender: TObject);Button2Click(Sender: TObject);

{ Private declarations }

{ Public declarations };: TForm2;Unit1;

{$R *.dfm}TForm2.Button1Click(Sender: TObject);.button1.click;.Close;;TForm2.Button2Click(Sender: TObject);

begin.close;;.


Аннотация В работе представлены теоретические основы машинной графики, необходимые для организации алгоритмов удаления невидимых линий и поверхностей. Со

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ