圖學與幾何

何援軍

(上海交通大學計算機系，上海 200240)

圖學與幾何

何援軍

(上海交通大學計算機系，上海 200240)

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

圖學；幾何；幾何計算；數計算；形計算

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

何謂科學？給科學一個充分的、本質的定義并非易事，因為科學其實是一種社會的、歷史的和文化的人類活動?？茖W首先是對應于自然領域的知識，經擴展，引用至社會、思維等領域，如社會科學、自然科學和思維科學等?？茖W是知識，且不是零碎而是理論化、系統(tǒng)化的知識體系，是人類對自然、社會的認識活動。

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

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

1 圖與圖學

1.1 圖形圖像

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

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

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

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

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

1.2 圖學(graphics)

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

現有關于圖的科學主要有工程圖學、計算機圖形學和計算機圖像處理。

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

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

計算機圖像處理包括對數字圖像的處理、對數字圖像的分析與理解、數字化圖像的采集，以及對圖像處理結果的數字化表達等。計算機圖像的本質是平面上的點以及點的屬性(顏色、灰度等)，因此其理論可以分成兩個部分：對密集的點的處理和對色彩的處理。

IEEE對計算機圖形學的定義是：Computer graphics is the art or science of producing graphical images with the aid of computer，這個定義有幾個關注點：首先，定位計算機圖形學不僅是一門科學，還是一門藝術；其次，雖然認為圖像借助于計算機但沒有提及從何產生？

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

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

2 圖學與幾何

2.1 圖學的本質是幾何

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，短短兩句話，揭示了計算機圖形學和造型的基礎是點與向量的運算，充分認識到了圖學與幾何的緊密關系。國際學術組織International Society for Geometry and Graphics (ISGG)，每 2年召開一次 International Conference on Geometry and Graphics，這是將圖學與幾何定位得最緊密也是最貼切的國際學術組織與國際會議。

圖學研究將形演繹到圖，以及圖的表達、產生、處理與傳播。圖源于形，由形而來，在計算機中，形與圖都是由幾何構造與描述的，這里的幾何是點、線、面等，可被稱為“幾何元”，這些不同的幾何元依照一定的拓撲關系組織起來構造成不同的幾何形體；通過投影在平面顯示成圖——圖形或圖像，此時，點、線被稱為“圖元”，圖元是具有不同屬性的幾何元。因此，不論是位圖還是矢量圖，終極處理對象是點、線等幾何元。它們都源于幾何。表1給出了幾何計算在計算機圖形學中的作用，幾何與幾何計算在圖學中的地位和作用可見一斑。

表1 幾何計算在計算機圖形學中的作用

在學科分工上，計算機圖形學與計算機圖像處理各有側重，計算機圖形學偏重于從形得到圖，計算機圖像處理則偏重于對圖本身的處理。盡管圖形與圖像的處理方式存在差異，但是其計算基礎是相同的，同是幾何。

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

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

最后，圖學計算中常用的幾何變換、圖形變換和坐標系變換也是與幾何密切相關的。平移、旋轉、比例以及投影(正投影或透視投影)等，這些變換都是幾何變換，可以用變換幾何化方式實現。

2.2 圖學計算中的若干問題

2.2.1 圖學計算的本質是求取幾何間的關系[3,9-11]

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

2.2.2 維度差距的矛盾

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

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

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

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

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

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

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

2.3 計算基礎

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

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

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

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

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

2.4 圖學計算的模式選擇

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

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

(3) 計算的基礎是數學。人們對計算及其結果的基本要求是快速而直觀，是一個(組)簡單的數字，或是一幅(批)合適的圖。因此，表述計算的對象與結果只有2種：數和形，數和形又分別對應于數學的2個基礎學科——代數與幾何，對應于數計算與形計算。

數學是永恒的！好的數學思想很少會過時，雖然運用方式會發(fā)生很大變化。

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

(5) 數計算的一些缺陷需要暫且擱置。數計算求解過程的不直觀使得人的空間思維特長蕩然無存，計算常變得不可讀，甚至不可掌控。史蒂芬·霍金有一句名言：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 (有人告訴我，我在書中的每一個方程都會使這本書的銷量減半，為此我決定一個方程也不用。)[18]足見代數的不可讀性對交流的殺傷力。還有一些問題困擾著純代數方法，如不必要的復雜度、需要較復雜的數學計算工具、算法時間性能低下、無法完美處理奇異性問題等等。

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

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

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

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

3 圖學中的形計算

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

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

3.1 形計算的理論基礎

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

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

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

對幾何計算，Leibniz就認為應該有一種“幾何代數”，其接近于幾何本身，每個表達式都有明確的幾何解釋，其元素被稱為“幾何數”[16]。由幾何數處理幾何體，實現幾何計算的設想本質就是解決幾何體的數制問題。形計算機制將采用 Leibniz幾何數的名字，引入幾何數表征幾何的表述。數制問題解決了，形計算就有基礎了。

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

3.2 形計算在計算中的地位

當然，不能嚴格的照搬數計算機制的模式去定義、去理解這個形計算，其更多的是在人的思考層面、解決幾何問題的框架層面和算法的設計層面，表述不同維度下的形數轉化機制。

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

圖1 形計算在計算中的地位

3.3 引入幾何數

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

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

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

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

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

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

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

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

(7) 強調幾何在“標準坐標系(計算坐標系)”下描述；等等。

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

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

3.4 引入幾何基

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

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

幾何基運用公理去誘導幾何推理計算，處理幾何元之間的幾何關系，而非用純代數計算去解決幾何問題。從解的形式來看，幾何問題的求解形式表現為幾何基的序列，即幾何元的操作序列組成問題的解，使計算的每一個步驟都具有幾何意義。使幾何問題的求解結構化、直觀化、簡單化。

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

圖2 3點求圓樹結構求解示意圖

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

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

3.5 幾何變換幾何化

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

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

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

3.6 形計算的基本架構

形計算的基本架構如下(圖3)：

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

(2) 引入幾何數，協助表征幾何的定義，表述幾何間的關系，并輔助整個計算過程。引入幾何基，構建基本幾何的定義、相交等的基本工具，作為形計算的基本幾何單元。

(3) 對三維的形，以解決表示為主，在幾何數的協助下，表征幾何體的構造關系，以形為綱，在空間層面整體考慮幾何問題的求解方案；然后，根據主幾何元建立相應的計算坐標系，參考2D/3D對應理論，建立三維形與二維圖的映射關系，將空間問題降為平面問題。

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

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

圖3 形計算的總體框架與求解機制

3.7 基于幾何數的幾何奇異處理[20]

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

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

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

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

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

圖4 重交點的取舍

圖5 重邊交點的選擇

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

圖6 引入幾何數解決幾何奇異問題的實施方案

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

3.8 形計算若干例子

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

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

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

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

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

圖8 基于降維的二維裁剪

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

圖9 4種矩形裁剪的測試樣例與結果

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

計算效率的測試分成兩種：①是各種布局的線段的測試，即對所有67條線重復進行50萬次裁剪；

測試結果見表 4，4種方法所花的計算時間在同一個數量級上，稍有區(qū)別。

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

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

視錐體裁剪是計算機圖形學的一個重要而基礎的算法，下面的算法利用畫法幾何的投影理論，將3D計算降為2D計算。

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

圖10 視錐體計算坐標系

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

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

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

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

3.8.3 基于幾何數的幾何形體布爾運算

文獻[21]敘述了一種基于幾何數的十分簡單的二維布爾運算算法。邊界的幾何數使圖形邊界劃分為有內邊界與外邊界，交點的幾何數決定了交點是入點還是出點，算法原理十分簡單。

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

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

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

這個方法也可以方便的擴展到三維形體的布爾運算(圖13)。

圖12 對2個圖形A與B求并集的形運算

圖13 三維布爾運算的原理

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

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

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

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

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

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

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

圖14 用形計算求取空間直線與球面交點的實施過程

3.8.5 兩空間三角形的位置關系[9,26]

空間兩三角形相互關系判定與計算是有限元分析、碰撞檢測中的基礎算法。

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

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

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

圖16 經降維后的空間兩三角形關系簡化、奇異狀態(tài)清晰

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

4 結 論

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

圖源于形，幾何構造了形與圖。因此圖學的核心是形，本質是幾何，圖學計算的主要工作是幾何計算，理論基礎是幾何學。只有基于計算與幾何兩個最核心的要素，才能清晰圖學與幾何的關系。即圖學研究的目標是圖、核心是形、本質是幾何，最根本的理論基礎是幾何學。這些理論、方法和技術會借助于其他學科或是學科交叉。

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

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

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

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

[1] 中國圖學學會. 2012-2013圖學學科發(fā)展報告[R]. 北京:中國科學技術出版社, 2014.

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

[3] 于海燕, 蔡鴻明, 何援軍. 圖學計算基礎[J]. 圖學學報, 2013, 34(6): 1-6.

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

[5] 何援軍, 王子茹. 談談圖學教材[J]. 圖學學報, 2015, 36(6): 819-827.

[6] 何援軍. 計算機圖形學[M]. 2版. 北京: 機械工業(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] 何援軍. 幾何計算[M]. 北京: 高等教育出版社, 2013: 1-19.

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

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

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

[13] 吳文俊. 數學機械化——回顧與展望[J]. 系統(tǒng)科學與數學, 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]. 數學譯林, 2002, (1): 1-24.

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

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

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

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

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

[21] 章 義, 于海燕, 何援軍. 二維布爾運算[J]. 上海交通大學學報, 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]. 圖學學報, 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-)，男，浙江諸暨人，教授，博士生導師。主要研究方向為CAD/CG、幾何計算。E-mail：yjhe@sjtu.edu.cn