Bài giảng Đồ họa máy tình (Computer Graphics) - Phần 2

Nội dung text: Bài giảng Đồ họa máy tình (Computer Graphics) - Phần 2

1. CHƢƠNGNG III CÁC PHÉP BIẾN ĐỔI ĐỒ HỌA HAI CHIỀU 3.1 Các phép biến đổi cơ sở Trong lĩnh vực đồ họa máy tính, hình dạng và kìch thước của đối tượng hai chiều đặc trưng bởi một số 2 chiều quan hệ với hệ thống tọa độ Descartes. Một tập hợp các phép biến đổi hình học áp dụng cho đối tượng như: dịch chuyển, thay đổi kìch thước, phương chiều của nĩ. Các hệ CAD lũn cĩ thao tác như: scale, move, rotate, copy thực hiện những phép biến đổi hình học cơ sở. 3.1.1 Phép tịnh tiến Khả năng tịnh tiến đối tượng là một đặc điểm cần thiết của mọi hệ thống đồ họa. Phép tịnh tiến làm cho đối tượng dịch chuyển theo một hướng với độ dâi xác định. Dưới dạng tốn học, mơ tả với hệ x' x Tx phương trình sau: (3-1) y' y Ty Trong đĩ Tx và Ty là các vectơ tịnh tiến, điểm P(x,y) sau khi tịnh tiến một khoảng [Tx, Ty] sẽ sinh ra điểm P’(x’,y’) với x’ và y’ được tình theo phương trính (3-1) Hình 3.1. Mơ tả tịnh tiến tam gíac trong khơng gian 2 chiều 42
2. 3.1.2 Phép biến đổi tỷ lệ Phép biến đổi tỉ lệ làm thay đổi kìch thước đối tượng. Phép biến đổi tỷ lệ cịn được gọi là phép co giãn. Để co hay giãn tọa độ của một điểm P(x,y) theo trục hồnh và trục tung lần lượt là Sx và Sy(gọi là các hệ số tỉ lệ), ta nhân Sx và Sy lần lượt cho các tọa độ x' x . Sx của P. (3 - 2) y' y . Sy Trong đĩ Sx là hệ số co giãn theo trục x là Sy là hệ số co giãn theo trục y Sx 0 x' y' x y 0 S y Khi các giá trị Sx, Sy nhỏ hơn 1, phép biển đổi sẽ thu nhỏ đối tượng. Ngược lại, khi các giá trị này lớn hơn 1, phép biến đổi sẽ phĩng lớn đối tượng. Khi Sx = Sy, người ta gọi đĩ là phép đồng dạng (uniform scaling). Đây là phép biến đổi bảo tồn tính cân xứng của đối tượng. Ta gọi là phép phĩng đại nếu |S|>1 và là phép thu nhỏ nếu |S|<1. Nếu hai hệ số tỉ lệ khác nhau thì ta gọi là phép khơng đồng dạng. Trong trường hợp hoặc Sx hoặc Sy cĩ giá trị 1, ta gọi đĩ là phép căng (strain). Ví dụ: Cho điểm A cĩ tọa độ là A(10,20) sau khi biến đổi tỷ lệ theo trục tung là 5 và theo trục hồnh là 10 sẽ sinh ra điểm A’(50, 200) 3.1.3 Phép đối xứng Thuật ngữ đối xứng hiểu như hình ảnh trong gương. Phép đối xứng sử dụng trong việc tạo các hình đối xứng. Ví dụ như một nửa hình được tạo ra, sau đĩ lấy đối xứng để 43
3. tạo nguyên hình, hoặc việc tạo khung đỡ mái nhà. Các ứng dụng như CAD luơn cĩ chỉ thị Mirror thực hiện chức năng trên. Phép đối xứng qua điểm hay qua trục nào đĩ. Ma trận đối xứng sẽ cĩ dạng chung như sau: (3-3) Các trường hợp khác nhau của đối xứng trục X, Y, Z như sau: 3.1.4 Phép quay Phép quay làm thay đổi hướng của đối tượng. Một phép quay địi hỏi phải cĩ tâm quay, gĩc quay. Gĩc quay dương thường được qui ước là chiếu ngược chiều kim đồng hồ. Ta cĩ cơng thức biến đổi của phép quay điểm P(x,y) quanh gốc tọa độ gĩc θ tới vị trí P’(x’, y’): x' x . cos - y.sin (3-4) y' x.sin y.cos Ví dụ: Cho 3 điểm A, B, C cĩ tọa độ lần lượt là: A(0,40); B(- 37,125); C(40, -81) 44
4. Hãy tìm tọa độ mới của các điểm trên qua phép quay gĩc 60o, ngược chiều kim đồng hồ quanh gốc tọa độ? 3.2. Kết hợp các phép biến đổi Những phép biến hình 2 chiều địi hỏi khơng chỉ một mà là chuỗi thứ tự các phép biến hính cơ sở để cuối cùng thu được mục tiêu mong muốn. 3.2.1. Kết hợp các phép tịnh tiến Nếu ta thực hiện phép tịnh tiến lên điểm P được điểm P', rồi lại thực hiện tiếp một phép tịnh tiến khác lên P' được điểm Q. Như vậy, điểm Q là ảnh của phép biến đổi kết hợp hai phép tịnh tiến liên Qx Px ( Tx1 Tx2 ) tiếp. Qy Py ( Ty1 Ty2 ) Vậy kết hợp hai phép tịnh tiến là một phép tịnh tiến. Từ đĩ, ta cĩ kết hợp của nhiều phép tịnh tiến là một phép tịnh tiến. T(Tx , Ty ).T(Tx , Ty )=T(Tx +Tx , Ty +Ty ) 1 1 2 2 1 2 1 2 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 Tx1 Ty1 1 Tx2 Ty2 1 Tx1 Tx2 Ty1 Ty2 1 3.2.2 Kết hợp các phép biến đổi tỷ lệ Tương tự như phép tịnh tiến, ta cĩ tọa độ điểm Q là điểm cĩ được sau hai phép tỷ lệ M1(Sx1, Sy1 ), M2 (Sx2, Sy2 ) là : Qx Px * Sx1 * Sx2 Qy Py* Sy1* Sy2 Vây kết hợp hai phép tỷ lệ là một phép tỷ lệ. Từ đĩ, ta cĩ kết hợp của nhiều phép tỷ lệ là một phép tỷ lệ. S(Sx , Sy ).S(Sx , Sy )=S(Sx .Sx , Sy .Sy ) 1 1 2 2 1 2 1 2 45
5. 3.2.3 Kết hợp các phép quay Tương tự, ta cĩ tọa độ điểm Q là điểm kết quả sau khi kết hợp hai phép quay quanh gốc tọa độ MR1(θ1) và MR2(θ2) là : Qx Px * cos(1  2) - Py*sin(1  2) Qy Px * sin(1  2) Py* cos(1  2) Tổng hợp 2 phép quay như sau: R(θ ).R(θ ) = R(θ +θ ) 1 2 1 2 3.2.4. Một số phép biến đổi khác a. Phép biến dạng Phép biến dạng làm thay đổi hình dạng đối tượng, biến dạng theo trục hồnh hay trục tung bằng cách thay đổi tọa độ điểm ban đầu theo cách sau đây: Sx và Sy là các hệ số biến dạng theo trục hồnh và trục tung b. Phép đối xứng Phép đối xứng xem như phép quay quanh trục đối xứng gĩc 46
6. 180o. Nếu trục đối xứng là trục hồnh hay trục tung , ta cĩ các ma trận biến đổi đối xứng qua trục hồnh và trục tung như sau: 3.3 Phép biến đổi giữa các hệ tọa độ Để thuận tiện cho việc mơ tả đối tượng, thơng thường đối tượng được mơ tả trong hệ tọa độ cục bộ gắn với chúng. Tuy nhiên, muốn hiển thị tồn bộ ảnh bao gồm nhiều đối tượng thành phần, các mơ tả phải chuyển về một hệ tọa độ. Quá trình chuyển đổi tọa độ chia thành 2 loại:  Từ hệ tọa độ cực, tọa độ cầu sang hệ tọa độ đề các.  Giữa 2 hệ tọa độ đề các. Trong nội dung trình bày của chương này, ta chỉ xét đối tượng hình học trong khơng gian tọa độ Đề các, do đĩ ta khảo sát phép biến đổi giữa 2 hệ tọa độ Đề các. Giả sử ta cĩ hệ tọa độ I cĩ gốc tọa độ O và các véc tơ đơn vị là i, j . Hệ tọa độ II là ảnh của hệ tọa độ I qua phép biến đổi T(M), cĩ gốc tọa độ O’ và các véc tơ đơn vị là tương ứng u, v. Lúc này, một điểm P(x, y) trong hệ tọa độ I sẽ biến đổi thành điểm Q(a, b) trong hệ tọa độ II. BÀI TẬP ÁP DỤNG Bài 1: Cho biết phép biến đổi hình vuơng thành hình chữ nhật? Bài 2: Chứng minh rằng ma trận phép biến đổi lấy đối xứng qua đường thẳng y = x tương đương với kết hợp của phép lấy đối xứng trục hồnh và phép quay quanh gốc tọa độ gĩc 90o . Bài 3: Chứng minh phép quay cĩ tính giao hốn. 47
7. CHƢƠNG IV PHÉP QUAN SÁT HAI CHIỀU 4.1 Cửa sổ, Vùng quan sát Hệ tọa độ Descartes là dễ thích ứng cho các chương trính ứng dụng để miêu tả các hình ảnh trên hệ tọa độ thực. Các hình ảnh được định nghĩa trên hệ tọa độ thực này sau đĩ được hệ đồ họa vẽ lên các hệ tọa độ thiết bị. Điển hình, một vùng đồ họa cho phép người sử dụng xác định vùng nào của hình ảnh sẽ được hiển thị và bạn muốn đặt nĩ ở nơi nào trên hệ tọa độ thiết bị. Một vùng đơn lẻ hoặc vài vùng của hình ảnh cĩ thể được chọn. Những vùng này cĩ thể được đặt ở những vị trí tách biệt, hoặc một vùng cĩ thể được chèn vào một vùng lớn hơn. Quá trính biến đổi này liên quan đến những thao tác như tịnh tiến, biến đổi tỷ lệ Vùng được chọn , xĩa bỏ Vùng khơng được chọn. Những thao tác trên là Windowing và Clipping. Hình 4.1. Ánh xạ từ cửa sổ - vùng quan sát 48
8. Một vùng cĩ dạng hình chữ nhật được xác định trong hệ tọa độ thực được gọi là một cửa sổ (window). Cịn vùng hình chữ nhật trên thiết bị hiển thị để cửa sổ đĩ ánh xạ đến được gọi là một vùng quan sát (viewport). Hình 4.1 minh họa việc ánh xạ một phần hình ảnh vào trong một vùng quan sát. Việc ánh xạ này gọi là một phép biến đổi hệ quan sát, biến đổi cửa sổ, biến đổi chuẩn hĩa. Các lệnh để xây dựng một cửa sổ và vùng quan sát từ một chương trính ứng dụng cĩ thể được định nghĩa như sau: set_window(xw_min, xw_max, yw_min, yw_max) set_viewport(xv_min, xv_max, yv_min, yv_max) Các tham số trong mỗi hâm được dùngđể định nghĩa các giới hạn tọa độ của các vùng chữ nhật. Các giới hạn của cửa sổ được xác định trong hệ tọa độ thực. Hệ tọa độ thiết bị chuẩn thường được dùng nhất cho việc xác định vùng quan sát, dù rằng hệ tọa độ thiết bị cĩ thể được dùng nếu chỉ cĩ một thiết bị xuất duy nhất trong hệ thống. Khi hệ tọa độ thiết bị chuẩn được dùng, lập trình viên xem thiết bị xuất cĩ giá trị tọa độ trong khoảng 0 1. Một sự xác định Vùng quan sát được cho với các giá trị trong khoảng này. Các việc xác định sau đây, đặt một phần của sự định nghĩa hệ tọa độ thực vào trong gĩc trên bên phải của Vùng hiển thị, như được minh họa trong hình 4.2: set_window(-60.5, 41.25, -20.75, 82.5); set_viewport(0.5, 0.8, 0.7, 1.0); Nếu một cửa sổ buộc phải được ánh xạ lấp đầy Vùng hiển thị, sự xác định vùng quan sát được thiết lập theo thủ tục: set_viewport(0,1, 0, 1) 49
9. Hình 4.2: Ánh xạ một cửa sổ vào một vùng quan sát trong hệ tọa độ thiết bị chuẩn Các vị trì được biểu diễn trên hệ tọa độ thiết bị chuẩn phải được biến đổi sang hệ tọa độ thiết bị trước khi được hiển thị bởi một thiết bị xuất cụ thể. Thơng thường một thiết bị xác định được chứa trong các gĩi đồ họa cho mục đìch này. Thuận lợi của việc dùnghệ tọa độ thiết bị chuẩn là để các gĩi đồ họa độc lập với thiết bị. Các thiết bị xuất khác nhau cĩ thể được dùngnhờ việc cung cấp các trình điều khiển thiết bị thích hợp. Mọi điểm được tham khảo đến trong các gĩi đồ họa phải được xác định tương ứng trong hệ tọa độ Descartes. Bất kỳ sự định nghĩa hình ảnh nào dùngtrong một hệ tọa độ khác, như hệ tọa độ cực, người sử dụng trước tiên phải biến đổi nĩ sang hệ tọa độ thực. Những hệ tọa độ Descart này sau đĩ được dùngtrong các lệnh cửa sổ để xác định phần nào của hình ảnh muốn được hiển thị. 50
10. 4.2 Phép biến đổi từ cửa sổ - đến - vùng quan sát Khi tất cả các điểm, đoạn thẳng, và văn bản vừa bị cắt, chúng được ánh xạ lên vùng quan sát để hiển thị. Phép biến đổi đến vùng quan sát này được thực hiện để các vị trí tọa độ liên hệ được giữ lại. Trong hình, một điểm ở vị trí (xw, yw) trong một cửa sổ được ánh xạ và trong vị trí (xv, yv) trong Vùng quan sát. Để duy trì sự sắp đặt liên hệ tương tự trong vùng quan sát như trong cửa sổ, chúng ta cần xác định ánh xạ: x x x x y y y y v vmin w wmin ; v vmin w wmin (4-1) xvmax xvmin xwmax xwmin yvmax yvmin ywmax ywmin Vì vậy: x x x x x v max v min x v w wmin v min xwmax xwmin y y y y y v max v min y v w wmin v min (4-2) ywmax ywmin x x v max v min yv max yv min Các giá trị tỷ lệ , là xwmax xwmin yw max yw min hằng số đối với các điểm được ánh xạ và là hệ số tỷ lệ Sx và Sy theo 2 trục tương ứng. Nếu 2 tỷ lệ khác nhau thì hình vẽ mới trong Vùng quan sát bị biến dạng so với hình ban đầu, cịn nếu 2 tỷ lệ giống nhau thì hình vẽ mới khơng biến dạng. 4.3 Phép cắt xén 2 chiều Ánh xạ một Vùng cửa sổ vào trong một Vùng quan sát, kết quả là chỉ hiển thị những phần trong phạm vi cửa sổ. Mọi thứ bên 51
11. ngồi cửa sổ sẽ bị loại bỏ. Các thủ tục để loại bỏ các phần hình ảnh nằm bên Ngồi biên cửa sổ được xem như các thuật tốn cắt xén (clipping algorithms) hoặc đơn giản được gọi là clipping. Việc cài đặt phép biến đổi cửa sổ thường được thực hiện bằng việc cắt khỏi cửa sổ, sau đĩ ánh xạ phần bên trong cửa sổ vào một vùng quan sát. Như một lựa chọn, một vài gĩi đồ họa đầu tiên ánh xạ sự định nghĩa trong hệ tọa độ thực vào trong hệ tọa độ thiết bị chuẩn và sau đĩ cắt khỏi biên vùng quan sát. Trong các các phần thảo luận sau, chúng ta giả thiết rằng việc cắt được thực hiện dựa vào đường biên cửa sổ trong hệ tọa độ thực. Sau khi cắt xong, các điểm bên trong cửa sổ mới được ánh xạ đến vùng quan sát. Việc cắt các điểm khỏi cửa sổ được hiểu đơn giản là chúng ta kiểm tra các giá trị tọa độ để xác định xem chúng cĩ nằm bên trong biên khơng. Một điểm ở vị trì (x,y) được giữ lại để chuyển đổi sang vùng quan sát nếu nĩ thỏa các bất phương trình sau: xwmin ≤ x ≤ xwmax, ywmin ≤ y ≤ ywmax (4-3) Hình 4.3. Hình ảnh các đoạn thẳng trƣớc và sau khi Clipping 52
12. Nếu điểm nào khơng thỏa mãn một trong các bất phương trình trên, nĩ bị cắt bỏ. Trong hình trên, điểm P1 được giữ lại, trong khi điểm P2 bị cắt bỏ. Hình 4.3 minh họa các quan hệ cĩ thể cĩ giữa các vị trì đoạn thẳng với biên cửa sổ. Để kiểm tra một đoạn thẳng cĩ bị cắt hay khơng bằng việc xác định hai điểm đầu một đoạn thẳng là nằm trong hay nằm ngồi cửa sổ. Một đoạn thẳng với cả hai đầu nằm trong cửa sổ thì được giữ lại hết, như đoạn từ P5 đến P6. Một đoạn với một đầu nằm ngồi (P9) và một đầu nằm trong (P10) sẽ bị cắt bớt tại giao điểm với biên cửa sổ (P’9). Các đoạn thẳng cĩ cả hai đầu đều nằm Ngồi cửa sổ, cĩ thể rơi vào hai trường hợp: tồn bộ đoạn thẳng đều nằm Ngồi hoặc đoạn thẳng cắt hai cạnh cửa sổ. Đoạn từ P3 đến P4 bị cắt bỏ hồn tồn. Nhưng đoạn từ P7 đến P8 sẽ được giữ lại phần từ P’7 đến P’8. Thuật tốn cắt xén đường xác định xem đoạn nào tồn bộ nằm trong, đoạn nào bị cắt bỏ hồn tồn hay bị cắt một phần. Đối với các đoạn bị cắt bỏ một phần, các giao điểm với biên cửa sổ phải được tính. Vì một hình ảnh cĩ thể chứa hàng ngân đoạn thẳng, việc xử lý clipping nên được thực hiệnsao cho cĩ hiệu quả nhất. Trước khi đi tình các giao điểm, một thuật tốn nên xác định rõ tất cả các đoạn thẳng được giữ lại hồn tồn hoặc bị cắt bỏ hồn tồn. Với những đoạn được xem xét là bị cắt bỏ, việc xác định các giao điểm cho phần được giữ lại nên được thực hiện với sự tính tốn ít nhất. 4.3.1 Giải thuật Cohen - Suntherland Một tiếp cận để cắt các đoạn là dựa trên cơ chế đánh mã được phát triển bởi Cohen và Sutherland. Mọi điểm ở hai đầu một đoạn thẳng trong hình ảnh sẽ được gán một mã nhị phân 4 bit, được gọi là mã vùng, giúp nhận ra vùng tọa độ của một điểm. Các Vùng này được xây dựng dựa trên sự xem xét với biên cửa sổ, như ở hình 4.4. 53
13. Hình 4.4. Cơ chế đánh mã Mỗi vị trí bit trong mã Vùng được dùng để chỉ ra một trong bốn vị trí tọa độ tương ứng của điểm so với cửa sổ: bên trái, phải, trên đỉnh, dưới đáy. Việc đánh số theo vị trí bit trong mã vùng từ 1 đến 4 cho từ phải sang trái, các vùng tọa độ cĩ thể liên quan với vị trí bit như sau: Bit 1 - trái ; Bit 2 - phải; Bit 3 – dưới; Bit 4 – trên. Giá trị 1 ở bất kỳ vị trí nào chỉ ra rằng điểm ở vị trì tương ứng, ngược lại bit ở vị trì đĩ là 0. Nếu một điểm nằm trong cửa sổ, mã vị trí là 0000. Một điểm bên dưới và bên trái cửa sổ cĩ mã vùng là 0101 . Các giá trị bit trong mã Vùng được xác định bằng cách so sánh giá trị tọa độ (x,y) của điểm đầu một với biên cửa sổ. Bit 1 đặt lên 1 nếu x < xwmin. Các giá trị của ba bit cịn lại được xác định bằng cách so sánh tương tự. Trong các ngơn ngữ lập trình, làm việc trên bit như thế này cĩ thể thực hiện được, các giá trị bit mã Vùng cĩ thể được xác định theo các bước sau: (1) Tìm hiệu giữa tọa độ các điểm đầu một với biên cửa sổ. (2) Dùng bit dấu (kết 54
14. quả của mỗi hiệu) để đặt giá trị tương ứng trong mã Vùng. Bit 1 là bit dấu của x - xwmin; bit 2 là bit dấu của xwmax - x; bit 3 là bit dấu của y - ywmin; và bit 4 là bit dấu của ywmax - y. Khi chúng ta xây dựng xong các mã Vùng cho tất cả các điểm đầu một, chúng ta cĩ thể xác định nhanh chĩng đoạn thẳng nào là hồn tồn nằm trong cửa sổ, đoạn nào là hồn tồn nằm ngồi. Bất kỳ đoạn nào cĩ mã Vùng của cả 2 đầu một là 0000 thì nằm trong cửa sổ và chúng ta chấp nhận các đường này. Bất kỳ đường nào mà trong hai mã Vùng của hai đầu một cĩ một số 1 ở cùng vị trí bit thì đoạn hồn tồn nằm Ngồi cửa sổ, và chúng ta loại bỏ các đoạn này. Ví dụ, chúng ta vứt bỏ đoạn cĩ mã Vùng ở một đầu là 1001, cịn đầu kia là 0101 (cĩ cùng bit 1 ở vị trí 1 nên cả hai đầu một của đoạn này nằm ở phía bên trái cửa sổ). Một phương pháp cĩ thể được dùng để kiểm tra các đoạn cho việc cắt tồn bộ là thực hiện phép logic and với cả hai mã Vùng. Nếu kết quả khơng phải là 0000 thì đoạn nằm bên Ngồi cửa sổ. Các đường khơng được nhận dạng là hồn tồn nằm trong hay hồn tồn nằm Ngồi một cửa sổ thơng qua các phép kiểm tra trên sẽ được tìm giao điểm với biên cửa sổ. Như được chỉ ra ở hình dưới đây, các đường thuộc nhĩm này cĩ thể cắt hoặc khơng cắt cửa sổ. Chúng ta cĩ thể xử lý các đoạn này bằng cách so sánh một điểm đầu một (cái đang nằm Ngồi cửa sổ) với một biên cửa sổ để xác định phần nào của đường sẽ bị bỏ. Sau đĩ, phần đường được giữ lại sẽ được kiểm tra với các biên khác, và chúng ta tiếp tục cho đến khi tồn bộ đường bị bỏ đi hay đến khi một phần đường được xác định là nằm trong cửa sổ. Chúng ta xây dựng thuật tốn để kiểm tra các điểm đầu mút tương tác với biên cửa sổ là ở bên trái, bên phải, bên dưới hay trên đỉnh. Để minh họa các bước xác định trong việc cắt các đoạn khỏi biên cửa sổ dùng thuật tốn của Cohen- 55
15. Sutherland, chúng ta xem các đoạn trong hình được xử lý như thế nào. Bắt đầu ở điểm đầu mút bên dưới từ P1 đến P2, ta kiểm tra P1 với biên trái, phải và đáy cửa sổ và thấy rằng điểm này nằm phía dưới cửa sổ. Ta tím giao điểm P’1 với biên dưới. Sau khi tìm giao điểm P’1, chúng ta vứt bỏ đoạn từ P1 đến P’1. Giao điểm P’2 được tính, và đoạn từ P’1 đến P’2 được giữ lại. Kết thúc quá trình xử lý đoạn P1P2. Bây giờ xét đoạn kế tiếp, P3P4. Điểm P3 nằm bên trái cửa sổ, vì vậy ta xác định giao điểm P’3 và loại bỏ đoạn từ P’3 đến P3. Bằng cách kiểm tra mã vùng phần đoạn thẳng từ P’3 đến P4, chúng ta thấy rằng phần cịn lại này nằm phìa dưới cửa sổ và cũng bị vứt bỏ luơn. Các giao điểm với biên cửa sổ cĩ thể được tính bằng cách dùng các tham số của phương trính đường thẳng. Với một đường thẳng đi qua hai điểm (x1, y1) và (x2, y2), tung độ y của giao điểm với một biên dọc cửa sổ cĩ thể tình được theo phép tính: y = y1 + m (x - x1) (4-4) Ở đây giá trị x được đặt là xwmin hoặc xwmax, và độ dốc m được tính bằng là m = (y2 - y1)/ (x2 - x1) Tương tự, nếu ta tìm giao điểm với biên ngang, hồnh độ x cĩ thể được tình như sau: x = x1 + (y - y1)/m (4-5) với y là ywmin hoặc ywmax. 4.3.2 Giải thuật chia tại trung điểm Một kỹ thuật để xác định giao điểm với biên cửa sổ mà khơng dùngđến phương trình đường thẳng là dùng thủ tục tìm kiếm nhị phân, được gọi là sự phân chia tại trung điểm. Đầu tiên, việc kiểm tra các đoạn một lần nửa được thực hiện bằng cách dùng mã vùng. Bất kỳ đoạn nào khơng được chấp nhận hồn tồn hoặc khơng bị huỷ bỏ hồn tồn (nhờ vào kiểm tra mã vùng) thì sẽ 56
16. được đi tìm giao điểm bằng cách kiểm tra tọa độ trung điểm. Tiếp cận này được minh họa trong hình dưới đây. Mọi đoạn thẳng với hai điểm đầu mút (x1,y1) và (x2, y2), trung điểm được tính như sau: xm = (x1 + x2) / 2; ym = (y1 + y2) / 2 (4-6) Mỗi kết quả tính tốn cho tọa độ giao điểm liên quan đến một phép cộng và một phép chia 2. Khi tọa độ giao điểm được xác định, mỗi nửa đoạn thẳng được kiểm tra để chấp nhận hay huỷ bỏ tồn bộ. Nếu một nửa đoạn được chấp nhận hoặc bị huỷ bỏ, một nửa kia sau đĩ sẽ được xử lý theo cách tương tự. Điều này tiếp tục cho đến khi gặp một giao điểm. Nếu một nửa được chấp nhận hoặc bị huỷ bỏ tồn bộ, nửa kia tiếp tục được xử lý cho đến khi tồn bộ nĩ là bị huỷ bỏ hoặc được giữ lại. Cài đặt phần cứng theo phương pháp này cĩ thể giúp ta clipping khỏi biên Vùng quan sát nhanh chĩng sau khi các đối tượng vừa được chuyển sang hệ tọa độ thiết bị. 4.3.3 Giải thuật Liang - Barsky Giải thuật được dựa trên phân tìch phương trình tham số đoạn thẳng: x x1 t(x2 x1) x 1 tDx y y1 t(y2 y1) y1 tD y , 0 t 1 (4-7) Ứng với mỗi giá trị t, ta cĩ một điểm P tương ứng thuộc đường thẳng. Tập hợp các điểm thuộc phần giao của đoạn thẳng và cửa sổ thỏa mãn hệ bất phương trình: 57
17. (4-8) Đặt p1 = -Dx, q1 = x1 - xwmin P2 = Dx, q2 = xwmax - x1 p3 = -Dy, q3 = y1 - ywmin p4 = Dy, q4 = ywmax - y1 Hệ bất pt 4-8 cĩ dạng: (4-9) Như thế, tìm đoạn giao thực chất là tìm nghiệm của hệ bất phương trính 4-9. Cĩ các trường hợp sau: - Nếu  k {1,2,3,4} : pk = 0 và qk 0: ta cĩ t pk qk Vậy nghiệm của hệ phương trính (4-9) là [t1, t2] thỏa mãn  Nếu hệ 4-9 cĩ nghiệm thì đoạn giao giữa đoạn thẳng và cửa sổ là : Q1( x1 t 1Dx , y1 t1 Dy) và Q2 ( x1 t 2Dx , y1 t 2 Dy ) 58
18. Bài tập áp dụng Bài 1 Ý nghĩa mã Vùng trong giải thuật Cohen - Sutherland. Bài 2 So sánh hai thuật tốn Cohen - Sutherland và Liang - Barsky về số phép tính thực hiện trong các trường hợp chính. Bài 3 Cài đặt thuật tốn cắt xén hình chữ nhật với 1 đoạn thẳng cho trước theo giải thuật Liang Barsky hay Cohen - Sutherland. Bài 4 Cho biết ma trận của phép biến đổi từ cửa sổ sang Vùng quan sát. Gợi ý: ma trận biến đổi là tích ba ma trận tịnh tiến, tỷ lệ, tịnh tiến. 59
19. CHƢƠNG V ĐỒ HỌA 3 CHIỀU 5.1 Tổng quan về đồ họa ba chiều Khi mơ hình hĩa và hiển thị một đối tượng ba chiều, ta cần mơ tả thơng tin cho đối tượng. Các cơng cụ hỗ trợ đồ họa cung cấp một số hâm hiển thị các thành phần bên trong, những nét tiëu biểu hay một phần của đối tượng. Ngồi ra, các phép biến đổi được dùngđa dạng hơn so với đồ họa hai chiều vì phải chọn nhiều tham số mơ tả đối tượng. Mơ tả một đối tượng ba chiều phải qua quy trình xử lý gồm nhiều cơng đoạn như phép biến đổi hệ tọa độ quan sát và phép chiếu phối cảnh , chuyển đổi từ hệ tọa độ quan sát ba chiều sang hệ tọa độ quan sát hai chiều. Những phần nhìn thấy trong hệ tọa độ quan sát được chọn, xác định và cuốicùng, giải thuật vẽ bề mặt của đối tượng được áp dụng nhằm tạo ra hình ảnh thực tế của đối tượng ba chiều. 5.1.1 Quy trình hiển thị đồ họa ba chiều Đối tượng được mơ tả trong khơng gian (x, y, z). Cĩ hai dạng mơ hình hĩa là mơ hình thể hiện vật thể (solid) hay bề mặt (boundaries) của đối tượng. Các mơ hình được biểu diễn trong hệ tọa độ cục bộ, hệ tọa độ này chỉ định nghĩa cho đối tượng nên gốc tọa độ và đơn vị đo được chọn sao cho phù hợp với đối tượng. Bước đầu tiên trong quy trình hiển thị là biến đổi đối tượng từ khơng gian đối tượng sang khơng gian thực. Trong khơng gian này thì đối tượng, nguồn sáng, người quan sát cùng tồn tại. Quá trình này gọi là biến đổi mơ hình. Tiếp theo, ta loại bỏ các phần của đối tượng khơng nhìn thấy, giúp giảm bớt những thao tác dư thừa của hình ảnh sẽ hiển thị. Bước tiếp theo là phải chiếu sáng đối tượng, gán cho chúng 60
20. màu sắc dựa vào đặc điểm hình thành vật. Sau khi chiếu sáng, phải thực hiện một phép biến đổi hệ tọa độ đặt vị trí quan sát về gốc tọa độ và mặt phẳng quan sát tại vị trí phù hợp. Các đối tượng được đưa về khơng gian quan sát. Sau đĩ, chiếu đối tượng xuống mặt phẳng hai chiều, biến đổi từ khơng gian quan sát sang khơng gian thiết bị màn hình. Đối tượng xem như tập hợp các điểm, tồn cảnh đối tượng được hiển thị lên màn hình. 5.1.2 Mơ hình hĩa đối tượng Một phương pháp thơng dụng để mơ hình hĩa đối tượng là mơ hình khung nối kết. Mơ hình khung nối kết gồm tập đỉnh và tập cạnh nối các đỉnh. Khi thể hiện mơ hình, các đối tượng là rỗng và khơng giống thực tế. Để hồn thiện, ta tạo Màu sắc, độ bĩng bề mặt, loại bỏ các mặt đường khơng nhìn thấy. Hình dạng của đối tượng ba chiều được biểu diễn trên hai danh sách: danh sách đỉnh và danh sách cạnh. Danh sách đỉnh cho thơng tin hình học là vị trì các đỉnh, cịn danh sách cạnh xác định thơng tin kết nối. Ngồi ra, đơi khi ta mơ tả các mặt phẳng của đối tượng. Mỗi mặt được định nghĩa bởi một đa giác bao. Ví dụ đối tượng hình lập phương cĩ 6 mặt và danh sách đỉnh, cạnh biểu diến mơ hình khung nối kết của nĩ như bảng sau: 61
21. 5.2 Biểu diễn đối tƣợng ba chiều Các cảnh đồ họa được biểu diễn theo những phương pháp khác nhau sao cho phù hợp với thuộc tình đối tượng. Các mặt đa giác và mặt bậc hai cung cấp cho chúng ta mơ tả gần đúng của các đối tượn elip, hyperbol, cách tiếp cận thủ tục như Fractal cho phép ta biểu diễn chình xác các đối tượng tự nhiên như bầu trời, khơng gian thực tế. Sơ đồ biểu diễn một đối tượng chia thành 2 dạng chình: Phương pháp biểu diễn bề mặt B - reps và phương pháp biểu diễn theo phân hoạch khơng gian. 5.2.1 Biểu diễn mặt đa giác Mơ hình hĩa bề mặt đối tượng thường được biểu diễn đối 62
22. tượng, thơng qua tập hợp các mặt đa giác xác định bề mặt đối tượng. Với cách biểu diễn trên, ta đơn giản hĩa cách lưu trữ dữ liệu và tăng tốc độ hiển thị đối tượng vì bề mặt được mơ tả bằng phương trình tuyến tính. Vì nguyên nhân trên mà mơ tả các đối tượng thơng qua mặt đa giác được dùngcho các đối tượng đồ họa cơ sở. Trong một vài trường hợp, ta chỉ cĩ thể chọn lựa cách biểu diễn đa giác, việc biểu diễn như thế cung cấp một định nghĩa chình xác về đặc tính của đối tượng. Ví dụ như biểu diễn một hình trụ thì xem như hình trụ là tập các mặt đa giác ghép liền. Nếu cần thể hiện hình trụ thực hơn thì phải biến đổi tạo bĩng nội suy cho hình trụ. 5.2.2 Đường cong và mặt cong , đường cong và mặt cong Bezier, B-Spline Hình ảnh các đường cong và mặt cong cĩ thể được tạo ra từ một tập các hàm tốn học định nghĩa các đối tượng hoặc tập các điểm trên đối tượng. Đối với các đối tượng hình học như hình trịn hay elip thì thư viện đồ họa đã cung cấp sẵn hàm vẽ đối tượng lên mặt phẳng hiển thị. Hình biểu diễn đường cong là tập các điểm dọc theo hình chiếu của đường mơ tả bởi hàm số. Nhưng với các đường cong hay mặt cong khơng cĩ quy luật, thì tập điểm hay lưới đa giác xấp xỉ với đường mặt cong sẽ tạo ra. Hệ đồ họa hay tạo các lưới tam giác để đảm bảo tình đồng phẳng của các cạnh. Một đường cong hay mặt cong cĩ thể diễn tả bằng phương trình tham số hay khơng cĩ tham số, tuy nhiên cách biểu diễn thứ nhất được áp dụng trong các Bài tốn đồ họa sẽ thuận tiện hơn cách kia. Những đối tượng hình học như hình trịn, elip hình trụ, hình nĩn, hay hình cầu được xem là những đường và mặt cong xác định được phương trình tham số chình xác cho nĩ. Do đĩ, mọi hệ đồ họa đều hỗ trợ trực tiếp biểu diễn các đối tượng hình học 63
23. trên. Tuy nhiên, trong thực tế, cĩ những đối tượng hình học khơng cĩ quy luật chình xác để mơ tả những đối tượng như mặt cong của thanh chắn va đập của xe õ tơ, hình thãn tâu thủy, tay cầm tách chén cafe Ngồi ra, cũng khơng thể mơ tả đối tượng hình học thơng qua phép nội suy. Yêu cầu đặt ra là: Cĩ một đường cong, xác định theo tập các điểm phân biệt p1, p2, pk . Hãy tìm ra giải thuật tạo đường cong ban đầu với độ chính xác nào đĩ? Cĩ 2 cách giải quyết: - Thứ nhất, định vị tọa độ các điểm đã biết thuộc đường cong, tìm ra phương trình tham số để nĩ đi qua các điểm đĩ và trùng khớp hình dáng với đường cong ban đầu. - Thứ hai, xác định một số điểm điều khiển, và tìm giải thuật tạo ường cong dựa trên các điểm đĩ. Ta phải thay đổi vị trì điểm điều khiển cho tới khi đường cong mới cĩ hình dáng giống như hình dáng đường cong ban đầu thì xem như giải quyết xong. 5.3 Các phép biến đổi hình học 3 chiều Các điểm trong khơng gian ba chiều được biểu diễn bằng hệ trục tọa độ ba chiều, cĩ thể xem là mở rộng của hệ trục tọa độ hai chiều. Trong thế giới hai chiều, mặt phẳng xy chứa tồn bộ đối tượng. Trong thế giới ba chiều, một trục z vuơng gĩc được đưa ra để tạo thêm hai mặt phẳng chính khác là xz và yz. Chiều của các trục tọa độ trong hệ trục tọa độ ba chiều cĩ thể tuân theo quy tắc bàn tay phải hay quy tắc bàn tay trái. Hệ trục tọa độ tuân theo quy tắc bàn tay phải được mơ tả bằng bàn tay phải, với ngĩn tay cái hướng theo trục z, các ngĩn tay cịn lại xoắn theo chiều từ trục x dương sang trục y dương. Hệ trục tọa độ tuân theo quy tắc bàn tay trái được mơ tả bằng bàn tay trái, nếu đặt bàn tay trái sao cho các ngĩn tay uốn cong theo chiều từ trục x dương tới trục y dương, thì ngĩn tay cái sẽ chỉ theo chiều trục z 64
24. dương. Hình 5.1 Các hệ trục tọa độ Hệ tọa độ thuần nhất: Mỗi điểm (x,y,z) trong khơng gian Descartes được biểu diễn bởi một bộ bốn tọa độ trong khơng gian 4 chiều thu gọn (hx,hy,hz,h). Người ta thường chọn h=1. Các phép biến đổi tuyến tính là tổ hợp của các phép biến đổi sau : tỉ lệ, quay, biến dạng và đối xứng. Các phép biến đổi tuyến tính cĩ các tính chất sau:  Gốc tọa độ là điểm bất động  Ảnh của đường thẳng là đường thẳng  Ảnh của các đường thẳng song song là các đường thẳng song song  Bảo tồn tỉ lệ khoảng cách  Tổ hợp các phép biến đổi cĩ tình phân phối. 5.3.1 Phép biến đổi tỷ lệ Phép biến đổi tỷ lệ tạo thành bằng cách gán các giá trị cho đường chéo chính của ma trận biến hình tổng quát 4×4 . Một điểm 65
25. P(x, y, z) được biến đổi tỷ lệ thành P(x’, y’, z’) bằng phép biến đổi sau: (5-1) Phép biến đổi được coi là phép tỷ lệ theo gốc tọa độ. Nếu các hệ số A, E khác nhau thì hình ảnh của đối tượng sẽ biến dạng. Ngược lại, thì kìch thước đối tượng cĩ thể thay đổi nhưng tỷ lệ với gốc tọa độ vẫn giữ nguyên. 5.3.2 Phép biến dạng Phép biến dạng ba chiều tạo ra sự biến dạng cho đối tượng bởi việc thay giá trị của một hoặc nhiều tọa độ bằng các hệ số tỷ lệ của cột thứ ba. Cách thực hiện trên là biến dạng theo mặt phẳng tạo ra bởi hai trục tọa độ được điều khiển bởi trục thứ ba. Các thành phần Ngồi đường chéo chính của ma trận con 3×3 phía trên của ma trận biến hình tổng quát ảnh hưởng đến phép biến dạng. 66
26. Ma trận biến dạng theo trục X: (5-2) Ma trận biến dạng theo trục Y: (5-3) Ma trận biến dạng theo trục Z: (5-4) Ví dụ: Cho 3 điểm A, B, C cĩ tọa độ lần lượt là A(-1,-6, 8); B(6, 0, -39); C(4, 0, -2). Hãy tìm tọa độ mới của các điểm trên qua phép biến đổi 67
27. tỷ lệ, hệ số biến đổi theo trục x là 2, trục y là 3 và trục z là 1 Hướng dẫn: Tìm ma trận lần lượt của 3 điểm A, B, C theo hệ số biến dạng theo trục x, trục y và trục z 5.3.3 Phép tịnh tiến Ma trận biến đổi hình sẽ thay đổi điểm P(x, y, z) thành P(x’, y’, z’) bằng phép biến đổi sau: Các giá trị J, K, L mơ tả sự tịnh tiến tương đối theo các hướng x, y, z. 5.3.4 Phép quay hình Phép quay trong khơng gian là quan trọng để tìm hiểu hình dạng của đối tượng hoặc kiểm tra quá trình thiết kế ở các gĩc độ khác nhau. So với phép quay hai chiều, phép quay ba chiều khĩ hơn vì phải sử dụng trục quay thay thế điểm quay. Các phép quay được phân tích dựa vào các phép quay quanh các trục chính Ma trận quay quanh trục X: 68
28. Ma trận quay quanh trục Y: Ma trận quay quanh trục Z: 69
29.  Đối với phép quay trong hệ trục tọa độ theo quy tắc bân tay trái, chỉ cần thay đổi hệ số gĩc quay θ thành - θ là xong. Bài tập áp dụng Bài 1 Các kiến thức mơ tả trong chương xét trong hệ tọa độ Đề các theo quy tắc bàn tay trái hay bàn tay phải. Bài 2 Xác định ma trận của phép đối xứng qua trục X, Y, Z. Bài 3 Xác định điểm Q là ảnh của điểm P cho trước phép biến dạng theo trục tung, với các hệ số biến dạng là 2. Bài 4 Xác định ma trận của phép quay gĩc 90o quanh trục, đi qua 2 điểm Po(0, 0) P1 ( 10, -10) f à 70
30. CHƢƠNG VI QUAN SÁT TRONG KHƠNG GIAN BA CHIỀU 6.1. Các phép chiếu Trong đồ họa hai chiều, các thao tác quan sát biến đổi các điểm hai chiều trong mặt phẳng tọa độ thực thành các điểm hai chiều trong mặt phẳng hệ tọa độ thiết bị. Sự định nghĩa đối tượng, bị cắt bởi một cửa sổ, được ánh xạ vào một Vùng quan sát. Các hệ tọa độ thiết bị chuẩn hĩa này sau đĩ được biến đổi sang các hệ tọa độ thiết bị, và đối tượng được hiển thị lên thiết bị kết xuất. Đối với đồ họa ba chiều, việc làm này phức tạp hơn một chưt, vì bãy giờ cĩ vài chọn lựa để cĩ thể quan sát ảnh như thế nào. Chúng ta cĩ thể quan sát ảnh từ phìa trước, từ phía trên, hoặc từ phía sau. Hoặc chúng ta cĩ thể tạo ra quang cảnh về những gỵ chúng ta cĩ thể thấy nếu chúng ta đang đứng ở trung tãm của một nhĩm các đối tượng. Ngồi ra, sự mơ tả các đối tượng ba chiều phải được chiếu lên bề mặt quan sát của thiết bị xuất. Trong chương này, trước hết chúng ta sẽ thảo luận các cơ chế của phép chiếu. Sau đĩ, các thao tác liên quan đến phép biến đổi cách quan sát, và đầy đủ các kỹ thuật quan sát ảnh ba chiều sẽ được phát triển. Cĩ hai phương pháp cơ bản để chiếu các đối tượng ba chiều lên bề mặt quan sát hai chiều. Tất cả các điểm của đối tượng cĩ thể được chiếu lên bề mặt theo các đường thẳng song song, hoặc các điểm cĩ thể được chiếu theo các đường hội tụ về một điểm được gọi là tâm chiếu. Hai phương pháp này được gọi là phép chiếu song song và phép chiếu phối cảnh. 71
31. Hình 6.1. Phƣơng pháp chiếu một đoạn thẳng lên bề mặt của mặt phẳng chiếu Trong cả hai trường hợp, giao điểm của đường chiếu với bề mặt quan sát xác định các tọa điểm của điểm được chiếu lên mặt phẳng chiếu này. Chúng ta giả sử rằng mặt phẳng chiếu là mặt z = 0 của hệ tọa độ bàn tay trái. Phép chiếu song song bảo tồn mối quan hệ về chiều của các đối tượng, và đây là kỹ thuật được dùng trong việc phác thảo để tạo ra các bức vẽ tỷ lệ của các đối tượng ba chiều. Phương pháp này được dùng để thu các hình ảnh chính xác ở các phía khác nhau của một đối tượng. Tuy nhiên, phép chiếu song song khơng cho một hình ảnh thực tế của các đối tượng ba chiều. Ngược lại, phép chiếu phối cảnh tạo ra các hình ảnh thực nhưng khơng bảo tồn các chiều liên hệ. 72
32. 6.1.1 Phép chiếu song song Các hình ảnh được hình thành bằng phép chiếu song song cĩ thể được xác định dựa vào gĩc hợp bởi hướng của phép chiếu hợp với mặt phẳng chiếu. Khi hướng của phép chiếu vuơng gĩc với mặt phẳng, ta cĩ phép chiếu trực giao (hay phép chiếu vuơng gĩc – orthographic projection). Một phép chiếu cĩ thể khơng vuơng gĩc với mặt phẳng chiếu được gọi là phép chiếu xiên. Hình 6.2 Phép chiếu cùng kích thƣớc của một đối tƣợng lên bề mặt quan sát Các phép chiếu trực giao đa số được dùngđể tạo ra quang cảnh nhìn từ phìa trước, bên sườn, và trên đỉnh của đối tượng. Quang cảnh phìa trước, bên sườn, và phía sau của đối tượng được gọi là “mặt chiếu”, và quang cảnh phía trên được gọi là “mặt phẳng” . Các bản vẽ trong kỹ thuật thường dùng các phép chiếu 73
33. trực giao này, vì các chiều dài và gĩc miêu tả chính xác và cĩ thể đo được từ bản vẽ. Chúng ta cũng cĩ thể xây dựng các phép chiếu trực giao để cĩ thể quan sát nhiều hơn một mặt của một đối tượng. Các quang cảnh như thế được gọi là các phép chiếu trực giao trục lượng học. Hầu hết phép chiếu trục lượng học được dùng là phép chiếu cùng kìch thước. Một phép chiếu cùng kìch thước được thực hiện bằng việc sắp xếp song song mặt phẳng chiếu mà nĩ cắt mỗi trục tọa độ ở nơi đối tượng được định nghĩa (được gọi là các trục chính) ở các khoảng cách như nhau từ ảnh gốc. Hình trình bày phép chiếu cùng kích thước. Cĩ tám vị trí, một trong tám mặt, đều cĩ kìch thước bằng nhau. Tất cả ba trục chình được vẽ thu gọn bằng nhau trong phép chiếu cùng kìch thước để kìch thước liên hệ của các đối tượng được bảo tồn. Đây khơng là trường hợp phép chiếu trực giao trục lượng học tổng quát, khi mà các hệ số tỷ lệ theo ba trục chính cĩ thể khác nhau. 74
34. Hình 6.3 Ba phép chiếu trực giao của một đối tƣợng. Các phương trính biến đổi để thực hiện một phép chiếu song song trực giao thì dễ hiểu. Đối với điểm bất kỳ (x, y, z), điểm chiếu (xp, yp, xp) trên bề mặt chiếu được tình như sau: xp = x, yp = y, zp = 0 (6-1) Một phép chiếu xiên đạt được bằng việc chiếu các điểm theo các đường thẳng song song, các đường thẳng này khơng vuơng gĩc với mặt phẳng chiếu. Hình 6.3 trình bày hình chiếu xiên của điểm (x, y, z) theo một đường thẳng chiếu đến vị trí (xp, yp). Các tọa độ chiếu trực giao trên mặt phẳng chiếu là (x, y). Đường thẳng của phép chiếu xiên tạo một gĩc α với đường thẳng trên mặt phẳng chiếu (đây là đường nối điểm (xp, yp) với điểm (x, 75
35. y)). Đường này, cĩ chiều dài L, hợp một gĩc φ với phương ngang trên mặt phẳng chiếu. Chúng ta cĩ thể diễn tả các tọa độ chiếu qua các số hạng x, y, L, và φ: xp = x + L cosφ (6-2) yp = y + L sinφ 6.1.2 Phép chiếu phối cảnh Để đạt được phép chiếu phối cảnh của đối tượng ba chiều, chúng ta chiếu các điểm theo đường thẳng chiếu để các đường này gặp nhau ở tâm chiếu. Trong dưới đây, tãm chiếu trên trục z và cĩ giá trị âm, cách một khoảng d phía sau mặt phẳng chiếu. Bất kỳ điểm nào cũng cĩ thể được chọn làm tâm của phép chiếu, tuy nhiên việc chọn một điểm dọc theo trục z sẽ làm đơn giản việc tính tốn trong các phương trình biến đổi. Hình 6.4 Phép chiếu phối cảnh của điểm P ở tọa độ (x, y, z) thành điểm P’(x’, y’, 0) trên mặt phẳng chiếu. 76
36. Chúng ta cĩ thể đạt được các phương trính biến đổi cho phép chiếu phối cảnh từ các phương trính tham số mơ tả các đường chiếu từ điểm P đến tâm chiếu. Các tham số xây dựng các đường chiếu này là: x’ = x - xu y’ = y - yu (6-5) z’ = z - (z + d)u Tham số u lấy giá trị từ 0 đến 1, và các tọa độ (x’, y’, z’) thể hiện cho bất kỳ điểm nào dọc theo đường thẳng chiếu. Khi u = 0, điểm P ở tọa độ (x, y, z). Ở đầu mút kia của đường thẳng u =1, và chúng ta cĩ các tọa độ của tâm chiếu, (0, 0, d). Để thu được các tọa độ trên mặt phẳng chiếu, chúng ta đặt z’ = 0 và tìm ra tham số u 6.2 Điểm tụ Khi các đối tượng ba chiều đựợc chiếu lên một mặt phẳng dùng các phương trính biến đổi phối cảnh, bất kỳ tập hợp các đường thẳng song song nào của đối tượng mà khơng song song với mặt phẳng chiếu được chiếu thành các đường hội tụ (đồng quy). Các đường thẳng song song với mặt phẳng khi chiếu sẽ tạo ra các đường song song. Điểm mà tại đĩ tập hợp các đường thẳng song song được chiếu xuất hiện hội tụ về đĩ được gọi là điểm tụ. Mỗi tập hợp các đường thẳng song song được chiếu như thế sẽ cĩ một điểm tụ riêng . 77
37. Hình 6.5 Các quang cảnh phối cảnh của một hình lập phƣơng. Điểm tụ cho bất kỳ tập các đường thẳng, tức các đường song song với một trong các trục tọa độ thực được nĩi đến như một điểm tụ chính. Chúng ta quản lý số lượng các điểm tụ chính (một, hai, hoặc ba) với hướng của mặt phẳng chiếu, và các phép chiếu phối cảnh được phân loại dựa vào đĩ để cĩ các phép chiếu: một-điểm, hai-điểm, hoặc ba-điểm. Số lượng các điểm tụ chính trong một phép chiếu được xác định bởi số lượng các trục của hệ tọa độ thực cắt mặt phẳng chiếu. Hình trên minh họa hình ảnh của các phép chiếu phối cảnh một-điểm và hai-điểm của hình lập phương. 78
38. Trong hình 6.5(b), mặt phẳng chiếu cĩ phương song song với mặt xy để chỉ cĩ trục z bị cắt. Phương này tạo ra phép chiếu phối cảnh một-điểm với một điểm tụ trên trục z. Với quang cảnh trong hình 6.5(c), mặt phẳng chiếu cắt cả hai trục x và z nhưng khơng cắt trục y. Kết quả, phép chiếu phối cảnh hai-điểm này chứa cả hai điểm tụ: trên trục x và trên trục z. 6.3. Loại bỏ mặt khuất Một vấn đề cần được quan tãm đến trong việc tạo ra các hình ảnh thực là sự xác định và xĩa bỏ các phần của đối tượng hình học mà ta khơng nhìn thấy được từ một vị trí quan sát. Cĩ nhiều tiếp cận chúng ta cần để giải quyết vấn đề này, và cũng cĩ nhiều thuật tốn khác nhau đã và đang được phát triển để xĩa bỏ các phần bị che khuất một cách hiệu quả cho những loại ứng dụng khác nhau. Cĩ phương pháp tốn bộ nhớ, một số khác cần nhiều thời gian xử lý hay chỉ áp dụng được cho những kiểu đối tượng đặc biệt. Các thuật tốn về đường khuất và mặt khuất dựa vào xử lý trực tiếp định nghĩa đối tượng hay xử lý hình chiếu của các đối tượng đĩ. Hai tiếp cận này được gọi là các phương pháp khơng gian đối tượng và các phương pháp khơng gian ảnh. Phương pháp khơng gian đối tượng xác định các thành phần của đối tượng được nhìn thấy bằng cách sử dụng các quan hệ hình học và khơng gian. Nĩ thực hiện với độ chính xác từ dữ liệu mơ tả đối tượng. Trong thuật tốn khơng gian ảnh, tính chất nhìn thấy được của một điểm được quyết định bởi điểm ở vị trí pixel trên mặt phẳng chiếu. Hầu hết các thuật tốn khử mặt khuất dùng phương pháp khơng gian ảnh, tuy nhiên các phương pháp khơng gian đối tượng vẫn cĩ thể được dùngmột cách hiệu quả cho một số trường hợp. 79
39. Các thuật tốn khử đường khuất hầu hết dùng phương pháp khơng gian đối tượng, dù rằng nhiều thuật tốn khử mặt khuất khơng gian ảnh cĩ thể dễ dàng được chỉnh sửa cho việc khử đường khuất. 6.3.1 Phương pháp mặt sau Một phương pháp khơng gian đối tượng đơn giản là phương pháp mặt sau, dựa vào các phương trình mặt phẳng: Ax + By + Cz + D = 0 Bất kỳ điểm (x’, y’, z’) trên hệ tọa độ bân tay trái sẽ ở “phìa trong” mặt này nếu nĩ thỏa bất phương trình: Ax’ + By’ + Cz’ + D < 0 Nếu điểm (x’, y’, z’) là vị trì quan sát, khi đĩ bất kỳ mặt phẳng nào làm cho bất phương trình đúng phải là một mặt ở đằng sau. Tức là, nĩ là mặt ta khơng thể nhìn thấy từ vị trí quan sát. Hình 6.6 Một mặt phẳng với tham số C < 0 Chúng ta cĩ thể thực hiện một cách kiểm tra mặt đằng sau đơn giản hơn bằng cách nhìn ở vector pháp tuyến của mặt cĩ phương trính 7-1, vector này cĩ tọa độ Descartes (A, B, C). Trong hệ tọa độ bân tay phải với hướng quan sát cùng chiều với trục z 80
40. âm (xem hình 6.6), vector cĩ tham số C song song với hướng quan sát. Nếu C 0 khi hướng quan sát cùng hướng với trục z dương. Trong tất cả các thảo luận sau này trong chương, chúng ta giả sử rằng hệ quan sát bân tay trái được dùng. Hình 6.7 Trong hệ quan sát bân tay trái, khi hƣớng quan sát cùng chiều với trục zv dƣơng, một mặt ở đằng sau là mặt với tham số C>0. Bằng việc kiểm tra tham số C ở mỗi mặt của đối tượng, ta cĩ thể xác định được ngay tất cả các mặt ở đằng sau. Đối với một khối đa diện lồi đơn lẻ, như hính kim tự tháp trong hình 6.10, việc kiểm tra này xác định tất cả các mặt bị che khuất trên đối tượng, bởi vì mỗi mặt thí là hồn tồn được nhìn thấy hoặc hồn tồn bị che khuất. Đối với các đối tượng khác, các kiểm tra phức tạp hơn cần được thực hiện để xác định xem các mặt là bị che khuất hồn tồn hay chỉ bị che khuất một phần. 81
41. Hình 6.8 Ảnh một đối tƣợng với một mặt bị che khuất một phần Tương tự, chúng ta cần xác định xem các đối tượng là cĩ một phần hay tồn bộ bị che khuất bởi các đối tượng khác. Một cách tổng quát, việc khử mặt khuất sẽ loại bỏ khoảng một nửa số mặt trong một ảnh khi thực hiện các phép kiểm tra. 82
42. MỤC LỤC Trang Lời nĩi đầu 1 Chƣơng 1. Tổng quan về đồ họa máy tính 2 1.1. Giới thiệu tổng quan 2 1.1.1. Lịch sử phát triển của đồ họa máy tình 2 1.2. Các ứng dụng tiêu biểu của kỹ thuật đồ họa máy tình 4 1.2.1. Ứng dụng CAD/CAM 4 1.2.2. Ứng dụng biểu diễn thơng tin 6 1.2.3. Ứng dụng hoạt hính và nghệ thuật 7 1.2.4. Ứng dụng đào tạo 8 1.2.5. Ứng dụng xây dựng giao diện người dùng 9 1.2.6. Ứng dụng xây dựng bản đồ 10 1.2.7. Ứng dụng trong y tế 11 1.3. Tổng quan về một hệ tọa độ 12 1.3.1. Phần cứng đồ họa 13 1.3.2. Phần mềm đồ họa 14 1.3.3. Hệ tọa độ thực, hệ tọa độ thiết bị và hệ tọa độ chuẩn 15 1.3.4. Hệ màu 17 Chƣơng 2. Các thuật tốn cơ sở 20 2.1. Giới thiệu 20 2.1.1. Các đối tượng đồ họa cơ sở 20 2.1.2. Các thuộc tình của các đối tượng đồ họa cơ sở 21 2.2. Các thuật tốn vẽ đường thẳng 22 2.2.1. Thuật tốn vẽ đường thẳng 22 2.2.2. Thuật tốn DDA 22 2.2.3. Thuật tốn Bresenham 25 83
43. 2.2.4. Thuật tốn MidPoint 29 2.3. Thuật tốn vẽ đường trịn, elip 33 2.3.1. Thuật tốn MidPoint 35 2.3.2. Thuật tốn Bresenham 38 2.3.3. Thuật tốn vẽ Elip 41 Chƣơng 3. Biến đổi trong khơng gian hai chiều 42 3.1. Các phép biến đổi cơ bản 42 3.1.1. Phép tịnh tiến 42 3.1.2. Phép biến đổi tỷ lệ 43 3.1.3 Phép đối xứng 43 3.1.4 Phép quay 44 3.2. Kết hợp các phép biến đổi 45 3.2.1. Kết hợp các phép tịnh tiến 45 3.2.2. Kết hợp các phép biến đổi tỷ lệ 45 3.2.3. Kết hợp các phép quay 46 3.2.4. Một số phép biến đổi khác 46 3.3. Phép biến đổi giữa các hệ tọa độ 47 Chƣơng 4. Phép quan sát hai chiều 48 4.1. Cửa sổ và vùng quan sát 48 4.2. Phép biến đổi cửa sổ - Vùng quan sát 50 4.3. Phép cắt xén hai chiều (Clipping) 50 4.3.1. Giải thuật Cohen – Suntherland 53 4.3.2. Giải thuật chia tại trung điểm 56 4.3.3. Giải thuật Liang – Basky 57 Chƣơng 5. Đồ họa ba chiều 60 5.1. Tổng quan về đồ họa ba chiều 60 5.1.1. Quy trính hiển thị đồ họa ba chiều 60 5.1.2. Mơ hính hĩa đối tượng 61 84
44. 5.2. Biểu diễn đối tượng ba chiều 62 5.2.1. Biểu diễn mặt đa giác 62 5.2.2. Đường cong và mặt cong, đường cong và mặt cong Bezier, B-spline 63 5.3. Các phép biến đổi hính học ba chiều 64 5.3.1. Phép biến đổi tỷ lệ 65 5.3.2. Phép biến dạng 66 5.3.3. Phép tịnh tiến 68 5.3.4. Phép quay hình 68 Chƣơng 6. Quan sát trong khơng gian ba chiều 71 6.1. Các phép chiếu 71 6.1.1. Phép chiếu song song 73 6.1.2. Phép chiếu phối cảnh 76 6.2. Điểm tụ 77 6.3. Loại bỏ mặt khuất 79 6.3.1. Phương pháp mặt sau 80 85
45. TÀI LIỆU THAM KHẢO [1] Đặng Văn Đức Kỹ thuật đồ họa máy tình, Viện Cơng nghệ thơng tin, 2002 [2] Phan Hữu Phúc Cơ sở đồ họa máy vi tình, NXB Giáo dục, 2000 T 86