計(jì)算機(jī)圖形學(xué) 課件全套 許社教 第1-9章 緒論、圖形處理中的幾何問(wèn)題-圖形學(xué)研究專(zhuān)題

第1章緒論1.1計(jì)算機(jī)圖形學(xué)的概念1.2計(jì)算機(jī)圖形學(xué)的研究?jī)?nèi)容1.3計(jì)算機(jī)圖形系統(tǒng)的組成1.4點(diǎn)陣圖形顯示器簡(jiǎn)介1.5計(jì)算機(jī)圖形學(xué)的應(yīng)用

1.1計(jì)算機(jī)圖形學(xué)的概念

計(jì)算機(jī)圖形學(xué)起源于20世紀(jì)50年代。1950年，第一臺(tái)圖形顯示器旋風(fēng)Ⅰ號(hào)誕生于美國(guó)麻省理工學(xué)院。之后，H.JosephGerber設(shè)計(jì)了第一臺(tái)平臺(tái)式繪圖機(jī)。1959年，Calcomp公司研制了第一臺(tái)滾筒式繪圖機(jī)。

什么是計(jì)算機(jī)圖形學(xué)？國(guó)際標(biāo)準(zhǔn)化組織ISO對(duì)于計(jì)算機(jī)圖形學(xué)（ComputerGraphics，CG）的定義為：利用計(jì)算機(jī)將數(shù)據(jù)轉(zhuǎn)換為圖形，并在繪圖設(shè)備上進(jìn)行圖形顯示或繪制的一門(mén)學(xué)科。

計(jì)算機(jī)圖形學(xué)涉及圖形輸入、圖形處理和圖形輸出三個(gè)過(guò)程。圖形輸入和圖形輸出都是視覺(jué)圖形與數(shù)據(jù)的映射，前者為圖形到數(shù)據(jù)的映射，后者為數(shù)據(jù)到圖形的映射。圖形處理即數(shù)據(jù)轉(zhuǎn)換，可以實(shí)現(xiàn)簡(jiǎn)單圖形到復(fù)雜圖形的轉(zhuǎn)換。輸入的圖形一般為簡(jiǎn)單的圖形，圖形輸入計(jì)算機(jī)后為簡(jiǎn)單圖形的數(shù)據(jù)，其經(jīng)過(guò)圖形處理后可得到復(fù)雜圖形的數(shù)據(jù)，將復(fù)雜圖形的數(shù)據(jù)以視覺(jué)形式在繪圖設(shè)備上顯示或繪制就得到了最終需要的圖形，此過(guò)程便是圖形輸出。

1.2計(jì)算機(jī)圖形學(xué)的研究?jī)?nèi)容

計(jì)算機(jī)圖形學(xué)研究的圖形分為參數(shù)圖和像素圖兩類(lèi)。用尺寸、參數(shù)描述的圖稱(chēng)為參數(shù)圖，常稱(chēng)為圖形，如機(jī)械圖中的零件圖、裝配圖，電路圖等。用點(diǎn)陣法描述的圖（圖由若干像素點(diǎn)構(gòu)成，每個(gè)像素點(diǎn)有不同的色彩或灰度）稱(chēng)為像素圖，簡(jiǎn)稱(chēng)為圖像，如彩色照片、油畫(huà)等。圖形與圖像可以相互轉(zhuǎn)換。圖形數(shù)字化（光柵化）的結(jié)果就是圖像，圖像識(shí)別與理解的結(jié)果就是圖形。圖形、圖像的研究趨于融合。

計(jì)算機(jī)圖形學(xué)的研究?jī)?nèi)容從大的方面分為硬件、軟件、圖形理論與算法三個(gè)方面。

1.硬件研究

硬件研究是指研制圖形輸入、輸出設(shè)備，研究計(jì)算機(jī)圖形系統(tǒng)的硬件配置（系統(tǒng)集成）。

2.軟件研究

軟件研究是指研究圖形軟件的設(shè)計(jì)與使用、各種圖形軟件的開(kāi)發(fā)研究以及圖形軟件的標(biāo)準(zhǔn)化。

3.圖形理論與算法研究

圖形理論研究側(cè)重于圖形表示和新圖形生成，圖形算法研究側(cè)重于圖形問(wèn)題的解決途徑。

解決某一問(wèn)題的算法可能有多個(gè)，評(píng)價(jià)算法優(yōu)劣的指標(biāo)是時(shí)間復(fù)雜度和空間復(fù)雜度。前者要求計(jì)算量小、運(yùn)算速度快，后者要求占用存儲(chǔ)空間少。主要研究?jī)?nèi)容如下：

1）圖形設(shè)備顯示或繪制的基本圖形元素生成算法

該研究?jī)?nèi)容包括直線、圓弧、字符、二次曲線、圖案填充等圖形元素的生成算法。

2）圖形變換及裁剪

圖形變換是指對(duì)圖形進(jìn)行比例、平移、旋轉(zhuǎn)、錯(cuò)切、反射等幾何變換和對(duì)物體進(jìn)行各種投影變換（正投影變換、軸測(cè)投影變換、透視投影變換）；圖形裁剪包括二維開(kāi)窗裁剪、三維取景裁剪。

3）自由曲線、曲面的生成與處理

自由曲線、曲面的生成與處理包括曲線和曲面的插值、逼近、拼接、分解、過(guò)渡、光順、整體和局部修改等。圖1.1是自由曲面示例。

4）消隱處理

消隱處理是指對(duì)沿觀察方向看不到的物體上的棱線或表面（分別稱(chēng)為隱藏線、隱藏面）進(jìn)行判斷處理。

圖1.1自由曲面示例

5）二維、三維造型技術(shù)

二維、三維造型技術(shù)包括二維面素拼合構(gòu)圖（解決二維圖形的并、交、差運(yùn)算）、三維實(shí)體造型（研究體素的形成，體素間的并、交、差運(yùn)算，局部造型等）、特征造型。圖1.2是焊片視圖的二維造型過(guò)程，圖1.3是支架的三維造型結(jié)果。

圖1.2焊片視圖的二維造型過(guò)程圖1.3支架的三維造型結(jié)果

6）真實(shí)感圖形（逼真圖像）的生成

真實(shí)感圖形是指用計(jì)算機(jī)模擬生成像彩色照片效果的圖形，也稱(chēng)為光照仿真圖形（渲染圖）。紋理映射（軟件中稱(chēng)為“貼圖”）是真實(shí)感圖形生成的重要技術(shù)之一。圖1.4是建模后經(jīng)光照仿真得到的物體真實(shí)感圖形。

圖1.4物體真實(shí)感圖形

7）科學(xué)計(jì)算可視化（圖形可視化）

用有限元法、矩量法、有限差分法等工程分析法對(duì)物體進(jìn)行應(yīng)力、熱、流動(dòng)性、電場(chǎng)、磁場(chǎng)分析后，可得到大量的標(biāo)量（如溫度）場(chǎng)或矢量（如電場(chǎng)強(qiáng)度）場(chǎng)數(shù)據(jù)。這些數(shù)據(jù)只有通過(guò)圖形的形式才能反映物理量的變化規(guī)律，彩色云圖是數(shù)據(jù)可視化的主要表現(xiàn)形式。圖形可視化也可用于分析模型的驗(yàn)證。圖1.5是多個(gè)領(lǐng)域的模型或數(shù)據(jù)圖形可視化圖例。

圖1.5模型或數(shù)據(jù)圖形可視化圖例

8）三維重建技術(shù)

根據(jù)實(shí)物掃描得到的點(diǎn)云或物體的視圖而求取其三維幾何模型稱(chēng)為三維重建。三維重建屬于逆向工程。三維重建的數(shù)據(jù)源有兩種，一種是對(duì)實(shí)物用專(zhuān)用儀器（如三坐標(biāo)測(cè)量機(jī)、CT機(jī)等）進(jìn)行層掃描測(cè)量得到的點(diǎn)云數(shù)據(jù)，另一種是設(shè)計(jì)或物體攝像經(jīng)圖像矢量化處理得到的視圖數(shù)據(jù)。

9）3D（三維）打印模型處理技術(shù)

3D打印是智能制造和個(gè)性化制造的典型技術(shù)，屬于增材制造。3D打印的數(shù)據(jù)源為物體的三維幾何模型。

10）圖形數(shù)據(jù)結(jié)構(gòu)及圖形數(shù)據(jù)庫(kù)

圖形數(shù)據(jù)結(jié)構(gòu)及圖形數(shù)據(jù)庫(kù)是解決復(fù)雜圖形問(wèn)題（尤其是三維問(wèn)題）的關(guān)鍵，它與算法一樣重要。

11）分形幾何

傳統(tǒng)幾何為歐氏幾何，即整數(shù)維幾何，如一維的直線、二維的多邊形、三維的立方體。而分形幾何屬于分?jǐn)?shù)維幾何，可用于描述不規(guī)則、隨機(jī)且有統(tǒng)計(jì)自相似的物體或現(xiàn)象，如山川地貌、樹(shù)木花草、水、火、煙、云、霧等。分形圖形通過(guò)迭代生成。圖1.6（a）是雪花分形圖形的迭代生成過(guò)程，圖1.6（b）是其迭代規(guī)則。

圖1.6雪花分形圖形的迭代生成

設(shè)

N

為每一步細(xì)分的數(shù)目，S為細(xì)分時(shí)的縮放倍數(shù)，則分維數(shù)定義為

對(duì)于圖1.6所示的圖形，N=4，S=1/3，則其維數(shù)D=1.2619。

分形幾何圖形的生成方法有分形布朗運(yùn)動(dòng)法（主要是MPD法，即隨機(jī)中點(diǎn)位移法）、IFS法（迭代函數(shù)系統(tǒng)法）、L系統(tǒng)方法（正規(guī)文法模型）、粒子系統(tǒng)方法、DLA法（擴(kuò)散有限凝聚模型法）等。圖1.7是幾種典型的分形幾何圖形。

圖1.7

12）計(jì)算機(jī)動(dòng)畫(huà)生成

計(jì)算機(jī)動(dòng)畫(huà)生成是指研究如何實(shí)時(shí)（快速）、方便、自動(dòng)地生成場(chǎng)景中的物體和圖形，以及動(dòng)畫(huà)的播放技術(shù)。

1.3計(jì)算機(jī)圖形系統(tǒng)的組成

1.計(jì)算機(jī)圖形系統(tǒng)的功能（1）計(jì)算功能。（2）存儲(chǔ)功能。（3）輸入功能。（4）對(duì)話功能。（5）輸出功能。

2.計(jì)算機(jī)圖形系統(tǒng)的硬件配置

（1）主機(jī)。

（2）外存儲(chǔ)器。

（3）圖形輸入設(shè)備。

圖1.8為幾種圖形輸入設(shè)備。

（4）圖形輸出設(shè)備。

圖1.8圖形輸入設(shè)備

3.計(jì)算機(jī)圖形系統(tǒng)的軟件配置

（1）系統(tǒng)軟件。系統(tǒng)軟件也稱(chēng)為一級(jí)軟件，它包括各種操作系統(tǒng)、各種高級(jí)語(yǔ)言系統(tǒng)、數(shù)據(jù)庫(kù)管理系統(tǒng)、網(wǎng)絡(luò)操作系統(tǒng)等。

（2）支撐軟件。支撐軟件也稱(chēng)為二級(jí)軟件，是利用一級(jí)軟件開(kāi)發(fā)的，能夠提供最基本的、具有通用功能的軟件，如圖形軟件（AutoCAD）、動(dòng)畫(huà)軟件、幾何造型系統(tǒng)、有限元分析軟件、熱分析軟件等。

（3）應(yīng)用軟件。應(yīng)用軟件也稱(chēng)為三級(jí)軟件，是利用一級(jí)或二級(jí)軟件開(kāi)發(fā)的針對(duì)某行業(yè)、某專(zhuān)業(yè)或某一產(chǎn)品開(kāi)發(fā)的專(zhuān)業(yè)軟件，其優(yōu)點(diǎn)是效率高、效益明顯，代表著軟件的發(fā)展方向，如汽車(chē)CAD軟件、各類(lèi)模具CAD軟件、建筑CAD軟件、服裝CAD軟件、電子CAD軟件等。

1.4點(diǎn)陣圖形顯示器簡(jiǎn)介

點(diǎn)陣圖形顯示器是目前的CAT顯示器、液晶顯示器、等離子體顯示器、發(fā)光二極管顯示器等的統(tǒng)稱(chēng)，稱(chēng)其為點(diǎn)陣圖形顯示器是為區(qū)別早期的隨機(jī)掃描矢量顯示器。點(diǎn)陣圖形顯示器顯示圖形的原理是所有光柵圖形設(shè)備生成圖形的原理。

1.幾個(gè)概念

1）像素

把顯示屏幕劃分為矩形網(wǎng)格，每個(gè)網(wǎng)格就稱(chēng)為像素。屏幕顯示圖形時(shí)，每個(gè)像素都處于“亮”與“不亮”兩種狀態(tài)，所有發(fā)亮的像素點(diǎn)拼成一幅圖形。其中，彩色圖形顯示器每個(gè)像素的顏色是由紅、綠、藍(lán)三原色分量合成的。圖1.9是屏幕上顯示字符和直線段的示例。

圖1.9字符和直線段的顯示原理

2）屏幕分辨率

屏幕分辨率是指屏幕可顯示的像素點(diǎn)總數(shù)，用水平方向的像素點(diǎn)數(shù)乘以豎直方向的像素點(diǎn)數(shù)來(lái)表示，如800×600、1024×768、1280×1204等。顯示器分辨率越高，所顯示的圖形越光滑、越清晰。

3）背景

屏幕上未被字符和圖形填充的區(qū)域稱(chēng)為背景。

4）前景

屏幕上被字符和圖形填充的區(qū)域稱(chēng)為前景。

2.點(diǎn)陣圖形顯示器的組成

1）圖形監(jiān)視器

圖形監(jiān)視器用于觀察圖形的部件，其結(jié)構(gòu)與電視機(jī)類(lèi)似。

2）幀緩沖存儲(chǔ)器（視頻緩存）

幀緩沖存儲(chǔ)器的邏輯結(jié)構(gòu)與屏幕顯示網(wǎng)格對(duì)應(yīng)，其作用是暫時(shí)保存屏幕上的圖形。新生成的圖形以及圖形的刷新都要使用幀緩沖存儲(chǔ)器，其主要技術(shù)指標(biāo)是容量。

容量可進(jìn)行如下估算：

其中，顏色（灰度）的實(shí)現(xiàn)方法主要有位平面法和壓縮像素法。與屏幕分辨率對(duì)應(yīng)的存儲(chǔ)區(qū)稱(chēng)為位平面。位平面法就是用多個(gè)位平面實(shí)現(xiàn)多顏色的顯示，如用4個(gè)位平面就可實(shí)現(xiàn)每個(gè)像素的16種顏色的顯示。壓縮像素法是將一個(gè)像素的全部顏色信息壓縮成一個(gè)字節(jié)或多個(gè)字節(jié)，紅、綠、藍(lán)三原色分占其中的幾位。

3）顯示控制器

顯示控制器用于控制圖形的刷新及顯示。實(shí)際中，幀緩沖存儲(chǔ)器和顯示控制器做在一塊印制板上，稱(chēng)為顯示卡（或顯示適配器）。

1.5計(jì)算機(jī)圖形學(xué)的應(yīng)用

與手工繪圖相比，計(jì)算機(jī)繪圖具有提高繪圖的速度、繪圖的準(zhǔn)確度、可進(jìn)行屏幕模擬與動(dòng)畫(huà)顯示的突出優(yōu)點(diǎn)。計(jì)算機(jī)圖形學(xué)的應(yīng)用領(lǐng)域很廣，幾乎在各個(gè)行業(yè)都有應(yīng)用。

1.繪制工程圖樣

因?yàn)橛?jì)算機(jī)繪圖具有圖形復(fù)制容易和修改快的優(yōu)點(diǎn)，所以它比手工繪圖快得多。產(chǎn)品設(shè)計(jì)中圖樣繪制的工作量約占總工作量的70%左右，采用計(jì)算機(jī)繪圖代替手工繪圖能明顯縮短產(chǎn)品研發(fā)周期并提高設(shè)計(jì)質(zhì)量，因此目前工程設(shè)計(jì)基本上淘汰了手工繪圖，大量采用計(jì)算機(jī)繪制工程圖樣（如零件圖、裝配圖）。圖1.10是用AutoCAD軟件繪制的虎鉗裝配圖。

圖1.10虎鉗裝配圖

2.計(jì)算機(jī)輔助設(shè)計(jì)CAD和計(jì)算機(jī)輔助制造CAMCAD和CAM是計(jì)算機(jī)圖形學(xué)應(yīng)用最活躍和最能產(chǎn)生經(jīng)濟(jì)效益的領(lǐng)域，在機(jī)械、建筑、電子、航空航天、造船、服裝等行業(yè)獲得了廣泛應(yīng)用。

圖1.11是用CAD軟件設(shè)計(jì)的產(chǎn)品（直板手機(jī)為西安電子科技大學(xué)工業(yè)設(shè)計(jì)專(zhuān)業(yè)本科畢業(yè)設(shè)計(jì)作品），圖1.12是用CAM軟件模擬零件加工。

圖1.11CAD的應(yīng)用

圖1.12ＣＡＭ的應(yīng)用

3.計(jì)算機(jī)藝術(shù)設(shè)計(jì)

計(jì)算機(jī)藝術(shù)設(shè)計(jì)包括曲線曲面藝術(shù)造型、分形圖案設(shè)計(jì)等。圖1.13為一些計(jì)算機(jī)藝術(shù)設(shè)計(jì)圖例。

圖1.13計(jì)算機(jī)藝術(shù)設(shè)計(jì)圖例

4.虛擬現(xiàn)實(shí)（VR）/增強(qiáng)現(xiàn)實(shí)（AR）

虛擬現(xiàn)實(shí)、增強(qiáng)現(xiàn)實(shí)是指將虛擬物體置于環(huán)境中，控制物體運(yùn)動(dòng)使其與環(huán)境協(xié)調(diào)并融入環(huán)境。VR、AR中的作用對(duì)象為使用者、虛擬物體和環(huán)境。VR、AR集計(jì)算機(jī)、電子信息（主要是傳感系統(tǒng)，如數(shù)據(jù)手套）、仿真技術(shù)于一體，軟硬結(jié)合，用計(jì)算機(jī)模擬現(xiàn)實(shí)環(huán)境，從而給人以身臨其境的真實(shí)感。計(jì)算機(jī)圖形學(xué)在VR、AR中的作用是三維建模（包括虛擬物體、環(huán)境）、顯示和交互（幫助虛擬物體在環(huán)境中更好地呈現(xiàn)）。

VR/AR越來(lái)越多地應(yīng)用于各個(gè)行業(yè)，如教育、培訓(xùn)與訓(xùn)練、醫(yī)療、設(shè)計(jì)、娛樂(lè)、工業(yè)仿真等。圖1.14為VR/AR的應(yīng)用。圖1.14VR/AR的應(yīng)用

5.計(jì)算機(jī)輔助教學(xué)（CAI）

計(jì)算機(jī)輔助教學(xué)CAI是綜合應(yīng)用多媒體（文字、聲音、圖形圖像）、超文本（網(wǎng)頁(yè)）、人工智能、網(wǎng)絡(luò)通信和知識(shí)庫(kù)等進(jìn)行教學(xué)訓(xùn)練的方法與技術(shù)。CAI具有重點(diǎn)突出、靈活方便、交互性好、聲圖文并茂、圖形形象直觀等優(yōu)點(diǎn)，能提高學(xué)習(xí)者的學(xué)習(xí)興趣和學(xué)習(xí)效率，提高教學(xué)質(zhì)量。MOOC、翻轉(zhuǎn)課堂等CAI將引發(fā)一場(chǎng)新的教育革命。第2章圖形處理中的幾何問(wèn)題2.1圖形坐標(biāo)系2.2幾何元素的定義及特點(diǎn)2.3平面圖形的幾何性質(zhì)2.4幾何元素之間的位置判斷2.5幾何元素之間的求交計(jì)算2.6多邊形及其凸凹性2.7多邊形的分解與網(wǎng)格劃分

2.1圖形坐標(biāo)系

對(duì)圖形對(duì)象的描述，圖形的處理及輸入、輸出，都是在一定的坐標(biāo)系中進(jìn)行的。目前，對(duì)世界坐標(biāo)系、用戶(hù)坐標(biāo)系、局部坐標(biāo)系還沒(méi)有統(tǒng)一的定義，各種文獻(xiàn)及圖形軟件中的說(shuō)法不一。這里從圖形系統(tǒng)的角度提出世界坐標(biāo)系、局部坐標(biāo)系、觀察坐標(biāo)系、設(shè)備坐標(biāo)系、規(guī)范化設(shè)備坐標(biāo)系等5種坐標(biāo)系。在標(biāo)準(zhǔn)圖形系統(tǒng)中，主要坐標(biāo)系使用的邏輯關(guān)系如圖2.1所示。

圖2.1坐標(biāo)系使用的邏輯關(guān)系

在三維坐標(biāo)系統(tǒng)中，有右手坐標(biāo)系和左手坐標(biāo)系之分，通常采用右手坐標(biāo)系。左手坐標(biāo)系和右手坐標(biāo)系的判斷方法有旋向法和三指法。伸開(kāi)右手，若坐標(biāo)系的手指間關(guān)系符合圖2.2所示的關(guān)系則稱(chēng)為右手坐標(biāo)系，否則為左手坐標(biāo)系。

圖2.2右手坐標(biāo)系的判斷方法

2.1.1世界坐標(biāo)系

世界坐標(biāo)系是用戶(hù)為繪圖而建立的初始直角坐標(biāo)系，

為右手坐標(biāo)系，可以是二維或三維的坐標(biāo)系。世界坐標(biāo)系的坐標(biāo)軸方位是固定的，在顯示屏幕上，一般x軸正向朝右，y軸正向朝上，z軸正向按右手定則垂直于屏幕顯示平面朝外，坐標(biāo)系的原點(diǎn)由定義的作圖范圍來(lái)確定，坐標(biāo)的取值范圍可以是計(jì)算機(jī)能夠處理的實(shí)數(shù)范圍，可根據(jù)需要設(shè)置。

2.1.2局部坐標(biāo)系

局部坐標(biāo)系是用戶(hù)在世界坐標(biāo)系或當(dāng)前的坐標(biāo)系中定

義的直角坐標(biāo)系，為右手坐標(biāo)系。局部坐標(biāo)系的坐標(biāo)原點(diǎn)、坐標(biāo)軸的方位是任意的。在某些圖形系統(tǒng)中，把局部坐標(biāo)系稱(chēng)為用戶(hù)坐標(biāo)系。設(shè)立局部坐標(biāo)系是為了便于作圖。例如，在三維繪圖中，利用局部坐標(biāo)系可以把較為復(fù)雜的三維作圖問(wèn)題轉(zhuǎn)化為二維作圖問(wèn)題。圖2.3為局部坐標(biāo)系的應(yīng)用。

圖2.3局部坐標(biāo)系的應(yīng)用

2.1.3觀察坐標(biāo)系

觀察坐標(biāo)系是以視點(diǎn)為坐標(biāo)原點(diǎn)的三維左手(或右手)直角坐標(biāo)系，其中z軸方向?yàn)橐朁c(diǎn)與世界坐標(biāo)系原點(diǎn)(默認(rèn)情況)或模型上點(diǎn)的連線方向，xy平面(觀察平面，即投影平面)與z軸垂直，如圖2.4所示。

觀察坐標(biāo)系取為左手系的原因在于:當(dāng)把觀察平面作為屏幕時(shí)，z軸正方向朝向顯示器里的方向符合我們的視覺(jué)習(xí)慣，越向里表示離我們?cè)竭h(yuǎn)，z值也就越大。

圖2.4觀察坐標(biāo)系與世界坐標(biāo)系

2.1.4設(shè)備坐標(biāo)系

與一個(gè)圖形設(shè)備(輸入設(shè)備或輸出設(shè)備)相關(guān)聯(lián)的直角坐標(biāo)系稱(chēng)為設(shè)備坐標(biāo)系。設(shè)備坐標(biāo)系可以是二維坐標(biāo)系(如二維掃描儀、屏幕、繪圖機(jī)、二維打印機(jī)等)，也可以是三維坐標(biāo)系(如三維掃描儀、三維打印機(jī))。圖形的輸出在設(shè)備坐標(biāo)系下進(jìn)行。設(shè)備坐標(biāo)系的坐標(biāo)取值范圍與設(shè)備的有效幅面和精度有關(guān)，為某個(gè)整數(shù)區(qū)間。對(duì)點(diǎn)陣圖形顯示器和無(wú)筆繪圖機(jī)而言，坐標(biāo)單位是像素(也叫光柵單位)；對(duì)筆式繪圖機(jī)而言，其坐標(biāo)單位是步距(也叫脈沖當(dāng)量)。

點(diǎn)陣圖形顯示器的設(shè)備坐標(biāo)系與屏幕分辨率有關(guān)。假定顯示器的分辨率為1024×768，則該顯示器的設(shè)備坐標(biāo)系為:x∈［0，1023］，y∈［0，767］，x、y為整數(shù)(代表像素位置)。坐標(biāo)原點(diǎn)默認(rèn)情況是在屏幕左上角，如圖2.5(a)所示；坐標(biāo)原點(diǎn)也可設(shè)置在屏幕左下角，如圖2.5(b)所示。

圖2.5屏幕坐標(biāo)系

2.1.5規(guī)范化設(shè)備坐標(biāo)系

坐標(biāo)取值范圍為0到1.0的坐標(biāo)系稱(chēng)為規(guī)范化設(shè)備坐標(biāo)系(。規(guī)范化設(shè)備坐標(biāo)系為:x∈［0.0，1.0］，y∈［0.0，1.0］，x、y為實(shí)數(shù)。用戶(hù)的圖形處理數(shù)據(jù)(如對(duì)模型投影并經(jīng)窗口裁剪得到的數(shù)據(jù))經(jīng)歸一化轉(zhuǎn)換即得規(guī)范化設(shè)備坐標(biāo)系中的坐標(biāo)值。

另外，在一些圖形系統(tǒng)中還使用圓柱面坐標(biāo)系(ρ-φ-z，ρ、φ為空間點(diǎn)在xOy平面上投影的極坐標(biāo)，ρ為極徑，φ為極角，z為空間點(diǎn)到xOy平面的距離)和球面坐標(biāo)系(r-φ-θ，r為空間點(diǎn)到原點(diǎn)的距離，φ為從x軸正向起度量的經(jīng)度角(0°~360°)，θ為從z軸正向起度量的緯度角(0°~180°))。在某些工程應(yīng)用中，如三角形區(qū)域內(nèi)物理量的插值計(jì)算，還可使用面積坐標(biāo)等。

2.2幾何元素的定義及特點(diǎn)

1.點(diǎn)點(diǎn)是圖形處理中最基本的元素，分為端點(diǎn)、交點(diǎn)、切點(diǎn)等。在通常的直角坐標(biāo)系下，二維空間中的點(diǎn)用二元組｛x，y｝或｛x(t)，y(t)｝表示；三維空間中的點(diǎn)用三元組｛x，y，z｝或｛x(t)，y(t)，z(t)｝表示。而在齊次坐標(biāo)系下，n維空間中的點(diǎn)用n+1維坐標(biāo)表示。

在自由曲線和曲面的描述中，常用以下三種類(lèi)型的點(diǎn)：

(1)控制點(diǎn):用來(lái)確定曲線和曲面的位置與形狀，而相應(yīng)的曲線和曲面不一定經(jīng)過(guò)的點(diǎn)。控制點(diǎn)用于構(gòu)造逼近曲線、逼近曲面。

(2)型值點(diǎn):用來(lái)確定曲線和曲面的位置與形狀，而相應(yīng)的曲線和曲面一定經(jīng)過(guò)的點(diǎn)。型值點(diǎn)用于構(gòu)造插值曲線、插值曲面。

(3)插值點(diǎn):為提高曲線和曲面的輸出精度，在型值點(diǎn)之間插入的一系列點(diǎn)。

2.邊(線)

邊分為直線邊和曲線邊。直線邊由其端點(diǎn)(起點(diǎn)和終點(diǎn))定界；曲線邊由一系列型值點(diǎn)或控制點(diǎn)表示，也可用顯式、隱式方程表示。

3.環(huán)

環(huán)是由有序的有向邊(直線段或曲線段)組成的封閉邊界。環(huán)有內(nèi)、外之分，確定面的最大外邊界的環(huán)稱(chēng)為外環(huán)，其邊(或頂點(diǎn))按逆時(shí)針?lè)较蚺判?；而把確定面中內(nèi)孔或凸臺(tái)邊界的環(huán)稱(chēng)為內(nèi)環(huán)，其邊(或頂點(diǎn))按順時(shí)針?lè)较蚺判颉；谶@種定義，在面上沿一個(gè)環(huán)前進(jìn)，其左側(cè)總是面內(nèi)，右側(cè)總是面外。

4.面

面是由一個(gè)外環(huán)和若干個(gè)(包括0個(gè))內(nèi)環(huán)圍成的區(qū)域。一個(gè)面可以無(wú)內(nèi)環(huán)，但必須有一個(gè)且只有一個(gè)外環(huán)。形體中的面有方向性，一般用其外法線矢量方向作為該面的正向。若一個(gè)面的外法線矢量向外，此面為正向面；反之，為反向面。區(qū)分正向面和反向面在實(shí)體造型中的新面生成、真實(shí)感圖形顯示等方面都很重要。

5.體

體是由封閉表面圍成的空間，其邊界是有限面的并集。為了保證幾何造型的可靠性和可加工性，要求形體上任意一點(diǎn)的足夠小的鄰域在拓?fù)渖蠎?yīng)是一個(gè)等價(jià)的封閉圓，即圍繞該點(diǎn)的形體鄰域在二維空間中可以構(gòu)成一個(gè)單連通域。我們把滿(mǎn)足這個(gè)定義的形體稱(chēng)為正則形體(或稱(chēng)為流形物體)。含懸掛邊、懸掛面、懸掛體(以點(diǎn)、邊接觸的體)的形體均不是正則形體。

6.形體定義的層次結(jié)構(gòu)

形體在計(jì)算機(jī)中可按上述幾何元素分五個(gè)層次表示，如圖2.6所示。圖2.6形體的層次表示

2.3平面圖形的幾何性質(zhì)

1.平面的外法線矢量計(jì)算設(shè)形體表面外環(huán)上三個(gè)相鄰頂點(diǎn)依次為P1(x1，y1，z1)、P2(x2，y2，z2)、P3(x3，y3，z3)，則該平面的外法線矢量(按右手定則定方向)為

2.三角形的面積、質(zhì)心和質(zhì)量因子的計(jì)算

設(shè)三角形的三個(gè)頂點(diǎn)依次為P1(x1，y1，z1)、P2(x2，y2，z2)、P3(x3，y3，z3)，則有三角形的面積：

其中，ｐ為三角形周長(zhǎng)的一半，a、b、c為三邊的邊長(zhǎng)。

當(dāng)α=0時(shí)，表示一條直線；當(dāng)α=1時(shí)，表示正三角形，這時(shí)質(zhì)量最好。圖2.7分別為不同三角形的質(zhì)量因子α的值。在三角形質(zhì)量判斷中，α的取值由經(jīng)驗(yàn)數(shù)據(jù)決定，一般它的推薦值為α>0.1。

圖2.7不同三角形的質(zhì)量因子α的值

3.平面凸四邊形的面積、質(zhì)心和質(zhì)量因子的計(jì)算

2.4幾何元素之間的位置判斷

1.點(diǎn)與點(diǎn)的位置判斷點(diǎn)與點(diǎn)的位置關(guān)系主要用于兩點(diǎn)是否重合、兩三角形是否有公共邊的判斷等方面。設(shè)空間兩點(diǎn)P1(x1，y1，z1)、P2(x2，y2，z2)，則這兩點(diǎn)之間的距離1為當(dāng)1＜ε(ε為誤差精度)時(shí)，可判定P1、P2兩點(diǎn)是同一點(diǎn)。

2.點(diǎn)與直線段的位置判斷

點(diǎn)與直線之間的位置關(guān)系用于點(diǎn)是否在直線上、三點(diǎn)是否共線以及三點(diǎn)是否能構(gòu)成三角形的判斷等方面。

設(shè)點(diǎn)為P(x，y，z)，直線段端點(diǎn)為P1(x1，y1，z1)、P2(x2，y2，z2)，則點(diǎn)P到線段P1P2的距離為

3.點(diǎn)與平面的位置判斷

點(diǎn)與平面之間的位置關(guān)系用于四點(diǎn)共面、兩相鄰三角形是否可合并構(gòu)成平面四邊形的判斷等方面。

已知平面上不共線的三點(diǎn)為P1(x1，y1，z1)、P2(x2，y2，z2)、P3(x3，y3，z3)，空間點(diǎn)為P(x，y，z)，設(shè)ｑ為點(diǎn)到平面的代數(shù)距離，則有

若｜ｑ｜≤ε(ε為誤差精度)，則點(diǎn)P在不共線的三點(diǎn)P1、P2、P3所確定的平面上。

4.點(diǎn)在多邊形內(nèi)部的判斷

判斷平面上一個(gè)點(diǎn)是否包含在同平面的一個(gè)多邊形內(nèi)有多種算法，經(jīng)典方法有叉積判斷法、夾角之和檢驗(yàn)法和交點(diǎn)計(jì)數(shù)檢驗(yàn)法。

1)叉積判斷法

叉積判斷法適用于空間平面上一點(diǎn)在同一平面內(nèi)的一個(gè)凸多邊形內(nèi)的判斷。如圖2.8所示，設(shè)P0為平面上一點(diǎn)，P1P2P3P4為凸多邊形。由于空間點(diǎn)可用位置矢徑表示，令Vi=Pi-P0(i=1，2，…，n)，Vn+1=V1，一般情況下，點(diǎn)P0在多邊形內(nèi)的充要條件是叉積Vi×Vi+1

(i=1，2，…，n)的符號(hào)相同。特殊地，當(dāng)Vi×Vi+1=0(點(diǎn)P0在多邊形的邊上或邊的延長(zhǎng)線上)時(shí)，認(rèn)為點(diǎn)在多邊形外。

圖2.8叉積判斷法

2)夾角之和檢驗(yàn)法

如圖2.9所示，假設(shè)平面上有點(diǎn)P0和多邊形P1P2P3

P4P5，將點(diǎn)P0分別與Pi相連，構(gòu)成向量Vi=Pi-P0(i=1，2，…，n)，Vn+1=V1。假設(shè)∠Pi

P0Pi+1=αi(Pn+1=P

1)，則它可通過(guò)下列公式計(jì)算：

αi的正負(fù)號(hào)由Vi×Vi+1的正負(fù)決定。

圖2.9夾角之和檢驗(yàn)法

3)交點(diǎn)計(jì)數(shù)檢驗(yàn)法

交點(diǎn)計(jì)數(shù)檢驗(yàn)法適用較廣，特別適用凹多邊形及帶孔多邊形情況下的點(diǎn)是否在多邊形內(nèi)的判斷。判斷的基本思想是:從被判斷點(diǎn)(x0，y0)向右作一射線至無(wú)窮遠(yuǎn)，即射線方程為

求射線與多邊形相交時(shí)的交點(diǎn)個(gè)數(shù)。

如果交點(diǎn)個(gè)數(shù)為奇數(shù)，則點(diǎn)在多邊形之內(nèi)；如果交點(diǎn)

個(gè)數(shù)為偶數(shù)(含0)或特殊情況時(shí)點(diǎn)在多邊形邊上，則點(diǎn)在多邊形之外。如圖2.10(a)所示，射線a、c、d與多邊形相交，其交點(diǎn)個(gè)數(shù)分別為2、2、4，為偶數(shù)，可以直接判斷A、C、D三點(diǎn)均在多邊形之外；而射線b、e分別交多邊形的交點(diǎn)數(shù)為3和1，所以也可直接判斷B、E兩點(diǎn)均在多邊形之內(nèi)。

但當(dāng)圖2.10(b)中的射線f、g、h、i、j均通過(guò)多邊形的頂點(diǎn)、圖2.10(a)中射線ｋ與邊重合時(shí)，交點(diǎn)計(jì)數(shù)應(yīng)特殊處理。如射線

g與多邊形的邊6、邊7交于一頂點(diǎn)，這時(shí)如果將交點(diǎn)計(jì)數(shù)為2，則會(huì)誤判斷點(diǎn)G在多邊形之外；如果將交點(diǎn)計(jì)數(shù)為1，則又會(huì)誤判斷點(diǎn)F在多邊形之內(nèi)(射線f與邊7、邊8交于一頂點(diǎn))。

圖2.10交點(diǎn)計(jì)數(shù)檢驗(yàn)法

參見(jiàn)圖2.11，具體計(jì)數(shù)時(shí)，當(dāng)兩條邊的另兩個(gè)端點(diǎn)的y值均大于y0，即兩邊均處于射線上方時(shí)，計(jì)數(shù)為2，如圖2.11(a)所示；當(dāng)兩條邊另兩端點(diǎn)的y值均小于y0，即兩條邊均處在射線下方時(shí)，交點(diǎn)計(jì)數(shù)為0，如圖2.11(b)所示；當(dāng)兩條邊的兩端點(diǎn)分布在射線兩側(cè)時(shí)，交點(diǎn)計(jì)數(shù)為1，如圖2.11(c)所示。當(dāng)邊與射線重合時(shí)，可將邊視作壓縮為一點(diǎn)，按圖2.11(d)、(e)、(f)類(lèi)似處理。

圖2.11交點(diǎn)計(jì)數(shù)方法

5.點(diǎn)在多面體內(nèi)的判斷

1)點(diǎn)在凸多面體內(nèi)的判斷

設(shè)點(diǎn)P為空間點(diǎn)，Ni是凸多面體每個(gè)面的外法矢量，Pi是面上一點(diǎn)(常取面的頂點(diǎn))，若滿(mǎn)足Ni·(P-Pi)＜0，則點(diǎn)P在多面體內(nèi)。

2)點(diǎn)在一般多面體內(nèi)的判斷

點(diǎn)在一般多面體內(nèi)的判斷類(lèi)似于點(diǎn)在多邊形內(nèi)部判斷的交點(diǎn)計(jì)數(shù)法。

2.5幾何元素之間的求交計(jì)算

幾何元素之間的求交計(jì)算主要有兩直線段求交、直線段與平面求交、平面與平面求交等，其應(yīng)用十分廣泛，除用于點(diǎn)在多邊形及多面體內(nèi)的包含性判斷外，還用于區(qū)域填充、二維或三維圖形裁剪、二維或三維圖形布爾運(yùn)算、投影求取、多邊形或多面體分解、對(duì)稱(chēng)計(jì)算、幾何量或物理量插值計(jì)算、消隱計(jì)算、光線跟蹤計(jì)算等。

1.空間平面上兩直線段的求交

兩條線段的求交分兩步，第一步為快速排斥判斷及跨立判斷以確定兩線段是否相交；第二步為對(duì)相交線段求交點(diǎn)。設(shè)線段P1P2、Q1Q2在同一平面上，兩線段求交算法的步驟如下。

1)快速排斥判斷

設(shè)以線段P1P2為對(duì)角線的軸向矩形(矩形邊與坐標(biāo)軸平行)為R、以線段Q1Q2為對(duì)角線的軸向矩形為T(mén)，如果R和T分離不相交，顯然兩線段不會(huì)相交，則求交結(jié)束；否則(R和T相交或內(nèi)含情況，這時(shí)線段可能相交，也可能不相交)進(jìn)行跨立判斷。

2)跨立判斷

如果兩線段相交，則兩線段必然相互跨立對(duì)方(一條線段的兩個(gè)端點(diǎn)在另一條線段的兩側(cè))，如圖2.12所示。

圖2.12跨立驗(yàn)證

3)求取交點(diǎn)

線段P1P2、Q1Q2的方程用矢量形式分別表示為

2.直線段與平面的求交

1)矢量求解方法

考慮直線段與無(wú)界平面的求交問(wèn)題，如圖2.13所示。

給定直線段的兩個(gè)端點(diǎn)，則直線段方程可表示為

給定平面上三個(gè)點(diǎn)，則平面方程可表示為

圖2.13直線段與平面的求交

2)代數(shù)求解方法

其中：

2.14直線與空間平面的交點(diǎn)

3.平面與平面的求交

平面是最常用的一種面。在進(jìn)行包含平面的實(shí)體之間的布爾運(yùn)算、進(jìn)行實(shí)體的剖切運(yùn)算(以便得到實(shí)體的剖面圖)或利用掃描線進(jìn)行光照計(jì)算及消隱時(shí)，都涉及平面與平面的求交問(wèn)題。

1)基于線面求交的面面求交算法

設(shè)兩個(gè)一般多邊形分別記為A和B，面面求交算法包括下面四步：

(1)將A的所有邊分別與B求交(利用直線段與平面求交，直線段落在平面上時(shí)不計(jì)交點(diǎn))，求出所有有效交點(diǎn)(既在多邊形A的邊上(檢查參數(shù)范圍判斷)，又在多邊形B內(nèi)(利用點(diǎn)在多邊形內(nèi)的判斷)的點(diǎn))；

(2)將B的所有邊分別與A求交，求出所有有效交點(diǎn)(既在多邊形B的邊上，又在多邊形A內(nèi)的點(diǎn))；

(3)將所有交點(diǎn)依次按x、y、z的大小進(jìn)行排序，即先按x坐標(biāo)排序，然后對(duì)x坐標(biāo)相同的交點(diǎn)再按y坐標(biāo)排序，最后對(duì)x、y相同的交點(diǎn)按z坐標(biāo)排序；

(4)將每對(duì)交點(diǎn)(如交點(diǎn)1、交點(diǎn)2為一對(duì)，交點(diǎn)3、交點(diǎn)4為一對(duì)，依次類(lèi)推)的中點(diǎn)與A和B進(jìn)行包含性檢測(cè)(利用點(diǎn)在多邊形內(nèi)的判斷)，若該中點(diǎn)既在A中又在B中，則該對(duì)交點(diǎn)為A和B的一條交線段。

2)基于線線求交的面面求交算法———課程思政案例

基于線線求交的面面求交算法是編者已授權(quán)的國(guó)家發(fā)明專(zhuān)利。此案例的創(chuàng)新思路在于抓住了平面與平面的理論交線這個(gè)兩個(gè)平面之間的橋梁，進(jìn)而可以將線面求交轉(zhuǎn)化為線線求交并利用交點(diǎn)在理論交線的位置參數(shù)(直線參數(shù)方程中的參數(shù))對(duì)交點(diǎn)排一次序即可。此案例旨在培養(yǎng)創(chuàng)新思維能力和創(chuàng)新精神。

設(shè)兩個(gè)一般多邊形分別記為A和B，參見(jiàn)圖2.15、圖2.16，算法步驟如下：

(1)求取A和B的理論交線，并取足夠長(zhǎng)度形成理論交線段；

(2)分別在A和B上進(jìn)行理論交線段與多邊形的邊線段求交(利用直線段與直線段求交)，線段重合時(shí)不計(jì)交點(diǎn)，以避免在進(jìn)行三維實(shí)體布爾運(yùn)算時(shí)出現(xiàn)重合或懸掛的線、面；

(3)分別對(duì)A和B沿理論交線對(duì)交點(diǎn)按位置參數(shù)從小到大排序并形成交點(diǎn)組(如圖2.15所示，A的交點(diǎn)11、9為一組，交點(diǎn)10、12為一組；B的交點(diǎn)9′、11′為一組，交點(diǎn)12′、10′為一組)，剔除端點(diǎn)重合的交點(diǎn)組，以避免在三維實(shí)體布爾運(yùn)算時(shí)出現(xiàn)孤立的點(diǎn)或懸掛的線；

(4)對(duì)A和B的交點(diǎn)組按位置參數(shù)求交集得到可能交線段(如圖2.15所示的線段9′-9、10-10′，圖2.16所示的線段1-2、3-4、5-6)；

(5)對(duì)可能交線段的中點(diǎn)進(jìn)行A和B的包含性檢測(cè)以確定最終交線段，這一步主要適用于有內(nèi)環(huán)且內(nèi)環(huán)邊在兩個(gè)平面理論交線上時(shí)的處理，如圖2.16所示。

按此算法，圖2.15的最終交線段為9′-9、10-10′，圖2.16所示最終交線段為1-2、5-6。圖2.15面面求交示例

圖2.16面面求交奇異情況

4.矢量表示點(diǎn)批判學(xué)習(xí)案例

比較有影響的國(guó)外專(zhuān)著《計(jì)算機(jī)圖形學(xué)幾何工具算法詳解》的9.2.1節(jié)講平面方程時(shí)，平面上的點(diǎn)用P=dn表示，其中n為平面法線矢量，d為常數(shù)，即點(diǎn)用矢量表示。11.5.1節(jié)講兩個(gè)平面求交時(shí)，直線上的點(diǎn)用P=an1+bn2表示，其中n1、n2分別為兩個(gè)平面的法線矢量，a、b為常數(shù)，an1+bn2的結(jié)果仍為矢量，即點(diǎn)也用矢量表示。

2.6多邊形及其凸凹性2.6.1基本概念1.簡(jiǎn)單多邊形設(shè)Vi(i=1，2，3，…，n)是給定封閉多邊形的n個(gè)頂點(diǎn)。若同時(shí)滿(mǎn)足以下條件：(1)對(duì)任意的i≠j(i，j=1，2，3，…，n)，存在Vi≠Vj，即所有頂點(diǎn)均不相同；(2)任何頂點(diǎn)都只屬于它所在的邊；(3)任何兩條非相鄰邊都不相交。則稱(chēng)該多邊形為簡(jiǎn)單多邊形。

圖2.17為簡(jiǎn)單多邊形，圖(a)是一個(gè)簡(jiǎn)單單連通多邊形(不帶內(nèi)環(huán))，圖(b)是一個(gè)簡(jiǎn)單多連通多邊形(帶內(nèi)環(huán))。圖2.17簡(jiǎn)單多邊形

圖2.18不是簡(jiǎn)單多邊形，其中(a)不滿(mǎn)足第(1)條，(b)不滿(mǎn)足第(2)、(3)條。圖2.18非簡(jiǎn)單多邊形

2.簡(jiǎn)單多邊形頂點(diǎn)凸凹性的定義、凸角與凹角、凸多邊形與凹多邊形

設(shè)V1，…，Vn是一個(gè)簡(jiǎn)單多邊形。對(duì)于任一頂點(diǎn)Vi(i=1，2，3，…，n)，若線段Vi

-

1Vi(令V0=Vn)與線段ViVi+1(令Vn+1=V1)所形成的內(nèi)角(由該多邊形所圍成有界區(qū)域內(nèi)兩邊所夾的角)是一個(gè)小于180°的角，則稱(chēng)Vi是凸頂點(diǎn)；若內(nèi)角是一個(gè)大于180°的角，則稱(chēng)Vi是凹頂點(diǎn)；若內(nèi)角是一個(gè)等于180°的角，則稱(chēng)Vi是中性點(diǎn)，在圖形處理時(shí)可根據(jù)需要將其看作凸頂點(diǎn)或者凹頂點(diǎn)。由此定義可知，對(duì)任意一個(gè)簡(jiǎn)單多邊形，其每個(gè)頂點(diǎn)或是凸的，或是凹的。凸頂點(diǎn)對(duì)應(yīng)的內(nèi)角稱(chēng)為凸角，凹頂點(diǎn)對(duì)應(yīng)的內(nèi)角稱(chēng)為凹角。

對(duì)簡(jiǎn)單單連通多邊形而言，所有頂點(diǎn)都為凸頂點(diǎn)的多邊形稱(chēng)為凸多邊形，至少有一個(gè)頂點(diǎn)為凹頂點(diǎn)的多邊形稱(chēng)為凹多邊形。

3.多邊形的方向、有向邊

多邊形的方向有逆時(shí)針?lè)较蚝晚槙r(shí)針?lè)较蛑?。?duì)簡(jiǎn)單單連通多邊形而言，沿觀察方向看去，若觀察者按頂點(diǎn)序列V1V2…VnVn+1繞多邊形一周時(shí)，該多邊形所圍的有界區(qū)域總在左邊，則稱(chēng)該多邊形為逆時(shí)針?lè)较?，如圖2.19(a)所示；否則，稱(chēng)其為順時(shí)針?lè)较?，如圖2.19(b)所示。

圖2.19多邊形的方向

4.頂點(diǎn)的叉積

2.6.2多邊形凸凹性的判斷

1.多邊形方向的判斷

多邊形方向的判斷方法為極值頂點(diǎn)法。多邊形頂點(diǎn)中坐標(biāo)值為xmin或xmax或ymin或ymax的頂點(diǎn)稱(chēng)為極值頂點(diǎn)，極值頂點(diǎn)必為凸頂點(diǎn)。

極值頂點(diǎn)法如下：

(1)找出多邊形的某一極值頂點(diǎn)。

(2)求該極值頂點(diǎn)的叉積。

(3)若叉積值nz>0，則多邊形的方向?yàn)槟鏁r(shí)針?lè)较颍蝗舨娣e值nz＜0，則多邊形的方向?yàn)轫槙r(shí)針?lè)较颉?/p>

2.多邊形頂點(diǎn)凸凹性的判斷

假定多邊形V1V2…Vn的方向?yàn)槟鏁r(shí)針?lè)较?，這是常見(jiàn)的情況。多邊形頂點(diǎn)凸凹性的判斷方法有頂點(diǎn)叉積法、平移旋轉(zhuǎn)法等。這里介紹較為簡(jiǎn)單的頂點(diǎn)叉積法。

對(duì)于逆時(shí)針?lè)较虻亩噙呅?，任一頂點(diǎn)Vi凸凹性判斷的頂點(diǎn)叉積法如下：

(1)計(jì)算頂點(diǎn)Vi的叉積。

(2)若叉積值nz>0，則該頂點(diǎn)為凸頂點(diǎn)；若叉積值nz＜0，則該頂點(diǎn)為凹頂點(diǎn)；若叉積值nz=0，則該頂點(diǎn)為中性點(diǎn)，可根據(jù)需要將其看作凸頂點(diǎn)或者凹頂點(diǎn)

如圖2.20所示，多邊形V1V2V3V4V5V6為逆時(shí)針走向，圖中箭頭代表各個(gè)頂點(diǎn)的叉積方向。箭頭朝上表示叉積值為正，可知頂點(diǎn)V1、V2、V3、V4、V6是凸頂點(diǎn)；箭頭朝下表示叉積值為負(fù)，可知頂點(diǎn)V5是凹頂點(diǎn)。

圖2.20逆時(shí)針?lè)较蚨噙呅蔚牟娣e示意圖

3.多邊形凸凹性的判斷

經(jīng)過(guò)頂點(diǎn)凸凹性判斷后，若多邊形所有頂點(diǎn)都為凸頂點(diǎn)，則該多邊形是凸多邊形；否則為凹多邊形。

經(jīng)上述判斷，圖2.20所示的多邊形為凹多邊形。

2.7多邊形的分解與網(wǎng)格劃分

2.7.1凸多邊形的三角分解參見(jiàn)圖2.21，凸多邊形三角分解的算法如下：(1)找出多邊形最長(zhǎng)對(duì)角線的兩個(gè)端點(diǎn)，目的是得到質(zhì)量較好的三角形。(2)將每個(gè)端點(diǎn)與它們相鄰頂點(diǎn)連線形成兩個(gè)三角形并輸出。(3)對(duì)剩余部分按(1)、(2)遞歸剖分，直至剖分完畢或最后剩余一個(gè)三角形輸出。

圖2.21凸多邊形的三角分解過(guò)程

2.7.2凹多邊形的分解

參見(jiàn)圖2.22，凹多邊形分解的算法如下：

圖2.22凹多邊形的分解

(1)找出多邊形中的第一個(gè)凹頂點(diǎn)(如C點(diǎn))，并確定其前一個(gè)頂點(diǎn)(如B點(diǎn))和后一個(gè)頂點(diǎn)(如D點(diǎn))。

(2)根據(jù)頂點(diǎn)順序，往后另找一點(diǎn)(如E點(diǎn))，判斷此點(diǎn)與凹頂點(diǎn)的連線是否與多邊形的各邊相交，如果相交，則繼續(xù)找下一點(diǎn)，直到找到不相交的點(diǎn)為止。

(3)計(jì)算并判斷此點(diǎn)(如E點(diǎn))與凹頂點(diǎn)連線是否可將本凹頂點(diǎn)(如C點(diǎn))對(duì)應(yīng)的凹角(如∠BCD)劃分為兩個(gè)凸角(此例即是判斷劃分的兩個(gè)內(nèi)角∠BCE和∠ECD是否構(gòu)成凸頂點(diǎn)，可通過(guò)求頂點(diǎn)的叉積進(jìn)行判斷)；如果可以，將凹角劃分，并將劃分后的多邊形分別輸出；如果不行繼續(xù)找下一點(diǎn)，直到滿(mǎn)足條件為止(此例F點(diǎn)滿(mǎn)足將凹角劃分為兩個(gè)凸角的要求，輸出兩個(gè)多邊形ABCF和DEFC)。

(4)判斷輸出的兩個(gè)多邊形的類(lèi)型，若為三角形或凸多邊形，則不需再劃分；否則執(zhí)行步驟(1)～(3)。

(5)對(duì)劃分出的凸多邊形調(diào)用凸多邊形分解算法，將這些凸多邊形分解為三角形輸出。

此算法簡(jiǎn)單，但缺點(diǎn)是分解結(jié)果與多邊形頂點(diǎn)的排序有關(guān)，分解不具有唯一性。

2.7.3帶內(nèi)環(huán)多邊形的分解與基于單調(diào)鏈的凸分解

1.非自交多邊形

在有向多邊形中，非相鄰邊相交的多邊形稱(chēng)為自交多邊形，如圖2.23所示。非相鄰邊不相交但可以重疊的多邊形稱(chēng)為非自交多邊形，如圖2.24所示。非自交多邊形包括簡(jiǎn)單多邊形(圖2.24(a))和有重疊邊但不自相交的多邊形(圖2.24(b))。在圖形處理中，為使帶內(nèi)環(huán)多邊形拓?fù)涞葍r(jià)于不帶內(nèi)環(huán)的多邊形，從而使多邊形分解簡(jiǎn)單、統(tǒng)一，就需要在形式上消除內(nèi)環(huán)，其方法就是在外環(huán)與內(nèi)環(huán)之間、內(nèi)環(huán)與內(nèi)環(huán)之間引入重疊邊或“橋邊”，如圖2.23、圖2.24、圖2.25所示。

圖2.23自交多邊形

圖2.24非自交多邊形NIP

2.基于NIP多邊形的三角分解

該方法通過(guò)在外環(huán)與內(nèi)環(huán)之間、內(nèi)環(huán)與內(nèi)環(huán)之間引入“橋邊”將帶內(nèi)環(huán)多邊形轉(zhuǎn)換為NIP多邊形，然后對(duì)NIP多邊形進(jìn)行三角分解。圖2.25是帶兩個(gè)內(nèi)環(huán)的多邊形轉(zhuǎn)換為一個(gè)NIP多邊形的情況。

圖2.25帶內(nèi)環(huán)多邊形的NIP轉(zhuǎn)換

圖2.26NIP三角分解過(guò)程

圖2.27帶內(nèi)環(huán)多邊形的NIP三角分解

3.基于單調(diào)鏈的凸分解

基于單調(diào)鏈的凸分解的目標(biāo)是將帶內(nèi)環(huán)多邊形分解為凸多邊形。

1)單調(diào)鏈、尖點(diǎn)的概念

單調(diào)鏈的定義:如果一條鏈(開(kāi)口多邊形)上的點(diǎn)在直線L上的正交投影是有序的，即投影點(diǎn)的坐標(biāo)值依次增大(包括相等)，或依次減小(包括相等)，則稱(chēng)該鏈相對(duì)于L單調(diào)，如圖2.28所示。點(diǎn)在直線L上的正交投影是否有序的判斷方法為:沿直線L建立局部坐標(biāo)系并取L為x軸正向，將鏈頂點(diǎn)坐標(biāo)轉(zhuǎn)換為局部坐標(biāo)，比較鏈頂點(diǎn)的x坐標(biāo)看其是否依次增大或依次減小。

圖2.28單調(diào)鏈

如果直線L為y軸，則稱(chēng)該單調(diào)鏈為對(duì)y軸單調(diào)鏈。基于單調(diào)鏈的凸分解算法中的單調(diào)鏈均為對(duì)y軸單調(diào)鏈。圖2.29中的多邊形有M1、M2、M3、M4共4條單調(diào)鏈。

尖點(diǎn)的定義:任意多邊形中，單調(diào)鏈的端點(diǎn)稱(chēng)為尖點(diǎn)。對(duì)于相對(duì)于y軸的單調(diào)鏈，其上端點(diǎn)定義為上尖點(diǎn)，其下端點(diǎn)定義為下尖點(diǎn)。如圖2.29中，S1、S3為上尖點(diǎn)，S2、S4為下尖點(diǎn)。

上、下單調(diào)鏈:任意多邊形中，若沿環(huán)的方向單調(diào)鏈的起點(diǎn)為上尖點(diǎn)，終點(diǎn)為下尖點(diǎn)，則定義其為下單調(diào)鏈，相反則定義其為上單調(diào)鏈。圖2.29中，M1、M3為下單調(diào)鏈，M2、M4為上單調(diào)鏈。

圖2.29上、下尖點(diǎn)與上、下單調(diào)鏈

2)凸分解算法

參見(jiàn)圖2.30，基于單調(diào)鏈的凸分解算法主要包括三個(gè)步驟：

(1)將帶內(nèi)環(huán)多邊形分解為有序單調(diào)鏈。圖2.30(a)按下單調(diào)鏈分解，可分解為9個(gè)下單調(diào)鏈。

(2)通過(guò)分裂和組合單調(diào)鏈，逐次拆分出單調(diào)多邊形。由兩條單調(diào)鏈組成的多邊形稱(chēng)為單調(diào)多邊形，圖(a)的多邊形可拆分如圖(b)所示的4個(gè)單調(diào)多邊形。

(3)將單調(diào)多邊形分解為凸多邊形，如圖(c)所示?？衫们笆龅陌级噙呅畏纸馑惴ㄟM(jìn)行分解。

圖2.30基于單調(diào)鏈的凸分解過(guò)程

2.7.4Delaunay三角剖分

蘇聯(lián)數(shù)學(xué)家Delaunay于1934年證明，對(duì)于散亂點(diǎn)集，必定存在且僅存在一種三角剖分算法，使得剖分得到的所有三角形的最小內(nèi)角之和最大(“最小角最大原則”)，這種算法稱(chēng)為Delaunay三角剖分，簡(jiǎn)稱(chēng)DT剖分。Delaunay三角剖分算法是最著名的三角化網(wǎng)格生成方法，因?yàn)樗哂小叭瞧史肿钚?nèi)角之和為最大”的性質(zhì)，從而保證了網(wǎng)格整體質(zhì)量最優(yōu)，稱(chēng)為最優(yōu)三角剖分。DT剖分可用于數(shù)字地形建模、工程網(wǎng)格劃分、人臉圖像結(jié)構(gòu)建模等。

1.Delaunay三角剖分的性質(zhì)

Delaunay三角剖分具有一些非常重要的性質(zhì)，其中最為重要的性質(zhì)如下：

1)最小內(nèi)角最大準(zhǔn)則

對(duì)一個(gè)凸四邊形進(jìn)行劃分時(shí)，該準(zhǔn)則要求對(duì)角線兩側(cè)兩個(gè)三角形中的最小內(nèi)角為最大。沿短對(duì)角線進(jìn)行劃分可滿(mǎn)足最小內(nèi)角最大準(zhǔn)則，如圖2.31所示。

圖2.31最小內(nèi)角最大原則

2)空外接圓(空外接球)準(zhǔn)則

對(duì)于三角形剖分而言，該準(zhǔn)則稱(chēng)為空外接圓準(zhǔn)則。對(duì)于四面體剖分而言，該準(zhǔn)則稱(chēng)為空外接球準(zhǔn)則。這里討論三角形剖分。對(duì)于任意一個(gè)Delaunay三角形，它的外接圓的內(nèi)部區(qū)域不包含其他的任何結(jié)點(diǎn)，所有Delaunay三角形互不重疊，并且完整地覆蓋整個(gè)區(qū)域。

如圖2.32所示，左圖三點(diǎn)組成了Delaunay三角形，因其外接圓內(nèi)即虛線所示部分再無(wú)其他結(jié)點(diǎn)，而右圖三角形不滿(mǎn)足空外接圓準(zhǔn)則，故不是Delaunay三角形。

圖2.32Delaunay三角形空外接圓準(zhǔn)則

3)局部性

在已有的Delaunay剖分中加入、去除或移動(dòng)一個(gè)結(jié)點(diǎn)后，僅需進(jìn)行局部修改即可獲得Delaunay三角剖分，這就是DT剖分的局部性。所有需要進(jìn)行修改的三角形的并集稱(chēng)為影響域。圖2.33左圖影響域?yàn)閹摼€的5個(gè)三角形的并集，右圖影響域?yàn)閹摼€的3個(gè)三角形的并集?？梢宰C明，影響域的各結(jié)點(diǎn)對(duì)于加入或刪除的點(diǎn)來(lái)說(shuō)都是可見(jiàn)的，所謂可見(jiàn)是指該點(diǎn)與結(jié)點(diǎn)連線不與三角形的邊相交，這給出了影響域的求取方法。因此，影響域是局部的。圖2.33表示了加入或刪除一點(diǎn)所需進(jìn)行的修改。局部性可用于網(wǎng)格稀疏或加密操作。

圖2.33Delaunay三角剖分的局部性

2.Delaunay三角剖分算法

參見(jiàn)圖2.34，算法主要步驟如下：

(1)從當(dāng)前多邊形(初始多邊形和每剖分一次剩余的多邊形)的第一邊開(kāi)始，找對(duì)該邊的可見(jiàn)頂點(diǎn)(在多邊形內(nèi)且頂點(diǎn)與邊的端點(diǎn)連線不與多邊形的邊相交的頂點(diǎn))，若可見(jiàn)頂點(diǎn)有多個(gè)，取對(duì)邊張最大角(邊與頂點(diǎn)形成的三角形外接圓半徑最小)的頂點(diǎn)，由此頂點(diǎn)和邊形成一個(gè)三角形進(jìn)行輸出；

(2)通過(guò)增加或刪除邊、進(jìn)行邊替換、修改第一邊的編號(hào)等操作對(duì)剩余部分形成新的當(dāng)前多邊形；

(3)重復(fù)步驟(1)～(2)，直到剩一個(gè)三角形直接輸出，剖分結(jié)束。

2.7.5用于三角剖分的前沿推進(jìn)法

前沿推進(jìn)法或稱(chēng)為推進(jìn)波前法，是皮埃爾等人提出的一種三角形網(wǎng)格全自動(dòng)生成方法。該方法從邊界向區(qū)域內(nèi)部推進(jìn)，只需要給出區(qū)域邊界的輪廓描述，網(wǎng)格生成的難易與區(qū)域形狀無(wú)關(guān)，因此該算法的適應(yīng)性很強(qiáng)。前沿推進(jìn)法分為兩點(diǎn)前沿推進(jìn)法和三點(diǎn)前沿推進(jìn)法。

兩點(diǎn)前沿推進(jìn)法是指在一條前沿邊(待劃分區(qū)域的邊界邊稱(chēng)為前沿邊)的垂直平分線上生成內(nèi)點(diǎn)，由前沿邊的兩個(gè)端點(diǎn)和此內(nèi)點(diǎn)構(gòu)成三角形，所生成的三角形接近正三角形或等腰三角形，具有局部網(wǎng)格最優(yōu)的特點(diǎn)，但為了判斷所生成點(diǎn)的有效性，需要反復(fù)檢驗(yàn)線段相交情況，故運(yùn)算量較大。

三點(diǎn)前沿推進(jìn)法以?xún)蓷l相鄰的前沿邊為基礎(chǔ)，檢驗(yàn)該兩邊的夾角大小，若其夾角是鈍角或較大的銳角，則在角的平分線上生成一點(diǎn)，該點(diǎn)與兩條前沿邊的三個(gè)端點(diǎn)相連生成兩個(gè)三角形；若其夾角為不大的銳角或夾角雖大但邊短能形成質(zhì)量較好的三角形，則將兩條前沿邊的非公共點(diǎn)直接相連，生成一個(gè)三角形。三點(diǎn)前沿推進(jìn)法簡(jiǎn)單，每步操作都是有效的，故剖分效率較高。

1.前沿推進(jìn)法

前沿推進(jìn)法的主要過(guò)程如下：

(1)按網(wǎng)格大小即三角單元邊長(zhǎng)將邊界離散化，全部邊界點(diǎn)及其連接線段作為初始生成波(初始的前沿)，如圖2.35所示。

圖2.35初始生成波

(2)從邊界的一個(gè)角開(kāi)始，在生成波上選取一邊(對(duì)兩點(diǎn)前沿法)或相鄰兩邊(對(duì)三點(diǎn)前沿法)作為前沿邊，若生成波上相鄰兩邊可直接構(gòu)成銳角三角形，則構(gòu)造一個(gè)三角形單元，稱(chēng)為波的凝聚；否則，以前沿邊為底邊，在區(qū)域內(nèi)生成一點(diǎn)，構(gòu)造一個(gè)三角形單元(對(duì)兩點(diǎn)前沿法，稱(chēng)為波的膨脹)或兩個(gè)三角形單元(對(duì)三點(diǎn)前沿法)。然后隨著前沿邊的前移，不斷生成新的三角形單元，形成新的生成波即新的前沿，如圖2.36所示。

圖2.36波的凝聚與膨脹

(3)生成波的分解。如果前沿邊與相對(duì)的生成波上的點(diǎn)連線構(gòu)成大小符合要求的三角形，則生成波可分解為兩個(gè)子波，如圖2.37所示。針對(duì)兩個(gè)子波可分別生成三角形單元，重復(fù)上述步驟，直到生成波消失從而區(qū)域全部被三角形單元覆蓋為止。

圖2.37波的分解

三點(diǎn)前沿推進(jìn)法也可擴(kuò)展到四邊形網(wǎng)格劃分。在上述網(wǎng)格生成過(guò)程中，以梯形(包括菱形、正方形)代替三角形，當(dāng)兩個(gè)相鄰的前沿邊夾角為銳角或直角時(shí)，則以此兩邊構(gòu)造一個(gè)梯形；當(dāng)兩個(gè)相鄰的前沿邊夾角為鈍角時(shí)，則以此兩邊及其角平分線構(gòu)造兩個(gè)梯形。

2.前沿推進(jìn)法用于載體天線結(jié)構(gòu)三角網(wǎng)格劃分———課程思政案例

圖2.38為編者已授權(quán)發(fā)明專(zhuān)利“基于三角矢量基函數(shù)矩量法的載體天線結(jié)構(gòu)網(wǎng)格劃分方法”的案例，該方法先采用三點(diǎn)前沿推進(jìn)法同時(shí)忽略天線對(duì)載體表面進(jìn)行三角網(wǎng)格劃分，之后用編者提出的質(zhì)心調(diào)勻法進(jìn)行邊界內(nèi)的網(wǎng)格頂點(diǎn)位置微調(diào)，最后在天線與車(chē)體表面連接位置進(jìn)行局部網(wǎng)格劃分，使連接點(diǎn)位于一個(gè)正六邊形的中心，以滿(mǎn)足插值函數(shù)的要求。質(zhì)心調(diào)勻法比傳統(tǒng)的Laplacian迭代調(diào)勻法得到的三角形質(zhì)量要優(yōu)。此案例可培養(yǎng)學(xué)生知行合一、創(chuàng)新的科學(xué)精神。

圖2.38第3章圖形軟件設(shè)計(jì)技術(shù)3.1軟件的模塊化設(shè)計(jì)3.2交互任務(wù)3.3交互技術(shù)3.4用戶(hù)接口3.5交互式圖形軟件的界面構(gòu)成及界面元素3.

6圖形軟件標(biāo)準(zhǔn)3.7OpenGL系統(tǒng)及其應(yīng)用開(kāi)發(fā)

3.1軟件的模塊化設(shè)計(jì)

模塊就是執(zhí)行某一特定任務(wù)的程序代碼。模塊化是指將一個(gè)待開(kāi)發(fā)的軟件分解成若干個(gè)小的簡(jiǎn)單的部分，即模塊，每個(gè)模塊可獨(dú)立地開(kāi)發(fā)、測(cè)試，最后組裝成完整的軟件。模塊化是一種復(fù)雜問(wèn)題“分而治之”的思想。

軟件模塊化必須遵循軟件工程學(xué)的基本原則，其核心問(wèn)題如下：

（1）模塊劃分與調(diào)用。

（2）模塊的獨(dú)立性。模塊之間的聯(lián)系越少，其獨(dú)立性越強(qiáng)。

理想的情況是一個(gè)模塊只使用局部數(shù)據(jù)變量，完成一個(gè)功能。具體設(shè)計(jì)時(shí)，應(yīng)注意：

①設(shè)計(jì)功能獨(dú)立單一的模塊；

②控制使用全局?jǐn)?shù)據(jù)；

③模塊間盡量傳遞數(shù)據(jù)型信息。

耦合度依賴(lài)以下幾個(gè)因素：

①一個(gè)模塊對(duì)另一個(gè)模塊的調(diào)用方式；

②一個(gè)模塊向另一個(gè)模塊傳遞的數(shù)據(jù)量；

③一個(gè)模塊施加到另一個(gè)模塊的控制的多少；

④模塊之間接口的復(fù)雜程度。

模塊劃分的數(shù)量會(huì)影響軟件的開(kāi)發(fā)成本，圖3.1為兩者之間的關(guān)系。

圖3.1模塊化設(shè)計(jì)成本曲線

3.2交互任務(wù)

交互任務(wù)是指用戶(hù)輸入到計(jì)算機(jī)的一個(gè)單元信息。交互任務(wù)分為基本交互任務(wù)和組合交互任務(wù)兩類(lèi)。組合交互任務(wù)是由基本交互任務(wù)結(jié)合而成的，有三種主要的組合交互任務(wù)：對(duì)話框、構(gòu)造和動(dòng)態(tài)操作。對(duì)話框用來(lái)指定信息表中的多個(gè)項(xiàng)；構(gòu)造用來(lái)產(chǎn)生需要有位置約束的形體；動(dòng)態(tài)操作用來(lái)修改已有的幾何形體的形狀，調(diào)整形體之間的相對(duì)位置。

1.定位

定位即給應(yīng)用程序指定位置坐標(biāo)，如（x，y）或（x，y，z）。實(shí)現(xiàn)定位的常用交互技術(shù)是移動(dòng)屏幕上的光標(biāo)輸入位置，或由具有輸入功能的定位設(shè)備（如鍵盤(pán)）直接輸入位置坐標(biāo)值。

2.選擇

選擇任務(wù)是要從一個(gè)選擇集中挑選一個(gè)元素，常用的是命令選擇、操作數(shù)選擇、屬性選擇和對(duì)象選擇等。選擇集一般分為定長(zhǎng)和變長(zhǎng)兩種。像命令、操作數(shù)、屬性等類(lèi)型選擇集一般是定長(zhǎng)的，而對(duì)象選擇集通常是變長(zhǎng)的。

完成選擇任務(wù)有基于名字（或標(biāo)識(shí)符）和位置（坐標(biāo)點(diǎn)）選擇兩種情況。

3.文本

文本任務(wù)是指輸入一個(gè)字符串到字處理器中。

4.定值

定值任務(wù)是要在最大和最小數(shù)值之間確定一個(gè)值。

5.定向

定向即在指定的坐標(biāo)系中確定形體的方向。

6.定路徑

定路徑是一系列定位和定向任務(wù)的結(jié)合。

7.三維交互

三維交互任務(wù)涉及定位、選擇和旋轉(zhuǎn)。

8.對(duì)話框

對(duì)話框多在交互過(guò)程中需要從一個(gè)選擇集中選擇多個(gè)元素時(shí)使用。

9.構(gòu)造

實(shí)現(xiàn)構(gòu)造這類(lèi)任務(wù)的主要方式有橡皮筋方式和約束方式。

圖3.2是用橡皮筋方式畫(huà)折線的情況，首先輸入起點(diǎn)，在要求輸入線段終點(diǎn)時(shí)，移動(dòng)鼠標(biāo)器，光標(biāo)（圖中的十字線）隨之移動(dòng)，線段的終點(diǎn)也在移動(dòng)，而在當(dāng)前點(diǎn)和光標(biāo)點(diǎn)之間始終有一條連線（圖中的虛線），就像橡皮筋一樣隨光標(biāo)移動(dòng)，當(dāng)用戶(hù)認(rèn)為滿(mǎn)意后按下拾取鍵就可以繪出一段直線。利用橡皮筋方式可以畫(huà)直線段、折線、圓、橢圓、矩形、多邊形等。

圖3.2用橡皮筋方式畫(huà)折線

引力場(chǎng)是一種設(shè)定的約束范圍，圖3.3是直線的引力場(chǎng)，一旦光標(biāo)進(jìn)入這個(gè)范圍，就被吸引到這條直線上，從而實(shí)現(xiàn)直線段端點(diǎn)或線內(nèi)點(diǎn)的捕捉。因?yàn)閲@端點(diǎn)的場(chǎng)域比較大，所以使光標(biāo)與端點(diǎn)的重合特別容易。圖3.3直線的引力場(chǎng)

10.動(dòng)態(tài)操作

動(dòng)態(tài)操作包括物體的拖動(dòng)、旋轉(zhuǎn)、縮放以及形變。

拖動(dòng)是指執(zhí)行拖動(dòng)物體的命令后，先用定位設(shè)備（如鼠標(biāo)）拾取某個(gè)要拖動(dòng)的對(duì)象，再按住鍵移動(dòng)光標(biāo)，則此物體將隨光標(biāo)的移動(dòng)而移動(dòng)，就好像光標(biāo)在拖動(dòng)物體一樣，當(dāng)移動(dòng)到滿(mǎn)意位置后予以確認(rèn)。

旋轉(zhuǎn)是指拾取或指定要旋轉(zhuǎn)的物體并給定旋轉(zhuǎn)中心后，當(dāng)移動(dòng)光標(biāo)時(shí)，物體將圍繞此旋轉(zhuǎn)中心隨光標(biāo)的移動(dòng)而旋轉(zhuǎn)，當(dāng)旋轉(zhuǎn)到滿(mǎn)意位置后予以確認(rèn)，如AutoCAD的ROTATE命令。

縮放需要指定縮放中心的位置，當(dāng)移動(dòng)光標(biāo)時(shí)，物體將以此縮放中心為基準(zhǔn)進(jìn)行放大（外移鼠標(biāo)時(shí)）或縮?。▋?nèi)移鼠標(biāo)時(shí)），如AutoCAD的SCALE命令。

形變是指在確定操作對(duì)象后，拖動(dòng)物體上的某個(gè)點(diǎn)或某條邊使物體產(chǎn)生形狀上的改變，如用AutoCAD的STRETCH拉伸命令可以加長(zhǎng)螺釘桿長(zhǎng)、可以將矩形拉伸成平行四邊形等。

3.3交互技術(shù)

1.定位技術(shù)定位技術(shù)用于指定一個(gè)坐標(biāo)。定位技術(shù)涉及維數(shù)，如一維、二維或三維；涉及分辨率，即定位精度，鍵盤(pán)可以提供無(wú)限高的分辨率，而定位設(shè)備提供的分辨率有限，可通過(guò)窗口到視區(qū)的坐標(biāo)變換技術(shù)提供分辨率，即將世界坐標(biāo)系中的某個(gè)區(qū)域放大，從而使屏幕上的一個(gè)區(qū)域與世界坐標(biāo)系中任意小的單位對(duì)應(yīng)起來(lái)；還涉及點(diǎn)是離散點(diǎn)還是連續(xù)點(diǎn)。

定位技術(shù)主要有以下兩種：

（1）鍵盤(pán)輸入坐標(biāo)值定位；

（2）鼠標(biāo)器、數(shù)字板或鍵盤(pán)光標(biāo)鍵控制光標(biāo)定位。

2.選擇技術(shù)

選擇技術(shù)主要有以下四種：

（1）鼠標(biāo)器或數(shù)字板控制光標(biāo)拾取圖形；

（2）鼠標(biāo)器、數(shù)字板或鍵盤(pán)光標(biāo)鍵控制光標(biāo)點(diǎn)取菜單項(xiàng)；

（3）鍵入名字、名字縮寫(xiě)、排列的唯一序號(hào)、標(biāo)識(shí)號(hào)等作選擇；

（4）用功能鍵作選擇。

3.拾取圖形技術(shù)

拾取圖形是常用的可變集選擇技術(shù)。在交互式圖形系統(tǒng)的增、刪、改操作中，都是以拾取整個(gè)圖形（如窗口拾?。┗蛞允叭D形的某一位置點(diǎn)為基礎(chǔ)的。拾取圖形的速度和精度又極大地影響著交互系統(tǒng)的質(zhì)量。

點(diǎn)的拾取、直線段的拾取、字符串的拾取是拾取圖形的基本技術(shù)，符號(hào)集、折線集、曲線、填充區(qū)域、三維圖形等的拾取可看作這些基本技術(shù)的運(yùn)用。

這里介紹點(diǎn)、直線段、字符串三種圖形元素的拾取技術(shù)。假定拾取點(diǎn)（光標(biāo)點(diǎn)）為P0（x0，y0）。

1）點(diǎn)的拾取

對(duì)于圖形中的一點(diǎn)P1（x1

，y1），該點(diǎn)的拾取區(qū)域（引力場(chǎng)）是以該點(diǎn)為圓心、以r（r是圖形系統(tǒng)設(shè)定的拾取精度）為半徑的一個(gè)圓形區(qū)域。如果拾取點(diǎn)P0（x0

，y0）滿(mǎn)足：

則拾取點(diǎn)P0落在P1點(diǎn)的拾取區(qū)域，即對(duì)P1點(diǎn)拾取成功。

2）直線段的拾取

若圖形中一條直線段的端點(diǎn)為P1（x1，y1）、P2（x2，y2），則該線段的拾取區(qū)域（引力場(chǎng)）為圖3.4中的虛線矩形所示，則

3）字符串的拾取

字符串的拾取方法是依次判斷每個(gè)字符的顯示區(qū)域（拾取區(qū)域，通常為矩形區(qū)域）是否包含拾取點(diǎn)，如點(diǎn)在多邊形內(nèi)的判斷。當(dāng)字符串中某一個(gè)字符的拾取區(qū)域包含拾取點(diǎn)時(shí)，表示對(duì)該字符串拾取成功。

為減少拾取圖形時(shí)的計(jì)算量，以便提高拾取速度，需要采取一些加速措施，如區(qū)域粗判法，即對(duì)要拾取的圖形先作其軸向矩形（也稱(chēng)為軸向包圍盒），若拾取點(diǎn)包含在此矩形內(nèi)，再作上述的各種圖形元素的判斷，否則跳過(guò)這些圖形。

4.菜單技術(shù)

菜單是一組功能列表、對(duì)象列表、數(shù)據(jù)列表或其他用戶(hù)可選擇實(shí)體的列表。菜單技術(shù)是常用的固定集選擇技術(shù)，在交互式圖形系統(tǒng)中被廣泛采用。

菜單由菜單項(xiàng)組成。菜單項(xiàng)的內(nèi)容通常為命令、命令的選項(xiàng)、字符、數(shù)據(jù)等。菜單項(xiàng)的表示方法有三種：字符式（見(jiàn)圖3.5）、圖符式（見(jiàn)圖3.6）和圖像（標(biāo)）式（見(jiàn)圖3.7）。

圖3.5字符式菜單

圖3.6圖符式菜單

圖3.7圖像式菜單（如工具欄菜單）

按照菜單的出現(xiàn)與消失，菜單結(jié)構(gòu)可分為固定式（見(jiàn)圖3.8（a））、翻頁(yè)式（見(jiàn)圖3.8（b））、滾動(dòng)式（見(jiàn)圖3.8（c））、拉簾式（包括下拉式，見(jiàn)圖3.8（d））、增長(zhǎng)式（見(jiàn)圖3.8（e））、彈出式（見(jiàn)圖3.8（f））和綜合式?；拘问交蚱渑缮问降慕Y(jié)合稱(chēng)為綜合式，如圖3.9所示的選項(xiàng)板菜單。

圖3.8菜單的基本形式

圖3.9選項(xiàng)板菜單

5.定向技術(shù)

定向就是在一個(gè)坐標(biāo)系中規(guī)定形體的一個(gè)方向，此時(shí)需要確定坐標(biāo)系的維數(shù)、分辨率、精度和反饋類(lèi)型。

定向技術(shù)有以下兩種：

（1）鍵入角度值或輸入兩點(diǎn)構(gòu)成向量，再由系統(tǒng)求取向量的方向角；

（2）用標(biāo)度盤(pán)或操縱桿控制方向角。

6.定路徑技術(shù)

定路徑是指在一定的時(shí)間或一定的空間內(nèi)，確定一系列的定位點(diǎn)和方向角。

雖然路徑可以由定位和定向這兩個(gè)更基本的交互任務(wù)組成，但由于定路徑中要考慮現(xiàn)實(shí)世界中的一個(gè)重要參數(shù)——時(shí)間，因此仍把它列為基本的交互任務(wù)。這時(shí)用戶(hù)關(guān)心的不是某一點(diǎn)及其方向，而是一系列的定位點(diǎn)和方向值及其次序。

7.定值技術(shù)

定值技術(shù)在交互過(guò)程中應(yīng)用很多，而且是必不可少的。

定值技術(shù)主要有以下三種：

（1）由鍵盤(pán)輸入數(shù)值；

（2）用光標(biāo)移動(dòng)屏幕上的標(biāo)度盤(pán)指針或刻度尺指針；

（3）用上下翻轉(zhuǎn)數(shù)字的計(jì)數(shù)器選擇數(shù)值。

8.文本技術(shù)

文本技術(shù)需要確定字符集（如ASCII碼字符集、中文國(guó)標(biāo)字符集、外文字符集等）及字符串的長(zhǎng)度。

實(shí)現(xiàn)文本的技術(shù)主要有以下兩種：

（1）鍵盤(pán)輸入字符；

（2）用菜單選擇字符。

9.橡皮筋技術(shù)

橡皮筋技術(shù)主要針對(duì)變形類(lèi)的要求，動(dòng)態(tài)地、連續(xù)地將變形過(guò)程表現(xiàn)出來(lái)，直到產(chǎn)生用戶(hù)滿(mǎn)意的結(jié)果為止。其中最基本的工作是動(dòng)態(tài)、連續(xù)地改變相關(guān)點(diǎn)的設(shè)備坐標(biāo)。

10.徒手畫(huà)技術(shù)

徒手畫(huà)技術(shù)是按鼠標(biāo)移動(dòng)軌跡畫(huà)圖的技術(shù)，用于實(shí)現(xiàn)用戶(hù)的任意畫(huà)圖要求。配合數(shù)字書(shū)寫(xiě)板，徒手畫(huà)技術(shù)可用于在線手繪草圖的輸入。

11.拖動(dòng)技術(shù)

拖動(dòng)技術(shù)是將形體在空間移動(dòng)的過(guò)程動(dòng)態(tài)地、連續(xù)地表示出來(lái)，直至滿(mǎn)足用戶(hù)的位置要求為止。

3.4用戶(hù)接口

用戶(hù)接口是用戶(hù)與計(jì)算機(jī)、智能手機(jī)、儀器等交互作用的界面。一個(gè)良好的用戶(hù)接口可以大大縮短人與計(jì)算機(jī)之間的距離，使得計(jì)算機(jī)易學(xué)、易理解、易用，從而提高工作效率和人們使用計(jì)算機(jī)的水平。現(xiàn)在，在軟件系統(tǒng)的設(shè)計(jì)中，人們?cè)絹?lái)越重視用戶(hù)接口的設(shè)計(jì)與開(kāi)發(fā)，如智能手機(jī)終端軟件APP的開(kāi)發(fā)涉及大量人機(jī)界面。

3.4.1用戶(hù)接口的設(shè)計(jì)目標(biāo)

1.提高學(xué)習(xí)速度

學(xué)習(xí)速度是一個(gè)與用戶(hù)熟練掌握?qǐng)D形交互系統(tǒng)的使用方法所花時(shí)間有關(guān)的量，是一個(gè)相對(duì)量。

2.提高使用速度

使用速度是一個(gè)與那些熟練的操作員用系統(tǒng)完成某個(gè)特定任務(wù)所需時(shí)間有關(guān)的量。

3.降低操作失誤率

操作失誤率是指每次交互操作的平均失誤次數(shù)。

4.增強(qiáng)記憶

交互系統(tǒng)應(yīng)能幫助用戶(hù)在長(zhǎng)期不使用該系統(tǒng)后，一旦接觸，就能盡快地回憶起各個(gè)交互操作。

5.增強(qiáng)對(duì)潛在用戶(hù)的吸引力

增強(qiáng)對(duì)潛在用戶(hù)的吸引力是市場(chǎng)方面的一個(gè)目標(biāo)。

3.4.2用戶(hù)接口的設(shè)計(jì)步驟

1.概念設(shè)計(jì)

概念設(shè)計(jì)定義了圖形系統(tǒng)中必須由用戶(hù)掌握的基本概念，包括對(duì)象定義、對(duì)象屬性定義、對(duì)象關(guān)系定義和對(duì)象操作定義。例如，在簡(jiǎn)單的文字編輯軟件中，操作對(duì)象是字符、行和文件，文件的屬性是文件名。

2.功能設(shè)計(jì)

功能設(shè)計(jì)也稱(chēng)為語(yǔ)義設(shè)計(jì)，它規(guī)定了用戶(hù)接口的詳細(xì)功能。對(duì)于每個(gè)操作，要說(shuō)明需要什么參數(shù)、會(huì)產(chǎn)生什么結(jié)果、會(huì)給出什么反饋、有錯(cuò)誤時(shí)會(huì)出現(xiàn)什么錯(cuò)誤以及如何處理可能產(chǎn)生的錯(cuò)誤等。

3.交互順序設(shè)計(jì)

交互順序設(shè)計(jì)也稱(chēng)為語(yǔ)法設(shè)計(jì)，它定義輸入和輸出的順序。對(duì)于輸入，從語(yǔ)法上講，是按一定的規(guī)則將各個(gè)詞組組成一個(gè)完整的句子，詞組可以看成通過(guò)交互技術(shù)輸入到系統(tǒng)中的不可分割的最小單元。

4.聯(lián)結(jié)設(shè)計(jì)（詞法設(shè)計(jì)）

聯(lián)結(jié)設(shè)計(jì)也稱(chēng)為詞法設(shè)計(jì)，它定義如何由單詞形成一個(gè)個(gè)有意義的詞組。對(duì)于輸入，單詞可以看成聯(lián)結(jié)到系統(tǒng)上的各種輸入設(shè)備，聯(lián)結(jié)設(shè)計(jì)就是選擇或設(shè)計(jì)前面介紹過(guò)的交互技術(shù)；對(duì)于輸出，單詞可以看成圖形軟件庫(kù)提供的各種幾何形狀（如直線、圓、字符）以及它們的屬性（如色彩、字體），聯(lián)結(jié)設(shè)計(jì)就是把這些圖素及其屬性組合起來(lái)，形成圖標(biāo)和其他符號(hào)。

3.4.3用戶(hù)接口的風(fēng)格

1.所見(jiàn)即所得

用戶(hù)與接口需要交互什么內(nèi)容，圖形系統(tǒng)就會(huì)及時(shí)在屏幕上顯示相應(yīng)內(nèi)容的圖像。交互式圖形系統(tǒng)都具有所見(jiàn)即所得的風(fēng)格。

2.直接操作

直接操作是指將可以操作的對(duì)象、對(duì)象屬性、對(duì)象關(guān)系以文字或圖標(biāo)形式在屏幕上顯示出來(lái)，用鼠標(biāo)器在它們上面進(jìn)行某個(gè)動(dòng)作，達(dá)到實(shí)行某種操作的目的。這樣，無(wú)需用選菜單或鍵入命令這種傳統(tǒng)的方式來(lái)實(shí)現(xiàn)某個(gè)操作，而是將操作隱含在各種動(dòng)作中。

3.圖標(biāo)化用戶(hù)界面

圖標(biāo)是操作對(duì)象、對(duì)象屬性、對(duì)象關(guān)系、動(dòng)作或某些概念的圖形表示。用戶(hù)接口的設(shè)計(jì)者可以選擇文字表示某個(gè)概念，也可以用圖標(biāo)表示這個(gè)概念，但精心設(shè)計(jì)的圖標(biāo)比文字更易于識(shí)別其含義（如用剪刀表示圖形的剪切、用橡皮表示圖形的刪除等）。

4.其他對(duì)話形式

還有一些既適合圖形交互接口，又適合其他軟件的對(duì)話形式，如菜單、命令語(yǔ)言、自然語(yǔ)言理解、問(wèn)答式對(duì)話等。

（1）菜單：廣泛應(yīng)用于圖形系統(tǒng)和非圖形系統(tǒng)。

（2）命令語(yǔ)言：一種與計(jì)算機(jī)實(shí)現(xiàn)交互作用的傳統(tǒng)方法。

（3）自然語(yǔ)言理解：交互系統(tǒng)的最高目標(biāo)。

（4）問(wèn)答對(duì)話：其過(guò)程是：計(jì)算機(jī)在屏幕上顯示出問(wèn)題，等待用戶(hù)回答，用戶(hù)可用輸入設(shè)備輸入答案（通常答案是受限制的，如圓半徑只能是正值）。

3.4.4用戶(hù)接口的設(shè)計(jì)原則

1.一致性原則

（1）所有同類(lèi)界面元素在相同的應(yīng)用環(huán)境下，在視覺(jué)上具有一致的界面外觀。

（2）相似場(chǎng)景下的界面操作方式保持一致，同一操作行為應(yīng)保持視覺(jué)的一致。

（3）界面外觀與用戶(hù)的預(yù)測(cè)一致，視覺(jué)元素的外觀及其操作結(jié)果應(yīng)與用戶(hù)的心理認(rèn)知相符等。

2.簡(jiǎn)潔性原則

（1）界面中應(yīng)使用盡可能少的元素，不提供與當(dāng)前任務(wù)無(wú)關(guān)的信息，以減輕視覺(jué)負(fù)擔(dān)。

（2）界面信息采用簡(jiǎn)明的文字表述，清晰易懂、內(nèi)涵豐富，易于理解和記憶，如使用的圖標(biāo)要具有個(gè)性、盡量表達(dá)功能含義。

（3）界面操作應(yīng)減少冗余的操作步驟，如窗口層次要少，一般不超過(guò)3層，軟件功能盡量在主窗口上，并在菜單、工具欄中同時(shí)體現(xiàn)。

3.免干擾性原則

（1）明確用戶(hù)在特定界面中的首要任務(wù)和目標(biāo)，盡可能避免界面出現(xiàn)視覺(jué)干擾。

（2）要對(duì)菜單、控件、按鈕和命令文本的可用性進(jìn)行控制，使不允許操作的菜單、控件、按鈕和命令文本禁用（如置灰）或隱藏。

4.反饋性原則

（1）最低級(jí)的反饋（對(duì)應(yīng)于聯(lián)結(jié)設(shè)計(jì)）：用戶(hù)在交互設(shè)備上的每個(gè)動(dòng)作都應(yīng)立即產(chǎn)生明顯的反饋。

（2）二級(jí)反饋（對(duì)應(yīng)于順序設(shè)計(jì)）：當(dāng)系統(tǒng)接受輸入語(yǔ)言中的每個(gè)詞組（如命令、位置、操作對(duì)象等）時(shí)，應(yīng)提供反饋，被拾取的物體或被選中的菜單項(xiàng)要著重顯示，使用戶(hù)知道其動(dòng)作已被接受。

（3）功能級(jí)反饋（對(duì)應(yīng)于功能設(shè)計(jì)）：這是最有用且最受用戶(hù)歡迎的一種反饋形式。它告訴用戶(hù)，其發(fā)出的命令已經(jīng)執(zhí)行完了。

5.容錯(cuò)性原則

（1）界面應(yīng)提供撤銷(xiāo)（UNDO）及恢復(fù)（REDO）操作，使得用戶(hù)可以返回上一步操作或重新進(jìn)行選擇，系統(tǒng)配置界面應(yīng)提供“恢復(fù)初始設(shè)置”選項(xiàng)讓用戶(hù)敢于嘗試。

（2）應(yīng)使用單選、多選或下拉列表等合適的選擇控件，提供有代表性的默認(rèn)選項(xiàng)以及相應(yīng)的輸入幫助，方便用戶(hù)準(zhǔn)確輸入信息。

（3）對(duì)用戶(hù)的輸入和選擇等操作，界面應(yīng)提供校驗(yàn)功能進(jìn)行實(shí)時(shí)判斷，提示錯(cuò)誤所在，并提供有用的恢復(fù)建議，幫助用戶(hù)及時(shí)更正錯(cuò)誤輸入。

6.面向多層次用戶(hù)原則

交互式圖形系統(tǒng)要面向各種層次的用戶(hù)，使毫無(wú)經(jīng)驗(yàn)的新手、經(jīng)驗(yàn)不多的用戶(hù)以及熟練用戶(hù)都能找到適合自己的交互手段。

使系統(tǒng)能容納多層次用戶(hù)的方法是：提供加速技術(shù)、增加提示信息、提供幫助信息、提供可擴(kuò)展功能、隱藏復(fù)雜功能等。

把復(fù)雜功能隱藏起來(lái)不讓使用是新手們學(xué)習(xí)系統(tǒng)基本功能很好的方法。這樣不用指定選項(xiàng)、不用學(xué)習(xí)不常用的特殊命令、不用經(jīng)歷復(fù)雜的啟動(dòng)過(guò)程就可以開(kāi)始實(shí)際的工作。有些命令常常會(huì)有很多可選參數(shù)項(xiàng)，對(duì)于這種命令，就需要簡(jiǎn)化，提供合理的默認(rèn)值代替任選參數(shù)項(xiàng)。隱藏復(fù)雜命令的另一個(gè)策略是：復(fù)雜的、高級(jí)的命令只有通過(guò)鍵盤(pán)或功能鍵才能執(zhí)行。這樣可以保持菜單更小、系統(tǒng)更簡(jiǎn)單。

3.5交互式圖形軟件的界面構(gòu)成及界面元素

圖形軟件與人的信息交換是通過(guò)界面進(jìn)行的，界面的設(shè)計(jì)除了滿(mǎn)足前面介紹的一般原則外，界面的易用性和美觀性對(duì)圖形軟件來(lái)說(shuō)也非常重要。（1）易用性。易用性主要涉及操作流程設(shè)計(jì)，即通過(guò)設(shè)計(jì)工作流程使用戶(hù)的工作量減小、工作效率提高，如使用功能綜合的對(duì)話框、設(shè)置缺省值、提供導(dǎo)航功能等。

（2）美觀性。美觀性包括界面布局設(shè)計(jì)、顏色設(shè)計(jì)等。界面布局設(shè)計(jì)體現(xiàn)在各視區(qū)劃分的比例、各界面元素的大小及位置排列等方面，做到界面的布局合理、協(xié)調(diào)。

圖形軟件的界面包括主界面和子界面。

3.5.1圖形軟件主界面

主界面（主窗口）是軟件系統(tǒng)的常駐界面，作用是實(shí)現(xiàn)系統(tǒng)所有功能模塊的調(diào)用。主界面布局因軟件不同而不同，主要按照各區(qū)域功能不同進(jìn)行劃分，以圖3.10中的AutoCAD圖形軟件的主界面為例。

圖3.10AutoCAD圖形軟件主界面

圖3.11為編者主持研制的一款工程軟件——通信車(chē)無(wú)線系統(tǒng)電磁兼容仿真軟件的主界面，包含有標(biāo)題欄、菜單欄、工具欄、主視區(qū)（圖形顯示區(qū)）、控制區(qū)（任務(wù)區(qū)）、信息輸出區(qū)等主要組成部分。

圖3.11某工程分析軟件主界面

3.5.2圖形軟件子界面及其主要組成元素

子界面用于軟件中功能模塊的人機(jī)交互操作，實(shí)現(xiàn)形式主要為對(duì)話框。對(duì)話框分為模式對(duì)話框（常用）和非模式對(duì)話框兩種。模式對(duì)話框是指在沒(méi)有關(guān)閉前不可切換到擁有該對(duì)話框的應(yīng)用程序的其他窗口；而非模式對(duì)話框在打開(kāi)后不影響用戶(hù)的任何操作。

圖3.12為AutoCAD圖形軟件的兩個(gè)子界面，圖3.13為圖3.11所示工程軟件的子界面。

子界面（對(duì)話框）中的元素有十幾種，主要如下：

（1）標(biāo)簽：用于子界面功能提示，如圖3.12、圖3.13所示。

（2）選項(xiàng)卡：用于功能切換，如圖3.12所示。

（3）靜態(tài)文本項(xiàng)：用于顯示靜態(tài)文字，是不可選擇、編輯的，如提示信息、警告信息。

（4）圖像項(xiàng)：用于顯示圖像，是不可選擇、編輯的，其作用是說(shuō)明、提示，如圖3.13所示。

（5）文本編輯框：用于輸入和編輯文字，如圖3.13所示。

（6）列表框：用于從一組項(xiàng)目中選擇一項(xiàng)，如圖3.12中的圖案選擇框。

（7）組合框：用于從一組相關(guān)