Giáo trình Đồ họa máy tính - Chương 4: Hiển thị đối tượng hai chiều

, t1, t2)) // Giai he bat phuong trinh 2 
{ 
if (ClipTest(-Dy, y1 - ymin, t1, t2)) // Giai he bat phuong trinh 3 
{ 
if (ClipTest(Dy, ymax - y1, t1, t2)) // Giai he bat phuong trinh 4 
{ 
Q1.x = x1 + t1. Dx; 
Q1.y = y1 + t1. Dy; 
Q2.x = x1 + t2. Dx; 
Q2.y = y1 + t2. Dy; 
return TRUE; 
} // Giai he bat phuong trinh 4 
} // Giai he bat phuong trinh 3 
} // Giai he bat phuong trinh 2 
} // Giai he bat phuong trinh 1 
return FALSE; 
} // LiangBarskyClipping 
Nhận xét 
Thông thường, thuật toán Liang-Barsky cho tốc độ tốt hơn thuật toán 
Cohen-Sutherland vì rút gọn được số giao điểm cần tính. Mỗi lần cập nhật 
các giá trị 21 , tt , chỉ cần một phép chia, và giao điểm của đoạn thẳng với 
cửa sổ chỉ được tính duy nhất một lần sau khi đã tìm ra được giá trị 21 , tt . 
Trong khi đó thuật toán Cohen-Sutherland đôi lúc phải tính giao điểm cho 
các điểm không nằm trong biên của cửa sổ đòi hỏi nhiều phép toán hơn. 
3. THUẬT TOÁN XÉN ĐA GIÁC 
Chúng ta có thể hiệu chỉnh các thuật toán xén đoạn thẳng để xén đa giác 
bằng cách xem đa giác như là một tập các đoạn thẳng liên tiếp nối với 
nhau. Tuy nhiên, kết quả sau khi xén nhiều khi lại là tập các đoạn thẳng 
rời nhau. Điều chúng ta mong muốn ở đây đó là kết quả sau khi xén phải 
là một các đa giác để sau này có thể chuyển thành các vùng tô. 
Hình 4.11 – Kết quả sau khi xén đa giác ban đầu. Đa giác ban đầu (a). Kết quả là các đoạn rời nhau (b) 
và kết quả là các đa giác (c) 
Trong phần này chúng ta sẽ khảo sát một trong các thuật toán xén đa giác 
đó là thuật toán Sutherland-Hodgeman. 
Hình 4.12 – Quá trình xén một đa giác vào cửa sổ 
Thuật toán này sẽ tiến hành xén đa giác lần lượt với các biên cửa sổ. Đầu 
tiên, đa giác sẽ được xén dọc theo biên trái của cửa sổ, kết quả sau bước 
này sẽ được dùng để xén tiếp biên phải, rồi cứ tương tự như vậy cho các 
biên trên, dưới. Sau khi xén hết với bốn biên của cửa sổ, ta được kết quả 
cuối cùng. 
Với mỗi lần xén đa giác dọc theo một biên nào đó của cửa sổ, nếu gọi 
1, +ii VV là hai đỉnh kề cạnh 1+iiVV , ta có 4 trường hợp có thể xảy ra khi xét 
từng cặp đỉnh của đa giác ban đầu với biên của cửa sổ như sau: 
• (i) Nếu iV nằm ngoài, 1+iV nằm trong, ta lưu giao điểm I của 1+iiVV với 
biên của cửa sổ và 1+iV . 
• (ii) Nếu cả iV , 1+iV đều nằm trong, ta sẽ lưu cả iV , 1+iV . 
(a) (b) (c)
• (iii) Nếu iV nằm trong, 1+iV nằm ngoài, ta sẽ lưu iV và I. 
• (iv) Nếu cả iV , 1+iV đều nằm ngoài, ta không lưu gì cả. 
Hình 4.13 – Các trường hợp khi xét 1, +ii VV với các biên của cửa sổ 
Cài đặt minh họa thuật toán Sutherland-Hodgeman 
#include 
#include 
#include 
#include 
#include 
#define TRUE 1 
#define FALSE 0 
#define LEFT 1 
#define RIGHT 2 
#define TOP 4 
#define BOTTOM 8 
typedef struct { 
 int x, y; 
}POINT; 
typedef struct { 
 int Left, Top, Right, Bottom; 
}RECT; 
// Xac dinh p co nam ben trong cua so neu xet theo mot canh b 
int Inside(POINT p, int Edge, RECT rWin) 
{ 
 switch(Edge) 
 { 
case LEFT : 
if(p.x < rWin.Left) 
return FALSE; 
break; 
case RIGHT : 
if(p.x > rWin.Right) 
 return FALSE; 
break; 
case TOP : 
if(p.y > rWin.Top) 
 return FALSE; 
break; 
case BOTTOM : 
if(p.y < rWin.Bottom) 
 return FALSE; 
break; 
 } 
 return TRUE; 
Vi Vi+1I Vi
Vi+1
Vi
Vi+1
I
(i)
Vi
Vi+1
(ii) (iii) (iv)
} //Inside 
// Tra ve giao diem cua doan noi p1&p2 voi canh b 
POINT Intersect(POINT p1, POINT p2, int Edge, RECT rWin) 
{ 
 POINT iPt; 
 float m; 
if(p1.x != p2.x) 
 m = float(p2.y-p1.y)/(p2.x-p1.x); 
switch(Edge) 
{ 
case LEFT : 
iPt.x = rWin.Left; 
iPt.y = p2.y + (rWin.Left-p2.x)*m; 
break; 
case RIGHT : 
iPt.x = rWin.Right; 
iPt.y = p2.y + (rWin.Right-p2.x)*m; 
break; 
case TOP : 
iPt.y = rWin.Top; 
if(p1.x != p2.x) 
 iPt.x = p2.x + (rWin.Top-p2.y)/m; 
else 
 iPt.x = p2.x; 
break; 
case BOTTOM : 
iPt.y = rWin.Bottom; 
if(p1.x != p2.x) 
 iPt.x = p2.x + (rWin.Bottom-p2.y)/m; 
else 
 iPt.x = p2.x; 
break; 
} 
return (iPt); 
} // Intersect 
// Tien hanh cat da giac voi mot canh nao do cua cua so. 
void ClipEdge(POINT *pIn, int N, POINT *pOut, int &Cnt, int Edge, 
RECT rWin) 
{ 
int FlagPrevPt = FALSE; 
Cnt = 0; 
POINT pPrev; 
pPrev = pIn[0]; 
if(Inside(pPrev, Edge, rWin)) // Save point 
{ 
pOut[Cnt] = pPrev; 
Cnt++; 
FlagPrevPt = TRUE; 
} 
for(int i=1; i<N; i++) 
{ 
if(FlagPrevPt) // Diem bat dau nam trong 
{ 
if(Inside(pIn[i], Edge, rWin)) // Save point P 
{ 
 pOut[Cnt] = pIn[i]; 
 Cnt++; 
} 
else // Save I 
{ 
 FlagPrevPt = FALSE; 
 pOut[Cnt] = Intersect(pPrev, pIn[i], Edge, rWin); 
 Cnt++; 
} 
} 
else // Diem bat dau canh nam ngoai 
{ 
if(Inside(pIn[i], Edge, rWin)) // Save point I, P 
{ 
 FlagPrevPt = TRUE; 
 pOut[Cnt] = Intersect(pPrev, pIn[i], Edge, rWin); 
 Cnt++; 
 pOut[Cnt] = pIn[i]; 
 Cnt++; 
} 
} 
pPrev = pIn[i]; 
} 
// Neu Diem cuoi va dau giao voi bien cua cua so Save point I 
if(!(Inside(pIn[N], Edge, rWin) == Inside(pPrev, Edge, rWin))) 
{ 
 pOut[Cnt] = Intersect(pPrev, pIn[N], Edge, rWin); 
 Cnt++; 
} 
pOut[Cnt] = pOut[0]; 
} // Intersect 
void ClipPolygon(POINT *pIn, int N, POINT *pOut, int &Cnt, 
RECT rWin) 
{ 
 POINT pTmp[20]; 
 _fmemcpy(pTmp, pIn, (N+1)*sizeof(POINT)); 
 ClipEdge(pTmp, N, pOut, Cnt, LEFT, rWin); 
 N = Cnt; 
 _fmemcpy(pTmp, pOut, (N+1)*sizeof(POINT)); 
 ClipEdge(pTmp, N, pOut, Cnt, RIGHT, rWin); 
 N = Cnt; 
 _fmemcpy(pTmp, pOut, (N+1)*sizeof(POINT)); 
 ClipEdge(pTmp, N, pOut, Cnt, TOP, rWin); 
 N = Cnt; 
 _fmemcpy(pTmp, pOut, (N+1)*sizeof(POINT)); 
 ClipEdge(pTmp, N, pOut, Cnt, BOTTOM, rWin); 
} // ClipPolygon 
Nhận xét 
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 như hình 4.11. Điều này xảy ra khi đa giác sau khi xén bị 
tách thành hai hay nhiều vùng. Do chúng ta chỉ lưu kết quả xuất trong một 
danh sách các đỉnh nên đỉnh cuối của danh sách ứng với đa giác trước sẽ 
nối với đỉnh đầu của danh sách ứng với đa giác sau. Một trong nhiều cách 
để khắc phục điểm này là phân đa giác lõm thành hai hay nhiều đa giác 
lồi và xử lí mỗi đa giác lồi riêng. 
TÓM TẮT 
Hiển thị đối tượng là quá trình đưa các mô tả đối tượng từ thế giới thực sang một thiết bị xuất cụ thể 
nào đó. Quy trình này bắt đầu bằng cách định nghĩa từng đối tượng thành phần trong hệ tọa độ cục bộ 
và kết thúc bằng việc chuyển toàn bộ đối tượng lên hệ tọa độ thiết bị. Bằng cách đưa ra định nghĩa hệ 
tọa độ quan sát và các khái niệm cửa sổ, vùng quan sát; mỗi đối tượng có thể được quan sát ở nhiều vị trí 
và góc độ khác nhau. Thông thường mỗi hình ảnh mà chúng ta quan sát được trên màn hình thiết bị được 
gọi là một thể hiện (view) của đối tượng. 
Quá trình ánh xạ một vùng định nghĩa trong hệ tọa độ thế giới thực vào một vùng trong hệ tọa độ 
thiết bị được gọi là phép biến đổi hệ quan sát. Đây thực chất là phép biến đổi hệ tọa độ. Quá trình loại 
bỏ các phần hình ảnh nằm ngoài một vùng cho trước được gọi là xén hình. Vùng được dùng để xén hình 
gọi là cửa sổ xén. 
Các thuật toán xén đoạn thẳng Cohen-Sutherland, Liang-Barsky đều tập trung giải quyết hai vấn đề 
chính nhằm tối ưu tốc độ thuật toán đó là : loại bỏ việc tìm giao điểm đối với các đoạn thẳng chắc chắn 
không cắt cửa sổ (như nằm hoàn toàn trong, nằm hoàn toàn ngoài), và với các đoạn có khả năng cắt 
cửa sổ, cần phải tìm cách hạn chế số lần cần tìm giao điểm với các biên không cần thiết. Thuật toán 
Cohen-Sutherland giải quyết hai ý này thông qua kiểu dữ liệu mã vùng mà về mặt bản chất đó chỉ là sự 
mô tả vị trí tương đối của vùng đang xét so với các biên của cửa sổ. Còn thuật toán Liang-Barsky thì tuy 
dựa vào phương trình tham số của đoạn thẳng để lập luận nhưng thực chất là dựa trên việc xét các giao 
điểm có thể có giữa đoạn thẳng kéo dài với các biên của cửa sổ (cũng được kéo dài). Các giao điểm 
này tương ứng với các giá trị kkk pqr /= . Cả hai thuật toán này đều có thể được mở rộng cho việc xén 
hình trong đồ họa ba chiều. 
BÀI TẬP 
1. Phân tích các hệ tọa độ dùng trong quy trình hiển thị đối tượng hai chiều. 
2. Viết đoạn chương trình minh họa quá trình chuyển đổi từ cửa sổ sang vùng quan sát. 
3. Ý nghĩa của mã vùng trong thuật toán Cohen-Sutherland. 
4. Hãy cho một đoạn thẳng minh họa mà trong trường hợp này thuật toán phải thực 
hiện việc tìm giao điểm 4 lần theo thứ tự LEFT, TOP, RIGHT, BOTTOM. 
5. Cài đặt thuật toán Cohen-Sutherland để xén một đa giác. Phân tích các trường hợp 
thuật toán này cho kết quả là các đoạn thẳng rời rạc. 
6. So sánh hai thuật toán Cohen-Sutherland và Liang-Barsky về số phép toán thực hiện 
trong các trường hợp chính. 
7. Cài đặt thuật toán Liang-Barsky và so sánh với tốc độ thuật toán Cohen-Sutherland. 
8. Hiệu chỉnh các thuật toán xén đoạn thẳng đã học để có thể xén đoạn thẳng vào cửa 
sổ hình chữ nhật nghiêng với trục hoành một góc α . 
9. Trình bày và cài đặt thuật toán phân một đa giác lõm thành các đa giác lồi. 
10. Dựa trên kết quả của bài tập trên, hiệu chỉnh thuật toán Sutherland-Hodgeman để 
xén các đa giác lõm được chính xác.