淺析梁友棟—Barsky直線段裁剪算法的講授方法

1.授課方法介紹

在教學(xué)方法上，講授梁友棟-Barky算法時(shí)應(yīng)注意順序性和啟發(fā)性，首先采取先粗略介紹算法的思想，然后通過采用發(fā)現(xiàn)問題、解決問題的方法，逐步完善算法中的各個(gè)細(xì)節(jié)，再者講授過程中還應(yīng)充分利用圖形圖示的作用，這樣會(huì)使復(fù)雜的算法變得易于理解，易于學(xué)生的接受。

2.講授過程

存在矩形裁剪窗口和直線段P0P1，直線段及其延長(zhǎng)線和窗口交于兩點(diǎn)Q0、Q1，如圖（一）

所示，求其裁剪后的線段Q0P1

圖（一）

提出問題（1）：窗口是一個(gè)二維對(duì)象，直線是一個(gè)一維對(duì)象，兩個(gè)對(duì)象的維度不同，能不能把二維窗口轉(zhuǎn)化為一維對(duì)象來解決裁剪問題？

引導(dǎo)學(xué)生回答問題：刷新式光柵掃描顯示器的屏幕是通過像素來表現(xiàn)的，屏幕上的對(duì)象都可以看成像素點(diǎn)的集合。如果把窗口和直線段分別看成一個(gè)像素點(diǎn)集的話，其交集即為像素點(diǎn)組成的裁剪結(jié)果Q0P1，即為所求。

首先把二維窗口轉(zhuǎn)化為一維對(duì)象：設(shè)直線段所在的直線與窗口交與兩點(diǎn)Q0、Q1，Q0Q1稱為誘導(dǎo)窗口，它是一維的。直線段P0P1，與誘導(dǎo)窗口Q0Q1的交集與所求的裁剪結(jié)果是一致的。

其次討論如何進(jìn)行一維裁剪的問題：以P0為數(shù)軸原點(diǎn)，建立一維數(shù)軸，令P0，P1分別對(duì)應(yīng)參數(shù)0、1，得到直線參數(shù)表達(dá)式

x（t）=x0+（x1-x0）t

y（t）=y0+（y1-y0）t 0≤t≤1

令Q0，Q1對(duì)應(yīng)參數(shù)t0、t1，設(shè)t0≤t1，P0P1與Q0Q1的關(guān)系有以下四種：

圖（二）

如圖所示可以看出，P0P1至少部分可見的充分必要條件是：max（0，t0）≤min（1，t1），且可見部分VW的參數(shù)區(qū)間為[max（0，t0），min（1，t1）]，即區(qū)間[0，1]與區(qū)間[t0，t1]取交集。

提出問題（2）：如何求得誘導(dǎo)窗口Q0Q1所對(duì)應(yīng)的參數(shù)t0，t1 ？

圖（三）

引導(dǎo)學(xué)生回答問題：還是利用集合的觀點(diǎn)，如圖（三）所示直線與裁剪窗口分別交與L、B、R、T，如果把裁剪窗口左右邊所在直線夾成的帶裝區(qū)域△1和裁剪窗口上下邊所在直線夾成的帶裝區(qū)域△2看成像素點(diǎn)集的話，直線與△1的交集為線段LR，直線與△2的交集為線段BT，線段LR和線段BT的交集即為誘導(dǎo)窗口Q0Q1，用公式表示為

其中為直線段所在的直線，利用直線參數(shù)表達(dá)式及裁剪窗口四條邊的坐標(biāo)，就很容易求出L、R、B、T所分別對(duì)應(yīng)的參數(shù)、、、

即 t0=max（，），t1= min（，）

Q0Q1=[max（，），min（，）]

又因?yàn)?VW=[max（0，t0），min（1，t1）]

所以 VW=[max（0， ，），min（1， ，）]

提出問題（3）：剛才只是考慮了一種情況，如果直線和窗口的相對(duì)位置關(guān)系變了，如圖（四）所示，那么剛才的結(jié)果是不是一樣正確呢？

圖（四）

顯然這個(gè)結(jié)果是錯(cuò)誤的，怎么解決這個(gè)問題呢？

令Δx= x1-x0 ， Δy= y1-y0 ，如果Δx>=0，x=xmin為始邊，x=xmax為終邊；Δx<0時(shí)x=xmax為始邊，x=xmin為終邊。同理，如果Δy>=0，y=ymin為始邊，y=ymax為終邊；Δy<0時(shí)y=ymax為始邊，y=ymin為終邊。與始邊求得的結(jié)果放在一起求其最大值，與終邊求得的結(jié)果放在一起求其最小值，則圖（四）的正確結(jié)論為

t0=max（，），t1= min（，）

即 VW=[ max（0，，），min（1， ，）]

此外，水平直線或垂直直線和裁剪窗口還有兩種特殊的裁剪狀態(tài)，比較簡(jiǎn)單，不另作敘述。

結(jié)束語

本文通過提出問題、解決問題，層層推進(jìn)的教學(xué)方式，激發(fā)了學(xué)生的學(xué)習(xí)興趣，讓學(xué)生主動(dòng)參與到教學(xué)中來，師生互動(dòng)良好。課堂實(shí)踐表明，此方法可行且有效，達(dá)到了良好的教學(xué)效果。

參考文獻(xiàn)

[1]孫家廣.計(jì)算機(jī)圖形學(xué)（新版）.北京：清華大學(xué)出版社，1995.

[2]唐澤圣.計(jì)算機(jī)圖形學(xué)基礎(chǔ).北京：清華大學(xué)出版社，2001.

[3]倪明田.計(jì)算機(jī)圖形學(xué).北京：北京大學(xué)出版社，2009.

[4]杜曉增.計(jì)算機(jī)圖形學(xué)基礎(chǔ).北京：機(jī)械工業(yè)出版社，2004.

[5]吳學(xué)毅.計(jì)算機(jī)圖形學(xué)原理與實(shí)踐.北京：印刷工業(yè)出版社，2008.

（作者單位：長(zhǎng)江大學(xué)計(jì)算機(jī)科學(xué)學(xué)院）