Bài giảng Đồ họa máy tính: Mô hình và cấu trúc

10/22/2007Bùi Thế Duy - Bộ môn KHMT 1 Đồ họa máy tính Mô hình và cấu trúc 10/22/2007Bùi Thế Duy - Bộ môn KHMT 2 Bề mặt đa giác z Dạng 3D cơ bản trong hầu hết các ứng dụng – trong tất cả các ứng dụng thời gian thực. z Xử lý dễ và nhanh. z Một số ứng dụng có thể sử dụng các hình khối khác, v.d. Splines, tuy nhiên sau đó đều đưa về dạng đa giác để xử lý. z Rất phù hợp với thuật toán “dòng quét” (scan-line algorithms). 10/22/2007Bùi Thế Duy - Bộ môn KHMT 3 Thuật toán quét đơn giản z Khi cần phải tô màu đa giác. z Cài đặt một thuật toán quét đơn giản. z Tìm các giao điểm của đường quét với đa giác Finish Start Scan line 10/22/2007Bùi Thế Duy - Bộ môn KHMT 4 Các loại đa giác. Loại z Tam giác z Tứ giác z Hình bốn cạnh z Lồi z Lõm z Tự cắt z Lặp nhiều lần z Có lỗ hổng Lõm Có lỗ hổng Lồi Tự cắt Hai cách tiếp cận : • Thuật toán quét tổng quát • Chia thành các tam giác 10/22/2007Bùi Thế Duy - Bộ môn KHMT 5 Định nghĩa z Một đa giác là lồi nếu: với mọi cạnh, tất cả các đỉnh của đa giác nằm trên cùng nửa mặt phẳng tạo bởi cạnh đó. z Nếu không, đó là đa giác lõm. z Các đa giác lõm có thể rất khó xử lý. LõmLồi 10/22/2007Bùi Thế Duy - Bộ môn KHMT 6 Tam giác luôn lồi z Đơn giản về mặt toán học – chỉ liên quan đến phương trình tuyến tính đơn giản. z Ba điểm đảm bảo nằm trên cùng mặt phẳng. z Bất cứ đa giác nào cũng có thể tách ra thành các tam giác. z Các tam giác có thể dùng để xấp xỉ các hình khối. z Theo bất cứ chiều nào, một đường quét sẽ chỉ cắt tam giác một đoạn duy nhất. 10/22/2007Bùi Thế Duy - Bộ môn KHMT 7 Tách đa giác Tách các đa giác lồi là một công việc đơn giản, tuy nhiên tách các đa giác lõm thì không đơn giản chút nào. Trong một số trường hợp, phải thêm các đỉnh mới. 10/22/2007Bùi Thế Duy - Bộ môn KHMT 8 Xấp xỉ bất cứ hình nào bằng các tam giác Bất cứ mặt 2D hay hình khối 3D nào cũng có thể được xấp xỉ bởi các đa giác. Để tăng độ chính xác, chỉ cần tăng số đa giác. 10/22/2007Bùi Thế Duy - Bộ môn KHMT 9 Các hình bốn cạnh cũng đơn giản và cũng thường được dùng lẫn với tam giác 10/22/2007Bùi Thế Duy - Bộ môn KHMT 10 Thể hiện các hình Đa giác V1 V2 V3 P1 P2 E1 E2 E3 Dùng con trỏ đến danh sách các điểm. • Phải tìm các đa giác nằm cạnh nhau. • Các cạnh phải vẽ hai lần. Dùng con trỏ đến danh sách cạnh, các cạnh trỏ đến các điểm. Lưu trữ toàn bộ các đỉnh của đa giác • Không hiệu quả • Không thể thay đổi vị trí các điểm. 10/22/2007Bùi Thế Duy - Bộ môn KHMT 11 Cấu trúc dữ liệu đa giác chuẩn 10/22/2007Bùi Thế Duy - Bộ môn KHMT 12 Tô màu tam giác (filling, tiling) z Tính hình chữ nhật bao ngoài cho tam giác z Với tất cả các điểm trong hình chữ nhật – Kiểm tra xem điểm đó có nằm trong tam giác hay không – Nếu nằm trong thì vẽ điểm đó Bounding box 10/22/2007Bùi Thế Duy - Bộ môn KHMT 13 Tô màu tam giác tile3( vert v[3] ) { int x, y; bbox b; bound3(v,&b); // calculate bounding box for( y=b.ymin; y<b.ymax, y++ ) for( x=b.xmin; x<b.xmax, x++ ) if( inside3(v,x,y) ) draw_fragment(x,y); } Bounding box 10/22/2007Bùi Thế Duy - Bộ môn KHMT 14 Kiểm tra một điểm nằm trong tam giác z Viết phương trình đường thẳng cho các cạnh, kiểm tra xem điểm đó có nằm cùng nửa mặt phẳng với đỉnh còn lại của đa giác z Có thể ngừng kiểm tra sớm nếu sai với một cạnh. cbyaxyxf ++=),( 10/22/2007Bùi Thế Duy - Bộ môn KHMT 15 Tô màu tam giác tile3( vert v[3] ) { int x, y; bbox b;edge l0, l1, l2; float e0, e1, e2; make_edge(&v[0],&v[1],&l2); // Calculate a,b & c for the edges make_edge(&v[1],&v[2],&l0); make_edge(&v[2],&v[0],&l1); bound3(v,&b); // Calculate bounding box e0 = l0.a * b.xmin + l0.b * b.ymin + l0.c; // Calculate f(x,y) for e1 = l1.a * b.xmin + l1.b * b.ymin + l1.c; // the 3 edges. e2 = l2.a * b.xmin + l2.b * b.ymin + l2.c; for( y=b.ymin; y<b.ymax, y++ ) { for( x=b.xmin; x<b.xmax, x++ ) { if( e0<=0 && e1<=0 && e2<=0 ) draw_fragment(x,y); // Draw if e0 += l0.a; e1 += l1.a; e2 += l2.a; // inside triangle } e0 += l0.a * (b.xmin - b.xmax) + l0.b; // same for e1 & e2. } } 10/22/2007Bùi Thế Duy - Bộ môn KHMT 16 Khe hở và trường hợp đặc biệt Bỏ sót mất điểm Cạnh chung: vẽ hai lần 10/22/2007Bùi Thế Duy - Bộ môn KHMT 17 Xử lý thế nào với cạnh chung? z Vẽ các điểm nằm bên trái và dưới cạnh 10/22/2007Bùi Thế Duy - Bộ môn KHMT 18 Các khe hở Giải pháp: Kiểm tra trái phải, trên dưới 10/22/2007Bùi Thế Duy - Bộ môn KHMT 19 Tổng kết z Kiểm tra xem một điểm có nằm trong tam giác không. z Vấn đề với khe hở. z Vấn đề với các đa giác lõm. 10/22/2007Bùi Thế Duy - Bộ môn KHMT 20 Tách đa giác thành các tam giác z Dùng cách kiểm tra điểm nằm ở nửa mặt phẳng nào, có thể tách đa giác thành các tam giác. P1 P3 P5P7 Đơn giản với đa giác lồi.P6 Đa giác lõm khó hơn nhiều. P4 P0 P2 10/22/2007Bùi Thế Duy - Bộ môn KHMT 21 Tách đa giác z Kiểm tra xem mọi điểm có nằm ngoài tam giác ABC không. A B C D Điểm ‘D’ nằm ngoài. 10/22/2007Bùi Thế Duy - Bộ môn KHMT 22 Tách đa giác z Nếu mọi điểm nằm ngoài tam giác⇒ lưu lại tam giác, bỏ đỉnh đó và tiếp tục với đỉnh trái nhất tiếp theo. z Nếu có một đỉnh nằm trong, tạo nên một tam giác mới với điểm nằm trong trái nhất. B C D Kiểm tra ABD tương tự, A 10/22/2007Bùi Thế Duy - Bộ môn KHMT 23 Định lý Jordan. Một cách khác để kiểm tra một điểm nằm trong hay ngoài đa giác •Hai định nghĩa của nằm bên trong: •Kiểm tra tính chẵn lẻ của số điểm cắt 0 1 234 Số điểm cắt chẵn: Ngoài đa giác Số điểm cắt lẻ: Trong đa giác 10/22/2007Bùi Thế Duy - Bộ môn KHMT 24 Định lý Jordan. 0 1 234 Số điểm cắt chẵn: Ngoài đa giác Số điểm cắt lẻ: Trong đa giác Không đúng đối với đa giác tự cắt 0 1 2 3 4 10/22/2007Bùi Thế Duy - Bộ môn KHMT 25 Định lý Jordan Kiểm tra đại lượng e -Sử dụng cả hướng của đường thẳng -đặt e = 0 -Cắt từ trái qua phải e + +, phải qua trái e - - -e != 0, nằm trong 0 1 2 1 0 0 1 01 10/22/2007Bùi Thế Duy - Bộ môn KHMT 26 Trường hợp đặc biệt • Có 2 trường hợp đặc biệt trong thuật toán Jordan : • Cắt trùng lên cạnh • Cắt trùng lên đỉnh đa giác 10/22/2007Bùi Thế Duy - Bộ môn KHMT 27 Thuật toán đường quét z Kiểm tra Jordan tăng dần z Sắp xếp theo giá trị của y y 10/22/2007Bùi Thế Duy - Bộ môn KHMT 28 Thuật toán đường quét z Kiểm tra Jordan tăng dần z Sắp xếp theo giá trị của y z Sử dụng sự liên kết giữa các đường quét – giá trị cho đường quét trước gần bằng giá trị cho đường quét sau. z Lưu trữ danh sách các cạnh đang xét 10/22/2007Bùi Thế Duy - Bộ môn KHMT 29 Danh sách các cạnh đang xét Xóa Tạo Thay thế Các đỉnh là các ‘sự kiện’ trong danh sách cạnh – các cạnh có thể được xét, không được xét hoặc được thay bằng các cạnh khác - Sắp xếp các giao điểm theo x - Kết quả chính là phần giữa cạnh bên trái và bên phải y 10/22/2007Bùi Thế Duy - Bộ môn KHMT 30 Tô màu tam giác 0 1 2 ystruct edge { int x ; // x intercept of a point on // the line. // y coord is assumed to be // current scanline float dxdy ; // dx/dy for the line } struct vert { int x ; int y ; } Assume : 1. Vertices already sorted 2. Single left hand edge - Tại sao dùng dx/dy ? Vì chúng ta có thể tăng dần giá trị của y và mỗi lần tăng x một đại lượng dx/dy 10/22/2007Bùi Thế Duy - Bộ môn KHMT 31 Tô màu tam giác 0 1 2 e2 e1 e0 scany( vert v[3]) { ybot = ceil(v[0].y); ymid = ceil(v[1].y); ytop = ceil(v[2].y); // Make edges. l is left edge, r is right mkedge(&v[0],&v[2],&e1,ybot); mkedge(&v[0],&v[1],&e2,ybot); mkedge(&v[1],&v[2],&e0,ymid); l=e1; r=e2; for( y=ybot; y<ytop; y++ ) { if( y >= ymid ) r = e0; scanx(&l,&r,y); l.x += l.dxdy; r.x += r.dxdy; } } Assume : 1. Vertices already sorted 2. Single left hand edge 10/22/2007Bùi Thế Duy - Bộ môn KHMT 32 Tô màu tam giác b t e->x y mkedge(vert *b, vert *t, edge *e, int y) { e->dxdy = (t->x - b->x) / (t->y - b->y); e->x = b->x + (y - b->y) * e->dxdy; } scanx( edge *l, edge *r, int y) { lx = ceil(l->x); rx = ceil(r->x); for( x=lx; x<rx; x++ ) fragment(x,y); } 10/22/2007Bùi Thế Duy - Bộ môn KHMT 33 Tổng kết z Thực hiện kiểm tra Jordan tăng dần. z Lưu trữ một danh sách các cạnh đang xét. z Tô màu đoạn nằm giữa cạnh trái và cạnh phải z Sử dụng phương trình đường thẳng để tính ra các vị trí cắt tiếp theo 10/22/2007Bùi Thế Duy - Bộ môn KHMT 34 Làm thế nào để vẽ các tam giác nhanh hơn? z Thể hiện một tam giác bằng 3 đỉnh và 3 cạnh. Nếu ta thực hiện các phép biên đổi với một tam giác, chúng ta phải biến đổi tọa độ của 3 điểm. ⇒ 3 phép toán ma trận cho một tam giác 10/22/2007Bùi Thế Duy - Bộ môn KHMT 35 Quạt tam giác. z Các tam giác được dùng trong các hình khối phức tạp. Quạt tam giác. Để thêm một tam giác mới, chỉ cần thêm một đỉnh. Đỏ - đỉnh đang có. Đen – đỉnh mới 10/22/2007Bùi Thế Duy - Bộ môn KHMT 36 Chuỗi tam giác z Sử dụng các tam giác để thể hiện các vật đặc. z Các tam giác thường xuất hiện theo chuỗi: Một tam giác mới được thể hiện qua một điểm mới thêm vào chuỗi 10/22/2007Bùi Thế Duy - Bộ môn KHMT 37 Làm thế nào để vẽ các đa giác nhanh hơn? z Đối với các quạt và chuỗi tam giác, chỉ cần thêm một phép biến đổi cho mỗi tam giác mới. – 1 phép tính ma trận cho một tam giác. – Nhanh hơn rất nhiều! z Cũng như vậy với chuỗi tứ giác - 2 đỉnh mới cho một tứ giác 10/22/2007Bùi Thế Duy - Bộ môn KHMT 38 Tổng kết z Tam giác – 3 phép tính ma trận cho mỗi phép biến đổi tam giác. z Quạt tam giác – Một nhóm các tam giác cùng chung một đỉnh – 1 phép tính ma trận cho mỗi biến đổi tam giác. z Chuỗi tam giác – Nhóm các tam giác, tam giác trước và sau chung nhau 2 đỉnh. – 1 phép tính ma trận cho mỗi biến đổi tam giác. 10/22/2007Bùi Thế Duy - Bộ môn KHMT 39 10/22/2007Bùi Thế Duy - Bộ môn KHMT 40 10/22/2007Bùi Thế Duy - Bộ môn KHMT 41 10/22/2007Bùi Thế Duy - Bộ môn KHMT 42 10/22/2007Bùi Thế Duy - Bộ môn KHMT 43 10/22/2007Bùi Thế Duy - Bộ môn KHMT 44 10/22/2007Bùi Thế Duy - Bộ môn KHMT 45 10/22/2007Bùi Thế Duy - Bộ môn KHMT 46