Растровые алгоритмы. Алгоритм Брезенхейма. Построение одноцветного треугольника. Вывод на экран произвольной точки

Общий случай произвольного отрезка легко сводится к рассмотренному выше, следует только иметь в виду, что при выполнении неравенства |Dy| >= |Dx| необходимо поменять местами x и y.

2.2.2. Отсечение отрезка. Алгоритм Сазерленда-Кохена

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

Ниже рассматривается достаточно простой и эффективный алгоритм отсечения отрезков по границе произвольного прямоугольника. Он заключается в разбиении всей плоскости на 9 областей прямыми, образующими прямоугольник. В каждой из этих областей все точки по отношению к прямоугольнику расположены одинаково. Определив, в какие области попали концы рассматриваемого отрезка, легко понять, где именно необходимо отсечение. Для каждой области сообщается 4-битовый код, где установленный:

бит 0 означает, что точка лежит левее прямоугольника,

бит 1 означает, что точка лежит выше прямоугольника,

бит 2 означает, что точка лежит правее прямоугольника,

бит 3 означает, что точка лежит ниже прямоугольника.

Приведенная ниже программа реализует алгоритм Сазерленда-Кохена отсечения отрезка по прямоугольной области.

procedure Swap(var a, b: Integer);

var c: Integer;

begin

c := a; a := b; b := c;

end;

function OutCode(x, y, x1, y1, x2, y2: Integer): Integer;

var code: Integer;

begin

code := 0;

if x < x1 then code := code or 1;

if y < y1 then code := code or 2;

if x > x2 then code := code or 4;

if y > y2 then code := code or 8;

end;

procedure ClipLine(x1, y1, x2, y2, dx1, dy1, dx2, dy2: Integer);

var

code1, code2: Integer;

inside: Boolean;

begin

code1 := OutCode(x1, y1, dx1, dy1, dx2, dy2);

code2 := OutCode(x2, y3, dx1, dy1, dx2, dy2);

inside := (code1 or code2) = 0;

while (not inside) do

begin

if  code1 = 0 then

begin Swap(x1, x2); Swap(y1, y2); Swap(code1, code2); end;

if (code1 and 1) <> 0 then   // clip left

begin inc(y1, LongInt((y2 – y1)*(dx1 – x1)) div (x2 – x1)); x1 := dx1; end;

if (code1 and 2) <> 0 then   // clip above

begin inc(x1, LongInt((x2 – x1)*(dy1 – y1)) div (y2 – y1)); y1 := dy1; end;

if (code1 and 4) <> 0 then   // clip left

begin inc(y1, LongInt((y2 – y1)*(dx2 – x1)) div (x2 – x1)); x1 := dx2; end;

if (code1 and 8) <> 0 then   // clip above

begin inc(x1, LongInt((x2 – x1)*(dy2 – y1)) div (y2 – y1)); y1 := dy2; end;

code1 := OutCode(x1, y1, dx1, dy1, dx2, dy2);

code2 := OutCode(x2, y3, dx1, dy1, dx2, dy2);

inside := (code1 or code2) = 0;

end;

line(x1, y1, x2, y2);

end;

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

2.2.3. Алгоритм построения однородного треугольника

Изображение треугольника на экране представляет собой набор горизонтальных отрезков, и т.к. треугольник - фигура выпуклая, то каждой строке экрана соответствует один отрезок. Поэтому достаточно пройтись по всем строкам экрана с которыми пересекается треугольник (то есть от минимального до максимального значения y для вершин треугольника), и нарисовать соответствующие горизонтальные отрезки.

Перед началом рисования треугольника необходимо отсортировать его вершины так, чтобы вершина A была верхней, C -  нижней, тогда min_y = A.y, max_y = C.y, и необходимо пройтись по всем линиям от min_y до max_y. Рассмотрим какую-то линию sy, A.y <= sy <= C.y. Если sy < B.y, то она пересекает стороны AB и AC; если sy >= B.y - то стороны BC и AC. Имея координаты всех вершин, можно написать уравнения сторон и найти пересечение нужной стороны с прямой y = sy. Получаем два конца отрезка. Т. к. не известно, какой из них левый, а какой правый, сравниваются их координаты по x, и при необходимости меняются значения. Этот отрезок рисуется и процедура повторяется для каждой строки.

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

Частные случаи:

·  Если A = B = C, то треугольник представляет собой одну точку.

·  Если A.y = C.y, то треугольник пустой и рисуется только одна горизонтальная линия.

·  Если A.y = B.y или B.y = C.y, то прорисовка включает только один этап.

3. Порядок выполнения работы

1.  Написать процедуру вывода точки под разрешение 640*480*24бит.

2.  Использовав предыдущую процедуру, написать на основе алгоритма Брезенхейма процедуру вывода произвольного отрезка.

3.  Реализовать алгоритм Сазерленда-Кохена и использовать его при рисовании отрезка.

4.  Написать процедуру вывода одноцветного треугольника, не используя