幾何處理

幾何處理，亦稱網格處理，是一個以應用數學、計算機科學、工程學等領域理論為基礎，以設計高效獲取、重建、分析、處理、模擬及傳輸複雜三維模型算法為目標的快速成長的新興研究領域。作為計算機圖形學的分支之一，幾何處理關注對幾何形體本身的建模，處理，分析及應用，常見操作包括表面重建，噪點過濾，幾何分析，形狀簡化以及交互設計。在概念與方法層面上，幾何處理可以被理解為信號處理（一維）和圖像處理（二維）的三維類比。

幾何處理的過程常被形象地比喻為幾何形體的生命周期。

幾何處理的應用領域包括從多媒體、娛樂、傳統的計算機輔助設計到生物醫學計算、逆向工程及計算科學等等。

幾何處理作為幾何形體的生命周期

幾何形體在幾何處理中通常是多維的，尤其以2D和3D最為常見。關於幾何形體的處理，通常涉及三個階段：建模，分析與編輯，使用。這三種階段統稱為幾何形體的生命周期。

離散模型

不同於數學，在計算機科學中，幾何處理的模型通常是離散的。這些離散模型需要具有幾何和拓撲性質：幾何性質與模型的維度，空間位置，切線，法線和曲率有關；拓撲性質並不會隨着平滑的空間變化而發生改變，比如空洞和邊界的數量，以及模型的可定向性。有名的不可定向的模型是莫比烏斯帶和克萊因瓶。

幾何處理常用三角網格（多邊形網格的一種）來建立模型。三角網格的幾何性質由其構成來表現： 網格中每一個三角形有三個頂點與其相應的空間坐標（通常是3維）；連接這些頂點的是具有方向的線段；線段的方向通過右手定則決定了三角形的法線。

網格匹配

幾何處理中遇到的一個常見問題是如何將不同視角、位置的同一物體合併起來，這個問題稱為匹配。匹配問題需要找到最優的剛體變換，使得曲面$X$和曲面$Y$儘可能地重合。用公式來表示，如果$P_{Y}(x)$是點$x$在曲面$Y$上的射影，我們希望找到最優的旋轉矩陣$R$和平移坐標$t$來最小化目標函數：

$\int _{x\in X}||Rx+t-P_{Y}(x)||dx$

雖然旋轉不是線性變換，但一個微小的旋轉可以線性化成反對稱矩陣。同樣的距離函數$x-P_{Y}(x)$也不是線性的，但當$X$的變化足夠小時，也可以線性近似。於是可以使用迭代最近點法（ICP），每次迭代計算微小的變換，而不是一口氣計算一個很大的變換。在迭代最近點法（ICP）中，從曲面$X$選擇$n$個隨機的樣本點，並投影到曲面$Y$。為了在網格曲面上均勻抽樣，抽樣過程分為兩步：在單一三角形內均勻抽樣；不均勻地抽樣三角形，使得每個三角形出現的概率正比於它的面積。單步最優變換從$x$與它的投影計算而得，變換迭代到收斂為止。

變形

變形是涉及將一些幾何形狀轉換為新幾何形狀的問題。通常，這些變換是連續的，不會改變形狀的拓撲性質。現代基於網格的變形方法能在滿足用戶在網格上選定的頂點或區域的變形約束的同時，將這些操控位置的變形平滑地傳播到其餘形狀區域，而不會移除或扭曲細節。常見的交互式變形有基於點，基於骨架和基於網箱的形式。在基於點的變形中，用戶可以在形狀上的一小組點上施加位置變換。基於骨架的變形定義了形狀的骨架，允許用戶移動骨架並旋轉關節。基於網箱的變形需要圍繞全部或部分形狀繪製網箱，以便用戶在操縱網箱上的點時，其包圍的體積相應地發生改變。

參見

• 計算機輔助設計 (CAD)

外部連結

• "數字幾何處理", Peter Schroder 與 Wim Sweldens

• 幾何處理論文集（頁面存檔備份，存於互聯網檔案館）

• Multi-Res Modeling Group（頁面存檔備份，存於互聯網檔案館）, Caltech

• Computer Graphics & Multimedia Department, RWTH-Aachen University