Đồ Họa máy tính!

**Admin** Sun Dec 19, 2010 8:05 am

Câu 1:
Đồ hoạ máy tính là gì? Các ứng dụng của đồ hoạ máy tính?
- Đồ họa máy tính là lĩnh vực của khoa học máy tính nghiên cứu về cơ sở toán học, các thuật toán cũng như các kĩ thuật để cho phép tạo, hiển thị và điều khiển hình ảnh trên màn hình máy tính.
- Đồ họa máy tính nghiên cứu tạo ra, lưu trữ và tính toán các mô hình hoặc ảnh, kết quả tạo ra phải là ảnh.
Một số ứng dụng cơ bản của ĐHMT:
- Giải trí , nghệ thuật.
- Y tế.
- Giáo dục đào tạo.
- Kiến trúc thiết kế.
- An ninh quốc phòng.
- Nông nghiệp lâm nghiêp.

Hướng dẫn làm phần bài tập phần vẽ đường thẳng.
- Không làm mất tính tổng quát của bài toán, ta giả sử rằng ≥
- Cũng không làm mất tính tổng quát của bài toán, ta giả thiết hệ số góc của đường thẳng tương ứng với đoạn thẳng
0 < k = ≤ 1 vì:
+ Nếu k > 1, ta sẽ xét đoạn thẳng ( , ); ( , ) và thay mỗi điểm (x,y) tìm được bởi (y,x).

+ Nếu k = 0, bài toán trở nên đơn giản, đoạn thẳng cần vẽ song song với 1 trong các trục tọa độ.
+ Nếu k < 0, Xét đoạn thẳng ( , ); ( , ); và thay mỗi điểm (x, y) tìm được bởi ( , y);

(x¬A, yA)

(x¬B, yB)

Câu 2:
Trình bày thuật toán vẽ đoạn thẳng Bresenham? Áp dụng xác định các điểm tạo nên đoạn thẳng (1,1); (5,3), (1,5); (3,1)
Bài Làm
** TH1: (1,1); (5,3)
A.Trình Bày Thuật Toán:
1. ý tưởng.
2. xây dụng thuật toán
3. sơ đồ khối
4. chương trình

B.Áp dụng thuật toán với các điểm tạo nên đoạn thẳng (1,1); (5,3)
Ta có:
+ k = (3 – 1)/(5 - 3) = ½
+ Khởi đầu : x = 1; y = 1; ∆x = - = 4; ∆y= yB – yA = 2, P = 2∆y - ∆x = 0;
+ Nếu P ≤ 0 : P = P + 2∆y
Ngược Lại : P= P+ 2∆y-2∆x, y++;
Dừng: x > =(5)

x y P
1 1 0
2 1 4
3 2 0
4 2 4
5 3 0
0 1 2 3 4 5
0
1 *
*

2 *
*

3 *

Dừng
→ Các điểm nối đoạn (1; 1) ;( 5; 3) là :
(1; 1), (2, 1); (3, 2); ( 4, 2); (5, 3)

** TH2: (1,5); (3,1) (Trường hợp tổng quát nhất)
B.Áp dụng thuật toán với các điểm tạo nên đoạn thẳng (1,5); (3,1)
Ta có:
+ k = (1 – 5)/(3 - 1) = -2 < 0.
Xét đoạn thẳng ( , ); ( , ); và thay mỗi điểm (x, y) tìm được bởi ( , y). như vậy xét đoạn thẳng nối hai điểm (3,1); (5, 5)

+ Ta lại xét đường thẳng nối hai điểm (3,1); (5, 5)
Hệ số góc k = (5 – 1)/(5 – 3) = 4/2 > 1

+ Ta lại xét đường thẳng (yA, xA); (yB, xB), tương đương hai điểm (1, 3); (5, 5)
Hệ số góc k = (5 – 3)/(5 – 1) = 2/4 > 0,5 (thỏa)

+ Khởi đầu :
x = 3; y = 1; ∆x = - = 4; ∆y = yB – yA = 2; P = 2∆y - ∆x = 0.
Nếu P ≤ 0 : P = P + 2∆y
Ngược Lại : P= P+ 2∆y-2∆x, y++;
Dừng: x > =(5)

x y P
1 3 0
2 3 4
3 4 0
4 4 4
5 5 0
0 1 2 3
0
1 *

2
*
3 *

4
*
5 *

• Các điểm nối đoạn thẳng (1,3); (5,5) là:
(x, y) : (1,3), (2,3), (3,4), (4,4); (5,5)

• Các điểm nối đoạn thẳng (3,1); (5,5) là: “đổi lại tọa độ y thành tọa độ x, và ngược lại. (x, y) = (y, x):”
(x, y): (3,1), (3,2), (4,3), (4,4); (5,5)

• Các điểm nối đoạn thẳng (1,5); (3,1) là: (x, y) = (2xB – x, y) = (2*3 – x, y) :
“tọa độ x bây giờ được tính bởi x = 2xB - x, trong đó xB là tọa độ x của điểm (3,1)”
(x, y): (3,1), (3,2), (2,3), (2,4); (1,5)

***Note: lưu ý lúc giải bài tập này đọc kĩ 3 trường hợp đặc biệt trên để có lời giải chính xác nhất.
Câu 3:
Trình bày thuật toán vẽ đoạn thẳng MidPoint? Áp dụng xác định các điểm tạo nên đoạn thẳng (1,1); (5,3)
Bài Làm
** TH1: (1,1); (5,3)
A.Trình Bày Thuật Toán:
1. ý tưởng.
2. xây dụng thuật toán
3. sơ đồ khối
4. chương trình

B.Áp dụng thuật toán với các điểm tạo nên đoạn thẳng (1,1); (5,3)
Ta có:
k = 2/4 = 0,5
x = 1, y = 1, ∆x = xB - xA = 4, ∆y = yB – yA = 2, P = ∆y – (∆x/2) = 2 – (4/2) = 0
Nếu: P ≤ 0: P = P + ∆y
Ngược lại: P = P + ∆y - ∆x, y++;
Dừng: x <

x y P
1 1 0
2 1 2
3 2 0
4 2 2
5 3 0
0 1 2 3 4 5
0
1 *
*

2 *
*

3 *

Dừng
→ Các điểm nối đoạn (1; 1) ;( 5; 3) là :
(1; 1), (2, 1); (3, 2); ( 4, 2); (5, 3)

** TH2: (1,5); (3,1) (Trường hợp tổng quát nhất)
Ta có:
+ k = (1 – 5)/(3 - 1) = -2 < 0.
Xét đoạn thẳng ( , ); ( , ); và thay mỗi điểm (x, y) tìm được bởi ( , y). như vậy xét đoạn thẳng nối hai điểm (3,1); (5, 5)

+ Ta lại xét đường thẳng nối hai điểm (3,1); (5, 5)
Hệ số góc k = (5 – 1)/(5 – 3) = 4/2 > 1

+ Ta lại xét đường thẳng (yA, xA); (yB, xB), tương đương hai điểm (1, 3); (5, 5)
Hệ số góc k = (5 – 3)/(5 – 1) = 2/4 > 0,5 (thỏa)

+ Khởi đầu :
x = 1; y = 3; ∆x = - = 4; ∆y = yB – yA = 2; P = ∆y – (∆x/2) = 2 – (4/2) = 0.
Nếu: P ≤ 0: P = P + ∆y
Ngược lại: P = P + ∆y - ∆x, y++;
Dừng: x < =(5)
Lặp
x y P
1 3 0
2 3 2
3 4 0
4 4 2
5 5 0
0 1 2 3
0
1 *

2
*
3 *

4
*
5 *

• Các điểm nối đoạn thẳng (1,3); (5,5) là:
(x, y) : (1,3), (2,3), (3,4), (4,4), (5,5)

• Các điểm nối đoạn thẳng (3,1); (5,5) là: “đổi lại tọa độ y thành tọa độ x, và ngược lại. (x, y) = (y, x):”
(x, y): (3,1), (3,2), (4,3), (4,4); (5,5)

• Các điểm nối đoạn thẳng (1,5); (3,1) là: (x, y) = (2xB – x, y) = (2*3 – x, y) :
“tọa độ x bây giờ được tính bởi x = 2xB - x, trong đó xB là tọa độ x của điểm (3,1)”
(x, y): (3,1), (3,2), (2,3), (2,4); (1,5)
Câu 4:
Trình bày thuật toán vẽ đường tròn Bresenham? Áp dụng xác định các điểm để vẽ đường tròn: (x-2)2 + (y-1)2 = 9
Bài Làm:
Ta có:
= 2, = 1, R = 3
Khởi đầu: x = 0, y = R =3, P = 5- 4R = -7
Điều kiện dừng: x > (R/ ) = 2,12
+ P <= 0: P+= 8x + 12
+ Ngược lại: P+= 8x – 8y + 20, y--;
(x,y):
( x+xt , y+yt ) ; ( -x+xt , -y+yt )
( -x+xt , y+yt ); ( x+xt , -y+yt )
( -y+xt , x+yt ); ( y+xt ,-x+yt )
( -y+xt , -x+yt ); ( y+xt , x+yt )

Áp dụng:
x y P
0 3 -7
1 3 5
2 2 33

Ta có:
(0,3): (2,4), (5,1), (-1,1), (2,-2)
(1,3): (3,4), (1,4), (5,0), (-1,2), (3,-2), (1,-2), (-1,0), (5,2)
(2,2): (4,3), (3,4), (0,-1), (4,1), (4,-1), (0,3)

-2 -1 0 1 2 3 4 5
4 * * *
3 * *
2 * *
1 * * *
0 * *
-1 * *
-2 * * *

Câu 5:
Trình bày thuật toán vẽ đường tròn MidPoint? Áp dụng xác định các điểm để vẽ đường tròn: (x-1)2 + (y-3)2 = 4
Bài Làm:
Ta có: = 1, = 3, R = 2, P = 5/4 – R
Nếu: P < 0: P+= 2x + 3
Ngược lại: P+= 2x – 2y + 5, y--;
Điều kiện dừng: x > R/
Áp Dụng.

x y P
0 2 -3/4
1 2 9/4
Dừng.

Ta có: (0,2): (1,5), (3,3), (1,1), (-1,3)
(1,2): (2,5), (3,4), (0,5), (3,2), (2,1), (-1,4), (-1,2), (0,1).

-1 0 1 2 3
5 * * *
4 * *
3 * * *
2 * *
1 * * *
0

Câu 6 :
Trình bày thuật toán tô màu vết dầu loang (Boundary Line)
- Thuật toán thực hiện tô màu một vùng kín giới hạn bởi màu biên Bcolor, sử dụng màu tô Fcolor và bắt đầu từ 1 điểm gieo (x, y) nằm trong vùng cần tô
- Thuật toán sử dụng quá trình đệ qui, ban đầu điểm (x, y) được tô với màu Fcolor, putpixel (x, y , Fcolor), bước tiếp theo là kiểm tra thuộc tính màu của điểm lân cận, nếu các điểm lân cận có màu khác màu biên Bcolor và màu tô Fcolor thì thuật toán gọi đệ quy với các điểm lân cận đang xét.
- Các điểm lân cận được xét là các điểm láng giềng {(x + 1 , y); (x , y-1); (x-1 , y); (x, y + 1)} hàm lấy giá trị của điểm (x, y) là getpixel( x, y).

Câu 7 :
Trình bày thuật toán tô màu nước nổi (Scan Line)
- Thuật toán thực hiện việc tô màu 1 vùng kín, giới hạn bởi mà biên Bcolor, sử dụng màu tô Fcolor, nằm trong vùng xmin , ymin , xmax, ymax.
- Thuật toán sử dụng một dòng quét ngang đi từ ymax đến ymin của vùng cần tô màu, ứng với mỗi dòng quét ta tìm các đoạn [xj min , yj max] nằm trong vùng cần tô.
- Với mỗi x [xj min , xj max] ta thực hiện việc tô màu putpixel (x, y, Fcolor)

Câu 8 :
Áp dụng phép quay quanh gốc tọa độ tính tọa độ mới của hình chữ nhật {(2, 1) ; (3, 1) ; (3, -1) ; (2 , -1)} quay xung quanh điểm (2, 2)
- B1 : Tịnh tiến điểm (2, 2) về gốc tọa độ (0 , 0) theo ma trận biến đổi T(-2 ,-2)như sau :

T=(-2, -2) =
-B2 : Quay hình chữ nhật theo góc quay quanh gốc tọa độ, ta có ma trận biến đổi như sau :

T( ) =
= 30¬¬¬¬¬¬¬¬¬¬¬¬ 0

 T(300) =
B3 : Ngược với B1, tịnh tiến từ gốc tọa độ (0 , 0) về vị trí (1, 2). Ma trận biến đổi T-1 (2 , -2)

T = T[2, 2] =

Ma trận biến đổi của phép quay góc = 300 quanh (2, 2) là :

T = T[-2 , -2] x T(30 ) x T[2 ,2 ]

=

=

A¬¬¬¬¬’ : (2 1 1) x T =
 A’
B’ : (3 1 1) x T =
 B’

C’ (3 -1 1) x T =

 C’

D’ (2 -1 1) x T =
 D’

Hình chữ nhật mới sau khi quay quanh điểm (2 , 2) 1 góc là :

{ }

Câu 9:
Toạ độ thuần nhất là gì? Tại sao người ta sử dụng toạ độ thuần nhất?
- Các phép biến đổi thông thường có thể biểu diễn thành tích của 2 ma trận, nếu xem (x,y) là ma trận 1 dòng 2 cột. Nhưng phép tịnh tiến lại biểu diễn tổng của 8 ma trận, trọng khi đối tượng chuyển động lại thường tham gia đồng thời nhiều chuyển động, trong đó có chuyển động tịnh tiến, từ đó nãy sinh ra nhu cầu các phép biến đổi này và đưa ra khái niệm tọa độ thuần nhất.
Trong hệ tọa độ thuần nhất chúng ta thêm phần tọa độ thứ 3 (áp dụng với hệ tọa độ 1 dòng 1 cột, hay còn gọi là trong không gian 2 chiều) trong tọa độ của một điểm.
Do đó: P(x, y) được biến thành P(x, y,w).
Hai tọa độ cùng biểu diễn 1 điểm nếu nó là tích của cùng 1 bộ 3 nhân với các hệ số khác nhau.
VD: (1,2,3) và (3,6,9) cùng biểu diễn điểm (1,2,3).
Nếu w !=0 (khác 0) thì ta chia cho các thành phần của tọa độ z, và như thế (x,y,w) và (x/w, y/w, 1) cùng biểu diễn 1 điểm. Điểm (x/w, y/w) là tọa độ Decac thuần nhất.
Ý tưởng của phương pháp là việc thể hiện một vector vị trí (x,y) bất kỳ trên mặt phẳng x,y bằng tập vô số các tọa độ điểm đồng nhất (hx hy h), thông thường láy h là 1.
- Tại sao người ta sử dụng toạ độ thuần nhất: Vì khi ta kết hợp 2 hay nhiều phép biến đổi Affine thì ma trận hợp của nhiều phép biến đổi được tính bằng cách nhân các ma trận của các phép biến đổi thành các phần.
Câu 10:
Hệ tọa độ tay trái là gì? Tại sao người ta sử dụng hệ tọa độ tay trái?
- Hệ tọa độ quy ước theo bàn tay trái là hệ tọa độ với các trục x, y, z thõa điều kiện :Nếu để bàn tay trái sao cho ngón cái hướng cùng chiều với trục z, khi nắm tay lại, chiều các ngón tay chuyển động theo hướng từ trục x đến trục y.

Hệ tọa độ quy ước theo bàn tay trái.

- Thông thường người ta hay sử dụng hệ tọa độ bàn tay phải, chiều dương là chiều ngược chiều kim đồng hồ, nhưng hệ tọa độ này không phù hợp trong đồ họa 3 chiều, vì khi giá trị tọa độ x tăng thì đối tượng lại được thể hiện càng gần người sử dụng, để khắc phục nhược điểm đó người ta sử dụng hệ tọa độ bàn tay trái, trong hệ tọa độ này chiều dương là chiều thuận với chiều kim đồng hồ.

Câu 11:
Hãy trình bày phép quay quanh trục song song với tọa độ và áp dụng để tính toạ độ mới của hình chữ nhật {(2,1,0);(3,1,0);(3,-1,0);(2,-1,0)} sau phép quay một góc 30o quanh trục x’//x đi qua (1,1,1).

B1 : Tịnh tiến điểm (1, 1, 1) ->(0, 0, 0) theo ma trận biến đổi :

T[-1 , -1, -1] =

B2 : Quay HCN quanh OX với góc quay

T(2) =

B3 : Ngược với B1 tịnh tiến từ gốc tọa độ  (1, 1, 1)

T = T[-1, -1, -1] x T[2] x T[1, 1, 1]

=

=

A’ : (2 1 0 1) x T =

 A’ =

B’ : (3 1 0 1) x T =
 B’ =

 C’ = ( )

 D’ = ( )