如何写一个用GPU来抽奖的程序

我们奇舞团有一个传统，那就是每年年会时，会由我给大家现场写一个抽奖程序，所有在场的人共同review代码，确认没有问题后，开启这一年愉快的年会抽奖活动。

写抽奖程序，核心无非就是将数据按照随机的规则进行抽取，确保每个人抽中奖品的概率是公平的。

今年，我写了一个比较另类的抽奖程序——使用GPU而不是CPU进行抽奖。

那用GPU抽奖究竟是怎么一回事？

我们具体一步一步来看一下。

首先，我们创建了一个基础的页面：

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>抽奖</title>
  <style>
    div, button {
      font-size: 3rem;
    }
    canvas {
      background: #000;
    }
    span {
      margin-left: 20px;
    }
  </style>
</head>
<body>
  <div><button id="updateBtn">抽奖</button><span id="user"></span></div>
  <canvas id="glDoodle" width="512" height="512"></canvas>
</body>
</html>

这个页面上现在只有一个抽奖按钮，一个显示人名的span元素，和一个canvas元素 —— 既然是用GPU抽奖，我们肯定需要使用canvas元素。

这是页面运行后的样式，除了一个黑色的方块区域外，什么都没有。

接下来，我们开始写抽奖的JavaScript代码，这是一个WebGL的程序。原生WebGL的API比较复杂，为了简化操作，我写了一个叫 gl-renderer 的开源库。

<script type="module">
  import GLRenderer from './lib/gl-renderer.js';
  const container = document.getElementById('glDoodle');
  const doodle = new GLRenderer(container, {autoUpdate: false});
  doodle.render();
</script>

在这里，我们使用GLRenderer从canvas元素创建一个WebGL的上下文环境，并执行渲染。

这时候，界面上没有任何变化，这是因为，我们没有给WebGL渲染定义对应的着色器。

接下来我们写一个简单的片元着色器：

#ifdef GL_ES
precision mediump float;
#endif

void main() {
  gl_FragColor = vec4(0, 0, 1.0, 1.0);
}

这个着色器主要代码只有一行：gl_FragColor = vec4(0, 0, 1.0, 1.0);

这个代码的作用是将纯蓝色输出到屏幕上，赋给gl_FragColor的是一个四维向量，代表一个RGBA色值，不过与Web标准的RGBA色值不同，着色器中的RGBA四个通道的取值都是0到1之间，所以vec4(0, 0, 1.0, 1.0)相当于rgba(0,0,255,1)。

我们将这个着色器读取并加载到 renderer 中：

import GLRenderer from './lib/gl-renderer.js';
const container = document.getElementById('glDoodle');
const doodle = new GLRenderer(container, {autoUpdate: false});
(async function() {
  const program = await doodle.load('./lib/fragment.glsl');
  doodle.useProgram(program);
  doodle.render();
}());

现在我们的UI界面由原来的黑色变成了蓝色:

为什么这段着色器代码能让整个Canvas输出为蓝色呢？很重要的一点是GPU渲染是并行的，片元着色器操作的是像素，gl_FragColor = vec4(0, 0, 1.0, 1.0);将当前像素设为蓝色，而实际执行绘制的时候，画布上的每一个像素都会同时被执行这段着色器代码，所以我们看到的就是每个点都被绘制成蓝色，于是整个画布就呈现蓝色了。

在这里，我们忽略了另一个着色器——顶点着色器（vertex shader），但是没有关系，我们创建的renderer会启用默认的顶点着色器，关于顶点着色器的问题，我们在专栏后续的文章中会有深入的探讨。

我们只是改变画布颜色，显然没法完成我们期待的抽奖功能。接下来我们要做的事情，是必须要让画布的不同位置呈现不同的颜色。换句话说，我们要在画布上创建不同的区块，创建多少个区块，取决于多少人参与抽奖。假设我们有100人，那么我们可以创建一个10X10的区块。

我们可以通过修改shader来做到：

#ifdef GL_ES
precision mediump float;
#endif

uniform vec2 resolution;

void main() {
  vec2 st = gl_FragCoord.xy / resolution;
  st = floor(10.0 * st);
  gl_FragColor = vec4(0, 0, 1.0, 1.0);
}

在这里，我们先声明一个resolution的变量，我们会在JavaScript中将画布的宽高传入进来。

然后，我们通过gl_FragCoord.xy / resolution，将当前渲染像素点的x、y坐标对应到0~1的范围，然后我们将它乘10并向下取整，这样我们就可以得到[0,0] [9,9]的100块不同的区域。

import GLRenderer from './lib/gl-renderer.js';
const container = document.getElementById('glDoodle');
const doodle = new GLRenderer(container, {autoUpdate: false});
const width = 512,
  height = 512;

(async function() {
  const program = await doodle.load('./lib/fragment.glsl');
  doodle.useProgram(program);
  doodle.uniforms.resolution = [width, height];
  doodle.render();
}());

我们修改JS代码将[width, height]通过doodle.uniforms传入shader中。

不过这时候，我们的页面还没有变化，因为虽然我们划分了10X10的区域，但是每个区域显示的颜色还是相同的，都是蓝色。

我们可以修改gl_FragColor让每一块根据st显示不同的颜色，比如：

gl_FragColor = vec4(st / 10.0, 1.0, 1.0);

现在我们可以对区块呈现不同的颜色，也就意味着我们可以来通过随机数让区块呈现为我们想要的颜色，或者保持为黑色。

#ifdef GL_ES
precision mediump float;
#endif

highp float random(vec2 co) {
  highp float a = 12.9898;
  highp float b = 78.233;
  highp float c = 43758.5453;
  highp float dt= dot(co.xy ,vec2(a,b));
  highp float sn= mod(dt,3.14);
  return fract(sin(sn) * c);
}

uniform vec2 resolution;
uniform float rate;
uniform float seed;

void main() {
  vec2 st = gl_FragCoord.xy / resolution;
  st = floor(10.0 * st);
  float p = random(st + seed);
  p = step(p, rate);
  gl_FragColor = vec4(0, 0, 1.0, 1.0) * p;
}

我们修改shader，使用一个比较简单的伪随机函数，我们需要增加两个变量，rate和seed，rate控制中奖概率，seed保证随机。

p = step(p, rate);，step函数当rate不小于p的时候，返回1.0，否则返回0。

这样，p只会是0或1，因此，gl_FragColor = vec4(0, 0, 1.0, 1.0) * p; 要么是 vec4(0, 0, 1.0, 1.0)即蓝色，要么是 vec4(0, 0, 0, 0) 是透明的。而出现蓝色块和透明块的几率是由rate控制的。

import GLRenderer from './lib/gl-renderer.js';
const container = document.getElementById('glDoodle');
const doodle = new GLRenderer(container, {autoUpdate: false});
const width = 512,
  height = 512;

(async function() {
  const program = await doodle.load('./lib/fragment.glsl');
  doodle.useProgram(program);
  doodle.uniforms.resolution = [width, height];
  doodle.uniforms.rate = 0.3; // 30% 中奖概率
  doodle.uniforms.seed = Math.random(); // 随机种子
  doodle.render();
}());

这样，我们就让画布随机呈现出不同的色块：

蓝色区域的块表示中奖，黑色区域的块表示未中奖，中奖的概率是rate控制，现在的设置是30%。

最后我们还要做的一件事情是，如果要多次抽奖，我们要让已中奖的人不能再次中奖。

由于GPU是并行渲染，我们并不能在shader中拿到当前像素以外的其他像素的情况，也就是说，我们没法直接获得已中奖区域的信息。不过，我们可以将上一次输出的结果，以图片纹理的方式输入回shader中：

#ifdef GL_ES
precision mediump float;
#endif

highp float random(vec2 co) {
  highp float a = 12.9898;
  highp float b = 78.233;
  highp float c = 43758.5453;
  highp float dt= dot(co.xy ,vec2(a,b));
  highp float sn= mod(dt,3.14);
  return fract(sin(sn) * c);
}

uniform vec2 resolution;
uniform float rate;
uniform float seed;

uniform sampler2D texture;
varying vec2 vTextureCoord;

void main() {
  vec2 st = gl_FragCoord.xy / resolution;
  st = floor(10.0 * st);
  float p = random(st + seed);
  p = step(p, rate);

  vec2 texCoord = vec2(vTextureCoord.x, 1.0 - vTextureCoord.y);
  vec4 texColor = texture2D(texture, texCoord);

  gl_FragColor = texColor + vec4(0, 0, 1.0, 1.0) * (1.0 - sign(length(texColor))) * p;
}

我们声明一个texture变量，vTextureCoord是它的图片纹理坐标，因为我们的texture变量对应的纹理图片是Bitmap图片格式，所以对应的坐标的y轴是要反转一下的。

然后我们修改设置像素颜色代码：

  gl_FragColor = texColor + vec4(0, 0, 1.0, 1.0) * (1.0 - sign(length(texColor.rgb))) * p;

如果当前的texColor有色值，那么sign(length(texColor))的值肯定是1，1.0 - sign(length(texColor.rgb))就会是0，这时候呈现的颜色就是texColor + 0，即texColor本身，否则，因为texColor是vec4(0)，所以最终显示的颜色就是vec4(0, 0, 1.0, 1.0) * 1.0 * p。

import GLRenderer from './lib/gl-renderer.js';
const container = document.getElementById('glDoodle');
const doodle = new GLRenderer(container, {autoUpdate: false});
const width = 512,
  height = 512;

const button = document.getElementById('updateBtn');

(async function() {
  const textureCanvas = new OffscreenCanvas(width, height);
  const ctx = textureCanvas.getContext('2d');
  const program = await doodle.load('./lib/fragment.glsl');
  doodle.useProgram(program);

  button.addEventListener('click', () => {
    const texture = doodle.createTexture(textureCanvas.transferToImageBitmap());
    doodle.uniforms.resolution = [width, height];
    doodle.uniforms.rate = 0.2; // 20% 中奖概率
    doodle.uniforms.seed = Math.random(); // 随机种子
    doodle.uniforms.texture = texture;
    doodle.render();
    doodle.deleteTexture(texture);
    ctx.drawImage(doodle.canvas, 0, 0, width, height);
  });
}());

在JS代码中，我们创建一个离屏Canvas，然后将它的内容输出为Bitmap，作为纹理传给shader，我们把绘制的步骤给移到button的click事件中，这样我们就能在前一次中奖的基础上继续抽奖了。

至此，我们最核心的抽奖代码就写完了。当然我们还有很多细节要处理，比如每次抽奖之后，因为要把已中奖的人排除在总人数之外，所以rate需要做修正。我们还要把区块对应到具体的人名上，这样才能真正完成抽奖。还有很多交互细节也需要修改。

最终完成的代码，详细见GitHub仓库。

akira-cn / FE_You_dont_know

如何用GPU来实现一个抽奖程序 #27

如何写一个用GPU来抽奖的程序