于海燕， 蔡鴻明， 何援軍

（1. 東華大學機械工程學院，上海 201620；2. 上海交通大學計算機系，上海 200240）

當今計算機體系無法有效解決未來應(yīng)用對功能性提出的越來越高的要求，“人腦計算機時代”將挑戰(zhàn)統(tǒng)治計算機結(jié)構(gòu)50余年的馮·諾依曼體系[1]。同樣，圖學計算，作為圖學學科的基礎(chǔ)，對其計算精度要求越來越高，原有體系的穩(wěn)定性日益受到挑戰(zhàn)，一些原以為已成熟的算法逐漸暴露出問題。因此，有必要對圖學計算的內(nèi)涵、關(guān)鍵問題、研究方法進行梳理與研究，探索穩(wěn)定、快速的圖形計算新理論與方法。

本文首先揭示圖形、圖像和視頻的本質(zhì)，探索圖學計算的內(nèi)涵，構(gòu)造圖學的公共基礎(chǔ)。從表現(xiàn)的視角理解圖形/圖像只是基本圖元不同組合的顯示方式，揭示圖形/圖像的幾何特性；從對圖形/圖像產(chǎn)生機理的梳理入手，分析圖形計算的矛盾，明確圖學計算的根本任務(wù)；從幾何奇異是造成幾何計算不穩(wěn)定性的本源入手，把握圖形計算的關(guān)鍵。

結(jié)合最新研究進展，總結(jié)提煉圖學計算的研究動向，并基于計算與幾何兩個最核心的要素，進一步闡述一種有別于代數(shù)化的幾何化計算理論。

1 圖學計算內(nèi)涵

回顧計算歷史，從石塊、貝殼到結(jié)繩計數(shù)，到算盤的出現(xiàn)，再到計算機的誕生，隨著科學技術(shù)的發(fā)展，人類社會進入了一個嶄新的計算時代。從計數(shù)到推理、由實踐到理論，從自然科學到哲學命題，人類對于計算的認識在不斷深入。

人類的思維是基于圖形的。人類的計算歷史與人從孩童到成年對數(shù)學的認知歷程一樣，也始于圖形，由具體的形，到抽象的形，再到更抽象的圖。至今我們?nèi)粤晳T于通過在紙上涂涂畫畫的方式把復雜的問題分解提煉，抽象出其本質(zhì)，說明人類的計算是源于圖形、基于圖形的。

盡管圖形與圖像的處理方式存在差異，但是他們的計算基礎(chǔ)是相同的——從表現(xiàn)的視角理解，圖形與圖像都只是具有線形、寬度、顏色等屬性信息的基本圖元（點、線等幾何）的不同組合。例如，計算機圖形學中的隱藏線消除算法與真實感圖形繪制算法是分別由三維場景生成圖形和圖像的典型算法。兩者在三維空間的主要計算都是直線（向量）與空間物體的求交計算，計算的目標都是為了求得空間點，前者是2個點，后者是1個點，只是在最后的顯示階段，他們的工作才各走自己的路，一個取2個點得到線段及線的寬度、線型、顏色等屬性，組成圖形；另一個則只需計算1個點的色調(diào)、色飽和度和亮度等屬性，得到像素，組成圖像。

因此，組成圖形與圖像的基元是幾何，圖學計算的本質(zhì)是幾何計算。

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

世界由形構(gòu)造，形由圖在畫面上顯示，形是圖之源。計算機背景下，圖學的主要工作是由圖顯示形，由圖構(gòu)造形，以及由一張圖變成另一張圖。

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

用兩個典型的例子說明圖、形、幾何與幾何計算的關(guān)系。隱藏線消除是由形顯示為圖形的典型算法。消隱過程是一條一條線的輸出，每條線需與場景中所有物體（面）進行比較，線的各可見部分的交集即為此線的最終可見部分。因此，整個場景的輸出（顯示）過程就是一條一條地去確定場景中所有線條的哪些部分該顯示，哪些部分不該顯示。這涉及大量的幾何運算和代數(shù)運算。真實感圖形繪制是由形顯示為圖像的典型算法。這是一個光強與色彩的量化、紋理映射、圖像合成、幀緩存等基于物理、光學、色彩理論和技術(shù)的復雜計算過程。這里，貫穿整個算法的關(guān)鍵計算是從光源發(fā)出的每一條光線與景物表面的空間線面的求交，包括反射和折射計算，都是幾何求交、比較等的幾何計算。

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

1.2 圖形的本質(zhì)

人工生命理論的創(chuàng)立者蘭頓(Chris Langton)認為[2]，生命的本質(zhì)不在于具體的物質(zhì)，而在物質(zhì)的組織形式；這種組織原完全可以用算法或程序表達出來，所以，只要能將物質(zhì)按著正確的形式構(gòu)建起來，這個新的系統(tǒng)就可以表現(xiàn)出生命。”而這種所謂的“正確的形式”就是生命的算法或程序。所以，算法和程序是把非生命和生命連接起來的橋梁，是生命的靈魂。這在圖上也體現(xiàn)出來，下面以兩個簡單例子說明這個論點。

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

對圖 2左上角所顯示的三維空間框架施以不同的裁剪，就得到不同的圖，這些圖反映在人們大腦中是不同的形，或是實心的、或是空心的、或是盒子，等等。這里，空間線的幾何參數(shù)并沒有改變，只是線的部分被用于構(gòu)成圖形，本質(zhì)上也是幾何元的拓撲關(guān)系改變導致展現(xiàn)了不同的形。

圖1 圖元關(guān)系的改變導致圖的大變形

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

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

1.3 圖形計算的矛盾

還有一個問題存在于圖形計算的過程中：“形是二維或三維的，圖是二維的，計算是一維的?！逼鋵?，長期以來人們習慣的基于代數(shù)的數(shù)計算一直蘊涵著“一維計算處理二維問題”這樣一個矛盾，遺憾的是，這個矛盾并沒有引起人們足夠的重視。正如吳文俊先生總結(jié)數(shù)學機械化的實質(zhì)是“把質(zhì)的困難轉(zhuǎn)化為量的復雜”一樣，人們習慣于這樣的復雜。

計算不應(yīng)該僅僅局限于數(shù)的一維計算機制，也要考慮形的二維形計算機制。有必要厘清形、數(shù)、人在圖形計算中的特點與關(guān)系，盡可能充分的發(fā)揮各自的作用，探索形、數(shù)、人相結(jié)合的圖形計算理論，探索求解圖形問題的新方向、新方法。應(yīng)該以人的三維思維，從形的角度，依賴于幾何計算、數(shù)字計算以及計算機的算法等去構(gòu)建圖學的計算基礎(chǔ)。

1.4 圖形計算的關(guān)鍵

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

計算復雜度包括空間復雜性和時間復雜性?？臻g復雜性一般指存儲量的問題，時間復雜性則是指計算的工作量問題。一般從量與質(zhì)兩個方面去降低計算的復雜度，或者減少計算對象的數(shù)目，或者降低參與計算對象的復雜度。

計算穩(wěn)定性問題是一個長期的難題，本質(zhì)是計算正（準）確性問題。即使在一些已被廣泛使用的大型應(yīng)用系統(tǒng)中，也存在幾何引擎的穩(wěn)定性問題。這里有理論問題，也有實施問題。導致幾何計算不穩(wěn)定主要有兩個原因，一是由數(shù)字計算誤差引起，通常與數(shù)制及計算方法有關(guān)；二是由幾何本身原因引起，因幾何間的重疊（共點、共線、共面等）引起的幾何奇異而造成判斷的不確定性。

2 研究動態(tài)

圖形計算基于傳統(tǒng)的數(shù)學理論、幾何與代數(shù)。由于計算機的介入，代數(shù)計算發(fā)揮了更多的作用，但是，對圖形來說，它的基本元素是點與線，因此在圖學中應(yīng)更多的發(fā)揮幾何本身的特性。國外在這方面做了很多的工作。

文獻[3]提出了一個隱式曲面（例如仿射度量、共線法線向量和法線向量、仿射高斯、平均曲率）的局部仿射結(jié)構(gòu)的估計量，給出了一個更加簡單和穩(wěn)定的幾何簡化，避免了直接求導而導致的巨大的計算量和數(shù)據(jù)的不穩(wěn)定。文獻[4]通過空間有理立方 Bezier曲線研究了拉格朗日幾何插值。此論文展示了在某些自然條件下，插值問題的解是存在并唯一的。論文中多個例子說明了非線性幾何細分算法的應(yīng)用前景。文獻[5]通過單調(diào)螺旋五次曲線研究了包含終點、切線、曲率的幾何Hermite數(shù)據(jù)插值?；趯臻gPythagorean速度曲線的Hopf映射方程，論文展現(xiàn)了通過解決某一單一變量 12維的多項式方程可以決定幾何Hermite插值。文獻[6]通過開發(fā)一套系統(tǒng)的運動軌跡描述機制來實現(xiàn)有效的運動軌跡描述。論文作者提出了一個靈活的運動軌跡信號描述工具，采用移動框架技術(shù)實現(xiàn)公式化運動軌跡再生。該研究在機器人學習等方面將有較廣闊應(yīng)用前景。

文獻[7]采用光線投射法(ray casting)表示圓球，避免了采用多邊形化(polygonization)方法表示帶來的缺陷，并提出了一種基于 GPU的快速光線投射方法來渲染圓球，很好地解決了因此帶來的大量計算。文獻[8]提出了一個渲染大型復雜場景下圖像的全局光照效果的軟件系統(tǒng)，通過采用GPU，大幅提高了整體的渲染速度。

文獻[9]提出了基于二維空間的光線傳播模型，建立了用來簡化復雜的全局光照理論的理論框架。這種概念上“降維”的方式帶來了不少切實的好處：各種全局光照概念在2D中的可視化變得更加容易；處理2D光線傳輸及其派生物所需的計算時間大幅減少，這使建模和實驗更加簡單；由于2D中光線傳輸?shù)谋磉_式比較簡單，復雜的全局光照概念的導出變得相對容易；文中描述的2D全局光照框架也有在教育方面的潛在應(yīng)用。文獻[10]提出了一種從3D圖像中識別并提取出重復出現(xiàn)的結(jié)構(gòu)的計算架構(gòu)，通過一種對相似變換(similarity transformations)的恰當表示將該問題規(guī)約到2D的網(wǎng)格中，采用了一種優(yōu)化算法來探測這些網(wǎng)格。該算法在有異常值和缺失信息的情況下也有很好的穩(wěn)健性，因此在復雜且紊亂的圖中也可以有效地發(fā)現(xiàn)重復結(jié)構(gòu)。文獻[11]介紹了一種分層發(fā)型合成架構(gòu)，它把發(fā)型同時看作一個3D向量場和一個發(fā)束在頭皮上的2D分布圖，只需提供一種真實的發(fā)型，就可以合成一個從空間的發(fā)束到幾何細節(jié)都滿足統(tǒng)計上相似的模型。

從以上文獻可以看出，近年，在代數(shù)化的基礎(chǔ)上，幾何問題已經(jīng)傾向于采用更簡潔直觀的幾何方法。這種方法的推進，還需要理論層面的支撐。

3 幾何化的圖學計算理論與方法

圍繞圖學計算的矛盾與關(guān)鍵問題的研究，我們已經(jīng)建立了“幾何問題幾何化”的幾何計算的全新理論框架及整套實用算法，處理幾何表示、幾何創(chuàng)建和幾何計算中的各種問題。根據(jù)幾何問題幾何化的理論，國內(nèi)學者提出了以“形計算”補充“數(shù)計算”的論點，構(gòu)建了基于“幾何基”和“幾何數(shù)”的“形計算”機制，對數(shù)計算的非可讀性、幾何奇異引起的計算不穩(wěn)定性等方面有了較大的改善。

1） 以形學統(tǒng)一幾何與畫法幾何理論

現(xiàn)在似乎沒有人將畫法幾何列入幾何的范疇。其實，畫法幾何研究的基本對象也是幾何，也是研究形的科學。國內(nèi)學者已經(jīng)從形的角度去揭示畫法幾何與幾何的共性問題，將其應(yīng)用于幾何計算中[12-14]。探索以形為核心，綜合地、巧妙地融合幾何、畫法幾何、代數(shù)與計算機的多學科理論與方法，將各學科的長處融合在一起。反過來，這又為畫法幾何計算化提供了一條新途徑，這是多學科理論與方法的融合與相輔相成。

2） 以圖統(tǒng)一圖形與圖像

傳統(tǒng)意義上的圖形與圖像是有區(qū)別的。計算機科學與技術(shù)的發(fā)展使圖形與圖像的區(qū)別逐漸被模糊化，例如在計算機屏幕上，展現(xiàn)在人們面前的，不管是圖形還是圖像，都是由離散的像素組成的畫面（圖）。因此，在計算機語境下用“圖”來統(tǒng)稱圖形與圖像是合適的，這種統(tǒng)一對圖學科學的發(fā)展是十分有益的，它統(tǒng)一了圖學計算的源頭。

3） 數(shù)計算與形計算構(gòu)成完整的算學

上世紀 80年代起，國內(nèi)外就利用現(xiàn)代計算工具對畫法幾何等傳統(tǒng)形計算進行改造，但大都采取代數(shù)化思路，掩蓋了其本身的光芒。其實，形一般是二維以上的，它的關(guān)鍵是幾何間的拓撲關(guān)系，代數(shù)是一維的，它是線性的有序的運算，兩者的矛盾十分明顯。在Leibniz“形式化整個數(shù)學，使之變成一個龐大的代數(shù)機器”的學術(shù)目標影響下，圖形本身的直觀、簡潔優(yōu)勢似乎蕩然無存，更減弱了人類直覺這個最有力的武器。圖學計算的關(guān)鍵字是圖，計算也應(yīng)基于圖，因此，用包含形計算與數(shù)計算的算學來統(tǒng)一圖學的計算基礎(chǔ)更為合理。

4） 幾何計算理論

文獻[12]首次以“幾何計算”的方式闡述幾何算法，認為幾何的定義、構(gòu)造、度量、顯示以及相關(guān)處理（幾何相交、幾何碰撞、幾何分析等）就是幾何計算。與數(shù)字計算是以“數(shù)字”作為計算對象不同，幾何計算以各種“幾何”作為計算對象，研究基于幾何（元）計算的理論與方法。通過引入幾何基與幾何數(shù)，構(gòu)建了一個幾“幾何問題幾何化的幾何計算的理論體系和實施框架。將求解幾何問題變成為如何尋找這些幾何基的某一個序列，使計算的每一個步驟帶有幾何意義，形成一種形計算機制。 主要包括以下理論：

· 幾何問題幾何化：幾何代數(shù)化并非是解決幾何問題的必由之路，順其自然是處理問題的最好方式，回歸幾何，淡化幾何問題的代數(shù)（方程）方法，強調(diào)從幾何的角度，用幾何的方法去處理幾何問題。

· 解表述的多樣化：在計算機科學高度發(fā)達的今天，有必要重新審視計算結(jié)果的表述形式，不能一味追求所謂顯式解，應(yīng)該考慮幾何、代數(shù)、畫法幾何、計算機科學等綜合的理論、計算方法、方式與計算結(jié)果表述。

· 形計算機制：提出了一種基于幾何的形計算機制，它是對傳統(tǒng)數(shù)計算的一種補充。這個形計算機制基于以下兩點認識基礎(chǔ)。引入“幾何基”，用幾何基的序列構(gòu)造幾何解。在數(shù)計算層面，充分利用笛卡兒創(chuàng)立的坐標幾何思想，用幾何代數(shù)化方法構(gòu)建一些基本幾何基，作為常用的作圖工具。在形計算層面，則是從幾何的角度，去尋求幾何問題的幾何基求解序列。

· 幾何計算的穩(wěn)定性：計算的復雜度與穩(wěn)定性是計算的兩個關(guān)鍵問題。一種計算方法的提出，一個算法的設(shè)計首先要考慮的因素就是較高的穩(wěn)定性，較低的復雜性，再考慮其他易讀性、可交流性等伴隨要求。引入“幾何數(shù)”，用幾何數(shù)更好的表示問題的幾何結(jié)構(gòu)和幾何性質(zhì)，使幾何奇異的判定與解決轉(zhuǎn)化成幾何數(shù)的簡單數(shù)字運算，從理論上構(gòu)建了一個解決幾何奇異問題的完整解決方案。簡化幾何計算的復雜性，使幾何計算的穩(wěn)定性和計算效率大大提高。

文獻[15]對這種幾何化的圖學計算理論的應(yīng)用作了探索，提出了一種基于投影降維的空間兩三角形求交檢測算法。引入“計算坐標系”，如圖3所示，使“幾何奇異”狀態(tài)最后歸結(jié)為平面上線段被三角形裁剪時的共點、共線問題，如圖4所示，簡單而明晰，從理論上保證了算法的魯棒性。

圖3 計算坐標系下兩三角形交線的計算

圖 4 水平線段與三角形位置分布的奇異情況

4 總 結(jié)

圖學計算的基礎(chǔ)面臨新的挑戰(zhàn)，為此需要更優(yōu)秀的圖學計算理論、算法和系統(tǒng)架構(gòu)，從而滿足精確性、魯棒性和可擴展性的需要。圖學計算將向著多元化、多學科相融合的方向發(fā)展，穩(wěn)定性將成為圖學計算的研究熱點與難點。

本文從圖形計算的內(nèi)涵與本質(zhì)分析出發(fā)，指出幾何代數(shù)化方法存在的用一維的代數(shù)方法決定二維幾何關(guān)系的矛盾；結(jié)合圖形計算的最新動態(tài)與應(yīng)用需求，指出圖學計算基礎(chǔ)革新的趨勢：探索一種發(fā)揮幾何直觀簡潔特點的幾何化求解方法，追求形、數(shù)結(jié)合的新突破。

幾何問題幾何化理論是具有革新意義的基礎(chǔ)理論，它與形計算機制將挑戰(zhàn)數(shù)百年來的幾何代數(shù)之路。具體而言：淡化幾何問題的代數(shù)化方法，“回歸幾何”，擴大幾何的自然屬性在幾何問題求解中的作用，解決“用一維的代數(shù)方法去決定二維幾何關(guān)系”的矛盾；探索一種“從定性、直觀的角度去思考，以定量、有序的方式去求解”的圖學計算理論和方法，達到形思考、數(shù)計算或定性思考、定量求解的境界；尋求建立一種“三維思維，二維圖解，一維計算”的多維空間融合，追求形、數(shù)結(jié)合突破的形計算機制。此外，今后的研究會更關(guān)注于計算穩(wěn)定性問題。完善基于“幾何基”和“幾何數(shù)”的“形計算”機制，將對數(shù)計算的非可讀性、幾何奇異引起的計算不穩(wěn)定性等方面有較大的改善。

[1]何 屹, 毛 黎. 開啟計算機“高智商”新時代[N].科技日報, 2011-08-20 (002).

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

[3]Andrade M, Lewiner T. Affine-invariant curvature estimators for implicit surfaces [J]. Computer Aided Geometric Design, 2012, 29(2): 162-173.

[4]Jaklic G, Kozak J, Krajnc M, Vitrih V, Zagar E.Geometric lagrange interpolation by planar cubic Pythagorean-hodograph curves [J]. Computer Aided Geometric Design, 2008, 25(9): 720-728.

[5]Han C Y. Geometric Hermite interpolation by monotone helical quintics [J]. Computer Aided Geometric Design, 2010, 27(9): 713-719.

[6]Wu S, Li Y. Motion trajectory reproduction from generalized signature description [J]. Pattern Recognition, 2010, 43(1): 204-221.

[7]Kanamori Y, Szego Z, Nishita T. GPU-based fast ray casting for a large number of metaballs [C]//EUROGRAPHICS, 2008, 27.

[8]Budge B, Bernardin T, Stuart J A, Sengupta S, Joy K I,Owens J D. Out-of-core data management for path tracing on hybrid resources [C]//Eurographics, 2009, 28.

[9]Jarosz W, Sch?nefeld V, Kobbelt L, Jensen H W.Theory, analysis and applications of 2D global illumination [C]//SIGGRAPH, 2012.

[10]Pauly M, Mitra N J, Wallner J, Pottmann H, Guibas L.Discovering structural regularity in 3D geometry [C]//SIGGRAPH, 2008.

[11]Wang L, Yu Yizhou, Zhou Kun, Guo Baining.Example-based hair geometry synthesis [C]//SIGGRAPH, 2009.

[12]何援軍. 幾何計算[M]. 北京: 高等教育出版社,2013.

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

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

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