Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритм Коена-Засерленда
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра автоматизованих систем управління
Інформація про роботу
Рік:
2014
Тип роботи:
Лабораторна робота
Предмет:
Комп'ютерна графіка
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет «Львівська політехніка»
Кафедра автоматизованих систем управління
/
Лабораторна робота №4
з дисципліни
«Комп’ютерна графіка»
на тему:
“Алгоритм Коена-Засерленда”
Львів 2014
Лабораторна робота №4
Тема: Алгоритм Коена-Сазерленда
Мета роботи: вивчення алгоритму Коена-Сазерленда
Теоретичні відомості:
Перед тим, як досліджувати методи одержання зображень більш складних,
ніж відрізки прямих, розглянемо проблему, присутню в більшості задач
комп'ютерної графіки. Ця проблема відсікання зображення за деякою межею,
наприклад, по межі екрану, або, в загальному випадку, деякого прямокутного
вікна. Розглянемо цю задачу стосовно відрізкам прямих. Деякі з них повністю
лежать всередині області екрану, інші цілком поза нею, а деякі перетинають
межу екрану. Правильне відображення відрізків означає знаходження точок
перетину їх з межею екрану і малювання тільки тих їх частин, які потрапляють
на екран. Один з очевидних способів відсікання відрізків полягає у визначенні
точок перетину прямої, що містить відрізок, з кожної з чотирьох прямих, на
яких лежать межі вікна та перевірки чи не лежить хоча б одна точка перетину
на межі. У цьому випадку для кожної пари сторона-відрізок необхідно
вирішувати систему з двох рівнянь, використовуючи операції множення і
ділення.
Якщо зображення виходить за межі екрану, то на частини дисплеїв
збільшується час побудови за рахунок того, що зображення будується в
"думці". У деяких дисплеях вихід за межі екрану призводить до спотворення
картини, так як координати просто обмежуються при досягненні ними
граничних значень, а не виконується точний розрахунок координат перетину
(ефект "стягування" зображення). Деякі, в основному, прості дисплеї просто не
допускають виходу за межі екрану. Все це, особливо в зв'язку з широким
використанням технології перегляду вікнами, потребує виконання відсікання
сцени по кордонах вікна видимості.
У простих графічних системах достатньо двомірного відсікання, в
тривимірних пакетах використовується трьох і чотиривимірне відсікання.
Останнє виконується в раніше розглянутих однорідних координатах, що
дозволяють єдиним чином виконувати аффінні і перспективні перетворення.
Програмне виконання відсікання достатньо повільний процес, тому,
природно, в потужні дисплеї вбудовується відповідна апаратура. Перше
повідомлення про апаратуру відсікання, що використовує алгоритм відсікання діленням відрізка навпіл і реалізованої в пристрої Clipping Divider, з'явилося в
1968 р. Цей алгоритм був розглянутий при вивченні технічних засобів. Тут ми
розглянемо програмні реалізації алгоритму відсікання.
Відсікаються відрізки можуть бути трьох класів - цілком видимі, цілком
невидимі і які перетинають вікно. Очевидно, що доцільно можливо більш рано,
без виконання великого обсягу обчислень прийняти рішення про видимості
цілком або відкиданні. За способом вибору простого рішення про відкидання
невидимого відрізка цілком або прийняття його існує два основних типи
алгоритмів відсікання - алгоритми, які використовують кодування кінців
відрізка або всього відрізка і алгоритми, які використовують параметричне
представлення відсікаються відрізків і вікна відсікання. Представники першого
типу алгоритмів - алгоритм Коена-Сазерленда (Cohen-Sutherland, CS-алгоритм)
і FC-алгоритм (Fast Clipping - алгоритм). Представники алгоритмів другого
типу - алгоритм Кірус-Бека (Curus-Beck, CB - алгоритм) і пізніший алгоритм
Ліанга-Барського (Liang-Barsky, LB-алгоритм).
Алгоритми з кодуванням застосовні для прямокутного вікна, сторони
якого паралельні осях координат, в той час як алгоритми з параметричним
представленням застосовні для довільного вікна.
Спочатку ми розглянемо алгоритм Коена-Сазерленда, який є стандартом
де-факто алгоритму відсікання ліній і володіє одним з кращих швидкодії при
компактній реалізації. Потім розглянемо найбільш швидкий, але і надзвичайно
громіздкий FC-алгоритм. Далі розглянемо алгоритм Ліанга-Барського для
відсікання прямокутним вікном з використанням параметричного подання.
Швидкодія цього алгоритму порівнянно з швидкодією алгоритму Коена-
Сазерленда при більшої компактності і наявності 3D і 4D реалізацій. Останнім
розглянемо алгоритм Кірус-Бека, який використовує параметричне
представлення і дозволяє відсікати довільним опуклим вікном. На закінчення
порівняємо швидкодію різних алгоритмів.
Розглянемо алгоритм Коена-Сазерленcда для відсікання відрізків прямих.
Цей алгоритм дозволяє легко визначати знаходження відрізка повністю
всередині або повністю зовні вікна, і якщо так, то його можна малювати або не
малювати, не піклуючись про відсікання по межі вікна.
Для роботи алгоритму вся площина в якій лежить вікно розбивається на
дев'ять підобластей або квадрантів. Вікну відповідає область позначена кодом 0000. Кінцевим точкам відрізку
приписується 4-бітний код "поза / усередині" в залежності від знаходження
відрізка у відповідній підобласті. Кожному біту присвоюється значення 1 у
відповідності з наступним правилом.
Біт 1 - точка перебуває вище вікна;
Біт 2 - точка знаходиться нижче вікна;
Біт 3 - точка знаходиться праворуч від вікна;
Біт 4 - точка знаходиться зліва від вікна;
Інакше біту присвоюється нульове значення. Значення цих бітів для
кінцевих точок відрізків легко визначити по знаках відповідних різниць: (ymaxy)
- для 1-го біта, (y-ymin) - для 2-го біта, (xmax-x) - для 3-го біта і (x-xmin) - для 4-го
біта. Відрізок малюється без відсікання, тобто приймається цілком, якщо
обидва коди дорівнюють 0000, або [код Р1] АБО [код Р1] = 0000, де АБО -
бінарна операція. Відрізок відкидається без обчислень якщо обидва його кінця
знаходяться вище, нижче, правіше або лівіше вікна. У цих випадках відповідні
біти в обох кодах рівні 1 і це легко визначити, помноживши ці коди по бінарної
операції І. Якщо результат операції І дорівнює 0000, то відрізок не можна ні
прийняти ні відкинути, так як він може перетинатися з вікном. У цьому
випадку застосовується послідовне поділ відрізка, так що на кожному кроці
кінцева точка відрізка з ненульовим кодом поза / всередині замінюється на
точку, що лежить на боці вікна або на прямій містить сторону. При цьому
порядок перебору сторін вікна не має значення.
Код програми
import java.awt.*;
import java.applet.Applet;
import java.awt.event.*;
class Point
{
double x,y;
Point(double thisx, double thisy)
{
x=thisx;
y=thisy;
}
}
public class laba4 extends Applet
{
final int xMax = 500,yMax = 400;
private int firstX, firstY,lastX,lastY,points = 0;
static double xLeft=100.0, xRight=400.0,yBottom=100.0, yTop=300.0;
//dimensions of rectangle to clip against
Point P0,P1;
public void init()
{
resize( xMax, yMax );
this.addMouseListener(new MouseAdapter(){
public void mousePressed(MouseEvent evt)
{
if(points == 0) { firstX=evt.getX(); firstY=evt.getY(); points++;}
else if (points == 1)
{lastX=evt.getX(); lastY=evt.getY(); points = 0;
P0 = new Point((double)firstX,(double)firstY);
P1 = new Point((double)lastX,(double)lastY);
paint(getGraphics());}
}});
show();
}
public void paint(Graphics g)
{
g.drawRect((int)xLeft,(int)yBottom, (int)(xRight-xLeft), (int)(yTop-yBottom));
if(CohenSutherland2DClipper(P0,P1))
g.drawLine((int)P0.x,(int)P0.y, (int)P1.x,(int)P1.y);
}
private static int outCodes(Point P)
{
int Code = 0;
if(P.y > yTop) Code += 1;
else if(P.y < yBottom) Code += 2;
if(P.x > xRight) Code += 4;
else if(P.x < xLeft) Code += 8;
return Code;
}
private static boolean rejectCheck(int outCode1, int outCode2)
{
if ((outCode1 & outCode2) != 0 ) return true;
return(false);
}
private static boolean acceptCheck(int outCode1, int outCode2)
{
if ( (outCode1 == 0) && (outCode2 == 0) ) return(true);
return(false);
}
static boolean CohenSutherland2DClipper(Point P0,Point P1)
{
int outCode0,outCode1;
while(true)
{
outCode0 = outCodes(P0);
outCode1 = outCodes(P1);
if( rejectCheck(outCode0,outCode1) ) return(false);
if( acceptCheck(outCode0,outCode1) ) return(true);
if(outCode0 == 0)
{
double tempCoord; int tempCode;
tempCoord = P0.x; P0.x= P1.x; P1.x = tempCoord;
tempCoord = P0.y; P0.y= P1.y; P1.y = tempCoord;
tempCode = outCode0; outCode0 = outCode1; outCode1 = tempCode;
}
if( (outCode0 & 1) != 0 )
{
P0.x += (P1.x - P0.x)*(yTop - P0.y)/(P1.y - P0.y);
P0.y = yTop;
}
else
if( (outCode0 & 2) != 0 )
{
P0.x += (P1.x - P0.x)*(yBottom - P0.y)/(P1.y - P0.y);
P0.y = yBottom;
}
else
if( (outCode0 & 4) != 0 )
{
P0.y += (P1.y - P0.y)*(xRight - P0.x)/(P1.x - P0.x);
P0.x = xRight;
}
else
if( (outCode0 & 8) != 0 )
{
P0.y += (P1.y - P0.y)*(xLeft - P0.x)/(P1.x - P0.x);
P0.x = xLeft;
}
}
}
}
Висновок: в даній роботі я вивчив алгоритм Коена-Сазерленда та реалізував його на java.
30.05.2015 16:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора