Hiển thị đối tượng hai chiều

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ơinà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.

Hệ tọa độ quan sát và hệ tọa độ thiết bị chuẩn

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ổ.

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 thuộc vùng đó với các biên của cửa sổ. Bit 1 được đặt là 1 nếu , 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 của đoạn thẳng cần xén lần lượt là . Ta 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ó , ứ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 , sao cho với bit thứ k của đề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 , 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 . 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 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 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à . Bằng cách xét mã vùng của là 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 của đoạn thẳng với biên đó. Lúc này, đoạn thẳng ban đầu được xén thành . Tới đây chúng ta lại lặp lại thao tác đã xét cho đoạn thẳng mới 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.

Chúng ta minh họa thuật toán bằng hình vẽ 4.8. Với đoạn thẳng , ta sẽ kiểm tra lần lượt với 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 của đ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 . Vì nằm ngoài 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 của với biên trên và lúc này đoạn , chính là phần nằm hoàn toàn trong cửa sổ.

Trong trường hợp đoạn , nằm bên trái cửa sổ nên chúng ta có thể xác định điểm giao , và từ đó loại bỏ đoạn thẳng . Bằng cách kiểm tra mã vùng, chúng ta dễ dàng xác định được đoạn thẳng 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 , trong đó x có thể là hay . Tương tự, hoành độ x của điểm giao đoạn thẳng với biên ngang của cửa sổ có thể tính từ công thức : , trong đó y có thể là hay .

Lưu đồ thuật toán Cohen-Sutherland dùng để xén một đoạn thẳng qua hai điểm (x 1 ,y 1 ) và (x 2 ,y 2 ) 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 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;

typedef int CODE;

#define Accept(a,b)(!(a|b))

#define Reject(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

intCohenSutherlandClipping(POINT P₁, POINT P₂, POINT &Q₁, POINT &Q₂, RECT rWin)

{

int fStop = FALSE, fResult = FALSE;

CODE c1, c2;

while(!fStop)

{

EnCode(P₁, c1, rWin);

EnCode(P₂, c2, rWin);

// Neu duong thang nam hoan toan ben trong cua so

if(Accept(c1, c2))

{

fStop = TRUE;//break

fResult = TRUE;

}// Accept

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(P₁, P₂, c1, c2);

float m;

if(P₂.x!=P₁.x)

m =float(P₂.y-P₁.y)/(P₂.x-P₁.x);

if(c1 & LEFT)

{

P₁.y +=(rWin.Left-P₁.x)*m;

P₁.x = rWin.Left;

} // Left

else

{

if(c1 & RIGHT)

{

P₁.y += (rWin.Right-P₁.x)*m;

P₁.x = rWin.Right;

} // Right

else

{

if(c1 & TOP)

{

if(P₂.x!=P₁.x)

P₁.x +=(rWin.Top - P₁.y)/m;

P₁.y = rWin.Top;

} // Top

else// Bottom

{

if(P₂.x!=P₁.x)

P₁.x +=(rWin.Bottom - P₁.y)/m;

P₁.y = rWin.Bottom;

} // Bottom

}

}

} // Xet truong hop duong thang co the cat cua so

}

} //while

Q₁= P₁;

Q₂= P₂;

return(fResult);

} //CohenSutherlandClipping

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.

Ứ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 sẽ thuộc về tia P₂x.
• Các điểm ứng với sẽ thuộc về tia P₂x’.
• Các điểm ứng với sẽ thuộc về đoạn thẳng .

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 : 

Đặt

Lúc này ta viết hệ phương trình trên dưới dạng :

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 .

            Ta xét các trường hợp :

• Nếu thì rõ ràng bất phương trình ứng với k trên là vô nghiệm, do đó hệ vô nghiệm.
• Nếu thì với các bất phương trình mà ứng với pk = 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 mà , ta có .
• Với các bất phương trình mà , ta có .

            Vậy nghiệm của hệ bất phương trình là với :

                               

Nếu hệ trên có nghiệm thì đoạn giao sẽ là .

Nếu xét thuật toán này ở khía cạnh hình học ta có :

• Trường hợp 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ổ () và nằm ngoài cửa sổ () nên sẽ bị loại bỏ sau khi xén.
• Với , giá trị 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 , 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 , đườ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ị được tính như sau : Giá trị chính là giá trị lớn nhất của các mà (đường thẳng đi từ ngoài vào trong cửa sổ) và 0; giá trịchính là giá trị nhỏ nhất của các mà (đườ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 P₁P₂ có hướng đi từ ngoài vào trong, nhưng so với biên phải đoạn thẳng P’₁P’₂ 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ị t₁, t₂ được khởi động . 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ị 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 , tham số sẽ được xem xét để cập nhật , khi , r dùng để cập nhật . Khi cập nhật và nếu , đ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ị và 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 &t 1 , float &t 2 )

{

float r;

if (p<0)

{

r =float(q)/p;

if (r>t₂)

return FALSE;

else

if (r>t₁)

t₁= r;

}

else

{

if (p>0)

{

r =float(q)/p;

if (r<t₁)

return FALSE;

else

if (r<t₂)

t₂= r;

}

else // p=0

{

if (q<0)

return FALSE;

}

}

return TRUE;

}

int LiangBarskyClipping(POINT P 1 , POINT P 2 , RECT R, POINT *Q 1 , POINT *Q 2 )

{

float t₁, t₂;

int Dx, Dy, x₁, y₁, x₂, y₂, xmin, ymin, xmax, ymax;

t₁= 0;

t₂= 1;

x₁= P₁.x; y₁= P₁.y;

x₂= P₂.x; y₂= P₂.y;

Dx = x₂- x₁; Dy = y₂- y₁;

xmin = R.Left; ymin= R.Top;

xmax = R.Right; ymax= R.Bottom;

if (ClipTest(-Dx, x₁ - xmin, t₁, t₂))// Giai he bat phuong trinh 1

{

if (ClipTest(Dx, xmax - x₁, t₁, t₂))// Giai he bat phuong trinh 2

{

if (ClipTest(-Dy, y₁- ymin, t₁, t₂))// Giai he bat phuong trinh 3

{

if (ClipTest(Dy, ymax - y₁, t₁, t₂))// Giai he bat phuong trinh 4

{

Q₁.x = x₁+ t₁. Dx;

Q₁.y = y₁+ t₁. Dy;

Q₂.x = x₁+ t₂. Dx;

Q₂.y = y₁+ t₂. 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ị , 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ị. 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.

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 là hai đỉnh kề cạnh , 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 nằm ngoài, nằm trong, ta lưu giao điểm I của với biên của cửa sổ và .

(ii) Nếu cả , đều nằm trong, ta sẽ lưu cả , .

(iii) Nếu nằm trong, nằm ngoài, ta sẽ lưu và I.

(iv) Nếu cả , đề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 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 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

intInside(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.

voidClipEdge(POINT *pIn,int N, POINT *pOut,int&Cnt,int Edge,

RECT rWin)

{

int FlagPrevPt = FALSE;

Cnt = 0;

POINT pPrev;