Bài giảng Đồ họa máy tính

ĐỒ HỌA MÁY TÍNH 
Trƣờng Đại Học Bách Khoa TP Hồ Chí Minh 
Khoa Khoa học & Kỹ thuật Máy tính 
CHƢƠNG 1: 
GIỚI THIỆU ĐỒ HỌA 
MÁY TÍNH 
Slide 2 Faculty of Computer Science and Engineering - HCMUT 
NỘI DUNG TRÌNH BÀY 
Giới thiệu tổng quan về đồ họa máy tính 
Đối tƣợng cơ bản trong đồ họa máy tính 
Thiết bị hiển thị đồ họa 
Slide 3 Faculty of Computer Science and Engineering - HCMUT 
CHƢƠNG TRÌNH 
Nội dung 
Chƣơng 1-Giới thiệu đồ họa máy tính 
Chƣơng 2-Bƣớc đầu tạo dựng hình ảnh 
Chƣơng 3-Xây dựng công cụ vẽ hình ảnh 
Chƣơng 4-Vector trong đồ họa máy tính 
Chƣơng 5-Biến đổi hình 
Chƣơng 6-Mô hình hóa đối tƣợng 3 D bằng lƣới đa giác 
Chƣơng 7-Phép nhìn trong không gian ba chiều 
Chƣơng 8-Tô màu vật thể ba chiều 
Chƣơng 9-Kỹ thuật lặp đệ quy, ứng dụng tạo hoa văn 
Chƣơng 10-Đồ họa raster 
Slide 4 Faculty of Computer Science and Engineering - HCMUT 
TÀI LIỆU MÔN HỌC 
 [1] Francis S. Hill, Jr, Computer Graphics, Macmillan Publishing 
Company, 1990. 
 [2] Foley, van Dam, Feiner, Hughes, Computer Graphics principles and 
practice, Addison-Wesley Publishing Company, 1996. 
 [3] Nguyễn Hữu Lộc, Đồ họa máy tính và mô hình hóa hình học, Nhà 
xuất bản thành phố Hồ Chí Minh, 2000. 
 [4] Hoàng Kiếm, Dƣơng Anh Đức, Lê Đình Huy, Vũ Hải Quân, Cơ sở 
đồ họa máy tính, Nhà xuất bản giáo dục, 2000. 
 [5] Nguyễn Quốc Cƣờng, Hoàng Đức Hải, Đồ họa vi tính, Nhà xuất bản 
giáo dục, 1998. 
 [6] Tống Nghĩa, Hoàng Đức Hải, Đồ họa máy tính trong ngôn ngữ C, Nhà 
xuất bản giáo dục, 1999. 
 [7] Nguyễn Tiến, Ngô Quốc Việt, Giáo trình đồ họa máy tính, Nhà xuất 
bản thống kê, 2001. 
 [8] Lê Tấn Hùng, Huỳnh Quyết Thắng, Kỹ thuật đồ họa, Nhà xuất bản 
Khoa học và Kỹ thuật, 2004 
  Graphics 
Slide 5 Faculty of Computer Science and Engineering - HCMUT 
ĐỊNH NGHĨA ĐỒ HỌA MÁY TÍNH 
Dùng máy tính để tạo ra hình ảnh 
Đồ họa máy tính và xử lý ảnh 
– Đồ họa máy tính: tạo hình ảnh dựa trên đặc tả hoặc 
mô hình 
– Xử lý ảnh: nâng cao chất lƣợng hoặc chỉnh sửa hình 
ảnh. 
Slide 6 Faculty of Computer Science and Engineering - HCMUT 
ỨNG DỤNG CỦA ĐỒ HỌA MÁY TÍNH 
Ứng dụng trong giải trí, xuất bản và nghệ thuật 
– Sản xuất phim hoạt hình, tạo hiệu ứng cho phim nhựa 
– Trò chơi máy tính 
– Duyệt Web 
– Chế bản điện tử 
Xử lý ảnh 
Ứng dụng trong tự động hóa và điều khiển 
Mô phỏng 
Máy tính hỗ trợ thiết kế 
– Hỗ trợ thiết kế kiến trúc 
– Hỗ trợ thiết kế mạch điện tử 
Hình ảnh hóa số liệu khoa học 
Slide 7 Faculty of Computer Science and Engineering - HCMUT 
ĐỐI TƢỢNG CƠ BẢN TRONG ĐHMT 
Đƣờng gấp khúc (polyline) 
Văn bản (text) 
Vùng tô (filled region) 
Ảnh ma trận điểm hay ảnh raster (raster image) 
Slide 8 Faculty of Computer Science and Engineering - HCMUT 
ĐƢỜNG GẤP KHÖC 
Đƣờng gấp khúc là một tập các đoạn thẳng đƣợc nối với 
nhau. 
Đƣờng gấp khúc đƣợc dùng mô phỏng đƣờng cong. 
Các hàm liên quan 
– Vẽ điểm: drawDot(x1, y1) 
– Vẽ đoạn thẳng: drawLine(x1, y1, x2, y2) 
– Vẽ đƣờng gấp khúc: drawPolyline(poly) 
Slide 9 Faculty of Computer Science and Engineering - HCMUT 
ĐƢỜNG GẤP KHÖC 
Khi đỉnh đầu và đỉnh cuối đƣợc nối bằng một đoạn thẳng 
thì đƣờng gấp khúc trở thành đa giác 
Slide 10 Faculty of Computer Science and Engineering - HCMUT 
ĐƢỜNG GẤP KHÖC 
Thuộc tính 
– Màu sắc 
– Độ dày 
– Kiểu đƣờng (liền nét, đứt nét) 
– Cách nối hai cạnh dày 
Thiết lập thuộc tính: 
 setDash (dash7) hoặc setLineThickness(thickness). 
Slide 11 Faculty of Computer Science and Engineering - HCMUT 
VĂN BẢN 
Một số thiết bị có hai chế độ hiển thị 
– Chế độ hiển thị văn bản 
– Chế độ hiển thị đồ họa 
Thủ tục hiển thị chuỗi 
– drawString(x, y, string); 
Thuộc tính 
– Font 
– Màu sắc 
– Kích thƣớc 
– Hƣớng 
– Khoảng cách giữa các ký tự trong chuỗi 
Slide 12 Faculty of Computer Science and Engineering - HCMUT 
VĂN BẢN 
Slide 13 Faculty of Computer Science and Engineering - HCMUT 
VÙNG TÔ 
Hình đƣợc tô bởi màu hoặc mẫu tô. Đƣờng biên thƣờng 
là hình đa giác. 
Thủ tục : fillPolygon(poly, pattern); 
Slide 14 Faculty of Computer Science and Engineering - HCMUT 
VÙNG TÔ 
Dùng vùng tô để mô phỏng các mặt khác nhau của vật 
thể tô màu 
Slide 15 Faculty of Computer Science and Engineering - HCMUT 
ẢNH RASTER 
Đƣợc tạo bởi các pixel 
Lƣu trữ dƣới dạng mảng các giá trị 
Phƣơng pháp tạo ảnh raster 
– Thiết kế thủ công 
– Tạo bằng thuật toán 
– Quét 
Ảnh raster có thể tiến hành xử lý 
Slide 16 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ HIỂN THỊ ĐỒ HỌA 
Thiết bị đồ họa vector: tạo hình ảnh từ những đoạn 
thẳng 
– Ƣu điểm: nhanh 
– Khuyết điểm: không tô màu cho vùng đƣợc 
Các loại thiết bị vector thƣờng gặp 
– Máy vẽ: 
• Máy vẽ flatbed 
• Máy vẽ dạng trống 
– Màn hình vector 
Slide 17 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ HIỂN THỊ ĐỒ HỌA 
Thiết bị raster: Tạo hình ảnh từ ma trận điểm 
Phân loại: 
– Màn hình video 
– Màn hình tấm phẳng 
– Các thiết bị sao chép cứng 
• Máy in film (film recorder) 
• Máy in laser 
• Máy in phun 
Slide 18 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ RASTER 
Các vấn đề cần tìm hiểu 
– Bề mặt hiển thị 
– Bộ đệm frame 
– Quá trình quét dòng 
Bề mặt hiển thị (display surface) 
Slide 19 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ RASTER 
Bộ đệm frame 
CPU Bộ nhớ hệ 
thống 
Bộ đệm 
Bộ điều khiển 
quét dòng 
Bộ chuyển đổi 
Bus hệ thống 
Bề mặt hiển thị 
Slide 20 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ RASTER 
Quá trình quét dòng 
Slide 21 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ RASTER 
Màn hình video màu 
Slide 22 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ RASTER 
Màu chỉ mục và bảng tìm kiếm 
Slide 23 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ RASTER 
Màu chỉ mục và bảng tìm kiếm 
Slide 24 Faculty of Computer Science and Engineering - HCMUT 
THIẾT BỊ RASTER 
Màn hình tấm phẳng 
CHƢƠNG 2: 
BƢỚC ĐẦU TẠO HÌNH ẢNH 
Trƣờng Đại Học Bách Khoa TP Hồ Chí Minh 
Khoa Khoa học & Kỹ thuật Máy tính 
Slide 26 Faculty of Computer Science and Engineering - HCMUT 
NỘI DUNG TRÌNH BÀY 
Xây dựng chƣơng trình đồ họa. 
Thành phần cơ bản trong một chƣơng trình sử dụng 
OpenGL. 
Vẽ điểm, vẽ đoạn thẳng, vẽ đƣờng gấp khúc, vẽ hình 
chữ nhật. 
Giao tiếp với chuột và bàn phím. 
Một số ứng dụng. 
Slide 27 Faculty of Computer Science and Engineering - HCMUT 
XÂY DỰNG CHƢƠNG TRÌNH ĐỒ HỌA 
Môi trƣờng lập trình 
– Phần cứng: màn hình, card đồ họa. 
– Phần mềm: hệ điều hành (Window), ngôn ngữ lập 
trình (MS Visual C++), thƣ viện đồ họa (OpenGL, 
Direct X). 
Trình tự xây dựng chƣơng trình đồ họa 
– Thiết lập chế độ hiển thị (văn bản, đồ họa) 
– Thiết lập hệ trục tọa độ 
– Sử dụng các hàm của môi trƣờng lập trình để tạo 
dựng hình ảnh. 
Slide 28 Faculty of Computer Science and Engineering - HCMUT 
THIẾT LẬP TRỤC TỌA ĐỘ 
Môi trƣờng lập trình DOS 
Môi trƣờng lập trình Window 
(100, 50) 
(150, 80) 
(0, 290) 
Slide 29 Faculty of Computer Science and Engineering - HCMUT 
SỬ DỤNG CÁC HÀM ĐỂ XÂY DỰNG HÌNH ẢNH 
Hàm do hệ điều hành và ngôn ngữ lập trình cung cấp: 
– setPixel(x, y, color) 
 tên khác: putPixel(), SetPixel() hoặc drawPoint() 
– line(100, 50, 150, 80); 
 line(150, 80, 0, 290); 
Hàm do thƣ viện đồ họa cung cấp. 
Hàm tự xây dựng. 
Slide 30 Faculty of Computer Science and Engineering - HCMUT 
THÀNH PHẦN CƠ BẢN CỦA CT SỬ DỤNG OpenGL 
OpenGL là thƣ viện lập trình đồ họa độc lập thiết bị 
– Không phụ thuộc vào phần cứng và hệ điều hành 
– Cách làm thống nhất cho cả đồ họa 2D và 3D 
Lập trình Window 
– Lập trình sự kiện là gì? 
– Hàng đợi sự kiện (event queue). 
– Callback function. 
– Đăng ký hàm xử lý sự kiện: 
• glutDisplayFunc(myDisplay) 
• glutReshapeFunc(myReshape) 
• glutMouseFunc(myMouse) 
• glutKeyboardFunc(myKeyboard) 
Slide 31 Faculty of Computer Science and Engineering - HCMUT 
THÀNH PHẦN CƠ BẢN CỦA CT SỬ DỤNG OpenGL 
// phần #include những file header cần thiết - xem phụ lục 1 
void main(int argc, char** argv) 
{ 
 glutInit(&argc, argv); //initialize the tool kit 
 glutInitDisplayMode(GLUT_SINGLE |GLUT_RGB);//set the display 
 mode 
 glutInitWindowSize(640, 480); //set window size 
 glutInitWindowPosition(100, 150); // set window position on screen 
 glutCreateWindow("My first program"); // open the screen window 
 // register the callback function 
 glutDisplayFunc(myDisplay); 
 myInit(); //additional initialization as necessary 
 glutMainLoop(); 
} 
Slide 32 Faculty of Computer Science and Engineering - HCMUT 
THÀNH PHẦN CƠ BẢN CỦA CT SỬ DỤNG OpenGL 
 Thiết lập hệ trục tọa độ 
void myInit() 
{ 
 glMatrixMode(GL_PROJECTION); 
 glLoadIdentity(); 
 gluOrtho2D(0.0, 640.0, 0.0,480.0); 
} 
Slide 33 Faculty of Computer Science and Engineering - HCMUT 
VẼ ĐIỂM 
glBegin(GL_POINTS); 
 glVertex2i(100, 50); 
 glVertex2i(100, 130); 
 glVertex2i(150, 130); 
glEnd(); 
My first program 
glVertex2i(...) 
thư 
viện 
gl 
phần cơ 
bản của 
tên hàm 
số lượng 
đối số 
kiểu của 
đối số 
Slide 34 Faculty of Computer Science and Engineering - HCMUT 
VẼ ĐIỂM 
Trạng thái trong OpenGL 
– glColor3f(1.0, 0.0, 0.0); // đổi màu vẽ thành màu đỏ 
– glClearColor(1.0,1.0,1.0,0.0);// set white background 
color 
– glPointSize(4.0); 
– glLineWidth(2.0); 
Slide 35 Faculty of Computer Science and Engineering - HCMUT 
VẼ ĐIỂM 
 Một chƣơng trình hoàn chỉnh 
int main(int argc, char* argv[]) 
{ 
 glutInit(&argc, argv); //initialize the tool kit 
 glutInitDisplayMode(GLUT_SINGLE |GLUT_RGB);//set the display 
mode 
 glutInitWindowSize(640, 480); //set window size 
 glutInitWindowPosition(100, 150); // set window position on screen 
 glutCreateWindow("My first program"); // open the screen window 
 glutDisplayFunc(myDisplay);// register redraw funtion 
 myInit(); 
 glutMainLoop();// go into a perpetual loop 
 return 0; 
} 
Slide 36 Faculty of Computer Science and Engineering - HCMUT 
VẼ ĐIỂM 
void myInit() 
{ 
 glClearColor(1.0,1.0,1.0,0.0);// set white background color 
 glColor3f(0.0f, 0.0f, 0.0f); // set the drawing color 
 glPointSize(4.0); // a ‘dot’ is 4 x 4 pixels 
 glMatrixMode(GL_PROJECTION); 
 glLoadIdentity(); 
 gluOrtho2D(0.0, 640.0, 0.0, 480.0); 
} 
Slide 37 Faculty of Computer Science and Engineering - HCMUT 
VẼ ĐIỂM 
void myDisplay() 
{ 
 glClear(GL_COLOR_BUFFER_BIT); // clear the screen 
 glBegin(GL_POINTS); 
 glVertex2i(100, 50); // draw three points 
 glVertex2i(100, 130); 
 glVertex2i(150, 130); 
 glEnd(); 
 glFlush(); // send all output to display 
} 
Slide 38 Faculty of Computer Science and Engineering - HCMUT 
MỘT SỐ VÍ DỤ 
Vẽ chòm sao Đại Hùng: 
 {Dubhe, 289, 190}, {Merak, 320, 128}, {Phecda, 239, 67}, 
{Megrez, 194, 101}, {Alioth, 129, 83}, {Mizar, 75, 73}, 
{Alcor, 74, 74}, {Alkaid, 20, 10} 
Slide 39 Faculty of Computer Science and Engineering - HCMUT 
MỘT SỐ VÍ DỤ 
Vẽ Sierpinski gasket 
P3 
P2 
P1 
T0 
T2 
T1 
Slide 40 Faculty of Computer Science and Engineering - HCMUT 
MỘT SỐ VÍ DỤ 
 Vẽ Sierpinski gasket 
1. Chọn 3 điểm cố định T0, T1, T2 để tạo nên một tam giác. Lƣu ý 
rằng chúng ta không vẽ 3 điểm này lên màn hình 
2. Chọn điểm khởi đầu p0. Điểm p0 đƣợc chọn ngẫu nhiên trong số 3 
điểm T0, T1, T2. Sau đó vẽ p0. 
 Lặp lại những bƣớc sau cho đến khi đạt đƣợc một kết quả vừa ý 
3. Chọn một điểm bất kỳ trong số 3 điểm T0, T1, T2. Gọi điểm đó là T. 
4. Tạo điểm tiếp theo (pk ) bằng cách lấy điểm trung điểm của đoạn 
thẳng nối T và điểm trƣớc đó (pk-1 ). Tức là : pk = điểm giữa của 
pk-1 và T 
5. Dùng hàm drawDot() để vẽ pk. 
Slide 41 Faculty of Computer Science and Engineering - HCMUT 
MỘT SỐ VÍ DỤ 
 Vẽ Sierpinski gasket 
void Sierpinski() 
{ 
 GLintPoint T[3]={{10, 10}, {300, 30}, {200, 300}} ; 
 int index = random(3) ; 
 GLintPoint point = T[index] ; 
 glClear(GL_COLOR_BUFFER_BIT); 
 drawDot(point.x, point.y) ; 
 for(int i=0; i<1000;i++) 
 { 
 index = random(3); 
 point.x = (point.x + T[index].x) / 2; 
 point.y = (point.y + T[index].y) / 2; 
 drawDot(point.x, point.y) ; 
 } 
 glFlush(); 
} 
Slide 42 Faculty of Computer Science and Engineering - HCMUT 
MỘT SỐ VÍ DỤ 
class GLintPoint{ 
 public : 
 GLint x, y ; 
} ; 
int random(int m) 
{ 
 return rand() % m ; 
} 
void drawDot(GLint x, GLint y) 
{ //vẽ một điểm ở tọa độ (x, y) 
 glBegin(GL_POINTS); 
 glVertex2i(x, y); 
 glEnd(); 
} 
Slide 43 Faculty of Computer Science and Engineering - HCMUT 
VẼ ĐOẠN THẲNG 
 glBegin(GL_LINES); 
 glVertex2i(40, 100); 
 glVertex2i(202, 96); 
 glEnd(); 
 void drawLineInt(GLint x1, GLint y1, GLint x2, GLint y2) 
 { 
 glBegin(GL_LINES); 
 glVertex2i(x1, y1); 
 glVertex2i(x2, y2); 
 glEnd(); 
 } 
 glBegin(GL_LINES); 
 glVertex2i(10, 20);// vẽ đoạn thẳng thứ nhất 
 glVertex2i(40, 20); 
 glVertex2i(20, 10);// vẽ đoạn thẳng thứ hai 
 glVertex2i(20, 40); 
 thêm 4 lời gọi hàm glVertex2i()để vẽ hai đoạn thẳng còn lại 
 glEnd(); 
a) đoạn thẳng mỏng b) đoạn thẳng dày c) đoạn thẳng đứt nét 
Slide 44 Faculty of Computer Science and Engineering - HCMUT 
VẼ ĐƢỜNG GẤP KHÖC 
 p0 = (x0, y0), p1 = (x1, y1), ..., pn = (xn, yn) 
 glBegin(GL_LINE_STRIP); //vẽ đường gấp khúc mở 
 glVertex2i(20, 10); 
 glVertex2i(50, 10); 
 glVertex2i(20, 80); 
 glVertex2i(50, 80); 
 glEnd(); 
a) b) 
 GL_LINE_LOOP 
vẽ đường gấp khúc khép kín 
Slide 45 Faculty of Computer Science and Engineering - HCMUT 
VÍ DỤ 
 void hardwirededHouse() 
{ 
 glBegin(GL_LINE_LOOP);//vẽ khung ngôi nhà 
 glVertex2i(40, 40); 
 glVertex2i(40, 90); 
 glVertex2i(70, 120); 
 glVertex2i(100, 90); 
 glVertex2i(100, 40); 
 glEnd(); 
 glBegin(GL_LINE_STRIP);//vẽ ống khói 
 glVertex2i(50, 100); 
 glVertex2i(50, 120); 
 glVertex2i(60, 120); 
 glVertex2i(60, 110); 
 glEnd(); 
 . . . // vẽ cửa ra vào 
 . . . // vẽ cửa sổ 
} 
120 40 
120 
40 
Slide 46 Faculty of Computer Science and Engineering - HCMUT 
VÍ DỤ 
 void parameterizedHouse(GLintPoint peak,GLint width,GLint 
height) 
 // tọa độ của nóc nhà là peak, 
 // chiều cao, chiều rộng của ngôi nhà là height và width 
 { 
 glBegin(GL_LINE_LOOP); 
 glVertex2i(peak.x, peak.y); 
 glVertex2i(peak.x + width/2,peak.y – 3*height/8); 
 glVertex2i(peak.x + width/2,peak.y – height); 
 glVertex2i(peak.x - width/2,peak.y – height); 
 glVertex2i(peak.x - width/2,peak.y – 3*height/8); 
 glEnd(); 
 vẽ ống khói 
 vẽ cửa ra vào 
 vẽ cửa sổ 
 } 
Slide 47 Faculty of Computer Science and Engineering - HCMUT 
VÍ DỤ 
Slide 48 Faculty of Computer Science and Engineering - HCMUT 
VẼ ĐƢỜNG GẤP KHÖC 
 class GLintPointArray 
 { 
 const int MAX_NUM = 100; 
 public: 
 int num ; 
 GLintPoint pt[MAX_NUM] ; 
 }; 
 void drawPolyLine(GLintPointArray poly,int closed) 
 { 
 glBegin(closed ? GL_LINE_LOOP : GL_LINE_STRIP); 
 for(int i=0;i<poly.num;i++) 
 glVertex2i(poly.pt[i].x, poly.pt[i].y); 
 glEnd(); 
 glFlush(); 
 } 
Slide 49 Faculty of Computer Science and Engineering - HCMUT 
VẼ ĐOẠN  ... edure 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; 
0 MaxColumn 1 2 
0 
1 
2 
Moâ hình laäp trình 
‟ Moâ hình cho frame buffer 
‟ Caùc thao taùc leân frame buffer. 
MaxRow 
Slide 326 Faculty of Computer Science and Engineering - HCMUT 
Thuaät toaùn veõ ñoaïn thaúng 
Yeâu caàu 
‟ Ñi qua 2 ñieåm ñaàu muùt cuûa ñoaïn thaúng 
‟ Ñoä saùng ñoàng ñeàu, trôn 
‟ Ñöôøng thaúng coù ñoä doác khaùc nhau phaûi coù ñoä 
saùng nhö nhau 
‟ Giaûi thuaät phaûi coù tính laëp laïi (duøng ñeå xoùa 
ñöôøng thaúng) 
‟ Khoâng phuï thuoäc vaøo caùc choïn ñieåm baét ñaàu 
veõ 
Slide 327 Faculty of Computer Science and Engineering - HCMUT 
Giaûi thuaät DD_Line 
 Procedure DD_Line(row1,col1,row2,col2,color:integer); 
 {Giaû söû ñoä doác naèm giöõa [-1,1], col1<= col2} 
 var 
 dx, dy, y, m: real; 
 x: integer; 
 begin 
 dx:= col2-col1; 
 dy:= row2 – row1; 
 m:= dy/dx; 
 y:= row1; 
 for x:=col1 to col2 do 
 begin 
 SetPixel(x, Round(y),color); 
 y:= y + m; 
 end; 
 end; 
Slide 328 Faculty of Computer Science and Engineering - HCMUT 
Thuaät toaùn Bresenham 
Nhöõng haïn cheá cuûa giaûi thuaät DD_Line 
– Chaäm vì söû duïng haøm Round 
– Khoâng chính xaùc khi khoaûng caùch giöõa 2 ñieåm ñaàu 
muùt lôùn 
– Ñoä saùng khoâng ñoàng ñeàu 
Thuaät toaùn Bresenham 
– Chæ duøng soá nguyeân 
– Thuoäc vaøo lôùp giaûi thuaät incremental (xaùc ñònh toïa ñoä 
cuûa ñieåm hieän haønh döïa vaøo toïa ñoä cuûa ñieåm tröôùc) 
Slide 329 Faculty of Computer Science and Engineering - HCMUT 
Cho ñoaïn thaúng noái hai ñieåm (x
a
 , y
a
) vaø (x
b
 , y
b
), 
– caùc toïa ñoä ñeàu laø soá nguyeân (toïa ñoä trong frame buffer) 
Bieåu dieãn töôøng minh cuûa ñöôøng thaúng: 
– Ñoä doác: , vôùi 
Baøi toaùn: Xaùc ñònh caùc pixel bieåu dieãn ñoaïn thaúng “toát” nhaát 
– tuøy thuoäc vaøo caùch ñònh nghóa sai soá 
Wlog (without loss of generality), x
a
 < x
b
 vaø 0 < m < 1 
– X taêng töø a ñeán b 
– X taêng nhanh hôn y 
– Moãi laàn x taêng leân 1, y khoâng taêng hoaëc taêng leân 1 
Bieåu dieãn ñoaïn thaúng trong frame buffer 
y = m(x - x
a
) + y
a
x
y
m
Dy = y
b
 - y
a
Dx = x
b
 - x
a
Slide 330 Faculty of Computer Science and Engineering - HCMUT 
Sai soá khi choïn pixel 
Sinh caùc pixel baèng phöông phaùp taêng daàn 
Ñònh nghóa sai soá e(Ti) = y* - yi - 1 
e(S
i
) = (y
i - 1
 + 1) - y* 
x
i - 1 
x
i
y
i - 1 
S
i
T
i
Ñoaïn thaúng lyù töôûng 
y
*
Slide 331 Faculty of Computer Science and Engineering - HCMUT 
Quy taéc choïn pixel xaáp xæ toát ñoaïn thaúng thöïc 
Quy taéc choïn pixel 
Tính e(T
i
) - e(S
i
) = 2m(x
i
 - x
a
) + 2(y
a
 - y
i - 1
) - 1 
Töø treân, ñeå chæ tính vôùi soá nguyeân, ñònh nghóa 
e
i
 = Dx(e(T
i
) - e(S
i
)) 
 = 2(Dy)(x
i
 - x
a
) + 2(Dx)(y
a
 - y
i - 1
) - Dx (*) 
Choïn T
i
 neáu vaø chæ neáu e(T
i
) - e(S
i
) < 0 
Neáu e
i
 < 0 thì choïn y
i
 = y
i - 1
 , neáu khoâng thì choïn y
i
 = y
i - 1
 + 1
Caàn kieåm tra tính ñuùng ñaén cuûa quy taéc treân! 
Slide 332 Faculty of Computer Science and Engineering - HCMUT 
Kieåm tra tính ñuùng ñaén cuûa quy taéc choïn pixel 
Tröôøng hôïp ñoaïn thaúng lyù töôûng ñi qua giöõa S
i
 vaø T
i
x
i - 1
 x
i
y
i - 1
S
i
T
i
Ñoaïn thaúng lyù töôûng 
e(T
i
) = y* - y
i - 1 
e(S
i
) = (y
i - 1
 + 1) - y* 
y
*
Slide 333 Faculty of Computer Science and Engineering - HCMUT 
Kieåm tra tính ñuùng ñaén cuûa quy taéc choïn pixel (tieáp) 
Caùc tröôøng hôïp coøn laïi 
xi 1 xi 
yi 1 
Si 
Ti 
xi 1 xi 
yi 1 
Si 
Ti 
Nhaéc laïi: e(T
i
) = y* y
i 1 
 e(S
i
) = (y
i 1 + 1) y* 
ñoaïn thaúng lyù töôûng 
ñi qua phía treân S
i
 vaø T
i 
ñoaïn thaúng lyù töôûng 
ñi qua phía döôùi S
i
 vaø T
i 
e(T
i
) >= 0
e(S
i
) <= 0 
e(T
i
) <= 0
e(S
i
) >= 0 
Slide 334 Faculty of Computer Science and Engineering - HCMUT 
Tính sai soá moät caùch höõu hieäu 
Töø 
 suy ra e
i + 1
 = 2(Dy)(x
i + 1
 - x
a
) + 2(Dx)(y
a
 - y
i 
) ‟ Dx 
 Töø treân, e
i + 1
 = e
i
 + 2(Dy)(x
i + 1
 - x
i
) - 2(Dx)(y
i
 - y
i - 1 
) 
 Theo quy taéc choïn pixel, 
‟ neáu e
i
 < 0 thì choïn y
i
 = y
i - 1
 e
i + 1
 = e
i
 + 2Dy 
‟ neáu khoâng thì choïn y
i
 = y
i - 1 
+ 1 
 e
i + 1
 = e
i
 + 2Dy - 2Dx 
e
i
 = 2(Dy)(x
i
 - x
a
) + 2(Dx)(y
a
 - y
i - 1
) - Dx 
Slide 335 Faculty of Computer Science and Engineering - HCMUT 
Giaûi thuaät cuûa Bresenham 
Bieåu dieãn ñoaïn thaúng trong frame buffer 
‟ Giaûi thuaät baét ñaàu nhö theá naøo? 
„ x
0
 = x
a
, y
0
 = y
a
„ Töø (*) coù e
1
 = 2(Dy) - Dx (duøng x
1
 - x
a
 = 1) 
procedure Bresenham(xa, xb : col; ya, yb : row; col_val : color); 
{veõ ñoaïn thaúng coù maøu laø col_val töø (xa, ya) ñeán (ya, yb)} 
{wlog, xa < xb vaø 0 < ñoä doác cuûa ñoaïn thaúng < 1} 
var 
 x : col; 
 y : row; 
 dx, dy, 
 e_inc, {thay ñoåi cuûa sai soá khi y taêng} 
 e_noinc, {thay ñoåi cuûa sai soá khi y khoâng taêng} 
 e : integer; {sai soá hieän thôøi} 
Slide 336 Faculty of Computer Science and Engineering - HCMUT 
Giaûi thuaät cuûa Bresenham (tieáp) 
begin 
 y := ya; 
 dx := xb - xa; 
 dy := yb - ya; 
 e_noinc := dy + dy; {2dy} 
 e := e_noinc - dx; {e1=2dy-dx} 
 e_inc := e - dx; {2dx-dy} 
 for x := xa to xb do {voøng laëp chính} 
 begin 
 SetPixel(x, y, col_val); 
 if e < 0 then e := e + e_noinc; 
 else begin 
 y := y + 1; 
 e := e + e_inc 
 end; 
 end; 
end; {Bresenham} 
Slide 337 Faculty of Computer Science and Engineering - HCMUT 
Caùc tröôøng hôïp khaùc 
 Giaûi thuaät Bresenham giaû söû x
a
 > x
b
 vaø 0 < m < 1. 
Giaûi quyeát caùc tröôøng hôïp coøn laïi: 
x
a
 > x
b
 (ñoåi vò trí hai ñaàu muùt) 
m > 1 (ñoåi vai troø cuûa x vaø y) 
Ñoä doác aâm: -1 < m < 0 (thay dy baèng ‟dy) 
m < -1 (thay dx baèng ‟dx, ñoåi vai troø cuûa x vaø y) 
Ñoaïn thaúng ñöùng vaø ñoaïn thaúng naèm ngang 
Slide 338 Faculty of Computer Science and Engineering - HCMUT 
Bieåu dieãn voøng troøn trong frame buffer 
Baøi toaùn: Xaùc ñònh caùc pixel bieåu dieãn voøng troøn y2 = 
R
2
 ‟ x2 “toát” nhaát 
‟ tuøy thuoäc vaøo caùch ñònh nghóa sai soá 
Giaûi quyeát 
‟ Do ñoái xöùng, chæ caàn khaûo saùt caùch veõ khi 0 x 
sao cho y(x) x töùc laø cung AB. 
‟ Sinh caùc pixel baèng phöông phaùp taêng daàn 
(incremental). 
Slide 339 Faculty of Computer Science and Engineering - HCMUT 
Ñoái xöùng treân voøng troøn 
Giaûm phí toån tính toaùn baèng caùch duøng pheùp ñoái 
xöùng treân voøng troøn 
‟ Chæ caàn xaùc ñònh caùc pixel töông öùng vôùi moät 
cung laø 1/8 voøng troøn, ôû ñaây choïn cung AB. 
(x, y) 
(y, x) 
(y, x) 
( x, y) (x, y) 
( y, x) 
( y, x) 
( x, y) 
x 
y 
A 
B 
Slide 340 Faculty of Computer Science and Engineering - HCMUT 
Sai soá khi choïn pixel 
Giaû söû coù pixel toát nhaát taïi böôùc thöù i - 1 laø P
i - 1
 = 
(x
i - 1
, y
i - 1
) 
Ñònh nghóa 
 S
i
 = (x
i - 1
 + 1, y
i - 1
) 
 T
i
 = (x
i - 1
 + 1, y
i - 1
 - 1) 
Ñònh nghóa sai soá 
 e(P) = (x
2
 + y
2
) - R
2 
Ñònh nghóa haøm soá quyeát ñònh 
 d
i
 = e(S
i
) + e(T
i
) 
xi 
1 
xi 
yi 1 
Pi 1 Si 
Ti 
Slide 341 Faculty of Computer Science and Engineering - HCMUT 
Qui taéc choïn pixel xaáp xæ toát cung voøng troøn 
 xi 
1 
xi 
yi 1 
Pi 1 Si 
Ti 
Neáu d
i
 < 0 thì choïn S
i 
coøn neáu khoâng thì choïn T
i 
Caàn kieåm tra tính ñuùng ñaén cuûa quy taéc treân! 
Slide 342 Faculty of Computer Science and Engineering - HCMUT 
Kieåm tra tính ñuùng ñaén cuûa quy taéc choïn pixel 
Nhaéc laïi: d
i
 = e(S
i
) + e(T
i
) 
Tröôøng hôïp: d
i
 < 0 (S
i 
gaàn ñöôøng troøn hôn)
Si Si Si 
Ti Ti 
Ti 
e(Si) > 0 
e(Ti) < 0 
e(Si) > 0 
e(Ti) > 0 
e(Si) < 0 
e(Ti) < 0 
OK! OK, vì di < 0 
 S
i
 gaàn ñöôøng troøn hôn
Khoâng theå! 
Slide 343 Faculty of Computer Science and Engineering - HCMUT 
Kieåm tra tính ñuùng ñaén cuûa quy taéc choïn pixel (tieáp) 
Nhaéc laïi: d
i
 = e(S
i
) + e(T
i
) 
Tröôøng hôïp: d
i
 0 (T
i
 gaàn ñöôøng troøn hôn)
Si Si Si 
Ti Ti 
Ti 
e(Si) > 0 
e(Ti) < 0 
e(Si) > 0 
e(Ti) > 0 
e(Si) < 0 
e(Ti) < 0 
Khoâng theå! OK!
OK, vì d
i
 0 
 T
i
 gaàn ñöôøng troøn hôn 
Slide 344 Faculty of Computer Science and Engineering - HCMUT 
Tính haøm soá quyeát ñònh moät caùch höõu hieäu 
Nhaéc laïi: e(P) = (x2 + y2) - R2 
Coù theå chöùng minh ñöôïc (baøi taäp): 
 d
i + 1
 = d
i
 + 4 x
i - 1
 + 6 + 2(y
i
2
 - y
i - 1
2
) - 2(y
i
 - y
i - 1
) 
 Theo quy taéc choïn pixel 
‟ neáu d
i
 < 0 thì ta coù y
i
 = y
i - 1 
, do ñoù choïn T
i
 d
i + 1
 = d
i
 + 4 x
i - 1
 + 6 
‟ neáu khoâng thì y
i
 = y
i - 1
 - 1, do ñoù choïn S
i
 d
i + 1
 = d
i
 + 4(x
i - 1
 - y
i - 1
) + 10 
Giaûi thuaät baét ñaàu nhö theá naøo? 
 x
0
 = 0, y
0
 = R 
 do ñoù S
1
 = (1, R) vaø T
1
 = (1, R - 1), vaäy 
 d
1
=e(S
1
) + e(T
1
) =(1
2
+R
2
-R
2
)+(1
2+
(R-1)
2
-R
2)=
3 - 2R 
Slide 345 Faculty of Computer Science and Engineering - HCMUT 
Giaûi thuaät cuûa Michener 
Bieåu dieãn voøng troøn trong frame buffer 
procedure MichCirc(xc : col; yc : row; Rad : integer; value : color); 
{Veõ voøng troøn coù taâm (xc, yc), baùn kính Rad, vaø maøu value} 
var 
 x : col; 
 y : row; 
 d : integer; 
begin 
 x := 0; y := Rad; 
 d := 3 - 2*Rad; 
Slide 346 Faculty of Computer Science and Engineering - HCMUT 
Giaûi thuaät cuûa Michener (tieáp) 
 while x <= y do begin 
 SetPixel(xc + x, yc + y, value); {draw 8 points } 
 SetPixel(xc - x, yc + y, value); {based on (x, y)} 
 SetPixel(xc + x, yc - y, value); 
 SetPixel(xc - x, yc - y, value); 
 SetPixel(xc + y, yc + x, value); 
 SetPixel(xc - y, yc + x, value); 
 SetPixel(xc + y, yc - x, value); 
 SetPixel(xc - y, yc - x, value); 
 if d < 0 then d := d + 4*x + 6 {update error term} 
 else begin 
 d := d + 4*(x - y) + 10; 
 y := y - 1 
 end; 
 x := x + 1 
 end 
end; {MichCirc} 
Slide 347 Faculty of Computer Science and Engineering - HCMUT 
Ñònh nghóa vuøng 
Ñònh nghóa vuøng baèng pixel 
Ñònh nghóa vuøng baèng ña giaùc 
Slide 348 Faculty of Computer Science and Engineering - HCMUT 
Định nghĩa vùng bằng pixel 
 Dựa trên màu của các pixel 
 Hai cách định nghĩa tính kết nối: 
– 4-connected: 2 điểm ảnh được xem là kết nối nếu 
chúng nằm kề nhau theo chiều ngang hay chiều dọc 
– 8-connected: 2 điểm ảnh được xem là kết nối nếu 
chúng nằm kề nhau theo chiều ngang, chiều dọc hay 
đường chéo 
 Hai cách xác định vùng bởi: 
– Tất cả các điểm ảnh trong vùng có cùng 1 màu, có thể 
có lỗ trống (hole) bên trong. 
– Vùng được xác định bởi các điểm ảnh có cùng màu của 
đường bao quanh, các điểm ảnh bên trong không có 
màu bao, có thể có lỗ trống bên trong 
Slide 349 Faculty of Computer Science and Engineering - HCMUT 
Ví duï 
Slide 350 Faculty of Computer Science and Engineering - HCMUT 
Giải thuật tô màu tràn đệ qui 
 Dùng trong các phần mềm đồ họa 
 Vùng xác định bởi 1 màu và 4-connected 
 Bắt đầu bằng bởi 1 điểm hạt giống (seed) nằm bên trong vùng cần tô 
procedure FloodFill(x : col; y : row; int_color, new_color : color); 
{bắt đầu từ điểm (x,y), đổi từ màu int_color sang new_color} 
begin 
 if GetPixel(x, y) = int_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); 
 end 
end; 
Slide 351 Faculty of Computer Science and Engineering - HCMUT 
Giải thuật tô màu tràn đệ qui (tt.) 
 Vùng xác định bởi 1 màu và 8-connected 
 Bắt đầu bằng bởi 1 điểm hạt giống (seed) nằm bên trong vùng 
cần tô 
 Thêm: 
 FloodFill(x – 1, y – 1, int_color, new_color); 
 FloodFill(x – 1, y + 1, int_color, new_color); 
 FloodFill(x + 1, y + 1, int_color, new_color); 
 FloodFill(x + 1, y – 1, int_color, new_color); 
. Nhược điểm: 
 - bị lặp lại nhiều lần 
 - dễ bị tràn stack 
Slide 352 Faculty of Computer Science and Engineering - HCMUT 
Giải thuật tô màu tràn đệ qui (tt.) 
 Vùng xác định bởi màu bao và 4-connected 
 Bắt đầu bằng bởi 1 điểm hạt giống (seed) nằm bên trong vùng cần tô 
procedure FloodFill(x : col; y : row; int_color, new_color : color); 
{bắt đầu từ điểm (x,y), đổi từ màu int_color sang new_color} 
begin 
 if (GetPixel(x, y) >< 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); 
 end 
end; 
Slide 353 Faculty of Computer Science and Engineering - HCMUT 
Run of Pixels 
 Giaû thieát caùc pixel laø 4-connected 
 Giaûi thuaä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; 
Slide 354 Faculty of Computer Science and Engineering - HCMUT 
Ví duï 
Slide 355 Faculty of Computer Science and Engineering - HCMUT 
Ví duï 
D 
C 
Slide 356 Faculty of Computer Science and Engineering - HCMUT 
Ví duï 
J 
I 
G 
F 
C 
Slide 357 Faculty of Computer Science and Engineering - HCMUT 
Tô màu vùng đa giác 
Xé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ác 
– Sắp xếp các giao điểm theo chiều tăng dần giá trị x 
– Tô các điểm ảnh nằm giữa các cặp giao điểm 
Slide 358 Faculty of Computer Science and Engineering - HCMUT 
Tô màu vùng đa giác 
 Cạ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 pixel 
Slide 359 Faculty of Computer Science and Engineering - HCMUT 
Tô màu vùng đa giác 
 Active Edge List (AEL) lợi dụng tính lân cận của cạnh 
– những cạnh cắt bởi scanline y sẽ cắt bởi scanline y+1 
– giá trị x của giao điểm có thể dự đoán trước 
 type 
 edge_ptr = ^edge_info 
 edge_info = record 
 y_upper : row; 
 x_int : real; 
 recip_slope : real; 
 next : egde_ptr; 
 end; 
Slide 360 Faculty of Computer Science and Engineering - HCMUT 
Tô màu vùng đa giác 
 update AEL cho scanline y+1 
– xóa tất cả những cạnh có y_upper < new_y 
– thay đổi x_value bằng cách cộng thêm recip_slope 
– có thể thêm vào cạnh mới có y_lower = new_y 
– thứ tự của giao điểm có thể bị xáo trộn, nên phải sắp 
xếp lại 
Slide 361 Faculty of Computer Science and Engineering - HCMUT 
Tô màu vùng đa giác 
 Xây dựng bảng cạnh: edge_table: array [row] of edge_ptr