何援軍

(上海交通大學(xué)計(jì)算機(jī)系，上海 200240)

圖學(xué)與幾何

何援軍

(上海交通大學(xué)計(jì)算機(jī)系，上海 200240)

本文討論圖學(xué)與幾何的關(guān)系。從形是圖之源、圖形/圖像的本質(zhì)是幾何這個(gè)基本認(rèn)識(shí)出發(fā)，指出圖的產(chǎn)生、表示、處理與傳播過程都是在處理幾何的定義、變換與其間關(guān)系，因此圖與圖學(xué)的基礎(chǔ)是幾何，圖學(xué)計(jì)算的基礎(chǔ)是幾何計(jì)算?；趫D學(xué)與計(jì)算的內(nèi)涵分析，剖析了圖形計(jì)算的本質(zhì)、矛盾和關(guān)鍵技術(shù)。討論了代數(shù)與幾何在圖學(xué)計(jì)算中各自的作用與利弊，強(qiáng)調(diào)人在算法設(shè)計(jì)中的主導(dǎo)地位。指出生成一幅圖或構(gòu)建一個(gè)模型的主要工作不是決定構(gòu)成該圖或模型的元素本身，而在于找出元素之間的相互關(guān)系。針對(duì)圖形圖像已經(jīng)成為計(jì)算的主要對(duì)象與結(jié)果表述，介紹了一種基于幾何的形計(jì)算機(jī)制，彌補(bǔ)常規(guī)數(shù)計(jì)算的不足，追求“形思考、數(shù)計(jì)算”的幾何計(jì)算新模式。

圖學(xué)；幾何；幾何計(jì)算；數(shù)計(jì)算；形計(jì)算

這是關(guān)于圖與圖學(xué)的第六篇文章[1-5]，這次討論圖學(xué)與幾何——這兩門科學(xué)的關(guān)系。

何謂科學(xué)？給科學(xué)一個(gè)充分的、本質(zhì)的定義并非易事，因?yàn)榭茖W(xué)其實(shí)是一種社會(huì)的、歷史的和文化的人類活動(dòng)。科學(xué)首先是對(duì)應(yīng)于自然領(lǐng)域的知識(shí)，經(jīng)擴(kuò)展，引用至社會(huì)、思維等領(lǐng)域，如社會(huì)科學(xué)、自然科學(xué)和思維科學(xué)等?？茖W(xué)是知識(shí)，且不是零碎而是理論化、系統(tǒng)化的知識(shí)體系，是人類對(duì)自然、社會(huì)的認(rèn)識(shí)活動(dòng)。

圖學(xué)已經(jīng)是這樣的一門科學(xué)。圖形的形象性、直觀性、準(zhǔn)確性和簡(jiǎn)潔性使得人們可以通過圖形來認(rèn)識(shí)未知，探索真理，圖形/圖像在人們生活中的應(yīng)用已經(jīng)極大的普及。圖形/圖像已成為重要的計(jì)算對(duì)象與計(jì)算結(jié)果，已被作為解的一種表現(xiàn)形式去追求，不管是靜態(tài)的或者是動(dòng)態(tài)的，這樣的計(jì)算，遍及各個(gè)領(lǐng)域。人類社會(huì)已經(jīng)進(jìn)入一個(gè)圖形/圖像時(shí)代。統(tǒng)一圖形/圖像的研究順應(yīng)了這個(gè)形勢(shì)，符合圖形/圖像發(fā)展的規(guī)律，圖與研究圖的圖學(xué)科學(xué)的作用將會(huì)日益增大。

本文闡述圖學(xué)理論化、系統(tǒng)化的知識(shí)體系，梳理圖形/圖像的表達(dá)機(jī)制與產(chǎn)生機(jī)理，指出圖形/圖像的源頭是形，基礎(chǔ)是幾何，由此認(rèn)識(shí)圖學(xué)與幾何的關(guān)系。從圖形/圖像的本質(zhì)入手，分析圖學(xué)計(jì)算的若干關(guān)鍵問題，揭示圖學(xué)計(jì)算的內(nèi)涵，從計(jì)算與幾何兩個(gè)關(guān)鍵問題出發(fā)，分析了圖學(xué)計(jì)算的基礎(chǔ)，討論了代數(shù)與幾何在圖學(xué)計(jì)算中各自的作用與利弊，這決定了圖學(xué)計(jì)算模式的選擇。最后，本文依據(jù)圖學(xué)計(jì)算的對(duì)象和目標(biāo)是圖形/圖像，介紹一種“形計(jì)算”機(jī)制，研究從形的整體去主導(dǎo)算法設(shè)計(jì)，構(gòu)建算法框架；闡述形計(jì)算在計(jì)算中的地位、作用和應(yīng)用領(lǐng)域，給出其理論基礎(chǔ)、計(jì)算基礎(chǔ)和實(shí)施方案及實(shí)例。這是幾何代數(shù)化發(fā)展到圖形/圖像時(shí)代的必然趨勢(shì)——加強(qiáng)圖形認(rèn)知方式在計(jì)算中的作用。

1 圖與圖學(xué)

1.1 圖形圖像

文獻(xiàn)[6]指出，圖(graph/picture/graphical images)實(shí)際上可分成“圖形類”和“圖像類”兩種。

圖形類(drawing or wire frame)，以矢量圖形式呈現(xiàn)，在計(jì)算機(jī)中由場(chǎng)景的幾何模型與物理屬性表示的圖形，能體現(xiàn)景物的幾何個(gè)體，記錄體元的形狀參數(shù)與屬性參數(shù)。例如，工程圖紙(drawing)，最基本的圖形單元(簡(jiǎn)稱“圖元”——primitives)是點(diǎn)、線、圓/弧等，其信息包含圖元的幾何信息與屬性信息(顏色、線型、線寬等顯式屬性和層次等隱式屬性)。

圖像類(image/bitmap)，以點(diǎn)陣圖形式呈現(xiàn)，在計(jì)算機(jī)中以具有顏色信息的點(diǎn)陣來表示的圖形，其更強(qiáng)調(diào)整體形式，描述一個(gè)個(gè)點(diǎn)——像素(pixel)或圖像單元(pels，picture elements)，記錄點(diǎn)的幾何位置及它的灰度或色彩，如照片、掃描圖片和由計(jì)算機(jī)產(chǎn)生的真實(shí)感、非真實(shí)感圖形等。其信息實(shí)際上是點(diǎn)與它的屬性信息(顏色、灰度、亮度等)。

因此，本質(zhì)上圖形和圖像都是帶有屬性的基本幾何的組合。

圖形，由“圖”和“形”兩個(gè)字組成，其實(shí)這里至少有兩層意思：其一，圖描述形，是形在畫面上展現(xiàn)，去展現(xiàn)形，是形的載體；其二，圖源于形，由形而來，形是圖之源。在計(jì)算機(jī)上模擬現(xiàn)實(shí)世界、構(gòu)建虛擬世界，先要造型，而后得圖。形是對(duì)現(xiàn)實(shí)的模擬和構(gòu)造，其屬性是表示、是輸入；圖是形在畫面上展現(xiàn)，其屬性是表現(xiàn)、是輸出。它們的共性元素是幾何。可以用“圖”一詞，從“形”的角度去統(tǒng)一圖形/圖像的表述，研究圖形/圖像的表示、產(chǎn)生、處理與傳輸理論和方法。

1.2 圖學(xué)(graphics)

圖乃萬物之現(xiàn)，與宇宙同生并存，承載人類文明，展示人類文化，敘述蒼穹之變化，記錄文明之發(fā)展。圖書圖書，左圖右書。對(duì)圖形作為計(jì)算源與計(jì)算結(jié)果的需求大大增加。圖的學(xué)科不僅僅是“工程圖學(xué)”，已經(jīng)發(fā)展到“信息圖學(xué)”、“科學(xué)圖學(xué)”乃至“生活圖學(xué)”等等。

現(xiàn)有關(guān)于圖的科學(xué)主要有工程圖學(xué)、計(jì)算機(jī)圖形學(xué)和計(jì)算機(jī)圖像處理。

工程圖學(xué)作為工程與技術(shù)科學(xué)基礎(chǔ)學(xué)科，是發(fā)展最早，理論與實(shí)踐也最完善的圖學(xué)學(xué)科。其現(xiàn)在面對(duì)一個(gè)新的現(xiàn)實(shí)，計(jì)算機(jī)的介入改變了原先的制圖工具，制圖過程中人的思維與計(jì)算機(jī)圖形軟件兩個(gè)終端的直接連接使工程圖學(xué)處于一個(gè)尷尬境地。但是，圖紙作為工程語言的地位沒有改變，制圖、讀圖、圖紙的信息共享等的理論、方法與技術(shù)需要工程圖學(xué)去承擔(dān)。

計(jì)算機(jī)圖形學(xué)現(xiàn)在地位穩(wěn)固，幾乎所有領(lǐng)域都可涉及，新的理論、方法乃至硬件日新月異。這就需要靜下心來思考，計(jì)算機(jī)圖形學(xué)最基礎(chǔ)、最本質(zhì)的是什么？圖的生成與處理應(yīng)該是計(jì)算機(jī)圖形學(xué)的核心內(nèi)容，在計(jì)算機(jī)圖形學(xué)中講造型，處于服務(wù)于繪制的地位，是可以選擇的內(nèi)容。

計(jì)算機(jī)圖像處理包括對(duì)數(shù)字圖像的處理、對(duì)數(shù)字圖像的分析與理解、數(shù)字化圖像的采集，以及對(duì)圖像處理結(jié)果的數(shù)字化表達(dá)等。計(jì)算機(jī)圖像的本質(zhì)是平面上的點(diǎn)以及點(diǎn)的屬性(顏色、灰度等)，因此其理論可以分成兩個(gè)部分：對(duì)密集的點(diǎn)的處理和對(duì)色彩的處理。

IEEE對(duì)計(jì)算機(jī)圖形學(xué)的定義是：Computer graphics is the art or science of producing graphical images with the aid of computer，這個(gè)定義有幾個(gè)關(guān)注點(diǎn)：首先，定位計(jì)算機(jī)圖形學(xué)不僅是一門科學(xué)，還是一門藝術(shù)；其次，雖然認(rèn)為圖像借助于計(jì)算機(jī)但沒有提及從何產(chǎn)生？

由于計(jì)算機(jī)的介入與發(fā)展，圖形與圖像在計(jì)算機(jī)上的表示已逐漸趨于統(tǒng)一，研究圖形、圖像科學(xué)的發(fā)展也已經(jīng)到了幾乎彼此不分的地步。社會(huì)已經(jīng)進(jìn)入到一個(gè)在“大圖”與“大圖學(xué)”概念上研究圖與圖學(xué)的歷史新階段。統(tǒng)一圖形、圖像的研究順應(yīng)了這個(gè)形勢(shì)，符合圖形、圖像發(fā)展的規(guī)律。

中國圖學(xué)學(xué)會(huì)在2013年發(fā)布圖學(xué)學(xué)科報(bào)告[1]，給圖學(xué)下的定義是：“圖學(xué)是以圖為對(duì)象，研究在將形演繹到圖的過程中，關(guān)于圖的表達(dá)、產(chǎn)生、處理與傳播的理論、技術(shù)與應(yīng)用的科學(xué)”。這個(gè)定義的主要論點(diǎn)是：圖學(xué)研究形和圖的表示、表現(xiàn)以及互相關(guān)系，其基本內(nèi)容包括：造型、由形得到圖、圖的處理、由圖得到形以及圖的傳輸?shù)?。這里，目標(biāo)是圖、核心是形、本質(zhì)是幾何，基礎(chǔ)是幾何計(jì)算。圖學(xué)的理論、方法和技術(shù)的主要基礎(chǔ)是幾何學(xué)及代數(shù)學(xué)，也借助于其他學(xué)科或?qū)W科交叉。其首次揭示了形是圖之源，并統(tǒng)一了圖形圖像的稱謂，合并稱圖，建立了大圖和大圖學(xué)的概念。這個(gè)定義也反映了圖、圖學(xué)與幾何的關(guān)系。

2 圖學(xué)與幾何

2.1 圖學(xué)的本質(zhì)是幾何

James R. Miller[7]說過：Computer graphics and modeling rely on mathematical operations on points and vectors. I advocate using vector geometric analysis to simplify required derivations，短短兩句話，揭示了計(jì)算機(jī)圖形學(xué)和造型的基礎(chǔ)是點(diǎn)與向量的運(yùn)算，充分認(rèn)識(shí)到了圖學(xué)與幾何的緊密關(guān)系。國際學(xué)術(shù)組織International Society for Geometry and Graphics (ISGG)，每 2年召開一次 International Conference on Geometry and Graphics，這是將圖學(xué)與幾何定位得最緊密也是最貼切的國際學(xué)術(shù)組織與國際會(huì)議。

圖學(xué)研究將形演繹到圖，以及圖的表達(dá)、產(chǎn)生、處理與傳播。圖源于形，由形而來，在計(jì)算機(jī)中，形與圖都是由幾何構(gòu)造與描述的，這里的幾何是點(diǎn)、線、面等，可被稱為“幾何元”，這些不同的幾何元依照一定的拓?fù)潢P(guān)系組織起來構(gòu)造成不同的幾何形體；通過投影在平面顯示成圖——圖形或圖像，此時(shí)，點(diǎn)、線被稱為“圖元”，圖元是具有不同屬性的幾何元。因此，不論是位圖還是矢量圖，終極處理對(duì)象是點(diǎn)、線等幾何元。它們都源于幾何。表1給出了幾何計(jì)算在計(jì)算機(jī)圖形學(xué)中的作用，幾何與幾何計(jì)算在圖學(xué)中的地位和作用可見一斑。

表1 幾何計(jì)算在計(jì)算機(jī)圖形學(xué)中的作用

在學(xué)科分工上，計(jì)算機(jī)圖形學(xué)與計(jì)算機(jī)圖像處理各有側(cè)重，計(jì)算機(jī)圖形學(xué)偏重于從形得到圖，計(jì)算機(jī)圖像處理則偏重于對(duì)圖本身的處理。盡管圖形與圖像的處理方式存在差異，但是其計(jì)算基礎(chǔ)是相同的，同是幾何。

計(jì)算機(jī)圖形學(xué)中的兩個(gè)典型算法隱藏線消除算法與真實(shí)感圖形繪制算法可以很好的說明其同一性。隱藏線消除是將形顯示為圖形的典型算法，消隱過程是一條一條線的輸出，每條線需與場(chǎng)景中所有可能遮擋它的物體(面)進(jìn)行比較，線的各可見部分的交集即為此線的最終可見部分。真實(shí)感圖形繪制則是將形顯示為圖像的典型算法，這是一個(gè)基于光強(qiáng)與色彩的量化、紋理映射、圖像合成、幀緩存等基于物理、光學(xué)、色彩理論的復(fù)雜計(jì)算過程。兩個(gè)算法在三維空間的主要計(jì)算都是從光源發(fā)出的每一條光線與景物表面的空間線面的求交與分割計(jì)算，計(jì)算的目標(biāo)都是為了求得空間點(diǎn)，消隱計(jì)算是2個(gè)點(diǎn)，光照計(jì)算是1個(gè)點(diǎn)。只是在最后的顯示階段，其才各走自己的路，一個(gè)取2個(gè)點(diǎn)得到線段及線的寬度、線型、顏色等屬性，組成圖形；另一個(gè)則去計(jì)算1個(gè)點(diǎn)的色調(diào)、色飽和度和亮度等屬性，得到像素，組成圖像。這里，算法研究的重點(diǎn)與主要的計(jì)算工作都在幾何求交、幾何分割和幾何比較等幾何計(jì)算上。

在計(jì)算機(jī)圖像處理領(lǐng)域，在基于剪影輪廓三維重建中，通過空間線段的求交計(jì)算獲取構(gòu)成可視化外殼的公共線段集合是核心步驟。聲稱空間線段求交計(jì)算在整個(gè)重建流水線耗時(shí)約占整個(gè)建模時(shí)間的 30%～40%，目前求交運(yùn)算的速度還是該技術(shù)在速度方面的瓶頸之一[8]。

最后，圖學(xué)計(jì)算中常用的幾何變換、圖形變換和坐標(biāo)系變換也是與幾何密切相關(guān)的。平移、旋轉(zhuǎn)、比例以及投影(正投影或透視投影)等，這些變換都是幾何變換，可以用變換幾何化方式實(shí)現(xiàn)。

2.2 圖學(xué)計(jì)算中的若干問題

2.2.1 圖學(xué)計(jì)算的本質(zhì)是求取幾何間的關(guān)系[3,9-11]

圖形/圖像的基礎(chǔ)是幾何。幾何由一系列幾何元按照一定的幾何關(guān)系構(gòu)成，少數(shù)基本幾何元根據(jù)不同的關(guān)系就可組合出萬千幾何。例如，給出平面上不重疊的4個(gè)點(diǎn)，這4個(gè)點(diǎn)可以構(gòu)造C42=6條線，這6條線可以組成∑C6i(i=1, 2, 3, 4, 5, 6)個(gè)不同的圖形。在空間，更要指出哪2個(gè)點(diǎn)構(gòu)成了一條線，哪些線圍成了一個(gè)面，哪些面構(gòu)成了一個(gè)形體等等?？梢姡鲗?dǎo)形表示的是幾何元間關(guān)系而非幾何參數(shù)。在用兩個(gè)形體產(chǎn)生一個(gè)新模型時(shí)，難點(diǎn)也在如何根據(jù)參與運(yùn)算的那些源去重新構(gòu)建一個(gè)幾何間的新關(guān)系，而且這個(gè)新關(guān)系的組織遠(yuǎn)比只通過幾何間的求交就可得到幾何參數(shù)的計(jì)算困難得多。這背后顯現(xiàn)出的另一個(gè)問題是：幾何計(jì)算不僅僅是“計(jì)算”，還有一個(gè)“表示”問題。

2.2.2 維度差距的矛盾

圖學(xué)計(jì)算過程中，存在多種空間維度的不統(tǒng)一問題。

(1) 實(shí)體空間與表示空間不統(tǒng)一。不管是“立體圖”還是三視圖，看到的圖都是二維的，是用二維表示三維的。因此，實(shí)體空間(三維)與表示空間(平面)是不統(tǒng)一的。

(2) 思維空間與計(jì)算空間不統(tǒng)一。形是空間的，代數(shù)計(jì)算是線性的。幾何代數(shù)化將對(duì)幾何的圖形認(rèn)知轉(zhuǎn)化成基于參考系的數(shù)字表述形式，三維的形被直接跨越到一維的數(shù)，缺少必要的過渡和銜接。幾何屬性被打得面目全非，形的關(guān)系和變化難以完備獲得和表達(dá)。人的空間思維優(yōu)勢(shì)難以發(fā)揮，對(duì)算法的掌控能力下降。遺憾的是，人們似乎常常忽視這些空間不統(tǒng)一的矛盾，長期以來人們大多使用這樣的方式——“用一維計(jì)算處理二維甚至三維問題”。人們習(xí)慣于這樣的復(fù)雜！數(shù)學(xué)機(jī)械化[12-13]就公開宣稱，其工作就是“把質(zhì)的困難轉(zhuǎn)化為量的復(fù)雜”。

2.2.3 算法穩(wěn)健性的不可控

現(xiàn)在的算法研究常出現(xiàn)兩個(gè)偏向，一是只偏重速度而忽視穩(wěn)定性(robustness)，偏重速度的研究方法只是減少了浮點(diǎn)運(yùn)算，是令人擔(dān)心的。二是采用一些大規(guī)模沒有理論分析的隨機(jī)測(cè)試去驗(yàn)證算法的穩(wěn)定性，很難檢測(cè)到影響算法的特殊狀況[14]。

模型通常是有界的，例如不是直線而是線段或向量、不是平面而是多邊形等。模型的有界造成幾何間的特殊關(guān)系(共點(diǎn)、共線、共面)，形成幾何奇異，其錯(cuò)誤對(duì)幾何計(jì)算穩(wěn)定性的沖擊是根本性的[9-11]。

幾何體在浮點(diǎn)運(yùn)算環(huán)境下的表示是不精確的，幾何計(jì)算也是近似的。需要從構(gòu)造的角度闡述幾何奇異的幾何本質(zhì)，認(rèn)識(shí)幾何奇異的根本性，在檢測(cè)與處理兩個(gè)層次，準(zhǔn)確界定幾何位置的奇異界線，保證幾何奇異的正確判定、準(zhǔn)確檢測(cè)，從理論上構(gòu)筑一個(gè)幾何奇異問題的完整解決方案。

2.3 計(jì)算基礎(chǔ)

數(shù)學(xué)是研究“數(shù)”與“形”的科學(xué)，代數(shù)是研究“數(shù)”的學(xué)科，幾何是研究“形”的學(xué)科，幾何與代數(shù)的概念及方法都是研究科學(xué)和工程問題的重要數(shù)學(xué)工具[15]。幾何涉及的是空間問題，幾何從空間概念形象地審視問題，常用幾何間的相互(空間)關(guān)系處理問題，人們努力將一些問題歸結(jié)為幾何形式，因?yàn)檫@樣可以使用人的直覺，直覺是人類最有力的武器。代數(shù)涉及的是時(shí)間的操作，采用線性、有序的方式去處理問題。代數(shù)的目標(biāo)總是想建立一個(gè)公式，就是拿來一個(gè)有意義的東西，將其化成一個(gè)公式，然后得到答案。代數(shù)計(jì)算時(shí)本質(zhì)上不會(huì)再思考其含義，停止用幾何、圖形或物理的觀念去考慮問題。

數(shù)學(xué)上主要有兩種推理：符號(hào)推理與直觀推理，前者源于計(jì)數(shù)制，后者源于圖形制。繼數(shù)之后，形作為數(shù)學(xué)的第二個(gè)主要概念被引入，形能充分發(fā)揮人的空間思維特長。歐幾里得在幾何著作中首次系統(tǒng)地使用了形，少量使用符號(hào)，大量使用邏輯。他的著作結(jié)合了兩種創(chuàng)新：圖形的使用和證明的邏輯結(jié)構(gòu)。

數(shù)學(xué)科學(xué)發(fā)展的歷程中，幾何與代數(shù)原本分別考慮“形”和“數(shù)”的問題，各有自己的發(fā)展空間和問題域，也各有自己的理論基礎(chǔ)和方法學(xué)，理論上應(yīng)該各占半壁江山，各司其職。然而，歷史并不是這樣，兩者并不平衡。17世紀(jì)初，Descartes(笛卡兒)將坐標(biāo)引入幾何，把代數(shù)中形式化符號(hào)體系的表示方法引進(jìn)到幾何學(xué)中，使得幾何間的計(jì)算也能用代數(shù)形式實(shí)現(xiàn)，幾何(形)的概念用代數(shù)(數(shù))表示，人稱“幾何代數(shù)化”[16]，這是數(shù)學(xué)史上最豐富和最有效的創(chuàng)造之一。之后，形勢(shì)變了，代數(shù)與幾何之間出現(xiàn)了一種令人感到不太自然的關(guān)系。在笛卡兒“一切問題可以化為數(shù)學(xué)問題，一切數(shù)學(xué)問題可以化為代數(shù)問題，一切代數(shù)問題可以化為代數(shù)方程求解問題”思想的統(tǒng)治下，使得代數(shù)基本上取代了經(jīng)典幾何的地位。

在幾何的大家族中，有一個(gè)不為人注意的分支——畫法幾何(descriptive geometry)[17]，現(xiàn)在幾乎沒有人將畫法幾何列入幾何的范疇。其實(shí)，畫法幾何研究的基本對(duì)象也是幾何，也是研究形的科學(xué)。17世紀(jì)一些幾何學(xué)家將其方法與結(jié)論視為歐基里德幾何學(xué)的一部分，直到 1799年法國幾何學(xué)家蒙日(Gaspard Monge，1746—1818年)非數(shù)學(xué)地闡述了投影理論，使畫法幾何成為一門獨(dú)立學(xué)科。畫法幾何以“正投影”理論為基礎(chǔ)，通過投影將空間物體轉(zhuǎn)換成平面圖形，引導(dǎo)人們?cè)谄矫嫔先ヌ摌?gòu)三維物體，解讀三維空間。由于維數(shù)的降低導(dǎo)致信息的缺失而需要多個(gè)視圖表述三維物體，引發(fā)“2D/3D對(duì)應(yīng)”理論的出現(xiàn)，它是將視圖“還原”成三維物體的理論基礎(chǔ)。三維物體化為平面問題以后，平面圖形基本上只要考慮點(diǎn)、線、圓等基本幾何元素，“尺規(guī)作圖”方法使少量的作圖工具和方法就可作出大部分平面圖形。至今，畫法幾何在空間形體的表述、幾何問題的求解方法上仍然保留了幾何的方法，這似乎更接近于人的圖形認(rèn)知模式。

模型的表述與構(gòu)造，圖的產(chǎn)生與處理，進(jìn)行這些工作的都屬于圖學(xué)計(jì)算的范疇。圖學(xué)計(jì)算的對(duì)象和結(jié)果是形、圖形和圖像，所以，圖學(xué)計(jì)算有其獨(dú)特的矛盾和特別需要解決的問題，只有看到和分析清楚這些問題，才能有的放矢地研究和探索圖學(xué)計(jì)算的理論與方法。

2.4 圖學(xué)計(jì)算的模式選擇

(1) 計(jì)算是一切的基礎(chǔ)。在人類的社會(huì)進(jìn)步、經(jīng)濟(jì)建設(shè)和科技發(fā)展過程中，“計(jì)算”始終都扮演著非常重要的角色。“X計(jì)算”已是計(jì)算機(jī)廣為應(yīng)用的一個(gè)概念，例如，科學(xué)計(jì)算、網(wǎng)格計(jì)算、平行計(jì)算、智能計(jì)算、云計(jì)算等，幾何計(jì)算是其中之一。幾何計(jì)算是科學(xué)與工程計(jì)算的基礎(chǔ)與支撐，在計(jì)算機(jī)圖形學(xué)、計(jì)算機(jī)輔助設(shè)計(jì)與制造、計(jì)算幾何以及醫(yī)學(xué)圖像處理、建筑設(shè)計(jì)、運(yùn)動(dòng)學(xué)與機(jī)器人等領(lǐng)域有重要作用與應(yīng)用。

(2) 計(jì)算的學(xué)問應(yīng)該叫“算學(xué)”。其實(shí)，算學(xué)一詞很有特色，其抓住了計(jì)算的本質(zhì)，更能體現(xiàn)計(jì)算的神韻，又有動(dòng)態(tài)感。而且，從某種意義上說算學(xué)的范圍似乎比數(shù)學(xué)的大，例如，在計(jì)算機(jī)時(shí)代，至少算學(xué)還包括算法。Mathematics在中文中對(duì)應(yīng)的是“數(shù)學(xué)”這里的“數(shù)”不是 Data、Digital等，而是Calculate、Compute、Consider、Analysis和Plan等，是Arithmetic。在計(jì)算機(jī)時(shí)代，更應(yīng)包含Algorithm。計(jì)算對(duì)象可能并非一個(gè)，結(jié)果也不一定是一個(gè)，甚至是不確定的。

(3) 計(jì)算的基礎(chǔ)是數(shù)學(xué)。人們對(duì)計(jì)算及其結(jié)果的基本要求是快速而直觀，是一個(gè)(組)簡(jiǎn)單的數(shù)字，或是一幅(批)合適的圖。因此，表述計(jì)算的對(duì)象與結(jié)果只有2種：數(shù)和形，數(shù)和形又分別對(duì)應(yīng)于數(shù)學(xué)的2個(gè)基礎(chǔ)學(xué)科——代數(shù)與幾何，對(duì)應(yīng)于數(shù)計(jì)算與形計(jì)算。

數(shù)學(xué)是永恒的！好的數(shù)學(xué)思想很少會(huì)過時(shí)，雖然運(yùn)用方式會(huì)發(fā)生很大變化。

(4) 算法的關(guān)鍵在于設(shè)計(jì)與模型構(gòu)建。對(duì)一個(gè)問題求解的一般過程是：提出問題→建模表達(dá)問題-使問題抽象化→用一個(gè)幾何模型去表示問題→將幾何模型生成圖形/圖像→使問題可視化→根據(jù)生成的圖形/圖像進(jìn)一步理解問題、思考解決方法。因此，在幾何計(jì)算的算法設(shè)計(jì)中，設(shè)計(jì)與模型是引領(lǐng)性、整體性的，如同有一個(gè)“形”的整體始終貫穿于整個(gè)求解過程，正是這個(gè)“形”使人的圖形認(rèn)知能力在算法的設(shè)計(jì)過程中得到最大的發(fā)揮，保證人在幾何計(jì)算中的掌控地位。

(5) 數(shù)計(jì)算的一些缺陷需要暫且擱置。數(shù)計(jì)算求解過程的不直觀使得人的空間思維特長蕩然無存，計(jì)算常變得不可讀，甚至不可掌控。史蒂芬·霍金有一句名言：Some told me that each equation I included in the book would halve the sales. I therefore resolved not to have any equation at all (有人告訴我，我在書中的每一個(gè)方程都會(huì)使這本書的銷量減半，為此我決定一個(gè)方程也不用。)[18]足見代數(shù)的不可讀性對(duì)交流的殺傷力。還有一些問題困擾著純代數(shù)方法，如不必要的復(fù)雜度、需要較復(fù)雜的數(shù)學(xué)計(jì)算工具、算法時(shí)間性能低下、無法完美處理奇異性問題等等。

(6) 目前的幾何計(jì)算方式過于依賴于數(shù)計(jì)算。隨著計(jì)算機(jī)科學(xué)的發(fā)展，許多計(jì)算的對(duì)象都是圖形和模型，結(jié)果也以圖形/圖像的形式呈現(xiàn)，其主要元素是幾何或形。由于一般的計(jì)算都是采用數(shù)計(jì)算機(jī)制，這樣，幾何計(jì)算的過程就變得有點(diǎn)復(fù)雜：【形→數(shù)】→【數(shù)計(jì)算】→【數(shù)→形】。這樣，人的大量工作就會(huì)花在【形→數(shù)】和【數(shù)→形】的轉(zhuǎn)換上，這不符合人的思維習(xí)慣。其實(shí)，數(shù)學(xué)主要發(fā)生于幕后，起關(guān)鍵作用的是人，人的思維、人的邏輯。所謂“交互”，就是人與機(jī)器的相互作用。交互系統(tǒng)的產(chǎn)生，就是充分考慮了在計(jì)算機(jī)快速中發(fā)揮人的直觀感知能力的作用，這是一個(gè)很大的進(jìn)步，是人機(jī)結(jié)合的典范。

(7) 在幾何計(jì)算中更充分發(fā)揮幾何特性。幾何的本質(zhì)是某些屬性不依賴于參考坐標(biāo)系，具有不變性，這是研究幾何的基礎(chǔ)。面對(duì)一個(gè)幾何問題，是首先考慮如何將它化成一個(gè)代數(shù)方程(公式)，送到計(jì)算機(jī)里，搖一搖就得到結(jié)果，而不管過程如何復(fù)雜；還是充分發(fā)揮形與數(shù)各自的優(yōu)勢(shì)，先從空間的角度審視一個(gè)幾何問題，借助于圖形的直觀，用幾何的思路尋求一個(gè)全局、直觀的解決方案，將枯燥的數(shù)字與反復(fù)的的代數(shù)計(jì)算分離給計(jì)算機(jī)去做，發(fā)揮人的直覺優(yōu)勢(shì)，回歸人的主控地位，一改數(shù)百年來的幾何代數(shù)之路。長期以來，人們總以幾何代數(shù)化這樣的思路去解決幾何問題，這無意地削弱了幾何的作用范圍，掩蓋了幾何的一種天然美感。

(8) 追求“形思考、數(shù)計(jì)算”的幾何計(jì)算模式。應(yīng)該以幾何學(xué)家的思路去考慮問題——宏觀而慎密，以代數(shù)學(xué)家的方式去解決問題——嚴(yán)格而有序。與人的圖形認(rèn)知能力相匹配，在幾何的框架下宏觀設(shè)計(jì)，按照代數(shù)的方式有序求解。

代數(shù)管數(shù)，幾何管形。數(shù)引出數(shù)計(jì)算，形可否引出形計(jì)算？其實(shí)，形計(jì)算早已有之，在希臘科學(xué)中幾何學(xué)就是占統(tǒng)治地位的：量被解釋為長度，兩個(gè)量之積解釋為矩形、面積等。畫法幾何的尺規(guī)作圖方法本質(zhì)上就是一種形計(jì)算。因此，計(jì)算不應(yīng)該只是數(shù)計(jì)算，還應(yīng)該有形計(jì)算。

3 圖學(xué)中的形計(jì)算

圖學(xué)計(jì)算的基礎(chǔ)面臨新的挑戰(zhàn)，圖學(xué)計(jì)算將向著多元化、多學(xué)科相融合的方向發(fā)展，穩(wěn)定性將成為圖學(xué)計(jì)算的研究熱點(diǎn)與難點(diǎn)。為此需要更優(yōu)秀的圖學(xué)計(jì)算理論、算法和系統(tǒng)架構(gòu)，滿足圖學(xué)計(jì)算精確性、魯棒性和可擴(kuò)展性的需要。探索一種發(fā)揮幾何直觀簡(jiǎn)潔特點(diǎn)的幾何化求解方法，追求形、數(shù)結(jié)合的新突破。

下面介紹的“形計(jì)算”機(jī)制[4,16-26]基于下列認(rèn)知：將思維、幾何、代數(shù)及計(jì)算在幾何計(jì)算中定位在4個(gè)不同的層次：思維是認(rèn)知與設(shè)計(jì)層次、幾何是表述層次、代數(shù)是計(jì)算層次、計(jì)算是實(shí)施層次。基于幾何問題幾何化的思路，“回歸幾何”，淡化代數(shù)化計(jì)算。尋求建立一種“三維思維，二維圖解，一維計(jì)算”的多維空間融合，追求形-數(shù)的順滑過渡。加強(qiáng)人在計(jì)算中的主控地位，更好發(fā)揮人的空間邏輯思維。將對(duì)數(shù)計(jì)算的非可讀性、幾何奇異引起的計(jì)算不穩(wěn)定性等方面有較大的改善。

3.1 形計(jì)算的理論基礎(chǔ)

解決一個(gè)問題首先是要清晰、簡(jiǎn)單的表述它，如果連表述尚且困難，何來解決問題？

針對(duì)圖形圖像的新需求，為了適應(yīng)新的計(jì)算，一些理論和方法被建立起來去描述新的計(jì)算對(duì)象。如圖論采用圖的形式建立關(guān)系圖，能充分發(fā)揮人善于形象思維的優(yōu)勢(shì)；數(shù)據(jù)結(jié)構(gòu)理論將數(shù)分成了參數(shù)域和指針域以及樹結(jié)構(gòu)等。特別是不真正參與運(yùn)算的指針的引入使常規(guī)的計(jì)算有了質(zhì)的變化。在點(diǎn)形成線，線形成面，面構(gòu)造形體的幾何計(jì)算中，指針對(duì)解決形體的表述，簡(jiǎn)化復(fù)雜的幾何算法(例如布爾運(yùn)算)有很大的作用。這些，實(shí)際上是對(duì)數(shù)制與計(jì)算單元的擴(kuò)充。

(1) 數(shù)制。現(xiàn)在用的記數(shù)制是位值制，例如十進(jìn)位值制。用這種方法寫出的數(shù)字，它的大小不僅和用到的數(shù)字符號(hào)有關(guān)，還和這些符號(hào)所在的位置有關(guān)。這是一個(gè)很美妙的發(fā)明。計(jì)算機(jī)能夠用于計(jì)算，首先就是解決如何用0/1機(jī)制表述十進(jìn)位值制，馮·諾依曼二進(jìn)制數(shù)制奠定了計(jì)算機(jī)的計(jì)數(shù)理論[20]，以及八進(jìn)制、十六進(jìn)制和浮點(diǎn)數(shù)表示方法使計(jì)算機(jī)的數(shù)字計(jì)算得以實(shí)現(xiàn)。

對(duì)幾何計(jì)算，Leibniz就認(rèn)為應(yīng)該有一種“幾何代數(shù)”，其接近于幾何本身，每個(gè)表達(dá)式都有明確的幾何解釋，其元素被稱為“幾何數(shù)”[16]。由幾何數(shù)處理幾何體，實(shí)現(xiàn)幾何計(jì)算的設(shè)想本質(zhì)就是解決幾何體的數(shù)制問題。形計(jì)算機(jī)制將采用 Leibniz幾何數(shù)的名字，引入幾何數(shù)表征幾何的表述。數(shù)制問題解決了，形計(jì)算就有基礎(chǔ)了。

(2) 計(jì)算單元。幾何代數(shù)化已經(jīng)給出了基本幾何元(點(diǎn)、線、面等)的表述，一些基本幾何體(錐、柱等)主干表述也已給出，除了它們的范圍以外(例如表示圓柱除了方程x2+y2=R2，外加h1≤z≤h2表示范圍)。形計(jì)算機(jī)制將在幾何代數(shù)化的基礎(chǔ)上引入“幾何基”的概念。幾何基的引入吸取了畫法幾何“尺規(guī)作圖”，高等代數(shù)線性空間“任一向量可以用它的基底線性表出”以及計(jì)算機(jī)算法的思想。幾何基的原始模型可以作以下抽象化的表述：幾何基是幾何元操作的抽象表示，一種對(duì)幾何元的原子操作，也是幾何關(guān)系的表現(xiàn)，它構(gòu)建了幾何解的基礎(chǔ)。由此，對(duì)幾何問題解的新解讀就變成：“幾何問題的解可由幾何基的序列表述”，它類似于計(jì)算結(jié)果由一系列的計(jì)算單元按照一定的算式表述出來。

3.2 形計(jì)算在計(jì)算中的地位

當(dāng)然，不能嚴(yán)格的照搬數(shù)計(jì)算機(jī)制的模式去定義、去理解這個(gè)形計(jì)算，其更多的是在人的思考層面、解決幾何問題的框架層面和算法的設(shè)計(jì)層面，表述不同維度下的形數(shù)轉(zhuǎn)化機(jī)制。

圖 1展示了形計(jì)算(虛框)在整個(gè)計(jì)算中的地位。提出形計(jì)算的背景是圖形/圖像已成為計(jì)算的主要對(duì)象與目標(biāo)，其源頭是形,而形的基礎(chǔ)是幾何。形計(jì)算機(jī)制是一種基于幾何的計(jì)算概念與機(jī)制，其將幾何看做計(jì)算單元，以求取幾何間的關(guān)系作為計(jì)算目標(biāo)。從形的角度去揭示畫法幾何與幾何的共性問題，將其應(yīng)用于幾何計(jì)算中。探索以形為核心，將幾何、畫法幾何、代數(shù)和計(jì)算機(jī)等多學(xué)科理論與方法的長處融合在一起，達(dá)到所謂的“形思考、數(shù)實(shí)施”，更好發(fā)揮人擅長思維與計(jì)算機(jī)擅長計(jì)算各自的特長。

圖1 形計(jì)算在計(jì)算中的地位

3.3 引入幾何數(shù)

引入幾何數(shù)(geometric number)，協(xié)助表征幾何的定義與幾何間關(guān)系的表示，并輔助整個(gè)計(jì)算過程。

天地萬物，陰陽而已。一個(gè)陽爻符號(hào)“－”與一個(gè)陰爻符號(hào)“--”書寫了一部易經(jīng)，“0”與“1”構(gòu)建了整個(gè)計(jì)算機(jī)體系，物理中電之“正/負(fù)”、電路之“開/關(guān)”，···，均那陰/陽之分也。幾何定義之“左/右(向量)”、“內(nèi)/外(邊界)”、“進(jìn)/出(交點(diǎn))”，幾何關(guān)系之“離/交/切/含”，幾何度量之“正/負(fù)(面積)”、“逆/順(角度)”等等何嘗不只是陰陽之分？借用了 Leibniz幾何數(shù)一詞。在形計(jì)算中引入幾何數(shù)表示幾何的陰/陽兩極，它隱含在幾何的表示、構(gòu)造、定位、度量及幾何間的關(guān)系處理的各個(gè)方面。如：

(1) 對(duì)基本幾何元直線、圓(弧)、面等引入方向(左/右、順/逆、前/后)；

(2) 對(duì)幾何的長度、面積、體積等引入正負(fù)(正/負(fù))；

(3) 將幾何邊界分成外邊界與內(nèi)邊界(左/右)；

(4) 對(duì)兩幾何間的交點(diǎn)區(qū)分“入點(diǎn)/出點(diǎn)(負(fù)/正)”；

(5) 若干幾何間的連接遵照“皮帶輪法則”；

(6) 對(duì)描述直線、平面等的系數(shù)進(jìn)行規(guī)格化(單位法向量)；

(7) 強(qiáng)調(diào)幾何在“標(biāo)準(zhǔn)坐標(biāo)系(計(jì)算坐標(biāo)系)”下描述；等等。

幾何數(shù)的定義符合自然規(guī)律，也符合人的認(rèn)知體系，其引入將能更好的表述幾何的屬性，使幾何間的關(guān)系也更清晰。

幾何數(shù)在形計(jì)算中的作用是多方面的，表2列出了它在幾何表示、簡(jiǎn)化計(jì)算、解的選擇等方面作用的例子。

3.4 引入幾何基

引入幾何基(primary geometric basis)作為形計(jì)算的基本單元?！都t樓夢(mèng)》只用了4 462個(gè)不同漢字，關(guān)鍵是如何組織。幾何形體、圖形圖像無非由點(diǎn)線面構(gòu)造。幾何元素通常有 25種，建立一個(gè)通用的定義與求交函數(shù)庫，最終“字?jǐn)?shù)”也就 C252+25=325個(gè)。幾何基按一定的關(guān)系組合起來就構(gòu)建了形的構(gòu)造樹，樹的遍歷就是形的解(圖2)。

表2 幾何數(shù)在幾何表示、簡(jiǎn)化計(jì)算、解的選擇中作用的一些例子

幾何基運(yùn)用公理去誘導(dǎo)幾何推理計(jì)算，處理幾何元之間的幾何關(guān)系，而非用純代數(shù)計(jì)算去解決幾何問題。從解的形式來看，幾何問題的求解形式表現(xiàn)為幾何基的序列，即幾何元的操作序列組成問題的解，使計(jì)算的每一個(gè)步驟都具有幾何意義。使幾何問題的求解結(jié)構(gòu)化、直觀化、簡(jiǎn)單化。

用一個(gè)“求取過平面上3點(diǎn)的圓”例子來闡述用幾何基求解平面幾何問題的實(shí)施過程。(圖 2)如果將“作 2點(diǎn)的垂直平分線”的幾何基命名為“LPPN()”(表述時(shí)只需名字而省略參數(shù))，將“求兩直線的交點(diǎn)”的幾何基命名為“PLL()”，“CPPP()”表述為 3點(diǎn)所求的圓。用幾何基序列表示就是：CPPP()={LPPN，LPPN，PLL}。表3列出了這個(gè)求解過程。

圖2 3點(diǎn)求圓樹結(jié)構(gòu)求解示意圖

表3 過平面上3點(diǎn)作圓的幾何求解過程與幾何基序列表述

這種從幾何的角度描述并求解的原理將繁復(fù)的代數(shù)計(jì)算隱藏在幾何基中，使算法設(shè)計(jì)的思考過程變得直觀，也更宏觀。求取交點(diǎn)的代數(shù)實(shí)施過程被隱含了。因此，引入幾何基是企圖淡化(或隱藏)代數(shù)表述和代數(shù)運(yùn)算，表現(xiàn)出的是用空間的思維去構(gòu)建與描述整個(gè)求解過程。

3.5 幾何變換幾何化

形計(jì)算中幾何變換的重點(diǎn)不是空間幾何的平移、旋轉(zhuǎn)等常規(guī)變換，而是通過揭示幾何代數(shù)化的要素為三維形的降維服務(wù)。幾何代數(shù)化的基礎(chǔ)是引入坐標(biāo)系，坐標(biāo)系是什么？平面上任意兩條共點(diǎn)不共線的單位向量或空間任意3條共點(diǎn)不共面的單位向量就構(gòu)成一個(gè)坐標(biāo)系。同一幾何在不同坐標(biāo)系下有不同的表述，但幾何是不變的。因此，對(duì)任一幾何一定可找到一組最佳向量構(gòu)建坐標(biāo)系，在這個(gè)坐標(biāo)系下，幾何的表述、求解以及幾何間相交關(guān)系的求取是最簡(jiǎn)單的，稱為“計(jì)算坐標(biāo)系”。計(jì)算坐標(biāo)系的引入使點(diǎn)、線、圓、面等基本幾何，以及三角形、球面、錐面、柱面等基本體素能在它們所謂的“標(biāo)準(zhǔn)坐標(biāo)系”下解析描述，使幾何的表述與相交關(guān)系的求取更為簡(jiǎn)單?？臻g幾何的降維也一般可在正投影下進(jìn)行，表述簡(jiǎn)潔，計(jì)算復(fù)雜度也常會(huì)降低。

所謂變換幾何化[9-11]其最基本的表述是：平面上任意兩條相交(不共線)的單位向量構(gòu)成一個(gè)新坐標(biāo)系，新舊坐標(biāo)系間的坐標(biāo)變換可由兩條相交向量在原坐標(biāo)系下的直線方程系數(shù)及齊次項(xiàng)表出?？臻g任意 3個(gè)相交平面的單位法向量構(gòu)成一個(gè)新坐標(biāo)系，新舊坐標(biāo)系間的坐標(biāo)變換齊次矩陣由3個(gè)相交平面的規(guī)格化方程系數(shù)及齊次表出。

變換的幾何化表示方法所得到的齊次矩陣統(tǒng)一描述平移、旋轉(zhuǎn)、錯(cuò)切、對(duì)稱和比例等變換，而且它的矩陣元素可由基本幾何(向量、平面)的定義求解系統(tǒng)得到。

3.6 形計(jì)算的基本架構(gòu)

形計(jì)算的基本架構(gòu)如下(圖3)：

(1) 對(duì)變換實(shí)施幾何化，盡量使計(jì)算在相關(guān)幾何的“標(biāo)準(zhǔn)坐標(biāo)系(計(jì)算坐標(biāo)系)”下實(shí)施。

(2) 引入幾何數(shù)，協(xié)助表征幾何的定義，表述幾何間的關(guān)系，并輔助整個(gè)計(jì)算過程。引入幾何基，構(gòu)建基本幾何的定義、相交等的基本工具，作為形計(jì)算的基本幾何單元。

(3) 對(duì)三維的形，以解決表示為主，在幾何數(shù)的協(xié)助下，表征幾何體的構(gòu)造關(guān)系，以形為綱，在空間層面整體考慮幾何問題的求解方案；然后，根據(jù)主幾何元建立相應(yīng)的計(jì)算坐標(biāo)系，參考2D/3D對(duì)應(yīng)理論，建立三維形與二維圖的映射關(guān)系，將空間問題降為平面問題。

(4) 對(duì)二維的形和圖，以求解為主，主要基于畫法幾何投影理論和變換幾何化機(jī)制，解決3D幾何體降維以后的幾何的求解關(guān)系，建立幾何問題的構(gòu)造樹。

(5) 在線性空間，則是以代數(shù)計(jì)算為主，在平面上求得幾何基序列解，最后反變換返回到空間問題的最終解。形計(jì)算機(jī)制強(qiáng)調(diào)在幾何體整體下的降維，和順解決(幾何)表述空間與(代數(shù))線性計(jì)算空間不統(tǒng)一問題，順勢(shì)解決幾何奇異問題，提升算法的穩(wěn)定性。

圖3 形計(jì)算的總體框架與求解機(jī)制

3.7 基于幾何數(shù)的幾何奇異處理[20]

幾何計(jì)算不穩(wěn)定的主要原因是“幾何奇異”(理論層面)和“計(jì)算誤差”(實(shí)施層面)。判定是否幾何奇異(未知問題變成已知問題)與處理幾何奇異問題(解決一個(gè)已知問題)是計(jì)算穩(wěn)定性(共性問題)的兩個(gè)方面。如何在理論上(整體)解決幾何奇異問題一直沒有很好解決。

下面闡述如何依據(jù)“交點(diǎn)幾何數(shù)”概念簡(jiǎn)潔、有效地去解決幾何奇異問題。設(shè)兩向量的交點(diǎn)的幾何數(shù)取“入點(diǎn)”為“-1”，“出點(diǎn)”為“+1”，那么就有如下重交點(diǎn)與重邊交點(diǎn)處理規(guī)則。

(1) 重交點(diǎn)取舍規(guī)則(圖4)：將重交點(diǎn)的幾何數(shù)累加，若幾何數(shù)的代數(shù)和為0，則取消形成此重點(diǎn)的各交點(diǎn)；否則，合并為一個(gè)交點(diǎn)，并以代數(shù)和的符號(hào)作為其幾何數(shù)。

(2) 重邊交點(diǎn)的取舍規(guī)則(圖5)：如果在同一向量上有連續(xù)兩個(gè)交點(diǎn)的幾何數(shù)相同，則若幾何數(shù)均為+1，刪除后一個(gè)交點(diǎn)；若幾何數(shù)均為-1，刪除前一個(gè)交點(diǎn)。

兩個(gè)規(guī)則只是對(duì)交點(diǎn)幾何數(shù)的簡(jiǎn)單運(yùn)算，但從理論層面上解決了已知幾何關(guān)系奇異問題。

圖4 重交點(diǎn)的取舍

圖5 重邊交點(diǎn)的選擇

圖 6給出了用幾何數(shù)解決各類奇異問題的方案，圖7給出解決計(jì)算穩(wěn)定性的總體方案。

圖6 引入幾何數(shù)解決幾何奇異問題的實(shí)施方案

圖7 形計(jì)算中解決計(jì)算穩(wěn)定性的總體方案

3.8 形計(jì)算若干例子

下面給出用形計(jì)算機(jī)制處理幾何計(jì)算的一些實(shí)施例子[9-11,21-26]。

3.8.1 降維的二維矩形窗口裁剪[9]

Liner2D算法將二維裁剪降維化成二次一維裁剪，二次一維裁剪分x方向與y方向獨(dú)立進(jìn)行，合并兩次裁剪的結(jié)果就得到最后的裁剪結(jié)果。

設(shè)被裁剪線P0P1是用參數(shù)形式P=P0+(P1-P1)t表示的，如圖8所示。P0P1在裁剪窗口中的可見部分為：

P0P1∩LR∩BT，即[0,1]∩[t1,t2]∩[t3,t4]。

圖8 基于降維的二維裁剪

對(duì)基于線性裁剪的Liner2D算法與國際上認(rèn)可的 3種裁剪算法 CohenSutherland、CyrusBeck、LiangBarsky進(jìn)行了測(cè)試與對(duì)比，測(cè)試樣品采用6+61條線段，其中含對(duì)角線的菱形6條線為各種方位的常規(guī)線段，61條線遍歷了被裁剪線與矩形窗口的各種位置(含奇異位置，圖9)。

圖9 4種矩形裁剪的測(cè)試樣例與結(jié)果

正確性，4種算法都能正確的對(duì)這些線段作出裁剪。

計(jì)算效率的測(cè)試分成兩種：①是各種布局的線段的測(cè)試，即對(duì)所有67條線重復(fù)進(jìn)行50萬次裁剪；

測(cè)試結(jié)果見表 4，4種方法所花的計(jì)算時(shí)間在同一個(gè)數(shù)量級(jí)上，稍有區(qū)別。

表4 4種矩形窗口裁剪的計(jì)算效率參考表

3.8.2 基于投影降維的視錐體裁剪

視錐體裁剪是計(jì)算機(jī)圖形學(xué)的一個(gè)重要而基礎(chǔ)的算法，下面的算法利用畫法幾何的投影理論，將3D計(jì)算降為2D計(jì)算。

以視錐體的底平面及兩個(gè)對(duì)稱平面作為坐標(biāo)平面構(gòu)成計(jì)算坐標(biāo)系，以視錐體下底中心到上底中心的向量作為 z軸，建立視錐體的計(jì)算坐標(biāo)系(圖10)，利用畫法幾何理論建立V/W投影體系，在這個(gè)計(jì)算坐標(biāo)系下，視錐體在V面上的投影Tv與在W面上的投影Tw均為等腰梯形(圖11)。空間直線投影在V面與W面上分兩次裁剪，它們的交集即為三維裁剪結(jié)果。

圖10 視錐體計(jì)算坐標(biāo)系

圖11 視錐體二次裁剪原理圖

比較了3種算法，“Liang-Barsky視錐體裁剪方法”、“線面直接求交”算法和“基于投影降維的視錐體裁剪”算法。設(shè)計(jì)了包含與視錐體頂點(diǎn)、邊界線和邊界面處于奇異狀態(tài)的78組被裁剪線段樣本，在經(jīng)過預(yù)處理之后的標(biāo)準(zhǔn)坐標(biāo)系下，對(duì)這78個(gè)樣本重復(fù)10萬次裁剪的計(jì)算，計(jì)算時(shí)間的參考比例為：

L-B：線面求交：投影降維=4243：4228：4212說明3種算法的計(jì)算效率在同一數(shù)量級(jí)上。

需要強(qiáng)調(diào)的是，上面兩個(gè)窗口裁剪和視錐體裁剪算法與經(jīng)典算法作了比較，似乎在時(shí)間上并不占有優(yōu)勢(shì)，但這是形計(jì)算機(jī)制下的規(guī)則算法與專門研究的個(gè)體化算法的比較。

3.8.3 基于幾何數(shù)的幾何形體布爾運(yùn)算

文獻(xiàn)[21]敘述了一種基于幾何數(shù)的十分簡(jiǎn)單的二維布爾運(yùn)算算法。邊界的幾何數(shù)使圖形邊界劃分為有內(nèi)邊界與外邊界，交點(diǎn)的幾何數(shù)決定了交點(diǎn)是入點(diǎn)還是出點(diǎn)，算法原理十分簡(jiǎn)單。

二維圖形布爾算法(圖12)：從某一個(gè)交點(diǎn)出發(fā)，對(duì)并(交、差)運(yùn)算，若交點(diǎn)幾何數(shù)為負(fù)(正)，則轉(zhuǎn)向另一環(huán)(頂點(diǎn)則按原走向搜索下去)，直至回到出發(fā)時(shí)的首交點(diǎn)，就得到一個(gè)新邊界(環(huán))。一旦所有交點(diǎn)均被遍歷，算法結(jié)束(這里省略了重邊界的處理)。

在此，交點(diǎn)的幾何數(shù)能夠根據(jù)運(yùn)算的性質(zhì)協(xié)助決定環(huán)的走向，新邊界的內(nèi)外性質(zhì)在求解過程中同時(shí)被確定，也避免了從頂點(diǎn)出發(fā)需要進(jìn)行繁瑣的包容性測(cè)試，計(jì)算工作量較少。運(yùn)算中的幾何奇異問題也可由交點(diǎn)的幾何數(shù)簡(jiǎn)單的予以解決。

圖12展示了對(duì)兩個(gè)圖形A與B求并集的形運(yùn)算過程，分別從交點(diǎn)10和交點(diǎn)13出發(fā)得到A與B并集的兩條邊界(圖12(b)，圓圈里的數(shù)字為交點(diǎn)，方框里的數(shù)字為頂點(diǎn))。

這個(gè)方法也可以方便的擴(kuò)展到三維形體的布爾運(yùn)算(圖13)。

圖12 對(duì)2個(gè)圖形A與B求并集的形運(yùn)算

圖13 三維布爾運(yùn)算的原理

3.8.4 空間幾何的相交計(jì)算[9,21-26]

空間問題的形計(jì)算盡量采用降維計(jì)算，通常會(huì)利用畫法幾何的投影與2D/3D對(duì)應(yīng)理論。根據(jù)主幾何元建立相應(yīng)的計(jì)算坐標(biāo)系，參考 2D/3D對(duì)應(yīng)理論，在三維整體概念下建立空間幾何與平面圖形間的映射關(guān)系，得到三維形的二維圖表示，將空間問題降為平面問題。在平面上求得幾何基序列解，最后反變換返回到空間問題的最終解(這也構(gòu)成一個(gè)三維幾何基)。

空間兩幾何的求交算法可簡(jiǎn)單表述如下(空間直線與球面求交算法為例)：

步驟 1. 根據(jù)參與運(yùn)算幾何元的性質(zhì)，構(gòu)造計(jì)算坐標(biāo)系(以球心為原點(diǎn)，直線方向?yàn)閤軸方向構(gòu)建計(jì)算坐標(biāo)系。參閱圖14，下同)，建立V/W/H絕對(duì)投影體系。將參與計(jì)算的兩個(gè)幾何元的參數(shù)(點(diǎn)的坐標(biāo)，球中心與直線的兩端點(diǎn))變換到計(jì)算坐標(biāo)系下。

步驟2. 應(yīng)用2D/3D對(duì)應(yīng)理論建立空間幾何元降維前后的計(jì)算關(guān)系，形成投影面上的計(jì)算方案(在兩個(gè)投影面上分別求直線投影與圓①與圓②的交點(diǎn))。在兩投影平面各自構(gòu)造幾何基序列，分別得到兩幾何元交點(diǎn)在兩投影面上的坐標(biāo)參數(shù)，并將其合成為三維交點(diǎn)參數(shù)。

步驟 3. 如果有交點(diǎn)，將得到的交點(diǎn)參數(shù)逆變換回原始坐標(biāo)系。

算法包括預(yù)處理(步驟1，構(gòu)建計(jì)算坐標(biāo)系并作正向變換)、實(shí)施(步驟 2，在新坐標(biāo)系下的坐標(biāo)平面上求取交點(diǎn)，這是用幾何基的序列表述的)和后處理(步驟3，將交點(diǎn)坐標(biāo)逆變換) 3步。其中，求交過程在二維平面上進(jìn)行，例中用了兩次“直線與圓求交”幾何基。

圖14 用形計(jì)算求取空間直線與球面交點(diǎn)的實(shí)施過程

3.8.5 兩空間三角形的位置關(guān)系[9,26]

空間兩三角形相互關(guān)系判定與計(jì)算是有限元分析、碰撞檢測(cè)中的基礎(chǔ)算法。

設(shè)兩個(gè)三角形A與B所在的平面分別為ΠA，ΠB，兩平面的交線為L，A與ΠB的交線段為LA，B與ΠA的交線段為LB，則LA與LB必定在L上，若LA與LB有重疊部分，則兩三角形相交(圖15(a))，否則就相離(圖15(b))。直接空間判別比較復(fù)雜。

下面的算法通過降維的辦法簡(jiǎn)化兩三角形的關(guān)系，并解決幾何奇異問題(圖16)。

圖15 兩三角形空間求交的基本原理

圖16 經(jīng)降維后的空間兩三角形關(guān)系簡(jiǎn)化、奇異狀態(tài)清晰

先建立一個(gè)計(jì)算坐標(biāo)系，使其中一個(gè)三角形在該計(jì)算坐標(biāo)系的一個(gè)坐標(biāo)平面上(圖16(a))。這樣，該三角形在計(jì)算坐標(biāo)系的V投影坐標(biāo)平面上的投影為直線段和直線段(圖16(b)，在W面上的投影也是直線段)，在 H投影平面上的投影保持原始三角形(圖16(b), (c))。經(jīng)過投影降維后，兩個(gè)三角形的關(guān)系將分別在兩個(gè)坐標(biāo)平面上處理，轉(zhuǎn)變成“線段-線段”、“線段-三角形”的關(guān)系(圖 16(b), (d))，相互關(guān)系簡(jiǎn)化，奇異狀態(tài)也變得更清晰。

4 結(jié) 論

研究圖的科學(xué)應(yīng)統(tǒng)一被稱為“圖學(xué)”，圖學(xué)研究形和圖的表示、表現(xiàn)以及互相關(guān)系，其基本內(nèi)容應(yīng)該包含以下幾個(gè)方面：造型理論與方法、由形→圖的理論與方法、圖的處理理論與方法、由圖→形的理論與方法以及圖的傳輸理論與方法等。

圖源于形，幾何構(gòu)造了形與圖。因此圖學(xué)的核心是形，本質(zhì)是幾何，圖學(xué)計(jì)算的主要工作是幾何計(jì)算，理論基礎(chǔ)是幾何學(xué)。只有基于計(jì)算與幾何兩個(gè)最核心的要素，才能清晰圖學(xué)與幾何的關(guān)系。即圖學(xué)研究的目標(biāo)是圖、核心是形、本質(zhì)是幾何，最根本的理論基礎(chǔ)是幾何學(xué)。這些理論、方法和技術(shù)會(huì)借助于其他學(xué)科或是學(xué)科交叉。

計(jì)算是一切的基礎(chǔ)，計(jì)算的基礎(chǔ)是數(shù)學(xué)。數(shù)學(xué)上主要有兩種推理：符號(hào)推理與直觀推理，前者源于計(jì)數(shù)制，后者源于圖形制。繼數(shù)之后，形作為數(shù)學(xué)的第二個(gè)主要概念被引入，形能充分發(fā)揮人的空間思維特長。

通過對(duì)圖和形內(nèi)涵的分析，論述了處理圖形計(jì)算中的三個(gè)核心關(guān)系：幾何關(guān)系、形數(shù)關(guān)系和維度關(guān)系。指出求取新的幾何關(guān)系是圖學(xué)計(jì)算的目標(biāo)與主要工作；處理好維度關(guān)系，從而解決思維空間與計(jì)算空間、表述空間與顯示空間維度不統(tǒng)一問題是圖學(xué)計(jì)算的關(guān)鍵；幾何代數(shù)化引起三維幾何形表述與線性代數(shù)計(jì)算之間形數(shù)關(guān)系出現(xiàn)跳躍，解決形數(shù)關(guān)系的順滑過渡是圖學(xué)計(jì)算的綱。

介紹了一種發(fā)揮幾何直觀簡(jiǎn)潔特點(diǎn)的幾何化求解方法，即“從定性、直觀的角度去思考，以定量、有序的方式去求解”的思路，尋求“三維思維，二維圖解，一維計(jì)算”多維空間融合的求解機(jī)制，追求形-數(shù)順滑過渡的新突破。算例表明，形計(jì)算能夠彌補(bǔ)常規(guī)數(shù)計(jì)算的不足，對(duì)數(shù)計(jì)算的非可讀性，奇異引起的不穩(wěn)定性會(huì)有較大的改善。這種“形思考”、“數(shù)計(jì)算”的幾何計(jì)算新模式將能更好地發(fā)揮人在計(jì)算機(jī)中的主控地位。

(東華大學(xué)于海燕副教授，上海交通大學(xué)蔡鴻明、柳偉副教授，大連理工大學(xué)王子茹教授參與了討論，特致謝意。)

[1] 中國圖學(xué)學(xué)會(huì). 2012-2013圖學(xué)學(xué)科發(fā)展報(bào)告[R]. 北京:中國科學(xué)技術(shù)出版社, 2014.

[2] 何援軍, 童秉樞, 丁宇明, 等. 圖與圖學(xué)[J]. 圖學(xué)學(xué)報(bào), 2013, 34(4): 1-10.

[3] 于海燕, 蔡鴻明, 何援軍. 圖學(xué)計(jì)算基礎(chǔ)[J]. 圖學(xué)學(xué)報(bào), 2013, 34(6): 1-6.

[4] 何援軍. 一種基于幾何的形計(jì)算機(jī)制[J]. 圖學(xué)學(xué)報(bào), 2015, 36(3): 1-10.

[5] 何援軍, 王子茹. 談?wù)剤D學(xué)教材[J]. 圖學(xué)學(xué)報(bào), 2015, 36(6): 819-827.

[6] 何援軍. 計(jì)算機(jī)圖形學(xué)[M]. 2版. 北京: 機(jī)械工業(yè)出版社, 2009: 1-9.

[7] Miller J R. Vector geometry for computer graphics [J]. IEEE Computer Graphics and Applications, 1999, 19(3): 66-73.

[8] Duckworth T, Roberts D J. Accelerated polyhedral visual hulls using opencl [C]//IEEE Virtual Reality Conference. New York: IEEE Press, 2011: 203-204.

[9] 何援軍. 幾何計(jì)算[M]. 北京: 高等教育出版社, 2013: 1-19.

[10] 何援軍. 幾何計(jì)算及其理論研究[J]. 上海交通大學(xué)學(xué)報(bào), 2010, 44(3): 513-517.

[11] 何援軍. 對(duì)幾何計(jì)算的一些思考[J]. 上海交通大學(xué)學(xué)報(bào), 2012, 46(2): 18-22.

[12] 吳文俊. 初等幾何判定問題與機(jī)械化問題[J]. 中國科學(xué), 1977, (7): 507.

[13] 吳文俊. 數(shù)學(xué)機(jī)械化——回顧與展望[J]. 系統(tǒng)科學(xué)與數(shù)學(xué), 2008, 28(8): 898-904.

[14] Ericson C. Triangle-triangle teste, plus the art of benchmarking [EB/OL]. [2016-04-15]. http:// realtimecollisiondetection.net/blog/?p=29.2007,9.12,File d under Robustness, from hell, Code.

[15] Atiyah M. 二十世紀(jì)的數(shù)學(xué)[J]. 數(shù)學(xué)譯林, 2002, (1): 1-24.

[16] 將幾何代數(shù)化的數(shù)學(xué)家——笛卡兒[EB/OL]. [2016-04-15]. http://bbs.matwav.com/archiver/? tid-137115.html.

[17] 劉克明, 楊叔子. 畫法幾何學(xué)的歷史及其現(xiàn)代意義——紀(jì)念蒙日畫法幾何學(xué)公開發(fā)表 200周年[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 1998, 28(3): 281-288.

[18] 霍 金. 時(shí)間簡(jiǎn)史——從大爆炸到黑洞[M]. 許明賢,吳忠超, 譯. 長春: 北方婦女兒童出版社, 2003: 1-5.

[19] 張景中. 幾何問題的機(jī)器求解[J]. 科學(xué), 2001, (2): 20-23.

[20] 百度百科. 馮諾依曼體系結(jié)構(gòu)[EB/OL]. [2016-04-15]. http://baike. baidu.com/view/7719.htm.

[21] 章 義, 于海燕, 何援軍. 二維布爾運(yùn)算[J]. 上海交通大學(xué)學(xué)報(bào), 2010, (11): 1486-1490.

[22] Yu H Y, He Y J. 3D geometrical intersection based on dimension reduction [C]//The 15th International Conference on Geometry and Graphics (ICGG 2012 Montréal, Canada), 2012: 8.

[23] Yu H Y, He Y J. Geometric computing based on computerized descriptive geometry [J]. Computer Aided Drafting, Design and Manufacturing (CADDM), 2011, 21(2): 55-61.

[24] Yu H Y, He Y J, Wang Y X. Evaluation on triangle-triangle intersection tests algorithms [C]//The 16th International Conference on Geometry and Graphics (ICGG 2014, Innsbruck, Austria), 2014: 8.

[25] Lin W, Yu H Y, He Y J. A preliminary framework for geometric basis computing pattern [C]//Proceedings of the 2010 IEEE International Conference on Progress in Informatics and Computing. New York: IEEE Press, 2010: 710-713.

[26] 于海燕, 何援軍. 空間兩三角形的相交問題[J]. 圖學(xué)學(xué)報(bào), 2013, 34(4): 54-62.

Graphics and Geometry

He Yuanjun
(Department of Computer Science & Engineering, Shanghai Jiao Tong University, Shanghai 200240, China)

The relationships between graphics and geometry are discussed in this paper. From the view that shape is the source of the graph, the drawing/image are fundamentally constructed by geometric elements, thus the process of generation, representation, processing and propagation of drawing/image could be regarded as some operations of definition, transformation and interrelation of geometric elements. Therefore, it can be concluded that geometry is the basis of graphics and its theory, and meanwhile geometric computing is also the basis of graphics computing. Then, based on the analysis of graphics and its computing fundamentally, the essence, contradiction and key technologies of graphics computing are presented. The respective roles and advantages/disadvantages of algebra and geometry, emphasizing the leading status of human in the design of algorithms are also discussed. Moreover, the generation of a drawing or a model depends more on the relations between their elements than the elements themselves. Since the drawing/images have become the major objects and representation in graphics computing, a geometry-based shape calculation mechanism is introduced to fix the shortage of normal numerical calculation mechanism, so as to pursuit a new mode of geometric computing as thinking by shape while computing by number.

graphics; geometry; geometric computing; numerical computing; shape computing

TP 391

10.11996/JG.j.2095-302X.2016060741

A

2095-302X(2016)06-0741-13

2016-05-03；定稿日期：2016-06-19

何援軍(1945-)，男，浙江諸暨人，教授，博士生導(dǎo)師。主要研究方向?yàn)镃AD/CG、幾何計(jì)算。E-mail：yjhe@sjtu.edu.cn