Перейти к содержанию

Реализации алгоритмов/Алгоритм Брезенхэма

Материал из Викиучебника — открытых книг для открытого мира

Алгоритм Брезенхе́ма (англ. Bresenham's line algorithm) — это алгоритм, определяющий, какие точки n-мерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками.

Существует обобщение алгоритма Брезенхэма для построения окружностей.

Рисование линий

[править]

Реализация на Verilog

[править]
`define IDLE 	0
`define LINEY	1
`define LINEX	2
`define	ERRORX 	3
`define ERRORY	4

module Bresenham ( clk, rst, DRAW, X0, Y0, X1, Y1, X, Y, WE, DONE );

 input		clk;
 input		rst;
 input		DRAW;
 input	[31:0]	X0;
 input	[31:0]	Y0;
 input	[31:0]	X1;
 input	[31:0]	Y1;
 output	[31:0]	X;
 output	[31:0]	Y;
 output		WE;
 output         DONE;
	
 reg	[2:0]	state;
 reg		we;
	
 integer	x1, x2, y1, y2;
 integer	error;	
 integer	dX;
 integer	dY;
 wire signed [31:0] signY = y2 > y1 ? 1 : -1;		
	
 always	@(posedge clk or posedge rst)
   if (rst) begin
     x1 <= 0;
     x2 <= 0;
     y1 <= 0;
     y2 <= 0;
     we <= 0;
     error <= 0;
     state <= 0;
   end else
     case (state)
       `IDLE : 
	begin
	  we <= 0;
	  if (DRAW) begin
	    x1 <= X0;
	    y1 <= Y0;
	    x2 <= X1;
	    y2 <= Y1;
            dX = X1 > X0 ? X1 - X0 : X0 - X1;
            dY = Y1 > Y0 ? Y1 - Y0 : Y0 - Y1;
            error <= dX - dY;
            state <= {1'b0, !(dX == 0), !(dY == 0)};
	  end
	end			
	`ERRORX : 
	begin
	  we <= 0;				
	  if (error <<< 1  > -dY) begin error <= error - dY; x1 <= x1 + 1'b1; end				
	  state <= `ERRORY;
	end			
	`ERRORY : 
	begin
	  we <= 1;
	  if (error <<< 1 < dX) begin error <= error + dX; y1 <= y1 + signY; end
          state <= {1'b0, !(x1 == x2), !(y1 == y2)};
	end			
	`LINEX : 
	begin
	  we <= 1;
	  x1 <= x1 + 1'b1;
	  if (x1 == (x2 - 1)) state <= `IDLE;
	end
	`LINEY : 
	begin
	  we <= 1;
	  y1 <= y1 + signY;
	  if (y1 == (y2 - signY)) state <= `IDLE;
	end
     endcase
			
 assign X    = x1;
 assign Y    = y1;
 assign WE   = we;
 assign DONE = state == `IDLE;
	
endmodule

Реализация на C++

[править]
void drawLine(int x1, int y1, int x2, int y2) {
    const int deltaX = abs(x2 - x1);
    const int deltaY = abs(y2 - y1);
    const int signX = x1 < x2 ? 1 : -1;
    const int signY = y1 < y2 ? 1 : -1;
    int error = deltaX - deltaY;
    setPixel(x2, y2);
    while(x1 != x2 || y1 != y2) 
   {
        setPixel(x1, y1);
        int error2 = error * 2;
        if(error2 > -deltaY) 
        {
            error -= deltaY;
            x1 -= signX;
        }
        if(error2 < deltaX) 
        {
            error += deltaX;
            y1 -= signY;
        }
    }

}

Реализация на Java

[править]
// Этот код "рисует" все 9 видов отрезков. Наклонные (из начала в конец и из конца в начало каждый), вертикальный и горизонтальный - тоже из начала в конец и из конца в начало, и точку.
private int sign (int x) {
	return (x > 0) ? 1 : (x < 0) ? -1 : 0;
	//возвращает 0, если аргумент (x) равен нулю; -1, если x < 0 и 1, если x > 0.
}

public void drawBresenhamLine (int xstart, int ystart, int xend, int yend, Graphics g)
 /**
  * xstart, ystart - начало;
  * xend, yend - конец; 
  * "g.drawLine (x, y, x, y);" используем в качестве "setPixel (x, y);"
  * Можно писать что-нибудь вроде g.fillRect (x, y, 1, 1);
  */
{
	int x, y, dx, dy, incx, incy, pdx, pdy, es, el, err;

	dx = xend - xstart;//проекция на ось икс
	dy = yend - ystart;//проекция на ось игрек

	incx = sign(dx);
	/*
	 * Определяем, в какую сторону нужно будет сдвигаться. Если dx < 0, т.е. отрезок идёт
	 * справа налево по иксу, то incx будет равен -1.
	 * Это будет использоваться в цикле постороения.
	 */
	incy = sign(dy);
	/*
	 * Аналогично. Если рисуем отрезок снизу вверх -
	 * это будет отрицательный сдвиг для y (иначе - положительный).
	 */

	if (dx < 0) dx = -dx;//далее мы будем сравнивать: "if (dx < dy)"
	if (dy < 0) dy = -dy;//поэтому необходимо сделать dx = |dx|; dy = |dy|
	//эти две строчки можно записать и так: dx = Math.abs(dx); dy = Math.abs(dy);

	if (dx > dy)
	//определяем наклон отрезка:
	{
	 /*
	  * Если dx > dy, то значит отрезок "вытянут" вдоль оси икс, т.е. он скорее длинный, чем высокий.
	  * Значит в цикле нужно будет идти по икс (строчка el = dx;), значит "протягивать" прямую по иксу
	  * надо в соответствии с тем, слева направо и справа налево она идёт (pdx = incx;), при этом
	  * по y сдвиг такой отсутствует.
	  */
		pdx = incx;	pdy = 0;
		es = dy;	el = dx;
	}
	else//случай, когда прямая скорее "высокая", чем длинная, т.е. вытянута по оси y
	{
		pdx = 0;	pdy = incy;
		es = dx;	el = dy;//тогда в цикле будем двигаться по y
	}

	x = xstart;
	y = ystart;
	err = el/2;
	g.drawLine (x, y, x, y);//ставим первую точку
	//все последующие точки возможно надо сдвигать, поэтому первую ставим вне цикла

	for (int t = 0; t < el; t++)//идём по всем точкам, начиная со второй и до последней
	{
		err -= es;
		if (err < 0)
		{
			err += el;
			x += incx;//сдвинуть прямую (сместить вверх или вниз, если цикл проходит по иксам)
			y += incy;//или сместить влево-вправо, если цикл проходит по y
		}
		else
		{
			x += pdx;//продолжить тянуть прямую дальше, т.е. сдвинуть влево или вправо, если
			y += pdy;//цикл идёт по иксу; сдвинуть вверх или вниз, если по y
		}

		g.drawLine (x, y, x, y);
	}
}

Реализация на Python3

[править]
""" Имплементация алгоритма на языке Python(перевод с Java)
setPixel(x,y) - функция закрашивает пиксель, с координатами x и y""" 


    def draw_line(self, x1=0, y1=0, x2=0, y2=0):
         
        dx = x2 - x1
        dy = y2 - y1
        
        sign_x = 1 if dx>0 else -1 if dx<0 else 0
        sign_y = 1 if dy>0 else -1 if dy<0 else 0
        
        if dx < 0: dx = -dx
        if dy < 0: dy = -dy
        
        if dx > dy:
            pdx, pdy = sign_x, 0
            es, el = dy, dx
        else:
            pdx, pdy = 0, sign_y
            es, el = dx, dy
        
        x, y = x1, y1
        
        error, t = el/2, 0        
        
        setPixel(x, y)
        
        while t < el:
            error -= es
            if error < 0:
                error += el
                x += sign_x
                y += sign_y
            else:
                x += pdx
                y += pdy
            t += 1
            setPixel(x, y)

Реализация на Object Pascal

[править]
    Procedure Swap(var x,y:Integer);
    var t:Integer;
    begin
      t:=x;x:=y;y:=t;
    end;

    Procedure Line(Canvas: TCanvas; x1,y1,x2,y2:integer);
    var dx,dy,i,sx,sy,check,e,x,y:integer;
    begin
        dx:=abs(x1-x2);
        dy:=abs(y1-y2);
        sx:=Sign(x2-x1);
        sy:=Sign(y2-y1);
        x:=x1;
        y:=y1;
        check:=0;
        if dy>dx then begin
            Swap(dx,dy);
            check:=1;
        end;
        e:= 2*dy - dx;
        for i:=0 to dx do begin
            Canvas.Pixels[x,y]:=clBlack;
            if e>=0 then begin
                if check=1 then inc(x,sx) else inc(y,sy);
                dec(e,2*dx);
            end;
            if check=1 then inc(y,sy) else inc(x,sx);
            inc(e,2*dy);
        end;
    end;

примечание[1]

Реализация на PascalABC

[править]
procedure drawLine(x1, y1, x2, y2: integer);
var
  currentX, currentY: integer;
  errorX, errorY: integer;
  d, dx, dy, incX, incY: integer;
begin
  dx := x2 - x1;
  dy := y2 - y1;
  errorX := 0;
  errorY := 0;

  if(dx > 0) then incX := 1
    else if(dx = 0) then incX := 0
      else incX := -1;

  if(dy > 0) then incY := 1
    else if(dy = 0) then incY := 0
      else incY := -1;

  dx := abs(dx);
  dy := abs(dy);

  if(dy > dx) then d := dy
    else d := dx;

  currentX := x1;
  currentY := y1;
  SetPixel(currentX, currentY, 0);
  while((currentX <> x2) OR (currentY <> y2)) do
  begin
    errorX := errorX + dx;
    errorY := errorY + dy;
    if(errorX >= d) then
    begin
         errorX := errorX - d;
         currentX := currentX + incX;
    end;
    if(errorY >= d) then
    begin
         errorY := errorY - d;
         currentY := currentY + incY;
    end;
    SetPixel(currentX, currentY, 0);
  end;
end;

Рисование окружностей

[править]

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

   // R - радиус, X1, Y1 - координаты центра
   int x := 0
   int y := R
   int delta := 1 - 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 = 1 - 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;
		}
		if(delta > 0 && error > 0) {
			--y;
			delta += 1 - 2 * y;
			continue;
		}
		++x;
		delta += 2 * (x - y);
		--y;
	}
}

Для Delphi 7

[править]
    Edit1: TEdit;
    Edit2: TEdit;
    Button1: TButton;
    Edit3: TEdit;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    { Объявляем процедуру "DrawCircle", реализующую
      алгоритм Брезенхема для рисования окружности }
    procedure DrawCircle(x1, y1, R : Integer); 
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.DrawCircle(x1, y1, R : Integer);
var x,y,error,delta : integer;
begin
  InvalidateRect(0, nil, true); //Очистка Canvas, необходимая для затирания созданных кругов
  x := 0;
  y := R;
  delta := (1 - 2 * R);
  error := 0;
  while y >= 0 do
  begin
    Canvas.Pixels[X1 + x,Y1 + y] := clBlack;
    Canvas.Pixels[X1 + x,Y1 - y] := clBlack;
    Canvas.Pixels[X1 - x,Y1 + y] := clBlack;
    Canvas.Pixels[X1 - x,Y1 - y] := clBlack;
    error := 2 * (delta + y) - 1;
    if ((delta < 0) and (error <= 0)) then
    begin
      inc(x);
      delta := delta + (2 * x + 1);
      continue;
    end;
    error := 2 * (delta - x) - 1;
    if ((delta > 0) and (error > 0)) then
    begin
      dec(y);
      delta := delta + (1 - 2 * y);
      continue;
    end;
    inc(x);
    delta := delta + (2 * (x - y));
    dec(y);
  end;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  { Здесь получаем необходимые данные из Edit-ов, содержащих информацию 
   для построения окружности по алгоритму Брезенхема, а именно координаты 
   центра окружности и радиус, реализуем их в процедуру DrawCircle }
  DrawCircle(StrToInt(Edit1.Text),StrToInt(Edit2.Text), StrToInt(Edit3.Text));
end;

Для TurboPascal

[править]
procedure BrezenCircle(x0, y0, r: integer);
 var
 x, y: integer;
 dv, dd, dh: integer;
 procedure sim(x, y: integer); {построить 4 симметричные точки}
  begin
    putpixel(x0+x, y0+y, 0); {верхняя правая четверть}
    putpixel(x0+x, y0-y, 0); {нижняя правая четверть}
    putpixel(x0-x, y0+y, 0); {верхняя левая четверть}
    putpixel(x0-x, y0-y, 0); {нижняя левая четверть}
  end;
begin
  x:=0;
  y:=r;
  while((y>=0)or(x<r)) do {обход идет по верхней правой четверти}
    begin
     sim(x,y);
     dv:=abs(r*r - x*x - (y-1)*(y-1)); {сдвиг на 1 вниз}
     dh:=abs(r*r - (x+1)*(x+1) - y*y); {сдвиг на 1 вправо}
     dd:=abs(r*r - (x+1)*(x+1) - (y-1)*(y-1)); {сдвиг на 1 по диагонали вправо и вниз}
     if(dv<dh) then {если сдвиг вниз ближе к радиусу круга}
      begin
        dec(y);
        if(dd<dv) then inc(x); {если сдвиг по диагонали ближе к радиусу круга}
      end
     else {если сдвиг вправо ближе к радиусу круга}
      begin
        inc(x);
        if(dd<dh) then dec(y); {если сдвиг по диагонали ближе к радиусу круга}
      end;
    end;
end;

Для Python

[править]
def draw_circle(x, y, r):
    disp_x = x
    disp_y = y
    x = 0
    y = r
    delta = (1-2*r)
    error = 0
    while y >= 0:
        setPixel(disp_x + x, disp_y + y)
        setPixel(disp_x + x, disp_y - y)
        setPixel(disp_x - x, disp_y + y)
        setPixel(disp_x - x, disp_y - y)
        
        error = 2 * (delta + y) - 1
        if ((delta < 0) and (error <=0)):
            x+=1
            delta = delta + (2*x+1)
            continue
        error = 2 * (delta - x) - 1
        if ((delta > 0) and (error > 0)):
            y -= 1
            delta = delta + (1 - 2 * y)
            continue
        x += 1
        delta = delta + (2 * (x - y))
        y -= 1


Модифицированный пример из книги Г.Шилдта «Си для профессиональных программистов» [2]

[править]
/* Вспомогательная функция, печатает точки, определяющие окружность */
void plot_circle(int x, int y, int x_center, int  y_center, int color_code)
{
    mempoint(x_center+x,y_center+y,color_code);
    mempoint(x_center+x,y_center-y,color_code);
    mempoint(x_center-x,y_center+y,color_code);
    mempoint(x_center-x,y_center-y,color_code);
}

/* Вычерчивание окружности с использованием алгоритма Мичнера */
void circle(int x_center, int y_center, int radius, int color_code)
{
    int x,y,delta;
    x = 0;
    y = radius;
    delta=3-2*radius;
    while(x<y) {
        plot_circle(x,y,x_center,y_center,color_code);
        plot_circle(y,x,x_center,y_center,color_code);
        if (delta<0)
            delta+=4*x+6;
        else {
            delta+=4*(x-y)+10;
            y--;
        }
        x++;
    }

    if(x==y) plot_circle(x,y,x_center,y_center,color_code);
}

Реализация для Turbo Assembler

[править]
.model 	tiny
.stack	100h
.data
	eror dw ?
	x dw ?
	y dw ?
	x0 dw ?
	y0 dw ?
	delta dw ?
	radius dw ?
.code

Plot proc
	mov Ah, 0Ch		;Функция отрисовки точки
	mov al, 6		;Цвет
	int 10h			;Нарисовать точку
	ret
Plot endp

drawCircle proc
        mov x, 0
	mov ax, radius
        mov y, ax
        mov delta, 2
	mov ax, 2
	mov dx, 0
	imul y
	sub delta, ax
	mov eror, 0
	jmp ccicle
finally: ret
ccicle:
	mov ax, y
	cmp ax, 0
	jl  finally
	mov cx, x0
	add cx, x
	mov dx, y0
	add dx, y
	call Plot
        mov cx, x0
	add cx, x
	mov dx, y0
	sub dx, y
	call Plot
	mov cx, x0
	sub cx, x
	mov dx, y0
	add dx, y
	call Plot
	mov cx, x0
	sub cx, x
	mov dx, y0
	sub dx, y
	call Plot
	mov ax, delta
	mov eror, ax
	mov ax, y
	add eror, ax
	mov ax, eror
	mov dx, 0
	mov bx, 2
	imul bx
	sub ax, 1
	mov eror, ax
	cmp delta, 0
	jg sstep
	je sstep
	cmp eror, 0
	jg  sstep
	inc x
	mov ax, 2
	mov dx, 0
	imul x
	add ax, 1
	add delta, ax
        jmp ccicle
sstep:
	mov ax, delta
	sub ax, x
	mov bx, 2
	mov dx, 0
	imul bx
	sub ax, 1
	mov eror, ax
	cmp delta, 0
	jg tstep
	cmp eror, 0
	jg tstep
	inc x
	mov ax, x
	sub ax, y
	mov bx, 2
	mov dx, 0
	imul bx
	add delta, ax
        dec y
	jmp ccicle
tstep:
	dec y
        mov ax, 2
	mov dx, 0
	imul y
	mov bx, 1
	sub bx, ax
	add delta, bx
	jmp ccicle
drawCircle endp

start:
	mov ax, @data
	mov ds, ax
	mov Ah, 0
	mov Al, 4
	int 10h    ;Включение видеорежима VGA
	mov radius, 20    ;Радиус нашего круга.
	mov x0, 80    ;Номер строки, в котором будет находится центр круга
	mov y0, 80    ;Номер столбца, в котором будет находится центр круга
	call DrawCircle
	mov ah,	1    ;Функция захвата кода клавиши (идентична getch из "с")
	int 21h
	mov ah, 4Ch
	int 21h
end	start



Visual Basic

[править]

[3]

 Private Sub BresLine(InitialX As Long, InitialY As Long, FinalX As Long, FinalY As Long)

    Dim Steep As Boolean
    Dim DeltaX As Long, DeltaY As Long, Delta As Long
    Dim StepX As Long, StepY As Long
    Dim Coord As Long

    Steep = False
    DeltaX = Abs(FinalX - InitialX)
    If (FinalX - InitialX) > 0 Then
        StepX = 1
    Else
        StepX = -1
    End If
    DeltaY = Abs(FinalY - InitialY)
    If (FinalY - InitialY) > 0 Then
        StepY = 1
    Else
        StepY = -1
    End If
    If DeltaY > DeltaX Then
        Steep = True
        Swap InitialX, InitialY
        Swap DeltaX, DeltaY
        Swap StepX, StepY
    End If
    Delta = (DeltaY * 2) - DeltaX
    For Coord = 0 To DeltaX
        If Steep Then
            Me.PSet (InitialY, InitialX)
        Else
            Me.PSet (InitialX, InitialY)
        End If
        While Delta >= 0
            InitialY = InitialY + StepY
            Delta = Delta - (DeltaX * 2)
        Wend
        InitialX = InitialX + StepX
        Delta = Delta + (DeltaY * 2)
    Next Coord
    Me.PSet (FinalX, FinalY)
 End Sub

C++ для 3D-растра

[править]

Алгоритм Брезенхэма для построения трёхмерных точек линии (x1, y1, z1) — (x2, y2, z2).[4]

void Bresenham3D(int x1, int y1, int z1, const int x2, const int y2, const int z2, WorldMap *output, int symbol){
    
    int i, dx, dy, dz, l, m, n, x_inc, y_inc, z_inc, err_1, err_2, dx2, dy2, dz2;
    int point[3];
    
    point[0] = x1;
    point[1] = y1;
    point[2] = z1;
    dx = x2 - x1;
    dy = y2 - y1;
    dz = z2 - z1;
    x_inc = (dx < 0) ? -1 : 1;
    l = abs(dx);
    y_inc = (dy < 0) ? -1 : 1;
    m = abs(dy);
    z_inc = (dz < 0) ? -1 : 1;
    n = abs(dz);
    dx2 = l << 1;
    dy2 = m << 1;
    dz2 = n << 1;
    
    if ((l >= m) && (l >= n)) {
        err_1 = dy2 - l;
        err_2 = dz2 - l;
        for (i = 0; i < l; i++) {
            output->getTileAt(point[0], point[1], point[2])->setSymbol(symbol);
            if (err_1 > 0) {
                point[1] += y_inc;
                err_1 -= dx2;
            }
            if (err_2 > 0) {
                point[2] += z_inc;
                err_2 -= dx2;
            }
            err_1 += dy2;
            err_2 += dz2;
            point[0] += x_inc;
        }
    } else if ((m >= l) && (m >= n)) {
        err_1 = dx2 - m;
        err_2 = dz2 - m;
        for (i = 0; i < m; i++) {
            output->getTileAt(point[0], point[1], point[2])->setSymbol(symbol);
            if (err_1 > 0) {
                point[0] += x_inc;
                err_1 -= dy2;
            }
            if (err_2 > 0) {
                point[2] += z_inc;
                err_2 -= dy2;
            }
            err_1 += dx2;
            err_2 += dz2;
            point[1] += y_inc;
        }
    } else {
        err_1 = dy2 - n;
        err_2 = dx2 - n;
        for (i = 0; i < n; i++) {
            output->getTileAt(point[0], point[1], point[2])->setSymbol(symbol);
            if (err_1 > 0) {
                point[1] += y_inc;
                err_1 -= dz2;
            }
            if (err_2 > 0) {
                point[0] += x_inc;
                err_2 -= dz2;
            }
            err_1 += dy2;
            err_2 += dx2;
            point[2] += z_inc;
        }
    }
    output->getTileAt(point[0], point[1], point[2])->setSymbol(symbol);
}

Примечания

[править]
  1. переменная DX взята не удачно при написании фрагмента на асм’е среда плохо переварит
  2. Шилдт, 1989
  3. Encyclopedia > Bresenham’s line algorithm Visual basic code Bresenham’s line algorithm for Microsoft Visual Basic 6.0. Implementation by Robert Lee <rlee0001@maine.rr.com> July, 2002 Public Domain
  4. C++ Bresenham 3d Line Drawing Algorithm A slightly modified version of the source found at http://www.ict.griffith.edu.au/anthony/info/graphics/bresenham.procs Provided by Anthony Thyssen, though he does not take credit for the original implementation It is highly likely that the original Author was Bob Pendelton, as referenced here ftp://ftp.isc.org/pub/usenet/comp.sources.unix/volume26/line3d line3d was dervied from DigitalLine.c published as "Digital Line Drawing" by Paul Heckbert from "Graphics Gems", Academic Press, 1990 3D modifications by Bob Pendleton. The original source code was in the public domain, the author of the 3D version places his modifications in the public domain as well.