Ô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. 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. 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 đó. 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. 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. 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 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 Pk+1 =2(y2-y1)(xk+1)-2(x2-x1)yk+c = Pk +2(y2-y1) +) Pk>=0 d1>=d2 chọn yk+1=yk+1 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 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 trên đoạn thẳng. Lúc này điểm thực Q nằm dƣới điểm M nên ta chọn S tức là yi+1=yi Pi+1=2F(xi+1+1, yi+1+0.5)=2F(xi+2, yi+0.5)= 2A(xi+2)+2B(yi+0.5)+C = pi+2A = pi+2Dy + 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) : + = Với tâm C(xc, yc): (x-xc) 2 + (y-yc) 2 =R 2 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)). 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 trong đƣờng tròn F(x,y) =0 nếu (x,y) thuộc đƣờng tròn F(x,y) > 0 nếu (x,y) nằm ngoài đƣờng tròn Gọi M là trung điểm PS Xét pi=F(M)=F(xi+1, yi-0.5)= (xi+1) 2 + (yi-0.5) 2 -R 2 11 pi+1=F(xi+1+1, yi+1-0.5)= (xi+1+1) 2 + (yi+1-0.5) 2 - R 2 Ta có : + Nếu pi<0, điểm M nằm trong đƣờng tròn. Lúc này điểm thực Q gần S hơn nên ta chọn S, tức là yi+1=yi pi+1=F(xi+2, yi-0.5)= (xi+2) 2 + (yi-0.5) 2 -R 2 = pi+ 2xi+3 + 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 pi+1=F(xi+2, yi - 1.5)= (xi+2) 2 + (yi-1.5) 2 -R 2 = 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)=b 2 x 2 +a 2 y 2−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 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. Trong vùng 1 thành phần j lớn hơn thành phần i của gradient. a2(yp-0.5)>b 2 (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: pi =F(M)= F(xi+1,yi-1/2) = b 2 (xi+1) 2 + a 2 (yi-1/2) 2 -a 2 b 2 pi+1 = F(xi+1+1,yi+1-1/2) = b 2 (xi+1+1) 2 + a 2 (yi+1-1/2) 2 - a 2 b 2 - Nếu pi <0 chọn A: xi+1=xi+1 yi+1=yi Pi+1 = b 2 (xi+1+1) 2 + a 2 (yi+1-1/2) 2 - a 2 b 2 = b 2 (xi+2) 2 + a 2 (yi-1/2) 2 -a 2 b 2 = pi + b 2 (2xi +3) - Nếu pi >=0 chọn B: xi+1=xi+1 yi+1=yi -1 pi+1 = b 2 (xi+2) 2 + a 2 (yi-1.5) 2 -a 2 b 2 = pi + b 2 (2xi +3) + a 2 (-2yi +2) - Tính P1 khởi tạo tại (0,b): p1 = F(1,b-1/2) = b 2 + a 2 (b-1/2) 2 -a 2 b 2 = b 2 - a 2 b +a 2 /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 13 Tham số quyết định: qj =F(M)= F(xj+1/2,yj-1) = b 2 (xj+1/2) 2 + a 2 (yj-1) 2 -a 2 b 2 qj+1 = F(xj+1 +1+1/2, yj+1 -1) = b 2 (xj+1+1/2) 2 + a 2 (yj+1-1) 2 -a 2 b 2 - Nếu qj <0 chọn D: yj+1 =yj-1, xj+1 = xj +1 qj+1 b 2 (xj+1+1/2) 2 + a 2 (yj+1-1) 2 -a 2 b 2 = b 2 (xj+1.5) 2 + a 2 (yj-2) 2 -a 2 b 2 = qj + b 2 (2xj +2) +a 2 (-2yj +3) - Nếu qj >=0 chọn C: yj+1 =yj-1, xj+1 = xj qj+1 = b 2 (xj+1+1/2) 2 + a 2 (yj+1-1) 2 -a 2 b 2 = b 2 (xj+1/2) 2 + a 2 (yj-2) 2 -a 2 b 2 = qj + a 2 (- 2yj+3) - Tính q1 khởi tạo q1 = f(xp+1/2,yp -1) = b 2 (xp+1/2) 2 + a 2 (yp-1) 2 -a 2 b 2 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