如何用GPU来实现一个抽奖程序
akira-cn opened this issue · 0 comments
如何写一个用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仓库。