›
›

Bài giảng Đồ họa máy tính - Chương 2: Các đối tượng đồ họa cơ sở - Trần Thị Minh Hoàn

pdf 39 trang Gia Huy 16/05/2022 2760
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Đồ họa máy tính - Chương 2: Các đối tượng đồ họa cơ sở - Trần Thị Minh Hoàn", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_do_hoa_may_tinh_chuong_2_cac_doi_tuong_do_hoa_co_s.pdf

Nội dung text: Bài giảng Đồ họa máy tính - Chương 2: Các đối tượng đồ họa cơ sở - Trần Thị Minh Hoàn

  1. Chương II: Các đối tượng đồ họa cơ sở  Điểm  Đường thẳng  Tam giác 1
  2. Màn hình điểm -Chúng ta cần tọa độ màn ảnh thực 2D để chỉ rõ vị trí các điểm ảnh. -Các chi tiết của các hệ thống như vậy là biến đổi theo các API. -Nhưng phổ biến nhất là sử dụng lưới giá trị nguyên cho các tâm điểm ảnh, điểm ảnh trên ở vị trí trung tâm cách biên 0.5. 2
  3. Thuật toán vẽ đoạn thẳng  Input: điểm đầu A(x1, y1), điểm cuối B(x2, y2), màu tô color C.  Output: Xác định các điểm tạo thành một đoạn thẳng nối hai điểm AB và có màu C. 3
  4. Thuật toán vẽ đoạn thẳng  Chuyển đổi đường quét (Rasterization)  Biến đổi đường liên tục thành rời rạc (Sampling)  Scan conversion = Sampling  Yêu cầu chất lượng đường vẽ  Hình dạng liên tục  Độ dày và độ sáng đều  Các pixel gần đường “lý tưởng” được hiển thị  Vẽ nhanh 4
  5. Thuật toán vẽ đoạn thẳng  Phương trình đoạn thẳng đi qua hai điểm y2 y1 y x x1 y1 x2 x1 y y k 2 1 m y1 kx1 x2 x1 y kx m 5
  6. Để đơn giản giải thuật chúng ta chỉ xét các đường thẳng có hệ số góc dương và nhỏ hơn 1 để đảm bảo sự thay đổi của x sẽ lớn hơn của y. y k > - 1 m -1 y2 k > - 6
  7. Các thuật toán vẽ đoạn thẳng  Thuật toán DDA (Digital Defferencial Analyzer) hay thuật toán tăng dần (Basic Incremental Algorithm)  Thuật toán Bresenham  Thuật toán trung điểm 7
  8. Thuật toán DDA  DDA- Digital Defferencial Analyzer = Finite defferences Xét các đường thẳng có hệ số góc dương và nhỏ hơn 1 để đảm bảo sự thay đổi của x sẽ lớn hơn của y. Giả sử tại bước thứ i ta đã xác định được xi và yi. Ta cần xác định bước thứ i+1 xi+1=xi +1 Giá trị của y sẽ tương ứng từ phương trình sau: yi+1= yi+ k(xi+1- xi); yi+1= yi+ k Vì k là số thực nên để thu yi+1 nguyên ta buộc phải làm tròn trước khi đưa tọa độ truy xuất lên màn hình. Ví dụ (2,3) -> (12,9) 8
  9. Thuật toán DDA  Nhận xét thuật toán DDA  Không có phép nhân  Có phép chia và làm tròn số -> chậm  Quy tắc tổng quát khi vẽ đồ họa:  Cộng và trừ nhanh hơn nhân  Nhân nhanh hơn chia  Sử dụng bảng để đánh giá hàm rời rạc nhanh hơn tính toán  Tính toán số nguyên nhanh hơn số thực  Tránh các tính toán không cần thiết nhờ nhận ra các trường hợp đặc biệt của đường vẽ 9
  10. Thuật toán Bresenham vẽ line yi+1 y = ax + b  Giả sử vừa vẽ điểm tại (xi, yi), bây giờ phải xác định điểm sẽ vẽ thuộc một yi y -1 trong 8 pixel liền kề: (xi+1, yi), (xi-1, yi), i (xi, yi-1), (xi, yi+1) xi-1 xi xi+1  Hình dạng đoạn thẳng phụ thuộc vào các giá trị dx và dy y đ/thẳng song song trục y 1 2 y1 k > - 1 đ/thẳng song song trục x 1 2 0 k 1 x2 0 -> tọa độ x biến thiên tăng dần 0 k -1 (x2, y2)  dx tọa độ x biến thiên giảm dần (x1, y1)  Xét tương tự với dy x2 k -1  Nếu abs(dx)>abs(dy): y=f(x)  Nếu abs(dx) k > - 10
  11. Thuật toán Bresenham vẽ line 11
  12. Thuật toán Bresenham vẽ line  Xét đoạn thẳng có hệ số góc 0 k 1.  Điểm vừa chọn là (x,y) -> điểm tiếp theo sẽ vẽ là (x+1,y) hay (x+1, y+1).  Ta có phương trình đường thẳng y y y = x - x + y x x 1 1 y Đặt k= ; m= y - kx x 1 1 Ta có y=kx+m d2=yi + 1- yi+1; d1=yi+1 – yi Di= x (d2-d1)= x (2yi - 2yi+1 + 1) Di= x (2yi-2kxi - 2k-2m+1) Di+1= x (2yi+1-2kxi+1 - 2k-2m+1) Nếu Di>0, chọn điểm dưới Di+1=Di-2 y Nếu Di<=0, chọn điểm trên Di+1=Di +2 x - 2 y 12
  13. Thuật toán Bresenham vẽ line void breline (x1,y1,x2,y2){ int x, y, dx, dy, color; float D; dx=x2-x1; dy=y2-y1; D=dx-2dy; x=x1; y=y1; while (x 0 D=D-2dy; Else {D=D +2dx-2dy; y=y+1} x=x+1; } } 13
  14. Thuật toán Bresenham vẽ line  Thuật toán trên chỉ tính toán với số nguyên  Nhân 2 -> dịch trái  Chú ý cài đặt vẽ đoạn thẳng với hệ số góc bất kỳ 14
  15. Thuật toán trung điểm vẽ line  Pitteway công bố 1967, Van Aken cải tiến 1984  Giả sử ta đã chọn P để vẽ, xác định pixel tiếp theo tại E hay NE  Giao của đường thẳng với Xp+1 tại Q, M là trung điểm của NE và E  Ý tưởng: M nằm phía nào của đường thẳng, nếu M phía trên đường thẳng thì chọn E, ngược lại chọn NE.  Nhiệm vụ: Xác định M ở đâu. M” y +1/2 NE p Q M’ M yp+1/2 yp+1/2 E x +1 P=(xp, yp) p xp+2 15
  16. Thuật toán trung điểm vẽ line  Phương trình đường thẳng: F(x,y)=ax+by+c dy dy F(x, y) x B y 0 y x B dx dx F(x, y) dy.x dx.y B.dx 0  a=dy, b=-dx, c=B.dx  Giá trị hàm tại M: F(M)=F(xp+1, yp+1/2)=d  Nếu d>0, M nằm dưới đường thẳng -> chọn NE  Nếu d chọn E M” y +1/2  Nếu d=0, chọn E hay NE tùy ý NE p Q M’ M y +1/2 p yp+1/2 E x +1 P=(xp, yp) p xp+2 16
  17. Thuật toán trung điểm vẽ line  Giá trị của hàm tại M của điểm tiếp theo sẽ vẽ  Gọi giá trị d vừa tính là 1 d old a(x p 1) b(y p 2 ) c  Giả sử vừa chọn E: d F(x 2, y 1 ) a(x 2) b(y 1 ) c new p p 2 p p 2 dnew=dold+a=dold+dy -> dy là số gia của điểm tiếp theo  Giả sử vừa chọn NE 3 dnew F(x p 2, y p 2 ) M” NE yp+1/2 3 a(x p 2) b(y p 2 ) c Q M’ M y +1/2  dnew=dold+a+b=dold+dy-dx p yp+1/2  dy-dx là số gia của điểm tiếp theo E x +1 P=(xp, yp) p xp+2 17
  18. Thuật toán trung điểm vẽ line  Tính giá trị khởi đầu của d  Giả sử vẽ đoạn thẳng từ (x0, y0) đến (x1, y1) -> trung điểm thứ nhất có tọa độ (x0+1, y0+1/2) F(x 1, y 1 ) a(x 1) b(y 1 ) c 0 0 2 0 0 2 b b a.x0 b.y0 c a F(x0 , y0 ) a 2 2  F(x0, y0) = 0 -> dstart=a+b/2=dy-dx/2  Tránh số thập phân của dstart, định nghĩa lại hàm như sau F(x,y)=2(ax+by+c)  Do vậy, ta có dstart=2dy -dx; E=2dy; NE=2(dy-dx) 18
  19. Thuật toán trung điểm vẽ line procedure MidpointLine(x0, y0, x1, y1, color: integer) while x<x1 do var begin dx, dy, x, y, d, incrE, incrNE: integer; if d<=0 then begin begin {Select E} dx := x1 – x0; d := d+incrE; dy := y1 – y0; x := x+1 d := 2*dy-dx; end incrE := 2*dy; else incrNE := 2*(dy-dx); begin {Select NE} d := d+incrNE; x :=x0; x :=x+1; y :=y0; y :=y+1 WritePixel(x, y, color); end WritePixel(x, y, color); end {while} end; 19
  20. Thuộc tính của đường vẽ  Thuật toán vẽ đoạn thẳng nói trên đều vẽ đoạn thẳng có độ rộng 1 pixel, nét liên tục  Hai thuộc tính quan trọng của đường vẽ  Độ rộng: vẽ đoạn thẳng từ (x0, y0) đến (x1, y1)  Nếu dy>dx: các pixel được vẽ thêm tại tọa độ bên trái và bên phải điểm vẽ (x-1 và x+1)  Nếu dx>dy: vẽ thêm các pixel phía trên và dưới điểm vừa vẽ  Đường nét đứt:  Sử dụng các pattern, mặt nạ với bit cao nhất bằng 1  Dựa trên kết quả phép AND mặt nạ với mẫu để quyết định có vẽ điểm ảnh tại vị trí hiện hành hay không. 20
  21. Các thuật toán vẽ đường tròn  Một số tính chất đường tròn  Thuật toán Bresenham  Thuật toán trung điểm 21
  22. Các thuật toán vẽ đường tròn  Tương tự như vẽ đoạn thẳng, đường tròn đồ họa hình thành bởi các pixel gần đường tròn toán học nhất (Rasterization).  Một vài tính chất cơ bản:  Vẽ đường tròn tâm tại gốc tọa độ sau đó dịch chuyển đến vị trí mong muốn (-y, x) (y, x)  Tính đối xứng: khi biết tọa độ 1 điểm dễ dàng suy ra tọa độ của 7 (-x, y) (x, y) điểm còn lại 450  Sử dụng phương trình để tính tọa (-x, -y) độ đường tròn -> dấu phảy động. (x, -y)  Các thuật toán tối ưu khác (-y,-x) (y, -x) 22
  23. Thuật toán Bresenham vẽ đường tròn  Ý tưởng  Giả sử tại bước thứ i ta đã xác định được (xi,yi)  Tại bước thứ i+1  Ta có xi+1 = xi +1  Gọi yi+1 là giá trị chính xác của tung độ tương ứng với điểm có hoành độ là (xi +1)  d1 là khoảng cách giữa yi và yi+1  d2 là khoảng cách giữa yi+1 và (yi -1)  Khi đó nếu d1 < d2 thì yi+1 = yi  Ngược lại yi+1 = yi – 1 23
  24. Thuật toán Bresenham vẽ đường tròn  Phương trình đường tròn x2 y 2 R 2  Phương trình đường tròn có hàm mũ tại y nên nếu tính d1, d2 theo y thì sẽ có hàm căn làm chậm thuật toán, do vậy ta đặt: ' 2 2 d1 yi y i 1 d' y 2 ( y 1) 2 2i 1 i ''  Đặt pi d1 d 2  Tính pi+1 theo pi 24
  25. Thuật toán Bresenham vẽ đường tròn 1. Chọn vị trí thứ nhất để vẽ có tọa độ (x1, y1)=(0, r) 2. Tính tham số thứ nhất: p1=3-2r  Nếu p1<0: vị trí vẽ tiếp theo là (x1+1, y1). Ngược lại vẽ tại tọa độ (x1+1, y1-1). 3. Tiếp tục tăng x để tính p tiếp theo từ p trước đó  Nếu trước đó có pi<0: pi+1=pi+4xi+6  Ngược lại, ta có: pi+1=pi+4(xi-yi)+10  Nếu kết quả pi+1<0: điểm sẽ chọn tiếp theo là (xi-2, yi+1).  Ngược lại, ta chọn: (xi+2, yi+1-1).  Nếu pi<0 thì yi+1= yi, ngược lại yi+1= yi-1 yi 4. Lặp lại bước 3 cho đến khi x=y. y y -1 i xi+1 25
  26. Thuật toán trung điểm vẽ đường tròn  Ý tưởng thuật toán: Khi đã vẽ điểm P tại (xp, yp), phải quyết định điểm vẽ tiếp theo là E hay SE  Phương trình đường tròn 2 2 2 P=(x , y ) F (x, y) x y R p p E  F(x,y)=0 -> (x,y) trên đường tròn M M E  F(x,y) (x,y) trong đường tròn SE  F(x,y)>0 -> (x,y) ngoài đường tròn MSE  Nếu M trong vòng tròn -> E gần đường tròn  Ngược lại -> SE gần đường tròn 26
  27. Thuật toán trung điểm vẽ đường tròn  Biến quyết định d: giá trị hàm tại điểm giữa M 1 2 1 2 2 dold F(x p 1, y p 2 ) (xp 1) (y p 2 ) R  Nếu dold 0 thì chọn SE, x tăng 1, y giảm 1. old p p M M E 3 d new F (x p 2, y p 2) SE M 2 3 2 2 SE (x p 2) ( y p 2 ) R d new d old (2x p 2 y p 5) d old SE 27
  28. Thuật toán trung điểm vẽ đường tròn  Vòng lặp của thuật toán  Chọn pixel để vẽ dựa trên dấu biến quyết định d của vòng lặp trước  Cập nhật biến quyết định d bởi giá trị tương ứng với pixel SE hay E vừa chọn  Giá trị khởi đầu  Điểm vẽ đầu tiên có tọa độ (0, R) P=(x , y ) p p E  Biến quyết định d có giá trị: M M E 1 2 1 2 5 d F (1, R 2 ) 1 (R R 4 ) R 4 R SE MSE  Đặt biến quyết định mới h=d-1/4, ta có: 1 5 h 4 4 R h 1 R 28
  29. Thuật toán trung điểm vẽ đường tròn procedure MidpointCircle(radius, color: integer); {Giả sử tâm đường tròn tại gốc tọa độ} var procedure CirclePoints(x, y, x, y: integer; d: real; color: interger); begin begin x:=0; y:=radius; WritePixel(x,y, color); d:=1-radius; WritePixel(y,x, color); CirclePoints(x, y, color); while y>x do WritePixel(y,-x, color); begin WritePixel(x,-y, color); if d<0 then {Chọn E} begin WritePixel(-x,-y, color); d:=d+2*x+3; WritePixel(-y,-x, color); x:=x+1 end WritePixel(-y,x, color); else { Chọn SE } WritePixel(-x,y, color); begin d:=d+2*(x-y)+5; end; x:=x+1; y:=y-1 end; CirclePoints(x, y, color); end {while} end; 29
  30. Thuật toán trung điểm vẽ elíp  Phương trình elíp có tâm tại gốc tọa độ F (x, y) b2 x 2 a 2 y 2 a 2b 2 0  Áp dụng giải pháp trung điểm vẽ đường tròn để vẽ elíp  Tính đối xứng của elíp: khi biết tọa độ 1 điểm có thể dễ dàng suy ra tọa độ ba điểm khác. Tangent slope=-1 j E component Gradient vector Gradient vector SE Region 1 S SE Region 2 i component 30
  31. Thuật toán trung điểm vẽ elíp  Tìm ranh giới hai miền trong ¼ elíp  Vị trí: Điểm P là tiếp điểm của tiếp tuyến có hệ số góc –1  Xác định:  Véc tơ vuông góc với tiếp tuyến tại tiếp điểm -> gradient F F gradF (x, y) i j 2b2 x.i 2a 2 y. j x y  Tại P1 các thành phần i và j của véc tơ gradient có cùng độ lớn Tangent slope=-1 Miền 1: Thành j E component phần i lớn hơn Gradient vector Gradient vector thành phần j SE a 2 y b2 x Region 1 S SE Region 2 i component 31
  32. Thuật toán trung điểm vẽ elíp  Ý tưởng: Đánh giá hàm tại điểm giữa hai tọa độ pixel để chọn vị trí tiếp theo để vẽ. Dấu của nó cho biết điểm giữa nằm trong hay ngoài elíp.  Với vùng 1:  Tính biến quyết định d=F(x,y)=F(xp+1, yp-1/2)  Nếu d<0: chọn E, x tăng 1, y không thay đổi. E 1 2 2 2 1 2 2 2 dold F (x p 1, y p 2 ) b (x p 1) a ( y p 2 ) a b P1 d F (x 2, y 1 ) b 2 (x 2) 2 a 2 ( y 1 )2 a 2b 2 SE new p p 2 p p 2 Region 1 d d b 2 (2x 3) d S SE new old p old E Region 2  Nếu d 0: chọn SE, x tăng 1, y giảm 1 3 2 2 2 3 2 2 2 d new F (x p 2, y p 2 ) b (x p 2) a ( y p 2 ) a b 2 2 d new dold b (2x p 3) a ( 2 y p 2) dold SE 32
  33. Thuật toán trung điểm vẽ elíp  Với vùng 2:  Tính biến quyết định d =F(x, y)=F(xp+1/2, yp-1)  Nếu d<0: chọn SE, x tăng 1, y giảm 1.  Nếu d 0: chọn S, x không tăng, y giảm 1  Tìm số gia như vùng 1 2 S = a (-2yp+3) E 2 2 P1 SE= b (2xp+2)+a (-2y+3) SE Region 1 S SE Region 2 33
  34. Thuật toán trung điểm vẽ elíp  Tìm giá trị khởi đầu của số gia d  Miền 1:  Giả sử a, b nguyên; điểm bắt đầu vẽ là (0, b)  Điểm giữa thứ nhất: (1, b-1/2) a 2 1 2 2 1 2 2 2 2 2 1 2 2 F (1,b 2 ) b a (b 2 ) a b b a ( b 4 ) b a b 4  Miền 2:  Phụ thuộc vào điểm giữa (xp+1, yp-1/2) của điểm tiếp theo điểm cuối cùng của miền 1. E 1 2 1 2 2 2 2 2 F (x p 2 , y p 1) b (x 2 ) a ( y 1) a b P1 2 SE 2 2 2 b 2 2 2 2 Region 1 b x b x a ( y 1) a b S SE 4 Region 2 34
  35. Thuật toán trung điểm vẽ elíp procedure draw_ellipse(a, b, color: integer); EllipsePoints (x, y, color); var x, y: integer; d1, d2: real; end {Vùng 1} begin d2=b2(x+1/2)2+a2(y-1)2 –a2b2; x:=0; {Khởi động} while y>0 do {Vùng 2} y:=b; begin 2 2 2 d1:=b -a b+a /4; if d2 b2(x+1)) do {Vùng 1} d2:=d2+b2(2*x+2)+a2(-2*y+3); begin x:=x+1; if d1<0 then {Chọn E} y:=y-1 begin end d1:=d1+b2(2*x+3); else x:=x+1 begin d2:=d2+a2(-2*y+3); end y:=y-1 else {Chọn SE} end begin EllipsePoints (x, y, color); 2 2 d1:=d1+b (2*x+3)+a (-2*y+2); end {Vùng 2} x:=x+1; end y:=y-1 end; 35
  36. Phân điểm hoá tam giác  Khi vẽ tam giác, chúng ta có thể mong muốn nội suy màu hay các thuộc tính khác từ giá trị tại các đỉnh.  Sử dụng tọa độ barycentric. Ví dụ, nếu tại các đỉnh có các màu là c0, c1, c2 thì màu tại một điểm trong tam giác với hệ tọa độ barycentric (α,β,γ) là:  c = αc0 + βc1 + γc2 (nội suy Gouraud) 36
  37. Phân điểm hoá tam giác  Thuật toán phân điểm hóa ảnh bắt buộc là:  for all x do  for all y do  Compute (α, β, γ) for (x, y)  If (α [0, 1] and β [0, 1] and γ [0, 1]) then  c = αc0 + βc1 + γc2  drawpixel (x, y) with color c 38
  38. Hệ tọa độ barycentric p(α, β, γ) = αa + βb + γc Một tam giác 2D với các đỉnh a, b, c có thể được sử dụng để thiết lập một hệ tọa độ phi trực giao với gốc a và các vectơ cơ sở (b − a) và (c − a). Một điểm được biểu diễn bởi một cặp có thứ tự (β, γ). Ví dụ, điểm p = (2.0, 0.5), nghĩa là, p = a + 2.0(b - a) + 0.5(c - a). 39