何援軍

（上海交通大學(xué)計算機系，上海 200240）

一種基于幾何的形計算機制

何援軍

（上海交通大學(xué)計算機系，上海 200240）

提出一種幾何問題幾何化的形計算機制。它綜合了幾何、代數(shù)、畫法幾何及現(xiàn)代計算工具等理論、方法與技術(shù)，實現(xiàn)“三維思維，二維圖解，一維計算”多維空間的融合。從更宏觀的幾何角度構(gòu)筑算法框架，是對常規(guī)數(shù)計算的補充，可用于相當(dāng)寬泛的一類幾何計算。

幾何；幾何計算；數(shù)計算；形計算

中國圖學(xué)學(xué)會2013年發(fā)布《圖學(xué)學(xué)科發(fā)展報告》[1]，認為需要在已有的工程圖學(xué)、計算機圖形學(xué)和計算機圖像學(xué)學(xué)科基礎(chǔ)上建立大“圖學(xué)”學(xué)科。這個結(jié)論是基于“形”的概念——它們研究的對象都是形，形的表示與表現(xiàn)。該報告詳細闡述了“圖”和“形”的關(guān)系，認為形是客觀世界與虛擬世界的表示和構(gòu)造，圖是形在畫面上展現(xiàn)。形的屬性是表示，圖的屬性是表現(xiàn)。形是圖之源，圖展示形，是形的載體、形之表現(xiàn)。在計算機背景下，圖學(xué)的主要工作就是由圖顯示形，由圖構(gòu)造形，以及由一張圖變成另一張圖。這是對圖學(xué)科學(xué)與圖學(xué)學(xué)科表述與定位的首次嘗試。在這個基礎(chǔ)上，《圖學(xué)學(xué)科發(fā)展報告》對圖學(xué)科學(xué)的理論基礎(chǔ)、計算基礎(chǔ)、應(yīng)用基礎(chǔ)以及近期的研究方向等重大問題作了闡述。其中，揭示形的幾何品質(zhì)，認識幾何與幾何計算在圖學(xué)中的地位和作用的根本性，從形的角度去統(tǒng)一、去研究、去發(fā)展圖學(xué)的基礎(chǔ)理論和基本方法的研究是最基礎(chǔ)性的論述。

根據(jù)《圖學(xué)學(xué)科發(fā)展報告》的觀點，圖學(xué)的基本工作是研究“形→圖”和“圖→形”之間的轉(zhuǎn)換，因此，其本質(zhì)是幾何，最根本的理論基礎(chǔ)是幾何學(xué)?；诖耍疚奶岢鲆环N基于幾何概念的“形計算”機制，以更好適應(yīng)于對形的處理，它的核心思想是幾何問題幾何化。相對于現(xiàn)有的“數(shù)計算”機制是基于數(shù)的運算，形計算是一種基于幾何的運算機制，更有利于形的表述、圖的生成，更能發(fā)揮人的空間概念在構(gòu)建算法中的主導(dǎo)作用，從更宏觀的角度去構(gòu)建算法框架，使計算過程更加結(jié)構(gòu)化、直觀化、簡單化。既可比較明顯地改善數(shù)計算的非可讀性，也有利于降低計算的復(fù)雜度、提升計算的穩(wěn)定性。

本文將簡述這種形計算機制的理論基礎(chǔ)、基本框架、實施方法與執(zhí)行效果。還將論述一些計算在社會發(fā)展中的地位、計算的基礎(chǔ)、計算方法學(xué)、計算方式與解的表述等。討論圖、形、幾何與幾何計算的關(guān)系問題，揭示幾何計算的本質(zhì)與關(guān)鍵，關(guān)注問題空間與計算空間的不統(tǒng)一問題等等，作為提出形計算機制的支撐。

1 計算

1.1 計算與它的作用

在人類的社會進步、經(jīng)濟建設(shè)和科技發(fā)展過程中，“計算”始終都扮演著非常重要的角色。“X計算”已是計算機廣為應(yīng)用的一個概念，例如，科學(xué)計算、網(wǎng)格計算、平行計算、智能計算、云計算等。

計算主義者指出“生命的本質(zhì)不在于具體的物質(zhì)，而在于物質(zhì)的組織形式；這種組織完全可以用算法或程序表達出來，所以，只要能將物質(zhì)按著正確的形式構(gòu)建起來，這個新的系統(tǒng)就可以表現(xiàn)出生命?！盵2]而這種所謂的“正確的形式”就是生命的算法或程序。所以，算法是把非生命和生命連接起來的橋梁，是生命的靈魂。這足以說明計算在社會生活與社會發(fā)展中的重要作用。

1.2 計算的理論基礎(chǔ)

計算的基礎(chǔ)是數(shù)學(xué)。數(shù)學(xué)是永恒的！好的數(shù)學(xué)思想很少會過時，雖然運用方式會發(fā)生很大變化。數(shù)學(xué)上主要有兩種推理：符號推理與直觀推理，前者源于計數(shù)制，后者源于圖形制。繼數(shù)之后，圖形將數(shù)學(xué)的第二個主要概念引入了數(shù)學(xué)，這就是形，形能充分發(fā)揮人的空間思維特長。歐幾里德[3]在幾何著作中首次系統(tǒng)地使用了圖形，少量使用符號，大量使用邏輯。他的著作結(jié)合了兩種創(chuàng)新：圖形的使用和證明的邏輯結(jié)構(gòu)。因此，計算的對象有2種：數(shù)和形，它們分別基于數(shù)學(xué)的2個基礎(chǔ)科學(xué)——代數(shù)與幾何。

代數(shù)是研究數(shù)的科學(xué)。代數(shù)計算以數(shù)為計算對象，常需要公式推導(dǎo)、表達式的化簡、函數(shù)的微分及積分、精確地解各種方程等。17-18世紀(jì)中期，代數(shù)學(xué)被理解為在代數(shù)符號上進行計算的科學(xué)，用來研究與解方程有關(guān)的問題。到 19世紀(jì)末，代數(shù)學(xué)從方程理論轉(zhuǎn)向代數(shù)運算的研究。

幾何是研究形的科學(xué)。其用人們公認的一些事實列成一些定義和公理，以形式邏輯的方法，用這些定義和公理來研究各種幾何圖形的性質(zhì)，從而建立了一套從公理、定義出發(fā)，論證命題得到定理的幾何學(xué)論證方法，形成了一個嚴密的邏輯體系——幾何學(xué)。幾何學(xué)原來的論證方法一直是純幾何的。

代數(shù)學(xué)者更是一個形式主義者，要的是公理化、形式化，追求嚴格的、形式的描述。幾何與物理學(xué)者以幾何與拓撲的思想作為基本洞察工具，更關(guān)心物理內(nèi)蘊的表現(xiàn)形式。很清楚，兩者屬于不同的傳統(tǒng)。

當(dāng)然，計算與工具有關(guān)，當(dāng)今的計算工具主要是計算機，因此，與計算機有關(guān)的硬件、軟件以及應(yīng)用理論也都是計算的基礎(chǔ)。但是，主要的應(yīng)該是代數(shù)與幾何。

1.3 計算對象與結(jié)果

計算的對象與結(jié)果實質(zhì)上與計算的性質(zhì)、實體和工具等有關(guān)，不同的計算層面，有不一樣的計算對象，需要不同的計算結(jié)果。

以往，人們習(xí)慣于得到一個明確的數(shù)字為解。一般的計算均是基于數(shù)的，其計算源與計算結(jié)果都是數(shù)，可稱為數(shù)計算，數(shù)計算曾是科學(xué)計算的主要計算機制。數(shù)計算涉及到一個數(shù)的機制。最常用的是十進制，但也有例外，例如早期一市斤是16兩，這是16進制。計算機的設(shè)計是基于電路的開/關(guān)機制，表達成數(shù)字就是0/1，這導(dǎo)出了2進制、8進制等。目前在計算機中采用的是馮·諾依曼[4](John von Neumann, 1903-1957年)的二進制數(shù)制表示浮點數(shù)，基于這樣的浮點數(shù)實現(xiàn)數(shù)的計算。

下棋、指揮打仗等也都需要計算，但這些計算本質(zhì)上已經(jīng)變成“算計”了，其計算對象和計算結(jié)果與常規(guī)意義上的數(shù)計算大相徑庭。

現(xiàn)在，圖形、圖像在人們生活中的應(yīng)用大有普及趨勢，計算的結(jié)果是希望得到一幅由圖形或圖像表示的畫面。這樣的計算，遍地都是。圖形，不管是靜態(tài)的還是動態(tài)的，都作為解的一種表現(xiàn)形式去追求，對圖或者形作為計算源與計算結(jié)果的需求大大增加。

計算機作為主要計算工具以后，計算方式與解的表述更是起了革命性的變化。例如，“算法”常作為計算機時代解的一種表述方式被認可、被追求，相應(yīng)的計算理論與計算方法也產(chǎn)生了。

現(xiàn)代意義上的計算，它不僅可以是常規(guī)意義上的一次“算”，也可能是一個過程，搜索過程、決策過程等。因此，計算對象可能并非一個，結(jié)果也不一定是一個，甚至是不確定的。但是，萬變不離其宗，用于表述計算對象與結(jié)果的，主要的還是兩種：數(shù)和圖。

1.4 數(shù)計算與形計算

代數(shù)管數(shù)，幾何管形。數(shù)引出數(shù)計算，形可否引出形計算？

其實，形計算早已有之，在希臘科學(xué)中幾何學(xué)是占統(tǒng)治地位的，其威力之大，以致于純算術(shù)或純代數(shù)的問題都被轉(zhuǎn)譯為幾何語言：量被解釋為長度，兩個量之積解釋為矩形、面積等。現(xiàn)代數(shù)學(xué)中仍保留的稱二次冪為平方，三次冪為立方就源于此[5-7]。在歐幾里德《幾何原本》[3]中有五條公理和五條公設(shè)作為形計算的基礎(chǔ)，人們在公理體系內(nèi)對幾何關(guān)系進行推理和計算。畫法幾何的尺規(guī)作圖方法也是只用了幾種最基本的作圖方法就可完成一大類圖形的作圖。這些，本質(zhì)上就是一種形計算。

由此，計算不應(yīng)該只是數(shù)計算，還應(yīng)該有形計算。

1.5 計算的關(guān)鍵

一種計算方法的提出，一個算法的設(shè)計首先要考慮的因素就是較高的穩(wěn)定性，較低的復(fù)雜性，再考慮易讀性、可交流性等伴隨要求。計算的復(fù)雜度與穩(wěn)定性是計算的兩個關(guān)鍵問題，也是圖形計算中的關(guān)鍵問題。

計算復(fù)雜度包括空間復(fù)雜性和時間復(fù)雜性?？臻g復(fù)雜性一般指表述對象所需要的空間，時間復(fù)雜性則是指計算的工作量問題。常從量與質(zhì)兩個方面去降低計算的復(fù)雜度，或減少計算對象的數(shù)目，或降低參與計算對象的復(fù)雜度。隨著計算機硬件的發(fā)展，質(zhì)的問題更嚴重、更重要。

計算穩(wěn)定性問題是一個長期的難題，本質(zhì)是計算正(準(zhǔn))確性問題。即使在一些已被廣泛使用的大型應(yīng)用系統(tǒng)中，也存在幾何引擎的穩(wěn)定性問題。這里有理論問題，也有實施問題。導(dǎo)致幾何計算不穩(wěn)定主要有兩個原因：一是由數(shù)字計算誤差引起，通常與數(shù)制及計算方法有關(guān)；二是由幾何本身原因引起，因幾何間的重疊(共點、共線、共面等)引起的幾何奇異而造成判斷的不確定性。Christer Ericson[8]曾對那些只偏重速度、忽視穩(wěn)定性的研究方法表示擔(dān)心，覺得“這只是減少了浮點運算”。并認為用一些大規(guī)模隨機測試很難檢測到影響算法魯棒性的狀況。

1.6 計算的方法論

數(shù)學(xué)是研究現(xiàn)實世界的“數(shù)”與“形”的科學(xué)，一般認為幾何研究形，代數(shù)研究數(shù)。作為數(shù)學(xué)的兩個重要基本組成部分，幾何與代數(shù)各有其自己的發(fā)展空間和問題域，對應(yīng)的也有其自己的理論基礎(chǔ)和方法學(xué)[5-7]。

白馬非馬，畫法幾何一直作為工程設(shè)計的理論基礎(chǔ)，與傳統(tǒng)的幾何好像相離甚遠，也似乎沒有人將他列入幾何的范疇。其實，畫法幾何研究的基本對象也是幾何，也是研究形的學(xué)科。因此，在討論幾何計算時，也應(yīng)該將畫法幾何列入幾何計算的基礎(chǔ)理論與基本工具，構(gòu)建“大幾何”概念。

1.6.1 幾何代數(shù)化之路

宇宙，一切空間和時間的綜合。宇是空間，宙是時間，合為宇宙。

代數(shù)涉及的是時間的操作[6]。代數(shù)的目標(biāo)總是想建立一個公式，就是拿來一個有意義的東西，把它化成一個公式，然后得到答案。采用線性、有序的方式去處理問題，一連串的運算被一個接著一個地進行。它更偏重于定量地去得到結(jié)果，本質(zhì)上不會再思考其含義，停止用幾何、圖形或物理的觀念去考慮問題。求解過程一般不直觀、不可讀，常使得人的空間思維特長蕩然無存，計算常常會變得不可掌控。

幾何涉及的是空間問題[7]。幾何更多的是從空間概念形象地去審視問題，常用幾何間的相互關(guān)系處理問題。人們努力將一些問題歸結(jié)為幾何形式，借助于圖形(模型)的直觀，從總體上去構(gòu)建一個總體框架，去尋求一個全局、直觀的解決方案。它更偏重于定性地去得到一個結(jié)果，而將枯燥的數(shù)字與反復(fù)的代數(shù)計算分離給計算機去做，求解過程更宏觀、更直觀。使復(fù)雜問題簡單化，抽象問題具體化，化難為易，獲得簡便易行的成功方案。

17世紀(jì)初，笛卡兒[9]將坐標(biāo)引入幾何，把代數(shù)中形式化符號體系的表示方法引進到幾何學(xué)中，實現(xiàn)了數(shù)與形的緊密結(jié)合，使得幾何間的計算也能用代數(shù)的形式實現(xiàn)，人稱“幾何代數(shù)化”。這是數(shù)學(xué)史上最豐富和最有效的創(chuàng)造之一，但也使幾何與代數(shù)之間出現(xiàn)了一種令人感到不太自然的關(guān)系。

在笛卡兒把代數(shù)中形式化符號體系的表示方法引進到幾何學(xué)之后，走的基本上是幾何代數(shù)化之路?？v觀歷史，幾何與代數(shù)原本分別考慮“形”和“數(shù)”的問題，理論上應(yīng)該各占半壁江山，然而，歷史并不是這樣，兩者并不平衡。我們不能改變歷史，但是，我們是不是應(yīng)該能從歷史中學(xué)到一些什么？

1.6.2 代數(shù)化還是幾何化

先看一個簡單的例子，求通過P1、P2和P3三點的圓?？梢酝ㄟ^解三元二次方程得到所求圓圓心為：

兩式不足之處十分明顯：算式十分復(fù)雜，而當(dāng)兩式的分母為0時，要輪換點再算，即給出的3點是共點、共線的奇異情況的排除并非顯而易見。

但是，如果上面的問題改用幾何方法就變?yōu)椋?/p>

(1) 作 P1P2的垂直平分線 L1，作 P1P3的垂直平分線L2。共點的情況可在這一步排除。

(2) 求L1與L2的交點即為圓心。如果無交點，則說明三點共線，無圓可生成。

(3) 圓心和三點中任一點的距離即為半徑。

可以看到，從幾何的角度，用模擬原始的尺規(guī)作圖方法解決幾何計算問題直觀性強、效率很高，奇異情況表現(xiàn)明顯、排除簡潔。

其實，還有一些問題困擾著純代數(shù)方法，如不必要的復(fù)雜度、需要較復(fù)雜的數(shù)學(xué)計算工具、算法時間性能低下、無法完美處理奇異性問題等。

面對一個幾何問題，是首先考慮如何將它化成一個代數(shù)方程(公式)，送到計算機里，“搖一搖”就得到結(jié)果，而不管過程如何復(fù)雜；還是順其自然，回歸幾何，設(shè)法發(fā)揮人的直覺，先從空間的角度審視一個幾何問題，尋求一個全局、直觀地解決方案？這將挑戰(zhàn)數(shù)百年來大部分人們的思考習(xí)慣。

1.6.3 以“形”統(tǒng)一幾何與畫法幾何理論

畫法幾何研究的基本對象也是幾何，也是研究形的科學(xué)。17世紀(jì)一些幾何學(xué)家將它的方法與結(jié)論視為歐幾里德幾何學(xué)的一部分，直到 1799年法國幾何學(xué)家蒙日[10](Gaspard Monge, 1746-1818年)非數(shù)學(xué)地闡述了投影理論，才使畫法幾何(descriptive geometry)成為一門獨立學(xué)科。應(yīng)該從形的角度去揭示畫法幾何與幾何的共性問題，將其應(yīng)用于幾何計算。反過來，這又為畫法幾何計算化提供了一條新途徑。

2 形與形的計算

由于一般的計算都是采用數(shù)計算機制，至少，計算的實施過程是基于數(shù)計算機制。這使得對形的計算過程變得有點復(fù)雜：“形→數(shù)”→“數(shù)計算”→“數(shù)→形”。這樣，人的大量工作就會花在“形→數(shù)”和“數(shù)→形”的轉(zhuǎn)換上，這不符合人的思維習(xí)慣。其實，數(shù)學(xué)主要發(fā)生于幕后，起關(guān)鍵作用的是人，人的思維、人的邏輯?！敖换ァ毕到y(tǒng)的產(chǎn)生，就是充分考慮了在計算機快速中發(fā)揮人的直觀感知能力的作用，這是一個很大地進步。張景中[11]認為，“幾何解題是十分有吸引力的智力活動之一。圖形的直觀簡明，推理的曲折嚴謹，思路的新穎巧妙，常給人以科學(xué)美的享受。”這是符合事實的。

在許多應(yīng)用領(lǐng)域，對一個問題的求解可描述為如圖1所示的過程。

圖1 問題的求解過程

(1) 提出問題；

(2) 通過建模表達問題，使問題抽象化；

(3) 用一個幾何模型去表示問題；

(4) 將幾何模型生成圖形/圖像，使問題可視化；

(5) 根據(jù)生成的圖形/圖像進一步理解問題，從中思考解決方法。

人們常利用自己的空間直覺(spatial intuition)或者空間知覺(spatial perception)從總體上去考慮問題的解決方案，習(xí)慣于從幾何的角度去考慮幾何問題。努力將一些問題歸結(jié)為幾何形式，因為這樣可以使用人的直覺，直覺是人類最有力的武器。

引入形計算機制，最核心的思想就是幾何問題幾何化。形計算機制是一種基于幾何的計算概念與機制，它以幾何作為計算單元，以求取幾何間的關(guān)系作為計算目標(biāo)。從形的角度去揭示畫法幾何與幾何的共性問題，將其應(yīng)用于幾何計算中。探索以形為核心，將幾何、畫法幾何、代數(shù)和計算機等多學(xué)科理論與方法的長處融合在一起，實現(xiàn)“從形思考、以數(shù)實施”，更好發(fā)揮人的思維與計算機計算各自的特長。

2.1 圖、形、幾何與幾何計算

世界由形構(gòu)造，形由圖在畫面上顯示，因此，形是圖之源。在計算機中，形與圖均由幾何描述，這里的幾何是點、線、面，常被稱為“幾何元”，不同的幾何元依照一定的拓撲關(guān)系構(gòu)造成不同的場景，在空間構(gòu)造形；通過投影在平面顯示圖，此時，點、線常被稱為“圖元”，不同屬性圖元的組合構(gòu)造了所有的圖形或圖像。

用兩個典型的例子說明圖、形、幾何與幾何計算的關(guān)系。

隱藏線消除是將形顯示為圖的典型算法。消隱過程是一條一條線的輸出，每條線需與場景中所有物體（面）進行比較，線的各可見部分的交集即為此線的最終可見部分。因此，整個場景的輸出（顯示）過程就是一條一條地去確定場景中所有線條的哪些部分該顯示，哪些部分不該顯示。這本質(zhì)上是對幾何——一條條線段的分割工作。

真實感圖形繪制則是將形顯示為圖像的典型算法。這是一個光強與色彩的量化、紋理映射、圖像合成、幀緩存等基于物理、光學(xué)、色彩理論和技術(shù)的復(fù)雜計算過程。這里，貫穿整個算法的關(guān)鍵計算是從光源發(fā)出的每一條光線與景物表面的空間線面的求交，包括反射和折射計算。這些，也都是幾何間的求交、比較工作。

基于以上分析，本質(zhì)上，圖、形、幾何與幾何計算的關(guān)系可以簡單地表述為：形是表示、是輸入，圖是展現(xiàn)、是輸出；形與圖的基本元素是幾何，形構(gòu)造與圖形成的本質(zhì)都是幾何的定義、構(gòu)造、度量和顯示。

2.2 模型與圖形的本質(zhì)

模型與圖形的本質(zhì)也決定于幾何之間的相互關(guān)系。下面用兩個簡單例子說明這個論點。

圖2(a)表示平面上由4個點構(gòu)造的矩形，它們的拓撲關(guān)系為1-2-3-4-1。圖2(b)是保持拓撲關(guān)系而改變其中一個點P3的幾何參數(shù)，它仍能揭示原圖的基本構(gòu)圖形狀。而圖2(c)的4個圖形僅改變了4個點之間的連接關(guān)系，幾何參數(shù)相同的點因拓撲關(guān)系的不同而構(gòu)成了完全不同的圖形。

圖3左上角12條線段顯示的是一個三維空間框架，如果對這些線段施以不同的裁剪，就得到圖3中不同的圖(這里列舉了5個)。這些圖反映在人們大腦中是不同的形，或是實心的、或是空心的、或是盒子等。這里，空間線的幾何參數(shù)并沒有改變，只是用線的不同部分去構(gòu)成圖形而已，本質(zhì)上也是幾何間的拓撲關(guān)系改變了，導(dǎo)致展現(xiàn)出不同的形。

圖2 幾何參數(shù)和拓撲關(guān)系的改變對圖的影響

圖3 幾何元的不同部分展現(xiàn)了不同的形

因此，模型與圖形的本質(zhì)不是構(gòu)成它們的幾何本身，而在于幾何間的組織形式，決定于幾何之間的相互關(guān)系。

2.3 圖形計算的矛盾與關(guān)鍵

2.3.1 圖形計算的基礎(chǔ)是幾何求交

圖形生成、幾何造型，那怕是直線、曲線，平面、曲面，最基本的操作是幾何的定義與求交。在一個典型的幾何造型系統(tǒng)中，用到的幾何元素通常有25種，為了建立一個通用的定義與求交函數(shù)庫，所要完成的求交函數(shù)約為種！幾何的構(gòu)造、定位和度量工作雖然千變?nèi)f化，但都基于這些少量的基本幾何函數(shù)，它們是幾何計算的基石，起了“基”的作用。

2.3.2 幾何空間與計算空間的不統(tǒng)一

工程技術(shù)人員都有過用三視圖表示空間物體以及從三視圖得到立體圖這樣訓(xùn)練的經(jīng)歷，這是由于實體空間(三維)與表示空間(平面)的不統(tǒng)一。人們知道，形是二維及以上的，圖是二維的，而計算是一維的。因此在設(shè)計一個算法時存在這種不統(tǒng)一，即算法的思維空間與實施(計算)空間是不一致的。這增加了在設(shè)計算法時思維的復(fù)雜性，甚至?xí)霈F(xiàn)某些混亂。顯然，直接從二維乃至三維去考慮問題無疑會減少算法設(shè)計的復(fù)雜性，因為，算法的設(shè)計與最后的數(shù)字計算并不一定非要捆綁的。

遺憾的是，人們常常忽視這個幾何空間與計算空間不統(tǒng)一的矛盾，長期以來人們大多使用的方式——“用一維計算處理二維甚至三維問題”。正如吳文俊[12]總結(jié)數(shù)學(xué)機械化的實質(zhì)是“把質(zhì)的困難轉(zhuǎn)化為量的復(fù)雜”一樣，人們習(xí)慣于這樣的復(fù)雜。

2.3.3 幾何奇異是幾何計算不穩(wěn)定性的主要原因

幾何計算的不穩(wěn)定主要由數(shù)字計算誤差或幾何本身引起。由于所處理的模型通常是有界的，幾何元素也變成有界的，兩幾何間的交點會處于共點、共線、共面等奇異狀態(tài)。這會導(dǎo)致幾何計算的錯誤，造成幾何造型系統(tǒng)的不穩(wěn)定，這是幾何計算的主要困難，處理不好往往導(dǎo)致系統(tǒng)的崩潰。幾何奇異的處理涉及到兩個問題：一是幾何奇異的判定；二是對已知幾何奇異的處理。現(xiàn)在對幾何奇異的判定常由數(shù)計算實現(xiàn)，依賴于某個公差 ε，這涉及計算數(shù)學(xué)近似計算理論以及計算機的浮點運算。對已判定的幾何奇異，因為幾何奇異的本質(zhì)是幾何關(guān)系的奇異，從幾何角度去判定反而會直觀些。

2.3.4 降維計算是降低幾何復(fù)雜性的有效手段

在一些大型、實時的應(yīng)用場合，計算效率會影響到系統(tǒng)的應(yīng)用。形計算將探索采用畫法幾何投影理論與2D/3D對應(yīng)理論實現(xiàn)降維計算。建立解的空間與平面的映射關(guān)系，將空間問題轉(zhuǎn)化為2個或3個平面問題，分而治之。計算機圖形學(xué)中的梁-Barsky裁剪算法[13]的本質(zhì)就是采用降維方法把二維裁剪分解為2次一維裁剪，將三維裁剪分解為2次二維裁剪，既降低了幾何復(fù)雜度，也增加計算的穩(wěn)定性。

3 形計算機制

3.1 形計算的基本概念

不能完全按照數(shù)計算機制常規(guī)概念去理解形計算，即不能嚴格的照搬數(shù)計算機制的模式一樣去定義、去理解形計算。形計算更多的是在思考層面，而不是在實施層面。它以直線、圓等幾何元的定義、相交等基本運算作為基礎(chǔ)，考慮、規(guī)劃幾何問題的求解策略。引入了“幾何數(shù)(geometric number)”和“幾何基(geometric basis)”兩個概念，在這個基礎(chǔ)上構(gòu)建形計算的基本架構(gòu)如下[14-16]：

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

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

(3) 引入幾何基，構(gòu)建基本幾何的定義、相交等的基本工具，作為形計算的初始幾何基(它將繁復(fù)的代數(shù)計算隱藏在幾何基中)。

(4) 對平面問題，對圖形進行構(gòu)造性求解(參考尺規(guī)作圖)，求得的幾何基序列記錄了構(gòu)造過程，也得到了以“幾何基序列表述”的平面解(這同時構(gòu)成了一個更高一級幾何基)。

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

相對于數(shù)計算，這種形計算機制盡可能的用幾何方法去處理幾何問題，更偏重于從形的整體角度去構(gòu)建一個算法框架。在簡化問題的描述、降維計算以及降低計算復(fù)雜度等方面能補充數(shù)計算的不足。對數(shù)計算的非可讀性、幾何奇異引起的計算不穩(wěn)定性等方面也有較大的改善。這是對數(shù)計算機制的一種很好的輔助，是在人的思維掌控下，能將幾何、代數(shù)及計算機理論、方法與技術(shù)更好結(jié)合的新計算方法(機制)的一種探索。

3.2 形計算的理論基礎(chǔ)

下面簡述在圖形/幾何計算中引入形計算的主要理論基礎(chǔ)，一些最基本、最基礎(chǔ)的常用理論。

(1) 畫法幾何的理論。畫法幾何研究的基本對象是幾何，它的理論基礎(chǔ)是投影幾何，也是研究形的科學(xué)。不同于數(shù)學(xué)上的幾何偏重于解析方法，它以綜合法得到一些定性的關(guān)系，用幾種最基本的作圖方法就可完成平面上一類圖形的作圖，這就是所謂的“尺規(guī)作圖”理論。尺規(guī)作圖本質(zhì)上是用幾何方法處理幾何問題，而且這種原始的尺規(guī)作圖的基本工具很少，一般認為只有8種：作一條線段等于已知線段、作一個角等于已知角、作已知線段的垂直平分線、作已知角的角平分線、過一點作已知直線的垂線、已知一角/一邊做等腰三角形、已知兩角/一邊做三角形以及已知一角/兩邊做三角形等。它最樸素的思想是將復(fù)雜的幾何問題分解成有序的、簡單的基本幾何問題。這是一個很好的思想，引入幾何基的原始想法就出于此。

畫法幾何常采用正投影辦法，用3個平面視圖去表述一個三維物體，由尺規(guī)作圖得到其視圖。反之，也可由3個平面視圖還原三維物體，即所謂的“2D/3D對應(yīng)”理論。尺規(guī)作圖走的是幾何化之路，偏重于定性而不是定量地考慮問題。2D/3D對應(yīng)等理論使空間問題降為平面問題，有可能降低空間問題計算的復(fù)雜性。形計算的降維充分利用了畫法幾何的投影。

(2) 向量理論。形或者圖形的本質(zhì)不是幾何元本身而是幾何元的組織形式。因此，僅僅用幾何信息去表示幾何元是不夠的，因為這只能表述幾何本身，不能表述幾何間的相互關(guān)系。這就需要一些屬性信息去補充幾何元之間關(guān)系的表述。例如，圖形的一條邊界應(yīng)該有外邊界與內(nèi)邊界之分，即需要有一個屬性信息去表出該邊界的哪一側(cè)是圖形的內(nèi)部、哪一側(cè)是外部？而在三維空間，屬性信息能表達出物體的內(nèi)部或外部、平面的正面或反面等。更甚，對交點，關(guān)心的不僅僅只是它的幾何位置信息，更關(guān)心交點在兩個幾何關(guān)系中的作用，例如，這個交點對另一邊界是“入點”還是“出點”，因為這直接關(guān)系到圖形運算的過程與結(jié)果。

引入向量去表示線段是很有效的：向量有方向，使邊界能很好地區(qū)分出左右，兩向量的旋向能決定它是入點還是出點等。這是在形計算中引入幾何數(shù)的基礎(chǔ)。

向量理論在形計算中的另一個應(yīng)用是變換的幾何化。平面上任意2條不共線相交向量構(gòu)成了一個坐標(biāo)系(在空間則是 3條不共面向量構(gòu)成一個坐標(biāo)系)，而笛卡爾將幾何代數(shù)化以后，使向量也可用數(shù)字的方式表出和運算。利用這2個性質(zhì)以及矩陣論，可對變換實施幾何化。

(3) 高等代數(shù)理論。高等代數(shù)線性空間理論中的“任一向量可以用它的基底線性表出”思想也是引入幾何基的一個理由之一。

利用齊次坐標(biāo)與矩陣理論實施幾何變換也源于高等代數(shù)理論。

(4) 算法理論。計算機的發(fā)展使解的結(jié)果表述出現(xiàn)了很大的變化，例如，一個算法就是解的表述形式，而且，在一個算法中，可能還得到了多個希望的結(jié)果。包含一個算法之中可有許多計算，幾何運算、代數(shù)運算、邏輯運算等。這正是需要的結(jié)果：一個算法對外就是一個幾何基，但是，它將復(fù)雜的過程包含在其中了，而對外(對設(shè)計者或應(yīng)用者而言)，只是一個極其簡單的結(jié)果——一個幾何基而已。這使得解決一個復(fù)雜問題的框架變得相當(dāng)簡單、十分清晰。

另一方面，隨著幾何基的層層構(gòu)建、逐漸擴展，形計算的基礎(chǔ)也變得越來越扎實，工具越來越多，解決問題的方法會變得越來越多。

3.3 形計算的框架

形計算的核心是幾何問題幾何化，需要厘清幾何與代數(shù)、計算機、畫法幾何等的關(guān)系，綜合這些理論與知識、思想和方法去構(gòu)建形計算的理論架構(gòu)，采用合適的表示與結(jié)構(gòu)去構(gòu)建形計算的實施框架。簡化求解過程，便于解的表述與傳遞，形成統(tǒng)一、規(guī)范的形計算體系。探索一種發(fā)揮幾何直觀、簡潔特點的幾何化求解方法，追求形、數(shù)結(jié)合的新突破。形計算的基本框架如下：

(1) 在幾何定義與幾何關(guān)系的表述中引入幾何數(shù)。天地萬物，陰陽而已。一個陽爻符號“－”與一個陰爻符號“--”書寫了一部易經(jīng)，“0”與“1”構(gòu)建了整個計算機體系，物理中電之“正/負”、電路之“開/關(guān)”，……，均乃陰/陽之分也。幾何定義之“左/右(向量)”、“內(nèi)/外(邊界)”、“進/出(交點)”，幾何關(guān)系之“離/交/切/含”、幾何度量之“正/負(面積)”、“逆/順(角度)”等何嘗不只是陰陽之分？借用了萊布尼茨“如果存在這樣一種代數(shù)，它可被稱為‘幾何代數(shù)’，它的元素可被稱為‘幾何數(shù)’”而用幾何語言進行幾何計算”[5]的宏偉設(shè)想中的“幾何數(shù)”一詞。在形計算中引入幾何數(shù)表示幾何的陰/陽兩極，它涉及幾何的表示、構(gòu)造、定位、度量及幾何間的關(guān)系處理各個方面，如：

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

· 對幾何的長度、面積、體積等引入正負(正/負)；

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

· 對幾何間的交點區(qū)分“入點/出點(負/正)”；

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

· 幾何間的連接遵照“皮帶輪法則”；

· 強調(diào)幾何在“標(biāo)準(zhǔn)坐標(biāo)系(計算坐標(biāo)系)”下描述與運算；

· 等等。

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

(2) 在幾何求解中引入幾何基。幾何基的引入吸取了畫法幾何尺規(guī)作圖、高等代數(shù)線性空間關(guān)于向量可用它的基底線性表出以及計算機算法的思想。由此，對幾何問題解的新解讀就變成：“幾何問題的解可由幾何基的序列表述”。幾何基的原始模型可以作以下抽象化的表述：幾何基是幾何元操作的抽象表示，一種對幾何元的原子操作，也是幾何關(guān)系的表現(xiàn)，它構(gòu)建了幾何解的基礎(chǔ)。

幸運的是，在最底層的幾何基數(shù)量很少，一般的幾何關(guān)系主要包括以下6種類型：相交、相切、平行、垂直、分比、內(nèi)含，這就可以使幾何基的構(gòu)建做到“精致、精確、簡單”。而且，由于對幾何誤差、幾何奇異的處理分散到這些原子操作之中，這會提升幾何引擎的穩(wěn)定性。由于幾何問題的解是用幾何基的序列標(biāo)出的，這增加了解的可讀性。最后，還可以用已有幾何基序列構(gòu)建高一層次的幾何基。這樣，幾何基構(gòu)建了幾何問題解的基礎(chǔ)——算法基礎(chǔ)和工具基礎(chǔ)。

最后，引出的另一個問題是，如何將一個幾何問題歸納成為幾何基的序列，甚至能夠自動或半自動的求取這個序列？也給這個思想提供了又一個發(fā)展空間。

(3) 幾何變換采用幾何化方法。幾何變換包括同維變換及降維變換，形計算中對幾何變換也實施幾何化[17]。

平面上任意兩條相交(不共線)的單位向量構(gòu)成一個新坐標(biāo)系，新、舊坐標(biāo)系間的坐標(biāo)變換可由兩條相交向量在原坐標(biāo)系下的直線方程系數(shù)及齊次項表出。

空間任意3個相交平面的單位法向量構(gòu)成一個新坐標(biāo)系，新、舊坐標(biāo)系間的坐標(biāo)變換齊次矩陣由3個相交平面的規(guī)格化方程系數(shù)及齊次表出。

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

(4) 計算時引入計算坐標(biāo)系。計算坐標(biāo)系的引入使點、線、圓、面，以及三角形、球面、錐面、柱面等基本幾何能在它們所謂的“標(biāo)準(zhǔn)坐標(biāo)系”下解析描述，這使幾何的表述與相交關(guān)系的求取更為簡單，空間幾何的降維也一般可在正投影下進行，表述簡潔，計算復(fù)雜度也常會降低。

3.4 形計算的實施

3.4.1 形計算的實施框架

形計算在空間層面整體考慮幾何問題的求解方案，實施框架如圖4所示。

(1) 幾何數(shù)協(xié)助表述二維和三維幾何及幾何間的關(guān)系，簡化求解過程；

(2) 二維圖形尋求由幾何基序列表述的解；

(3) 三維物體經(jīng)降維后化為1～2個二維圖形，在二維面上求解，最后將交點反變換得到三維解；

(4) 在幾何層面上考慮幾何奇異問題，通過對幾何數(shù)的簡單運算，解決之；

(5) 形計算實施過程中的所有變換實現(xiàn)幾何化。

圖4 形計算的實施框架

3.4.2 幾何基的構(gòu)筑

下面以一個最基礎(chǔ)、最簡單、最常用的幾何操作說明幾何基的設(shè)計(圖5)。

例：過兩點作直線的幾何基lpp()。兩點：P1(x1, y1)、P2(x2, y2)，直線L：ax+by+c=0。

圖5 過兩點作直線的幾何基

從畫法幾何角度看，這是一次通過2點作直線的尺規(guī)作圖。

從幾何角度看，這是基本幾何元(直線)的產(chǎn)生工具。

從代數(shù)角度看，這是一系列數(shù)字(值)運算，由一些已知變量得到另一些需求變量。

從計算機角度看，這是用計算機語言實現(xiàn)的一個算法(子程序)。

幾何基的構(gòu)造本身也是基于幾何化思路，具有幾何意義的，且以幾何操作的面目呈現(xiàn)。

3.4.3 變換幾何化的實施

以“向任意平面的投影”的例子來闡述變換幾何化的實施方法[18]。

在坐標(biāo)系Oxyz下任意給定有一共點的3個相交平面，a1x+b1y+c1z+d1=0，a2x+b2y+c2z+d2=0，和a3x+b3y+c3z+d3=0，且單位法向量分別是：n1=(a1, b1, c1)，n2=(a2, b2, c2)和n3=(a3, b3, c3)，這3個空間單位向量構(gòu)成一個新坐標(biāo)系O*x*y*z*（互相垂直時構(gòu)成直角坐標(biāo)系）。那么，新、舊坐標(biāo)系的坐標(biāo)變換矩陣分別為：

新、舊坐標(biāo)的變換式為：

(X*Y*Z*H*)=(x y z 1)Txyz_x*y*z*

(X Y Z H)=(x*y*z*1)Tx*y*z*_xyz

由于 3個向量是可以任意定義的(兩兩互相垂直仍是直角坐標(biāo)系)，這就可以任意構(gòu)建合適的計算坐標(biāo)系，也意味著可以任選投影平面，達到簡化計算。計算坐標(biāo)系的選取往往依賴于相關(guān)幾何元的性質(zhì)，可以參考某一個幾何為主建立(也決定了投影平面)，該幾何可作為“主元”，例如直線與球相交，以球為主元，圓錐與球求交，以圓錐為主元，等等。

3.4.4 平面形計算的實施

用一個“求取過平面上3點的圓”例子來闡述平面上形計算的實施過程。如果將“作 2點的垂直平分線”的幾何基命名為“LPPN()”(表述時只對名字感興趣而省略參數(shù))，將“求兩直線的交點”的幾何基命名為“PLL()”，“CPPP()”表述為3點所求的圓。解的過程如表1。

表1 用幾何基序列表述求解過平面上3點的圓

用幾何基序列表示就是 CPPP()={LPPN，LPPN，PLL}。而CPPP()又構(gòu)建了新的求圓幾何基。

這是從幾何的角度去描述求解過程，使算法設(shè)計的思考過程變得直觀，也更宏觀，更可喜的是求取交點的代數(shù)實施過程被省略了。因此，引入幾何基是企圖，或者可以淡化(或隱藏)代數(shù)表述和代數(shù)運算，這強調(diào)了用空間的思維去構(gòu)建與描述整個求解過程。

3.4.5 空間形計算的實施

空間問題的形計算盡量采用降維計算，通常會利用畫法幾何的投影與2D/3D對應(yīng)理論。空間兩幾何的求交算法可簡單表述如下(參考圖 6中空間直線與球面求交的實施過程)。

空間形計算求交算法：

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

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

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

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

圖6 空間直線與球面求交形計算的實施過程

3.5 形計算的執(zhí)行效果

通過幾何數(shù)引入及降維處理兩個方面說明形計算的執(zhí)行效果。

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

表2 幾何數(shù)在幾何表示、簡化計算、解的選擇中作用的例子

(2) 基于幾何數(shù)的二維布爾運算。平面上的布爾運算是對兩個圖形進行交、并、差操作，由兩個圖形產(chǎn)生新的圖形。圖形由邊界描述，運算也只要通過邊界進行，新邊界由原圖形雙方的部分邊界組合構(gòu)成。關(guān)鍵點是邊界的改變在原圖形雙方邊界的相交處，求取這些交點，根據(jù)布爾運算的類型得到新邊界的走向。

文獻[19]敘述了一種基于幾何數(shù)的十分簡單的二維布爾運算算法。根據(jù)邊界的幾何數(shù)引入環(huán)表示邊界(外邊界與內(nèi)邊界分別由外環(huán)與內(nèi)環(huán)表示)，這樣，圖形邊界就具有方向，邊變成向量，圖形也就有了內(nèi)、外之分。交點的幾何數(shù)決定交點是“入點”還是“出點”。

算法十分簡單：從某一個交點出發(fā)，對并(交、差)運算，若交點幾何數(shù)為負(正)，則轉(zhuǎn)向另一環(huán)(頂點則按原走向搜索下去)，直至回到出發(fā)時的首交點，就得到一個新邊界(環(huán))。一旦所有交點均被遍歷，算法結(jié)束。

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

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

圖7 對兩個圖形A與B求并集的形運算

(3) 基于幾何數(shù)的幾何奇異處理。幾何計算不穩(wěn)定的主要原因是“幾何奇異”(屬于理論層面)和“計算誤差”(屬于實施層面)。即判定是否幾何奇異(未知問題變成已知問題)與處理幾何奇異問題(解決一個已知問題)是計算穩(wěn)定性(共性問題)的2個方面。如何在理論上(整體)解決幾何奇異問題一直沒有很好解決。可以依據(jù)“交點幾何數(shù)”概念，可簡潔、有效地解決幾何奇異問題。設(shè)兩向量交點的幾何數(shù)取“入點”為“-1”，“出點”為“+1”，那么就有以下重交點與重邊交點處理規(guī)則。

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

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

兩個規(guī)則只是對交點幾何數(shù)的簡單運算，但它從理論層面上解決了幾何的已知奇異問題。

形計算中解決幾何計算奇異問題的方案框架如圖10所示。

圖8 重交點的取舍

圖9 重邊交點的選擇

圖10 形計算中解決幾何奇異問題的總體方案

(4) 三維求交中的降維處理。給出2個比較典型的三維求交例子，說明通過降維處理后形計算中的執(zhí)行效果。

空間兩三角形關(guān)系。文獻[20]用這種形計算機制基于投影降維對空間兩三角形A與B的求交計算進行了測試?；舅枷胧牵阂?A所在平面作為 xy坐標(biāo)平面，該平面的法向作為z軸，并以A的一條邊作為x軸建立計算坐標(biāo)系(圖11)。在這個坐標(biāo)系下，2個三角形的表述與關(guān)系變得十分簡單：空間兩三角形的關(guān)系變?yōu)槠矫嫔暇€段-線段(圖12(a))、線段-三角形(圖 12(b))間的關(guān)系，幾何奇異問題也可以在平面上考慮了。

對40對空間三角形進行重復(fù)1百萬次相交計算，分別在筆記本電腦與臺式電腦兩類機器上進行測試，結(jié)果如下：在筆記本電腦上，0.95 s可處理1百萬對三角形的相交計算(關(guān)系判別)；在臺式電腦上，0.70 s可處理1百萬對三角形的相交計算。

視錐體裁剪。文獻[14]給出了一個視錐體裁剪的例子。視錐體裁剪是3D顯示系統(tǒng)的基礎(chǔ)技術(shù)之一，對算法效率的要求較高。視錐體是一個觀測金字塔(圖 13)，用代數(shù)辦法求取直線(線段)在視錐體內(nèi)的可見部分，通常要在3D空間計算直線與6個面的交點(最多6次)，每次求交后還要做交點在6個面(2個矩形、4個梯形)上的包容性測試。

圖11 兩空間三角形求交時的計算坐標(biāo)系

形計算方法是以視錐體的兩個對稱平面及視錐體的下底平面作為坐標(biāo)平面，視錐體下底中心到上底中心的向量作為z軸，建立視錐體的計算坐標(biāo)系與V/W/H投影體系(圖14)。在這個計算坐標(biāo)系下，視錐體在V面上的投影Tv與在W面上的投影Tw均為等腰梯形?？臻g直線投影在V面與W面上分2次二維裁剪，合成其結(jié)果即得三維裁剪結(jié)果，且無包容性測試。

圖12 計算坐標(biāo)系下空間兩三角形在投影面上的關(guān)系

圖13 視錐體與計算坐標(biāo)系

圖14 視錐體裁剪化成2次平面裁剪

在文獻[14]中可以看到“直線與圓柱面相交”、“直線與圓錐面相交”等更多的例子。

4 總 結(jié)

討論了一種基于幾何的“形計算”機制。它以幾何作為計算元，以求取幾何間的關(guān)系作為計算目標(biāo)。引入幾何數(shù)協(xié)助表征幾何關(guān)系，引入幾何基構(gòu)建幾何計算的基本工具，將繁復(fù)的代數(shù)運算分解到這些基本原子操作中，尋求解的表述與傳遞的新方法。

形計算機制的核心思想是“回歸幾何”，擴大幾何的自然屬性在幾何問題求解中的作用，淡化代數(shù)化的實施過程，弱化“用一維的代數(shù)方法去決定二維幾何關(guān)系”的矛盾；探索一種“從定性、直觀的角度去思考，以定量、有序的方式去求解”的幾何計算理論和方法，達到“形思考、數(shù)計算”或“定性思考、定量求解”的境界；尋求“三維思維，二維圖解，一維計算”的多維空間融合。

相對于常規(guī)的數(shù)計算，形計算更偏重于從更宏觀的形整體幾何角度去考慮與設(shè)計幾何問題的解決方案，使計算過程結(jié)構(gòu)化、直觀化、簡單化。對數(shù)計算的非可讀性、幾何奇異引起的計算不穩(wěn)定性以及降低計算復(fù)雜度等方面有較大的改善。這是對數(shù)計算機制的一種很好的輔助，也是對人、幾何、代數(shù)及計算機相結(jié)合的新計算機制的一種探索。

[1] 中國圖學(xué)學(xué)會. 2012-2013圖學(xué)學(xué)科發(fā)展報告[M]. 北京: 中國科學(xué)技術(shù)出版社, 2014: 3-30.

[2] Piccinini G. Computationalism in the philosophy of mind [J]. Philosophy Compass, 2009, 4(3): 515-532.

[3] Euc1id(歐幾里德). 幾何原本[EB/OL]. [2015-01-12]. http://baike.baidu.com/view/44606.htm.

[4] 百度百科. 馮·諾依曼體系結(jié)構(gòu)[EB/OL]. [2015-01-12]. http://baike.baidu.com/view/7719.htm.

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

[6] 百 度 百 科 . 代 數(shù) 學(xué) [EB/OL]. [2015-01-12]. http://baike.baidu.com/view /556393.htm.

[7] 百 度 百 科 . 幾 何 學(xué) [EB/OL]. [2015-01-12]. http://zh.wikipedia.org/wiki/%E5%87%A0%E4%BD% 95%E5%AD%A6.

[8] Christer Ericson. Triangle-triangle tests, plus the art of benchmarking [EB/OL]. (2007-09-12). http://realtimecollisiondetection.net/blog/?p=29.

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

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

[11] 張景中. 幾何問題的機器求解[J]. 科學(xué), 2001, 53(2): 1-4.

[12] 吳文俊. 數(shù)學(xué)機械化——回顧與展望[EB/OL]. [2015-01-12]. http://tieba.baidu.com/p/177537298.

[13] 何援軍. 計算機圖形學(xué)[M]. 2版. 北京: 機械工業(yè)出版社, 2009: 180-183.

[14] 何援軍. 幾何計算[M]. 北京: 高等教育出版社, 2013: 1-26, 226-240.

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

[16] 何援軍. 幾何計算及其理論研究[J]. 上海交通大學(xué)學(xué)報, 2010, 44(3): 407-412.

[17] 何援軍. 圖形變換的幾何化表示——論圖形變換和投影的若干問題之一[J]. 計算機輔助設(shè)計和圖形學(xué)學(xué)報, 2005, 17(4): 723-728.

[18] 何援軍. 投影與任意軸測圖的生成——論圖形變換和投影的若干問題之二[J]. 計算機輔助設(shè)計和圖形學(xué)學(xué)報, 2005, 17(4): 729-733.

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

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

A Shape Computing Mechanism Based on Geometry

He Yuanjun

(Department of Computer Science & Engineering, Shanghai Jiaotong University, Shanghai 200240, China)

Proposed a new computing mechanism called shape computing to treat a geometric problem in a geometric way. In this computing mechanism, theory and methods in geometry, algebra, descriptive geometry and modern computing tools are synthesized. A new paradigm of multi-dimensional integration is proposed, i.e. 3D thinking, 2D diagrams and linear computing. It is apt to build an algorithm framework in a macro geometric perspective. It will provide a much more efficient supplement to normal numeric computing to solve a very wide class of problems in geometric computation.

geometry; geometric computing; algebraic computing; graphic computing

TP 391

A

2095-302X(2015)03-0319-12

2015-01-25；定稿日期：2015-03-25

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