用Catmull-Clark細分及網格調整方法重構牙齒曲面

王玉慧， 張玉茹

（北京航空航天大學機械工程及自動化學院，北京 100191）

用Catmull-Clark細分及網格調整方法重構牙齒曲面

王玉慧， 張玉茹

（北京航空航天大學機械工程及自動化學院，北京 100191）

首先根據牙齒表面測量數據點，計算出其長方體包圍盒；并據此構造細分曲面的初始網格；采用矩陣對角化方法，推導Catmull-Clark細分極限點的表達式，計算初始網格的頂點經過細分后的極限點；按照極限點逼近數據點的原則移動控制網格頂點，經過逐次再細分、再調整網格，使各級網格在數據點的“引導”下逐步變形，使網格逐步逼近牙齒表面的測量數據點集合，實現牙齒表面模型的三維重建。

計算機輔助幾何設計；曲面重構；細分造型；牙齒模型

在虛擬現實環(huán)境中，虛擬場景建模是一項重要工作，直接影響系統的性能。本文研究力覺交互虛擬現實牙科手術培訓中由測量數據點重構牙齒表面模型。

關于牙齒表面的重構，LI Zhong[1]采用雙三次貝塞爾曲面進行了牙齒表面模型的重構，針對每一條輪廓線，用若干三次貝塞爾曲線段拼接得到；然后再對不同輪廓上的對應點進行貝塞爾曲線插值，得到由G2連續(xù)的雙三次貝塞爾曲面片拼接而成的表面模型。文獻[2]采用B-樣條曲面進行牙齒表面曲面模型的重構，由于B-樣條反算要解較大的線性方程組，計算量較大。Mikrogeorgis G[3]利用人類第六顆牙齒的斷層圖像得到斷層輪廓數據點，通過人機交互的方式進行基于三角片的牙齒表面模型重構。Isaac Newton Lima da Silva[4]由牙齒的斷層掃描圖像得到牙齒的斷層數據點，然后構建牙齒的多面體模型，再利用商用軟件Pro/E得到牙齒的實體模型。

用曲面擬合進行物體表面模型的重構計算復雜、計算量較大；采用直接給物體表面的數據點建立拓撲關系的方法，所建立的物體表面模型的質量依賴于測量數據點的測量精度及數據點的分布情況。本文嘗試采用細分造型構建牙齒表面模型。

細分方法是通過將多邊形網格中的每個多邊形按照一定的規(guī)則分成幾個子多邊形，從而得到更光滑的網格。其算法簡單、直觀，適用于構造復雜曲面，Chaikin[5]于 1974年提出了通過重復割去多邊形的角，最終得到光滑的極限曲線的方法，后來被證明該極限曲線是以多邊形為控制多邊形的二次 B-樣條曲線。Catmull和 Clark[6]提出基于四邊形的細分方法，其細分極限曲面是雙三次 B-樣條曲面，文中指出曲面在規(guī)則點處（關聯邊數為4）能達到曲率連續(xù)，而在異常點處曲面是切線連續(xù)。Doo D, Sabin[7]采用離散付立葉變換的方法證明了Catmull和Clark的結論。A A Ball[8-9]分別采用矩陣的特征值性質和離散付立葉變換的方法證明了以上結論。Loop[10]提出了一種基于三角形網格的細分方法，較之基于四邊形網格的細分方法算法更簡單。Suzuki[11]提出了一種基于 loop細分和網格調整的曲面重構算法。本文采用 Catmull-Clark細分方法，并針對數據點有噪聲，利用改進的網格調整方法進行牙齒曲面的三維重構，力圖使重構的網格在逼近牙齒數據點的同時具有較好的光順性。

1 算法原理

1.1 Catmull-Clark細分極限點表達式

由文獻[9]，經過 Catmull-Clark計算細分后新的點點、邊點和面點的公式為

圖1 Catmull-Clark細分算法示意圖

求得矩陣的特征值和特征向量如表1所示。

表1 矩陣的特征值和特征向量

采用與n=4時同樣的求細分極限點的方法求得，當n=3時

1.2 細分網格的構造與調整

首先，計算牙齒表面數據點的包圍盒，將包圍盒略作放大，然后建立如圖2左所示的初始網格；對初始網格進行一次 Catmull-Clark細分得到圖2右所示的網格；然后用式(3)、式(4)求出網格上每個頂點的細分極限點。

設牙齒數據點集合為 Pi(i = 0 ,1,… ,s )，網格頂點集合為 Vi(i = 0 ,1,… ,m)，其細分極限點集為( i = 0 ,1,… ,m)，其中 m為數據點個數。針對 n =4和 n =3兩種情況，用式(6)和式(7)計算每一個極限點。再對于每一個極限點，在數據點集合中求出與它距離最近的點 Pj。

δi則表示 Vi的對應細分極限點與其最近數據點 Pj之間的向量差。

則網格中所有頂點距離其最近數據點的平均距離為

接下來進行網格調整，調整的原則是移動控制網格頂點V使得其所對應的新的細分極限點V∞'重合于其在牙齒表面數據點中的最近距離點。

如果要根據牙齒表面數據點按照網格頂點的調整原則計算出所有新的控制頂點V，則需要解龐大的線性方程組，本文參考[11]的方法，用每次僅移動V而不改變iE，iF進行迭代的方法，即，在考慮使得 'V 對應的細分極限點逼近數據點時，只移動V，而不考慮其周圍的關聯點。等到一個點作為V移動完畢后，再更換一個點作為V，這時就僅考慮當前V點的移動。通過逐次迭代，使得調整后的網格點對應的細分極限點逐步接近其對應的最近點，直到滿足距離誤差ε＜E為止。

根據網格頂點的調整原則，原則上應使得細分的極限點重合于牙齒表面數據點中距其最近的數據點，即使得

其中 α為細分極限點逼近牙齒表面數據點逼近項的系數；β為反映網格調整過程中，當一個控制網格上的頂點被調整過程中，其周圍的點對該點的制約因素。這兩個參數的選取視具體應用問題的要求，通過實驗選定。

調整網格控制頂點算法步驟如下：

（1） 根據牙齒表面測量數據點建立初始網格；

（2） 分別用式(6)和式(7)計算網格中 4=n和 3=n 的每個控制頂點的 Catmull-Clark細分極限點；

（3） 求出牙齒表面測量數據點中距離每個極限點最近的點；

（4） 由式(9)計算網格上某一頂點的細分極限點與其最近數據點的距離；

（5） 由式(10)計算網格上所有點的細分極限點到其最近數據點的平均距離；

（6） 設定誤差閾值ε，如果ε＜E，則不再調整網格；

（7） 如果ε＞E，則對于網格中所有頂點用式(13)計算網格頂點V經過一次移動后的新位置 'V，將V移動到 'V；

（8） 將調整后的網格進行一次 Catmull-Clark細分；

（9） 用細分得到的新網格代替上一級網格，然后重復(2)～(9)的過程。

2 實驗結果

圖2 網格建立及調整過程

表2 初始網格參數

將初始網格進行一次調整后的網格如圖2(b)所示，調整后再細分一次的網格如圖2(c)所示，在此基礎上再次調整后的網格如圖2(d)所示，圖2(e)、圖 2(f)分別為第二次調整網格后再進行一次、二次細分后的網格。圖2(g)為牙齒模型的渲染圖。

圖3 平均誤差與迭代次數的關系

3 結 論

本文把細分算法應用于力覺交互的虛擬現實牙科醫(yī)生手術培訓系統的虛擬場景建模中，構造出牙齒曲面的不同精確程度的網格，并且針對原始數據點云有噪聲的問題，在網格調整中加入了光順項使得構造的牙齒表面網格在滿足精度要求的同時具備一定的光順性。且細分算法簡單，易于實現。

[1]LI Zhong, MA Li-zhuang, TAN Wu-zheng, et al.Reconstruction from contour lines based on bi-cubic Bézier spline surface [J]. Journal of Zhejiang University SCIENCE A, 2006, 7(7)：1241-1246.

[2]吳 雯. 人工牙的三維重建及其交互實現[D]. 北京：中國科學院, 2000.

[3]Mikrogeorgis G, Lyroudia K L, Nikopoulos N, et al.3D computer-aided reconstruction of six teeth with morphological abnormalities [J]. International Endodontic Journal, 1999, 32(2)：88-93.

[4]Isaac Newton Lima da Silva, Gustavo Frainer Barbosa,Rodrigo Borowski Grecco Soares, et al. Creating three-dimensional tooth models from tomographic images [J]. Stomatologija, Baltic Dental and Maxillofacial Journal, 2008, (10)：67-71.

[5]Chaikin G. An algorithm for high speed curve generation [J]. Computer Graphics and Image Processing, 1974, (3)：346-349.

[6]Catmull E, Clark J. Recursively generated B-spline surfaces on arbitrary topological surfaces [J].Computer-Aided Design, 1978, 10(6)：350-355.

[7]Doo D, Sabin M. Behaviour of recursive division surfaces near extraordinary points [J].Computer-Aided Design, 1978, 10(6) ：356-360.

[8]Ball A A, Storry D J T. Conditions for tangent plane continuity over recursively generated B-spline surfaces [J].ACM Trans. Graph., 1988, 7(2)：83-102.

[9]Ball A A, Storry D J T. A matrix approach to the analysis of recursively generated B-spline surfaces [J].Computer-Aided Design, 1986, 18(8)：437-442.

[10]Charles Teorell Loop. Smooth subdivision surfaces based on triangles [D]. Master's thesis, University of Utah, Department of Mathematics, 1987.

[11]Hiromasa Suzuki, Shingo Takeuchi, Fumihiko Kimura,et al. Subdivision surface fitting to a range of points[C]//Proceedings of the 7th Pacific Conference on Computer Graphics and Applications. Seoul Korea, 1999：158-167.

Tooth Surface Reconstruction by Catmull-Clark Subdivision and Mesh Modification

WANG Yu-hui, ZHANG Yu-ru
( School of Mechanical Engineering and Automation, Beijing University of Aeronautics and Astronautics, Beijing 100191, China )

Bounding box of data points are obtained according to data points of tooth surface, based on which initial control meshes are constructed. The limit points of Catmull-Clark subdivision are calculated by the expression derived by means of matrix diagonalization. Vertexes of control mesh are moved in order that each limit point approximates to its data point. Then subdivision and modification of the meshes are applied repeatedly so that the mesh at each level becomes deformed gradually under the “guide” of points to approximate to data points of tooth surface. Thus the three-dimensional reconstruction of tooth model is achieved.

computer aided geometric design; surface reconstruction; subdivision; tooth model

TP 391

A

1003-0158(2010)06-0056-06

2009-04-15

王玉慧（1964-），女，河南鄭州人，副教授，博士，主要研究方向為計算機圖形圖像處理。