图形学——Cell/Worley Noise

发表于2018-04-23

Cell Noise，有的又叫 Worley Noise，基于 voronoi，由Steven Worley在1996年提出了新的算法，新的算法并不能用来对既定的特征点进行 voronoi 区域划分，因此更多的被用来生成噪声，因此又被称作Worley Noise。

1、理论

voronoi的原始实现在一个博客里有相关细节，iq的文章则是采用了Steven Worley的算法，算法步骤在网站有讲到，下面就以iq最基础的示例源码来做分析（代码我做了精简和修改，但依然可以生成voronoi图）

// The MIT License
// Copyright © 2013 Inigo Quilez
vec2 hash( vec2 p ) ｛ p=vec2(dot(p,vec2(127.1,311.7)),dot(p,vec2(269.5,183.3))); return fract(sin(p)*18.5453); ｝
// return distance, and cell id
vec2 voronoi( in vec2 x )
｛
    vec2 n = floor( x );
    vec2 f = fract( x );
    vec3 m = vec3( 8.0 );
    for( int j=-1; j<=1; j++ )
    for( int i=-1; i<=1; i++ )
    ｛
        vec2  g = vec2( float(i), float(j) );
        vec2  o = hash( n + g );
        vec2  r = g - f + o;
        float d = dot( r, r );
        if( d<m.x )
            m = vec3( d, o );
    ｝
    return vec2( sqrt(m.x), m.y );
｝
void mainImage( out vec4 fragColor, in vec2 fragCoord )
｛
    vec2 p = fragCoord.xy/max(iResolution.x,iResolution.y);
    // computer voronoi patterm
    vec2 c = voronoi( 4.0*p );
    // colorize
    vec3 col = vec3(c.y);   
    fragColor = vec4( col, 1.0 );
｝

iq的算法是在GPU上跑的，因此voronoi的特征点并非是一开始就已经定下来的，而是在计算的过程中生成的，而生成的核心就是伪随机函数 hash，因为是伪随机函数，因此只要输入不变，输出的随机数就不会变。其大概流程如下：

将uv划分为4x4的网格，取整数得到网格顶点，取小数得到像素在网格中的位置
对于每一个像素，遍历其对应的网格以及相邻的8个网格
每次遍历，根据网格位置通过伪随机函数生成特征点，然后计算像素到特征点的距离，代码中写的是 r = g - f + o，这是因为伪随机函数的结果总是处于 [0, 1) ，必须加上顶点位移才能正确的得到像素和特征点的距离，然后用 m 记录距离最小的距离值和对应的特征点
最后，通过对应的特征点是否一致就能判断像素是否属于同一多边形内，在图形上则更直观，只需要将像素对应的特征值与像素颜色直接挂钩就可以了

上面的代码在Unity中运行效果如下：