›
›

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

Download
CHƯƠNG 4  
HIỂN THỊ ĐỐI TƯỢNG HAI CHIỀU  
Chương này sẽ đề cập tới các kĩ thuật để hiển thị các đối tượng hai chiều trên các thiết bị  
như màn hình, máy in, …  
Các hệ đồ họa cho phép người dùng mô tả các hình ảnh bằng hệ tọa độ thế giới thực. Nó  
có thể là bất kì hệ tọa độ Descartes nào mà người dùng cảm thấy thuận tiện nhất khi sử  
dụng. Các hình ảnh được mô tả trong hệ tọa độ thực sau đó sẽ được các hệ đồ họa ánh xạ  
vào hệ tọa độ thiết bị. Thông thường các hệ đồ họa cho phép người dùng xác định vùng  
nào của hình ảnh được hiển thị và nó sẽ được hiển thị ở đâu trên màn hình. Ta có thể  
chọn một vùng hay một số vùng để hiển thị cùng một lúc, các vùng này có thể đặt ở các  
nơi khác nhau trên màn hình hay lồng vào nhau. Quá trình biến đổi này đòi hỏi các phép  
biến đổi như dịch chuyển, quay, biến đổi tỉ lệ; và các thao tác loại bỏ các vùng hình ảnh  
nằm ngoài vùng được định nghĩa, ….  
1. QUY TRÌNH HIỂN THỊ ĐỐI TƯỢNG HAI CHIỀU  
1.1. Một số khái niệm  
Cửa sổ (window) là một vùng được chọn để hiển thị trong hệ tọa độ thế giới thực.  
Vùng quan sát (viewport) là vùng được chọn trên thiết bị hiển thị để các đối tượng ở  
trong cửa sổ ánh xạ vào.  
Cửa sổ xác định cái gì được thấy trên thiết bị hiển thị, còn vùng quan sát xác định nơi  
nào nó sẽ được hiển thị.  
Ở đây chúng ta nên phân biệt khái niệm cửa sổ được dùng trong phần này với khái niệm  
cửa sổ được dùng trong các chương trình ứng dụng trên các hệ điều hành như Windows.  
Thông thường cửa sổ và vùng quan sát có dạng hình chữ nhật, có các cạnh song song với  
các trục tọa độ. Tuy nhiên chúng cũng còn có một số dạng khác như đa giác, hình tròn,  
…
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 (viewing transformation).  
Hình 4.1 – Phép biến đổi hệ quan sát với cửa sổ và vùng quan sát có dạng là các hình chữ nhật  
Quy trình hiển thị các đối tượng trong đồ họa hai chiều có thể được mô tả qua sơ đồ sau :  
Trước tiên, các đối tượng sẽ được mô tả bằng các đối tượng đồ họa cơ sở và các thuộc  
tính của chúng trong từng hệ tọa độ cục bộ (modeling coordinates - MC) nhằm đơn giản  
hóa và tận dụng các đặc trưng riêng của từng loại. Sau đó, chúng ta sẽ dùng các phép biến  
đổi hệ tọa độ để chuyển các mô tả từ các hệ tọa độ cục bộ này sang một hệ tọa độ thế giới  
thực (world coordinates - WC) duy nhất chứa toàn bộ các đối tượng thành phần. Phép  
chuyển đổi này được gọi là phép chuyển đổi mô hình (modeling coordinates  
transformation).  
Tiếp theo, chúng ta sẽ định một hệ tọa độ quan sát (viewing coordinates - VC), là hệ tọa  
độ mô tả vị trí của người quan sát đối tượng. Nhờ việc sử dụng hệ tọa độ này mà cùng  
một mô tả, các đối tượng có thể được quan sát ở nhiều góc độ và vị trí khác nhau.  
Sau khi chuyển các mô tả đối tượng từ hệ tọa độ thế giới thực sang hệ tọa độ quan sát,  
chúng ta sẽ định nghĩa cửa sổ trong hệ tọa độ này, đồng thời định nghĩa vùng quan sát  
trong hệ tọa độ thiết bị chuẩn (normalized device coordinates - NDC) có tọa độ các chiều  
thay đổi trong khoảng từ 0 đến 1.  
Sau khi thực hiện phép ánh xạ từ cửa sổ sang vùng quan sát, tất cả các phần của đối  
tượng nằm ngoài vùng quan sát sẽ bị xén (clip) và toàn bộ những gì nằm trong vùng quan  
sát sẽ được ánh xạ sang hệ tọa độ thiết bị (device coordinates - DC). Việc đưa ra hệ tọa  
độ thiết bị chuẩn nhằm giúp cho việc tương thích dễ dàng với nhiều loại thiết bị hiển thị  
khác nhau.  
Hình 4.2 – Quy trình hiển thị đối tượng hai chiều  
Bằng cách thay đổi vị trí của vùng quan sát chúng ta có thể quan sát các đối tượng tại các  
vị trí khác nhau trên màn hình hiển thị, đồng thời, bằng cách thay đổi kích thước của  
vùng quan sát, chúng ta có thể thay đổi kích thước và tính cân xứng của các đối tượng  
được hiển thị. Chúng ta có thể thực hiện các hiệu ứng thu phóng bằng cách ánh xạ các  
cửa sổ có kích thước khác nhau vào vùng quan sát có kích thước cố định. Khi các cửa sổ  
được thu nhỏ, phần nằm trong cửa sổ sẽ được phóng to giúp chúng ta dễ dàng quan sát  
các chi tiết mà không thể thấy được trong các cửa sổ lớn hơn.  
1.2. Hệ tọa độ quan sát và hệ tọa độ thiết bị chuẩn  
1.2.1. Hệ tọa độ quan sát  
Để thiết lập hệ tọa độ quan sát, trước tiên ta sẽ chọn một điểm P0  
thực làm gốc tọa độ. Sau đó chúng ta sẽ sử dụng một vector V mô tả hướng quan sát để định hướng cho  
trục tung v của hệ tọa độ. Vector V được gọi là view-up vector.  
x0 , y0 trong hệ tọa độ thế giới  
y
Từ V chúng ta có thể tính được các vector đơn vị v vx ,vy  
trục tung yv và trục hoành xv của hệ tọa độ. Các vector đơn vị này sẽ được dùng để tạo thành hai dòng  
và u  
ux ,uy tương ứng cho các  
đầu tiên của ma trận quay MR để đưa các trục xv yv trùng với các trục xw yw của hệ trục tọa độ thế giới  
thực.  
Hình 4.3 – Phép biến đổi một điểm từ hệ tọa độ quan sát sang hệ tọa độ thực  
Ma trận của phép chuyển một điểm trong hệ tọa độ thế giới thực sang hệ tọa độ quan sát  
là tích của hai ma trận của các phép biến đổi : phép tịnh tiến gốc tọa độ hệ quan sát về  
gốc tọa độ hệ tọa độ thế giới thực, phép quay đưa các trục của hệ tọa độ quan sát trùng  
với các trục của hệ tọa độ thế giới thực. MWC,VC MT MR  
.
1.2.2. Hệ tọa độ thiết bị chuẩn  
Do cách định nghĩa củ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 chưa chắc hiển thị chính xác trên thiết bị kia. Chính vì vậy cần phải xây  
dựng hệ tọa độ thiết bị chuẩn đại diện chung cho các thiết bị để có thể mô tả các hình ảnh  
của thế giới thực mà không phụ thuộc vào bất cứ thiết bị nào.  
Trong hệ tọa độ này, các tọa độ x, y sẽ được gán các giá trị trong khoảng từ 0 đến 1. Như  
vậy, vùng không gian của hệ tọa độ thiết bị chuẩn chính là hình vuông đơn vị có góc trái  
dưới là (0,0) và góc phải trên (1,1).  
Hình 4.4 – Hệ tọa độ thiết bị chuẩn  
1.3. Chuyển đổi từ cửa sổ sang vùng quan sát  
Phép chuyển đổi từ cửa sổ sang vùng quan sát bao gồm 3 phép biến đổi : phép tịnh tiến  
để dịch chuyển góc trái dưới về gốc tọa độ (hình 4.5a), phép biến đổi tỉ lệ để chỉnh kích  
thước của cửa sổ về cùng kích thước của vùng quan sát (hình 4.5b, hình 4.5c), cuối cùng  
là phép tịnh tiến dịch chuyển về góc trái dưới của vùng quan sát (hình 4.5d).  
Hình 4.5 – Phép chuyển đổi từ cửa sổ sang vùng quan sát  
Ta có ma trận của phép biến đổi :  
umax umin vmax vmin  
xmax xmin ymax ymin  
MWV MTW  
xmin ,ymin  
MS  
,
MTV  
umin ,vmin  
umax umin  
xmax xmin  
0
0
0
1
vmax vmin  
ymax ymin  
vmax vmin  
0
umax umin  
xmax xmin  
xmin  
umin ymin  
vmin  
ymax ymin  
Như vậy nếu P  
x, y  
là điểm trong cửa sổ thì nó sẽ có tọa độ trong vùng quan sát là :  
umax umin  
xmax xmin  
vmax vmin  
ymax ymin  
sx  
x xmin umin , sy  
y ymin  
vmin  
với sx   
, sy   
.
sx, sy là các hệ số tỉ lệ của các kích thước của cửa sổ và vùng quan sát. Khi sx sy 1 , các đối  
tượng qua phép chuyển đổi sẽ được giữ nguyên hình dáng và tính cân xứng.  
1.4. Các thuật toán xén hình  
Thao tác 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 (clip window).  
Tùy thuộc vào từng ứng dụng cụ thể mà cửa sổ xén có thể có dạng là đa giác hay là  
đường cong khép kín. Trong phần này chúng ta sẽ khảo sát các thuật toán xén hình vào  
cửa sổ xén là hình chữ nhật trước, sau đó sẽ khảo sát các cửa sổ xén có dạng khác. Để  
đơn giản, trong các thuật toán xén hình, cửa sổ xén được gọi là cửa sổ.  
2. CÁC THUẬT TOÁN XÉN ĐIỂM, ĐOẠN THẲNG  
Giả sử cửa sổ xén là cửa sổ hình chữ nhật có tọa độ của các điểm dưới bên trái và điểm trên bên phải  
lần lượt là  
xmin , ymin  
và  
xmax , ymax  
.
Một điểm  
P
x, y  
được coi là nằm bên trong cửa sổ nếu thỏa hệ bất phương trình :  
x
x xmax  
min  
ymin y ymax  
Bây giờ, ta sẽ xét bài toán xén đoạn thẳng được cho bởi hai điểm P1 x1, y1  
và P2  
x2 , y2 vào cửa  
sổ hình chữ nhật trên.  
Hình 4.6 – Minh họa thao tác xén các đoạn thẳng vào một cửa sổ hình chữ nhật. Trước khi xén (a). Sau khi xén (b).  
Thao tác xén hình là một trong những thao tác cơ bản của quá trình hiển thị đối tượng, do  
đó vấn đề tối ưu tốc độ luôn là đích cho các thuật toán nhắm đến. Ý tưởng chung của các  
thuật toán xén đoạn thẳng đó là loại bỏ phép toán tìm giao điểm giữa đoạn thẳng với biên  
của cửa sổ một cách nhanh nhất đối với các đoạn thẳng đặc biệt như nằm hoàn toàn trong  
hoặc hoàn toàn bên ngoài cửa sổ (ví dụ như đoạn P1P2 và P3P4 trong hình 4.6). Đối với  
các đoạn thẳng có khả năng cắt cửa sổ, cần phải đưa ra cách tìm giao điểm thật nhanh.  
Nhận xét rằng, các đoạn thẳng mà có cả hai điểm nằm hoàn toàn trong cửa sổ thì cả đoạn  
thẳng nằm trong cửa sổ, đây cũng chính là kết quả sau khi xén (ví dụ như đoạn thẳng  
P1P2), mặt khác đối với các đoạn thẳng mà có hai điểm nằm về cùng một phía của cửa sổ  
thì luôn nằm ngoài cửa sổ và sẽ bị mất sau khi xén (ví dụ như đoạn thẳng P3P4). Với các  
đoạn thẳng có khả năng cắt cửa sổ (ví dụ như đoạn thẳng P5P6 và P7P8) để việc tìm giao  
điểm nhanh cần rút gọn việc tìm giao điểm với những biên cửa sổ không cần thiết để xác  
định phần giao nếu có của đoạn thẳng và cửa sổ.  
Người ta thường sử dụng phương trình tham số của đoạn thẳng trong việc tìm giao điểm  
giữa đoạn thẳng với cửa sổ.  
x x1 t  
y y1 t  
x2 x1  
x1 tDx, Dx x2 x1  
y1 tDy, Dy y2 y1 ,  
y2 y1  
0 t 1  
0,1 thì giao điểm đó sẽ không thuộc về  
Nếu giao điểm ứng với giá trị t nằm ngoài đoạn  
cửa sổ.  
2.1. Thuật toán Cohen-Sutherland  
Đây là một trong những thuật toán ra đời sớm nhất và thông dụng nhất.  
Bằng cách kéo dài các biên của cửa sổ, người ta chia mặt phẳng thành chín vùng gồm cửa  
sổ và tám vùng xung quanh nó.  
Khái niệm mã vùng (area code)  
Một con số 4 bit nhị phân gọi là mã vùng sẽ được gán cho mỗi vùng để mô tả vị trí tương  
đối của vùng đó so với cửa sổ. Bằng cách đánh số từ 1 đến 4 theo thứ tự từ phải qua trái,  
các bit của mã vùng được dùng theo quy ước sau để chỉ một trong bốn vị trí tương đối  
của vùng so với cửa sổ bao gồm : trái, phải, trên, dưới.  
Bit 1 : trái (LEFT)  
Bit 2 : phải (RIGHT)  
Bit 3 : trên (TOP)  
Bit 4 : dưới (BOTTOM)  
Giá trị 1 tương ứng với vị trí bit nào trong mã vùng sẽ chỉ ra rằng điểm đó ở vị trí tương  
ứng, ngược lại bit đó sẽ được đặt bằng 0. Ví dụ một vùng có mã là 1001, thì nó sẽ nằm  
phía dưới (bit 4 bằng 1), bên trái (bit 1 bằng 1) so với cửa sổ, vùng có mã là 0000 chính  
là cửa sổ.  
Hình 4.7 – Mã vùng quy định vị trí tương đối của vùng so với cửa sổ  
Các giá trị bit trong mã vùng được tính bằng cách xác định tọa độ của điểm  
x, y thuộc  
vùng đó với các biên của cửa sổ. Bit 1 được đặt là 1 nếu x xmin , các bit khác được tính  
tương tự.  
Thuật toán  
Gán mã vùng tương ứng cho các điểm đầu cuối P , P2 của đoạn thẳng cần xén lần lượt là c1 , c2 . Ta  
1
có nhận xét :  
•
•
Các đoạn thẳng nằm hoàn toàn bên trong cửa sổ sẽ có c1 c2 0000 , ứng với các  
đoạn này, kết quả sau khi xén là chính nó.  
Nếu tồn tại k   
1,..,4 , sao cho với bit thứ k của c1 , c2 đều có giá trị 1, lúc này đoạn  
thẳng sẽ nằm về cùng phía ứng với bit k so với cửa sổ, do đó nằm hoàn toàn ngoài cửa sổ.  
Đoạn này sẽ bị loại bỏ sau khi xén. Ví dụ, nếu c1 1001, c2 0101, rõ ràng bit 1 của  
chúng đều bằng 1 (ứng với biên trái), do đó đoạn thẳng nằm hoàn toàn về biên trái của  
cửa sổ. Để xác định tính chất này, đơn giản chỉ cần thực hiện phép toán logic AND trên  
c1 , c2 . Nếu kết quả khác 0000, đoạn thẳng sẽ nằm hoàn toàn ngoài cửa sổ.  
•
Nếu c1 , c2 không thuộc về hai trường hợp trên, đoạn thẳng có thể hoặc không cắt ngang  
cửa sổ (ví dụ đoạn P5 P6 , P7 P8 trong hình 4.6) chắc chắn sẽ tồn tại một điểm nằm ngoài  
cửa sổ, không mất tính tổng quát giả sử điểm đó là  
P1 . Bằng cách xét mã vùng của P là  
1
c1 ta có thể xác định được các biên mà đoạn thẳng có thể cắt để từ đó chọn một biên và  
tiến hành tìm giao điểm P 'của đoạn thẳng với biên đó. Lúc này, đoạn thẳng ban đầu  
1
được xén thành P P ' . Tới đây chúng ta lại lặp lại thao tác đã xét cho đoạn thẳng mới  
1
1
P P ' cho tới khi xác định được phần nằm trong hoặc loại bỏ toàn bộ đoạn thẳng.  
1
1
Chúng ta minh họa thuật toán bằng hình vẽ 4.8. Với đoạn thẳng P P2 , ta sẽ kiểm tra  
P lần lượt với  
1
1
các biên trái, phải, dưới, trên và tìm ra điểm này nằm dưới cửa sổ, sau đó chúng ta tìm giao điểm P ' của  
1
đoạn thẳng với biên dưới. Lúc này đoạn thẳng ban đầu được xén ngắn lại thành P ' P2 . Vì  
P2 nằm ngoài  
1
cửa sổ nên bằng cách xét tương tự, chúng ta sẽ tiến hành tìm giao điểm P2 ' của P ' P2 với biên trên và lúc  
1
này đoạn P ' P2 ' , chính là phần nằm hoàn toàn trong cửa sổ.  
1
Trong trường hợp đoạn P3 P4  
, P3 nằm bên trái cửa sổ nên chúng ta có thể xác định điểm giao P3 ' ,  
và từ đó loại bỏ đoạn thẳng P3 P3 '. Bằng cách kiểm tra mã vùng, chúng ta dễ dàng xác định được đoạn  
thẳng P3 ' P4 nằm hoàn toàn bên dưới cửa sổ nên có thể bỏ đi toàn bộ.  
Hình 4.8 – Minh họa thuật toán Cohen - Sutherland  
Các điểm giao với các biên cửa sổ của đoạn thẳng có thể được tính từ phương trình tham số như đã đề  
cập ở phần trên. Tung độ y của điểm giao đoạn thẳng với biên đứng của cửa sổ có thể tính từ công thức  
y y1 m  
với biên ngang của cửa sổ có thể tính từ công thức : x x1   
ymax  
x x1  
, trong đó x có thể là xmin hay xmax . Tương tự, hoành độ x của điểm giao đoạn thẳng  
y y1 / m , trong đó y có thể là ymin hay  
.
Lưu đồ thuật toán Cohen-Sutherland dùng để xén một đoạn thẳng qua hai điểm (x1,y1) và (x2,y2) vào cửa  
sổ hình chữ nhật cho trước  
Cài đặt minh họa thuật toán Cohen - Sutherland  
#define TRUE  
#define FALSE  
#define LEFT  
#define RIGHT  
#define TOP  
#define BOTTOM  
typedef struct {  
int x, y;  
1
0
1
2
4
8
}POINT;  
typedef struct {  
int Left, Top, Right, Bottom;  
}RECT;  
typedef int CODE;  
#define Accept(a,b)  
#define Reject(a,b)  
(!(a|b))  
(a&b)  
// Tra ve ma vung cua p la c  
void EnCode(POINT p, CODE &c, RECT rWin)  
{
c = 0;  
if(p.x < rWin.Left)  
c |= LEFT;  
if(p.x > rWin.Right)  
c |= RIGHT;  
if(p.y > rWin.Top)  
c |= TOP;  
if(p.y < rWin.Bottom)  
c |= BOTTOM;  
}
// Hoan vi hai diem p1 va p2 sao cho p1 luon nam ngoai cua so  
void SwapPoint(POINT& p1, POINT &p2, CODE &c1, CODE &c2)  
{
if(!c1) // Neu p1 nam hoan toan trong cua so  
{
POINT p;  
p = p1;  
p1 = p2;  
p2 = p;  
CODE c;  
c = c1;  
c1 = c2;  
c2 = c;  
}
}
// Tra ve TRUE neu co cat cua so. Nguoc lai tra ve FALSE  
int CohenSutherlandClipping(POINT P1, POINT P2, POINT &Q1, POINT &Q2, RECT rWin)  
{
int fStop = FALSE, fResult = FALSE;  
CODE c1, c2;  
while(!fStop)  
{
EnCode(P1, c1, rWin);  
EnCode(P2, c2, rWin);  
// Neu duong thang nam hoan toan ben trong cua so  
if(Accept(c1, c2))  
{
fStop  
fResult = TRUE;  
} // Accept  
= TRUE; // break  
else  
{
// Neu duong thang nam hoan toan ben ngoai cua so  
if(Reject(c1,c2))  
{
fStop = TRUE; // break  
} // Reject  
else // Xet truong hop duong thang co the cat cua so  
{
SwapPoint(P1, P2, c1, c2);  
float m;  
if(P2.x!=P1.x)  
m = float(P2.y-P1.y)/(P2.x-P1.x);  
if(c1 & LEFT)  
{
P1.y += (rWin.Left-P1.x)*m;  
P1.x = rWin.Left;  
} // Left  
else  
{
if(c1 & RIGHT)  
{
P1.y += (rWin.Right-P1.x)*m;  
P1.x = rWin.Right;  
} // Right  
else  
{
if(c1 & TOP)  
{
if(P2.x!=P1.x)  
P1.x += (rWin.Top - P1.y)/m;  
P1.y = rWin.Top;  
} // Top  
else // Bottom  
{
if(P2.x!=P1.x)  
P1.x  
+= (rWin.Bottom - P1.y)/m;  
P1.y = rWin.Bottom;  
} // Bottom  
}
}
} // Xet truong hop duong thang co the cat cua so  
}
} //while  
Q1 = P1;  
Q2 = P2;  
return (fResult);  
} //CohenSutherlandClipping  
2.2. Thuật toán Liang-Barsky  
Thuật toán Liang-Barsky được phát triển dựa vào việc phân tích dạng tham số của  
phương trình đoạn thẳng.  
x x1 t  
y y1 t  
x2 x1  
x1 tDx, Dx x2 x1  
y1 tDy, Dy y2 y1 ,  
y2 y1  
0 t 1  
Ứng với mỗi giá trị t, ta sẽ có một điểm P tương ứng thuộc đường thẳng.  
•
•
•
Các điểm ứng với t 1 sẽ thuộc về tia P2x.  
Các điểm ứng với t 0 sẽ thuộc về tia P2x’.  
Các điểm ứng với 0 t 1 sẽ thuộc về đoạn thẳng P P2  
.
1
x
P2(x2, y2)  
t>1  
t=1  
P1(x1, y1)  
t=0  
t<0  
x'  
Hình 4.9 – Phương trình tham số của đoạn thẳng  
Tập hợp các điểm thuộc về phần giao của đoạn thẳng và cửa sổ ứng với các giá trị t thỏa  
hệ bất phương trình :  
x
y
x1 tDx xmax  
y1 tDy ymax  
min  
min  
0 t 1  
p1  Dx, q1 x1 xmin  
p2 Dx, q2 xmax x1  
p3  Dy, q3 y1 ymin  
p4 Dy, q4 ymax y1  
Đặt  
Lúc này ta viết hệ phương trình trên dưới dạng :  
p t q , k   
0 t 1  
1,2,3,4  
k
k
Như vậy việc tìm đoạn giao thực chất là tìm nghiệm của hệ bất phương trình này. Có hai  
khả năng xảy ra đó là :  
•
Hệ bất phương trình vô nghiệm, nghĩa là đường thẳng không có phần giao với cửa sổ nên  
sẽ bị loại bỏ.  
•
Hệ bất phương trình có nghiệm, lúc này tập nghiệm sẽ là các giá trị t thỏa  
t   
t1 , t2  
0,1 .  
Ta xét các trường hợp :  
•
Nếu k   
vô nghiệm, do đó hệ vô nghiệm.  
Nếu k 1,2,3,4 : (pk 0) (qk 0) thì với các bất phương trình mà ứng với pk =  
1,2,3,4 : (pk 0) (qk 0) thì rõ ràng bất phương trình ứng với k trên là  
•
0 là các bất phương trình hiển nhiên, lúc này hệ bất phương trình cần giải tương đương  
với hệ bất phương trình có pk 0.  
•
•
Với các bất phương trình pk t qk mà pk 0 , ta có t qk / pk  
Với các bất phương trình pk t qk mà pk 0 , ta có t qk / pk  
t1 , t2  
.
.
Vậy nghiệm của hệ bất phương trình là  
với :  
qk  
pk  
t max(  
, p 0  
0 )  
1
k
qk  
pk  
t min(  
, p 0   
1 )  
2
k
t1 t2  
Nếu hệ trên có nghiệm thì đoạn giao Q1Q2 sẽ là  
Q1 (x1 t1 Dx, y1 t1 Dy),Q2 (x1 t2 Dx, y1 t2 Dy)  
.
Nếu xét thuật toán này ở khía cạnh hình học ta có :  
•
Trường hợp k   
1,2,3,4 : (pk 0) (qk 0) tương ứng với trường hợp đoạn thẳng  
cần xét song song với một trong các biên của cửa sổ ( pk 0 ) và nằm ngoài cửa sổ (  
qk 0 ) nên sẽ bị loại bỏ sau khi xén.  
•
Với pk 0 , giá trị t rk qk / pk sẽ tương ứng với giao điểm của đoạn thẳng với  
biên k kéo dài của cửa sổ. Trường hợp pk 0 , kéo dài các biên cửa sổ và đoạn thẳng về  
vô cực, ta có đường thẳng đang xét sẽ có hướng đi từ bên ngoài vào bên trong cửa sổ.  
Nếu pk 0 , đường thẳng sẽ có hướng đi từ bên trong cửa sổ đi ra. Do đó hai đầu mút  
của đoạn giao sẽ ứng với các giá trị t1 , t2 được tính như sau : Giá trị t1 chính là giá trị  
lớn nhất của các rk qk / pk mà pk 0 (đường thẳng đi từ ngoài vào trong cửa sổ) và  
0; giá trị t2 chính là giá trị nhỏ nhất của các rk qk / pk mà pk 0 (đường thẳng đi  
từ trong cửa sổ đi ra) và 1.  
Hình 4.10 – Xét với biên trái đoạn thẳng P1P2 có hướng đi từ ngoài vào trong, nhưng so với biên phải đoạn thẳng P’1P’2 lại có hướng  
đi từ trong cửa sổ đi ra  
Khi cài đặt thuật toán Liang-Barsky, ban đầu các giá trị t1, t2 được khởi động t1 0, t2 1. Với mỗi  
lần xén đoạn thẳng với một biên của cửa sổ, các giá trị p, q sẽ được truyền cho hàm ClipTest để xác định  
đoạn thẳng có bị loại bỏ hay bị xén bớt một đoạn hay không. Khi p 0, tham số r q / p sẽ được xem  
xét để cập nhật t1 , khi p 0 , r dùng để cập nhật t2 . Khi cập nhật t1 và t2 nếu t1 t2 , đoạn thẳng sẽ bị  
loại bỏ. Ngoài ra nếu (p=0 và q<0), chúng ta cũng sẽ loại bỏ đoạn thẳng vì nó song song và nằm ngoài cửa  
sổ. Nếu đoạn thẳng không bị loại bỏ sau bốn lần gọi với các tham số p, q tương ứng với các biên của cửa  
sổ, các giá trị t1 và t2 sẽ được dùng để suy ra tọa độ hai điểm đầu mút của đoạn giao.  
Cài đặt minh họa thuật toán Liang - Barsky  
// Tra ve TRUE neu khong xay ra truong hop nam ngoai cua so  
int ClipTest(int p, int q, float &t1, float &t2)  
{
float r;  
if (p<0)  
{
r = float(q)/p;  
if (r>t2)  
return FALSE;  
else  
if (r>t1)  
t1 = r;  
}
else  
{
if (p>0)  
{
r = float(q)/p;  
if (r<t1)  
return FALSE;  
else  
if (r<t2)  
t2 = r;  
}
else // p=0  
{
if (q<0)  
return FALSE;  
}
}
return TRUE;  
}
int LiangBarskyClipping(POINT P1, POINT P2, RECT R, POINT *Q1, POINT *Q2)  
{
float t1, t2;  
int Dx, Dy, x1, y1, x2, y2, xmin, ymin, xmax, ymax;  
t1 = 0;  
t2 = 1;  
x1 = P1.x; y1 = P1.y;  
x2 = P2.x; y2 = P2.y;  
Dx = x2 - x1; Dy = y2 - y1;  
xmin = R.Left; ymin = R.Top;  
xmax = R.Right; ymax = R.Bottom;  
if (ClipTest(-Dx, x1 - xmin, t1, t2)) // Giai he bat phuong trinh 1  
{
if (ClipTest(Dx, xmax - x1, 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ị t1 , t2 , 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ị t1 , t2 . 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 Vi ,Vi1 là hai đỉnh  
kề cạnh ViVi1 , 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 Vi nằm ngoài, Vi1 nằm trong, ta lưu giao điểm I của ViVi1 với biên của cửa  
sổ và Vi1  
.
•
•
•
(ii) Nếu cả  
Vi , Vi1 đều nằm trong, ta sẽ lưu cả Vi , Vi1 .  
(iii) Nếu Vi nằm trong, Vi1 nằm ngoài, ta sẽ lưu Vi và I.  
(iv) Nếu cả  
Vi , Vi1 đều nằm ngoài, ta không lưu gì cả.  
Vi  
I
Vi+1  
Vi  
Vi+1  
Vi  
Vi+1  
I
Vi+1  
Vi  
(i)  
(ii)  
(iii)  
(iv)  
Hình 4.13 – Các trường hợp khi xét Vi ,Vi1 với các biên của cửa sổ  
Cài đặt minh họa thuật toán Sutherland-Hodgeman  
#include <graphics.h>  
#include <mem.h>  
#include <conio.h>  
#include <stdio.h>  
#include <stdlib.h>  
#define TRUE  
#define FALSE  
#define LEFT  
#define RIGHT  
#define TOP  
1
0
1
2
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;  
} //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ị rk qk / pk . 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.  
doc 16 trang Thùy Anh 27/04/2022 7780
Download
Bạn đang xem tài liệu "Giáo trình Đồ họa máy tính - Chương 4, Phần 2: Hiển thị đối tượng hai chiều", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • docgiao_trinh_do_hoa_may_tinh_chuong_4_phan_2_hien_thi_doi_tuon.doc
  • htmChuong4.htm