計算機圖形學 課件 許社教 第1-4章 緒論、圖形處理中的幾何問題-圖形變換與裁剪

第1章緒論1.1計算機圖形學的概念1.2計算機圖形學的研究內容1.3計算機圖形系統(tǒng)的組成1.4點陣圖形顯示器簡介1.5計算機圖形學的應用

1.1計算機圖形學的概念

計算機圖形學起源于20世紀50年代。1950年，第一臺圖形顯示器旋風Ⅰ號誕生于美國麻省理工學院。之后，H.JosephGerber設計了第一臺平臺式繪圖機。1959年，Calcomp公司研制了第一臺滾筒式繪圖機。

什么是計算機圖形學？國際標準化組織ISO對于計算機圖形學（ComputerGraphics，CG）的定義為：利用計算機將數(shù)據(jù)轉換為圖形，并在繪圖設備上進行圖形顯示或繪制的一門學科。

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

1.2計算機圖形學的研究內容

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

計算機圖形學的研究內容從大的方面分為硬件、軟件、圖形理論與算法三個方面。

1.硬件研究

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

2.軟件研究

軟件研究是指研究圖形軟件的設計與使用、各種圖形軟件的開發(fā)研究以及圖形軟件的標準化。

3.圖形理論與算法研究

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

解決某一問題的算法可能有多個，評價算法優(yōu)劣的指標是時間復雜度和空間復雜度。前者要求計算量小、運算速度快，后者要求占用存儲空間少。主要研究內容如下：

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

該研究內容包括直線、圓弧、字符、二次曲線、圖案填充等圖形元素的生成算法。

2）圖形變換及裁剪

圖形變換是指對圖形進行比例、平移、旋轉、錯切、反射等幾何變換和對物體進行各種投影變換（正投影變換、軸測投影變換、透視投影變換）；圖形裁剪包括二維開窗裁剪、三維取景裁剪。

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

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

4）消隱處理

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

圖1.1自由曲面示例

5）二維、三維造型技術

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

圖1.2焊片視圖的二維造型過程圖1.3支架的三維造型結果

6）真實感圖形（逼真圖像）的生成

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

圖1.4物體真實感圖形

7）科學計算可視化（圖形可視化）

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

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

8）三維重建技術

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

9）3D（三維）打印模型處理技術

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

10）圖形數(shù)據(jù)結構及圖形數(shù)據(jù)庫

圖形數(shù)據(jù)結構及圖形數(shù)據(jù)庫是解決復雜圖形問題（尤其是三維問題）的關鍵，它與算法一樣重要。

11）分形幾何

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

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

設

N

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

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

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

圖1.7

12）計算機動畫生成

計算機動畫生成是指研究如何實時（快速）、方便、自動地生成場景中的物體和圖形，以及動畫的播放技術。

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

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

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

（1）主機。

（2）外存儲器。

（3）圖形輸入設備。

圖1.8為幾種圖形輸入設備。

（4）圖形輸出設備。

圖1.8圖形輸入設備

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

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

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

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

1.4點陣圖形顯示器簡介

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

1.幾個概念

1）像素

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

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

2）屏幕分辨率

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

3）背景

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

4）前景

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

2.點陣圖形顯示器的組成

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

圖形監(jiān)視器用于觀察圖形的部件，其結構與電視機類似。

2）幀緩沖存儲器（視頻緩存）

幀緩沖存儲器的邏輯結構與屏幕顯示網(wǎng)格對應，其作用是暫時保存屏幕上的圖形。新生成的圖形以及圖形的刷新都要使用幀緩沖存儲器，其主要技術指標是容量。

容量可進行如下估算：

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

3）顯示控制器

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

1.5計算機圖形學的應用

與手工繪圖相比，計算機繪圖具有提高繪圖的速度、繪圖的準確度、可進行屏幕模擬與動畫顯示的突出優(yōu)點。計算機圖形學的應用領域很廣，幾乎在各個行業(yè)都有應用。

1.繪制工程圖樣

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

圖1.10虎鉗裝配圖

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

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

圖1.11CAD的應用

圖1.12ＣＡＭ的應用

3.計算機藝術設計

計算機藝術設計包括曲線曲面藝術造型、分形圖案設計等。圖1.13為一些計算機藝術設計圖例。

圖1.13計算機藝術設計圖例

4.虛擬現(xiàn)實（VR）/增強現(xiàn)實（AR）

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

VR/AR越來越多地應用于各個行業(yè)，如教育、培訓與訓練、醫(yī)療、設計、娛樂、工業(yè)仿真等。圖1.14為VR/AR的應用。圖1.14VR/AR的應用

5.計算機輔助教學（CAI）

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

2.1圖形坐標系

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

圖2.1坐標系使用的邏輯關系

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

圖2.2右手坐標系的判斷方法

2.1.1世界坐標系

世界坐標系是用戶為繪圖而建立的初始直角坐標系，

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

2.1.2局部坐標系

局部坐標系是用戶在世界坐標系或當前的坐標系中定

義的直角坐標系，為右手坐標系。局部坐標系的坐標原點、坐標軸的方位是任意的。在某些圖形系統(tǒng)中，把局部坐標系稱為用戶坐標系。設立局部坐標系是為了便于作圖。例如，在三維繪圖中，利用局部坐標系可以把較為復雜的三維作圖問題轉化為二維作圖問題。圖2.3為局部坐標系的應用。

圖2.3局部坐標系的應用

2.1.3觀察坐標系

觀察坐標系是以視點為坐標原點的三維左手(或右手)直角坐標系，其中z軸方向為視點與世界坐標系原點(默認情況)或模型上點的連線方向，xy平面(觀察平面，即投影平面)與z軸垂直，如圖2.4所示。

觀察坐標系取為左手系的原因在于:當把觀察平面作為屏幕時，z軸正方向朝向顯示器里的方向符合我們的視覺習慣，越向里表示離我們越遠，z值也就越大。

圖2.4觀察坐標系與世界坐標系

2.1.4設備坐標系

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

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

圖2.5屏幕坐標系

2.1.5規(guī)范化設備坐標系

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

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

2.2幾何元素的定義及特點

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

在自由曲線和曲面的描述中，常用以下三種類型的點：

(1)控制點:用來確定曲線和曲面的位置與形狀，而相應的曲線和曲面不一定經過的點?？刂泣c用于構造逼近曲線、逼近曲面。

(2)型值點:用來確定曲線和曲面的位置與形狀，而相應的曲線和曲面一定經過的點。型值點用于構造插值曲線、插值曲面。

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

2.邊(線)

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

3.環(huán)

環(huán)是由有序的有向邊(直線段或曲線段)組成的封閉邊界。環(huán)有內、外之分，確定面的最大外邊界的環(huán)稱為外環(huán)，其邊(或頂點)按逆時針方向排序；而把確定面中內孔或凸臺邊界的環(huán)稱為內環(huán)，其邊(或頂點)按順時針方向排序?；谶@種定義，在面上沿一個環(huán)前進，其左側總是面內，右側總是面外。

4.面

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

5.體

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

6.形體定義的層次結構

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

2.3平面圖形的幾何性質

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

2.三角形的面積、質心和質量因子的計算

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

其中，ｐ為三角形周長的一半，a、b、c為三邊的邊長。

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

圖2.7不同三角形的質量因子α的值

3.平面凸四邊形的面積、質心和質量因子的計算

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

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

2.點與直線段的位置判斷

點與直線之間的位置關系用于點是否在直線上、三點是否共線以及三點是否能構成三角形的判斷等方面。

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

3.點與平面的位置判斷

點與平面之間的位置關系用于四點共面、兩相鄰三角形是否可合并構成平面四邊形的判斷等方面。

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

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

4.點在多邊形內部的判斷

判斷平面上一個點是否包含在同平面的一個多邊形內有多種算法，經典方法有叉積判斷法、夾角之和檢驗法和交點計數(shù)檢驗法。

1)叉積判斷法

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

(i=1，2，…，n)的符號相同。特殊地，當Vi×Vi+1=0(點P0在多邊形的邊上或邊的延長線上)時，認為點在多邊形外。

圖2.8叉積判斷法

2)夾角之和檢驗法

如圖2.9所示，假設平面上有點P0和多邊形P1P2P3

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

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

1)，則它可通過下列公式計算：

αi的正負號由Vi×Vi+1的正負決定。

圖2.9夾角之和檢驗法

3)交點計數(shù)檢驗法

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

求射線與多邊形相交時的交點個數(shù)。

如果交點個數(shù)為奇數(shù)，則點在多邊形之內；如果交點

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

但當圖2.10(b)中的射線f、g、h、i、j均通過多邊形的頂點、圖2.10(a)中射線ｋ與邊重合時，交點計數(shù)應特殊處理。如射線

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

圖2.10交點計數(shù)檢驗法

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

圖2.11交點計數(shù)方法

5.點在多面體內的判斷

1)點在凸多面體內的判斷

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

2)點在一般多面體內的判斷

點在一般多面體內的判斷類似于點在多邊形內部判斷的交點計數(shù)法。

2.5幾何元素之間的求交計算

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

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

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

1)快速排斥判斷

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

2)跨立判斷

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

圖2.12跨立驗證

3)求取交點

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

2.直線段與平面的求交

1)矢量求解方法

考慮直線段與無界平面的求交問題，如圖2.13所示。

給定直線段的兩個端點，則直線段方程可表示為

給定平面上三個點，則平面方程可表示為

圖2.13直線段與平面的求交

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

其中：

2.14直線與空間平面的交點

3.平面與平面的求交

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

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

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

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

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

(3)將所有交點依次按x、y、z的大小進行排序，即先按x坐標排序，然后對x坐標相同的交點再按y坐標排序，最后對x、y相同的交點按z坐標排序；

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

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

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

設兩個一般多邊形分別記為A和B，參見圖2.15、圖2.16，算法步驟如下：

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

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

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

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

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

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

圖2.16面面求交奇異情況

4.矢量表示點批判學習案例

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

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

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

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

2.簡單多邊形頂點凸凹性的定義、凸角與凹角、凸多邊形與凹多邊形

設V1，…，Vn是一個簡單多邊形。對于任一頂點Vi(i=1，2，3，…，n)，若線段Vi

-

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

對簡單單連通多邊形而言，所有頂點都為凸頂點的多邊形稱為凸多邊形，至少有一個頂點為凹頂點的多邊形稱為凹多邊形。

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

多邊形的方向有逆時針方向和順時針方向之分。對簡單單連通多邊形而言，沿觀察方向看去，若觀察者按頂點序列V1V2…VnVn+1繞多邊形一周時，該多邊形所圍的有界區(qū)域總在左邊，則稱該多邊形為逆時針方向，如圖2.19(a)所示；否則，稱其為順時針方向，如圖2.19(b)所示。

圖2.19多邊形的方向

4.頂點的叉積

2.6.2多邊形凸凹性的判斷

1.多邊形方向的判斷

多邊形方向的判斷方法為極值頂點法。多邊形頂點中坐標值為xmin或xmax或ymin或ymax的頂點稱為極值頂點，極值頂點必為凸頂點。

極值頂點法如下：

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

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

(3)若叉積值nz>0，則多邊形的方向為逆時針方向；若叉積值nz＜0，則多邊形的方向為順時針方向。

2.多邊形頂點凸凹性的判斷

假定多邊形V1V2…Vn的方向為逆時針方向，這是常見的情況。多邊形頂點凸凹性的判斷方法有頂點叉積法、平移旋轉法等。這里介紹較為簡單的頂點叉積法。

對于逆時針方向的多邊形，任一頂點Vi凸凹性判斷的頂點叉積法如下：

(1)計算頂點Vi的叉積。

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

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

圖2.20逆時針方向多邊形的叉積示意圖

3.多邊形凸凹性的判斷

經過頂點凸凹性判斷后，若多邊形所有頂點都為凸頂點，則該多邊形是凸多邊形；否則為凹多邊形。

經上述判斷，圖2.20所示的多邊形為凹多邊形。

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

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

圖2.21凸多邊形的三角分解過程

2.7.2凹多邊形的分解

參見圖2.22，凹多邊形分解的算法如下：

圖2.22凹多邊形的分解

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

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

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

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

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

此算法簡單，但缺點是分解結果與多邊形頂點的排序有關，分解不具有唯一性。

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

1.非自交多邊形

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

圖2.23自交多邊形

圖2.24非自交多邊形NIP

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

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

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

圖2.26NIP三角分解過程

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

3.基于單調鏈的凸分解

基于單調鏈的凸分解的目標是將帶內環(huán)多邊形分解為凸多邊形。

1)單調鏈、尖點的概念

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

圖2.28單調鏈

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

尖點的定義:任意多邊形中，單調鏈的端點稱為尖點。對于相對于y軸的單調鏈，其上端點定義為上尖點，其下端點定義為下尖點。如圖2.29中，S1、S3為上尖點，S2、S4為下尖點。

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

圖2.29上、下尖點與上、下單調鏈

2)凸分解算法

參見圖2.30，基于單調鏈的凸分解算法主要包括三個步驟：

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

(2)通過分裂和組合單調鏈，逐次拆分出單調多邊形。由兩條單調鏈組成的多邊形稱為單調多邊形，圖(a)的多邊形可拆分如圖(b)所示的4個單調多邊形。

(3)將單調多邊形分解為凸多邊形，如圖(c)所示。可利用前述的凹多邊形分解算法進行分解。

圖2.30基于單調鏈的凸分解過程

2.7.4Delaunay三角剖分

蘇聯(lián)數(shù)學家Delaunay于1934年證明，對于散亂點集，必定存在且僅存在一種三角剖分算法，使得剖分得到的所有三角形的最小內角之和最大(“最小角最大原則”)，這種算法稱為Delaunay三角剖分，簡稱DT剖分。Delaunay三角剖分算法是最著名的三角化網(wǎng)格生成方法，因為它具有“三角剖分最小內角之和為最大”的性質，從而保證了網(wǎng)格整體質量最優(yōu)，稱為最優(yōu)三角剖分。DT剖分可用于數(shù)字地形建模、工程網(wǎng)格劃分、人臉圖像結構建模等。

1.Delaunay三角剖分的性質

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

1)最小內角最大準則

對一個凸四邊形進行劃分時，該準則要求對角線兩側兩個三角形中的最小內角為最大。沿短對角線進行劃分可滿足最小內角最大準則，如圖2.31所示。

圖2.31最小內角最大原則

2)空外接圓(空外接球)準則

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

如圖2.32所示，左圖三點組成了Delaunay三角形，因其外接圓內即虛線所示部分再無其他結點，而右圖三角形不滿足空外接圓準則，故不是Delaunay三角形。

圖2.32Delaunay三角形空外接圓準則

3)局部性

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

圖2.33Delaunay三角剖分的局部性

2.Delaunay三角剖分算法

參見圖2.34，算法主要步驟如下：

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

(2)通過增加或刪除邊、進行邊替換、修改第一邊的編號等操作對剩余部分形成新的當前多邊形；

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

2.7.5用于三角剖分的前沿推進法

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

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

三點前沿推進法以兩條相鄰的前沿邊為基礎，檢驗該兩邊的夾角大小，若其夾角是鈍角或較大的銳角，則在角的平分線上生成一點，該點與兩條前沿邊的三個端點相連生成兩個三角形；若其夾角為不大的銳角或夾角雖大但邊短能形成質量較好的三角形，則將兩條前沿邊的非公共點直接相連，生成一個三角形。三點前沿推進法簡單，每步操作都是有效的，故剖分效率較高。

1.前沿推進法

前沿推進法的主要過程如下：

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

圖2.35初始生成波

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

圖2.36波的凝聚與膨脹

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

圖2.37波的分解

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

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

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

圖2.38第3章圖形軟件設計技術3.1軟件的模塊化設計3.2交互任務3.3交互技術3.4用戶接口3.5交互式圖形軟件的界面構成及界面元素3.

6圖形軟件標準3.7OpenGL系統(tǒng)及其應用開發(fā)

3.1軟件的模塊化設計

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

軟件模塊化必須遵循軟件工程學的基本原則，其核心問題如下：

（1）模塊劃分與調用。

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

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

①設計功能獨立單一的模塊；

②控制使用全局數(shù)據(jù)；

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

耦合度依賴以下幾個因素：

①一個模塊對另一個模塊的調用方式；

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

③一個模塊施加到另一個模塊的控制的多少；

④模塊之間接口的復雜程度。

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

圖3.1模塊化設計成本曲線

3.2交互任務

交互任務是指用戶輸入到計算機的一個單元信息。交互任務分為基本交互任務和組合交互任務兩類。組合交互任務是由基本交互任務結合而成的，有三種主要的組合交互任務：對話框、構造和動態(tài)操作。對話框用來指定信息表中的多個項；構造用來產生需要有位置約束的形體；動態(tài)操作用來修改已有的幾何形體的形狀，調整形體之間的相對位置。

1.定位

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

2.選擇

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

完成選擇任務有基于名字（或標識符）和位置（坐標點）選擇兩種情況。

3.文本

文本任務是指輸入一個字符串到字處理器中。

4.定值

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

5.定向

定向即在指定的坐標系中確定形體的方向。

6.定路徑

定路徑是一系列定位和定向任務的結合。

7.三維交互

三維交互任務涉及定位、選擇和旋轉。

8.對話框

對話框多在交互過程中需要從一個選擇集中選擇多個元素時使用。

9.構造

實現(xiàn)構造這類任務的主要方式有橡皮筋方式和約束方式。

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

圖3.2用橡皮筋方式畫折線

引力場是一種設定的約束范圍，圖3.3是直線的引力場，一旦光標進入這個范圍，就被吸引到這條直線上，從而實現(xiàn)直線段端點或線內點的捕捉。因為圍繞端點的場域比較大，所以使光標與端點的重合特別容易。圖3.3直線的引力場

10.動態(tài)操作

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

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

旋轉是指拾取或指定要旋轉的物體并給定旋轉中心后，當移動光標時，物體將圍繞此旋轉中心隨光標的移動而旋轉，當旋轉到滿意位置后予以確認，如AutoCAD的ROTATE命令。

縮放需要指定縮放中心的位置，當移動光標時，物體將以此縮放中心為基準進行放大（外移鼠標時）或縮?。▋纫剖髽藭r），如AutoCAD的SCALE命令。

形變是指在確定操作對象后，拖動物體上的某個點或某條邊使物體產生形狀上的改變，如用AutoCAD的STRETCH拉伸命令可以加長螺釘桿長、可以將矩形拉伸成平行四邊形等。

3.3交互技術

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

定位技術主要有以下兩種：

（1）鍵盤輸入坐標值定位；

（2）鼠標器、數(shù)字板或鍵盤光標鍵控制光標定位。

2.選擇技術

選擇技術主要有以下四種：

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

（2）鼠標器、數(shù)字板或鍵盤光標鍵控制光標點取菜單項；

（3）鍵入名字、名字縮寫、排列的唯一序號、標識號等作選擇；

（4）用功能鍵作選擇。

3.拾取圖形技術

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

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

這里介紹點、直線段、字符串三種圖形元素的拾取技術。假定拾取點（光標點）為P0（x0，y0）。

1）點的拾取

對于圖形中的一點P1（x1

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

，y0）滿足：

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

2）直線段的拾取

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

3）字符串的拾取

字符串的拾取方法是依次判斷每個字符的顯示區(qū)域（拾取區(qū)域，通常為矩形區(qū)域）是否包含拾取點，如點在多邊形內的判斷。當字符串中某一個字符的拾取區(qū)域包含拾取點時，表示對該字符串拾取成功。

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

4.菜單技術

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

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

圖3.5字符式菜單

圖3.6圖符式菜單

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

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

圖3.8菜單的基本形式

圖3.9選項板菜單

5.定向技術

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

定向技術有以下兩種：

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

（2）用標度盤或操縱桿控制方向角。

6.定路徑技術

定路徑是指在一定的時間或一定的空間內，確定一系列的定位點和方向角。

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

7.定值技術

定值技術在交互過程中應用很多，而且是必不可少的。

定值技術主要有以下三種：

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

（2）用光標移動屏幕上的標度盤指針或刻度尺指針；

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

8.文本技術

文本技術需要確定字符集（如ASCII碼字符集、中文國標字符集、外文字符集等）及字符串的長度。

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

（1）鍵盤輸入字符；

（2）用菜單選擇字符。

9.橡皮筋技術

橡皮筋技術主要針對變形類的要求，動態(tài)地、連續(xù)地將變形過程表現(xiàn)出來，直到產生用戶滿意的結果為止。其中最基本的工作是動態(tài)、連續(xù)地改變相關點的設備坐標。

10.徒手畫技術

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

11.拖動技術

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

3.4用戶接口

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

3.4.1用戶接口的設計目標

1.提高學習速度

學習速度是一個與用戶熟練掌握圖形交互系統(tǒng)的使用方法所花時間有關的量，是一個相對量。

2.提高使用速度

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

3.降低操作失誤率

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

4.增強記憶

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

5.增強對潛在用戶的吸引力

增強對潛在用戶的吸引力是市場方面的一個目標。

3.4.2用戶接口的設計步驟

1.概念設計

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

2.功能設計

功能設計也稱為語義設計，它規(guī)定了用戶接口的詳細功能。對于每個操作，要說明需要什么參數(shù)、會產生什么結果、會給出什么反饋、有錯誤時會出現(xiàn)什么錯誤以及如何處理可能產生的錯誤等。

3.交互順序設計

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

4.聯(lián)結設計（詞法設計）

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

3.4.3用戶接口的風格

1.所見即所得

用戶與接口需要交互什么內容，圖形系統(tǒng)就會及時在屏幕上顯示相應內容的圖像。交互式圖形系統(tǒng)都具有所見即所得的風格。

2.直接操作

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

3.圖標化用戶界面

圖標是操作對象、對象屬性、對象關系、動作或某些概念的圖形表示。用戶接口的設計者可以選擇文字表示某個概念，也可以用圖標表示這個概念，但精心設計的圖標比文字更易于識別其含義（如用剪刀表示圖形的剪切、用橡皮表示圖形的刪除等）。

4.其他對話形式

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

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

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

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

（4）問答對話：其過程是：計算機在屏幕上顯示出問題，等待用戶回答，用戶可用輸入設備輸入答案（通常答案是受限制的，如圓半徑只能是正值）。

3.4.4用戶接口的設計原則

1.一致性原則

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

（2）相似場景下的界面操作方式保持一致，同一操作行為應保持視覺的一致。

（3）界面外觀與用戶的預測一致，視覺元素的外觀及其操作結果應與用戶的心理認知相符等。

2.簡潔性原則

（1）界面中應使用盡可能少的元素，不提供與當前任務無關的信息，以減輕視覺負擔。

（2）界面信息采用簡明的文字表述，清晰易懂、內涵豐富，易于理解和記憶，如使用的圖標要具有個性、盡量表達功能含義。

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

3.免干擾性原則

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

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

4.反饋性原則

（1）最低級的反饋（對應于聯(lián)結設計）：用戶在交互設備上的每個動作都應立即產生明顯的反饋。

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

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

5.容錯性原則

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

（2）應使用單選、多選或下拉列表等合適的選擇控件，提供有代表性的默認選項以及相應的輸入幫助，方便用戶準確輸入信息。

（3）對用戶的輸入和選擇等操作，界面應提供校驗功能進行實時判斷，提示錯誤所在，并提供有用的恢復建議，幫助用戶及時更正錯誤輸入。

6.面向多層次用戶原則

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

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

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

3.5交互式圖形軟件的界面構成及界面元素

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

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

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

3.5.1圖形軟件主界面

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

圖3.10AutoCAD圖形軟件主界面

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

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

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

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

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

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

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

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

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

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

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

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

（7）組合框：用于從一組相關