View Full Version: Thuật toán Bresenham

SPTIN0307's FORUM > Đồ Họa Máy Tính > Thuật toán Bresenham


Title: Thuật toán Bresenham


greenapple - September 17, 2005 08:52 AM (GMT)
Lớp ḿnh có ai giải được bài tập của lớp do thầy phương ra không vậy. Nếu ai giải rồi poss lên cho mọi nguời cùng xem với

newMember - September 17, 2005 10:23 AM (GMT)
Ḿnh không nhầm th́ thuật toán Bresenham có cả vẽ đường tṛn và đường thẳng, ư bạn muốn nói ở đây là đường nào thế!

best-flower - September 18, 2005 03:18 PM (GMT)
Ê các bạn, thuật toán Brusenham là cái ǵ vậy?

ClickMe - September 19, 2005 12:32 PM (GMT)
Thuật toán Bresenham là thuật toán biểu diễn đường thẳng (hoặc đường tṛn) trên máy tính một cách tương đối thông qua các pixel (điểm ảnh). Một đường thẳng trên máy tính thực ra là một dăy các điểm ảnh nằm tương đối thẳng hàng với nhau và nó đánh lừa mắt thường rằng nó thẳng hàng.

thichdua - September 19, 2005 01:38 PM (GMT)
Đây là bài cài dặt thuật toán bresenham vẽ đường tṛn bằng C++, c̣n đường thẳng chắc dễ hơn.

CODE

#include <graphics.h>
#include <conio.h>

void Bresenham_Circle(int xc, int yc, int Radius, int color)
{
 int x, y, d;

 x = 0;
 y = Radius;
 d = 3 - 2 * Radius;

 while (x <= y)
 {
 putpixel(xc + x, yc + y, color);
 putpixel(xc - x, yc + y, color);
 putpixel(xc + x, yc - y, color);
 putpixel(xc - x, yc - y, color);
 putpixel(xc + y, yc + x, color);
 putpixel(xc - y, yc + x, color);
 putpixel(xc + y, yc - x, color);
 putpixel(xc - y, yc - x, color);
 if (d < 0)
 d += 4 * x + 6;
 else
 {
 d += 4 * (x-y) + 10;
 y--;
 }
 x++;
 }
}

void main()
{
 int gr_drive = DETECT, gr_mode;

 initgraph(&gr_drive, &gr_mode, "");

 Bresenham_Circle(getmaxx() / 2, getmaxy() / 2, 70, 4);
 Bresenham_Circle(getmaxx() / 2, getmaxy() / 2, 150, 5);
 Bresenham_Circle(getmaxx() / 2, getmaxy() / 2, 200, 6);
 getch();
 closegraph();
}


:blink:

newMember - September 19, 2005 01:40 PM (GMT)
Không có bác nào post bài giải à! Hay là chưa nghĩ ra. Bác nào biết rồi th́ post lên cho anh em biết với chứ!

vanminhnhat - September 19, 2005 02:52 PM (GMT)
NewMember khong thay bai giai o tren roi a!

Xin loi vi ngoi quan net khong co trinh go tieng Viet!
<_<

thichdua - September 20, 2005 11:13 AM (GMT)
thichdua t́m được bài toán vẽ đường thẳng bằng Bresenham đưa lên cho mọi người xem nha:

CODE

#include <graphics.h>
#include <conio.h>
#include <math.h>
#include <stdio.h>
/* Giả sử rằng x2>x1 (nếu không trong bài toán ta phải kiểm tra để t́m giá trị bé hơn để vẽ điểm đầu tiên */
void LineBres (int x1, int y1, int x2, int y2, int color)

{

int Dx, Dy, p, Const1, Const2;

int x, y;

Dx = x2 - x1;

Dy = y2 - y1;

p = 2*Dy - Dx; // Dy <<1 - Dx

Const1 = 2*Dy; // Dy <<1

Const2 = 2*(Dy-Dx); // (Dy-Dx) <<1

x = x1;

y = y1;

putpixel(x, y, Color);

for(i=x1; i<x2; i++)

{

if (p<0)

p += Const1;

else

{

p += Const2;

y++;

}

x++;

putpixel(x, y, Color);

}

}

void main()
{
int gr_driver = DETECT, gr_mode;
initgraph(&gr_driver, &gr_mode, "c://tc//bgi//");
LineBres(0,0,50,51,4);
getch();
closegraph();
}


:P

TivagVCH - October 1, 2005 11:47 AM (GMT)
Thuật toán vẽ đường thẳng Bresenham ở trên mới chỉ xét trường hợp hệ số góc m của đường thẳng nằm từ 0 đến 1 thôi (tức là đường thẳng chỉ nằm ở góc phần tám thứ nhất), c̣n các trường hợp khác th́ sao?

TivagVCH có hướng giải quyết như thế này, mọi người thử xem xem có được không?

Có tất cả 8 trường hợp của đường thẳng (chia hệ tọa độ ra làm 8 phần bằng nhau), nhưng khi đường thẳng nằm ở góc phần tám thứ nhất hoặc góc phần tám thứ năm th́ giống nhau (chỉ khác điểm đầu - điểm cuối th́ có thể đảo ngược lại được) --> V́ thế chỉ c̣n lại 4 trường hợp.

. .
. (2) .
. .
. .
. . (1)
....................
. .
. . (8)
. .
. .
. (7) .
. .
(Thông cảm vẽ hơi xấu, chịu khó vậy!)
Như vậy là chỉ cần xét 4 trường hợp ở các góc phần tám thứ 1,2,7 và 8.

Đến đây, nếu với mỗi trường hợp ta lại làm một hàm để vẽ th́ thật là mất công, bởi v́ ta có thể áp dụng thuật toán Bresenham ở trên do thichdua gửi để vẽ các trường hợp c̣n lại.

Ư tưởng thuật toán này như sau:
Ta để ư thấy 4 phần c̣n lại mỗi phần lệch nhau 45 độ, như vậy ta hoàn toàn có thể xây dựng được công thức chuyển tọa độ từ hệ tọa độ Oxy sang các hệ tọa độ khác, mà cụ thể ở đây là các hệ tọa độ có trục Ox trùng với các đường y=x, y=-x, y=0, x=0.
Như vậy, khi ta thực hiện chọn một điểm tiếp theo để vẽ th́ vẫn coi như điểm đó nằm trên hệ Oxy chuẩn, sau đó khi vẽ thật sự th́ ta sẽ chuyển tọa độ của nó sang hệ tọa độ phù hợp để đường thẳng mà ta cần vẽ luôn có hệ số góc với hệ tọa độ này là m mà 0<=m<=1.


thichdua - October 1, 2005 12:24 PM (GMT)
Ḿnh không hiểu ư Tivag nơi, để tối về Test thử xem sao ! Lần trước Test không chú ư lắm nhưng mà ḿnh vẽ được đường thẳng từ vị trí khoảng 10h trên đồng hồ đến vị trí 6h trên đồng hồ vẫn vô tư mà (cũng không nhớ góc phần tư thứ nhất là ở đâu nữa! Chắc ḿnh lộn.)

tu bich hong - October 3, 2005 02:11 AM (GMT)
e tui hoi cai nha
thay Phuong bao la viet bang PASCAL thoi chu khong viet bang C++ mo.
neu co giup moi nguoi thi giai bang pascal di nha
cam on nhieeu

tu bich hong - October 3, 2005 02:15 AM (GMT)
Nay cac ban oi,phai thua nhan la cac ban viet tot thuat toan song sao tui ve chay may o nha la no cu bao loi tum lum len ,khong biet may tui co loi hay thuat toan cua cac ban co loi,.
tui co tim nhung ma khong thay loi nam o dau ca,the moi kho chu
helf helf helf helf
cam on cac ban ha
:D

thichdua - October 3, 2005 12:00 PM (GMT)
Nếu viết bằng PC th́ chắc phải nhờ Tivag hoặc vitboy giup rồi!
Mod vitboy , ra tay đi chứ.

C̣n bạn nói t́m thấy nhiều lỗi khi chạy bằng C++ th́ ḿnh chịu, nhưng bạn không nên copy vào mà nên gơ vào(v́ ḿnh copy th́ bị nhiều lỗi lắm!), chắc không có lỗi đâu v́ ḿnh có thử rồi mà!

Nếu có th́ chắc saiở ḍng này initgraph(&gr_driver, &gr_mode, "c://tc//bgi//"); (bạn tra help của C++ với từ khóa initgraph xem sao nhe!)

newMember - October 3, 2005 01:32 PM (GMT)
Biểu diễn thuật toán bằng C++ hay Pascal đều như nhau cả thôi, quan trọng là bạn phải biết các hàm, thủ tục khởi tạo & kết thúc chế độ đồ hoạ.

Trong Pascal, thường người ta sử dụng unit GRAPH. C̣n các hàm trong đó th́ các bạn vào help của Pascal th́ thoải mái mà t́m.

TivagVCH - October 4, 2005 12:52 AM (GMT)
Đây là thuật toán Bresenham vẽ đường thẳng viết bằng Pascal (đă chạy thử), nhưng cũng mới chỉ đúng trong trường hợp hệ số góc 0<=m<=1 thôi. Mọi người đọc rồi cải tiến thêm.

CODE
uses crt,graph;
var GraphicDriver,GraphicMode:integer;
   goc:integer;
   x,y:integer;
Procedure Line_Bre(x1,y1,x2,y2:integer);
Var
  i:integer;
  x,y,p:Integer;
  const1,const2:integer;
  color:byte;
Begin
    p:=2*(y2-y1)-(x2-x1);
    x:=x1;
    y:=y1;
    color:=10;
    PutPixel(x,y,color);
    For i:=x1 to x2 do
        Begin
             If (p<0) then
                p:=p+2*(y2-y1)
             Else
                 Begin
                      p:=p+2*(y2-y1)-2*(x2-x1);
                      y:=y+1;
                 End;
             x:=x+1;
             PutPixel(x,y,color);
        End;
End;
BEGIN
    clrscr;
    GraphicDriver:=VGA;
    GraphicMode:=VGAHi;
    InitGraph(GraphicDriver,GraphicMode,'C:\bp\bgi');
    If(graphresult<>grok)then Halt(1);
    Line_Bre(10,35,550,600);
    Readln;
    CloseGraph;
END.

ClickMe - October 21, 2005 11:22 AM (GMT)
Nếu đă giải được một trường hợp này rồi th́ 3 trường hợp c̣n lại tương tự vậy thôi. Sau đó dùng câu lệnh switch để chia nhỏ ra mà làm.

tu bich hong - December 14, 2005 01:16 AM (GMT)
Này các ban ơi! thuật toan BRÉHAM có ở các bạn lớp A rồi ḱa. Đủ các trườg hợp luôn.Ḿnh thấy tất cẩ có 8 trường hợp đúng không?
0<m<1
-1<m<0
m<-1
m>1
x1=x2
y1=y2
m=1
m=-1
chúc các bạn học tốt môn đồ họa nghe! :D

TivagVCH - December 16, 2005 11:59 AM (GMT)
Đâu phải, chỉ có 4 trường hợp thôi chứ! Các trường hợp c̣n lại chỉ là trường hợp đặc biệt của 4 trường hợp này thôi!

trantutbqn - January 10, 2006 12:36 PM (GMT)
Thuật toán vẽ đường thẳmg tổng quát

CODE
BresenhamLine(int x1, int y1, int x2, int y2, int color) {
int Dx = x2 – x1, Dy = y2 – y1;
int x = x1, y = y1;

int dx = (Dx < 0) ? -1 : 1; Dx = abs(Dx);
int dy = (Dy < 0) ? -1 : 1; Dy = abs(Dy);

putpixel(x, y, color);
if (Dx > Dy)
{
 int p = 2 * Dy – Dx;
 int const1 = 2 * Dy, const2 = 2 * (Dy-Dx);

 while (x != x2) {
  if (p < 0) {
   p += const1;
  } else {
   p += const2;
   y += dy;
  }
  x += dx;
  putpixel(x, y, color);
 }
} else {
 int p=2*Dx-Dy;
 int const1 = 2 * Dx, const2 = 2 * (Dx-Dy);
 while (y!=y2)
  {
  if (p < 0) {
   p += const1;
  } else {
   p += const2;
   x += dx;
  }
  y += dy;
  putpixel(x, y, color);
}
}


Bài giảng ở đây này:

@today - January 11, 2006 11:02 AM (GMT)
Nhung ma khi di thi thay khong bat lam het cac truong hop nay dau, chac chi la mot truong hop dac biet nao do thoi.




* Hosted for free by zIFBoards