Лабораторна робота № 5 Метод цифрового диференціального аналізатора
Мета роботи: Освоїти розкладаннявідрізка в растр методом цифрового диференціального аналізатора.
Теоретичні відомості
Один з методів розкладання відрізка в растр полягає в розв’язуванні диференціального рівняння, що описує цей процес. Для прямої лінії маємо dy/dx=const чи Dy/Dx=(y2 - y1)/(x2 - x1)
Розв’язок представляється у вигляді
yi+1=yi+Dy yi+1=yi+Dx(y2-y1)/(x2-x1)
де x1, y1 і x2, y2 - кінці відрізка, що розкладається, і yi - початкове значення для чергового кроку вздовж відрізка. Фактично рівняння являє собою рекурентне співвідношення для послідовних значень y вздовж потрібного відрізка. Цей метод, використовуваний для розкладання в растр відрізків, називається цифровим диференціальним аналізатором (ЦДА). У простому ЦДА або Dx, або Dy (більше із збільшень) вибирається як одиниця растра. Нижче наводиться простий алгоритм, що працює у всіх квадрантах:
Процедура розкладання в растр відрізка по методу цифрового диференціального аналізатора (ЦДА)
Передбачається, що кінці відрізка (x1, y1) і (x2, y2) не збігаються
Апроксимуємо довжину відрізка
if abs(x2-x1)>=abs(y2-y1) then
Довжина=abs(x2-x1)
else
Довжина=abs(y2-y1)
End { if }
назначаємо більше із збільшень Dx чи Dy рівним одиниці растра
Dx=(x2-x1)/Довжина
Dy=(y2-y1)/Довжина
округляємо величини, а не відкидаємо дробову частину
використання знакової функції робить алгоритм придатним для всіх квадрантів
x=x1;
y=y1;
Plot (round(x), round(y)) //промалювання пікселя
початок основного циклу
i=1
while (i<=Довжина) do
x=x+Dx
y=y+Dy
i=i+1
Plot (round(x), round(y))
End; {while}
finish
Розглянемо відрізок із точки (0,0) у точку (-8,-4) в третьому квадранті. Використовуємо ЦДА для розкладання цього відрізка в растр. Результати роботи алгоритму такі:
початкові установки
x1=0
y1=0
x2=-8
y2=-4
Довжина=8
Dx=-1
Dy=-0,5
x=-0,5
y=-0,5
Таблиця 1
Результати роботи покрокового циклу
Незважаючи на те що результати, представлені на рис.2.2, виглядають цілком прийнятними, аналіз відрізків, проведених із точки (0,0) у точку (-8,4) і (8,-4), показує, що розкладений у растр відрізок лежить по одну сторону від реального і що на одному з кінців відрізка з’являється зайва точка, тобто результат роботи алгоритму залежить від орієнтації. Отже точність у кінцевих точках зменшується.
Рис.5.1. Результати роботи простого ЦДА в третьому квадранті.
ПОРЯДОК ВИКОНАННЯ РОБОТИ
1. Побудуйте декартову двовимірну систему координат, у якій максимальне значення по осях x i y було би близько 10 і початок координат був би по центру.
2. Розграфте площину побудови відрізків у вигляді сітки, на якій будуть будуватися піксели.
3. Побудуйте псевдовідрізок, який би з’єднував початок з кінцем відрізку.
4. Приведіть результат роботи алгоритму накреслення відрізку, методом цифрового диференціального аналізатора, у якому би підсвічувалися піксели, або ж клітинки сітки.
5. Проаналізуйте результати.
ЗМІСТ ЗВІТУ
Звіт повинен містити:
1) назву роботи;
2) мету роботи;
3) короткий теоретичний вступ;
4) завдання до лабораторної роботи;
5) тексти розроблених і відлагоджених програм
6) малюнки з реалізацією програми
7) висновки
ПРИКЛАД ПРОГРАМНОЇ РЕАЛІЗАЦІЇ
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
ExtCtrls,math, StdCtrls, Spin;
type
b=array[1..2,1..2] of real;
TForm1 = class(TForm)
p: TPaintBox;
Label1: TLabel;
Label2: TLabel;
SpinEdit1: TSpinEdit;
Panel1: TPanel;
Panel2: TPanel;
procedure pPaint(Sender: TObject);
procedure pMouseDown(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
procedure pMouseMove(Sender: TObject; Shift: TShiftState; X,
Y: Integer);
procedure pMouseUp(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
procedure SpinEdit1Change(Sender: TObject);
procedure FormCreate(Sender: TObject);
procedure Panel2Click(Sender: TObject);
procedure Panel1Click(Sender: TObject);
end;
var
Form1: TForm1;
pos:b;
DR:boolean=false;
temp_x,temp_y:real;
dx:integer;
implementation
{$R *.DFM}
procedure draw;
var pos_x,pos_y,pos_xx,pos_yy:real;
i:integer;
Dy,Dxx,l:real;
begin form1.p.Canvas.Brush.Style:=bssolid;
if abs(pos[2,1]-pos[1,1])>=abs(pos[2,2]-pos[1,2]) then
L:=abs((pos[2,1]-pos[1,1])) else L:=abs(pos[2,2]-pos[1,2]) ;
dxx:=((pos[2,1]-pos[1,1])/l)*dx;
dy:=((pos[2,2]-pos[1,2])/l)*dx;
pos_x:=((pos[1,1]*dx));
pos_y:=((pos[1,2]*dx));
i:=1; form1.p.Canvas.Brush.Color:=cllime; form1.p.Canvas.Rectangle (round(pos_x),round(pos_y), round(pos_x+dx),round(pos_y+dx)); form1.p.Canvas.Brush.Color:=clblack;
while i<=l do
begin
pos_xx:=0;
pos_yy:=0;
pos_x:=(pos_x+dxx);
pos_y:=(pos_y+dy); form1.p.Canvas.Brush.Style:=bssolid; form1.p.Canvas.Brush.Color:=cllime;
if (round(pos_y) mod dx) <>0 then
begin
pos_yy:=(round(pos_y) / dx);
pos_yy:=pos_Y-(round(pos_yy)*DX); //D(X)
pos_yy:=pos_y-pos_YY; //x-dx pos_xx:=pos_x;
end else pos_yy:=pos_y;
if (round(pos_x) mod dx) <>0 then
begin
pos_xx:=(round(pos_x) / dx);
pos_xx:=pos_x-(round(pos_xx)*dx);
pos_xx:=pos_x-pos_xx;
pos_yy:=pos_y;
end else pos_xx:=pos_x; form1.p.Canvas.Rectangle(round(pos_xx), round(pos_yy), round(pos_xx+dx),round(pos_yy+dx)); form1.p.Canvas.Brush.Color:=clblack;
inc(i);
end;
end;
procedure TForm1.pPaint(Sender: TObject);
var i:integer;
begin
p.Canvas.FillRect(clientrect); i:=0;
p.Canvas.Pen.Color:=clwhite;
while i<=p.Width do
begin
p.Canvas.moveto(i,0);
p.Canvas.lineto(i,p.Height);
inc(i,dx);
end; i:=0;
while i<=p.height do
begin
p.Canvas.moveto(0,i);
p.Canvas.lineto(p.width,i);
inc(i,dx);
end;
end;
procedure TForm1.pMouseDown(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
begin
ppaint(form1);
DR:=true;
pos[1,1]:=x;
pos[1,2]:=y;
temp_x:=pos[1,1];
temp_y:=pos[1,2];
end;
procedure TForm1.pMouseMove(Sender: TObject; Shift: TShiftState; X,
Y: Integer);
begin
if dr then
begin
p.Canvas.Pen.Mode:=pmxor; p.Canvas.MoveTo(round(pos[1,1]), round(pos[1,2])); p.Canvas.lineTo(round(temp_x), round(temp_y));
p.Canvas.Pen.Color:=clyellow;
pos[2,1]:=x;
pos[2,2]:=y;
form1.Canvas.Font.Color:=cllime;
label1.Caption:=’X = ‘+IntToStr(Round(pos[2,1]/dx))+#10+#13+’Y = ‘+IntToStr(Round(pos[2,2]/dx)); p.Canvas.MoveTo(round(pos[1,1]), round(pos[1,2])); p.Canvas.lineTo(round(x),round(y));
temp_x:=x;
temp_y:=y;
end;
end;
procedure TForm1.pMouseUp(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
var i:byte;
begin
i:=0;
if round(pos[1,1]) mod dx <>0 then
while round(pos[1,1]-i) mod dx <>0 do
inc(i);
pos[1,1]:=pos[1,1]-i;
i:=0;
if round(pos[1,2]) mod dx <>0 then
while round(pos[1,2]-i) mod dx <>0 do
inc(i);
pos[1,2]:=pos[1,2]-i ;
i:=0;
if round(x) mod dx <>0 then
while round(x-i) mod dx <>0 do
inc(i);
pos[2,1]:=x-i;
i:=0;
if round(y) mod dx <>0 then
while round(y-i) mod dx <>0 do
inc(i);
pos[2,2]:=y-i ;
pos[2,1]:=pos[2,1] / dx;
pos[2,2]:=pos[2,2] / dx;
pos[1,1]:=pos[1,1] / dx;
pos[1,2]:=pos[1,2] / dx;
dr:=false;
if LAb=2 then
if (pos[1,1]<>pos[2,1])or(pos[2,2]<>pos[1,2]) then
draw else else
if (pos[1,1]<>pos[2,1])or(pos[2,2]<>pos[1,2]) and (lab=1)then
draw1;
end;
procedure TForm1.SpinEdit1Change(Sender: TObject);
begin
if SpinEdit1.Value>1 then
dx:=SpinEdit1.Value;
ppaint(form1);
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
SpinEdit1.Value:=50;
dx:=SpinEdit1.value;
end;
procedure TForm1.Panel2Click(Sender: TObject);
begin
panel2.BevelOuter:=bvLowered;
panel2.Color:=clActiveBorder;
panel1.BevelOuter:=bvRaised;
panel1.Color:=clBtnFace;
form1.Caption:=’LAB 4';
lab:=1;
end;
procedure TForm1.Panel1Click(Sender: TObject);
begin
panel1.BevelOuter:=bvLowered;
panel1.Color:=clActiveBorder;
panel2.BevelOuter:=bvRaised;
panel2.Color:=clBtnFace;
form1.Caption:=’LAB 5';
lab:=2;
end;
end.
Лабораторна робота № 6
Алгоритм Брезенхема для побудови прямих
Мета роботи: Освоїти алгоритм Брезенхема для побудови прямих
Теоретичні відомості
6.1. Алгоритм Брезенхема для побудови прямих у першому октанті
Хоча алгоритм Брезенхема був спочатку розроблений для цифрових графопобудовувачів. Проте він має застосування для растрових пристроїв з ЕПТ. Алгоритм вибирає оптимальні растрові координати для представлення відрізка. У процесі роботи одна з координат - або x, або y (в залежності від кутового коефіцієнта) - змінюється на одиницю. Зміна іншої координати (на 0 чи 1) залежить від відстані між дійсним положенням відрізка і найближчих координат сітки. Таку відстань ми назвемо похибкою.
Алгоритм побудований так, що потрібно перевірити лише знак цієї похибки. На рис.6.1 це ілюструється для відрізка в першому октанті, тобто для відрізка з кутовим коефіцієнтом, що лежить у діапазоні від 0 до 1. З рисунка можна помітити що, якщо кутовий коефіцієнт відрізка з точки (0,0) більший, ніж 1/2, то перетин з прямою x=1 буде розташований ближче до прямої y=1, ніж до прямої y=0. Отже, точка растра (1,1) краще апроксимує хід відрізка, ніж точка (1,0). Якщо кутовий коефіцієнт менше 1/2, то навпаки. для кутового коефіцієнта, рівного 1/2, немає кращого вибору. У даному випадку вибирається точка (1,1).
Рис.6.1. Вибір точки за методом Брезенхема.
Не усі відрізки проходять через точки растра. Подібна ситуація ілюструється рис.3.2, де відрізок з тангенсом кута нахилу 3/8 спочатку проходить через точку растра (0,0) і послідовно перетинає три піксели. Також ілюструється обчислення похибки при представленні відрізка дискретними пікселами.
Рис.6.2. Графік похибки в алгоритмі Брезенхема
Оскільки бажано перевіряти тільки знак похибки, то вона спочатку встановлюється рівною -1/2. Таким чином, якщо кутовий коефіцієнт відрізка дорівнює чи більший 1/2, то величина похибки в наступній точці растра з координатами (1,0) може бути обчислена як
e=e+m
де m - кутовий коефіцієнт. У нашому випадку при початковому значенні похибки -1/2
e=-1/2+3/8=-1/8
Тому що е від’ємне, відрізок пройде нижче середини піксела. Отже, піксел на тому ж самому горизонтальному рівні краще апроксимує положення відрізка, тому в не збільшується. Аналогічно обчислюємо похибку
e=-1/8+3/8=1/4
у наступній точці растра (2,0). Тепер е додатне, значить відрізок пройде вище середньої точки. Растровий елемент (2,1) з наступною по величині координатою в краще апроксимує положення відрізка. Отже, у збільшується на 1. Перше ніж розглядати наступний піксел, необхідно відкоректувати похибку відніманням від неї 1. Маємо
e=1/4-1=-3/4
Помітимо, що перетин вертикальної прямої x=2 із заданим відрізком лежить на 1/4 нижче прямої у=1. Якщо ж перенести відрізок 1/2 вниз, ми одержимо саме величину -3/4. Продовження обчислень для наступного піксела дає
e=-3/4+3/8=-3/8
Тому що е від’ємне, то y не збільшується. З усього сказаного випливає, що похибка - це інтервал, що відтинається по осі y розглянутим відрізком у кожному растровому елементі (відносно -1/2).
Приведемо алгоритм Брезенхема для першого октанта, тобто для випадку
0 <= Dy<= Dx.