Вывод на экран произвольной точки
Растровое представление экрана представляет собой сетку размером SizeX пикселов по горизонтали и SizeY пикселов по вертикали. Мы будем рассматривать дисплей, каждая точка которого состоит из трех цветов (Red, Green, Blue), где каждая компонента цвета может иметь 256 градаций яркости (от 0 до 255) и занимает 1 байт. Т.о. одна точка занимает 3 байта. Объем памяти, занимаемый изображением равен X*Y*3.
При разрешении 640*480 мы имеем изменение по горизонтали от 0 до 639 и по вертикали от 0 до 479. Чтобы нарисовать произвольную точку, необходимо использовать следующую формулу:
p = (SizeX*Y + X)*3,
где X, Y – координаты рисуемой точки;
p – смещение точки в памяти.
Растровое представление отрезка
Рассмотрим задачу построения растрового изображения отрезка, соединяющего точки (x1, y1) и (x2, y2). Для простоты будем считать, что 0 . Тогда отрезок описывается следующим уравнением:
y = y1 + ((y2 – y1)/(x2 – x1))*(x – x1), x [x1, x2]
или
y = k*x + b.
Простейший алгоритм растрового представления отрезка имеет вид для случая dx >= dy:
procedure Line(x1, y1, x2, y2, color: Integer);
var
k, b: Single;
i: Integer;
begin
k = Single((y2 – y1)/(x2 – x1));
b = y1 – k*x1;
for i := x1 to x2 do PutPixel(i, round(k*x + b), color);
end;
Используя рекуррентное соотношение для вычисления , можно упростить функцию, однако это не устраняет основного недостатка алгоритма – использования вещественных вычислений для работы на целочисленной решетке.
Растровое представление отрезка. Алгоритм Брезенхейма
В 1965 году Брезенхеймом был предложен простой целочисленный алгоритм для растрового построения отрезка, первоначально предназначенный для использования в графопостроителях.
П
ри
построении растрового изображения
отрезка всегда выбирается ближайший
по вертикали пиксел. При этом из двух
точек A(x1, y1) и B(x2,
y2) (рис. 1) выбирается та, которая
ближе к исходной прямой (в данном случае
выбирается точка A, т.к. a
< b). Для этого вводится
число d, равное (x2
– x1)*(b - a).
В случае d > 0 значение y от предыдущей точки увеличивается на 1, а d – на 2*(y - x). В противном случае значение y не изменяется, а значение d заменяется на 2*y.
Пример реализации алгоритма, при условии 0 <= y2 – y1 <= x2- x1:
procedure Line(x1, y1, x2, y2, color: Integer);
var dx, dy, d, d1, d2, x: Integer;
begin
// Инициализация начальных переменных
dx := x2 – x1;
dy := y2 – y1;
d := dy*2 –dx;
d1 := dy shl 1;
d2 := (dy - dx) shl 1;
// Основной цикл
for x := x1 to x2 do
begin
PutPixel(x, y, color);
if d > 0 then
begin inc(d, d2); inc(y); end
else inc(d, d1);
end;
end;
Общий случай произвольного отрезка легко сводится к рассмотренному выше, следует только иметь в виду, что при выполнении неравенства |y| >= |x| необходимо поменять местами x и y.
Из предложенного примера несложно написать функцию для построения 4-связной развертки отрезка.
procedure Line(x1, y1, x2, y2, color: Integer);
var dx, dy, d, d1, d2, i: Integer;
begin
// Инициализация начальных переменных
dx := x2 – x1;
dy := y2 – y1;
d := 0;
d1 := dy shl 1;
d2 := – (dx shl 1);
PutPixel(x1, y1, color); // Вывод первой точки
x := x1; y = y1;
// Основной цикл
for i := 1 to dx + dy do
begin
if d > 0 then
begin inc(d, d2); inc(y); end
else begin inc(d, d1); inc(x); end;
PutPixel(x, y, color);
end;
end;