任洪海(大連交通大學(xué)軟件學(xué)院，遼寧大連116052)*

基于兩端點(diǎn)區(qū)域分布的線裁剪新算法

任洪海
(大連交通大學(xué)軟件學(xué)院，遼寧大連116052)*

在確定線段完全在窗口內(nèi)或某邊界外初始判斷后將兩端點(diǎn)的區(qū)域分布分成6種情況進(jìn)行處理.除可直接確定相交關(guān)系的情況外，一般過指定頂點(diǎn)在窗外作與對(duì)應(yīng)邊呈45度的輔助邊界進(jìn)一步排除完全在窗外的線段，再通過線段與指定邊界相交測(cè)試確定線段與窗口的位置關(guān)系.該方法可以加快線段與窗口的求交進(jìn)程，有效減少不必要的求交運(yùn)算和輔助操作，顯著提高裁剪效率.

計(jì)算機(jī)應(yīng)用;線裁剪;兩端點(diǎn)區(qū)域分布

0 引言

線裁剪作為計(jì)算機(jī)圖形學(xué)基礎(chǔ)理論的重要內(nèi)容之一，經(jīng)典的算法主要有以區(qū)域碼為代表的Cohen-Sutherland算法、中點(diǎn)分割算法、參數(shù)化的梁-Barsky算法以及Nicholl-Lee-Nicholl算法［1］.文獻(xiàn)［2］將線段兩端點(diǎn)獨(dú)立考慮，并將其區(qū)域分布分成邊域和角域兩種基本情況，并根據(jù)線段相交對(duì)應(yīng)邊界的情況確定線段與窗口的相交關(guān)系.近年來也有一些算法將原窗口擴(kuò)大并旋轉(zhuǎn)45°形成新窗口用來舍棄不與窗口相交的線段［3-4］，但存在冗余邊界測(cè)試.

本文通過線段完全在窗口之內(nèi)或某邊界之外的初始判斷后，將線段兩端點(diǎn)相對(duì)于窗口邊界所劃分區(qū)域的分布分成5種情況進(jìn)行處理.在必要情況下過指定窗口頂點(diǎn)作輔助邊界排除不與窗口相交的線段，再根據(jù)線段相交于指定邊界的范圍快速確定線段與窗口的相交情況.減少不必要的輔助操作和求交運(yùn)算，顯著提高裁剪效率.

1 區(qū)域?qū)?yīng)關(guān)系及輔助邊界

1.1窗口邊界劃分區(qū)域及對(duì)應(yīng)關(guān)系

如圖1所示，作為矩形裁剪窗口的四條邊分別標(biāo)記為L(zhǎng)邊、R邊、B邊、T邊.將每條邊延長(zhǎng)成直線形成對(duì)應(yīng)邊界，分別為L(zhǎng)邊界( x = xwmin)、R邊界( x = xwmax)、B邊界( y = ywmin)、T邊界( y = ywmax).四條邊界將平面分成九個(gè)區(qū)域，根據(jù)區(qū)域位置及符號(hào)標(biāo)識(shí)，區(qū)域?qū)?yīng)關(guān)系如下:

邊區(qū)與一條邊界相對(duì)應(yīng);而角區(qū)和兩條垂直相交的邊界相對(duì)應(yīng).例如，T邊區(qū)與T邊界相對(duì)應(yīng); LB角區(qū)與L邊界、B邊界相對(duì)應(yīng).窗口頂點(diǎn)是由兩條邊界垂直相交而成，一條邊界可稱另一邊界對(duì)應(yīng)頂點(diǎn)相關(guān)邊界.例如，L邊界與B邊界相交而成頂點(diǎn)VLB，L邊界稱B邊界為頂點(diǎn)VLB相關(guān)邊界.根據(jù)邊界所屬，一角區(qū)與一頂點(diǎn)相對(duì)應(yīng)，兩斜對(duì)邊區(qū)與一頂點(diǎn)相對(duì)應(yīng).例如，LB角區(qū)對(duì)應(yīng)頂點(diǎn)VLB，R邊區(qū)與T邊區(qū)對(duì)應(yīng)頂點(diǎn)VRT.

圖1 裁剪窗口邊界區(qū)域劃分

對(duì)應(yīng)邊界相平行的兩邊區(qū)稱為對(duì)邊區(qū).例如，T邊區(qū)和B邊區(qū)為對(duì)邊區(qū)，L邊區(qū)和R邊區(qū)為對(duì)邊區(qū).對(duì)應(yīng)邊界相垂直的兩邊區(qū)稱為斜邊區(qū).例如，T邊區(qū)是L邊區(qū)的斜邊區(qū)，T邊區(qū)是R邊區(qū)的斜邊區(qū).

不同時(shí)在任何邊界之外的角區(qū)和邊區(qū)稱為斜對(duì)關(guān)系，每個(gè)邊區(qū)都有兩個(gè)斜對(duì)角區(qū).例如，T邊區(qū)有兩個(gè)斜對(duì)角區(qū)，即LB角區(qū)和RB角區(qū).

不同時(shí)在任何邊界之外的兩角區(qū)為對(duì)角區(qū).四個(gè)角區(qū)中，LT角區(qū)和RB角區(qū)為對(duì)角區(qū)，RT角區(qū)和LB角區(qū)為對(duì)角區(qū).

1.2輔助邊界

在窗口外分別過指定頂點(diǎn)引與對(duì)應(yīng)邊界成45°的直線，定義為輔助邊界.判斷線段端點(diǎn)在此類輔助邊界之外的條件為:

端點(diǎn)在過頂點(diǎn)VLT所引輔助邊界之外的條件為: y－x + xwmin＞ywmax

端點(diǎn)在過頂點(diǎn)VLB所引輔助邊界之外的條件為: x + y－ywmin＜xwmin

端點(diǎn)在過頂點(diǎn)VRB所引輔助邊界之外的條件為: y－x + xwmax＜ywmin

端點(diǎn)在過頂點(diǎn)VRT所引輔助邊界之外的條件為: x + y－ywmax＞xwmin

如果線段兩端點(diǎn)同時(shí)在過任意一條此類邊界之外，則線段在窗口之外，裁剪掉該線段.

本文根據(jù)線段兩端點(diǎn)的區(qū)域分布完全可確定過哪個(gè)頂點(diǎn)作輔助邊界進(jìn)行測(cè)試，而不必同時(shí)檢測(cè)四個(gè)輔助邊界.

2 算法實(shí)現(xiàn)過程

通過線段兩端點(diǎn)坐標(biāo)與窗口四條邊界坐標(biāo)相比較確定兩端點(diǎn)所在區(qū)域，并進(jìn)行如下初始判斷:

如果兩端點(diǎn)都在四條邊界之內(nèi)，則線段在窗口之內(nèi)，保留該線段;

如果兩端點(diǎn)都在四條邊界中任意一條的外側(cè)，則線段在窗口之外，裁剪該線段.

通過兩步初始判斷后，所剩線段兩端點(diǎn)的區(qū)域分布情況完全可概括成6類情況:①一端點(diǎn)在窗口內(nèi)另一端點(diǎn)在邊區(qū);②一端點(diǎn)在窗口內(nèi)另一端點(diǎn)在角區(qū);③一端點(diǎn)在邊區(qū)另一端點(diǎn)在其對(duì)邊區(qū);④一端點(diǎn)在邊區(qū)另一端點(diǎn)在其斜對(duì)邊區(qū);⑤一端點(diǎn)在邊區(qū)另一端點(diǎn)在其斜對(duì)角區(qū);⑥一端點(diǎn)在角區(qū)另一端點(diǎn)在其對(duì)角區(qū).

針對(duì)6種情況，分別具體處理如下:

對(duì)于情況①:可得線段只與邊區(qū)對(duì)應(yīng)邊相交，窗口內(nèi)端點(diǎn)到交點(diǎn)間線段為裁剪結(jié)果(如圖2中線段a).

對(duì)于情況②:可得線段一定與兩角區(qū)對(duì)應(yīng)邊之一相交(如圖3中線段a和線段b).求線段與任一對(duì)應(yīng)邊界的交點(diǎn)，判斷是否在其對(duì)應(yīng)窗口邊上:

如果交點(diǎn)在其對(duì)應(yīng)窗口邊上，則內(nèi)端點(diǎn)到交點(diǎn)間線段為裁剪結(jié)果.

否則，線段一定與另一對(duì)應(yīng)窗口邊相交.求其交點(diǎn)，內(nèi)端點(diǎn)到交點(diǎn)間線段為裁剪結(jié)果.

圖2 窗口內(nèi)-邊區(qū)情況

圖3 窗口內(nèi)-角區(qū)情況

對(duì)于情況③:可得線段分別與兩對(duì)應(yīng)邊相交，交點(diǎn)間線段為裁剪結(jié)果(如圖4中線段a ).

對(duì)于情況④:可得線段或不與窗口相交或同時(shí)與兩邊區(qū)的對(duì)應(yīng)邊相交.過兩邊區(qū)對(duì)應(yīng)邊界相交而成的頂點(diǎn)作輔助邊界，排除兩端點(diǎn)都在此輔助邊界之外的線段(如圖5中線段a ) ;對(duì)于輔助邊界無(wú)法排除的線段，指定兩邊區(qū)對(duì)應(yīng)邊界任意一個(gè)，判斷線段是否相交在對(duì)應(yīng)邊上:

如果交點(diǎn)在對(duì)應(yīng)邊上，則線段一定與另一邊也相交.求在另一邊上的交點(diǎn)，交點(diǎn)間線段為裁剪結(jié)果(如圖5中線段c和線段d ).

否則，線段不與窗口相交(如圖5中線段b ).

圖4 邊區(qū)-對(duì)邊區(qū)情況

圖5 邊區(qū)-斜邊區(qū)情況

對(duì)于情況⑤:線段與窗口的位置關(guān)系有三種:①線段不與窗口相交;②線段與邊區(qū)對(duì)應(yīng)邊及其垂直的角區(qū)對(duì)應(yīng)邊相交;③線段與邊區(qū)對(duì)應(yīng)邊及其平行的角區(qū)對(duì)應(yīng)邊相交.

角區(qū)的兩個(gè)對(duì)應(yīng)邊界中，一個(gè)與其斜對(duì)邊區(qū)對(duì)應(yīng)邊界平行，另一個(gè)與其斜對(duì)邊區(qū)對(duì)應(yīng)邊界垂直相交.取與斜對(duì)邊區(qū)對(duì)應(yīng)邊界垂直相交的角區(qū)對(duì)應(yīng)邊界為指定邊界，過邊區(qū)對(duì)應(yīng)邊界與指定邊界相交而成的頂點(diǎn)作輔助邊界，排除兩端點(diǎn)都在此輔助邊界之外的線段后，判斷線段與指定邊界的相交范圍完全可確定線段與窗口相交關(guān)系.如圖6所示.

( 1)如果線段相交指定邊界于邊區(qū)對(duì)應(yīng)邊界之外，則線段不與窗口相交;

( 2)如果線段相交指定邊界于對(duì)應(yīng)窗口邊上，則線段同時(shí)與邊區(qū)對(duì)應(yīng)邊相交，兩交點(diǎn)間線段為裁剪結(jié)果;

( 3)否則，線段與邊區(qū)對(duì)應(yīng)邊及其對(duì)邊相交，兩交點(diǎn)間線段為裁剪結(jié)果.

圖6 邊區(qū)-斜對(duì)角區(qū)情況

圖7 角區(qū)-對(duì)角區(qū)情況

對(duì)于情況⑥:此時(shí)，線段一定不同時(shí)與端點(diǎn)所在角區(qū)兩對(duì)應(yīng)邊相交.因此，線段與窗口的位置關(guān)系有五種:①線段不與窗口相交;②相交于窗口兩垂直方向?qū)?③相交于窗口兩水平方向?qū)?④一個(gè)非端點(diǎn)所在角區(qū)兩對(duì)應(yīng)邊;⑤另一個(gè)非端點(diǎn)所在角區(qū)兩對(duì)應(yīng)邊.如圖7所示.

便于描述，將端點(diǎn)所在角區(qū)對(duì)應(yīng)頂點(diǎn)稱為本頂點(diǎn)，而非端點(diǎn)所在角區(qū)對(duì)應(yīng)頂點(diǎn)稱為基頂點(diǎn).過兩基頂點(diǎn)分別作輔助邊界，排除兩端點(diǎn)同時(shí)在任意輔助邊界之外的線段后.取任意兩平行邊界為兩指定邊界，通過判斷線段與兩指定邊界的相交情況可確定線段與窗口的相交關(guān)系:

( 1)如果線段相交指定邊界于其基頂點(diǎn)相關(guān)邊界之外，則線段不與窗口相交;

( 2)如果線段相交指定邊界對(duì)應(yīng)邊上且相交另一平行邊界于其本頂點(diǎn)相關(guān)邊界之外，則線段與指定邊界對(duì)應(yīng)邊及其基頂點(diǎn)相關(guān)邊界對(duì)應(yīng)邊相交，交點(diǎn)間線段為裁剪結(jié)果;

( 3)如果線段相交兩指定邊界對(duì)應(yīng)邊上，兩對(duì)應(yīng)邊上交點(diǎn)間線段為裁剪結(jié)果;

( 4)如果線段同時(shí)相交兩指定邊界于本頂點(diǎn)相關(guān)邊界之外，線段同時(shí)與兩非指定邊界對(duì)應(yīng)邊相交，交點(diǎn)間線段為裁剪結(jié)果.

3 算法分析與比較

本文根據(jù)端點(diǎn)的區(qū)域分布通過指定頂點(diǎn)在窗口之外作與對(duì)應(yīng)邊呈45°的輔助邊界進(jìn)一步排除不與窗口相交的線段，避免文獻(xiàn)［4］中應(yīng)用45°旋轉(zhuǎn)窗口對(duì)應(yīng)四條新邊界測(cè)試過程中不必要的邊界判斷.

通過線段與邊界的相交情況確定線段與窗口的相交關(guān)系是裁剪判斷的有效途徑.本文算法將線段兩端點(diǎn)區(qū)域分布分成6種可能情況:情況①和情況③直接可確定線段與窗口的相交邊，情況②、情況④和情況⑤通過判斷線段相交一條指定邊界范圍可完全確定相交情況，情況⑥通過線段相交兩條平行邊界范圍可完全確定相交情況，同時(shí)每個(gè)相交邊界測(cè)試過程中都可以排除對(duì)應(yīng)情況下不與窗口相交的線段.

同Cohe-Sutherland算法與文獻(xiàn)［2］相比，本文算法能夠根據(jù)線段兩端點(diǎn)區(qū)域分布情況確定最佳相交檢測(cè)邊界，從而減少不必要的求交運(yùn)算.例如排除圖6中線段b，Cohen-Sutherland算法邊界裁剪如果按照固定的左、右、下、上順序需要左、右兩邊界裁剪后在下邊界判斷中才能將其排除.而文獻(xiàn)［2］由于單獨(dú)考慮兩端點(diǎn)區(qū)域分布情況分別進(jìn)行裁剪判斷，同樣增加了多余判斷與邊界求交.而本文算法在該邊區(qū)-斜對(duì)角區(qū)端點(diǎn)分布情況中確定下邊界為指定邊界，通過判斷線段與下邊界一次相交情況就可排除線段b.

在同等硬件條件下，應(yīng)用C ++編程實(shí)現(xiàn)CS算法、ELC算法［2］及本文算法，三個(gè)裁剪算法裁剪400萬(wàn)條隨機(jī)線段所需的時(shí)間分別為3.529，3.274和2.418 s，從所用時(shí)間可以看出新算法的裁剪效率都高于現(xiàn)有的兩個(gè)典型算法.

4 結(jié)論

本文在初始測(cè)試后將線段兩端點(diǎn)區(qū)域分布分成5種情況分別進(jìn)行判斷并完成裁剪過程，只有在必要的情況，才通過指定頂點(diǎn)在窗口之外作與對(duì)應(yīng)邊呈45°的輔助邊界進(jìn)一步排除不與窗口相交的線段，并通過線段相交于指定邊界的范圍確定線段與窗口的相交關(guān)系.以最少的輔助操作和求交判斷確定線段與窗口的位置關(guān)系，明顯提高裁剪效率.

［1］DONALD HEARN，PAULINE BAKER M.Computer Graphics with OpenGL［M］.Third Edition，Upper Saddle River: Prentice Hall，2005: 315-340.

［2］汪灝泓，吳銳迅，蔡士杰.一種基于幾何變換的高效的線裁剪新算法［J］.軟件學(xué)報(bào)，1998，9( 10) : 728-733.

［3］陸國(guó)棟，吳煊暉.基于變窗口過濾技術(shù)的線段裁剪中點(diǎn)分割算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2002，14( 6) : 513-517.

［4］朱亞臣，譚建榮，陸國(guó)棟，等.基于連續(xù)分區(qū)與串聯(lián)編碼的線段裁剪新算法［J］.中國(guó)圖象圖形學(xué)報(bào)，2007，12( 4) : 732-739.

A New Line Clipping Algorithm based on Region Distribution of Two Endpoints

REN Honghai
( Software Institute，Dalian Jiaotong University，Dalian 116052，China)

The region distribution of two endpoints is divided into six kinds of cases for processing after the initial testing to determine whether a line segment is completely inside the clipping window or outside some window boundary.Except for the case that the intersection relation is determined directly，the line segments outside window is further eliminated through the 45°auxiliary boundary passing the specified vertex，and the position of a line segment in relation to window is determined by the intersection test between a line segment and the specified boundary.The new algorithm can quickly calculate the intersections between a line segment and window，avoid the unnecessary intersection calculation and auxiliary operation，and further improve the clipping efficiency.

computer applications; line clipping;region distribution of two endpoints

A

1673-9590( 2016) 01-0105-04

2015-04-07

任洪海( 1977－)，男，講師，碩士，主要從事計(jì)算機(jī)圖形學(xué)教學(xué)與研究

E-mail: honghai_ren@126.com.