Bài giảng Đồ họa máy tính - Chương 9: Kỹ thuật lặp, đệ quy ứng dụng tạo hoa văn

ĐỒ 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 9: 
KỸ THUẬT LẶP, ĐỆ QUY ỨNG DỤNG TẠO HOA VĂN 
NỘI DUNG TRÌNH BÀY 
Giới thiệu 
FRACTAL VÀ TÍNH TỰ TƯƠNG TỰ 
Tính tự tương tự: giống nhau ở mọi tỷ lệ 
Tính tự tương tự chính xác: hình ảnh sau khi phóng to giống hệt hình ảnh ban đầu 
Tính tự tương tự thống kê: mức độ bất quy tắc và lượn sóng chỉ giống nhau ở mức độ trung bình 
Ví dụ: đường bờ biển khi nhìn từ trên cao, sau đó tiến lại gần 
Fractal: các hình thức khác nhau của sự tự tương tự 
Các đường cong có chiều dài vô tận có chiều nằm giữa 1 và 2 
FRACTAL VÀ TÍNH TỰ TƯƠNG TỰ 
Tinh chỉnh đường cong: đường cong Koch 
Tạo K n+1 từ K n bằng cách chia mỗi đoạn của K n thành 3 phần bằng nhau và thay đoạn giữa bằng một tam giác đều 
Chiều dài bằng (4/3) i 
K 1 
K 2 
FRACTAL VÀ TÍNH TỰ TƯƠNG TỰ 
Bông tuyết Koch 
Chu vi bằng 3(4/3) n  vô cùng 
Diện tích bằng (8/5)S 0 khi n  vô cùng 
FRACTAL VÀ TÍNH TỰ TƯƠNG TỰ 
Vẽ đường cong Koch 
Vẽ Kn: 
	if (n bằng 0) 
	Vẽ một đoạn thẳng; 
	else 
	{ 
	Vẽ Kn-1 
	Quay trái 60 0 
	Vẽ Kn-1 
	Quay phải 120 0 
	Vẽ Kn-1 
	Quay trái 60 0 
	} 
SINH CHUỖI VÀ TẠO ĐƯỜNG CONG PEANO 
Dùng chuỗi để điều khiển con rùa 
'F' có nghĩa là forward(L, l) (đi theo hướng hiện hành một 	khoảng L, có vẽ đoạn thẳng) 
'+' có nghĩa là turn(A) (quay phải một góc A độ) 
'-' có nghĩa là turn(-A) (quay trái một góc A độ) 
'F-F++F-F', với góc A bằng 60 0  vẽ Knoch bậc 1 
Từ chuỗi 'F-F++F-F‘ chuyển thành chuỗi phức tạp? 
dựa vào tập luật sinh 
'F'  "F-F++F-F" (luật của đường cong Koch) 
SINH CHUỖI VÀ TẠO ĐƯỜNG CONG PEANO 
Chuỗi ban đầu: F 
Thế hệ thứ nhất: S 1 = "F-F++F-F" 
Thế hệ thứ 2: S 2 = "F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F" 
for (each character ch in the input file) 
	if (ch == '+' || ch == '-') write it to the output file; 
	else if (ch == 'F') write "F-F++F-F" to the output file; 
for (each character ch in the input file) 
	if (ch == '+') turn(A); 
	else if (ch == '-') turn(-A); 
	else if (ch == 'F') forward(1, 1); 
SINH CHUỖI VÀ TẠO ĐƯỜNG CONG PEANO 
produce() 
produce() 
produce() 
a) Hai giai đoạn của quá trình sinh chuỗi 
b) Hệ thống hàm lặp 
F 
F 
S n- 1 
S n 
F-F++F-F 
F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F 
SINH CHUỖI VÀ TẠO ĐƯỜNG CONG PEANO 
Mở rộng ngôn ngữ 
'F'  'F' 
'X'  "X+YF+“  tập luật sinh đường cong con rồng 
'Y'  "-FX-Y" 
atom = "FX“ 
Bắt đầu với nguyên tử F X, chúng ta có 
S 1 = "FX+YF+" 
S 2 = "FX+YF++-FX-YF+" 
X, Y bỏ qua khi vẽ 
F, +, - vẫn được thông dịch như trước đây. 
SINH CHUỖI VÀ TẠO ĐƯỜNG CONG PEANO 
Sinh chuỗi đệ quy và thao tác vẽ 
void produceString(char *st, int order){ 
 for(;st ; st++) 
	 switch(*st) { 
	case '+': CD -= angle; break; 
	case '-': CD +=angle; break; 
	case 'F': if (order > 0) produceString(Fstr, order – 1); 
	 else forward(length, 1); 
	 break; 
	case 'X': if (order > 0) produceString(Xstr, order – 1); 
	 break; 
	case 'Y': if (order > 0) produceString(Ystr, order – 1); 
	 break;} } 
SINH CHUỖI VÀ TẠO ĐƯỜNG CONG PEANO 
Cho phép rẽ nhánh: 
'[' : saveTurtle()  lưu trạng thái hiện tại của con rùa 
']' : restoreTurtle()  khôi phục trạng thái của con rùa vế trạng thái trước đó. 
Trạng thái của con rùa = {CP, CD} 
thêm các lệnh sau vào produceString(): 
	 '[': saveTurtle();break;  đẩy trạng thái hiện hành của con rùa vào ngăn xếp. 
	 ']': restoreTurtle();break;  lấy trạng thái hiện hành từ đỉnh ngăn xếp. 
SỬ DỤNG HỆ HÀM LẶP TẠO HÌNH ẢNH 
Máy photocopy thực nghiệm 
Các hình ảnh ở đầu ra có hội tụ về hình ảnh nào không? 
a) 
b) 
đầu vào 
bản copy 
máy photocopy 
hình ảnh ban đầu I 0 
SỬ DỤNG HỆ HÀM LẶP TẠO HÌNH ẢNH 
Máy photocopy Sierpinski 
Hình ảnh hội tụ về tam giác Sierpinski và không phụ thuộc vào hình ảnh ban đầu 
Gồm 3 thấu kính mỗi thấu kính thực hiện ba phép biến đổi cho chữ F để nhận được 3 chữ F mới 
SỬ DỤNG HỆ HÀM LẶP TẠO HÌNH ẢNH 
Máy photocopy Sierpinski 
	- Các phép biến đổi là 
Để tiện lợi, chúng ta liệt kê các phần tử của ma trận dưới dạng danh sách 
T = { m 11 , m 12 , m 21 , m 22 , m 13 , m 23 }	 
SỬ DỤNG HỆ HÀM LẶP TẠO HÌNH ẢNH 
Lý thuyết của quá trình copy 
hình ảnh nhập I = tập các điểm màu đen = {( x , y ) sao cho ( x , y ) được tô màu đen} 
hình ảnh xuất = T 1( I )  T 2( I )  T 3( I ) 
tổng quát hóa W (.) = T 1(.)  T 2(.)  T 3(.) 
khi lặp đi lặp lại thao tác đưa hình ảnh xuất vào ngõ nhập thì quỹ đạo của I 0 , I 1 , I 2 ... sẽ hội tụ về một hình ảnh gọi là nhân tố hấp dẫn A 
W(A) = A 
A không phụ thuộc vào hình ảnh ban đầu 
SỬ DỤNG HỆ HÀM LẶP TẠO HÌNH ẢNH 
Thực hiện thao tác vẽ ở lần lặp thứ k 
I 0 là một đường gấp khúc 
I 0 là một điểm 
Ví dụ: vẽ lá cây dương xỉ 
T 1 = {0, 0, 0, .16, 0, 0}; 
T 2 = {.2, .23, -.26, .22, 0, 1.6};	 
T 3 = {-.15, .26, .28, .24, 0, .44}; 
T 4 = {.85, -.04, .04, .85, 0, 1.6}; 
SỬ DỤNG HỆ HÀM LẶP TẠO HÌNH ẢNH 
void superCopier(RealPolyArray pts, int k) 
{ 
	int	i, j; 
	RealPolyArray newpts; 
	if(k == 0)	drawPoints(pts); 
	else for(i = 1; i <= N; i++) 
	{ 
	newpts.num = N*pts.num; 
	for(j = 0; j < newpts.num; j++) 
	transform(affines[i],pts.pt[j], newpts.pt[j]); 
	superCopier(newpts, k-1); 
	} 
} 
SỬ DỤNG HỆ HÀM LẶP TẠO HÌNH ẢNH 
TẬP MANDELBROT 
TẬP MANDELBROT 
f ( z ) = z 2 + c 
với giá trị ban đầu s, ta có quỹ đạo 
d 1 = ( s ) 2 + c 
d 2 = (( s ) 2 + c ) 2 + c 
d 3 = ((( s ) 2 + c ) 2 + c ) 2 + c 	 
d 4 = (((( s ) 2 + c ) 2 + c ) 2 + c ) 2 + c 
(.) 2 + c 
d k 
s 
f (.) 
TẬP MANDELBROT 
s và c có thể là số phức 
quỹ đạo hội tụ và quỹ đạo phân kỳ 
điểm cố định của hệ thống thỏa mãn 
f(z) = z  z 2 + c = z 
điểm cố định hấp dẫn, điểm cố định đẩy 
TẬP MANDELBROT 
Định nghĩa: 
với s luôn bằng 0 
điểm c nằm trong M nếu quỹ đạo của 0 hội tụ 
điểm c nằm ngoài M nếu quỹ đạo của 0 phân kỳ 
TẬP MANDELBROT 
c có nằm trong tập M hay không? 
	d k vượt qua giá trị 2 thì quỹ đạo phân kỳ 
	thời gian để d k vượt qua giá trị 2 được gọi là thời gian cư trú 
	c nằm trong M có thời gian cư trú rất lớn (Cận trên là Num) 
int dwell(double cx, double cy){ 
 #define Num 100 
double tmp, dx = cx, dy = cy, fsq = cx * cx + cy * cy; 
for(int count = 0; count <= Num && fsq <= 4; count++) 
{ 
	tmp = dx; 
	dx = dx * dx - dy * dy + cx; 
	dy = 2.0 * tmp * dy + cy; 
	fsq = dx * dx + dy * dy; 
} 
return count; } 
( x + yi ) 2 = ( x 2 – y 2 ) + (2 xy ) i , 
TẬP MANDELBROT 
Xác định màu cho điểm c 
c nằm trong M: tô bằng màu đen 
c nằm ngoài M: float	v = d/(float) Num; 
	 glColor3f(v*v, v*v, 0.2); 
d 
cường độ màu 
1 
Num 
đen 
xanh 
đỏ, vàng 
TẬP MANDELBROT 
Xác định sự tương ứng giữa pixel trên màn hình với số phức c 
cửa sổ 
TẬP MANDELBROT 
for( j = 0; j < rows; j++) 
	for(i = 0; i < cols; i++) 
	{ 
	 tìm số phức c tương ứng với pixel ở vị trí i, j 
	xác định thời gian cư trú của quỹ đạo 
	dựa trên thời gian cư trú xác định màu sắc tương ứng 
	setPixel(i, j, color); 
	} 
TẬP JULIA 
cho c cố định, khảo sát các giá trị khác nhau của s 
Tập Julia đầy đủ: là tập hợp tất cả các điểm khởi đầu s có quỹ đạo hội tụ. 
vẽ tập Julia 
	 for( j = 0; j < rows; j++) 
	for(i = 0; i < cols; i++){ 
	 tìm số phức s tương ứng với pixel ở vị trí i, j 
	xác định thời gian cư trú của quỹ đạo 
	dựa trên thời gian cư trú xác định màu sắc tương ứng 
	 setPixel(i, j, color); } 
phải truyền cả s và c cho hàm dwell() 
TẬP JULIA 
Tập Julia J c : là đường biên của tập Julia đầy đủ K c 
Tiền ảnh của z: 
 Các tiền ảnh của z có quỹ đạo giống như quỹ đạo của z 
a) 
b) 
tiền ảnh của s 
TẬP JULIA 
Vẽ tập Julia 
do{ 
	 if(coin flip is head) 
	 else 	 
	 draw dot at z; 
	}while (not bored); 
Tính căn bậc hai của z = x + iy 
 , y>= 0 
 , y < 0