Bài tập xén hình giải thuật cohen sutherland năm 2024
|
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à . 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ổ. thì giao điểm đó sẽ không thuộc về 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 :
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 8typedef 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 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 = 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(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 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. 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à :
Ta xét các trường hợp : 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ó : 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 . 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>t2) return FALSE; else if (r>t1) t1= r; } else { if (p>0) { r =float(q)/p; if (r return FALSE; else if (r t2= 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 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ị , 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
include
include
include
include
define TRUE 1
define FALSE 0
define LEFT 1
define RIGHT 2
define TOP 4
define BOTTOM 8typedef 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; pPrev = pIn[0]; if(Inside(pPrev, Edge, rWin))// Save point { pOut[Cnt]= pPrev; Cnt++; FlagPrevPt = TRUE; } for(int i=1; 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 voidClipPolygon(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. |
