Câu hỏi ôn tập Lý thuyết đồ họa máy tính

Nội dung text: Câu hỏi ôn tập Lý thuyết đồ họa máy tính

1. Câu 1. Đồ họa máy tính là gì? Cho biết các ứng dụng của đồ họa máy tính?  Khái niệm ĐHMT - Đồ họa máy tính là tất cả những gì liên quan đến việc sử dụng máy tính để phát sinh ra hình ảnh. Các vấn đề liên quan tới công việc này bao gồm : tạo, lưu trữ, thao tác trên các mô hình (các mô tả hình học của đối tượng) và các ảnh. - Đồ họa máy tính bao gồm việc thiết kế phần cứng như thiết bị hiển thị, các thuật toán cần thiết để phát sinh các đƣờng trên các thiết bị này, các phần mềm đƣợc sử dụng cho cả ngƣời lập trình hệ thống và người lập trình ứng dụng đồ họa, và các chƣơng trình ứng dụng tạo ảnh bằng máy tính. - Đồ họa máy tính tƣơng tác là một trong những phƣơng tiện mang lại thêm nhiều sự thuận lợi cho ngƣời dùng trong việc phát sinh hình ảnh kể từ khi có phát minh của máy ảnh và truyền hình.  Các ứng dụng của đồ họa máy tính  Hỗ trợ thiết kế (CAD/CAM) CAD: Computer Aided Design, CAM: Computer Aided Manufacture - Đồ họa máy tính đƣợc ứng dụng trong việc thiết kế các thành phần và hệ thống cơ khí, điện, các thiết bị điện tử, xây dựng, hệ thống cáp quang, mạng điện thoại, thiết kế các mạch điện tử Những phần liên quan đến thiết kế và vẽ đƣợc thực hiện trực tiếp trên màn hình nhờ những công cụ trợ giúp đồ họa  Xây dựng giao diện ngƣời dùng (User Interface) - Mọi ứng dụng đều phải có giao diện giao tiếp với ngƣời dùng. Các ứng dụng dựa trên hệ điều hành MS Windows là một minh họa rất trực quan của giao diện đồ họa. Các chức năng của các ứng dụng này đƣợc thiết kế cho ngƣời dùng làm việc thông qua các biểu tƣợng mô tả chức năng đó. - Các ứng dụng có giao diện đồ họa còn cho phép ngƣời dùng khả năng làm việc dễ dàng với nhiều cửa sổ với nhiều dạng tài liệu khác nhau cùng một lúc.  Biểu diễn thông tin - Đây là các ứng dụng sử dụng đồ họa máy tính để phát sinh các biểu đồ, đồ thị, dùng minh họa mối quan hệ giữa nhiều đối tƣợng với nhau. Các ứng dụng này thƣờng đƣợc dùng để tóm lƣợc các dữ liệu về tài chính, thống kê, kinh tế, khoa học, toán học, giúp cho việc nghiên cứu, quản lí, một cách có hiệu quả.  Tự động hoá văn phòng và chế bản điện tử - Có thể tạo ra các văn bản điện tử và các văn bản sao chép cứng nhƣ tài liệu, biểu, các hình vẽ, hình ảnh.  Lĩnh vực giải trí, nghệ thuật. 1
2. + Sản xuất phim hoạt hình và tạo các hiệu ứng đặc biệt. + Trò chơi máy tính. + Duyệt Web  Ứng dụng trong tự động hóa và điều khiển - Những hệ thống phức tạp nhƣ nhà máy điện, hệ thống điều khiển không lƣu cần phải có sự theo dõi giám sát cẩn thận. Thông thƣờng phải bố trí ít nhất một nhân viên giám sát để canh chừng những sự cố có thể xảy ra. Họ đƣợc cung cấp thông tin hiện tại của hệ thống trên màn hình trạng thái dƣới dạng dễ hiểu và dễ nắm bắt nhất. Quá trình đo đạc trong hệ thống đƣợc tiến hành liên tục và dữ liệu đƣợc gửi đến trạm giám sát, ở đó nó đƣợc chuyển đổi thành biểu diễn đồ họa và hiển thị trên màn hình.  Mô phỏng - Trong số các đối tƣợng đƣợc thể hiện trực quan bằng đồ họa, có một số đối tƣợng tồn tại trong thực tế và có thể tiến hành đo đạc theo thời gian thực. Trong khi đó một số đối tƣợng chƣa bao giờ đƣợc xây dựng trong thực tế mà chỉ tồn tại dƣới dạng phƣơng trình hay thuật toán trong máy tính. Tuy vậy chúng vẫn có thể đƣợc kiểm tra vận hành nhƣ thể chúng tồn tại thực sự. Đồ họa máy tính có khả năng hiển thị những đối tƣợng này nhƣ thể chúng tồn tại, trong khi chúng chỉ là các mô hình đƣợc mô tả bên trong máy tính.  Lĩnh vực bản đồ (Cartography) - Đồ họa máy tính đƣợc sử dụng để đƣa ra sơ đồ vị trí địa lý và các hiện tƣợng tự nhiên một cách chính xác từ những số liệu đo đạc đƣợc. Ví dụ nhƣ bản đồ địa lý, bản đồ thời tiết, bản đồ mật độ dân số, bản đồ khai thác cho khoan và khao thác mỏ, bản đồ hải dƣơng học  Giáo dục và đào tạo - Có thể dùng đồ họa để nghiên cứu các thực thể trìu tƣợng, mô phỏng cấu trúc của vật thể, tiến trình của các phản ứng hóa học trong chất lỏng, của hạt nhân, hệ thống sinh lý, hoạt động của các gói tin trên mạng máy tính đƣợc dùng rất nhiều trong việc hỗ trợ giảng dạy. Trong đào tạo, các ứng dụng mô phỏng đƣợc dùng để kiểm tra trình độ ngƣời lái, huấn luyện phi công, điều khiển giao thông  Hình ảnh hóa số liệu khoa học: - Số liệu khoa học thƣờng rất phức tạp, quan hệ giữa các đại lƣợng thực nghiệm thƣờng rất khó hình dung. Đồ họa máy tính cung cấp một công cụ tuyệt vời để thể hiện thông tin khoa học dƣới dạng dễ tƣởng tƣợng và dễ nắm bắt nhất. Câu 2: Trình bày hệ hiển thị thiết bị dạng Raster và Vecto?.  Phương thức hiển thị Raster - Tia điện tử quét ngang trên màn hình từ trái qua phải, khi quét hết một dòng ngang, tia điện tử đƣợc dập tắt và lái hồi về đầu dòng tiếp. 2
3. - Mỗi điểm ảnh trên màn hình đƣợc gọi là pixel. - Ảnh hiển thị theo công nghệ Raster là các đƣờng raster nằm ngang, mỗi đƣờng là một hàng gồm nhiều pixel. Hệ hiển thị Raster lƣu trữ dƣới dạng ma trận các điểm ảnh biểu diễn toàn bộ màn hình. - Sự bật tắt các điểm sáng trên màn hình phụ thuộc vào cƣờng độ của tia điện tử và đây chính là cơ sở của việc tạo ra hình ảnh trên màn hình. - Ưu điểm: Nguyên lý hoạt động tƣơng tự nhƣ tivi, hình ảnh tạo ra tƣơng đối tốt. - Nhược điểm: xảy ra hiệu ứng bậc thang. Phương pháp để tạo ra các pixel - Phương pháp dùng phần mềm để vẽ trực tiếp từng pixel một. - Dựa trên các lý thuyết mô phỏng để xây dựng nên hình ảnh mô phỏng của sự vật. - Phương pháp rời rạc hoá (số hoá) hình ảnh thực của đối tượng. - Có thể sửa đổi hoặc xử lý mảng các pixel thu được theo những phương pháp khác nhau để thu được hình ảnh đặc trưng của đối tượng.  Phương thức hiển thị vector - Quét vector theo tọa độ các điểm đầu và cuối vector. Ngƣời ta sử dụng các cuộn lái tia để quét thành các đoạn thẳng và nhƣ thế để vẽ đƣợc một đối tƣợng đồ họa ngƣời ta phải phân tích đối tƣợng thành các đoạn thẳng cơ sở và lần lƣợt vẽ chúng. - Chỉ di chuyển một số lần cần thiết để tạo ra hình ảnh. Khi đang ở giữa hai điểm mút của đoạn thẳng định vẽ thì chùm tia không bao giờ bị tắt. - Ưu điểm: + Thích hợp cho việc hiển thị các đối tƣợng hình học + Không bị hiệu ứng bậc thang + Tốn ít bộ nhớ - Nhƣợc điểm: + Với các ảnh phức tạp, cần thời gian vẽ lớn. - Một số loại thiết bị là “máy” vẽ đƣờng thẳng. Ví dụ máy vẽ (pen plotter). Nó di chuyển bút vẽ đến một vị trí nào đó đƣợc chỉ định bởi máy tính, đặt bút xuống, sau đó kéo bút đến một vị trí khác, để lại vết mực với màu sắc nào đó. 3
4. - Ngoài ra cũng có loại màn hình đƣợc gọi là màn hình “vector” hay màn hình “random -scan”. Loại màn hình này có mạch điện tử đƣợc thiết kế để quét chùm tia điện tử từ điểm này đến điểm khác trên bề mặt của ống tia âm cực, và để lại vệt sáng. Câu 3. Trình bày hệ tọa độ thế giới thực, hệ tọa độ thiết bị, hệ tọa độ chuẩn?  Hệ toạ độ thế giới thực (WCS: World Coordinate System) - WCS hay hệ toạ độ thực là hệ toạ độ đƣợc dùng mô tả các đối tƣợng trong thế giới thực. - Một trong hệ toạ độ thực đƣợc dùng nhiều nhất là hệ toạ độ Descartes. Bất kì điểm nào trong mặt phẳng đƣợc mô tả bằng cặp toạ độ (x,y) trong đó x,y ốc toạ độ là điểm O có toạ độ (0,0), Ox,Oy lần lƣợt là trục hoành và trục tung và x,y là hoành độ và tung độ. - Các toạ độ thế giới thực cho phép ngƣời sử dụng bất kì một thứ nguyên (dimension) qui ƣớc: foot, cm, nm, km, inch tuỳ ý.  Hệ toạ độ thiết bị (DCS: Device Coordinate System) - Hệ toạ độ thiết bị là hệ toạ độ đƣợc dùng bởi một thiết bị xuất cụ thể nào đó như máy in, màn hình - Các điểm đƣợc biểu diễn bởi cặp toạ độ (x,y), nhƣng x,y N. Điểm trong toạ độ thực đƣợc định nghĩa liên tục, còn trong toạ độ thiết bị thì rời rạc do tính chất của tập các số tự nhiên. - Các toạ độ (x,y) có giới hạn trong một khoảng nào đó. Khoảng giới hạn các tọa độ x, y là khac nhau đối với từng thiết bị khác nhau.  Hệ tọa độ thiết bị chuẩn (Normalized device coordinates) - Do cách định nghĩa các hệ tọa độ thiết bị khác nhau nên một hình ảnh hiển thị đƣợc trên thiết bị này là chính xác thì chƣa chắc hiển thị chính xác trên thíết bị khác. - Ngƣời ta xây dựng một hệ tọa độ thiết bị chuẩn đại diện chung cho tất cả các thiết bị để có thể mô tả các hình ảnh mà không phụ thuộc vào bất kỳ thiết bị nào. 4
5. - Trong hệ tọa độ chuẩn, các tọa độ x, y sẽ đƣợc gán các giá trị trong đoạn từ [0,1]. Nhƣ vậy, vùng không gian của hệ tọa độ chuẩn chính là hình vuông đơn vị có góc trái dƣới (0, 0) và góc phải trên là (1, 1). - Quá trình mô tả các đối tƣợng thực nhƣ sau: Câu 4. Trình bày nguyên lý chung vẽ đoạn thẳng ?  Nguyên lý chung Đầu vào: cho 2 điểm đầu mút (x1,y1) (x2,y2), màu vẽ C. Phương trình đƣờng thẳng đi qua 2 điểm đầu mút: (x-x1)/(y-y1) = (x2-x1)/(y2-y1) => Y=(y2-y1)*(x-x1)/(x2-x1)+y1 Đặt m= (y2-y1)/(x2-x1) b= y1-mx1 ta có phƣơng trình y=mx+b m đƣợc gọi là độ dốc hay hệ số góc của đƣờng thẳng, b đƣợc gọi là đoạn chắn trên trục y. - Từ phƣơng trình này chúng ta có thể xây dựng quá trình vẽ các đƣờng thẳng khi cho x biến thiên các khoảng x và kết quả ta có thể thu đƣợc giá trị của y thay đổi với các khoảng y tƣơng ứng y=m x. - Hoặc có thể làm ngƣợc lại cho y biến thiên từng khoảng y và kết quả ta có thể thu đƣợc giá trị của x thay đổi các khoảng x tƣơng ứng x= y/m - Đơn vị nhỏ nhất của màn hình là một điểm ảnh nên thông thƣờng chọn x= 1 ( x= -1) hoặc y= 1 ( y= -1). - Nguyên lý chung là cho một thành phần tọa độ x hay nguyên biến đổi theo từng đơn vị và tính tọa độ nguyên còn lại sao cho gần với tọa độ thực nhất. Câu 5. Trình bày thuật toán DDA vẽ đoạn thẳng ? - Để đơn giản hóa giải thuật, chúng ta chỉ xét các đƣờng thẳng có hệ số góc m trong khoảng [0,1] và Dx>0. Mỗi bƣớc nhẩy của x trong mỗi lần tính tƣơng đƣơng một điểm ảnh. 5
6. Như vậy tại bước i+1: = + 1 Và tọa độ y tƣơng ứng 1= +m Vì m là số thực nên để thu đƣợc nguyên buộc ta phải làm tròn y trƣớc khi đƣa tọa độ truy xuất lên màn hình. - Với đƣờng thẳng có hệ số góc m>1, ta có thể cho x biến đổi theo y nghĩa là ở đây y đóng vai trò tăng và x đƣợc tính theo tƣơng ứng: = +1, = +1/m. Và chúng ta có thể tính tƣơng tự cho các trƣờng hợp còn lại. - Nhận xét: Độ chính xác của thuật toán cao, đoạn thẳng vẽ đƣợc thể hiện rất gần với đoạn thẳng thực tế. Tuy nhiên tốc độ tính toán chậm do phải thƣờng xuyên làm việc với các phép toán cộng số thực và làm tròn. Câu 6. Trình bày thuật toán Breshenham vẽ đoạn thẳng? - Đây là một phƣơng pháp có hiệu quả chỉ sử dụng cộng trừ các số nguyên và phép nhân. Thực tế cho thấy rằng, máy tính có thể biểu diễn phép cộng trừ các số nguyên một cách nhanh chóng, giải quyết đƣợc về mặt thời gian khi biểu diễn các phép nhân, chia cho lũy thừa của 2 vì chỉ phải sử dụng các phép dịch bit. - Xét đoạn thẳng có hệ số góc m [0,1] Dx>0 Lúc này bằng cách cho x tăng một đơn vị tại mỗi bƣớc, ta sẽ tìm cách tính y để vẽ các pixel tƣơng ứng. Giả sử ở bƣớc thứ k ta đã xác định các tọa độ nguyên (xk, yk) nhƣ vậy chúng ta cần xác định tọa độ ( , ) cho bƣớc kế tiếp Theo công thức ta có: = +1 6
7. Giá trị của có thể đƣợc chọn bởi một trong 2 giá trị yk hoặc yk+1. Điểm đƣợc chọn là điểm gần với y thực nhất. Xét khoảng cách d1, d2 từ y thực đến yk và đến yk+1 Gọi (xk+1,y) là điểm thuộc đoạn thẳng, ta có y=m(xk+1)+b d1 = y - yk = m(xk +1) + b - yk . d2 = yk+1 - y = yk + 1 - m(xk + 1) - b - Nếu d1 yk+1 = yk - Ngƣợc lại d1 >= d2 => yk+1 = yk +1 d1 - d2= 2m(xk + 1) - 2yk + 2b - 1 m=(y2-y1)/(x2-x1) Nếu xác định đƣợc dấu của d1-d2 thì sẽ biết đƣợc điểm ảnh nào gần với đoạn thẳng hơn. Xác định tham số quyết định Pk cùng dấu với d1-d2. Đặt Pk = (x2-x1) (d1 - d2) Do Dx>0 nên Pk cùng dấu với d1-d2 Pk = (x2-x1)[(2(y2-y1)(xk +1)+(x2-x1)(- 2yk +2b-1)]/(x2-x1) =2(y2-y1)xk-2(x2-x1)yk+c Trong đó c là hằng số đối với đoạn thẳng và c=2(y2-y1)+(x2-x1)(2b-1) Pk+1 =2(y2-y1)xk+1-2(x2-x1)yk+1+c Pk+1 tại bƣớc thứ k+1 đƣợc tính tăng dần bằng cách sử dụng giá trị Pk tại bƣớc thứ k nhƣ sau : +) Pk =0 d1>=d2 chọn yk+1=yk+1 7
8. Pk+1 =2(y2-y1)(xk+1)-2(x2-x1)(yk+1)+c = Pk +2(y2-y1)-2(x2-x1) Tính giá trị P1 khởi tạo : P1=2(y2-y1)x1-2(x2-x1)y1+2(y2-y1)+(2b-1)(x2-x1) Do (x1, y1) là điểm nguyên thuộc đoạn thẳng nên ta có y1=mx1+b = (Dy/Dx)*x1 + b. Thế vào phƣơng trình trên ta suy ra : P1=2(y2-y1)- (x2-x1) Câu 7. Thuật toán trung điểm vẽ đoạn thẳng (MidPoint) Xét đoạn thẳng có hệ số góc thuộc [0,1]. Dx>0 Tại mỗi bƣớc x tăng lên một đơn vị, y giữ nguyên hoặc tăng lên một đơn vị, chọn giá trị y gần với đƣờng thẳng nhất. Thuật toán MidPoint đƣa ra cách chọn yi+1 là yi hay yi+1 bằng cách so sánh điểm thực Q(xi+1, y) với điểm MidPoint là trung điểm của S và P. Ta có: + Nếu điểm Q nằm dƣới điểm MidPoint, ta chọn S. + Ngƣợc lại nếu điểm Q nằm trên điểm MidPoint ta chọn P. Ta có dạng tổng quát của phƣơng trình đƣờng thẳng: F(x,y)=Ax+By+C=0 A=y2-y1, B= -(x2-x1), C=x2y1-x1y2 F(x,y)=0 với mọi điểm (x,y) thuộc đƣờng thẳng F(x,y)>0 với các điểm (x,y) nằm phía dƣới đƣờng thẳng F(x,y)<0 với các điểm (x,y) nằm phía trên đƣờng thẳng 8
9. Lúc này việc chọn các điểm S, P ở trên đƣợc đƣa về việc xét dấu của pi=2F(M)=2F(xi+1, yi+0.5)= 2A(xi+1)+2B(yi+0.5)+C M là trung điểm của PS + Nếu pi =0, điểm M nằm phía dƣới đoạn thẳng. Lúc này điểm thực Q nằm phía trên điểm M nên ta chọn P tức là yi+1=yi+1 Pi+1=2F(xi+1+1, yi+1+0.5)=2F(xi+2, yi+1.5)= 2A(xi+2)+2B(yi+1.5)+C = pi+2A+2B=pi + 2Dy-2Dx Ta tính giá trị p1 ứng với điểm ban đầu (x1, y1), với nhận xét rằng (x1, y1) là điểm thuộc về đoạn thẳng, tức là ta có Ax1+By1+C=0. P1=2F(x1+1, y1+0.5)= 2A(x1+1)+2B(y1+0.5)+C = 2(Ax1+By1+C)+ 2A+B =2A+B= 2Dy-Dx Câu 8. Trình bày nguyên lý chung vẽ đường tròn? Trong hệ tọa độ Descartes, phƣơng trình đƣờng tròn bán kính R có dạng: Với tâm O(0,0) : + = 2 2 2 Với tâm C(xc, yc): (x-xc) + (y-yc) =R Trong hệ tọa độ cực : x = xc + R.cosθ, y=yc + R.sinθ với θ [0, 2π]. Do tính đối xứng của đƣờng tròn C nên ta chỉ cần vẽ 1/8 cung tròn, sau đó lấy đối xứng qua 2 trục tọa độ và 2 đƣờng phân giác thì ta vẽ đƣợc cả đƣờng tròn. Với đƣờng tròn tâm (xc, yc) ta có thể vẽ đƣờng tròn tâm (0,0) sau đó tịnh tiến theo vecto (xc, yc). Cho x = 0, 1, 2, , int(R x sqrt(2)/2) với R>1. - Tại mỗi giá trị x, tính int(y = sqrt(R2-x2)). 9
10. - Vẽ điểm (x,y) cùng 7 điểm đối xứng của nó. Một cách tiếp cận khác là vẽ các điểm (R cos (θ), R sin (θ)), với θ chạy từ 00 đến 900. Cách này sẽ khắc phục hạn chế đƣờng không liền nét của thuật toán trên, tuy nhiên điểm hạn chế chính của thuật toán này đó là chọn bƣớc nhảy cho θ nhƣ thế nào cho phù hợp khi bán kính thay đổi. Câu 9. Thuật toán trung điểm (MidPoint) vẽ đƣờng tròn Xét đƣờng tròn tâm tại gốc tọa độ, bán kính R. Xét cung 1/8 đƣờng tròn C(1/8), sau đó lấy đối xứng. Nhƣ vậy nếu có (x, y) thuộc (C1/8) thì các điểm : (y, x), (y,-x), (x,-y), (-x,-y), (y,-x), (-y,x), (-x,y) sẽ thuộc (C). Chọn điểm bắt đầu để vẽ là điểm (0,R). Dựa vào hình vẽ, nếu (xi, yi) là điểm nguyên đã tìm đƣợc ở bƣớc thứ i, thì (xi+1, yi+1) ở bƣớc thứ (i+1) là sự lựa chọn giữa S và P. Nhƣ vậy: xi+1 =xi+1 yi+1 ϵ {yi, yi-1} Tƣơng tự nhƣ thuật toán MidPoint vẽ đoạn thẳng, việc quyết định chọn một trong hai điểm S và P sẽ đƣợc thực hiện thông qua việc xét dấu của một hàm nào đó tại điểm MidPoint là điểm nằm giữa chúng. Đặt F(x,y)=x2+y2-R2, ta có F(x,y) 0 nếu (x,y) nằm ngoài đƣờng tròn Gọi M là trung điểm PS 2 2 2 Xét pi=F(M)=F(xi+1, yi-0.5)= (xi+1) + (yi-0.5) -R 10
11. 2 2 2 pi+1=F(xi+1+1, yi+1-0.5)= (xi+1+1) + (yi+1-0.5) - R Ta có : + Nếu pi =0, điểm M nằm ngoài đƣờng tròn. Lúc này điểm thực Q gần P hơn nên ta chọn P, tức là yi+1=yi-1 2 2 2 pi+1=F(xi+2, yi - 1.5)= (xi+2) + (yi-1.5) -R = pi+ 2xi-2yi+5 Tính giá trị p1 ứng với điểm ban đầu (x1, y1) = (0, R) P1=F(1, R-0.5)= 5/4 –R Câu 10. Trình bày nguyên lý thuật toán trung điểm vẽ đường elip? Nguyên lý chung Cho elip tâm (h, k), độ dài trục chính là a, độ dài trục phụ là b Phƣơng trình đƣờng elip đƣợc xác định nhƣ sau : (x-h)2/a2+(y-k)2/b2=1. Phƣơng trình elip với tâm tại gốc tọa độ x2/b2+y2/b2=1 Elip đƣợc chia thành 4 phần đối xứng qua 2 trục tọa độ, do vậy ta chỉ cần vẽ cung ¼ elip sau đó thực hiện lấy đối xứng để thu đƣợc các phần còn lại. Để vẽ elip tâm (h,k) ta có thể thực hiện vẽ elip tâm tại gốc tọa độ sau đó tịnh tiến theo véc tơ (h,k). Tại mỗi bƣớc ta cho x tăng từ 0 đến a sau đó tính giá trị y tƣơng ứng qua biểu thức trên, sau đó lấy giá trị nguyên gần với giá trị y thực nhất. Thuật toán trung điểm (MidPoint) vẽ elip Xét elip tâm tại gốc tọa độ. Phƣơng trình đƣờng elip: F(x,y)=b2x2+a2y2−a2b2=0 Xét vẽ cung ¼ elip, sau đó lấy đối xứng để thu đƣợc các phần còn lại 0<=x<=a 0<=y<=b 11
12. Chia cung ¼ elip này thành 2 vùng với điểm chia P là tiếp điểm của tiếp tuyến có hệ số góc là -1. Véc tơ gradient vuông góc với tiếp tuyến tại tiếp điểm đƣợc xác định nhƣ sau: GradF(x,y) = (∂F/∂x)i+(∂F/∂y)j=2b2x.i+2a2y.j Ta có tiếp tuyến với cung tròn (độ dốc) = -1 Vector gradient có độ dốc là 1, do đó tại P các thành phần i và j của vecto gradient có cùng độ lớn. 2 2 Trong vùng 1 thành phần j lớn hơn thành phần i của gradient. a (yp-0.5)>b (xp+1). Trong vùng 2 thì ngƣợc lại. + Xét trên phần 1: Bắt đầu từ (0,b), Tại mỗi bƣớc x tăng lên một đơn vị, y biến đổi theo x bƣớc thứ i (xi,yi), Ở bƣớc i+1 chọn tiếp A(xi+1, yi) hoặc B(xi+1,yi-1). Chọn điểm gần với đƣờng elip nhất dựa trên việc xét dấu của hàm F tại trung điểm M của AB. Tham số quyết định: 2 2 2 2 2 2 pi =F(M)= F(xi+1,yi-1/2) = b (xi+1) + a (yi-1/2) -a b 2 2 2 2 2 2 pi+1 = F(xi+1+1,yi+1-1/2) = b (xi+1+1) + a (yi+1-1/2) - a b - Nếu pi =0 chọn B: xi+1=xi+1 yi+1=yi -1 2 2 2 2 2 2 2 2 pi+1 = b (xi+2) + a (yi-1.5) -a b = pi + b (2xi +3) + a (-2yi +2) 2 2 2 2 2 2 2 2 - Tính P1 khởi tạo tại (0,b): p1 = F(1,b-1/2) = b + a (b-1/2) -a b = b - a b +a /4 + Xét trên phần 2: Ta lấy toạ độ của Pixel sau cùng trong phần 1 của đƣờng cong để tính giá trị ban đầu cho phần 2. Tại mỗi bƣớc y giảm từng đơn vị, x biến đổi theo y. Tại bƣớc j ta có điểm (xj,yj). Pixel ở bƣớc kế tiếp j+1 có thể là: C(xj,yj-1) hoặc D(xj+1, yj-1 12
13. Tham số quyết định: 2 2 2 2 2 2 qj =F(M)= F(xj+1/2,yj-1) = b (xj+1/2) + a (yj-1) -a b 2 2 2 2 2 2 qj+1 = F(xj+1 +1+1/2, yj+1 -1) = b (xj+1+1/2) + a (yj+1-1) -a b - Nếu qj =0 chọn C: yj+1 =yj-1, xj+1 = xj 2 2 2 2 2 2 2 2 2 2 2 2 2 qj+1 = b (xj+1+1/2) + a (yj+1-1) -a b = b (xj+1/2) + a (yj-2) -a b = qj + a (- 2yj+3) 2 2 2 2 2 2 - Tính q1 khởi tạo q1 = f(xp+1/2,yp -1) = b (xp+1/2) + a (yp-1) -a b Câu 11. Định nghĩa đa giác, cho biết cách vẽ một đa giác? Khái niệm đa giác Đa giác là thành phần cơ bản nhất của bề mặt. Việc biểu diễn đa giác có thể thông qua tập các đƣờng thẳng hay tập các điểm thuộc đa giác. Một đa giác là một đƣờng gấp khúc có điểm đầu và điểm cuối trùng nhau. Xây dựng cấu trúc dữ liệu để vẽ đa giác Type d_dinh = record x,y: longint; end; dinh = array[0 10] of d_dinh; var d: dinh; Với cách xây dựng cấu trúc dữ liệu nhƣ thế này thì chúng ta chỉ cần nhập vào tọa độ các đỉnh và sau đó gọi thủ tục vẽ đƣờng thẳng lần lƣợt qua 2 đỉnh nhƣ (0, 1), (1,2), , (n-1, n), trong đó đỉnh n trùng với đỉnh 0 thì ta sẽ vẽ đƣợc toàn bộ đa giác. Câu 12. Trình bày thuật toán tô màu dựa theo dòng quét? Giả sử vùng tô đƣợc cho bởi một đa giác N đỉnh : Pi(xi, yi),i=0, ,N-1. Đa giác này có thể là đa giác lồi, đa giác lõm, và cả đa giác tự cắt, Ta có thể tóm bắt các bƣớc chính của thuật toán : - Tìm ytop, ybottom lần lƣợt là giá trị lớn nhất, nhỏ nhất của tập các tung độ của các đỉnh của đa giác đã cho: 13
14. ytop= max{yi,(xi,yi) ϵ P}, ybottom= min{yi, (xi, yi)ϵP} - Ứng với mỗi dòng quét y=k, với k thay đổi từ ybottom đến ytop lặp : + Tìm tất cả các hoành độ giao điểm của dòng quét y=k với các cạnh của đa giác. + Sắp xếp các hoành độ giao điểm theo thứ tự tăng dần : x0, x1, + Tô màu các đoạn thẳng trên đƣờng thẳng y=k lần lƣợt đƣợc giới hạn bởi các cặp (x0,x1), (x2, x3), . Nếu chỉ dừng ở mức này và chuyển sang cài đặt, chúng ta sẽ gặp một số vấn đề sau : + Nhận xét rằng, ứng với mỗi dòng quét, không phải lúc nào tất cả các cạnh của đa giác cũng tham gia cắt dòng quét. + Việc tìm giao điểm của cạnh đa giác với mỗi dòng quét sẽ gặp các phép toán phức tạp nhƣ nhân, chia, trên số thực nếu ta dùng cách giải hệ phƣơng trình tìm giao điểm. + Nếu số giao điểm tìm đƣợc giữa các cạnh đa giác và dòng quét là lẻ thì việc nhóm từng cặp giao điểm kế tiếp nhau để hình thành các đoạn tô có thể sẽ không chính xác Nếu tính số giao điểm tại đỉnh dòng quét đi ngang qua là hai thì có thể sẽ cho kết quả tô không chính xác. Ngoài ra, việc tìm giao điểm của dòng quét với các cạnh nằm ngang là một trƣờng hợp đặc biệt cần phải có cách xử lí thích hợp. Câu 13. Trình bày thuật toán tô màu theo đường biên? Đường biên của vùng tô đƣợc xác định bởi tập các đỉnh của một đa giác, đƣờng biên trong thuật toán đƣợc mô tả bằng một giá trị duy nhất đó là màu của tất cả các điểm thuộc về đƣờng biên. Bắt đầu từ điểm nằm bên trong vùng tô, ta sẽ kiểm tra các điểm lân cận của nó đã đƣợc tô màu hay có phải là điểm biên hay không, nếu không phải là điểm đã tô và không phải là điểm biên ta sẽ tô màu nó. Quá trình này đƣợc lặp lại cho tới khi nào không còn tô đƣợc điểm nào nữa thì dừng. Có hai quan điểm về cách tô này, đó là dùng bốn điểm lân cận hay tám điểm lân cận đối với điểm đang xét đƣợc tô bằng màu trắng Hình 2.25: 4 điểm lân cận (a) và 8 điểm lân cận (b) 14
15. Nhận xét + Thuật toán này có thể sẽ không hoạt động chính xác khi có một số điểm nằm trong vùng tô có màu là màu cần tô của vùng (FillColor). (không kt đc 1 điểm đã tô hay chưa) + Gây tràn bộ nhớ nếu ảnh lớn. Câu 14. Trình bày các mô hình màu RGB, CMY, CMYK?  Mô hình màu RGB (Red, Green, Blue - đỏ, lục, lam) - Mô hình không gian màu RGB đƣợc sắp xếp theo khối lập phƣơng đơn vị. Đƣờng chéo chính của khối lập phƣơng với sự cân bằng về số lƣợng từng màu gốc tƣơng ứng với các mức độ xám với đen là (0,0,0) và trắng (1,1,1). - Tọa độ trên các cạnh trục biểu diễn các màu cơ sở. - Các cạnh còn lại biểu diễn màu bù cho mỗi màu cơ sở. Đây là mô hình màu cộng tính C = rR + gG + bB Trong đó C = màu hoặc ánh sáng kết quả. (r,g,b) = toạ độ màu trong miền [0 1], (R,G,B) = các màu cơ bản đỏ, lục và lam. Nếu hai màu tạo ra cùng một giá trị kích thích thì chúng ta không thể phân biệt đƣợc hai màu. Không gian màu RGB dựa theo chuẩn ITU-R BT.709, với gama = 2.2 và điểm trắng của mô hình là 6500 degrees K. Một số thuận lợi khi dùng không gian RGB : + Không gian RGB là chuẩn công nghiệp cho các thao tác đồ họa máy tính. 15
16. + Có thể chuyển đổi qua lại giữa không gian RGB với các không gian màu khác nhƣ CIE, CMY, HSL, HSV, + Các thao tác tính toán trên không gian RGB thƣờng đơn giản hơn. Một số bất lợi : + Các giá trị RGB của một màu là khác nhau đối với các màn hình khác nhau : các giá trị RGB của màu tim trên màn hình màu này sẽ không sinh ra đúng màu đó trên một màn hình khác. + Sự mô tả các màu trong thế giới thực đối với không gian RGB còn nhiều hạn chế bởi vì không gian RGB không hoàn toàn phù hợp với sự cảm nhận màu sắc của con ngƣời.  Mô hình màu CMY (Cyan, Magenta, Yellow - xanh tím, Đỏ tƣơi, vàng) 3 màu cơ sở là Cyan, Magenta, Yellow đây là 3 màu bù của 3 màu Red, Green, Blue. Đây là mô hình màu bù (Subtractive color models) hiển thị ánh sáng và màu sắc phản xạ từ mực in. Bổ xung thêm mực đồng nghĩa với ánh sáng phản xạ càng ít. Khi bề mặt không phủ mực thì ánh sáng phản xạ là ánh sáng trắng - white. Khi 3 màu có cùng giá trị cho ra màu xám. Khi các giá trị đạt max cho màu đen. Color = cC + mM + yY Ta có Red +Cyan = Black ; Green +Magenta = Black ; Blue + Yellow = Black Đây là mô hình màu trừ tính. - Hệ màu CMY được dùng cho các thiết bị in màu/giấy, chẳng hạn như máy in tĩnh điện hoặc máy in phun. 16
17.  Mô hình màu CMY- K Mô hình mở rộng của CMY ứng dụng trong máy in màu. Giá trị đen bổ xung vào thay thế cho hàm lƣợng màu bằng nhau của 3 màu cơ bản. Công thức chuyển đổi: K = min(C, M, Y) ; C = C - K ; M = M - K; Y = Y - K ; C-Cyan, M-Magenta, Y-Yellow; K-blacK Câu 15. Trình bày các mô hình màu HSV, HLS?  Mô hình màu HSV (Hue, Saturation,Value) Yếu tố cảm nhận màu sắc: - Hue - sắc màu: dùng để phân biệt sự khác nhau giữa các màu nhƣ xanh, đỏ, vàng - Saturation - độ bão hoà: chỉ ra mức độ thuần của một màu hay khoảng cách của màu tới điểm có cƣờng độ cân bằng(màu xám) - Lightness - độ sáng: hiện thân về mô tả cƣờng độ sáng từ ánh sáng phản xạ nhận đƣợc từ đối tƣợng. - Brightness - độ phát sáng: cƣờng độ ánh sáng mà tự đối tƣợng phát ra chứ không phải do phản xạ từ các nguồn sáng khác. - HSV (Hue, Saturation, Value)=HSB(Hue, Saturation, Brightness) định hƣớng ngƣời sử dụng dựa trên cơ sở về trực giác về tông màu, sắc độ và sắc thái mỹ thuật Hue: màu sắc 00-3600 đo bởi góc quay xung quanh trục đứng với màu đỏ là 00, màu lục là 1200, màu lam là 2400. Các màu bổ sung cho hình chóp ở 1800 đối diện với màu khác. Value-Brightness:(độ sáng) 0-1 đƣờng cao V với đỉnh là các điểm gốc toạ độ (0,0). Điểm ở đỉnh là màu đen và giá trị V=0. Khi điểm có S=0 và V=1 là điểm màu trắng, những giá trị trung gian của V đối với S=0 là các màu xám. Khi S=0 giá trị của H phụ thuộc đƣợc gọi bởi các qui ƣớc không xác định. Ngƣợc lại khi S khác 0 giá trị H sẽ là phụ thuộc. Saturation: Độ bão hoà 0-1, giá trị của S là tập các giá trị từ 0 trên đƣờng trục tâm (trục V) đến 1 trên các mặt bên tại đỉnh của chóp 6 cạnh. 17
18. Một số thuận lợi của không gian HSV : + Không gian HSV dễ dàng đáp ứng các màu sắc của các chƣơng trình đồ họa do đƣợc xây dựng dựa trên sự bắt chƣớc luật trộn màu của ngƣời họa sĩ. + Do không cần sử dụng các phép biến đổi lƣợng giác khi muốn chuyển sang không gian RGB nên không gian HSV có nhiều thuận lợi về mặt tính toán hơn so với không gian HSL. Một số bất lợi : + Cần có các phép hiệu chỉnh gamma.  Mô hình màu HLS (Hue, Lightness, Saturation Model) – không gian màu trực quan Mô hình thƣờng đƣợc sử dụng trong kỹ thuật đồ hoạ. Ưu điểm là rất trực giác ví dụ ta có thể chọn màu, thay đổi độ sáng và thay đổi độ bão hoà. Nhược điểm là khi chuyển đổi với không gian màu RGB sẽ có sai số (cube stood on end) thay đổi trên các loại màn hình khác nhau, rõ ràng không cảm nhận đều các màu. 18
19. Có thể coi mô hình HLS nhƣ một sự biến dạng của mô hình HLS mà trong đó mô hình này màu trắng đƣợc kéo hƣớng lên hình chóp sáu cạnh phía trên từ mặt V=1. Độ sáng (Lightness)=0 cho màu đen (tại điểm mút thấp nhất của hình chóp sáu cạnh đôi) và bằng 1 cho màu trắng (tại đầu mút cao nhất). Một số thuận lợi của không gian HSL : + Không gian HSL gần với sự cảm nhận các thuộc tính màu sắc của con ngƣời hơn không gian RGB. Các màu đƣợc xác định dễ dàng hơn. + Việc kiểm soát các màu cơ sở HSL dễ hơn cho những ngƣời mới làm quen với các chƣơng trình đồ họa. Một số bất lợi : + Việc thêm vào một vector không thể thực hiện đơn giản nhƣ không gian RGB (chỉ thêm vào các thành phần màu). Các thao tác lƣợng giác khi biến đổi sẽ ảnh hƣởng đáng kể đến tốc độ của chƣơng trình. + Cần phải qua hiệu chỉnh gamma trƣớc khi hiển thị (giống nhƣ các không gian khác). Câu 16. Cho biết các vị trí tương đối của một đoạn thẳng và một cửa sổ xén hình chữ nhật cho trước? Cho biết cách xác định giao điểm trong trường hợp đoạn thẳng cắt cửa sổ?  Các vị trí tương đối của một đoạn thẳng và một cửa sổ xén hình chữ nhật cho trước. Giả sử cửa sổ xén là cửa sổ hình chữ nhật có tọa độ của các điểm dƣới bên trái và điểm trên bên phải lần lƣợt là (xmin, ymin), (xmax, ymax) Cho đoạn thẳng đi qua 2 điểm đầu mút (x1, y1), (x2, y2). Đoạn thẳng sẽ thuộc vào một trong 3 trƣờng hợp sau: 19
20. Trƣờng hợp 1: Nhìn thấy Đoạn thẳng nằm hoàn toàn trong cửa sổ xén. Tọa độ 2 đầu mút nằm hoàn toàn trong cửa sổ xén. Đoạn thẳng sẽ đƣợc hiển thị toàn bộ trong vùng dữ liệu hiển thị. Trƣờng hợp 2: Không nhìn thấy Đoạn thẳng nằm hoàn toàn về một phía ngoài của cửa sổ. 2 đầu mút của đoạn thẳng nằm hoàn toàn về một phía ngoài của cửa sổ thỏa mãn một trong 4 bất đẳng thức sau: x1, x2> xmax x1, x2 ymax y1, y2<ymin Đoạn thẳng bị loại bỏ khỏi vùng dữ liệu hiển thị. Trƣờng hợp 3: đoạn thẳng đƣợc cắt. Đoạn thẳng không thuộc trƣờng hợp một hoặc trƣờng hợp hai. Khi đó đoạn thẳng có thể cắt hoặc không cắt cửa sổ.  Cách xác định giao điểm trong trường hợp đoạn thẳng cắt cửa sổ - Đoạn thẳng cắt cửa sổ hình chữ nhật tại các giao điểm, ta quy về trường hợp đoạn thẳng cắt đoạn thẳng. Xét 2 đoạn thẳng AB, CD có các tọa độ đầu mút nhƣ sau: A(xa, ya), B(xb, yb), C(xc, yc), D(xd, yd) Ta thƣờng dùng phƣơng trình tham số của đoạn thẳng để tìm giao điểm. Phƣơng trình đoạn thẳng AB: 20
21. X=xa + (xb-xa) t Y=ya + (yb-ya) t 0<=t<= 1 Phƣơng trình đoạn thẳng CD: X’=xc + (xd-xc) v Y’=yc + (yd-yc) v 0<=v<= 1 Xét 2 đƣờng thẳng chứa 2 đoạn thẳng AB và CD tƣơng ứng (t, v ϵR) Nếu 2 đƣờng thẳng này giao nhau với giá trị tham số t, v tƣơng ứng nằm trong khoảng [0,1] giao điểm này sẽ nằm trong đoạn thẳng AB và CD. Nếu giá trị tham số nằm ngoài khoảng [0,1] thì hai đoạn thẳng này không giao nhau. Câu 17. Trình bày thuật toán xén đoạn thẳng Cohen-Sutherland? Một con số 4 bit nhị phân gọi là mã vùng sẽ đƣợc gán cho mỗi vùng để mô tả vị trí tƣơng đối của vùng đó so với cửa sổ. Bằng cách đánh số từ 1 đến 4 theo thứ tự từ phải qua trái, các bit của mã vùng đƣợc dùng theo quy ƣớc sau để chỉ một trong bốn vị trí tƣơng đối của vùng so với cửa sổ bao gồm : trái, phải, trên, dƣới. Bit 1 : trái (LEFT) Bit 2 : phải (RIGHT) Bit 3 : trên (TOP) Bit 4 : dƣới (BOTTOM) Giá trị 1 tƣơng ứng với vị trí bit nào trong mã vùng sẽ chỉ ra rằng điểm đó ở vị trí tƣơng ứng, ngƣợc lại bit đó sẽ đƣợc đặt bằng 0. Ví dụ một vùng có mã là 1001, thì nó sẽ nằm phía dƣới (bit 4 bằng 1), bên trái (bit 1 bằng 1) so với cửa sổ, vùng có mã là 0000 chính là cửa sổ. Các giá trị bit trong mã vùng đƣợc tính bằng cách xác định tọa độ của điểm thuộc vùng đó với các biên của cửa sổ. Bit 1 đƣợc đặt là 1 nếu x< xmin , các bit khác đƣợc tính tƣơng tự. Thuật toán 21
22. Gán mã vùng tƣơng ứng cho các điểm đầu cuối P1P2 của đoạn thẳng cần xén lần lƣợt là c1, c2. Ta có nhận xét : + Các đoạn thẳng nằm hoàn toàn bên trong cửa sổ sẽ có c1=c2=0000. Hay c1 OR c2 = 0000, ứng với các đoạn này, kết quả sau khi xén là chính nó. + Nếu tồn tại kϵ{1, ,4}, sao cho với bit thứ k của c1, c2 đều có giá trị 1, lúc này đoạn thẳng sẽ nằm về cùng phía ứng với bit k so với cửa sổ, do đó nằm hoàn toàn ngoài cửa sổ. Đoạn này sẽ bị loại bỏ sau khi xén. + Nếu c1, c2 không thuộc về hai trƣờng hợp trên, đoạn thẳng có thể hoặc không cắt ngang cửa sổ chắc chắn sẽ tồn tại một điểm nằm ngoài cửa sổ. Bằng cách xét mã vùng của P1 là c1 ta có thể xác định đƣợc các biên mà đoạn thẳng có thể cắt để từ đó chọn một biên và tiến hành tìm giao điểm P1’của đoạn thẳng với biên đó. Lúc này, đoạn thẳng ban đầu đƣợc xén thành P1P1’. Tới đây chúng ta lại lặp lại thao tác đã xét cho đoạn thẳng mới P1P1’ cho tới khi xác định đƣợc phần nằm trong hoặc loại bỏ toàn bộ đoạn thẳng. Các điểm giao với các biên cửa sổ của đoạn thẳng có thể đƣợc tính từ phƣơng trình tham số. Tung độ y của điểm giao đoạn thẳng với biên đứng của cửa sổ có thể tính từ công thức y=y1+m(x-x1), trong đó x có thể xmin hay xmax . Tƣơng tự, hoành độ x của điểm giao đoạn thẳng với biên ngang của cửa sổ có thể tính từ công thức : x=x1+(y-y1)/m , trong đó y có thể là ymin hay ymax . Câu 18. Trình bày thuật toán xén hình Liang-Barsky? Thuật toán Liang-Barsky đƣợc phát triển dựa vào việc phân tích dạng tham số của phƣơng trình đoạn thẳng. X=x1+t(x2-x1)=x1+tDx, Dx=x2-x1 Y=y1+t(y2-y1)= y1+tDy, Dy=y2-y1 Ứng với mỗi giá trị t, ta sẽ có một điểm P tƣơng ứng thuộc đƣờng thẳng. + Các điểm ứng với t>=1 sẽ thuộc về tia P2x. + Các điểm ứng với t<=0 sẽ thuộc về tia P2x’. + Các điểm ứng với 0<=t<=1 sẽ thuộc về đoạn thẳng P1P2 . 22
23. Tập hợp các điểm thuộc về phần giao của đoạn thẳng và cửa sổ ứng với các giá trị t thỏa hệ bất phƣơng trình : Đặt: P1=-Dx, q1=x1-xmin P2=Dx, q2=xmax-x1 P3=-Dy, q3=y1-ymin P4=Dy, q4=ymax-y1 Lúc này ta viết hệ phƣơng trình trên dƣới dạng : Nhƣ vậy việc tìm đoạn giao thực chất là tìm nghiệm của hệ bất phƣơng trình này. Có hai khả năng xảy ra đó là : + Hệ bất phƣơng trình vô nghiệm, nghĩa là đƣờng thẳng không có phần giao với cửa sổ nên sẽ bị loại bỏ. + Hệ bất phƣơng trình có nghiệm, lúc này tập nghiệm sẽ là các giá trị t thỏa mãn: Ta xét các trƣờng hợp : + Nếu tồn tại k ϵ {1, 2,3,4}: (pk=0) ˄ (qk = 0) thì với các bất phƣơng trình mà ứng với pk = 0 là các bất phƣơng trình hiển nhiên, lúc này hệ bất phƣơng trình cần giải tƣơng đƣơng với hệ bất phƣơng trình có pk ≠0. + Với các bất phƣơng trình pkt =qk/pk + Với các bất phƣơng trình pkt 0 , ta có t <=qk/pk Vậy nghiệm của hệ bất phƣơng trình là [t1, t2]với : 23
24. Nếu hệ trên có nghiệm thì đoạn giao Q1Q2 sẽ là Q1(x1+t1Dx, y1+t1Dy), Q2(x1+t2Dx, y1+t2Dy) Thông thƣờng, thuật toán Liang-Barsky cho tốc độ tốt hơn thuật toán CohenSutherland vì rút gọn đƣợc số giao điểm cần tính. Câu 19. Trình bày thuật toán cắt đa giác Sutherland-Hodgman? Cho P1, ,PN là danh sách các đỉnh của đa giác đã bị cắt tỉa P. Cho cạnh AB (điểm A,B) là cạnh bất kỳ của đa giác cắt tỉa Q lồi duyệt theo hƣớng dƣơng. Với mỗi cạnh của đa giác Q ta sẽ cắt mỗi cạnh của đa giác P và tạo nên một đa giác mới với các đỉnh đƣợc xác định nhƣ sau: Xét cạnh Pi-1Pi: - Các trƣờng hợp trong giải thuật Sutherland Hodgman (1) Nếu cả Pi-1 và Pi đều nằm bên trái của cạnh này thì Pi đƣợc lƣu lại (đƣa vào output) của đa giác cắt tỉa. (2) Nếu cả Pi-1 và Pi đều nằm bên phải của cạnh thì không có đỉnh nào đƣợc lƣu lại. (3) Nếu Pi-1 nằm bên trái và Pi nằm bên phải của cạnh thì giao điểm I của Pi-1Pi với cạnh sẽ đƣợc lƣu lại. (4) Nếu Pi-1 nằm bên phải và Pi nằm bên trái thì cả giao điểm I và Pi đều đƣợc lƣu lại. Quá trình thực hiện thuật toán bằng cách duyệt lần lƣợt tƣng cạnh của đa giác cắt. Với mỗi cạnh của đa giác cắt lại duyệt lần lƣợt từng cạnh của đa giác bị cắt mới thu đƣợc. Thuật toán Sutherland-Hodgeman cho kết quả rất chính xác khi làm việc với các đa giác lồi, tuy nhiên với các đa giác lõm kết quả hiển thị có thể sẽ có đoạn thừa. 24
25. Câu 20. Cho biết các tính chất của phép biến đổi affine?  Phép biến đổi affine bảo toàn đường thẳng Ảnh của đƣờng thẳng qua phép biến đổi affine là đƣờng thẳng. Từ kết quả trên, để biến đổi một đoạn thẳng đi qua hai điểm A và B, ta chỉ cần áp dụng phép biến đổi cho hai điểm A, B rồi vẽ lại đoạn thẳng qua hai điểm mới.  Tính song song của các đường thẳng được bảo toàn Ảnh của hai đƣờng thẳng song song là hai đƣờng song song. Một hệ quả quan trọng của tính chất này đó là ảnh của các hình bình hành sau phép biến đổi là các hình bình hành.  Tính tỉ lệ về khoảng cách được bảo toàn Giả sử C là điểm chia đoạn AB theo tỉ số t. Nếu A’, B’, C’ lần lƣợt là ảnh A, B, C qua phép biến đổi thì C’ cũng sẽ chia A’B’ theo tỉ số t. Trong trƣờng hợp đặc biệt, nếu C là trung điểm của AB thì C’ cũng là trung điểm của A’B’, từ đó ta có thể suy ra một số tính chất sau : + Trong hình vuông, các đƣờng chéo cắt nhau tại trung điểm của mỗi đƣờng nên các đƣờng chéo của bất cứ hình bình hành nào cũng cắt nhau tại trung điểm của mỗi đƣờng. + Trong tam giác đều, giao điểm của ba đƣờng trung tuyến chia mỗi đƣờng theo tỉ số 1:2. Mặt khác, một tam giác bất kì là ảnh của tam giác đều qua phép biến đổi affine, nên giao điểm của các đƣờng trung tuyến của nó cũng sẽ chia chúng theo tỉ lệ 1:2. Câu 21. Trình bày hệ tọa độ thuần nhất và cho biết ma trận tọa độ thuần nhất của các phép biến đổi tịnh tiến, quay quanh gốc tọa độ, phép tỷ lệ quanh gốc tọa độ trong không gian 2 chiều ?  Hệ tọa độ thuần nhất Tọa độ thuần nhất của một điểm trên mặt phẳng đƣợc biểu diễn bằng bộ ba số tỉ lệ (xh, yh, h) không đồng thời bằng 0 và liên hệ với các tọa độ (x,y) của điểm đó bởi công thức : x=xh/h, y=yh/h Nếu một điểm có tọa độ thuần nhất là (x, y, z) thì nó cũng có tọa độ thuần nhất là (h.x,h.y, h)trong đó h là số thực # 0 bất kì.  Phép tịnh tiến 25
26.  Phép biến đổi tỷ lệ  Phép quay quanh gốc tọa độ Câu 22. Trình bày phép biến đổi tỷ lệ quanh gốc tọa độ ? Phép biến đổi tỉ lệ làm thay đổi kích thƣớc đối tƣợng. Để co hay giãn tọa độ của một điểm P(x, y) theo trục hoành và trục tung lần lƣợt là sx và sy, ta nhân sx, sy lần lƣợt cho các tọa độ của P. Khi các giá trị sx, sy 1, phép biến đổi sẽ phóng lớn đối tƣợng. Khi sx, sy bằng nhau, ta gọi đó là phép đồng dạng, phép đồng dạng là phép biến đổi bảo toàn tính cân xứng của đối tƣợng. 26
27. Tâm tỉ lệ là điểm không bị thay đổi qua phép biến đổi tỉ lệ. Khi phép biến đổi tỉ lệ thu nhỏ đối tƣợng, đối tƣợng sẽ đƣợc dời về gần gốc tọa độ hơn, tƣơng tự khi phóng lớn đối tƣợng, đối tƣợng sẽ đƣợc dịch chuyển xa gốc tọa độ hơn. Câu 23. - Cho biết ma trận tọa độ thuần nhất của các phép đối xứng qua gốc tọa độ, qua trục Ox, trục Oy, qua đường y=x trong không gian 2 chiều? - Cho biết ma trận của phép lấy đối xứng qua tâm là điểm bất kì I(xI, yI)?( tức là quay 180 quanh tâm là điểm I).  Phép đối xứng qua Ox  Phép đối xứng qua Oy  Phép đối xứng qua đường y=x - Quay đường thẳng y=x 1 góc -45 để đt y=x trùng với trục Ox: √ √ MT1= [ ] = [√ √ ] - Lấy đối xứng qua Ox: MT2 = [ ] - Quay đường thẳng 1 góc 45 để đưa đt trở về vị trí ban đầu: √ √ MT3 = [ ] = [ √ √ ] => Ma trận thuần nhất của phép lấy đối xứng qua đt y=x: MT=MT1.MT2.MT3 √ √ √ √ MT = [√ √ ]. [ ] [ √ √ ] √ √ √ √ = [√ √ ]. [ √ √ ] = [ ] 27
28.  Phép lấy đối xứng qua tâm là điểm bất kì I(xI, yI)? (tức là quay 180 quanh tâm là điểm I). - Tịnh tiến theo vecto (-xI,-yI) để đưa tâm về gốc tọa độ: MT1 = [ ] - Quay quanh gốc 1 góc 180: MT2 = [ ] = [ ] - Tịnh tiến theo vecto (xI,yI) để đưa tâm về vị trí ban đầu: MT3 = [ ] => Ma trận kết quả là: MT = MT1.MT2.MT3 = ??? Câu 24. - Chứng minh rằng ma trận của phép 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 qua trục hoành và phép quay quanh gốc tọa độ một góc 900? - Chứng minh rằng ma trận của phép 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 qua trục tung và phép quay quanh gốc tọa độ một góc 900?  Chứng minh rằng ma trận của phép 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 qua trục hoành và phép quay quanh gốc tọa độ một góc 900? - Ta có phép đối xứng qua đường y=x: - Quay đường thẳng y=x 1 góc -45 để đt y=x trùng với trục Ox: √ √ MT1= [ ] = [√ √ ] - Lấy đối xứng qua Ox: MT2 = [ ] - Quay đường thẳng 1 góc 45 để đưa đt trở về vị trí ban đầu: √ √ MT3 = [ ] = [ √ √ ] => Ma trận thuần nhất của phép lấy đối xứng qua đt y=x: MT=MT1.MT2.MT3 √ √ √ √ MT = [√ √ ]. [ ] [ √ √ ] √ √ √ √ = [√ √ ]. [ √ √ ] = [ ] - Phép đối xứng qua trục Ox và quay quanh gốc tọc độ 1 góc 90: [ ] [ ] = [ ] => đpcm 28
29.  Chứng minh rằng ma trận của phép 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 qua trục tung và phép quay quanh gốc tọa độ một góc 900? Làm tương tự như trên Câu 25. Chứng minh rằng cặp hai phép tỉ lệ là giao hoán, nghĩa là MS1MS2=MS2MS1. Tương tự cho cặp hai phép quay? 29