Thư mục

Hỗ trợ kỹ thuật

  • (Hotline:
    - (04) 66 745 632
    - 0982 124 899
    Email: hotro@violet.vn
    )

Thống kê

  • truy cập   (chi tiết)
    trong hôm nay
  • lượt xem
    trong hôm nay
  • thành viên
  • Chào mừng quý vị đến với Thư viện Bài giảng điện tử.

    Quý vị chưa đăng nhập hoặc chưa đăng ký làm thành viên, vì vậy chưa thể tải được các tư liệu của Thư viện về máy tính của mình.
    Nếu đã đăng ký rồi, quý vị có thể đăng nhập ở ngay ô bên phải.

    Đồ họa máy tính

    (Tài liệu chưa được thẩm định)
    Nguồn: ĐH Tin Đồng Nai
    Người gửi: Vĩnh Hảo
    Ngày gửi: 23h:03' 24-03-2009
    Dung lượng: 3.5 MB
    Số lượt tải: 371
    Số lượt thích: 0 người
    Thành Viên Trong Nhóm
    Nguyễn Vĩnh Hảo  0985401816
    Nguyễn Thị Hồng Linh  0987741704
    Lê Thụy Hoài Phương  0955002770
    Phạm Thị Thủy  0929043688
    Nguyễn Lê Cẩm Ngọc  0985024152

    ĐỒ HỌA MÁY TÍNH
    Tìm hiểu và cài đặt các thuật toán vẽ đường cho trường hợp tổng quát

    Input:
    (x1,y1)(x2,y2)
    Output :
    {(x1,y1)(x2,y2)….(xn,yn)}
    là những điểm sáng nằm trên đường thẳng.
    (x1,y1)
    (X2,y2)
    (x1,y1)
    (x2,y2)
    1.Tăng chậm
    2.Tăng nhanh
    3. Giảm chậm ngược
    4. Giảm nhanh ngược
    - Đối tượng mô tả trong hệ tọa độ thực là đối tượng liên tục, còn đối tượng trong hệ tọa độ thiết bị là đối tượng rời rạc. Nên cần thực hiện việc rời rạc hóa và việc nguyên hóa một cách tối uư nhất.
    Từ đó hình thành các thuật toán khác nhau với những uư thế riêng của nó để tối uư về mặt tốc độ và sự chính xác.

    Digital Differential Analyzer
    Để hiển thị trên lưới nguyên được liền nét các điểm có tọa độ (xi+1; yi+1) sẽ phải chọn 1 trong 8 điểm có tọa độ (xi + 1;yi + 1 )
    3
    5
    8
    2
    7
    6
    4
    1
    Thuật toán DDA là một thuật toán tính toán các điểm vẽ dọc theo đường thẳng dựa vào hệ số góc của phương trình đường thẳng y = mx + b
    Trường hợp 1
    Đoạn thẳng tăng chậm với điểm đầu A(x1;y1) ở bên trái và điểm cuối B(xk; yk) ở bên phải và trường hợp đối xứng qua ox
    A
    B
    y = mx + b (0 < |m| <=1 )
    m = (yk – y1)/(xk – x1)
    Bước 1: Xác định điểm đầu tiên
    x1 = x1 ;
    y1 =y1;
    Bước 2: Xác định những điểm tiếp theo
    Lặp
    x1 < xk ;
    xi+1 = xi +1 ;
    y = yi + m ; //đã cải tiến y
    yi+1 = Round(y);
    A
    B
    Lưu đồ thuật toán DDA vẽ đoạn thẳng qua 2 điểm (x1,y1) và (x2,y2)
    trong trương hợp 1
    begin
    xend
    x=x+1;
    y=y+m;
    Putpixel(x,Round(y),c);
    m=Dy/Dx;
    x=x1;
    y=y1;
    Putpixel(x,y,c);
    NO
    yes
    Cài đặt thuật toán DDA trong trường hợp 1
    #include
    #include
    #include
    #define Round(a) int(a+0.5)
    using namespace std;
    Void DDA_line1(int x1,int y1,int x1,int y2, Color c)
    {
    int Dx = x2-x1; Dy= y2-y1;
    float m = (float)Dy/Dx;
    if (abs(m) < 1)
    {
    int x = x1;
    float y = y1;
    putpixel(x, Round(y),c);
    while (x < x2)
    {
    x++;
    y = y+m;
    putpixel(x, Round(y), c);
    }
    }
    }
    Trường hợp 2
    Đoạn thẳng tăng nhanh với điểm đầu A(x1;y1) ở bên trái và điểm cuối B(xk; yk) ở bên phải và trường hợp đối xứng qua oy
    A
    B
    y = mx + b (|m| > 1 )
    m = (yk – y1)/(xk – x1)
    Bước 1: Xác định điểm đầu tiên
    x1 = x1 ;
    y1 =y1;
    Bước 2: Xác định những điểm tiếp theo
    Lặp
    y1 < yk ;
    x = xi +1/m;
    xi+1 = Round(x) ;
    yi+1 = yi +1;
    A
    B
    Lưu đồ thuật toán DDA vẽ đoạn thẳng qua 2 điểm (x1,y1) và (x2,y2)
    trong trường hợp 2
    begin
    yend
    x=x+1/m;
    y=y+1;
    Putpixel(Round(x),y,c);
    m=Dy/Dx;
    x=x1;
    y=y1;
    Putpixel(x,y,c);
    NO
    yes
    Cài đặt thuật toán DDA trong trường hợp 2
    #include
    #include
    #include
    #define Round(a) int(a+0.5)
    using namespace std;
    Void DDA_line1(int x1,int y1,int x1,int y2, Color c)
    {
    int Dx = x2-x1; Dy= y2-y1;
    float m = (float)Dy/Dx;
    if (abs(m) > 1)
    {
    float x = x1;
    int y = y1;
    putpixel(Round(x),y,c);
    while (y < y2)
    {
    x = x+1/m ;
    y ++;
    putpixel(Round(x), y, c);
    }
    }
    }
    Trường hợp 3
    Đoạn thẳng giảm chậm với điểm đầu A(x1;y1) ở bên phải trên và điểm cuối B(xk; yk) ở bên trái dưới và đối xứng của nó qua ox
    y = mx + b (0 < |m| <=1 )
    m = (yk – y1)/(xk – x1)
    Bước 1: Xác định điểm đầu tiên
    x1 = x1 ;
    y1 =y1;
    Bước 2: Xác định những điểm tiếp theo
    Lặp
    x1 > xk ;
    xi+1 = xi -1 ;
    y = yi - m ;
    yi+1 = Round(y);
    B
    A
    B
    A
    Lưu đồ thuật toán DDA vẽ đoạn thẳng qua 2 điểm (x1,y1) và (x2,y2)
    trong trường hợp 3
    begin
    x >x2
    end
    x=x-1;
    y=y-m;
    Putpixel(x,Round(y),c);
    m=Dy/Dx;
    x=x1;
    y=y1;
    Putpixel(x,y,c);
    NO
    yes
    Cài đặt thuật toán DDA trong trường hợp 3
    #include
    #include
    #include
    #define Round(a) int(a+0.5)
    using namespace std;
    Void DDA_line1(int x1,int y1,int x1,int y2, Color c)
    {
    int Dx = x2-x1; Dy= y2-y1;
    float m = (float)Dy/Dx;
    if (abs(m) < 1)
    {
    int x = x1;
    float y = y1;
    putpixel(x, Round(y),c);
    while (x > x2)
    {
    x --;
    y = y - m;
    putpixel(x, Round(y), c);
    }
    }
    }
    Trường hợp 4
    Đoạn thẳng giảm nhanh với điểm đầu A(x1;y1) ở bên phải và điểm cuối B(xk; yk) ở bên trái và đối xứng của nó qua oy
    A
    B
    y = mx + b (m > 1 )
    m = (yk – y1)/(xk – x1)
    Bước 1: Xác định điểm đầu tiên
    x1 = x1 ;
    y1 =y1;
    Bước 2: Xác định những điểm tiếp theo
    Lặp
    y1 > yk ;
    x = xi -1/m;
    xi+1 = Round(x) ;
    yi+1 = yi -1;
    A
    B
    Lưu đồ thuật toán DDA vẽ đoạn thẳng qua 2 điểm (x1,y1) và (x2,y2)
    trong trường hợp 4
    begin
    y > y2
    end
    x=x-1/m;
    y=y-1;
    Putpixel(Round(x),y,c);
    m=Dy/Dx;
    x=x1;
    y=y1;
    Putpixel(x,y,c);
    NO
    yes
    Cài đặt thuật toán DDA trong trường hợp 4
    #include
    #include
    #include
    #define Round(a) int(a+0.5)
    using namespace std;
    Void DDA_line1(int x1,int y1,int x1,int y2, Color c)
    {
    int Dx = x2-x1; Dy= y2-y1;
    float m = (float)Dy/Dx;
    if (abs(m) > 1)
    {
    float x = x1;
    int y = y1;
    putpixel(Round(x),y,c);
    while (y > y2)
    {
    x = x-1/m ;
    y --;
    putpixel(Round(x), y, c);
    }
    }
    }
    Luư đồ thuật toán DDA trong tất cả các trường hợp vẽ đường thẳng
    begin
    Dx = x2 – x1
    Dy = y2 – y1
    abs(Dx) > abs(Dy)
    xinc = Dx / step
    yinc = Dy / step
    x = x1; y = y1
    putpixel (x, y,c )
    end
    NO
    YES
    step = abs(Dx)
    step = abs(Dy)
    k<= step
    YES
    NO
    YES
    x = x + xinc
    y = y + yinc
    Putpixel(Round(x),Round(y),c)
    NO
    Cài đặt thuật toán DDA trong trường hợp Tổng quát
    #include
    #include
    #include
    #define Round(a) int(a+0.5)
    using namespace std;
    Void DDA_line1(int x1,int y1,int x1,int y2, Color color){
    double x,y; int step;
    if(abs(x2-x1)>abs(y2-y1))
    step=abs(x2-x1);
    else
    step=abs(y2-y1);
    x=(double)x1;
    y=(double)y1;
    putpixel(Round(x),Round(y),color);
    double m=(double)(x2-x1)/step;
    double n=(double)(y2-y1)/step;
    for(double i=1;i<=step;i++)
    {
    x+=m;
    y+=n;
    putpixel(Round(x),Round(y),color);
    }
    }
    Ví dụ Demo vẽ đường thẳng từ điểm A(2, 10) đến điểm B(21, 16) (0 < m < 1) điểm A(9, 1) đến điểm B(17,12) (m > 1) bằng thuật toán DDA.
    A (2, 10) đến B (21, 1) m= 6/19 = 0,316 < 1
    i xi yi y
    0 2 10 10
    3 10 10,316
    4 11 10,632
    5 11 10,948
    6 11 11,264
    7 12 11,580
    8 12 11,896
    9 12 12,212
    10 13 12,528
    11 13 12,844
    12 13 13,160
    13 13 13,476
    14 14 13,792
    15 14 14,108
    16 14 14,424
    17 15 14,740
    18 15 15,056
    19 15 15,372
    20 16 15,688
    21 16 16,004
    A ( 9,1 ) đến B (17 , 12 ) m= 11/8 = 1.375> 1
    1/m = 0,73
    i xi yi x
    0 9 1 9
    10 2 9,73
    10 3 10,46
    11 4 11,19
    12 5 11,92
    13 6 12,65
    13 7 13,38
    14 8 14,11
    15 9 14,84
    16 10 15,57
    16 11 16,30
    17 12 17,03
    Tất cả các trường hợp của đoạn thẳng còn lại được vẽ dựa trên thuật toán DDA bằng việc hoán đổi vị trí của điểm đầu và điểm cuối hoặc lấy đối xứng qua các trục tọa độ của 4 trường hợp trên.
    Việc sử dụng công thức để tính giá trị y tại mỗi bước đã giúp cho thuật toán DDA nhanh hơn hẳn so với cách tính y từ phương trình y=mx +b do khử được phép nhân trên số thực. Tuy nhiên, việc cộng dồn giá trị thực m vào y có thể sẽ tích lũy sai số làm cho hàm làm tròn có kết quả sai dẫn tới việc xác định vị trí của điểm vẽ ra bị chệch hướng so với đường thẳng thực. Điều này chỉ xảy ra khi vẽ đoạn thẳng khá dài.
    Tuy đã khử được phép nhân số thực nhưng thuật toán DDA vẫn còn bị hạn chế về mặt tốc độ do vẫn còn phép toán cộng số thực và làm tròn. Có thể khắc phục thao tác cộng số thực m và làm tròn trong thuật toán bằng cách nhận xét m=Dy/Dx với Dy, Dx là các số nguyên.
    - Thuật toán Bresenham đưa ra cách chọn yi+1 là yi hay yi+1 theo một hướng khác sao cho có thể tối ưu hóa về mặt tốc độ so với thuật toán DDA. Vấn đề mấu chốt ở đây là làm thế nào để hạn chế tối đa các phép toán trên số thực trong thuật toán.
    - Ý tưởng chính của thuật toán Bresenham là việc so sánh khỏang cách giữa tọa độ y thực tại vị trí xi+1 với các tọa độ y nguyên trên và dưới nó.
    *** Phương pháp của thuật toán Bresenham
    Gọi (xi+1,y) là điểm thuộc đoạn thẳng thực.
    Ta có: y = m( xi+1) + b. (0 < m <1)
    Xét các hiệu khoảng cách của tung độ thực y so với các tung độ nguyên yi và yi+1 để chọn một điểm là S(xi +1, yi) hay P( xi + 1,yi + 1) gần với điểm thực nhất.
    Đặt d1 = y - yi
    d2 = ( yi+ 1) - y
    - Nếu d1- d2 < 0: Chọn điểm S, tức là yi+1=yi.
    - Nếu d1- d2 ≥ 0: Chọn điểm P, tức là yi+1 =yi + 1.
    Xây dựng pi
    Xét pi = Δx (d1 - d2) với Δx= x2- x1; Δy= y2 –y1;
    Ta có : d1 - d2 = 2 yi+1 - 2yi - 1 = 2m(xi+1) + 2b - 2yi - 1
    => pi = Δx (d1 - d2) = Δx[2m(xi+1) + 2b - 2yi - 1] = Δx[2 Δy/Δx (xi+1) + 2b - 2yi - 1]
    = 2Δy(xi+1) - 2Δx.yi + Δx(2b - 1) = 2Δy.xi - 2Δx.yi+ 2Δy + Δx(2b - 1)
    Vậy C = 2Δy + Δx(2b - 1) = Const
    => pi= 2Δy.xi - 2Δx.yi+ C
    Nhận xét rằng nếu tại bước thứ i ta xác định được dấu của Pi thì xem như ta xác định
    được điểm cần chọn ở bước (i+1). Ta có :
    pi +1 - pi= (2Δy.xi+1 - 2Δx.yi+1+ C) - (2Δy.xi - 2Δx.yi+ C )
    => Pi +1 = pi + 2Δy - 2Δx ( yi+1 - .yi)
    - Nếu pi< 0 : chọn điểm S, tức là yi +1= yi và pi +1 = pi + 2Δy.
    - Nếu pi≥ 0 : chọn điểm P, tức là yi +1= yi +1 và pi +1 = pi + 2Δy - 2Δx
    - Giá trị p0được tính từ điểm vẽ đầu tiên (x0,y0) theo công thức :
    P0= 2Δy.x0 - 2Δx.y0+ C
    Do (x0,y0) là điểm nguyên thuộc về đoạn thẳng nên ta có : y0 = m .x0+ b = Δy/Δx.x0 + b
    Thế vào phương trình trên ta được :
    p0= 2Δy - Δx
    Trường hợp 1
    |Dy|<=|Dx|
    A
    B
    A
    B
    B
    A
    B
    A
    Các dạng đường thẳng thỏa |yB - yA| <= |xB – xA|
    Giải thuật trong trường hợp 1:
    |Dy|<=|Dx|;
    Bước 1: Xác định điểm đầu
    int Dx = x2 – x1, Dy = y2 – y1;
    int p = 2 * Dy – Dx;
    int const1 = 2 * Dy, const2 = 2 * (Dy-Dx);
    int x = x1, y = y1;
    putpixel(x, y, color);
    int dx =(Dx>0)? 1:-1;
    int dy=(Dy>0)? 1:-1;
    Bước 2: Xác định những điểm tiếp theo
    Lặp
    x!=x2 ;
    Nếu p<0:
    p+=const1;
    Nếu p>=0:
    p+=const2;
    y+=dy;
    x+=dx;
    Putpixel(x,y,color);

    Luư đồ thuật toán Bresenham trường hợp 1: |Dy|<=|Dx|
    begin
    p = 2Dy - Dx;
    const1=2Dy; const2=2(Dy-Dx);
    x = x1; y = y1;
    putpixel(x,y,color);
    dx = (Dx >0)? 1:-1;
    dy = (Dy > 0)?1:-1;
    x != x2
    p+=const1;
    end
    NO
    YES
    p < 0
    p+=const2;
    y + = dy;
    x += dx;
    Putpixel(x, y,color);
    YES
    NO
    Cài đặt thuật tóan Bresenham trong trường hợp 1
    #include
    #include
    #include
    using namespace std;
    Void Bresenham_line (int x1,int y1, int x2, int y2, Color color)
    {
    int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1;
    int p = 2 * Dy – Dx ; int const1 = 2 * Dy , const2 = 2 * (Dy-Dx);
    putpixel(x, y, color) ;
    int dx =(Dx>0)? 1:-1 ,dy=(Dy>0)? 1:-1;
    if(abs(Dy) <= abs(Dx)) {
    while(x != x2)
    {
    if ( p < 0) p+=const1;
    else {
    p+=const2;
    y += dy;
    }
    x += dx;
    putpixel(x,y,color);
    }
    }
    }
    A
    B
    A
    B
    B
    A
    A
    B
    Trường hợp 2
    |Dy|<=|Dx|
    Các dạng đường thẳng thỏa |Dy| > |Dx|
    Giải thuật trong trường hợp 2
    |Dy|>|Dx|;
    Bước 1: Xác định điểm đầu
    int Dx = x2 – x1, Dy = y2 – y1;
    int x = x1, y = y1;
    int p = 2 * Dx – Dy;
    int const1 = 2 * Dx, const2 = 2 * (Dx-Dy);
    putpixel(x, y, color);
    int dx =(Dx>0)? 1:-1;
    int dy=(Dy>0)? 1:-1;
    Bước 2: Xác định những điểm tiếp theo
    Lặp
    y!=y2 ;
    Nếu p<0:
    p+=const1;
    Nếu p>=0:
    p+=const2;
    x+=dx;
    y+=dy;
    Putpixel(x,y,color);

    Luư đồ thuật toán Bresenham trong trường hợp 2: |Dy|>|Dx|
    begin
    p = 2Dx - Dy;
    const1=2Dx; const2=2(Dx-Dy);
    x = x1; y = y1;
    putpixel(x,y,color);
    dx = (Dx >0)? 1:-1;
    dy = (Dy > 0)?1:-1;
    y != y2
    p+=const1;
    end
    NO
    YES
    p < 0
    p+=const2;
    x+ = dx;
    y+= dy;
    Putpixel(x, y,color);
    YES
    NO
    Cài đặt thuật toán Bresenham trong trường hợp 2
    #include
    #include
    #include
    using namespace std;
    Void Bresenham_line (int x1,int y1, int x2, int y2, Color color)
    {
    int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1;
    int p = 2 * Dx – Dy ; int const1 = 2 * Dx , const2 = 2 * (Dx-Dy);
    putpixel(x, y, color) ;
    int dx =(Dx>0)? 1:-1 ,dy=(Dy>0)? 1:-1;
    if(abs(Dy) > abs(Dx)) {
    while(y != y2)
    {
    if ( p < 0) p+=const1;
    else {
    p+=const2;
    x += dx;
    }
    y += dy;
    putpixel(x,y,color);
    }
    }
    }
    Ví dụ Demo vẽ đường thẳng bằng thuật toán Bresenham qua hai điểm A(5,8) và B(20,13)
    Ta có Dy=5, Dx=15; p=2Dy-Dx=-5
    const1=2Dy=10, const2=2(Dy-Dx)=-20
    Thuật toán Bresenham chỉ làm việc trên số nguyên và các thao tác trên số nguyên chỉ là phép cộng và phép dịch bit (phép nhân 2) điều này là một cải tiến làm tăng tốc độ đáng kể so với thuật toán DDA.
    Ý tưởng chính của thuật toán nằm ở chỗ xét dấu pi để quyết định điểm kế tiếp, và sử dụng công thức truy hồi pi+1- pi để tính pi bằng các phép toán đơn giản trên số nguyên.
    Tuy nhiên thuật toán Bresenham xây dựng phức tạp hơn thuật toán DDA.
    Thuật toán MidPoint đưa ra cách chọn yi+1 là yi hay yi +1 bằng cách so sánh điểm thực Q với điểm MidPoint là trung điểm của S và P. Ta có :
    Nếu điểm Q nằm dưới điểm MidPoint, ta chọn S.
    - Ngược lại nếu điểm Q nằm trên điểm MidPoint ta chọn P.
    Ta có dạng tổng quát của phương trình đường thẳng là :
    Ax + By + C = 0 Với A = y2 –y1; B = - (x2 – x1) ; C = x2y1 -x1y2 
    Đặt F(x,y)=Ax + By + C thì ta có nhận xét F(x,y) <0,nếu (x,y) nằm phía trên đường thẳng
    F(x,y) = 0 nếu (x,y) nằm thuộc đường thẳng
    F(x,y) > 0 nếu (x,y)nằm phía dưới đường thẳng
    Lúc này việc chọn điểm S hay P được đưa về việc xét dấu của pi = 2F(midpoint) = 2F(xi+1;yi+1/2)
    Xây dựng pi trong trường hợp 0<=m<=1, và Dx <0
    Giống như một số thuật toán khác, ta không tính toán trực tiếp các giá trị pi để chọn điểm tiếp theo mà tính toán dựa trên kết quả của bước trước.
    Xét pi+1-pi=2F(xi+1+1,yi+1+1/2)-2F(xi+1,yi+1/2)
    Thay F(x,y)=Ax+By+C với A=Dy, B=-Dx vào ta được kết quả pi+1-pi=2Dy-2Dx(yi+1-yi) (1)
    Nhận xét:
    Khi yi+1=yi ta có (1) pi+1=pi+2Dy
    Khi yi+1=yi+1 ta có (1)  pi+1=pi+2Dy-2Dx=pi+2(Dy-Dx)

    Giá trị p0 ứng với điểm ban đầu được tính:
    p0=2F(xđầu+1, y đầu+1/2)=2[A(xđầu+1)+B(yđầu+1/2)+C] =2Dy-Dx
    Tóm tắt thuật toán:
    p0=2Dy-Dx
    yi+1=



    pi+1=

    yi nếu pi <0
    yi+1 nếu pi >=0
    pi+2Dy nếu pi <0
    pi+2(Dy-Dx) nếu pi >=0
    Trường hợp 1: |Dy|<=|Dx|
    A
    B
    A
    B
    B
    A
    B
    A
    Giải thuật bằng thuật toán Midpoint trong trường hợp 1
    |Dy|<=|Dx|;
    . Bước 1: Xác định điểm đầu
    int Dx = x2 – x1, Dy = y2 – y1;
    int x = x1, y = y1;
    int p = 2 * Dy – Dx;
    int const1 = 2 * Dy, const2 = 2 * (Dy-Dx);
    putpixel(x, y, color);
    dx =(Dx>0)? 1:-1;
    dy=(Dy>0)? 1:-1;
    Bước 2: Xác định những điểm tiếp theo
    Lặp
    x!=x2 ;
    Nếu p<0:
    p+=const1;
    Nếu p>=0:
    p+=const2;
    y+=dy;
    x+=dx;
    Putpixel(x,y,color);

    Luư đồ thuật toán Midpoint trường hợp 1: |Dy|<=|Dx|
    begin
    p = 2Dy - Dx;
    const1=2Dy; const2=2(Dy-Dx);
    x = x1; y = y1;
    putpixel(x,y,color);
    dx = (Dx >0)? 1:-1;
    dy = (Dy > 0)?1:-1;
    x != x2
    p+=const1;
    end
    NO
    YES
    p < 0
    p+=const2;
    y + = dy;
    x += dx;
    Putpixel(x, y,color);
    YES
    NO
    Cài đặt thuật tóan Midpoint trong trường hợp 1
    #include
    #include
    #include
    using namespace std;
    Void Bresenham_line (int x1,int y1, int x2, int y2, Color color)
    {
    int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1;
    int p = 2 * Dy – Dx ; int const1 = 2 * Dy , const2 = 2 * (Dy-Dx);
    putpixel(x, y, color) ;
    int dx =(Dx>0)? 1:-1 ,dy=(Dy>0)? 1:-1;
    if(abs(Dy) <= abs(Dx)) {
    while(x != x2)
    {
    if ( p < 0) p+=const1;
    else {
    p+=const2;
    y += dy;
    }
    x += dx;
    putpixel(x,y,color);
    }
    }
    }
    A
    B
    A
    B
    B
    A
    A
    B
    Trường hợp 2
    |Dy|<=|Dx|
    Các dạng đường thẳng thỏa |Dy| > |Dx|
    Giải thuật bằng thuật toán MidPoint trong trường hợp 2
    |Dy|>|Dx|;
    Bước 1: Xác định điểm đầu
    int Dx = x2 – x1, Dy = y2 – y1;
    int x = x1, y = y1;
    int p = 2 * Dx – Dy;
    int const1 = 2 * Dx, const2 = 2 * (Dx-Dy);
    putpixel(x, y, color);
    int dx =(Dx>0)? 1:-1;
    int dy=(Dy>0)? 1:-1;
    Bước 2: Xác định những điểm tiếp theo
    Lặp
    y!=y2 ;
    Nếu p<0:
    p+=const1;
    Nếu p>=0:
    p+=const2;
    x+=dx;
    y+=dy;
    Putpixel(x,y,color);

    Luư đồ thuật toán Midpoint trong trường hợp 2: |Dy|>|Dx|
    begin
    p = 2Dx - Dy;
    const1=2Dx; const2=2(Dx-Dy);
    x = x1; y = y1;
    putpixel(x,y,color);
    dx = (Dx >0)? 1:-1;
    dy = (Dy > 0)?1:-1;
    y != y2
    p+=const1;
    end
    NO
    YES
    p < 0
    p+=const2;
    x+ = dx;
    y+= dy;
    Putpixel(x, y,color);
    YES
    NO
    Cài đặt thuật toán Midpoint trong trường hợp 2
    #include
    #include
    #include
    using namespace std;
    Void Bresenham_line (int x1,int y1, int x2, int y2, Color color)
    {
    int Dx = x2 – x1, Dy = y2 – y1; int x = x1, y = y1;
    int p = 2 * Dx – Dy ; int const1 = 2 * Dx , const2 = 2 * (Dx-Dy);
    putpixel(x, y, color) ;
    int dx =(Dx>0)? 1:-1 ,dy=(Dy>0)? 1:-1;
    if(abs(Dy) > abs(Dx)) {
    while(y != y2)
    {
    if ( p < 0) p+=const1;
    else {
    p+=const2;
    x += dx;
    }
    y += dy;
    putpixel(x,y,color);
    }
    }
    }
    Mở rộng thuật toán Midpoint trong các trường hợp vẽ đường thẳng với m bất kì
    ***Trường hợp đặc biệt m = : Đoạn thẳng song song trục tung nên rất đơn giản khi vẽ.
    ***Trường hợp -1<=m<=1 :Sử dụng các công thức của thuật toán vẽ trong trường hợp 0 < = m <=1, Dx >0 và thay đổi một số điểm sau:
    Nếu Dx < 0 thì bước nhảy của x sẽ thay bằng -1 tương tự nếu Dy <0, bước nhảy của y cũng sẽ là -1.
    Thay Dx bằng abs(Dx), Dy = abs(Dy) trong tất cả các công thức có chứa Dx,Dy
    *** Trường hợp m<= -1 hay m>=1
    Thay đổi vai trò của x và y cho nhau, thay đổi vai trò của Dx và Dy cho nhau trong tất cả các công thức
    Thực hiện nguyên tắt về bước nhảy và thay đổi Dx, Dy như trong trường hợp -1< = m < =1
    Dựa vào tính chất đối xứng của đường tròn ta có thể mở rộng các thuật toán Bresenham và Midpoint cho việc vẽ đường tròn
    y
    THUẬT TOÁN VẼ ĐƯỜNG TRÒN
    y
    (x,y)
    (y,x)
    (-y,x)
    (x,-y)
    (-x,-y)
    (-y,-x)
    (y,-x)
    (-x,y)
    x
    Trong hệ tọa độ Descartes, phương trình đường tròn bán kính R có dạng:
    Với tâm O(0,0) :
    x2 + y2 = R2
    Với tâm C(xc,yc):
    (x - xc)2 + (y - yc)2 = R2
    Trong hệ tọa độ cực :
    x = xc+ R.cosθ
    y = yc + Y.sinθ
    với θ thuộc [0, 2π].
    - Do tính đối xứng của đường tròn C (xem hình 1.7) nên ta chỉ cần vẽ 1/8 cung tròn,
    - sau đó lấy đối xứng qua 2 trục tọa độ và 2 đường phân giác thì ta vẽ được cả đường tròn.
    THUẬT TOÁN VẼ ĐƯỜNG TRÒN BẰNG MIDPOINT
    Do tính đối xứng của đường tròn nên ta chỉ cần vẽ 1/8 cung tròn, sau đó lấy đối xứng là vẽ được cả đường tròn.
    Thuật toán MidPoint đưa ra cách chọn yi+1 là yi hay yi-1
    bằng cách so sánh điểm thực Q(xi+1,y) với điểm giữa MidPoind là trung điểm của S1 vàS2.
    Chọn điểm bắt đầu để vẽ là (0,R). Giả sử (xi, yi) là điểm nguyên đã tìm được ở bước thứ i (xem hình 1.8), thì điểm (xi+1, yi+1) ở bước i+1 là sự lựa chọn giữa S1 và S2.
    Xi+1 = x + 1
    yi+1= yi – 1 hoặc yi;

    THUẬT TOÁN VẼ ĐƯỜNG TRÒN BẰNG MIDPOINT
    Đặt F(x,y) = x2 + y2 - R2 , ta có :
    . F(x,y) < 0 , nếu điểm (x,y) nằm trong đường tròn.
    . F(x,y) = 0 , nếu điểm (x,y) nằm trên đường tròn.
    . F(x,y) > 0 , nếu điểm (x,y) nằm ngoài đường tròn.
    Xét Pi = F(MidPoint) = F(xi +1, yi - 1/2). Ta có :
    - Nếu Pi < 0 : điểm MidPoint nằm trong đường tròn. Khi đó, điểm thực Q gần với điểm
    S1 hơn nên ta chọn yi+1 = yi .
    - Nếu Pi>= 0 : điểm MidPoint nằm ngòai đường tròn. Khi đó, điểm thực Q gần với điểm
    S2 hơn nên ta chọn yi+1 = yi - 1.
    Mặt khác :
    Pi+1 - Pi = F(xi+1 +1, yi+1 - 1/2) - F(xi + 1, yi - 1/2)
    = [(xi+1 +1)2 + (yi+1 - 1/2)2 - R2 ] - [(xi +1)2 + (yi - 1/2)2 - R2 ]
    = 2xi + 3 + ((yi+1)2 + (yi)2 ) - (yi+1 - yi)

    Vậy :
    - Nếu Pi < 0 : chọn yi+1 = yi. Khi đó Pi+1 = Pi+ 2xi +3
    - Nếu Pi >= 0 : chọn yi+1 = yi - 1. Khi đó Pi+1 = Pi+ 2xi - 2yi +5.
    - Piứng với điểm ban đầu ( x0 , y0 ) = (0,R) là:
    P0 = F(x0 + 1, y0 - 1/2) = F(1, R - 1/2) =5/4 -R
    XÂY DỰNG THUẬT TOÁN VẼ ĐƯỜNG TRÒN BẰNG MIDPOINT
    Q(xi+1,y)
    Midpoint
    S1
    S2
    yi
    yi-1
    yi+1
    (xi,yi)
    Luư đồ thuật toán Midpoint cho đường tròn
    begin
    P = 5/4 - R;
    x=0 ; y= R;
    Putpixel8(x,y,c);
    xP = P + 2*x + 3
    end
    NO
    YES
    p < 0
    P = P + 2*(x-y)+5
    y = y - 1
    x++;
    putpixel8(x,y,color)
    YES
    NO
    Cài đặt thuật toán Midpoint cho đường tròn
    void MidpointCircle(int a,int b,int r,Color c){
    int x,y;
    x=0;
    y=r;
    put8pixel(x,y,a,b,c);
    int p=1-r;
    while(x if(p<0) {
    p+=2*x+3;
    }
    else {
    p+=2*(x-y)+5;
    y--;
    }
    x++;
    put8pixel(x,y,a,b,c);
    }
    }
    Ví dụ Demo đường tròn bằng thuật toán Midpoint
    Midpointcircle(15,16,13,Color(255,0,0));
    Vẽ đường tròn bằng thuật toán Bresenham
    Tương tự thuật toán vẽ đường thẳng Bresenham, các vị trí ứng với các tọa độ nguyên nằm trên đường tròn có thể tính được bằng cách xác định một trong hai pixel gần
    nhất với đường tròn thực hơn trong mỗi bước

    S1
    S2
    yi
    yi-1
    yi+1=y
    (xi,yi)
    d1
    d2
    XÂY DỰNG THUẬT TOÁN BRESENHAM VẼ ĐƯỜNG TRÒN
    Ta có :
    d1 = (yi)2 - y2 = (yi)2 - (R2- (xi + 1)2 )
    d2 = y2 - (yi - 1)2 = (R2- (xi + 1)2 ) - (yi - 1)2Pi = d1 - d2
    * Tính Pi+1 - Pi
    => Pi+1 = Pi + 4xi + 6 + 2((yi+1)2 - (yi)2 ) - 2(yi+1 - yi)
    - Nếu Pi < 0 : chọn yi+1 = yi. Khi đó Pi+1 = Pi+ 4xi +6
    - Nếu Pi >= 0 : chọn yi+1 = yi - 1. Khi đó Pi+1 = Pi+ 4(xi - yi ) + 10.
    - P0ứng với điểm ban đầu ( x0 , y0 ) = (0,R) là: P0= 3 - 2R.
    Luư đồ thuật toán Bresenham cho đường tròn
    begin
    P= 3 - 2R
    x=0 ; y= R;
    Putpixel8(x,y,c);
    xP = P+ 4x +6
    end
    NO
    YES
    p < 0
    P += 4(x - y ) + 10
    x++;
    putpixel8(x,y,color)
    YES
    NO
    Cài đặt thuật toán Bresenham cho đường tròn
    void Bres_circle(int a,int b,int r,Color c){
    int x,y;
    x=0;
    y=r;
    put8pixel(x,y,a,b,c);
    int p=3-2*r;
    while(x {
    if(p<0) {
    p+=4*x+6;
    }
    else {
    p+=4*(x-y)+10;
    y--;
    }
    x++;
    put8pixel(x,y,a,b,c);
    }
    }
    Ví dụ Demo thuật toán Bresenham vẽ đường tròn
    Bres_circle(25,26,17,Color(225,0,0));
    Ngoài ra ta còn có thể mở rộng thuật toán Bresenham cho việc vẽ đường tròn và các đường conic
    VẼ ELIP BẰNG BRESENHAM
    Tương tự thuật toán vẽ đường tròn, sử dụng thuật toán Bresenham để vẽ, ta chỉ cần
    vẽ 1/4 ellipse, sau đó lấy đối xứng qua các trục tọa độ sẽ vẽ được toàn bộ ellipse.
    Xét ellipse có tâm O, các bán kính là a và b, phương trình là x^2/a^2 – y^2/b^2=1
    Chọn tọa độ pixel đầu tiên cần hiển thị là (xi ,yi) = (0,b). Cần xác định pixel tiếp theo là
    (xi+1 ,yi+1).
    Ta có :
    xi+1=x+1;
    yi+1=yi-1 hay yi
    d1 = (yi)^2 – y^2
    d2 = y^2 - (yi - 1)^2

    XÂY DỰNG THUẬT TOÁN BRESENHAM VẼ ELIP
    d1 = (yi)^2 – y^2
    d2 = y^2 - (yi - 1)^2
    Pi = d1 - d2
    Tính Pi+1 - Pi
    => Pi+1 = Pi + 2((yi+1)^2 - (yi)^2 ) - 2(yi+1 - yi)+2b^2/a^2(2xi+3)
    - Nếu Pi < 0 : chọn yi+1 = yi. Khi đó Pi+1 = Pi+2b^2/a^2(2xi+3)
    - Nếu Pi >= 0 : chọn yi+1 = yi - 1.
    Khi đó Pi+1 = Pi+2b^2/a^2(2xi+3)+4(1-yi)
    - Pi ứng với điểm ban đầu ( x0 , y0 ) = (0,b) là:
    P0=2b^2/a^2-2b+1
    YES
    Luư đồ thuật toán Bresenham cho đường Elip
    begin
    int x=0,y=b;
    int z1= (b*b)/(a*a), z2= 1/ z1;
    int P= 2*z1 - 2*b +1; putpixel4(x,y,color)
    z1* (x/y) ≤ 1
    P +=2*z1*(2*x+3)
    end
    NO
    p < 0
    P +=2*z1*(2*x+3) + 4*(1-y);
    y--;
    x++;
    putpixel4(x,y,color)
    YES
    NO
    int y=0,x=a;
    int P= 2*z2 - 2*b +1;
    putpixel4(x,y,color)
    z2* (y/x) < 1
    p < 0
    P +=2*z2*(2*x+3)
    P +=2*z2*(2*x+3) + 4*(1-y);
    x--
    YES
    NO
    NO
    YES
    y++;
    putpixel4(x,y,color)
    Cài đặt thuật toán Bresenham cho Elip
    int x,y;
    void ellipse(int xc, int yc, int a, int b, Color color){
    double z1,z2,P;
    x=0;y=b;
    z1=(double)(b*b)/(a*a);
    z2=(double)1/z1;
    P=2*z1-(2*b)+1;
    while(z1*(double)x/y<=1){
    put4pixel(xc+x,yc+y,color);
    if (P<0) P+=2*z1*(2*x+3);
    else{
    P+=2*z1*(2*x+3)+4*(1-y);
    y--;
    }
    x++; }
    x=a;y=0;
    P=2*z2-2*a+1;
    while(z2*(double)y/x<=1){
    put4pixel(xc+x,yc+y,color);

    if (P<0) P+=2*z2*(2*y+3);
    else{
    P+=2*z2*(2*y+3)+4*(1-x);
    x--;
    }
    y++; }
    }

    Ví dụ Demo vẽ đường Elip bằng thuật toán Bresenham
    ellipse(23,28,22,10,Color(0,225,0));
    Đề tài của nhóm 9 đến đây xin kết thúc. Vì thời gian và kiến thức có hạn nên chắc chắn đề tài của chúng em còn nhiều vấn đề sai sót, rất mong được sự giúp đỡ và việc đóng góp ý kiến của thầy. Điều đó giúp chúng em hoàn thành những đề tài sau này tốt hơn. Chúng em xin cảm ơn thầy. Kính chúc thầy sức khỏe dồi dào.
    Cảm ơn
    No_avatar
    cái này rất hay, có thể còn tài liệu nào tiếp tài liệu tren ko ạ
     
    Gửi ý kiến
    print