顧險(xiǎn)峰,　 雷　娜

(1.紐約州立大學(xué)石溪分校計(jì)算機(jī)系, 紐約11794；　2.大連理工大學(xué)軟件學(xué)院, 遼寧大連116620)

?

計(jì)算共形幾何簡(jiǎn)介

顧險(xiǎn)峰1, 雷娜2

(1.紐約州立大學(xué)石溪分校計(jì)算機(jī)系, 紐約11794；2.大連理工大學(xué)軟件學(xué)院, 遼寧大連116620)

計(jì)算共形幾何是數(shù)學(xué)與計(jì)算機(jī)科學(xué)的交叉領(lǐng)域.本文介紹了計(jì)算共形幾何中理論基礎(chǔ)，計(jì)算方法及其在工程領(lǐng)域中的應(yīng)用等.基本理論概念包括共形映射，單值化定理，共形模，擬共形映射，模空間等.基本計(jì)算方法包括調(diào)和映照方法，基于黎曼面理論的全純微分方法，基于幾何分析的曲面Ricci流方法.基本應(yīng)用涵蓋了醫(yī)學(xué)圖像，機(jī)械制造，數(shù)字媒體和虛擬/增強(qiáng)現(xiàn)實(shí)等領(lǐng)域.

共形幾何; 黎曼面; 單值化； 調(diào)和映照； 全純微分; 曲面Ricci流

1　引　　言

幾何是自然的語(yǔ)言，大自然亙古不變的偉大樂(lè)章是由幾何譜寫(xiě)而成.對(duì)于深邃奧妙的幾何真理的不懈追求是人類(lèi)社會(huì)永恒的主旋律之一.幾何理論和方法為人類(lèi)提供了認(rèn)識(shí)自然、改造自然的強(qiáng)有力的工具.依隨人類(lèi)對(duì)于幾何真理的持續(xù)探索，基礎(chǔ)理論的提煉和深化，人類(lèi)認(rèn)識(shí)到她的巨大審美價(jià)值，越來(lái)越多的人認(rèn)識(shí)和體會(huì)到幾何內(nèi)在的優(yōu)美和深刻.依隨幾何計(jì)算手段的建立和發(fā)展，人類(lèi)認(rèn)識(shí)到她的巨大實(shí)用價(jià)值，幾何方法已經(jīng)被廣泛應(yīng)用到社會(huì)實(shí)踐的各個(gè)方面，極大地推動(dòng)了生產(chǎn)力的發(fā)展.本文簡(jiǎn)單介紹共形幾何的理論和方法在醫(yī)療和工程中的應(yīng)用，使讀者得以領(lǐng)略共形幾何的簡(jiǎn)潔優(yōu)美，和她解決實(shí)際問(wèn)題的威力.

計(jì)算共形幾何是一個(gè)交叉學(xué)科，根植于純數(shù)學(xué)領(lǐng)域，例如黎曼面理論，復(fù)分析，微分幾何，代數(shù)拓?fù)?，偏微分方程?計(jì)算共形幾何已經(jīng)被應(yīng)用于計(jì)算機(jī)科學(xué)中的諸多領(lǐng)域，包括計(jì)算機(jī)圖形學(xué)，計(jì)算機(jī)視覺(jué)，幾何建模，醫(yī)學(xué)圖像和計(jì)算幾何等.

歷史上，計(jì)算共形幾何也被廣泛應(yīng)用于工程領(lǐng)域[1]，例如在電磁學(xué)，聲學(xué)振動(dòng)膜，彈性力學(xué)，熱傳導(dǎo)與流體力學(xué)等.這些應(yīng)用絕大多數(shù)基于平面區(qū)域之間的共形變換.近來(lái)，隨著三維掃描技術(shù)的發(fā)展，計(jì)算能力的提升，以及數(shù)學(xué)理論的進(jìn)一步發(fā)展，人們已經(jīng)把計(jì)算共形幾何理論和算法從平面區(qū)域推廣到了具有任意拓?fù)涞亩攘壳?

2　直觀概覽

所謂共形幾何就是研究保角變換下不變量的一門(mén)學(xué)問(wèn)，她為研究曲面間的變換和映射提供了理想的理論工具，而曲面比較和匹配在諸多工程和醫(yī)療領(lǐng)域中具有根本的重要性.圖1顯示了人臉曲面的保角映射的實(shí)例.左幅三維人臉曲面由三維掃描儀獲取，右幅是保角映射的二維平面像.從圖中可以看出，保角映射局部上是相似變換，雖然整體上具有很大的畸變，局部上是保持形狀不變的.因此，保角變換又被稱為是保形變換，或共形變換.

圖1　人臉曲面的保角映射

圖2顯示了保角變換(共形變換)的幾何特性.我們?cè)诙S圓盤(pán)中鋪上不同的圖案(稱為紋理)，由圖1中的共形映射拉回到三維人臉曲面上，得到人臉曲面上不同的紋理貼圖.如果紋理為黑白相間的棋盤(pán)格，如左幅圖所示，棋盤(pán)格的四個(gè)角在人臉上依然是直角，這顯示了共形映射保持角度不變.如果紋理為由許多彼此相切的微小圓形構(gòu)成的模式，微圓在人臉上的像依然是微圓，這顯示了共形映射保持無(wú)窮小圓不變.保角性和保圓性都是共形映射的本質(zhì)特性.作為對(duì)比，圖3顯示了一個(gè)非共形映射的實(shí)例.同樣的人臉，經(jīng)由一般的微分同胚映到二維圓盤(pán).圓盤(pán)上的微圓域被拉回成人臉上的橢圓域.人臉的幾何特征沒(méi)有被映射所保持，局部幾何發(fā)生了很大的畸變.

圖2　共形映射的保角和保圓特性

圖3　非共形映射既不保圓，又不保形

人臉曲面到平面圓盤(pán)的共形映射并不唯一，兩個(gè)共形映射之間相差一個(gè)莫比烏斯變換.單位圓盤(pán)到自身的所有共形映射都是莫比烏斯變換，所有的莫比烏斯變換構(gòu)成一個(gè)三維的李群.圖4展示了另一共形變換的實(shí)例，一張女孩的臉被共形地映到平面單位圓盤(pán)，不同的映射之間相差莫比烏斯變換.

圖4　莫比烏斯變換

固定一個(gè)拓?fù)淝?，我們考察曲面上所有可能的黎曼度?如果兩個(gè)黎曼度量彼此相差一個(gè)標(biāo)量函數(shù)，則這兩個(gè)度量彼此共形等價(jià).每個(gè)黎曼度量的共形等價(jià)類(lèi)被稱為是曲面的一個(gè)共形結(jié)構(gòu).拓?fù)淝嫔纤械墓残谓Y(jié)構(gòu)構(gòu)成所謂的?？臻g.帶有共形結(jié)構(gòu)的曲面被稱為是黎曼面.一個(gè)共形結(jié)構(gòu)的全系不變量被稱為是黎曼面的共形模.

人臉曲面是單聯(lián)通的曲面，拓?fù)浞浅：?jiǎn)單.對(duì)于一般曲面，其拓?fù)溆墒欠窨啥ㄏ?，環(huán)柄數(shù)目(虧格)，邊界數(shù)目所決定.單值化定理斷言：所有帶有黎曼度量的可定向曲面都可以共形地變換到三種標(biāo)準(zhǔn)空間中的一種：球面，歐氏平面和二維雙曲空間.如圖5所示，第一列為虧格為0的女孩雕塑表面，共形地映到球面上；第二列是虧格為1的小貓雕塑，它被周期性地共形地映到歐氏平面上.任意兩個(gè)周期之間相差一個(gè)平移.第三列是高虧格的曲面，我們姑且稱之為扭曲的雙耳花瓶，它被周期性地共形地映到雙曲平面上，任意兩個(gè)周期之間相差一個(gè)莫比烏斯變換.莫比烏斯變換保持雙曲長(zhǎng)度不變，亦被稱為雙曲剛體變換.單值化定理在曲面幾何理論中占據(jù)中心地位.

圖5　封閉曲面單值化定理

帶邊界曲面的單值化定理如圖6所示，曲面被共形映到標(biāo)準(zhǔn)空間去掉一些圓盤(pán).大千世界，各種曲面千變?nèi)f化，難以盡訴，但是萬(wàn)變不離其中.這一理論對(duì)于工程實(shí)踐意義重大，這意味著所有三維幾何處理的問(wèn)題都可以轉(zhuǎn)換為三種標(biāo)準(zhǔn)空間中的二維問(wèn)題，這一轉(zhuǎn)換極大地簡(jiǎn)化了問(wèn)題的難度，增加了效率.

一般的微分同胚將無(wú)窮小圓映成無(wú)窮小橢圓，橢圓的偏心率(長(zhǎng)短軸之比)和方向定義了Beltrami系數(shù).基本上，映射和其Beltrami系數(shù)彼此相互決定.Beltrami系數(shù)的模有界的映射被稱為是擬共形映射.擬共形映射給出了曲面間微分同胚的理論基礎(chǔ).

圖6　帶邊界曲面單值化定理

3　計(jì)算方法

計(jì)算共形幾何的計(jì)算方法豐富多彩，涉及到的數(shù)學(xué)分支非常廣泛.我們以圖5的單值化定理為例，來(lái)解釋基本的計(jì)算方法.

調(diào)和映照曲面間的映射所誘導(dǎo)的彈性形變能量被表示成調(diào)和能量，使調(diào)和能量達(dá)到最優(yōu)的映射被稱為是調(diào)和映照.對(duì)于虧格為0的封閉曲面，調(diào)和映射必為共形映射.我們從一個(gè)微分同胚出發(fā)，運(yùn)用非線性熱流方法，逐步改變映射，使得調(diào)和能量逐漸減小，直至達(dá)到調(diào)和映照.

Hodge分解共形映射的導(dǎo)數(shù)是全純微分，由一對(duì)彼此共軛的實(shí)調(diào)和微分形式構(gòu)成.Hodge定理斷言：流形的每一個(gè)de Rham上同調(diào)類(lèi)中有且僅有一個(gè)調(diào)和微分形式.因此我們計(jì)算曲面的上同調(diào)群，然后用橢圓型偏微分方程求解調(diào)和微分形式，再由調(diào)和形式構(gòu)成全純微分，通過(guò)積分得到共形映射.圖5中，虧格為1的曲面的單值化就是由此算出的.

Ricci流Ricci 曲率流由Hamilton發(fā)明，用來(lái)證明龐加萊猜測(cè).Ricci流的基本思想是將黎曼度量變形，其變形程度正比于當(dāng)前的Ricci曲率，使得Ricci曲率依隨時(shí)間演化，其演化規(guī)律滿足反應(yīng)-擴(kuò)散方程，最后曲率處處成為常數(shù).圖5中，高虧格曲面的單值化就是由離散曲率流的方法計(jì)算出來(lái).目前，不存在其他可以替代的方法.

4　基本任務(wù)

下面的計(jì)算問(wèn)題，是計(jì)算共形幾何中的基本任務(wù).這些問(wèn)題本質(zhì)上是相關(guān)的：

(i) 共形結(jié)構(gòu)給定一個(gè)帶有黎曼度量的曲面，計(jì)算其內(nèi)蘊(yùn)共形結(jié)構(gòu)的各種表示.一種方法是計(jì)算阿貝爾微分群，另一種方法是計(jì)算標(biāo)準(zhǔn)黎曼度量.

(ii) 共形模完整的共形不變量被稱為黎曼面的共形模. 對(duì)于給定的黎曼面，計(jì)算其共形模.

(iii) 標(biāo)準(zhǔn)黎曼度量拓?fù)淝嫔系乃欣杪攘靠梢愿鶕?jù)共形等價(jià)來(lái)進(jìn)行分類(lèi).一個(gè)基本的定義是單值化定理，每個(gè)黎曼度量都共形于一個(gè)由常值高斯曲率誘導(dǎo)的黎曼度量.計(jì)算單值化度量是計(jì)算共形幾何中的根本重要問(wèn)題.

(iv) 共形映射計(jì)算給定兩個(gè)共形等價(jià)的曲面之間的共形映射.這可以被歸結(jié)為計(jì)算每個(gè)曲面到標(biāo)準(zhǔn)空間上的共形映射，例如球面，平面或者雙曲空間上的圓域.

(v) 擬共形映射黎曼面之間的絕大多數(shù)微分同胚都不是共形的.它們將無(wú)窮小圓映為無(wú)窮小橢圓.如果橢圓的長(zhǎng)短軸之比有一致的界，那么這個(gè)微分同胚被稱為擬共形映射. 黎曼面上的擬共形映射的微分由Beltrami系數(shù)表示.根據(jù)Beltrami系數(shù)可以恢復(fù)擬共形映射(可相差一個(gè)共形映射).如何從Beltrami微分計(jì)算擬共形映射是一個(gè)基本問(wèn)題，并有著廣泛應(yīng)用.

5　實(shí)際應(yīng)用

我們?cè)诜浅V泛的工程和醫(yī)學(xué)領(lǐng)域中展示了計(jì)算共形幾何的價(jià)值，主要原因如下：

(i) 標(biāo)準(zhǔn)域所有的度量曲面都可以被共形地映射為三種標(biāo)準(zhǔn)域之一：球面，平面或雙曲圓盤(pán).因此我們可以把三維幾何處理問(wèn)題轉(zhuǎn)化為二維問(wèn)題. 這極大地簡(jiǎn)化了算法設(shè)計(jì)和工程計(jì)算.例如某些偏微分方程的解在標(biāo)準(zhǔn)域上有封閉形式，比如單位圓盤(pán)上的泊松公式.

(ii) 根據(jù)曲率設(shè)計(jì)度量每種共形結(jié)構(gòu)都有著帶有常曲率的標(biāo)準(zhǔn)黎曼度量.這種度量在幾何處理問(wèn)題中具有重要的作用.例如，在雙曲度量下，非平凡的閉圈的每個(gè)同倫類(lèi)中具有唯一的閉測(cè)地線.進(jìn)一步，對(duì)于給定的曲率，我們可以設(shè)計(jì)度量，這在幾何建模中起到至關(guān)重要的作用.

(iii) 一般的幾何結(jié)構(gòu)構(gòu)造其它幾何結(jié)構(gòu)，往往要借助共形幾何的方法，例如仿射結(jié)構(gòu)，射影結(jié)構(gòu)等等.這些結(jié)構(gòu)在很多工程領(lǐng)域中起到了根本作用.

(iv)構(gòu)造微分同胚共形映射和擬共形映射可被用于構(gòu)造曲面間的微分同胚.曲面配準(zhǔn)和比較是計(jì)算機(jī)視覺(jué)和醫(yī)學(xué)圖像領(lǐng)域的最本質(zhì)問(wèn)題.

(v)等溫坐標(biāo)共形結(jié)構(gòu)可被看作是一種特殊的圖冊(cè)，使得所有的局部坐標(biāo)都是等溫坐標(biāo).在這種坐標(biāo)之下，黎曼度量具有最簡(jiǎn)單的形式.因此，所有的微分算子，例如Laplace-Beltrami算子，在這種坐標(biāo)下可以被很好地表示.這有助于簡(jiǎn)化偏微分方程.等溫坐標(biāo)保持局部形狀，如圖7所示，這在可視化和紋理映射中非常重要.

(a) 圓盤(pán)填充(b) 棋盤(pán)格　　　　圖7　等溫坐標(biāo)

5.1醫(yī)學(xué)圖像中的應(yīng)用

依隨核磁共振技術(shù)(MRI)和CT斷層掃描技術(shù)的發(fā)展，醫(yī)學(xué)圖像被日益廣泛地應(yīng)用于醫(yī)療實(shí)踐之中.例如，利用核磁共振技術(shù)，病患的大腦灰質(zhì)皮層可以被迅速獲取下來(lái).通過(guò)對(duì)灰質(zhì)皮層曲面形狀的分析，醫(yī)生可以診斷病人腦神經(jīng)系統(tǒng)存在的隱患，對(duì)于病情發(fā)展加以監(jiān)控.這一手段被廣泛應(yīng)用于有關(guān)老年癡呆癥，帕金森氏綜合癥等疾病的診斷.人類(lèi)大腦皮層的形狀非常復(fù)雜，不同的人之間大腦皮層曲面幾何非常不同，即便是同一個(gè)人，不同時(shí)期的大腦皮層的形狀也不相同.如何建立不同大腦皮層曲面間的映射，對(duì)不同皮層曲面加以比較，是一個(gè)非常具有挑戰(zhàn)性的問(wèn)題.共形幾何提供了一種優(yōu)雅而有效的解決方法.

如圖8所示，人的大腦皮層是虧格為零的拓?fù)淝蛎?，可以被共形地映到單位球面?這樣，我們?yōu)榇竽X皮層上的每一點(diǎn)賦予唯一的球面坐標(biāo)，從而實(shí)現(xiàn)精確地定位.另一方面，不同大腦皮層之間的映射可以由球面之間的自同構(gòu)映射建立.相比于復(fù)雜曲面間的映射，球面到自身的映射非常容易建立.

圖8　共形腦圖 [4]

人的大腦皮層上的溝回具有非常重要的神經(jīng)生理學(xué)的意義.如圖9所示，重要的溝回用黃色曲線勾勒出來(lái).中間的溝回在人的胚胎期形成，負(fù)責(zé)人的基本情感.在建立大腦皮層間的映射時(shí)，這些重要溝回需要對(duì)齊.我們沿著這些溝回將曲面切開(kāi)，再共形地將曲面映到平面帶圓形孔洞的圓盤(pán).在建立圓盤(pán)間映射的時(shí)候，我們刻意將圓形孔洞對(duì)齊，這樣就保證了原來(lái)大腦皮層曲面間映射將重要的溝回對(duì)齊.

直腸癌是人類(lèi)的第四號(hào)殺手.直腸癌是由直腸息肉經(jīng)過(guò)不斷的摩擦而發(fā)生癌變轉(zhuǎn)換而來(lái).如果在早期，通過(guò)腸鏡檢查，及時(shí)發(fā)現(xiàn)直腸息肉，并對(duì)較大的息肉進(jìn)行剪除，直腸癌可以避免.因此，腸鏡檢查對(duì)于中老年人群而言非常重要.但是，傳統(tǒng)的腸鏡檢查需要對(duì)病人進(jìn)行麻醉處理，病人需要承擔(dān)一定風(fēng)險(xiǎn)，對(duì)醫(yī)生的手工操作具有很高要求，費(fèi)時(shí)費(fèi)力，對(duì)病患具有一定的侵犯性.

圖10　基于共形幾何的虛擬腸鏡[5]

病患的直腸曲面可以由CT斷層掃描技術(shù)獲取，如圖10所示.直腸壁曲面有許多皺褶，直腸息肉有可能隱藏在這些皺褶中.傳統(tǒng)腸鏡方法無(wú)法檢查皺褶中的息肉，因此具有一定的誤診漏診率.一個(gè)自然的想法在于展平所有直腸曲面的皺褶，從而揭示所有隱藏其中的息肉和潛在病灶.我們利用共形幾何的方法，將直腸曲面周期性地映到平面，每一個(gè)周期是個(gè)長(zhǎng)方形.所有直腸曲面的幾何信息一目了然.這種虛擬腸鏡的方法，病人不需要做麻醉，和病人無(wú)肢體接觸，不具有侵犯性.無(wú)復(fù)雜手工操作，簡(jiǎn)便易行，提高了診斷準(zhǔn)確率和效率.目前，這種虛擬腸鏡技術(shù)已經(jīng)廣泛應(yīng)用于北美臨床診斷實(shí)踐之中.

5.2機(jī)械制造工業(yè)中的應(yīng)用

汽車(chē)，輪船，飛機(jī)，火車(chē)，幾乎所有的機(jī)械設(shè)備都由數(shù)控機(jī)床加工制造.曲面幾何在制造工業(yè)中的數(shù)字表示形式是所謂的樣條曲面.樣條曲面由分片有理多項(xiàng)式組成.通常情況下，樣條曲面需要二階光滑可導(dǎo).比如大家都希望轎車(chē)的車(chē)體光可鑒人， 并且車(chē)體表面的反射圖像也是光滑連續(xù)的.在幾何上，這意味著車(chē)殼表面應(yīng)當(dāng)曲率連續(xù).數(shù)控機(jī)床以樣條曲面為輸入，計(jì)算刀具運(yùn)行的軌跡，力度，速度等等，將金屬毛坯加工成光滑的曲面.

設(shè)計(jì)師利用石膏雕塑出所設(shè)計(jì)的款式，三維掃描儀可將現(xiàn)實(shí)中的曲面數(shù)字化，輸出稠密的點(diǎn)云.應(yīng)用三維Delaunay三角剖分的算法，點(diǎn)云可以被轉(zhuǎn)化為多面體曲面.將多面體曲面轉(zhuǎn)換成光滑樣條曲面是饒有興味的問(wèn)題.傳統(tǒng)樣條曲面的構(gòu)造方法是基于仿射幾何不變量的.對(duì)于拓?fù)浜?jiǎn)單的曲面，我們可以只用一個(gè)整體的參數(shù)域來(lái)覆蓋全部曲面，并在參數(shù)域上構(gòu)造樣條.

圖11　曲面的共形參數(shù)化

如圖11所示，我們將米開(kāi)朗基羅的大衛(wèi)王的頭像雕塑曲面共形地映射到平面，從而得到曲面的共形參數(shù).圖12展示了由這種方法得到的樣條曲面.我們?cè)趲缀螐?fù)雜的區(qū)域，如眼睛，前額處的頭發(fā)，增加了控制點(diǎn)的密度；在相對(duì)平滑的區(qū)域，如面頰，前額，控制點(diǎn)相對(duì)稀疏.這樣，我們能夠利用有限的控制點(diǎn)達(dá)到對(duì)曲面形狀最好的刻畫(huà).

圖12　米開(kāi)朗基羅的大衛(wèi)頭像的樣條曲面[6]

對(duì)于曲面具有復(fù)雜拓?fù)涞那樾危瑯?gòu)造全局光滑的樣條曲面等價(jià)于構(gòu)造原曲面的仿射結(jié)構(gòu).根據(jù)示性類(lèi)理論，由于拓?fù)湔系K，全局仿射結(jié)構(gòu)很多時(shí)候并不存在.樣條曲面上不可避免存在奇異點(diǎn).在奇異點(diǎn)，曲率不連續(xù)，曲面的反射圖像在奇異點(diǎn)有可能間斷.所以，實(shí)際生產(chǎn)中，我們應(yīng)當(dāng)盡量減少奇異點(diǎn)的個(gè)數(shù)，并且將奇異點(diǎn)盡量隱藏在不為人注意的地方.因此出于工程需要，奇異點(diǎn)的位置一般由用戶指定.構(gòu)造曲面帶有指定奇異點(diǎn)的仿射結(jié)構(gòu)是相對(duì)復(fù)雜的問(wèn)題.我們的解決方案是構(gòu)造一個(gè)特殊的黎曼度量，使得所有的曲率集中在奇異點(diǎn)上面.這個(gè)特殊的度量自然地引發(fā)一個(gè)仿射結(jié)構(gòu).圖13顯示了一個(gè)樣條曲面的實(shí)例，其上的奇異點(diǎn)由用戶指定.

圖13　帶有指定奇異點(diǎn)的樣條曲面

5.3無(wú)線網(wǎng)絡(luò)方面的應(yīng)用

無(wú)線傳感器網(wǎng)絡(luò)是一個(gè)近些年來(lái)迅猛發(fā)展的方向，它能夠協(xié)同地實(shí)時(shí)監(jiān)測(cè)、感知和采集網(wǎng)絡(luò)覆蓋區(qū)域中各種環(huán)境或監(jiān)測(cè)對(duì)象的信息，并對(duì)其進(jìn)行處理，處理后的信息通過(guò)無(wú)線方式發(fā)送給觀察者.無(wú)線傳感器網(wǎng)絡(luò)由稱為“微塵”的微型計(jì)算機(jī)構(gòu)成.這些微型計(jì)算機(jī)通?？梢酝ㄟ^(guò)自我重組形成網(wǎng)絡(luò)，彼此通信，并交換有關(guān)現(xiàn)實(shí)世界的信息.

每個(gè)微塵只有有限的計(jì)算和存儲(chǔ)能力，和有限的電池能量?jī)?chǔ)備，特別是所有的微塵只有局部的信息，只能和直接的鄰居通訊.網(wǎng)絡(luò)中通常沒(méi)有一個(gè)掌握全局信息的中樞機(jī)構(gòu).消息的傳遞一般由簡(jiǎn)單的路由協(xié)議實(shí)現(xiàn).如圖14所示，左圖的網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)都是一個(gè)微塵，若兩個(gè)節(jié)點(diǎn)之間存在一條邊，則它們可以直接通訊.網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)具有唯一的坐標(biāo)，坐標(biāo)可以由GPS設(shè)備得到的真實(shí)坐標(biāo)，也可以是虛擬坐標(biāo).網(wǎng)絡(luò)中信息的傳遞多由所謂“貪婪”算法實(shí)現(xiàn).假設(shè)網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)得到了一個(gè)消息，這個(gè)信息包括其目的地節(jié)點(diǎn)的坐標(biāo)，那么當(dāng)前網(wǎng)絡(luò)節(jié)點(diǎn)將此信息傳遞給它的一個(gè)鄰居，使得鄰居到目標(biāo)節(jié)點(diǎn)的距離小于當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離.通常情況下，每一次信息傳遞都使得當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離減小，如果信息能夠順利傳遞，最終它會(huì)抵達(dá)目標(biāo)節(jié)點(diǎn).

圖14　基于幾何方法的無(wú)線傳感器網(wǎng)絡(luò)路由設(shè)計(jì)[7]

“貪婪”算法簡(jiǎn)單實(shí)用，但是具有致命的缺陷.如圖14(a)所示，假設(shè)網(wǎng)絡(luò)中有一些障礙物，例如水塘，建筑物等，這些障礙物會(huì)在網(wǎng)絡(luò)中產(chǎn)生孔洞，如果孔洞不是凸形狀，“貪婪”算法會(huì)失敗.比如信息傳到了某個(gè)非凸孔洞邊緣的角點(diǎn)，非常有可能角點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離小于其任意鄰居到目標(biāo)節(jié)點(diǎn)的距離，從而“貪婪”算法無(wú)法將信息進(jìn)一步傳遞.利用共形幾何的方法，我們將原始網(wǎng)絡(luò)變形，從而所有的邊界都成為圓形，如圖14(b)所示.那么，可以證明“貪婪”算法在新的網(wǎng)絡(luò)中保證會(huì)成功.換言之，通過(guò)改換網(wǎng)絡(luò)的黎曼度量，我們可以提高網(wǎng)絡(luò)的性能和效率.

“貪婪”算法所得到的信息傳遞路徑都是網(wǎng)絡(luò)中鏈接起點(diǎn)和終點(diǎn)的最短路徑.如圖14(b)所示，大量的最短路徑會(huì)貼著網(wǎng)絡(luò)的孔洞邊緣，因此處于網(wǎng)絡(luò)孔洞邊緣的節(jié)點(diǎn)的負(fù)擔(dān)會(huì)很繁重，電力消耗會(huì)比其它節(jié)點(diǎn)更快.我們利用幾何中的“覆蓋空間”的概念來(lái)均衡節(jié)點(diǎn)的負(fù)擔(dān).如圖14(c)所示，我們將網(wǎng)絡(luò)關(guān)于它所有的內(nèi)邊界“反演”，這樣會(huì)增加孔洞的數(shù)目，縮小孔洞的總面積.我們可以再次將整個(gè)網(wǎng)絡(luò)關(guān)于它新的內(nèi)邊界反演，從而進(jìn)一步縮小所有孔洞的總面積.這樣所得到的網(wǎng)絡(luò)可以多重覆蓋原始的網(wǎng)絡(luò)，即新的網(wǎng)絡(luò)是舊網(wǎng)絡(luò)的“覆蓋空間”.信息傳遞在覆蓋空間中由貪婪算法完成.這樣，所有節(jié)點(diǎn)的負(fù)載基本均衡.

5.4電影動(dòng)漫，數(shù)字游戲中的應(yīng)用

紋理貼圖在數(shù)字游戲中，所有的三維物體的表示都可以分為兩部分：幾何和紋理.幾何表征了物體的形狀，由三維空間中的三角網(wǎng)格(離散曲面)表示；紋理表征了物體的材料，質(zhì)地，顏色，和光學(xué)特性，由二維圖像表示.將二維紋理圖像貼在三維離散曲面的過(guò)程被稱為“紋理貼圖”.紋理貼圖需要將三維曲面映射到平面上.如圖15所示，在左圖中，三維曲面被共形地映射到平面上，在右圖中，紋理圖像被這映射“拉回”到三維曲面上面.這樣，我們看到大理石雕塑的大衛(wèi)王的頭像.

圖15　紋理貼圖

圖16　計(jì)算機(jī)模仿藝術(shù)家的素描圖[8]

非真實(shí)感渲染很多時(shí)候，人們需用計(jì)算機(jī)模仿藝術(shù)家作畫(huà).如圖16所示，特殊的計(jì)算機(jī)渲染算法可以產(chǎn)生鉛筆素描的藝術(shù)效果.藝術(shù)家在素描寫(xiě)生過(guò)程中，運(yùn)筆的走向基本上是沿著明暗色調(diào)變化最劇烈的方向，和變化最緩慢的方向.這兩個(gè)方向彼此垂直，被稱為曲面的主曲率方向.在幾何上，計(jì)算機(jī)算法等價(jià)于如何在曲面上設(shè)計(jì)光滑矢量場(chǎng)，同時(shí)，矢量場(chǎng)的走向盡量與曲面的主曲率方向場(chǎng)保持一致.根據(jù)拓?fù)湔系K理論，一般曲面上不存在處處非零的光滑矢量場(chǎng)，矢量場(chǎng)的零點(diǎn)被稱為是奇異點(diǎn).首先，我們可以構(gòu)造一個(gè)新的黎曼度量，使得所有的曲率集中在零點(diǎn)上，換言之，我們生成零點(diǎn)之外的平直度量.在平直空間生成矢量場(chǎng)相對(duì)容易許多.然后我們計(jì)算曲面的主曲率方向場(chǎng)，通過(guò)幾何手段融合一些零點(diǎn).最后根據(jù)光照條件計(jì)算曲面的明暗色調(diào)，在渲染過(guò)程中，矢量的密度正比于色調(diào)強(qiáng)度.

表情捕捉在今天的CG電影(計(jì)算機(jī)生成電影), 表情的建模和生成是最具挑戰(zhàn)性的問(wèn)題之一.人類(lèi)對(duì)于表情極其敏感.根據(jù)心理認(rèn)知理論，人類(lèi)用于識(shí)別表情的大腦區(qū)域不同于識(shí)別一般形狀的區(qū)域.因此，對(duì)于微妙表情的建模和模擬非常困難.人類(lèi)所有可能的肢體動(dòng)作構(gòu)成一個(gè)有限維空間，因?yàn)槿祟?lèi)只有有限個(gè)關(guān)節(jié)，每個(gè)關(guān)節(jié)只有有限個(gè)自由度.但是人類(lèi)所有可能的表情構(gòu)成了無(wú)窮維空間.因此，表情生成具有根本的難度.

近些年來(lái)興起的表情捕捉技術(shù)為表情的建模和生成帶來(lái)了根本性的突破.基于光波干涉原理的高速三維相機(jī)可以實(shí)時(shí)獲取表情的動(dòng)態(tài)變化.如圖17所示，目前的技術(shù)可以達(dá)到每秒上百幀的速度，每幀具有上百萬(wàn)采樣點(diǎn)；但是，所有得到的掃描曲面都是相互獨(dú)立的，曲面之間的映射關(guān)系需要被建立起來(lái).我們將每幀曲面共形映射到平面上，在平面像上計(jì)算特征點(diǎn)，利用優(yōu)化方法尋找平面圓盤(pán)間的映射，如圖18所示.平面像之間的映射建立了三維人臉曲面間的映射.我們用統(tǒng)一的網(wǎng)格基于所得的映射貼到所有的人臉曲面上，如圖19所示，這樣我們可以追蹤人臉上每一點(diǎn)變化的軌跡，從而達(dá)到表情自動(dòng)跟蹤的目的.

圖17　三維動(dòng)態(tài)相機(jī)可以實(shí)時(shí)捕捉人臉表情的動(dòng)態(tài)變化

圖18　動(dòng)態(tài)人臉曲面被共形映射到平面圓盤(pán)[9]

圖20顯示了“虛擬明星”的概念.明星的面部幾何和紋理，以及各種動(dòng)態(tài)表情被掃描下來(lái)，保存在數(shù)據(jù)庫(kù)中.導(dǎo)演根據(jù)劇情需要，選擇合適的表情，視角，嘴型，以及場(chǎng)景，用計(jì)算機(jī)合成CG電影.這樣，真正的明星不需要出演電影，只需要提供各種標(biāo)準(zhǔn)的表情.或者，真人演員的表情被提取出來(lái)，轉(zhuǎn)移到卡通人物臉上，從而用表情捕捉技術(shù)取代目前的表情建模和合成，提高表情的逼真度和復(fù)雜性.

圖19　表情自動(dòng)跟蹤[10]

圖20　虛擬明星：明星的面部幾何和紋理、動(dòng)態(tài)表情被記錄下來(lái)，保存在數(shù)據(jù)庫(kù)中，導(dǎo)演根據(jù)劇情需要選擇合適的表情，合成CG電影

5.5虛擬/增強(qiáng)現(xiàn)實(shí)中的應(yīng)用

在虛擬現(xiàn)實(shí)和增強(qiáng)現(xiàn)實(shí)的應(yīng)用中，如何將光滑曲面離散化是一個(gè)基本問(wèn)題.在離散化的過(guò)程中，我們希望能夠保證離散曲面足夠好地逼近光滑曲面，例如拓?fù)湟恢?，位置接近，測(cè)地距離收斂，曲率測(cè)度收斂.我們提出了一種高效而嚴(yán)謹(jǐn)?shù)姆椒▽?shí)現(xiàn)離散化，同時(shí)保證曲率測(cè)度收斂.通過(guò)單值化，我們將曲面共形映到標(biāo)準(zhǔn)空間，然后在標(biāo)準(zhǔn)空間上采樣，使得采樣密度和曲率成正比，計(jì)算Delaunay三角剖分，再拉回到原來(lái)曲面.圖21顯示了這樣的一個(gè)算例.

圖21　曲面采樣離散化[11]

另一方面，虛擬現(xiàn)實(shí)和增強(qiáng)現(xiàn)實(shí)的應(yīng)用中，需要對(duì)幾何數(shù)據(jù)進(jìn)行壓縮，力圖保持幾何質(zhì)量的同時(shí)增大壓縮比.利用單值化定理，我們將曲面映到標(biāo)準(zhǔn)空間，那么面積變化率函數(shù)加上平均曲率就可以完全復(fù)制原來(lái)曲面.圖22顯示了一個(gè)離散曲面簡(jiǎn)化壓縮的實(shí)例.

圖22　離散曲面簡(jiǎn)化

6　總結(jié)展望

從以上的實(shí)例可以看到，共形幾何不但具有深邃和諧的美學(xué)價(jià)值，更具有無(wú)可比擬的實(shí)用價(jià)值.幾何知識(shí)的廣泛傳播和深入應(yīng)用，日益促進(jìn)了生產(chǎn)力的發(fā)展，根本地改變了人類(lèi)社會(huì)的日常生活.我們期待幾何的進(jìn)一步發(fā)展將為人類(lèi)帶來(lái)更多革命性的變革.

同時(shí)，作為一個(gè)新興學(xué)科，計(jì)算共形幾何依然有大量尚未解決的問(wèn)題，面臨許多挑戰(zhàn).這些基本的公開(kāi)問(wèn)題，需要用更加深刻的理解以及更加精致和準(zhǔn)確的算法去解決.下面這些問(wèn)題在理論和應(yīng)用上都有非常重要的意義：

(i) Teichmüller映射給定兩個(gè)度量曲面和它們之間的映射同倫類(lèi)，計(jì)算唯一的具有最小Beltrami系數(shù)模的擬共形映射，即所謂的Teichmüller映射.

(ii) Abel Differential計(jì)算不同類(lèi)型的Abel微分群，尤其是全純二次微分群.

(iii) 逼近理論盡管已經(jīng)有了計(jì)算共形不變量的算法，但是逼近理論的結(jié)果還沒(méi)有充分的發(fā)展. 對(duì)于平面區(qū)域間的共形映射，不同離散方法的收斂性已經(jīng)被建立. 而對(duì)于曲面間的共形映射，收斂性分析仍然是公開(kāi)問(wèn)題.

(iv) 精確性和穩(wěn)定性雙曲幾何計(jì)算對(duì)數(shù)值誤差非常敏感.提高計(jì)算的精確度很具有挑戰(zhàn)性.計(jì)算幾何中的精確算法有望攻克這個(gè)難題.

我們希望更多的有志年輕人投身到這一領(lǐng)域之中，在理論和工程領(lǐng)域中大展身手，為科學(xué)和實(shí)踐的發(fā)展做出歷史性的貢獻(xiàn).

[1]Gu X and Yau S-T. Computational Conformal Geometry [M]. Cambridge: International Press and Higher Education Press, 2007.

[2]Luo F, Gu X and Dai J. Variational Principles for Discrete Surfaces [M]. Cambridge: International Press and Higher Education Press, 2007.

[3]Zeng W, Gu X. Ricci Flow for Shape Analysis and Surface Registration -Theories, Algorithms and Applications [M]. New York: Springer, 2013.

[4]Gu X, Wang Y, Chan T F, Thompson P M and Yau S-T. Genus Zero Surface Conformal Mapping and Its Application to Brain Surface Mapping [J]. IEEE Transaction on Medical Imaging (TMI), 2004, 23(8): 949-958.

[5]Zeng W, Marino J, Gurijala K, Gu X and Kaufman A. Supine and Prone Colon Registration Using Quasi-Conformal Mapping[J]. IEEE Transactions on Visualization and Computer Graphics (IEEE TVCG), 2010, 16(6): 1348-1357.

[6]Gu X, He Y, and Qin H. Manifold Splines[J]. Graphical Models, 2006, 68(3):237-254.

[7]Sarkar R, Yin X, Gao J, and Gu X. Greedy Routing with Guaranteed Delivery Using Ricci Flows[C]. Proc. of the 8th International Symposium on Information Processing in Sensor Networks (IPSN’09), 2009:121-132.

[8]Lai Y, Jin M, Xie X, He Y, Palacios J, Zhang E, Hu S and Gu X. Metric-Driven RoSy Fields Design[J]. IEEE Transaction on Visualization and Computer Graphics (TVCG), 2010, 15(3): 95-108.

[9]Zeng W, Samaras D and Gu X. Ricci Flow for 3D Shape Analysis[J]. IEEE Transaction of Pattern Analysis and Machine Intelligence (PAMI), 2010, 32(4): 662-677.

[10]Zeng X, Wang C-H, Gu X. Higher-order Graph Principles towards Nonrigid Surface Registration[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2015, 1:1-14.

[11]Li H, Zeng W, Morvan J-M, Chen L, Gu X. Surface Meshing with Curvature Convergence[J]. IEEE Transaction on Visualization and Computer Graphics (TVCG), 2014, 20(6):919-93.

Introduction to Computational Conformal Geometry

GUXian-feng1,LEINa2

(1.Computer Science Department，State University of New York at Stony Brook，Stony Brook NY 11794, USA；2. School of Software, Dalian University of Technology, Dalian Liaoning 116620, China)

Computational Conformal Geometry is an interdisciplinary field between pure mathematics and computer science. This work introduces the fundamental theories, computational algorithms and applications in engineering fields of computational conformal geometry. Basic theoretic concepts include conformal mapping, uniformization, conformal module, quasi-conformal mapping, and moduli space and so on. Major computational algorithms include harmonic mapping, holomorphic differential methods based on Riemann surface theory, surface Ricci curvature flow in geometric analysis. Conformal geometry can be applied in many fields, such as medical imaging, mechanical manufacture, digital media and virtual/augmented reality and so on.

conformal geometry; Riemann surface; uniformization; harmonic map; holomorphic differential; surface Ricci flow

2016-05-10；[修改日期]2016-06-13

國(guó)家自然科學(xué)基金(11271156)

顧險(xiǎn)峰(1970-),男，博士，終身教授，從事計(jì)算幾何研究.Email:gu@cs.stonybrook.edu

雷娜(1977-)，女，博士，教授，從事計(jì)算幾何研究. Email:nalei@outlook.com

O186

B

1672-1454(2016)03-0001-13