1、介紹

????????Edelsbrunner 引入的皮膚表面和具有豐富而簡單的組合和幾何結構，使其適合在生物計算中模擬大分子。 對這些表面進行網格劃分通常是進一步處理其幾何形狀所必需的，例如在數值模擬和可視化中。

????????皮膚表面由一組加權點（輸入球）和一個稱為收縮因子的標量定義。如果收縮因子等于一，則表面只是輸入球并集的邊界。對于小于一的收縮因子，由于出現連接球的球面和雙曲面的斑塊，皮膚表面變得切線連續。

????????此程序包使用中描述的算法構建由一組球和收縮因子定義的皮膚表面網格同位素。

????????實現了一種優化算法，用于對一組球的并集進行網格劃分。

2、定義一個skin曲面

????????左圖：兩個加權點（兩個虛線圓）的凸組合。右圖：加權點的表面曲線。較小的圓形成加權點的子集，其邊界是表面曲線。

????????本節首先簡要回顧了皮膚表面。

????????皮膚表面由一組有限個加權點 P 和一個收縮因子 s 定義，其中 0≤s≤1。加權點 p=(p,wp)∈R3×R 對應于一個中心為 p、半徑為 wp??√ 的球。權重為零的加權點稱為無權點。

????????加權點p=(p,wP)和無權點x之間的偽距離被定義為： π(p,x)=∥p?x∥2?wp,

????????其中p?x是p和x之間的歐幾里得距離。加權點p對應的球是π(p,?)的零集。請注意，如果wp<0，則球的半徑為虛數，并且零集為空集。

????????我們可以通過取加權點距離函數的凸組合來獲得加權點的凸組合。上圖左顯示了通過取虛線圓圈的凸組合獲得的加權點。

????????從加權點p=(p,wP)開始，通過與以p為中心的無權點進行凸組合獲得收縮加權點ps。形式上，ps=sp+(1-s)p'，其中p'=(p,0)。經過簡單計算后，我們得到ps=(p,s?wp)。通過將P中的每個加權點按比例s收縮獲得的集合Ps定義為Ps={ps∣p∈P}。上圖（左）中收縮的加權點顯示在上圖（右）中。

????????現在我們定義與一組加權點P相關聯的皮膚表面skns(P)。考慮輸入加權點的凸包的加權點集合。經過計算，可以發現每個加權點都在輸入球的并集中。接下來，我們通過收縮凸包中的每個加權點來收縮它們。因此，我們將相應（實數）輸入圓的半徑乘以因子s√。皮膚表面是該集合的邊界：

????????這里conv(P)?R3×R是加權點集P的凸包，而?表示相應球集的并集在R3中的邊界。

????????回想一下，輸入加權點的凸包中的每個加權點都包含在輸入加權點的并集中。因此，對于等于 1 的收縮因子，皮膚表面是輸入加權點并集的邊界。

????????根據皮膚表面的定義，輸入球的權重（它們的半徑平方）以s為因子縮小，皮膚表面包裹在縮小的輸入球周圍。為了使皮膚表面包裹在（未縮小的）輸入球周圍，我們可以首先將輸入球的權重乘以因子1/s，然后計算皮膚表面。

3、接口

????????皮膚表面包的接口由一個主要功能組成，即獲取一組加權點和收縮因子，并輸出網格表面。此外，它定義了類和函數，并對用于執行算法的主要步驟進行了分類。存在兩個全局類Skin_surface_3和Union_of_balls_3，它們都是概念SkinSurface_3的模型，并且存在從上述類的對象提取皮膚表面的網格（球的并集）的兩個函數。最后一個函數獲取一個網格和從中構建的Skin_surface_3（Union_of_balls_3）對象，并細化該網格。本節將更詳細地描述這些類和函數。

template <class WP_iterator, class Polyhedron_3>
void make_skin_surface_mesh_3(Polyhedron_3 &p,WP_iterator begin, WP_iterator end,FT shrink_factor=.5,int nSubdiv=0,bool grow_balls = true);

????????下面是make_skin_surface_mesh_3函數的參數解釋：InputIterator points_begin：輸入迭代器，指向加權點的起始位置。加權點用于定義皮膚表面的幾何形狀。InputIterator points_end：輸入迭代器，指向加權點的結束位置。WeightedPoint：表示加權點的類型，其中包含點的坐標和權重。double shrink_factor：收縮因子，用于控制生成的皮膚表面的平滑程度。較小的收縮因子將導致更平滑的表面，而較大的收縮因子將使表面更加突出。unsigned int number_of_subdivision_steps：細分步驟數，用于控制生成的網格的精細程度。較大的細分步驟數將生成更精細的網格，而較小的細分步驟數將生成較粗糙的網格。OutputIterator mesh_begin：輸出迭代器，指向生成的網格的起始位置。網格將以Polyhedron_3的形式存儲。

????????皮膚表面包的主要功能是獲取加權點的迭代器范圍、收縮因子和細分步驟數，并在 Polyhedron_3 中輸出網格?

????????其中，FT是Weighted_points使用的數字類型。

????????為了更好地控制算法，還可以單獨執行不同的步驟。首先，從加權點的迭代器范圍和收縮因子中創建一個 Skin_surface_3 對象。可選參數是一個布爾值，它指示輸入加權點是否應以這樣的方式增長，即皮膚表面圍繞輸入球而不是收縮的輸入球。

template <class SkinSurfaceTraits_3>
Skin_surface_3(WP_iterator begin, WP_iterator end,FT shrink_factor,bool grow_balls = true);

?????????模板參數應實現SkinSurfaceTraits_3概念。類型WP_iterator是SkinSurfaceTraits_3定義的加權點的迭代器，FT是加權點使用的數值類型。

????????對于等于一的收縮因子，皮膚表面是輸入球的并集的邊界。在這種情況下，用于網格化皮膚表面的算法大大簡化。這些優化在Union_of_balls_3類中實現。球并集類的構造函數類似，除了缺少收縮因子：

template <class SkinSurfaceTraits_3>
Union_of_balls_3(WP_iterator begin, WP_iterator end,bool grow_balls = true);

????????使用概念SkinSurface_3的模型，可以生成與皮膚表面同質的粗網格。使用帶有簽名的函數mesh_skin_surface_3()?

template <class SkinSurface_3, class Polyhedron>
void mesh_skin_surface_3(const SkinSurface_3 &skin_surface, Polyhedron &p);

?????????最后一個函數采用（粗略的）網格，通過應用給定數量的1-4分割操作（每個三角形被分割成四個子三角形）并在皮膚表面移動新的頂點，在原地對網格進行細分。如果未指定迭代次數，則執行一次細分步驟。需要使用SkinSurface_3概念的對象來構造粗網格，以在皮膚表面上移動新的點。

template <class SkinSurface_3, class Polyhedron >
void subdivide_skin_surface_mesh_3 (const SkinSurface_3 &skinsurface,Polyhedron &p,int iterations = 1);

4、時間

????????粗網格的構建和第一次細分的時間以秒為單位，在具有1Gb內存的Pentium 4、3.5 GHz上完成。

Data set	Number of weighted points	Coarse mesh	first subdivision step
Caffeine	23	0.2 sec.	0.05 sec.
Gramicidin A	318	5 sec.	2 sec.

CGAL 5.6 - 3D Skin Surface Meshing: User Manual?