Bài giảng Đồ họa máy tính - Chương 4: Vector trong đồ họa máy tính

ĐỒ HỌA MÁY TÍNH 
Trường Đại Học Bách Khoa TP Hồ Chí Minh 
Khoa Khoa học & Kỹ thuật Máy tính 
CHƯƠNG 4: 
VECTOR TRONG ĐỒ HỌA MÁY TÍNH 
NỘI DUNG TRÌNH BÀY 
Giới thiệu 
Ôn tập kiến thức về vector 
Tích vô hướng 
Tích có hướng 
Biểu diễn đối tượng hình học 
Giao của hai đoạn thẳng 
Đường tròn đi qua ba điểm 
Giao của đường thẳng và mặt phẳng 
Bài toán liên quan đến đa giác 
GIỚI THIỆU 
Tại sao vector lại quan trọng trong đồ họa máy tính 
GIỚI THIỆU 
Hệ trục tọa độ 
Hệ trục tọa độ bàn tay phải ( dùng trong toán học v.v ) 
Hệ trục tọa độ bàn tay trái ( trong đồ họa ) 
Đơn vị của trục tọa độ không quan trọng 
ÔN TẬP KIẾN THỨC VỀ VECTOR 
Định nghĩa : 
 Vector là đại lượng có độ dài và hướng . Nó thường được dùng để biểu diễn các đại lượng vật lý như lực , vận tốc . 
Lưu ý: 
Điểm đặt của vector không quan trọng 
Vector vị trí 
ÔN TẬP KIẾN THỨC VỀ VECTOR 
a = (2, 5, 6), b = (-2, 7, 1) 
Phép cộng : a + b = (0, 12, 7) 
Phép nhân tỷ lệ: 6 a = (12, 30, 39) 
Phép trừ : a - b = a + (- b ) = (4, -2, 5) 
ÔN TẬP KIẾN THỨC VỀ VECTOR 
ÔN TẬP KIẾN THỨC VỀ VECTOR 
Tổ hợp tuyến tính của m vector v 1 ,v 2 ,, v m là vector 
 w = a 1 v 1 + a 2 v 2 +  + a m v m 
 ( với a 1 , a 2 ,  ,a m là các đại lượng vô hướng ) 
Tổ hợp affine là tổ hợp tuyến tính với 
 a 1 + a 2 +  +a m = 1 
Tổ hợp lồi là tổ hợp tuyến tính với 
 a 1 + a 2 +  +a m = 1 và 
	 a j >=0, với i=1,,m 
Độ lớn của vector: 
Vector đơn vị : 
TÍCH VÔ HƯỚNG 
Định nghĩa : Tích vô hướng d của hai vector n chiều v = ( v 1 , v 2 , ..., v n ) và w = ( w 1 , w 2 , ..., w n ) và được ký hiệu là v  w và có giá trị 	 
Tính chất : 
Tính đối xứng (symmetry): a  b = b  a 
Tính tuyến tính (linearity): ( a + c )  b = a  b + c  b 
Tính đồng nhất (homogeneity): ( s a )  b = s ( a  b ) 
| b | 2 = b  b 
TÍCH VÔ HƯỚNG 
Góc giữa hai vector: 
 b  c = | b || c | cos(  ) 
TÍCH VÔ HƯỚNG 
Vector vuông góc với vector 2 chiều 
 Cho a = ( ax , ay ). Thì a  = (- ay , ax ) là vector vuông góc ngược chiều kim đồng hồ với a . Vector này thường được gọi là vector "perp" (viết tắt của perpendicular). 
TÍCH VÔ HƯỚNG 
Phép chiếu trực giao và khoảng cách từ một điểm đến đt 
c = K v + M v  (cần xác định K và M ) 	 
c  v = K v  v + M v   v  
TÍCH VÔ HƯỚNG 
Tìm tia phản xạ 
r = e – m , e = a - m  r = a - 2 m 
r = a - 2( a  u n ) u n 
TÍCH CÓ HƯỚNG 
Tích có hướng của hai vector là một vector 
Tích có hướng chỉ được định nghĩa cho vector 3 chiều 
Cho hai vector 3 chiều a = ( a x , a y , a z ) và b = ( b x , b y , b z ), thì tích có hướng của chúng như sau 
 a  b = ( a y b z – a z b y ) i + ( a z b x – a x b z ) j + ( a x b y – a y b x ) k 
 | a  b | = | a || b |sin(  ) 
BIỂU DIỄN ĐỐI TƯỢNG HÌNH HỌC 
Hệ tọa độ và khung tọa độ 
(3, 2, 7) là điểm hay là vector? 
Khung tọa độ : gốc  và 3 trục a , b , c 
Biểu diễn vector v bằng cách tìm (v 1 , v 2 , v 3 ) sao cho 
 v = v 1 a + v 2 b + v 3 c 
Biểu diễn điểm 
 P -  = p 1 a + p 2 b + p 3 c 
 P =  + p 1 a + p 2 b + p 3 c 
BIỂU DIỄN ĐỐI TƯỢNG HÌNH HỌC 
Biểu diễn đồng nhất 
Hệ tọa độ thông thường  hệ tọa độ đồng nhất 
	 điểm : thêm 1; vector : thêm 0 
Hệ tọa độ đồng nhất  hệ tọa độ thông thường 
 điểm : xóa 1; vector : xóa 0. 
BIỂU DIỄN ĐỐI TƯỢNG HÌNH HỌC 
Điểm – điểm = vector;( x , y , z , 1) - ( u , v , w , 1) = ( x - u , y - v , z - w , 0). 
Điểm + vector = điểm; ( x , y , z , 1) + ( d , e , f , 0) = ( x + d , y + e , z + f , 1) . 
Vector + vector = vector ; ( d , e , f , 0) + ( m , n , r , 0) = ( d + m , e + n , f + r , 0) 
Đại lượng vô hướng x Vector = Vector; 3( d , e , f , 0) = (3 d , 3 e , 3 f , 0) 
Tổ hợp tuyến tính của vector là vector; v = ( v 1, v 2, v 3, 0) và w = ( w 1, w 2, w 3, 0) , a , b là hai đại lượng vô hướng thì a v + b w = ( av1 + bw1 , av2 + bw2 , av3 + bw3 , 0) 
BIỂU DIỄN ĐỐI TƯỢNG HÌNH HỌC 
Tổ hợp affine các điểm : là một điểm . P = ( P 1, P 2, P 3, 1) và R = ( R 1, R 2, R 3, 1), gọi f và g là hai giá trị vô hướng: 
	 fP + gR = ( fP 1 + gR 1, fP 2 + gR 2, fP 3 + gR 3, f + g ) . 
Điểm cộng vector là tổ hợp affine các điểm 
P = A + t ( B - A ) 
P = tB + (1 - t ) A 
Tổ hợp tuyến tính phụ 
 thuộc hệ tọa độ 
BIỂU DIỄN ĐỐI TƯỢNG HÌNH HỌC 
Nội suy tuyến tính hai điểm : P = A (1 - t ) + Bt 
float lerp(float a, float b, float t) 
 { return a + (b - a) * t; } 
Point2 Canvas::Tween(Point2 A, Point2 B, float t) 
Sử dụng tweening trong nghệ thuật, hoạt hình 
P i ( t ) = (1 - t ) A i + tB i . 
BIỂU DIỄN ĐỐI TƯỢNG HÌNH HỌC 
Nội suy bậc 2, bậc 3 
P ( t ) = (1 - t ) 2 A + 2(1 - t ) tB + t 2 C 1 = ((1 – t) + t) 2 
BIỂU DIỄN ĐỐI TƯỢNG HÌNH HỌC 
Biểu diễn đường thẳng : đoạn thẳng , tia , đường thẳng 
Biểu diễn tham số 
L ( t ) = C + b t 
Đoạn thẳng, 0  t  1 
Tia, 0  t   	 
Đường thẳng, -   t   	 
BIỂU DIỄN ĐỐI TƯỢNG HÌNH HỌC 
Dạng biểu diễn điểm pháp tuyến : n  ( R - C ) = 0 
Chuyển đổi giữa 
những cách biểu diễn 
khác nhau 
BIỂU DIỄN ĐỐI TƯỢNG HÌNH HỌC 
Biểu diễn mặt phẳng 
 dưới dạng tham số : 
 P ( s , t ) = C + s a + t b 
Chuyển đổi giữa 
những cách biểu diễn 
khác nhau 
BIỂU DIỄN ĐỐI TƯỢNG HÌNH HỌC 
Mảnh phẳng : P ( s , t ) = C + a s + b t 
	P (0, 0) = C;	 P (1, 0) = C + a 	 
	P (0, 1) = C + b 	 P (1, 1) = C + a + b 
GIAO ĐIỂM CỦA 2 ĐOẠN THẲNG 
AB ( t ) = A + b t ; CD ( u ) = C + d u 
Giao điểm : tìm t và u sao cho A + b t = C + d u 
b t = c + d u với c = C - A 
d   b t = d   c 
d   b  0 . 
d   b = 0 
ĐƯỜNG TRÒN ĐI QUA 3 ĐIỂM 
Đường trung trực 
Đặt a = B - A ; b = C - B ; c = A - C ; 
Trung trực của AB; A + a /2 + a  t ; của CD; A - c /2 + c  u 
a  t = b /2 + c  u  
GIAO CỦA ĐƯỜNG THẲNG VÀ MẶT PHẲNG 
n  ( A + c t hit - B ) = 0  n  ( A - B ) + n  c t hit = 0 
điểm cắt P hit = A + c t hit 
GIAO CỦA ĐƯỜNG THẲNG VÀ MẶT PHẲNG 
n  c > 0, tia đi "dọc theo" hướng pháp tuyến của đường thẳng 
n  c = 0, tia song song với đường thẳng	 
n  c < 0, tia đi "ngược với" hướng pháp tuyến của đường thẳng 
BÀI TOÁN LIÊN QUAN ĐẾN ĐA GIÁC 
Định nghĩa đa giác và đa diện 
Các bài toán liên quan 
Điểm P cho trước nằm trong hay nằm ngoài đa giác (hoặc khối đa diện) 
Giao điểm đầu tiên tia R với đa giác (hoặc khối đa diện) 
Phần nào của đường thẳng L sẽ nằm trong đa giác (hoặc khối đa diện), phần nào nằm ngoài. 
BÀI TOÁN LIÊN QUAN ĐẾN ĐA GIÁC 
Bài toán tìm giao điểm 
Đa giác ( đa diện ) lồi được mô tả bởi các đường thẳng ( mặt phẳng ) bao  tìm giao điểm với đường thẳng chẳng qua tìm giao điểm của đường thẳng với tập các đường thẳng ( mặt phẳng ) bao 
BÀI TOÁN LIÊN QUAN ĐẾN ĐA GIÁC 
Tìm giao điểm của tia với đa giác 
Điểm cắt vào = A + c t in ; 
Điểm cắt ra = A + c t out ; 
Nằm trong đa giác[ t in , t out ]. 
Cắt xén tia 
A ' = A + c max(0, t in ) C ' = A + c min(1, t out ) 
BÀI TOÁN LIÊN QUAN ĐẾN ĐA GIÁC 
Xác định tia đi vào hay đi ra khỏi đa giác 
Nếu n  c > 0, tia đi ra khỏi P 
Nếu n  c = 0, tia song song với đường thẳng 
Nếu n  c < 0, tia đi vào P 	 
Với mỗi đường bao, chúng ta sẽ phải xác định: 
	- Thời gian cắt của tia với đường bao. 
 - Tia đi vào hay đi ra khỏi đa giác ở đường bao. 
BÀI TOÁN LIÊN QUAN ĐẾN ĐA GIÁC 
Gọi đoạn [ t in , t out ] là đoạn dự tuyển 
Khởi gán giá trị ban đầu [0, 1] cho đoạn dự tuyển 
Với mỗi đường bao, xác định t hit và xác định tia đi vào hay đi ra khỏi đa giác: 
Nếu tia đi vào đa giác, thì t in = max( t in , t hit ). 
Nếu tia đi ra khỏi đa giác, thì t out = min( t out , t hit ). 
Nếu tin > tout thì tia không cắt đa giác, và chương trình kết thúc. 
Nếu đoạn dự tuyển không trống, thì đoạn thẳng từ A + c t in đến A + c t out nằm trong P .