一种基于Worley噪声的物品随机分布方法

2019-09-09宁方美

数码世界 2019年5期

关键词：网格

宁方美

摘要：本文涉及计算机地形场景模拟技术领域，特别是涉及一种基于沃利噪声的物品随机分布方法及装置。本文提出的方法可以快速、实时、高效地在图形场景中随机分布物品。很好的避免了随机分布时出现两个物品交叉碰撞的情况，同时可以快速效地在指定区域内搜索物品。

关键词：沃利噪声细胞噪声网格物品分布随机分布

计算机图形学中，在平面地形或者球体星球进行随机物品分布的方法通常是这样的，首先在空间中随机生成物品的坐标位置，然后进行放置。这种方法的特点是简单易于实现，但同时也存在明显的缺点，一是随机位置的分布很容易出现两个物品交叉碰撞的情况;二是如果要对物品进行按区域查找只能通过遍历所有物品来实现，效率较低。

本文基于沃利噪声，实现了一种较好的物品随机分布方法，并在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算法根据网格控制点的势力范围对空间区域进行划分，可以快速有效的进行物品随机分布。