一種基于幾何的形計(jì)算機(jī)制

何援軍

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

一種基于幾何的形計(jì)算機(jī)制

何援軍

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

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

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

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

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

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

1 計(jì)算

1.1 計(jì)算與它的作用

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

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

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

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

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

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

代數(shù)學(xué)者更是一個(gè)形式主義者，要的是公理化、形式化，追求嚴(yán)格的、形式的描述。幾何與物理學(xué)者以幾何與拓?fù)涞乃枷胱鳛榛径床旃ぞ?，更關(guān)心物理內(nèi)蘊(yùn)的表現(xiàn)形式。很清楚，兩者屬于不同的傳統(tǒng)。

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

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

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

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

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

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

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

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

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

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

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

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

1.5 計(jì)算的關(guān)鍵

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

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

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

1.6 計(jì)算的方法論

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

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

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

宇宙，一切空間和時(shí)間的綜合。宇是空間，宙是時(shí)間，合為宇宙。

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

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

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

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

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

先看一個(gè)簡(jiǎn)單的例子，求通過(guò)P1、P2和P3三點(diǎn)的圓?？梢酝ㄟ^(guò)解三元二次方程得到所求圓圓心為：

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

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

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

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

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

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

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

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

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

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

2 形與形的計(jì)算

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

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

圖1 問(wèn)題的求解過(guò)程

(1) 提出問(wèn)題；

(2) 通過(guò)建模表達(dá)問(wèn)題，使問(wèn)題抽象化；

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

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

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

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

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

2.1 圖、形、幾何與幾何計(jì)算

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

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

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

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

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

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

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

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

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

圖2 幾何參數(shù)和拓?fù)潢P(guān)系的改變對(duì)圖的影響

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

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

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

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

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

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

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

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

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

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

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

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

3 形計(jì)算機(jī)制

3.1 形計(jì)算的基本概念

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

利用齊次坐標(biāo)與矩陣?yán)碚搶?shí)施幾何變換也源于高等代數(shù)理論。

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

另一方面，隨著幾何基的層層構(gòu)建、逐漸擴(kuò)展，形計(jì)算的基礎(chǔ)也變得越來(lái)越扎實(shí)，工具越來(lái)越多，解決問(wèn)題的方法會(huì)變得越來(lái)越多。

3.3 形計(jì)算的框架

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

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

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

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

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

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

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

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

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

· 等等。

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

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

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

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

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

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

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

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

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

3.4 形計(jì)算的實(shí)施

3.4.1 形計(jì)算的實(shí)施框架

形計(jì)算在空間層面整體考慮幾何問(wèn)題的求解方案，實(shí)施框架如圖4所示。

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

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

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

(4) 在幾何層面上考慮幾何奇異問(wèn)題，通過(guò)對(duì)幾何數(shù)的簡(jiǎn)單運(yùn)算，解決之；

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

圖4 形計(jì)算的實(shí)施框架

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

下面以一個(gè)最基礎(chǔ)、最簡(jiǎn)單、最常用的幾何操作說(shuō)明幾何基的設(shè)計(jì)(圖5)。

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

圖5 過(guò)兩點(diǎn)作直線的幾何基

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

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

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

從計(jì)算機(jī)角度看，這是用計(jì)算機(jī)語(yǔ)言實(shí)現(xiàn)的一個(gè)算法(子程序)。

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

3.4.3 變換幾何化的實(shí)施

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

在坐標(biāo)系Oxyz下任意給定有一共點(diǎn)的3個(gè)相交平面，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è)空間單位向量構(gòu)成一個(gè)新坐標(biāo)系O*x*y*z*（互相垂直時(shí)構(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個(gè)向量是可以任意定義的(兩兩互相垂直仍是直角坐標(biāo)系)，這就可以任意構(gòu)建合適的計(jì)算坐標(biāo)系，也意味著可以任選投影平面，達(dá)到簡(jiǎn)化計(jì)算。計(jì)算坐標(biāo)系的選取往往依賴于相關(guān)幾何元的性質(zhì)，可以參考某一個(gè)幾何為主建立(也決定了投影平面)，該幾何可作為“主元”，例如直線與球相交，以球?yàn)橹髟?，圓錐與球求交，以圓錐為主元，等等。

3.4.4 平面形計(jì)算的實(shí)施

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

表1 用幾何基序列表述求解過(guò)平面上3點(diǎn)的圓

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

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

3.4.5 空間形計(jì)算的實(shí)施

空間問(wèn)題的形計(jì)算盡量采用降維計(jì)算，通常會(huì)利用畫法幾何的投影與2D/3D對(duì)應(yīng)理論?？臻g兩幾何的求交算法可簡(jiǎn)單表述如下(參考圖 6中空間直線與球面求交的實(shí)施過(guò)程)。

空間形計(jì)算求交算法：

步驟1. 根據(jù)參與運(yùn)算幾何元的的性質(zhì)，構(gòu)造計(jì)算坐標(biāo)系(以球心為原點(diǎn)，直線方向?yàn)閤軸方向構(gòu)建計(jì)算坐標(biāo)系)，建立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ì)算方案（在2個(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)逆變換)三步。其中，求交過(guò)程在二維平面上進(jìn)行，例中用了 2次“直線與圓求交”幾何基。

圖6 空間直線與球面求交形計(jì)算的實(shí)施過(guò)程

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

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

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

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

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

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

算法十分簡(jiǎn)單：從某一個(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ì)在求解過(guò)程中同時(shí)被確定，也避免了從頂點(diǎn)出發(fā)需要進(jìn)行繁瑣的包容性測(cè)試，計(jì)算工作量較少。運(yùn)算中的幾何奇異問(wèn)題也可由交點(diǎn)的幾何數(shù)簡(jiǎn)單的予以解決。

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

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

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

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

重邊交點(diǎn)的取舍規(guī)則(圖 9)：如果在同一向量上有連續(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)算，但它從理論層面上解決了幾何的已知奇異問(wèn)題。

形計(jì)算中解決幾何計(jì)算奇異問(wèn)題的方案框架如圖10所示。

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

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

圖10 形計(jì)算中解決幾何奇異問(wèn)題的總體方案

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

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

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

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

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

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

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

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

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

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

4 總 結(jié)

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

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

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

[1] 中國(guó)圖學(xué)學(xué)會(huì). 2012-2013圖學(xué)學(xué)科發(fā)展報(bào)告[M]. 北京: 中國(guó)科學(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é)公開(kāi)發(fā)表 200周年[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí), 1998, 28(3): 281-288.

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

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

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

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

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

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

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

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

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

[20] 于海燕, 何援軍. 空間兩三角形的相交問(wèn)題[J]. 圖學(xué)學(xué)報(bào), 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)師。主要研究方向?yàn)镃AD/CG、幾何計(jì)算。E-mail：yjhe@sjtu.edu.cn