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

寧方美

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

關鍵詞：沃利噪聲 細胞噪聲 網格 物品分布 隨機分布

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

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

1 Worley噪聲介紹

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

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

2基于Worley算法實現隨機物品分布的實現步驟

（1）步驟1，按照固定步長生成網格點

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

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

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

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

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

圖1為二維平面下的固定步長的網格點分布。

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

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

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

對比圖2與圖3會發現：S數值越小，網格越接近正方形;S數值越大，相鄰兩個網格點的最小距離就越小。

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

（4）步驟4，為每一個網格點設置某種物體，即實現了隨機物品的分布。

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

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

3總結

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

參考文獻

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

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

[3]http：//zh .wiklpedia.org/wiki/樣條函數

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