perlin噪声算法实践

    Perlin噪声算法，可以实现将一组散点进行平滑连接过渡，不仅适用于二维连线，同样适用于三维连线，甚至是n维的平滑过渡。

使用场景

    使用的场景也非常多，于二维，比如想要将统计数据平滑连接已显示趋势的曲线统计图，于三维生成平滑的地形，而非断崖。

    如果我们不使用噪声算法，直接连接，得到的效果图可能如下图所示。首先随机了几个顶点，然后进行直线连接，肉眼可见的尖锐顶点与生硬的过渡直线。

    如果使用了噪声算法，则可以达成如下效果。虽然我们也能依稀辨别顶点的位置，但是顶点并没有上图的那么尖锐了，对于两点之间的过渡，也让人觉得非常舒适。

    当然，噪声算法有很多可以选择的，不同的噪声算法可以实现不同的效果，因为也是初次研究，所以采用了最简单的perlin噪声算法。

什么是perlin算法

    perlin算法，是通过在两数之间使用平滑函数进行计算得到一个细粒度下光滑的数组。

光滑函数

    这里，涉及到一个数学概念——平滑函数。那么什么是平滑函数呢？从百度百科查询到明确的定义：光滑函数(smooth function)是指在其定义域内无穷阶数连续可导的函数。从数理上来说，就是对于函数f(x)，其导数及高阶导数 f'、f''、f'''、...在定义域上都可导。如f(x)=x²，f'(x) = 2x,f''(x) = 2,f'''(x) = 0,f''''(x) = 0，...这就是一个平滑函数。当然对于f(x)=x²大家肯定不陌生了。同样的，对于正余弦函数、指数函数、对数函数等等都是光滑函数。用同样的道理可以推导出来。

    当然，光滑函数有无数种，数理上可能无法直观的感受，那么从图像上来看的特征就是，在定义域上，没有突变和尖锐的拐点。下图是函数f(x) = |x|%2 的示例，该图就不是平滑函数。

    一般的，perlin噪声会使用如下的函数： f(x) = 6 * x^5 - 15 * x^4 + 10 * x^3 。图像如下所示，可以看出来其图像在[0,1]区间上近似S形。

噪声算法

    上文介绍了什么是光滑函数，那么光滑函数应该要怎么关联到噪声上来呢？答案是使用插值来填充间断点之间的空隙，我喜欢称之为细粒度，细粒度可大可小，如散点用的是整数，那么细粒度可以是0.1，则在两个整数之间插入了9个数值，如果细粒度是0.01，则两个整数之间插入了99个数值。对于相邻两个点p1(x1,y1), p2(x2,y2)，目标中间点p0(x0,y0)，使用平滑函数func，

有 f(x0) = y1 + (y2 - y1) * func ((x0 - x1) / (x2 - x1)) 

    其中(x0 - x1) / (x2 - x1)得到的是目标点在两个点之间所处的位置（或者换个视角理解就是百分比进度），所以取值必然是[0,1]，然后将该进度映射到对应的平滑值，计算y轴方向的取值。

代码实现

    首先是产生随机采样点，我这里产生了40个随机点，值域为[-2,2]，定义域为x∈[-20,20],且x∈Z。

Dot[] raw = new Dot[40]; // 原始采样点
for (int i = 0; i < raw.length; i++) {
    Dot tmp = new Dot(i - 20, Math.random() * 2 * (Math.random() > 0.5 ? 1 : -1));
    raw[i] = tmp;
}

    这边也标注了一下生成后的效果（注：因为每次都是随机，所以后文的采样点和下图的采样点效果会不一致）。

    接着是对这些采样点进行插值平滑连接，采用perlin算法实现。算法及函数核心：

// perlin噪声算法private double noise(Dot fi, Dot se, double x){
    return fi.y + (se.y - fi.y) * func((x - fi.x)/(se.x - fi.x));
}
// 平滑函数
private double func(double x) {
    return 6 * Math.pow(x, 5) - 15 * Math.pow(x, 4) + 10 * Math.pow(x, 3);
}

    插值示例代码见下（grid与细粒度有关，如grid=10就表示细粒度为1/grid=0.1）。这里的 [插入原始点] 其实可以不用单独拎出来，可以放入插值中进行处理，因为对于平滑函数x=0时，值就是原始值，我这边单独写，是因为要进行后续的图像绘制，有个坐标映射实际像素点的操作。

ArrayList<Dot> dots = new ArrayList<>();
for (int i = 0; i < raw.length - 1; i++) {

    // 插入原始点
    dots.add(raw[i]);

    // 取值
    Dot fi = raw[i];
    Dot se = raw[i + 1];
    
    // 插值
    for (int j = 1; j < grid; j++) {
        double x = fi.x + j * 1.0 / grid;
        Dot ist = new Dot(x, noise(fi, se, x));
        dots.add(ist);
    }
}

    这样，就会有 40 * grid 个点产生了，细粒度为 1/grid，grid越大，则连线越平滑。对于计算机显示器来说，最小的单位为像素点，为了不因为0.5像素点问题导致断点（如grid细粒度结果为0.7，1.1，最终两个点在像素上都会在同一个纵向上），x坐标需要按像素连续记录，而非虚拟的坐标轴点记录位置。

二维散点

    上面将一系列一维散点升到二维连续图像，而对于二维散点升三维平滑曲线也同理。

    对于原始点ABCD，要求其中的G点，只需要按照一维散点的方式，对A、B计算出E，对C、D计算出F，最后就可以对E、F计算出G。

    代码示例如下，其实和一维计算方式没有本质上的区别。

// 二维梯度
int dots = 30;
double[][] balls = new double[dots][dots];
List<Ball> list = new ArrayList<>();
for (int i = 0; i < dots; i++) {
	for (int j = 0; j < dots; j++) {
		balls[i][j]  = Math.random() * 1;
		Ball ball = new Ball(i, j, balls[i][j]);
		list.add(ball);
	}
}

// 插值运算
for (int i = 0; i < dots - 1; i++) {
	for (int j = 0; j < dots - 1; j++) {
		// 获得初始点
		Dot raw = new Dot(i,j);

		// 差值
		for (int m = 0; m < grid; m++) {
			for (int n = 0; n < grid; n++) {
				// <i + m, j + n>
				// 水平A
				double A = noise(
						new Dot(j,balls[i][j]),
						new Dot(j + 1,balls[i][j + 1]),
						n * 1.0 / grid + j);
				// 水平B
				double B = noise(
						new Dot(j,balls[i + 1][j]),
						new Dot(j + 1,balls[i + 1][j + 1]),
						n * 1.0 / grid + j);
				// 竖直C
				double C = noise(
						new Dot(i, A),
						new Dot(i + 1, B),
						m * 1.0 / grid + i);


				Ball ball = new Ball(i + m * 1.0 / grid, j + n * 1.0 / grid, C);
				list.add(ball);
			}
		}
	}
}

    下图是按照高度进行深浅绘制的显示效果。

    当然,黑白看起来并不优雅，于是乎，对高度值进行的颜色的映射（有参考腾讯云公众号发布的这篇文章：QQ 25年技术巡礼丨技术探索下的清新设计，打造轻盈简约的QQ9）。下图是其文章提到的图和代码：

// 获取噪音灰度值
float gray = noise(x, y);
// 颜色区间大小
float rangeSize = 1 / colorCount;
// 对应的颜色索引
int colorIndex = ceil(gray / rangeSize);
// 把gray值转换成两个不同颜色的区间值
gray -= rangeSize * colorIndex;
gray /= rangeSize;
// 颜色插值计算
mix(color1, color2, gray);

    我这边也理解了该方案，进行了实践，我的代码与效果图，效果还是非常不错的：

// draw
int[] colors = {0xE8FFF0,0x7CD1F8,0x0099FF,0x026EFF,0xC862FB,0xFF8A74,0xFAE366};
for (Ball ball : list) {
	Ball.BallInt ballInt = ball.toInt();


	double rangeSize = 1.0 / colors.length;
	int colorIndex = (int)Math.ceil(ball.z / rangeSize);
	g.setColor(new Color(colors[colorIndex - 1]));

	ballInt.x -= grid * 3;
	ballInt.y += grid * 3;
	g.drawLine(ballInt.x, ballInt.y,ballInt.x, ballInt.y);
}

尾声

    在颜色绘制后又尝试了不少有意思的改变，下面依次展示。以此作结。