一種基于Worley噪聲的物品隨機(jī)分布方法

寧方美

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

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

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

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

1 Worley噪聲介紹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3總結(jié)

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

參考文獻(xiàn)

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

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

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

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