Giáo trình Đồ họa máy tính (60 tiết)

vẽ đoạn thẳng Trong hình vẽ (xi+1,y) là điểm thuộc đoạn thẳng thực, ta có: y = m(xi+1) + b. Giả sử ở bước i ta đã xác định được điểm (xi,yi). Đặt d1 = y – y1 ; d2 = (yi +1) - y ; Việc chọn điểm tiếp theo (xi+1, yi+1) là S hay P tùy thuộc vào việc d1 lớn hơn hay nhỏ hơn d2, nói cách khác là phụ thuộc vào dấu của (d1 – d2) • Nếu d1 – d2 <0, ta sẽ chọn S, tức là yi+1 = yi • Trường hợp còn lại: d1 – d2 >0, ta sẽ chọn P, tức là yi+1 = yi+1 Đặt pi = dx (d1 – d2). Thay d1 = y – y1 ; d2 = (yi +1) – y vào ta có pi = dx (2y - 2yi -1) Thay y = mxi+b = dy(xi+1)/dx + b vào ta có pi = 2dx [dy(xi+1)/dx +b] – 2yidx –dx = 2xidy – 2yidx +C với C = 2dy + (2b-1)dx là hằng số. Ta 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ì sẽ xác định được điểm cần tô ở bước i+1. Làm sao để tính giá trị của pi ? ta dùng phương pháp “lũy tiến” như sau. Ta có: pi+1 –pi = (2xi+1dy – 2yi+1dx +C) - (2xidy – 2yidx +C) = 2dy -2dx(yi+1 – yi) • Nếu pi<0 thì điểm được chọn là S, tức là yi+1 = yi ⇒ pi+1 = pi +2dy • Nếu pi>0 thì điểm được chọn là P, tức là yi+1 = yi+1 ⇒ pi+1 = pi +2dy -2dx Cuối cùng, giá trị p0 được tính từ điểm ảnh đầu tiên (x0, y0) theo công thức sau p0 = 2x0dy – 2y0dx + c Thay giá trị của c vào, chú ý rằng điểm đầu (x0, y0) cũng thuộc đoạn thẳng thực nên y0 = mx0 + b = x0dy/dx + b, suy ra p0 = 2dy -dx tóm lại là: xi+1 S (xi+1,y) Pyi+1 d2 y d1 yi xi 35 ... y0 ... y1 p1 y2 p2 p0 Ví dụ: Cho A(12,20) và B(22,27), ta có dx = 22 – 12 = 10 ; dy = 27 – 20 = 7; c1 = 2dy = 14 ; c2 = 2(dy-dx) = -6; p0 = 2Dy – dx = 4 i xi yi pi 0 12 20 4 1 13 21 -2 2 14 21 12 3 15 22 6 4 16 23 0 5 17 24 -6 6 18 24 8 7 19 25 2 8 20 26 -4 9 21 26 10 10 22 27 4 36 Thuật toán Bresenham vẽ đoạn thẳng { Vẽ đoạn thẳng trong trường hợp 00} uses crt,graph; var gd,gm:integer; i,x1,y1,x2,y2,dx,dy,p,c1,c2,x,y:integer; Begin gd:=detect; initgraph(gd,gm,''); Randomize; Repeat x1:=random(GetMaxX); x2:=x1+random(GetMaxX-x1); y1:=random(GetMaxY); y2:=y1+random(x2-x1); {vẽ đoạn thẳng (x1,y1) (x2,y2) } Lưu đồ thuật toán Bresenham x < x2 ? p:=2dy - dx ; c1=2dy; c2=2(dy-dx); x:=x1; y:=y1 ; putpixel(x,y); Yes No End No p < 0 ? Yes p:=p+c1; p:=p + c2; y:=y+1; x:=x+1; PutPixel(x,y); Begin 37 dx:=x2-x1; dy:=y2-y1; p:=2*dy - dx; c1:=2*dy; c2:=2*(dy-dx); x:=x1; y:=y1; putpixel(x,y,white); for i:=x1 to x2 do begin if p<0 then p:=p+c1 else begin p:=p+c2; y:=y+1; end; x:=x+1; putpixel(x,y,white); end; delay(1000); Until Keypressed; closegraph; End. 3. Thuật toán MidPoint vẽ đoạn thẳng O: điểm giữa Pyi+1 S yi xi xi+1 Thuật toán này thực chất là 1 cách diễn giải khác của thuật toán Bresenham. Ta lựa chọn yi+1 là yi hay yi+1 bằng cách so sánh trung điểm của O của PS với đường thẳng thực • Nếu O nằm phía dưới đường thẳng, ta chọn P • Nếu O nằm phía trên, ta chọn S Phương trình đường thẳng thực: Ax + By + C = 0 với A = y2 – y1; B = x1 – x2; C = x2y1 – x1y2 ; Đặt F(x,y) = Ax + By + C, ta biết rằng • F(x,y) <0 nếu điểm (x,y) nằm phía trên đường thẳng • F(x,y) =0 nếu điểm (x,y) thuộc đường thẳng • F(x,y) >0 nếu điểm (x,y) nằm phía dưới đường thẳng vì vậy, vấn đề quy về việc xét dấu của pi = 2F(O) = 2F(xi +1,yi +1/2) • Nếu pi <0 tức là O nằm phía trên đường thẳng ⇒ ta chọn S 38 • Nếu pi >0 tức là O nằm phía dưới đường thẳng ⇒ ta chọn P Làm sao để tính pi ? tương tự như thuật toán Bresenham, ta cũng dùng phương pháp “lũy tiến”, dùng giá trị ở bước trước pi để tính giá trị ở bước tiếp theo pi+1 Ta có: pi+1 – pi =2F(xi+1 +1,yi+1 +1/2) - 2F(xi +1,yi +1/2) = 2[A(xi+1+1)+B(yi+1+1/2)+C] - 2[A(xi+1)+B(yi+1/2)+C] = 2dy – 2dx(yi+1 – yi) Như vậy • Nếu pi <0 thì ta chọn yi+1 = yi , do đó pi+1 = pi +2dy • Nếu pi >0 thì ta chọn yi+1 = yi+1 , do đó pi+1 = pi +2dy – 2dx Cuối cùng, giá trị đầu p0 được tính như sau: nhận xét rằng điểm đầu (x0, y0) thuộc đoạn thẳng thực tức là Ax0 + By0 +C = 0 p0 = 2F(x0+1,y0+1/2) = 2[A(x0+1)+B(y0+1/2)+C] = 2(Ax0 + By0 +C) + 2A +B = 2A+B = 2dy –dx II Vẽ đường tròn Thuật toán MidPoint B (-x, y) (-y, x) (-y, -x) (-x, -y) (x, -y) (y, -x) (y,x) (x,y) A Đầu tiên ta nhận xét rằng, do tính đối xứng của đường tròn nên ta chỉ cần vẽ được cung AB là cung 1/8 đường tròn, sau đó lấy đối xứng qua các trục và các đường phân giác ta sẽ có cả đường tròn. Chẳng hạn như ở hình vẽ trên nếu xác định được điểm (x,y), lấy đối xứng qua đường phân giác của góc phần tư thứ nhất ta thu được điểm (y,x), lấy đối xứng qua trục hoành ta thu được 2 điểm (y,-x) và (x,-y) ... Nếu ta chia thành 16,32 ... phần thì việc xác định tọa độ 15,31... điểm đối xứng còn lại sẽ rất khó. Còn nếu chia thành 4 hay 2 phần thì số điểm lân cận cần phải loại trừ có thể nhiều hơn 2 điểm. 39 P S M: điểm giữa Q(xi+1,y) xi xi+1 yi yi-1 Gọi R là bán kính đường tròn, ta xuất phát từ điểm A (0,R) để vẽ cung AB. Nhìn hình vẽ ta thấy, nếu (xi, yi) là điểm ảnh đã vẽ được ở bước thứ i thì điểm ảnh (xi+1, yi+1) ở bước tiếp theo chỉ có thể là S hoặc P, tức là • xi+1 = xi + 1 • yi+1 ∈ {yi, yi-1} Giống như thuật toán vẽ đoạn thẳng, ý tưởng chính để lựa chọn giữa S và P ở đây là căn cứ vào vị trí tương đối của điểm giữa M của SP với đường tròn. Nếu M nằm bên trong đường tròn như hình vẽ thì ta sẽ chọn S vì nó gần điểm thực Q hơn so với P. Ngược lại nếu M nằm ngoài đường tròn thì P sẽ được chọn. Đặt F(x,y) = x2 + y2 – R2 , các định lý toán học cho ta biết rằng • 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 Đặt pi = F(M) = F(xi+1,yi – ½) ta có • Nếu pi<0 tức là M nằm trong đường tròn, ta sẽ chọn S, tức là yi+1 = yi • Nếu pi≥0 ta sẽ chọn P, tức là yi+1 = yi -1 Cách tính giá trị của pi cũng tương tự như ở thuật toán vẽ đoạn thẳng. Ta có: pi+1 – pi = F[xi+1+1,yi+1 – ½] - F[(xi+1,yi – ½)] = [(xi+1+1)2 +(yi+1 – ½)2 - R2] - [(xi+1)2 +(yi – ½)2 - R2] = 2xi +3+(yi+12 – yi2) – (yi+1 - yi) Do đó • Nếu pi <0 ta chọn yi+1 = yi ⇒ pi+1 = pi + 2xi +3 • Nếu pi ≥0 ta chọn yi+1 = yi-1 ⇒ pi+1 = pi + 2xi -2yi +5 Cuối cùng ta tính giá trị đầu p0 ứng với điểm A(0,R) p0=F(x0+1,y0-1/2) = F(0,R-1/2) = 5/4 -R 40 Thuật toán MidPoint vẽ đường tròn Uses crt,graph; Var gd,gm,x,y,R,p,mau:integer; Procedure PutPixel8(x,y,c:integer); Begin putPixel(x,y,c); putPixel(y,x,c); putPixel(y,-x,c); putPixel(x,-y,c); putPixel(-x,-y,c); putPixel(-y,-x,c); putPixel(-y,x,c); putPixel(-x,y,c); End; Begin gd:=detect; initgraph(gd,gm,''); SetViewPort(GetMaxX div 2, GetMaxY div 2, GetMaxX,GetMaxY,false); Randomize; R :=100 + random(200); Lưu đồ thuật toán MidPoint vẽ đường tròn x < y ? p:=5/4 -R; x:=0; y:=R ; PutPixel8(x,y); Yes No End No p < 0 ? Yes p:=p+2x+3; p:=p+2(x-y); y:=y-1; x:=x+1; PutPixel(x,y); Begin 41 mau:=random(GetMaxColor); {Vẽ đường tròn MidPoint màu ngẫu nhiên } x:=0; y:=R; PutPixel8(x,y,mau); p:=1-R; while (x<y) do begin if p<0 then p:=p+2*x+3 else begin p:=p+2*(x-y)+5; y:=y-1; end; x:=x+1; PutPixel8(x,y,mau); end; readkey; End. VTại sao phải so sánh pi với 0 trong các thuật toán trên ? bản chất việc so sánh này là gì ? VTrong thuật toán MidPoint, tại sao phải nhân F() với 2 khi gán cho pi trong công thức pi = 2. F() VHãy so sánh thuật toán vẽ đoạn thẳng DDA với 2 thuật toán còn lai về mặt tốc độ thực hiện ? (Gợi ý: 2 thuật toán kia cải thiện đáng kể số phép tính cần thực hiện, vì sao? ) VVì sao nói thuật toán vẽ đoạn thẳng MidPoint chẳng qua là 1 cách diễn giải khác của thuật toán Bresenham ? VTrong thuật toán vẽ đường tròn MidPoint, vì sao không chia đường tròn thành nhiều hơn hoặc ít hơn 8 phần ? VTrong chương trình minh họa thuật toán vẽ đường tròn MidPoint, tại sao không để như lý thuyết là: p0 := 5/4 –R mà sửa thành p0:= 1- R ? III Cắt xén (Clipping) 1. Thuật toán Cohen-Sutherland Bài toán: giả thiết rằng cửa sổ hiển thị là một hình chữ nhật với các cạnh song song với các trục tọa độ như hình vẽ. Cho một đoạn thẳng bất kỳ, hãy xác định phần nào của nó nằm trong cửa sổ (tức là được hiển thị), phần nào nằm ngoài (bị che khuất). 42 F J 0110 0010 10101001 0001 0101 0100 0000 1000 L E D C B I J’ I’ A K K’ ymax ymin xmin xmax Cách làm: đầu tiên ta nhận xét rằng một điểm P(x,y) nằm trong cửa sổ (được nhìn thấy) khi và chỉ khi thỏa mãn đồng thời 2 điều kiện xmax ≥ x ≥ xmin ymax ≥ y ≥ ymin Ngược lại, nếu một trong 2 điều kiện bị vi phạm thì P nằm ngoài cửa sổ và sẽ không được hiển thị. Các đoạn thẳng chỉ có thể thuộc một trong những trường hợp sau: • Hoàn toàn nằm trong cửa sổ, ví dụ như AB, khi đó cả 2 đầu mút đều nằm bên trong cửa sổ • Hoàn toàn nằm ngoài cửa sổ (bị che toàn phần), ví dụ như CD, EF • Chỉ một phần nằm trong cửa sổ và được hiển thị, ví dụ như KL và IJ Đầu tiên, thuật toán Cohen – Sutherland dùng 4 đường thẳng chứa cạnh cửa sổ chia mặt phẳng thành 9 phần. Mỗi điểm A(x,y) thuộc mặt phẳng sẽ được gán mã 4 bit abcd theo cách sau: • a=1 ⇔ y > ymax : A nằm phía trên cửa sổ • b=1 ⇔ y < ymin : A nằm phía dưới cửa sổ • c=1 ⇔ x > xmax : A nằm phía phải cửa sổ • d=1 ⇔ x < xmin : A nằm phía trái cửa sổ Khi đó, ta nhận xét rằng: • đoạn thẳng sẽ hoàn toàn nằm trong cửa sổ nếu cả 2 đầu mút đều bằng 0000 • đoạn thẳng sẽ hoàn toàn nằm ngoài cửa sổ nếu kết quả phép AND của 2 đầu mút khác 0000 Thực vậy, nhận xét đầu là hiển nhiên. Để minh họa cho nhận xét 2, xét đoạn thẳng EF: E = 1010, F = 0010 ⇒ (E) AND (F) = (1010) and (0010) = 0010 ≠ 0 bit thứ 3 của cả 2 đầu mút E và F đều bằng 1, chứng tỏ chúng đều nằm bên phải cửa sổ, do đó cả đoạn thẳng dĩ nhiên cũng nằm bên phải cửa sổ và sẽ không được hiển thị. Vấn đề còn lại là, nếu kết quả phép AND hai đầu mút bằng 0000, khi đó thuật toán sẽ tìm giao của đoạn thẳng với các biên của cửa sổ và xét từng phần của nó. Ta ký hiệu 4 đường thẳng chứa cạnh cửa sổ là: 43 • đường 1: y = ymax • đường 2: y = ymin • đường 3: x = xmax • đường 4: x = xmin Khi đó nhìn vào mã của 2 đầu mút ta sẽ biết ngay đoạn thẳng đó cắt cạnh nào của cửa sổ. Ví dụ: 0010 0001 4 3 J K’ L KJ’ I’ I 0100 2 1 ymax ymin xmin xmax Xét đoạn IJ • Mã của I = 0100, bít thứ 2 =1 nên chắc chắn nó sẽ cắt đường 2 • Mã của J = 0001, bít thứ 4 =1 nên chắc chắn nó sẽ cắt đường 4 Xét đoạn KL • Mã của L = 0100, bít thứ 3 =1 nên chắc chắn nó sẽ cắt đường 3 Việc xác định tọa độ giao điểm là rất đơn giản vì ta đã biết rõ 2 đầu mút. Sau khi chia đoạn thẳng thành các đoạn, ta lặp lại thuật toán với mỗi đoạn chia cho đến khi kết thúc. Ví dụ ta xét đoạn IJ • Bước 1: kết quả phép and bằng 0 nhưng 2 đầu mút khác 0: tìm giao điểm với biên I’ • Bước 2: loại đoạn II’ • Bước 3: xét đoạn JI’ : tìm giao điểm J’ • Bước 4: loại đoạn JJ’. Kết thúc với đoạn I’J’ được hiển thị 2. Thuật toán Sutherland - Hodgman Bài toán: ta cần cắt 1 đa giác bất kỳ Y vào trong cửa sổ là một đa giác lồi X. Cách làm: Ta sẽ duyệt lần lượt các cạnh của X, với mỗi cạnh đó ta lại xét lần lượt cạnh của Y. Kết quả sau khi xén với cạnh thứ i (của cửa sổ X) sẽ được dùng để xén với cạnh tiếp theo i+1 của X. Quy tắc là: 44 • nếu cạnh đang xét của Y đi từ trong cửa sổ ra ngoài (Pi-1 ở trong, Pi ở ngoài) thì chỉ giữ lại giao điểm I của Pi-1 Pi với cạnh đang xét của X. • nếu cạnh đang xét đi từ ngoài vào trong (tức là Pi-1 ở ngoài, Pi ở trong): giữ lại giao điểm I và Pi • trường hợp cạnh ở ngoài hoàn toàn: loại bỏ • trường hợp cạnh ở trong hoàn toàn: giữ lại Pi . Ví dụ Đầu tiên ta xét cạnh UV của cửa sổ cắt là tam giác UVT. Cạnh đang xét (theo chiều vecto) Hướng đi Quyết định giữ lại AB (xét với UV) Từ ngoài vào trong P,B BC (xét với VT) Trong ra ngoài Q CD Ngoài vào trong R,D DE Hoàn toàn nằm trong E EK (xét với TU) Trong ra ngoài M KF Hoàn toàn nằm ngoài Loại hết FG Ngoài vào trong I,G GH (xét với UV) Trong ra ngoài J HA Hoàn toàn nằm ngoài Loại hết Ta thu được đa giác (theo thứ tự): P,B,Q,R,D,E,M,I,G,J như hình vẽ Đoạn mã giả (pseudocode) sau minh họa cho thuật toán trên. t:=1 for i:=1 to n do {Đa giác cửa sổ X có n cạnh} for j:=1 to m do {Đa giác bị cắt Y có m cạnh } k:=j+1; {Xét cạnh XjXj+1 của đa giác cửa sổ X} if k>n then k:=1 ; if (Xj ở trong) then V C R D A B P Q H K F G J E I U T M 45 begin if (Xk ở trong) then Yt := Yk else Yt := giao điểm của XjXk với cạnh i của X t:=t+1; end else if (Xk ở trong ) then begin Yt := giao điểm; t:=t+1; Yt := Xk ; t:=t+1; end; Vấn đề: cho tọa độ 1 điểm, làm sao biết điểm đó ở trong/ngoài đa giác lồi X ? Bổ đề: nếu điểm đó nằm bên phải 1 cạnh nào đó của đa giác lồi X theo chiều dương thì nó nằm ngoài X. Nếu nó nằm bên trái tất cả các cạnh thì nó nằm bên trong X B(x2,y2) chiều dương bên trái bên phải P(x,y) A(x1,y1) Bổ đề: cho vector AB và điểm P(x,y), P nằm bên trái vector AB (như hình vẽ) nếu và chỉ nếu (x2 – x1)(y – y1) – (y2 – y1)(x – x1) >0 Ta công nhận, không chứng minh bổ đề toán này. Vấn đề: cho tọa độ tập đỉnh của đa giác lồi X dưới dạng 1 danh sách có thứ tự (nghĩa là nếu biết 1 đỉnh thì ta luôn biết 2 đỉnh kề của nó), làm sao xếp chúng lại “theo chiều dương” ? Cách làm: Chọn đỉnh có hoành độ nhỏ nhất, ký hiệu là A như hình vẽ. Gọi 2 đỉnh kề nó là B,C trong đó xB < xC. Thứ tự theo chiều dương sẽ là BAC. Sau đó ta chỉ việc đi tới đỉnh tiếp theo C ... Thật vậy, ta có thể thấy rõ khi nhìn hình vẽ. Chỉ có 3 trường hợp: • B,C nằm ở 2 phía của đường thẳng x = xA • B,C cùng nằm bên phải đường thẳng đó • B,C cùng nằm bên trái 46 C B A C B C A B A 2. Clipping một đoạn thẳng vào đường tròn B O A d B O A d D C (b)(a) (c) A B Gọi d là khoảng cách từ tâm O tới đoạn thẳng AB. • Nếu d > bán kính r ⇒ clip(AB) = ∅ • Nếu d = bán kính r ⇒ clip(AB) = {điểm tiếp xúc} • Nếu d < bán kính r, ta chia thành 3 trường hợp o Cả A,B đều nằm trong đường tròn: clip(AB) = AB o Một trong hai điểm (giả sử là A) nằm ngoài đường tròn. Gọi C là giao của AB với đường tròn ta có clip(AB) = BC o Cả 2 cùng nằm ngoài đường tròn, xét dấu: ƒ Nếu (xA-xC) (xB-xC) <0 thì clip(AB)=CD (trường hợp (c)) ƒ Nếu (xA-xC) (xB-xC) >0 thì clip(AB)=∅ (trường hợp (b)) IV. Tô màu vùng khép kín Cho một vùng khép kín được giới hạn bởi một đường biên đồng màu. Vấn đề đặt ra là tô màu cho miền trong của vùng đó. Có 2 phương pháp chính: tô theo dòng quét (scan line fill) và tô dựa theo đường biên (boundary fill). 1. Thuật toán tô màu theo đường biên (Boundary algorithm) Cách tô này yêu cầu phải biết trước tọa độ một điểm (điểm “gieo”) nằm bên trong vùng cần tô. Bắt đầu từ điểm đó ta sẽ tô “loang” dần ra các vùng xung quanh bằng việc đọc màu của các điểm lân cận để kiểm tra xem chúng đã được tô màu hay chưa. Nếu đã được tô, 47 hoặc màu của điểm lân cận là màu của biên thì dừng lại và xét điểm khác, nếu không thì tô điểm lân cận đó. Có vài phương pháp khác nhau để xác định lân cận như: loại 4 điểm, loại 8 điểm Lân cận 4 điểm Lân cận 8 điểm Procedure BFill ( x,y,c,B:integer) {(x,y) điểm đang xét, c: màu tô, B: màu đường biên } Var t: integer; Begin t:=GetPixel(x,y); if (t B) and (tc) then { putpixel(x,y,c); BFill(x-1,y,c,B); BFill(x+1,y,c,B); BFill(x,y-1,c,B); BFill(x,y+1,c,B); } Cách làm như trên có nhược điểm là khi gọi đệ quy cho 4 điểm lân cận không xét tới việc chúng đã được kiểm tra ở các bước trước hay chưa. Cần có cải tiến để không xét lại những điểm đã được kiểm tra rồi. 2. Thuật toán tô màu dựa theo dòng quét (Scan-line algorithm) Giả sử dùng cần tô là một đa giác N đỉnh {Pi =(xi,yi)} i=1..N Ta sử dụng 1 dòng quét song song với trục Ox đi từ đỉnh trên cùng (Ymax) đến đỉnh dưới cùng (Ymin) của vùng cần tô. Với mỗi giá trị y = yi, dòng quét cắt các đường biên của vùng cần tô tạo thành các đoạn thẳng. Ta tô màu các điểm nằm giữa hai đầu mút của các đoạn thẳng đó. 48 Ymin Ymax Các bước: - Xác định Ymax, Ymin của đa giác cần tô - Với mỗi dòng quét y = yi (Ymin ≤ yi ≤ Ymax), xác định hoành độ giao điểm với các cạnh của đa giác - Sắp xếp chúng theo thứ tự tăng dần thành các cặp (x0, x1) ... - Tô các đoạn (x0, x1), (x2, x3), (x4, x5) ... Tuy nhiên, có một ngoại lệ là khi dòng quét đi qua đỉnh P của đa giác. Khi đó ta phải chia thành 2 trường hợp: - Nếu 2 cạnh kề của P có hướng ngược nhau, một cạnh đi lên một cạnh đi xuống thì trong danh sách giao điểm ta sẽ tính là 2 giao điểm có tọa độ trùng nhau ở đỉnh P. Nghĩa là xi = xi+1 = xP - Nếu 2 cạnh kề của P cùng hướng nhau, cả hai cùng đi lên hoặc đi xuống thì P chỉ được tính là 1 giao điểm. 2 3 1 4 2,3 1 49 Chương III. Các phép biến hình Các phép biến đổi hình học cơ sở bao gồm: - tịnh tiến /dời hình (translation) - quay (rotation) - tỷ lệ /vị tự / (scaling) Ví dụ: - một báo cáo viên muốn thu nhỏ các biểu đồ trong báo cáo - một kiến trúc sư muốn nhìn tòa nhà ở những góc nhìn khác nhau - nhà thiết kế muốn quan sát, tách rời và chỉnh sửa từng chi tiết của mẫu thiết kế - ... Có hai quan điểm về phép biến đổi hình học, có liên quan với nhau và đều có những lợi thế riêng: - Biến đổi đối tượng (object transformation): tọa độ của từng điểm trên đối tượng được biến đổi theo công thức của phép biến hình, tạo ra ảnh của đổi tượng qua phép biến hình đó. - Biến đổi hệ tọa độ (coordinate transformation): tạo ra một hệ tọa độ mới, sau đó tất cả các điểm của đối tượng sẽ được chuyển về hệ tọa độ đó. Phép biến hình affin Ánh xạ T: R2 Æ R2 P(x,y) ÆQ(x*,y*) trong đó: ⎩⎨ ⎧ = = ),(* ),(* yxgy yxfx và f() và g() là hai hàm tuyến tính thì được gọi là phép biến hình Affin (affine). Ta chỉ khảo sát các phép biến hình loại này. Phép biến hình affin có những tính chất sau: - Bảo toàn đường thẳng: ảnh của đường thẳng qua phép biến hình affine là đường thẳng. - Bảo toàn tính song song của các đường thẳng: ảnh của các đường thẳng song song qua phép biến hình affine cũng là các đường thẳng song song. - Bảo toàn tỷ lệ về khoảng cách: giả sử C là điểm chia đoạn AB theo tỷ lệ x và A’,B’,C’ lần lượt là ảnh của A,B,C qua một phép biến hình affin. Khi đó C’ cũng chia đoạn A’B’ theo tỷ lệ x. 4.1. Các phép biến hình phẳng 4.1.1 Các phép biến hình trong hệ tọa độ Decac Phép tịnh tiến Ảnh của phép tịnh tiến theo vector (a,b) của điểm P(x,y) là điểm Q(x*,y*) ⎩⎨ ⎧ += += byy axx * * Vector tịnh tiến (a,b) còn gọi là “vector độ dời”. Chúng ta có thể áp dụng quy tắc trên cho mọi điểm của đối tượng để dịch chuyển nó. Đơn giản hơn, để tịnh tiến một đa giác chỉ cần 1 tịnh tiến các đỉnh của nó rồi vẽ lại đa giác mới. Tương tự, đối với đường tròn, ellip ta tịnh tiến tâm của chúng tới vị trí mới rồi vẽ lại. Phép tỷ lệ Làm thay đổi kích thước của đối tượng. ⎩⎨ ⎧ = = ytyy xtxx .* .* trong đó ty, tx là hệ số co dãn theo trục tung và trục hoành. Khi tx,ty nhỏ hơn 1, phép biến đổi sẽ thu nhỏ đối tượng. Khi tx,ty lớn hơn 1, phép biến đổi sẽ phóng to đối tượng. Khi tx=ty: ta gọi đó là phép đồng dạng (uniform scaling), nó bảo toàn tỷ lệ về kích thước của vật thể. tx=ty=3 tx=3; ty=1 Phép tịnh tiến trong mặt phẳng 6 5 4 3 2 1 1 2 3 4 5 6 Phép tỷ lệ 2 Phép quay Phép quay làm thay đổi hướng của đối tượng. Để xác định phép quay, ta cần biết tâm quay và góc quay. Phép quay điểm P(x,y) quanh gốc tọa độ một góc α tạo thành điểm ảnh Q(x*,y*) có công thức như sau: ⎩⎨ ⎧ += −= αα αα cos.sin.* sin.cos.* yxy yxx 1800 Phép quay quanh một điểm 4.1.2 Ma trận của phép biến hình. Nếu ta biểu diễn điểm P,Q dưới dạng vector dòng (x,y) (x*,y*) như trên thì ma trận của các phép biến hình như sau: Phép tịnh tiến: (x*,y*) = (x,y) + (a,b) Q = P + T trong đó T = (a,b) Phép tỷ lệ: ( ) ( ) ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛= ty tx yxyx 0 0 ,**, Q = P×S trong đó là ma trận của phép đồng dạng ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛= ty tx S 0 0 Phép quay quanh gốc tọa độ: ( ) ( ) ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −= αα αα cossin sincos ,**, yxyx 3 hay Q=P×R trong đó là ma trận của phép quay ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −= αα αα cossin sincos R Tuy nhiên, cách biểu diễn trên sẽ gặp khó khăn khi kết hợp các phép biến đổi lại với nhau vì biểu diễn của phép tịnh tiến (cộng ma trận) khác với hai phép biến hình còn lại (nhân ma trận). Chẳng hạn, khi thiết kế một động cơ, ta muốn tháo riêng một chi tiết ra ngoài (tịnh tiến), xoay 1 góc (quay) rồi lắp vào chỗ cũ (tịnh tiến). Khi đó ta phải thực hiện 3 phép tính trên ma trận (+ × + ). Người ta đã tìm ra cách biểu diễn trong hệ tọa độ thuần nhất, nhờ đó rút gọn chuỗi biến đổi trên về chỉ một phép tính. 4.1.3 Hệ tọa độ thuần nhất (homogeneous coordinates) Tọa độ thuần nhất (đôi khi còn gọi là “đồng nhất”) của điểm (x,y) trên mặt phẳng được biểu diễn bằng bộ ba (xh,yh,h) liên hệ với tọa độ (x,y) bởi công thức h yy h xx hh == , Nếu một điểm có tọa độ thuần nhất là (x,y,z) trong không gian Decac thì nó cũng có tọa độ thuần nhất là (x.h,y.h,z.h) trong đó h là số thực khác không bất kỳ. Ngược lại điểm (x,y,z) trong hệ tọa độ thuần nhất sẽ có tương ứng với điểm (x/z,y/z) trong hệ tọa độ Decac. Tọa độ thuần nhất của một điểm trong không gian 3 chiều hay nhiều chiều cũng được xác định theo cách tương tự. Để đơn giản hóa, người ta thường chọn h=1, lúc này điểm P(x,y) sẽ được biểu diễn dưới dạng tọa độ thuần nhất là (x,y,1) 4.1.4 Ma trận của các phép biến hình trong hệ tọa độ thuần nhất Phép tịnh tiến: ( ) ( ) ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ ×= 1 010 001 1,,1*,*, ba yxyx Hay Q = P × T trong đó T là ma trận của phép tịnh tiến ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ = 1 010 001 ba T Phép tỷ lệ: ( ) ( ) ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ ×= 100 00 00 1,,1*,*, ty tx yxyx Hay Q = P × S trong đó S là ma trận của phép tỷ lệ ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ = 100 00 00 ty tx S Phép quay quanh gốc tọa độ: 4 ( ) ( ) ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ −×= 100 0cossin 0sincos 1,,1*,*, αα αα yxyx Hay Q = P × R trong đó R là ma trận của phép quay ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ −= 100 0cossin 0sincos αα αα R 4.1.5 Kết hợp các phép biến hình Bất kỳ phép biến hình nào cũng được kết hợp từ phép tịnh tiến, tỷ lệ và quay. Khi áp dụng liên tiếp các phép biến hình trên đối tượng, ta phải thực hiện nhiều phép nhân với các ma trận tương ứng. Thay vào đó, ta sẽ chuẩn bị sẵn ma trận tích và sử dụng như ma trận của phép biến hình tổng thể. Kết hợp các phép tịnh tiến Ta thực hiện phép tịnh tiến T1 với vector tịnh tiến (a,b) lên điểm P(x,y) và thu được ảnh Q’, sau đó thực hiện tiếp phép tịnh tiến T2(c,d) đối với Q’ và thu được Q(x*,y*) *)*,()','('),( ),(),( 21 yxQyxQyxP dcTbaT ⎯⎯ →⎯⎯⎯ →⎯ Kết hợp của 2 hay nhiều phép tịnh tiến cho kết quả là phép tịnh tiến có ma trận là tổng các ma trận hành phần: ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ ++ = ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ × ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ ++= 1 010 001 1 010 001 1 010 001 ),(),().,( 21 dbcadcba dbcaTdcTbaT Kết hợp các phép tỷ lệ Tương tự như phép tịnh tiến, kết hợp của nhiều phép tỷ lệ là một phép tỷ lệ. Giả sử ta kết hợp hai phép tỷ lệ sau: S = S1. S2 Ma trận kết hợp sẽ là ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ = ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ × ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ 100 00 00 100 00 00 100 00 00 21 21 1 2 1 1 tyty txtx ty tx ty tx Kết hợp các phép quay 5 Tương tự như phép tịnh tiến, kết hợp của nhiều phép quay quanh gốc tọa độ cũng là một phép quay quanh gốc tọa độ. Giả sử phép quay R1có góc quay là α1, phép quay R2 có góc quay α2, ma trận kết hợp của hai phép quay R1. R2 là ( ) ( ) ( ) ( ) ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ ++− ++ = ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ −× ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ − 100 0cossin 0sincos 100 0cossin 0sincos 100 0cossin 0sincos 2121 2121 22 22 11 11 αααα αααα αα αα αα αα Phép quay với tâm quay bất kỳ Phép quay quanh tâm quay A(x,y) góc quay α có thể phân tích thành các phép biến hình cơ sở sau: - Tịnh tiến theo vector (-x,-y) để đưa tâm quay về gốc tọa độ - Quay quanh gốc tọa độ một góc α - Tịnh tiến theo vector (x,y) để đưa đối tượng về chỗ cũ ( ) ( ) ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ −+−+− −= = ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ × ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ −× ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ −− 1cos1.sinsin.cos1 0cossin 0sincos 1 010 001 100 0cossin 0sincos 1 010 001 yxyx yxyx αααα αα αα αα αα Phép đối xứng Phép đối xứng trục có thể xem là phép quay 1800 quanh trục đối xứng. Phép đối xứng qua trục hoành và trục tung có ma trận lần lượt là ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛− = ⎟⎟ ⎟ ⎠ ⎞ ⎜⎜ ⎜ ⎝ ⎛ −= 100 010