基于計(jì)算機(jī)圖形學(xué)的多類型算法設(shè)計(jì)研究

摘要：本文通過結(jié)合基于計(jì)算機(jī)圖形學(xué)的多類型算法相關(guān)內(nèi)容進(jìn)行討論，并結(jié)合在計(jì)算機(jī)圖形學(xué)下的平面擴(kuò)展簡單多邊形面積計(jì)算以及高維空間中歐式距離計(jì)算，進(jìn)行多類型算法設(shè)計(jì)研究。

關(guān)鍵詞：計(jì)算機(jī)圖形學(xué)；算法；分析和探究

中圖分類號：TP391.4

1 計(jì)算機(jī)圖形學(xué)的基本算法介紹

在計(jì)算機(jī)圖形學(xué)的基本算法中，通常包括了裁剪算法、多邊形布爾運(yùn)算、復(fù)雜多邊形面積計(jì)算以及高維空間中點(diǎn)距離計(jì)算等幾種。其中，裁剪算法作為計(jì)算機(jī)圖形學(xué)中最為基本的內(nèi)容，是圖形合成的基礎(chǔ)及必要的操作，主要作用在于可以有選擇地對圖形數(shù)據(jù)進(jìn)行摘取。多邊形的布爾運(yùn)算通常被用于幾何以及實(shí)體造型等領(lǐng)域當(dāng)中，由于其可以用于計(jì)算交點(diǎn)，并避免了對其他幾何元素的計(jì)算，使得布爾運(yùn)算在幾何與實(shí)體造型等領(lǐng)域中具有較高的應(yīng)用價值。

2 基于計(jì)算機(jī)圖形學(xué)的平面擴(kuò)展簡單多邊形面積計(jì)算設(shè)計(jì)

在假定多邊形曲線邊為圓錐曲線邊或是三次Bezier曲線邊的基礎(chǔ)上，對原點(diǎn)到曲線邊端點(diǎn)直線段，以及其與曲線邊構(gòu)成的三角范圍進(jìn)行考察，在此過程中出現(xiàn)的不合理情形包括了以下四種，即從原點(diǎn)到圓錐曲線邊端點(diǎn)的直線段與邊相交、三次Bezier曲線邊有自交點(diǎn)、原點(diǎn)到Bezier曲線邊端點(diǎn)直線段與邊相交，以及連接Bezier曲線邊兩端點(diǎn)上的直線段與邊相交等情況。需要對曲線邊加以分割，行圓錐曲線邊求分割點(diǎn)與切點(diǎn)算法、三次Bezier曲線邊求可能的自交點(diǎn)算法、三次Bezier曲線邊求不同形式分割點(diǎn)與切點(diǎn)算法等。

2.1 圓錐曲線邊的分割算法

根據(jù)圓錐曲線方程f=a11x2+2a12xy+a22y2+2a1x+2a2y+a3。其中，V0=（x0，y0），V0與V1均為曲線兩端點(diǎn)，s為1（或-1），用于表示曲線段的走向選擇。若是從原點(diǎn)O到圓錐曲線邊端點(diǎn)V0的直線和曲線邊存在除V0之外的交點(diǎn)，則將其確定為分割點(diǎn)，并得到直線方程為：y=kx。綜合得出（a11+2a12k+a22k2）x2+2（a1+ka2）x+a3=0。根據(jù)偉大定理，推斷出方程的另一個根X1為：a3/[x0（a11+2a12k+a22k2）]。輸入a11、a12、a22、a1、a2、a3、V0、V1和s，根據(jù)A=a22-a3a22，B=2（a1a2-a12a3），C=a1-a11a3，求出AK2+BK+C=0的根k1、k2，再判斷是否有切點(diǎn)，若無根則說明沒有切點(diǎn)，否則進(jìn)行以下步驟：

Xq1=-（a1+k1a2）/（a11+2a12k1+a22k12）；yq1=k1*Xq1

Xq2=-（a1+k2a2）/（a11+2a12k2+a22k22）；yq2=k2*Xq2

若sign（V0Q1V1）=s，或是sign（V0Q2V1）=s，那么Q1或Q2為圓錐曲線邊的切點(diǎn)，否則說明交點(diǎn)在圓錐曲線段外部。

2.2 三次Bezier曲線的自交點(diǎn)

若是多邊形曲線邊均為三次Bezier曲線，此時可以借助曲線邊起點(diǎn)及終點(diǎn)P0和P3、以及P1和P2點(diǎn)來確定。將P0、P1、P2和P3各點(diǎn)的坐標(biāo)設(shè)定為（x0，y0），（x1，y1）（x2，y2）和（x3，y3），并將自交點(diǎn)先后兩次對應(yīng)的參數(shù)值設(shè)定為t1和t2，其中，t1、t2均在0到1之間，那么：

（1-t1）3x0+3（1-t1）2t1x1+3（1-t1）t12x2+t13x3=（1-t2）3x0+3（1-t2）2t2x1+3（1-t2）t22x2+t23x3（t1-t2）（（-3+3（t1+t2）-（t1+t2）2+t1t2）x0+3（1-2（t1+t2）+（t1+t2）2-t1t2）x1+3（（t1+t2）-（t1+t2）2+t1t2）x2+（（t1+t2）2-t1t2）x3）=0

2.3 三次Bezier曲線邊的分割

若是從原點(diǎn)向三次Bezier曲線邊某端點(diǎn)連接的直線段和曲線邊存在交點(diǎn)（分割點(diǎn)），那么，在對該直線段和曲線邊的交點(diǎn)進(jìn)行考查時，可以根據(jù)上述記號，表達(dá)為：

由P0點(diǎn)在公式y(tǒng)=kx上，可知P0=（x0，y0），由此可推斷出y0=kx0，代入上式得出方程At2+Bt+C=0。通過求解，判斷其根是否在0到1之間，若是，則說明直線和三次Bezier曲線邊有交點(diǎn)，可求出該交點(diǎn)的參數(shù)值。若是連接三次Bezier曲線邊兩端點(diǎn)的直線和曲線邊相交，此時其交點(diǎn)也相當(dāng)于分割點(diǎn)。通過假定過曲線邊兩端點(diǎn)的坐標(biāo)分別為（x0，y0）和（x3，y3），且其直線方程為：y=kx+b，將（1）式代入，推算出：

3 基于計(jì)算機(jī)圖形學(xué)的高維空間中歐式距離計(jì)算的設(shè)計(jì)

在高維空間中，各種對象所具備的特征組成均可看成一個點(diǎn)，例如在人臉識別方面，可通過提取更多的人臉特征，并將其存入相應(yīng)的人臉特征向量數(shù)據(jù)庫，當(dāng)需要查找某個人時，只需輸入相應(yīng)的人臉特征向量，便可完成對輸入人臉的識別。在此計(jì)算設(shè)計(jì)中，可假定一個n維向量空間，x為其特征向量，xi表示第i個人臉特征數(shù)值，c為一個高維數(shù)據(jù)點(diǎn)，R表示一個固定的半徑長度，c與R之間的所有點(diǎn)組合成一個n維的集合——超球C。

在n維空間中，x到y(tǒng)之間的歐式距離L2、以及街區(qū)距離L1和棋盤距離L∞分別為：

由此可見，計(jì)算其街區(qū)距離或是棋盤距離相對較為簡單。根據(jù)簡單驗(yàn)證L∞≤L2≤L1，計(jì)算L∞和L1的線性組合來取代對L2的計(jì)算。具體如下。

假定n維超球C的球心為坐標(biāo)系原點(diǎn)O，再根據(jù)半徑R，可推斷出方程：

根據(jù)超球C的球心為坐標(biāo)系原點(diǎn)，了解到L1和L∞中的yi均為0，那么L1和L∞的簡單形式：a（L1+L∞）為：

取絕大值和最大值，得出共有n·2n個超平面，圍成一個n維超多面體。假設(shè)在xi≥0的卦限，在第n個坐標(biāo)軸附近，L∞=xn，則其相應(yīng)表面所在的超平面方程為：

此時分幾種情況考慮，一是超多面體剛好在超球內(nèi)部，令第n個坐標(biāo)軸上的點(diǎn)P（0，0，……，0，R）落在超球表面以及超多面體的表面上，則a（0+0+……+R+R）=R，得出a的值為0.5。由此可了解到，n個坐標(biāo)數(shù)值中，存在i-1個0，或是n-i-1的值相等，為：

此時可以完成對某頂點(diǎn)到原點(diǎn)的距離平方的計(jì)算，得出 。其中，R2的系數(shù)不大于1。即所有點(diǎn)均在超球內(nèi)部，或者說超多面體剛好落在超球內(nèi)部，數(shù)值偏小。a=0.5，n=2，八邊形在圓的內(nèi)部；a=0.5，n=3，多面體在球的內(nèi)部。

二是超多面體剛好落在超球外部，用公式表示為：

假定一個數(shù)值A(chǔ)，代入上述公式以確保所選擇的a值使其xi有唯一解。首先，應(yīng)經(jīng)過平移公式xi=xi’+A（1≤i≤n），得出：

將其中的（x’1+x’2+……+xn+1’）的系數(shù)，以及最后一項(xiàng)設(shè)定為0，聯(lián)立得到的兩個方程求得：

并對（x’1+x’2+……+xn+1’）的系數(shù)，以及最后一項(xiàng)設(shè)定為0后的方程的前兩項(xiàng)進(jìn)行驗(yàn)證，可知方程前兩項(xiàng)可成為正定二次型。假設(shè)方程有唯一解，那么x’1=x’2=……=xn+1’=0，由此可知滿足要求的是：

為了驗(yàn)證超球是否與超多面體外切，可將a值代入（3）式，完成后將其代入方程：x12+x22+…+xn2=R2。計(jì)算得到各頂點(diǎn)到原點(diǎn)距離的平方為：

在1≤i≤n的條件下，驗(yàn)證得出R2的系數(shù)≥1，判斷超多面體落在超球外部，說明數(shù)值偏大。a=1/ ，n=2，八邊形和圓外切；a=a=1/ ，n=3，24面體和球外切。此外，在超多面體與超球體積相等時，還可求出八邊形與圓，或24面體與球存在相交情況。

4 結(jié)束語

可以看出，基于計(jì)算機(jī)圖形學(xué)的多類型算法能夠提高算法效率、縮短計(jì)算時間，同時，通過分析曲線多邊形的面積計(jì)算方式，還可以為基于計(jì)算機(jī)圖形學(xué)的多類型算法在三維空間曲面多面體體積的計(jì)算提供參考依據(jù)。

參考文獻(xiàn)：

[1]史浩.計(jì)算機(jī)圖形學(xué)中的Bresenham算法[J].計(jì)算機(jī)時代，2005，06（15）.

[2]趙曉峰.計(jì)算機(jī)圖形學(xué)中凸多邊形窗口的線裁剪算法研究[J].科技信息，2009，04（25）.

作者簡介：李國慶（1966-），男，江蘇徐州人，副教授，主要從事軟件工程、數(shù)據(jù)庫應(yīng)用技術(shù)方面的教學(xué)研究以及教學(xué)管理工作。