寧方美

摘要：本文涉及計算機地形場景模擬技術(shù)領(lǐng)域，特別是涉及一種基于沃利噪聲的物品隨機分布方法及裝置。本文提出的方法可以快速、實時、高效地在圖形場景中隨機分布物品。很好的避免了隨機分布時出現(xiàn)兩個物品交叉碰撞的情況，同時可以快速效地在指定區(qū)域內(nèi)搜索物品。

關(guān)鍵詞：沃利噪聲 細(xì)胞噪聲 網(wǎng)格 物品分布 隨機分布

計算機圖形學(xué)中，在平面地形或者球體星球進(jìn)行隨機物品分布的方法通常是這樣的，首先在空間中隨機生成物品的坐標(biāo)位置，然后進(jìn)行放置。這種方法的特點是簡單易于實現(xiàn)，但同時也存在明顯的缺點，一是隨機位置的分布很容易出現(xiàn)兩個物品交叉碰撞的情況;二是如果要對物品進(jìn)行按區(qū)域查找只能通過遍歷所有物品來實現(xiàn)，效率較低。

本文基于沃利噪聲，實現(xiàn)了一種較好的物品隨機分布方法，并在2D和3D模式下分別進(jìn)行了實現(xiàn)，取得了較好的效果。

1 Worley噪聲介紹

在圖形學(xué)中，我們使用噪聲就是為了把一些隨機變量引入到程序中，可以實現(xiàn)例如火焰、地形、云朵等效果模擬。圖形學(xué)中有很多不同的噪聲算法，Perhn噪聲被大量用于云朵、火焰和地形等自然環(huán)境的模擬;Simplex噪聲在其基礎(chǔ)上進(jìn)行了改進(jìn)，提到了效率和效果;而Worley噪聲被提出用于模擬一些多孔結(jié)構(gòu)，例如紙張、木紋、細(xì)胞、水波、巖石等。本文不比較不同噪聲算法的應(yīng)用，本文重點是研究如何使用Worley噪聲進(jìn)行有效物品隨機分布。

細(xì)胞噪聲（Cell Noise），常用來模擬細(xì)胞類有孔紋理，是一種基于Voronoi圖的噪聲生成算法，1996年，在Siggraph96上，StevenWorley發(fā)表的論文《A Cellular Texture Basis Function》提出了一種用于實現(xiàn)cellular texture方法，能有有限的資源時間內(nèi)快速生成Cell噪聲，因此Cell噪聲也常被稱為Worley噪聲。Worley噪聲主要是根據(jù)網(wǎng)格控制點的勢力范圍對空間區(qū)域進(jìn)行劃分的方法。

2基于Worley算法實現(xiàn)隨機物品分布的實現(xiàn)步驟

（1）步驟1，按照固定步長生成網(wǎng)格點

該步驟中，按照固定步長生成規(guī)則的網(wǎng)格點，二維平面下生成的網(wǎng)格點為正方形分布，三維立體下生成的網(wǎng)格點為立方體分布。固定步長即為相鄰兩個網(wǎng)格點的間距，假設(shè)其數(shù)值為l。

首先取出坐標(biāo)點（X，y）的整數(shù)值（m，n），將（m，n）視為網(wǎng)格點編號并獲取其實際位置。獲取與網(wǎng)格點（m.n）相鄰的8個網(wǎng)格點（m-l，n-l）、（m-l，n）、（m.n-l）、（m+l， n-l）、（m-l， n+l）、（m+1，n）、（m，n+l）、（m+l，n+l），并獲取其實際位置。然后從這九個網(wǎng)格點中找出一個距離點（x，y）最近的一個設(shè)置（i，j）同時得到最近的距離d。

（7）步驟7，三維空間的情況下，給定一個三維坐標(biāo)點（x，y，z），計算出距離其最近的物品所在網(wǎng)格點的編號（i，j，k），并返回距離值d。

首先取出坐標(biāo)點（x，y）的整數(shù)值（m，n，p），將（m，n，p）視為網(wǎng)格點編號并獲取其實際位置。獲取與網(wǎng)格點（m，n，p）相鄰的27個網(wǎng)格點并獲取其實際位置然后從這九個網(wǎng)格點中找出一個距離點（x，y'z）最近的一個設(shè)置（i，j，k），同時得到最近的距離d。圖2最大移動距離為0.25生成的網(wǎng)格點圖3最大移動距離為0.5生成的網(wǎng)格點

每個網(wǎng)格點都有一個編號，二維下為（i，j）分別表示該網(wǎng)格點的行號與列號;三維下為（i，j .k）分別表不該網(wǎng)格點的行號、列號與層號。

圖1為二維平面下的固定步長的網(wǎng)格點分布。

（2）步驟2，隨機移動網(wǎng)格點，移動距離小于固定步長的一半。

該步驟中，對網(wǎng)格點進(jìn)行隨機移動，移動方向隨機生成，移動距離也隨機生成，但不超過固定步長的一半;其中，移動后的網(wǎng)格點作為隨機物體的空間位置。假設(shè)網(wǎng)格點的最大移動距離為S：

那么固定步長網(wǎng)格點圖1則為二維平面下最大移動距離S為0生成的網(wǎng)格點分布;圖2為二維平面下最大移動距離S為0.25生成的網(wǎng)格點分布;圖3為二維平面下最大移動距離S為0.5生成的網(wǎng)格點分布。

對比圖2與圖3會發(fā)現(xiàn)：S數(shù)值越小，網(wǎng)格越接近正方形;S數(shù)值越大，相鄰兩個網(wǎng)格點的最小距離就越小。

（3）步驟3，劃分每一個網(wǎng)格點的勢力范圍，空間中的一點到哪個網(wǎng)格點最近，即該點就在該網(wǎng)格點的勢力范圍內(nèi)。沃利噪聲的特點就是它可以十分高效的得到空間中任意一個坐標(biāo)位置的網(wǎng)格點。

（4）步驟4，為每一個網(wǎng)格點設(shè)置某種物體，即實現(xiàn)了隨機物品的分布。

（5）步驟5，提供一種點選網(wǎng)格點的方法。計算出距離其最近的物品所在網(wǎng)格點的編號，并返回距離值。

（6）步驟6，二維空間的情況下，給定平面中的一個坐標(biāo)點（x，y），計算出距離其最近的物品所在網(wǎng)格點的編號（i，j），并返回距離值d。數(shù)碼世界P44

3總結(jié)

本文簡單介紹了噪聲算法在圖形學(xué)中的應(yīng)用，重點講述使用Worley算法實現(xiàn)物品隨機分布的操作步驟，并分別從2D和3D模式下進(jìn)行講解，同時分析了每個階段的實現(xiàn)效果。效果表明，基于Worley算法根據(jù)網(wǎng)格控制點的勢力范圍對空間區(qū)域進(jìn)行劃分，可以快速有效的進(jìn)行物品隨機分布。

參考文獻(xiàn)

[1]蓋杉，鮑中運基于深度學(xué)習(xí)的高噪聲圖像去噪算法[J]，自動化學(xué)報，2019.

[2]裴玉，劉桂陽，師翊虛擬現(xiàn)實中基于Hermite曲線實現(xiàn)固定漫游路徑算法與優(yōu)化[J]，黑龍江八一農(nóng)墾大學(xué)學(xué)報2014 （2）：71-24.

[3]http：//zh .wiklpedia.org/wiki/樣條函數(shù)

[4lhttps： //blog.csdn.net/yolon3000/article/details/783 86701，WorleyNoise