[Править] Рисование линий
Реализация на C++:
void drawLine(int x1, int y1, int x2, int y2)
{
int deltaX = abs(x2 - x1);
int deltaY = abs(y2 - y1);
int signX = x1 < x2 ? 1 : -1;
int signY = y1 < y2 ? 1 : -1;
int error = deltaX - deltaY;
for (;;)
{
setPixel(x1, y1);
if(x1 == x2 && y1 == y2)
break;
int error2 = error * 2;
if(error2 > -deltaY)
{
error -= deltaY;
x1 += signX;
}
if(error2 < deltaX)
{
error += deltaX;
y1 += signY;
}
}
}
Алгоритм Брезенхема для растеризации окружности.
Рисование окружностей
Также существует алгоритм Брезенхэма для рисования окружностей. По методу построения он похож на рисование линии. В этом алгоритме строится дуга окружности для первого квадранта, а координаты точек окружности для остальных квадрантов получаются симметрично. На каждом шаге алгоритма рассматриваются три пикселя, и из них выбирается наиболее подходящий путём сравнения расстояний от центра до выбранного пикселя с радиусом окружности.
// R - радиус, X1, Y1 - координаты центра
int x := 0
int y := R
int delta := 2 - 2 * R
int error := 0
while (y >= 0)
drawpixel(X1 + x, Y1 + y)
drawpixel(X1 + x, Y1 - y)
drawpixel(X1 - x, Y1 + y)
drawpixel(X1 - x, Y1 - y)
error = 2 * (delta + y) - 1
if ((delta < 0) && (error <= 0))
delta += 2 * ++x + 1
continue
error = 2 * (delta - x) - 1
if ((delta > 0) && (error > 0))
delta += 1 - 2 * --y
continue
x++
delta += 2 * (x - y)
y--
Для C++
void drawCircle(int x0, int y0, int radius) {
int x = 0;
int y = radius;
int delta = 2 - 2 * radius;
int error = 0;
while(y >= 0) {
setPixel(x0 + x, y0 + y);
setPixel(x0 + x, y0 - y);
setPixel(x0 - x, y0 + y);
setPixel(x0 - x, y0 - y);
error = 2 * (delta + y) - 1;
if(delta < 0 && error <= 0) {
++x;
delta += 2 * x + 1;
continue;
}
error = 2 * (delta - x) - 1;
if(delta > 0 && error > 0) {
--y;
delta += 1 - 2 * y;
continue;
}
++x;
delta += 2 * (x - y);
--y;
}
}
Алгоритм сглаживания Ву.
Алгоритм Ву — это алгоритм разложения отрезка в растр со сглаживанием. Был предложен У Сяолинем (Xiaolin Wu, отсюда устоявшееся в русском языке название алгоритма) в статье, опубликованной журналом Computer Graphics в июле 1991 года. Алгоритм сочетает высококачественное устранение ступенчатости и скорость, близкую к скорости алгоритма Брезенхема без сглаживания.
Алгоритм
Горизонтальные и вертикальные линии не требуют никакого сглаживания, поэтому их рисование выполняется отдельно. Для остальных линий алгоритм Ву проходит их вдоль основной оси, подбирая координаты по неосновной оси аналогично алгоритму Брезенхема. Отличие состоит в том, что в алгоритме Ву на каждом шаге устанавливается не одна, а две точки. Например, если основной осью является Х, то рассматриваются точки с координатами (х, у) и (х, у+1). В зависимости от величины ошибки, которая показывает как далеко ушли пиксели от идеальной линии по неосновной оси, распределяется интенсивность между этими двумя точками. Чем больше удалена точка от идеальной линии, тем меньше ее интенсивность. Значения интенсивности двух пикселей всегда дают в сумме единицу, то есть это интенсивность одного пикселя, в точности попавшего на идеальную линию. Такое распределение придаст линии одинаковую интенсивность на всем ее протяжении, создавая при этом иллюзию, что точки расположены вдоль линии не по две, а по одной.
Результат работы алгоритма
Реализация в псевдокоде (только для линии по x):
function plot(x, y, c) is
// рисует точку с координатами (x, y)
// и яркостью c (где 0 ≤ c ≤ 1)
function ipart(x) is
return целая часть от x
function round(x) is
return ipart(x + 0.5) // округление до ближайшего целого
function fpart(x) is
return дробная часть x
function draw_line(x1,y1,x2,y2) is
if x2 < x1 then
swap(x1, x2)
swap(y1, y2)
end if
dx := x2 - x1
dy := y2 - y1
gradient := dy ÷ dx
// обработать начальную точку
xend := round(x1)
yend := y1 + gradient × (xend - x1)
xgap := 1 - fpart(x1 + 0.5)
xpxl1 := xend // будет использоваться в основном цикле
ypxl1 := ipart(yend)
plot(xpxl1, ypxl1, 1 - fpart(yend) × xgap)
plot(xpxl1, ypxl1 + 1, fpart(yend) × xgap)
intery := yend + gradient // первое y-пересечение для цикла
// обработать конечную точку
xend := round(x2)
yend := y2 + gradient × (xend - x2)
xgap := fpart(x2 + 0.5)
xpxl2 := xend // будет использоваться в основном цикле
ypxl2 := ipart(yend)
plot(xpxl2, ypxl2, 1 - fpart(yend) × xgap)
plot(xpxl2, ypxl2 + 1, fpart(yend) × xgap)
// основной цикл
for x from xpxl1 + 1 to xpxl2 - 1 do
plot(x, ipart(intery), 1 - fpart(intery))
plot(x, ipart(intery) + 1, fpart(intery))
intery := intery + gradient
repeat
end function
Алгоритмы закрашивания.