[發明專利]一種刻蝕和沉積工藝三維元胞信息存儲結構及操作方法

有效

• 申請號: 201310218939.0
• 申請日: 2013-06-04
• 公開（公告）號: CN103336858A
• 公開（公告）日: 2013-10-02
• 發明（設計）人: 楊宏軍;宋亦旭;孫曉民;賈培發
• 申請（專利權）人: 清華大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 廖元秋

1.一種刻蝕和沉積工藝元胞自動機模擬時三維元胞信息存儲結構，其特征在于，設l、w和h分別代表三維元胞自動機模型中沿x軸、y軸和z軸三個方向元胞劃分的數量；每個元胞看作三維離散歐幾里得空間中的點(x,y,z),x∈[0..l-1]，y∈[0..w-1]，z∈[0..h-1]，x、y和z分別表示該元胞在x軸、y軸和z軸上坐標位置；三維元胞信息存儲結構定義如下：

將三維元胞自動機模型每一列元胞{(x,y,z)|y∈[0..h]}，x∈[0..l-1]，y∈[0..w-1]，定義為一個元胞，則將該三維元胞自動機模型轉變為二維元胞自動機模型；

創建一個二維靜態數組Cell2d[l][w]來表示該二維元胞自動機模型信息,該二維靜態數組包含l×w個元素，每個元素對應一組下標(x,y)，x和y分別表示該元素在x軸和y軸坐標位置，x∈[0..l-1]，y∈[0..w-1]，l、w分別稱為x維和y維的長度，該二維靜態數組每個元素Cell2d[x][y]存儲xy平面上(x,y)處一列元胞{(x,y,z)|y∈[0..h]}的信息；

該二維靜態數組每個元素Cell2d[x][y]的信息包括：記錄(x,y)列所有表面元胞的個數cellnum和一個用來存儲(x,y)列所有表面元胞一維動態數組zcell；該一維動態數組zcell中每個元素除記錄元胞的信息c(x,y,z)外，還增加一個記錄表面元胞沿z軸坐標值z，用于還原三維元胞自動機模型；一維動態數組zcell中所有元素按坐標值z由小到大排序；

其中:

Cell2d[x][y]:表示二維靜態數組Cell2d中，下標(x,y)對應的元素；

Cell2d[x][y].cellnum:表示二維靜態數組中元素Cell2d[x][y]中記錄(x,y)列所有表面元胞的個數cellnum;

Cell2d[x][y].zcell:表示二維靜態數組中元素Cell2d[x][y]中存儲(x,y)列所有表面元胞一維動態數組zcell;

Cell2d[x][y].zcell[znum]:表示二維靜態數組中元素Cell2d[x][y]中一維動態數組zcell中下標znum對應的元素;

c(x,y,z)用于描述元胞(x,y,z)的對應狀態。

2.一種利用如權利要求1所述存儲結構中元胞操作方法，包括對元胞的隨機訪問、元胞信息的添加、刪除及修改，其特征在于，具體包括以下步驟：

1）隨機訪問元胞(x,y,z)：

1.1）根據要訪問的元胞(x,y,z)在x軸和y軸的兩個坐標x和y，得到與該元胞(x,y,z)相同坐標x和y的元胞列的二維靜態數組中元素Cell2d[x][y]；

1.2）根據該二維靜態數組中元素Cell2d[x][y]的一維動態數組首元素的坐標位置z_min和尾元素的坐標位置z_max，判別要訪問的元胞(x,y,z)的坐標z是否在這兩數之間，若不滿足，則該元胞(x,y,z)不是表面元胞，則返回無效下標；否則利用二分法對該一維動態數組中的元素進行搜索，若查找到該元胞(x,y,z)的坐標z與該一維動態數組中元素的坐標z相同，則該元胞(x,y,z)是表面元胞，返回該元胞(x,y,z)在一維動態數組中的下標，否則返回無效下標；

2）添加新表面元胞(x,y,z)的信息c(x,y,z)：

2.1）根據要添加的元胞(x,y,z)在x軸和y軸的兩個坐標x和y，得到與該元胞(x,y,z)相同坐標x和y的元胞列的二維靜態數組中元素Cell2d[x][y]；

2.2）利用步驟1）訪問元胞(x,y,z)，根據返回下標值znum判斷元胞(x,y,z)是否是表面元胞，若znum≠-1，則元胞(x,y,z)是表面元胞，再用c(x,y,z)的信息修改一維動態數組中元素Cell2d[x][y].zcell[znum]的內容后，操作結束；否則繼續；

2.3）將(x,y)列中表面元胞數量增1，Cell2d[x][y].cellnum＝Cell2d[x][y].cellnum+1；

2.4）新建包含Cell2d[x][y].cellnum個元素的一維動態數組newzcell，并將c(x,y,z)的信息和原來一維動態數組Cell2d[x][y].zcell中的表面元胞信息一起按z坐標值由小到大的順序插入到一維動態數組newzcell中；

2.5）刪除一維動態數組Cell2d[x][y].zcell占用的內存空間，并將newzcell賦給它Cell2d[x][y].zcell＝newzcell；

3）刪除表面元胞(x,y,z)的信息c(x,y,z)

3.1）根據要刪除的元胞(x,y,z)在x軸和y軸的兩個坐標x和y，得到與該元胞(x,y,z)相同坐標x和y的元胞列的二維靜態數組中元素Cell2d[x][y]；

3.2）利用步驟1）訪問元胞(x,y,z)，根據返回下標值znum判斷元胞(x,y,z)是否是表面元胞，若znum==-1，則元胞(x,y,z)不是表面元胞，則操作結束，否則繼續；

3.3）將(x,y)列中表面元胞數量減1，Cell2d[x][y].cellnum=Cell2d[x][y].cellnum-1；

3.4）新建包含Cell2d[x][y].cellnum個元素一維動態數組newzcell，將原來一維動態數組Cell2d[x][y].zcell的表面元胞信息中除數組下標為znum元素外的剩余元素依次從左到右按順序插入到newzcell中；

3.5）刪除原來一維動態數組Cell2d[x][y].zcell占用的內存空間，并將newzcell賦給它Cell2d[x][y].zcell=newzcell；

4）修改表面元胞(x,y,z)的信息c(x,y,z)

4.1）根據要修改的元胞(x,y,z)在x軸和y軸的兩個坐標x和y，得到與該元胞(x,y,z)相同坐標x和y的元胞列的二維靜態數組中元素Cell2d[x][y]；

4.2）利用步驟1）訪問元胞(x,y,z)，根據返回值znum判斷元胞(x,y,z)是否是表面元胞，若znum==-1，則元胞(x,y,z)不是表面元胞，則利用步驟2）添加表面元胞信息c(x,y,z)后，操作結束，否則繼續；

4.3）用c(x,y,z)的信息修改一維動態數組中元素Cell2d[x][y].zcell[znum]的內容。