Chương 10: Các giải thuật nâng cao

Chương 10: Các giải thuật nâng caoScan conversionScan conversion: quá trình biểu diễn một đối tượng hình học (đoạn thẳng, vòng tròn,...) trong bộ đệm ảnh đơn (frame buffer) của hệ thống đồ họa quét raster.vận hành (drive) the frame buffer thông qua các thủ tụcSetPixel()GetPixel()Frame buffer và thiết bị hiển thịMô hình chức năng của frame bufferlàm tươi ảnhCRxyBMàn hình B=1(value=0) => (pixel off) black(value=1) => (pixel on) whiteTruy cập vào frame buffer const {moät ví duï} MaxColumn = 639; {= C - 1} MaxRow = 479; {= R - 1} MaxColor = 255; {= soá caùc maøu - 1}type col = 0..MaxColumn; row = 0..MaxRow; color = 0..MaxColor;procedure SetPixel(c : col, r : row, value : color); {load frame buffer}function GetPixel(c : col, r : row) : color; {read frame buffer}procedure SetPixelWord(c : col, r : row, value : word);function GetPixel(c : col, r : row) : word; 0MaxColumn12012Mô hình lập trìnhMô hình cho frame bufferCác thao tác lên frame buffer.MaxRowThuật toán vẽ đoạn thẳngYêu cầuĐi qua 2 điểm đầu mút của đoạn thẳngĐộ sáng đồng đều, trơnĐường thẳng có độ dốc khác nhau phải có độ sáng như nhauGiải thuật phải có tính lặp lại (dùng để xóa đường thẳng)Không phụ thuộc vào các chọn điểm bắt đầu vẽGiải thuật DD_LineProcedure DD_Line(row1,col1,row2,col2,color:integer); {Giaû söû ñoä doác naèm giöõa [-1,1], col1= 0e(Si) = 0Tính sai số một cách hữu hiệuTừ suy ra ei + 1 = 2(Dy)(xi + 1 - xa) + 2(Dx)(ya - yi ) - DxTừ trên, ei + 1 = ei + 2(Dy)(xi + 1 - xi) - 2(Dx)(yi - yi - 1 )Theo quy tắc chọn pixel,nếu ei xb và 0 xb (đổi vị trí hai đầu mút)m > 1 (đổi vai trò của x và y)Độ dốc âm: -1 0e(Ti) 0e(Ti) > 0e(Si) 0e(Ti) 0e(Ti) > 0e(Si) < new_color) then begin SetPixel(x, y, new_color); FloodFill(x – 1, y, int_color, new_color); FloodFill(x + 1, y, int_color, new_color); FloodFill(x, y + 1, int_color, new_color); FloodFill(x, y – 1, int_color, new_color); endend;Run of PixelsGiả thiết các pixel là 4-connectedGiải thuật Push address of seed pixel on the stack; while stack not empty do Pop the stack to provide the next seed; Fill in the run defined by the seed; Examine the row above for runs reachable from this run; Push the address of the rightmost pixels of each such run; Do the same for the row below the current run; end;Ví dụVí dụDCVí dụJIGFCTô màu vùng đa giácXét từng dòng ngang trên bộ đệm màn hình:Tìm các giao điểm của dòng với tất cả các cạnh của đa giácSắp xếp các giao điểm theo chiều tăng dần giá trị xTô các điểm ảnh nằm giữa các cặp giao điểmTô màu vùng đa giácCạnh nằm ngang không cần phải xử lýTính chẵn lẻ không còn đúng khi ở điểm mút không phải là cực trị địa phương.Cách giải quyết: dịch điểm đầu mút của một cạnh xuống 1 pixelTô màu vùng đa giácActive Edge List (AEL) lợi dụng tính lân cận của cạnhnhững cạnh cắt bởi scanline y sẽ cắt bởi scanline y+1giá trị x của giao điểm cĩ thể dự đốn trướctype edge_ptr = ^edge_info edge_info = record y_upper : row; x_int : real; recip_slope : real; next : egde_ptr; end;Tô màu vùng đa giácupdate AEL cho scanline y+1xĩa tất cả những cạnh cĩ y_upper < new_ythay đổi x_value bằng cách cộng thêm recip_slopecĩ thể thêm vào cạnh mới cĩ y_lower = new_ythứ tự của giao điểm cĩ thể bị xáo trộn, nên phải sắp xếp lạiTô màu vùng đa giácXây dựng bảng cạnh: edge_table: array [row] of edge_ptr