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

何援軍

（上海交通大學計算機系，上海 200240）

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

何援軍

（上海交通大學計算機系，上海 200240）

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

幾何；幾何計算；數計算；形計算

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

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

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

1 計算

1.1 計算與它的作用

在人類的社會進步、經濟建設和科技發展過程中，“計算”始終都扮演著非常重要的角色?！癤計算”已是計算機廣為應用的一個概念，例如，科學計算、網格計算、平行計算、智能計算、云計算等。

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

1.2 計算的理論基礎

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

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

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

代數學者更是一個形式主義者，要的是公理化、形式化，追求嚴格的、形式的描述。幾何與物理學者以幾何與拓撲的思想作為基本洞察工具，更關心物理內蘊的表現形式。很清楚，兩者屬于不同的傳統。

當然，計算與工具有關，當今的計算工具主要是計算機，因此，與計算機有關的硬件、軟件以及應用理論也都是計算的基礎。但是，主要的應該是代數與幾何。

1.3 計算對象與結果

計算的對象與結果實質上與計算的性質、實體和工具等有關，不同的計算層面，有不一樣的計算對象，需要不同的計算結果。

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

下棋、指揮打仗等也都需要計算，但這些計算本質上已經變成“算計”了，其計算對象和計算結果與常規意義上的數計算大相徑庭。

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

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

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

1.4 數計算與形計算

代數管數，幾何管形。數引出數計算，形可否引出形計算？

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

由此，計算不應該只是數計算，還應該有形計算。

1.5 計算的關鍵

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

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

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

1.6 計算的方法論

數學是研究現實世界的“數”與“形”的科學，一般認為幾何研究形，代數研究數。作為數學的兩個重要基本組成部分，幾何與代數各有其自己的發展空間和問題域，對應的也有其自己的理論基礎和方法學[5-7]。

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

1.6.1 幾何代數化之路

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

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

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

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

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

1.6.2 代數化還是幾何化

先看一個簡單的例子，求通過P1、P2和P3三點的圓。可以通過解三元二次方程得到所求圓圓心為：

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

但是，如果上面的問題改用幾何方法就變為：

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

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

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

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

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

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

1.6.3 以“形”統一幾何與畫法幾何理論

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

2 形與形的計算

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

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

圖1 問題的求解過程

(1) 提出問題；

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

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

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

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

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

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

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

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

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

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

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

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

2.2 模型與圖形的本質

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

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

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

圖2 幾何參數和拓撲關系的改變對圖的影響

圖3 幾何元的不同部分展現了不同的形

因此，模型與圖形的本質不是構成它們的幾何本身，而在于幾何間的組織形式，決定于幾何之間的相互關系。

2.3 圖形計算的矛盾與關鍵

2.3.1 圖形計算的基礎是幾何求交

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

2.3.2 幾何空間與計算空間的不統一

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

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

2.3.3 幾何奇異是幾何計算不穩定性的主要原因

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

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

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

3 形計算機制

3.1 形計算的基本概念

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

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

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

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

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

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

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

3.2 形計算的理論基礎

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

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

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

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

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

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

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

利用齊次坐標與矩陣理論實施幾何變換也源于高等代數理論。

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

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

3.3 形計算的框架

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

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

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

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

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

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

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

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

· 強調幾何在“標準坐標系(計算坐標系)”下描述與運算；

· 等等。

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

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

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

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

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

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

空間任意3個相交平面的單位法向量構成一個新坐標系，新、舊坐標系間的坐標變換齊次矩陣由3個相交平面的規格化方程系數及齊次表出。

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

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

3.4 形計算的實施

3.4.1 形計算的實施框架

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

(1) 幾何數協助表述二維和三維幾何及幾何間的關系，簡化求解過程；

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

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

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

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

圖4 形計算的實施框架

3.4.2 幾何基的構筑

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

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

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

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

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

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

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

幾何基的構造本身也是基于幾何化思路，具有幾何意義的，且以幾何操作的面目呈現。

3.4.3 變換幾何化的實施

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

在坐標系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個空間單位向量構成一個新坐標系O*x*y*z*（互相垂直時構成直角坐標系）。那么，新、舊坐標系的坐標變換矩陣分別為：

新、舊坐標的變換式為：

(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個向量是可以任意定義的(兩兩互相垂直仍是直角坐標系)，這就可以任意構建合適的計算坐標系，也意味著可以任選投影平面，達到簡化計算。計算坐標系的選取往往依賴于相關幾何元的性質，可以參考某一個幾何為主建立(也決定了投影平面)，該幾何可作為“主元”，例如直線與球相交，以球為主元，圓錐與球求交，以圓錐為主元，等等。

3.4.4 平面形計算的實施

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

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

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

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

3.4.5 空間形計算的實施

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

空間形計算求交算法：

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

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

步驟3. 如果有交點，將得到的交點參數逆變換回原始坐標系。

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

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

3.5 形計算的執行效果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖8 重交點的取舍

圖9 重邊交點的選擇

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

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

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

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

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

圖11 兩空間三角形求交時的計算坐標系

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

圖12 計算坐標系下空間兩三角形在投影面上的關系

圖13 視錐體與計算坐標系

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

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

4 總 結

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

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

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

[1] 中國圖學學會. 2012-2013圖學學科發展報告[M]. 北京: 中國科學技術出版社, 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] 百度百科. 馮·諾依曼體系結構[EB/OL]. [2015-01-12]. http://baike.baidu.com/view/7719.htm.

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

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

[7] 百 度 百 科 . 幾 何 學 [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] 將幾何代數化的數學家——笛卡兒[EB/OL]. [2015-01-12]. http://bbs.matwav.com/archiver/? tid-137115.html.

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

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

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

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

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

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

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

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

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

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

[20] 于海燕, 何援軍. 空間兩三角形的相交問題[J]. 圖學學報, 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-)，男，浙江諸暨人，教授，博士生導師。主要研究方向為CAD/CG、幾何計算。E-mail：yjhe@sjtu.edu.cn