来自Facebook的骚操作，O
初学纯代码MAC应用开发小记
Apr
1
现在canvas在h5的2D游戏中已经逐渐开始大显身手，各自高端大气上档次的h5游戏引擎也开始崭露头角，看着unity都可以导出为网页了，真特么牛啊。但是，在不使用webgl的情况下，canvas的能力是非常受限的。之前我们也讨论过通过mesh化贴图来实现canvas图像扭曲这里，再复杂一点，对于动态灯光和阴影的绘制怎么处理呢？这次我们就在尝试下这个话题。
问题细化
宽泛的定性这个问题之后，回过头来，我们具体想想我们解决的问题是一个什么场景。如果是3d场景，灯光和阴影的表现是投影，即将3d物体投影到2d的面上；如果是2d场景，灯光和投影更常见的表现方式则是明暗，即渲染的关照本身而不是投影，毕竟2d场景的投影是线，是无法被表现的。那么我们最终要达到的效果就如下：
实现如图的效果，我们的计算中有几个重要的元素：
- 硬光源，在2d场景中处理软光源也太复杂了，我们初步尝试以硬点光源为准进行计算。
- 遮挡物，在2d场景中，遮挡物即实际存在的像素块。
- 计算范围，由于2d场景的阴影不考虑是否存在投影物体，所以计算范围理论上是无限远，实际上最远是画布的大小即可。
参考3d场景中光照计算的方案：通过计算光源到模型的mesh边射线到对应物体的投影区域来绘制。那么最简单的，对于2d的图像，我们也可以mesh化图形并且通过连接光源到mesh图形边界的射线来实现。
mesh法
这里就是我们首先想到的方法：图形mesh法。这个思路和对于3d场景投影处理的思路很像，直观的画出来就是如图：
整个计算的图形中，存在三个关键点：
- light：即光源点：
- A：对于光源图形的外边界点，light到A的射线是计算得到阴影边界线的关键点。
- B：如上射线与其他边的交点，这是阴影边界线结束的关键点。
由以上计算路径可知道，计算B的位置是依赖light到A的射线计算的，那么对于所有的从light到mesh的点的射线，到底会有哪些情况呢？
- 就如上图，light到A1的射线，经过A1，打到最近的阻挡物上，得到B1
- 如下图A2，light射到A2的同时，也被阻挡住无法进行下去了，它同时也是B2
- 如下图A3，light在射到A3之前，已经打到前面的障碍物上了，得到了B2
因此得到我们mesh法最粗暴的解决方案：
- 前提是我们所有计算阴影的区域是由点和线段组成
- 遍历光源到所有点的射线
- 遍历每一条射线和所有的线段的交点
- 找到最近的交点
这样，我们就可以寻找到所有的B类的点了。
射线和线段的交点的算法
这里涉及到一个问题是，我们已知射线[Light,A]和线段[Sa,Sb]，怎样才能快速计算得到他们的交点呢？
我们首先尝试表示出这两组点对应的直线表达式，对于[Light,A]组成的射线，我们表示为直线R，其中任意一点[x,y]可以表示为：
x = Rx + Rdx x T1
y = Ry + Rdy x T1
其中T1为任意值，dx,dy可以通过Light和A两点查来得到，并且显然：
- 当T1为0的时候，Rx，Ry为表达式起始点，也就是射线的起始点，即Light点
- T1为1的时候，即[Rx + Rdx,Ry + Rdy]就是我们的A点
- 那么作为一条射线，只要T1>=0，[x,y]就是这条射线上的点。
同理，我们来看[Sa,Sb]表示的线段S：
x = Sx + Sdx x T2
y = Sy + Sdy x T2
和上面的道理一摸一样，不同的是，作为一点线段：
- 当T2为0，即Sa点，当T2为1，即Sb点
- 那么作为一条线段，只要0<=T2<=1，[x,y]才是线段上的点。
那么简单了，连接两个方程：
Rx + Rdx x T1 = Sx + Sdx x T2
Ry + Rdy x T1 = Sy + Sdy x T2
很容易得到解T1T2，并且T1>=0，0<=T2<=1才是有效解。代入即可得到实际的交点[x, y]了。
后续处理
我们知道了怎么计算一个射线到线段的交点，那综合整个图形，我们怎么才能计算到所有光线/阴影区域的所有AB类边界点，并且知道如何把这些点连接起来呢？
这里，我们采用一个比较投机取巧的办法，如下图
- 我们把每一条射线R1，向正逆时针各偏转一小丢丢，分别拆分为R11与R12射向关节点A
- 那么R11会刚刚好错过A点，打到背后的物体上得到B11
- R12会刚好打到A点旁边的线段上，得到B12
- 并且B11无限趋近于R1的B_r1，B12无限趋近于A_r1
- 并且通过R11与R12的角度，我们可以得到B11与B12的有序连接方式
所以对于这一个完整的图：
我们从顺时针的方向扫描每一条射线打在线段上的点：
- R0在画布右边缘打出了R01，i上打出了R02
- R1在i上打出了R11，item上打出了R12
- R2在item上打出了R21和R22
- R3在item上打出了R31，画布右边缘打出了R32
因此，继续顺时针链接起来所有的点，和整个光线区域的边缘，就能得到我们绘制的光线/应用多边形了。这样就完成了我们实现的目标。
Demo:http://lrdcq.com/test/light-canvas/mesh.html
- 有一个点值得注意的是，因为所有图形都得mesh化，所以demo中的圆肯定是大量边围起来
该方案总结
可以来回尝试试用一下该demo，和demo对应的源码，是有一些值得注意下的地方的：
- 这个方案很明显碰撞测试运算复杂度并不高，最终实现的算法碰撞的计算量为 点数量x边数量x2，因此如果场景中需要测试的边界可以简化，那对应的计算量也会大大减小。但是对应的，如果需要测试的图形是非常非常复杂的，比如场景中有大量的圆，计算量就会被放得超级大，如果有像素级的图形的话，就没法算了，这是该方案最大的问题
- 不过参考3d空间一般会做的深度优化，如果我们光照计算是明显有向的，那对于计算点和边的选取，也可以做相当大的剪枝[比如裁剪逆光向边和点]
- 多尝试上面那个demo，会注意到，如果鼠标移动的那个item和别的item/画布边界有重叠，算出来的光线会有问题。原因如下图：
- 很明显，如果这两个item相交，那相交的到的新mesh新增了两个蓝色的点，而这两个点不在我们计算范围之内的，因此会出现错误。因此显然，如果场景中有item重叠的场景，还是会增加不少计算量
- 整个计算过程虽然快，但是携带的信息量并不多，比如很重要的，实际光线边界/像素距离光源的距离信息和类似等价信息是没有的，如果有相关渲染比如阶梯阴影的需求的话，还得做更多的计算
像素法
上面的mesh法我说最大的问题是，测试图形复杂了或者像素化的，就没法计算。主要原因是，本方案本来就是针对的2d游戏，亲，2d游戏几乎没有mesh一说的，基本上都是矩形的贴图区域加上实际半透明的贴图/逐帧动画组成的，显然对于这样的素材做光线阴影，mesh法是无法做到的，因此第二种方法就是逐像素进行计算。
比如相同的demo，还是中心照射出360的光线，计算过程是：
- 首先以光线照射范围为中心得到光线画布，并且将画布划分为四部分，每个部分进行计算
- 比如如上图的右侧部分，画布边宽是512px
- 那么，我们的计算是，对画布右边界的每个像素，发射一条射线进行碰撞测试。实际的计算方法是从x轴水平推进，当前计算点的y就是对应在画布边界上的y的等比位置。对每个点进行判断是否是遮挡物，记录下每条画布边射线第一个遇到的遮挡物的距离信息，就可以了。如下图，通过从左到右的计算，我们为Ya找到了B点，并且储存max[Ya]=len(B)
- 那么经过四个方向的计算，我们得到四个数组，分布储存了画布每个边方向的最近的光线照射距离
- 最后渲染像素点的时候，判断每个像素对应的边界点，再去看当前像素点的距离信息是不是比记录的远，如果是更远的点，就是没有被光线照射到，否则是光线照射区域。如下图，对于任意点X，我们可以计算到它对应画布边界Ya，然后到max[Ya]去查距离信息，如果len(X)>max[Ya]，就是如图情况，就是光线照射不到的区域，否则能照射到。依据这个判断和正好有的距离信息去渲染就好了。
Demo:http://lrdcq.com/test/light-canvas/pixel.html
- 里面包含了一个mesh法做不到的，即透半明贴图级像素光线碰撞测试
- 里面的圆也是arc画的了，不是模拟的了
- 结合距离信息，这个demo的光线会随着距离衰弱
该方案总结
- 相对于像素法，该方法明显比mesh法消耗更多更多的性能，通过demo就能看出来。但是该方法的计算量不是随着测试物体的复杂度增加的，而是随着测试范围大小增加的。举一个实际场景，比如我是计算一个路灯下一个人的贴图的阴影，那么我只需要计算路灯的底部方向的贴图最大像素数即可：
显然，大部分游戏内都是类似的非四向光照的场景，同时由于是像素即贴图级别的计算，可以做一定的倍率缩放，只是缩放一倍，计算量也少了很多。
- 同时，由于计算的结果是携带距离信息的，就很容易做出如demo的光线进深和层次的效果，不需要做额外的计算；另外，碰撞测试是以像素为单位，那么碰撞的测试条件也相对自由，如demo直接alpha过滤也是非常快。
- 最后，该方法设计的既然是像素级扫描，当然是可以放到gpu中运算的，相关浮点运算的性能也能有较大的提升。
结论
本次测试验证了两种在Canvas中绘制2D动态光照的方法：
- Mesh法适合用在碰撞图形简单，但是碰撞测试范围大的场景，首要选择该方案，比如一些矢量化的二维游戏。
- 像素法适合在碰撞图形复杂/无法mesh化的场景，比如贴图拼装的一些游戏。
另外，验证了canvas绘制，而不是webgl/shader绘制的可行性～
问题细化
宽泛的定性这个问题之后，回过头来，我们具体想想我们解决的问题是一个什么场景。如果是3d场景，灯光和阴影的表现是投影，即将3d物体投影到2d的面上；如果是2d场景，灯光和投影更常见的表现方式则是明暗，即渲染的关照本身而不是投影，毕竟2d场景的投影是线，是无法被表现的。那么我们最终要达到的效果就如下：
实现如图的效果，我们的计算中有几个重要的元素：
- 硬光源，在2d场景中处理软光源也太复杂了，我们初步尝试以硬点光源为准进行计算。
- 遮挡物，在2d场景中，遮挡物即实际存在的像素块。
- 计算范围，由于2d场景的阴影不考虑是否存在投影物体，所以计算范围理论上是无限远，实际上最远是画布的大小即可。
参考3d场景中光照计算的方案：通过计算光源到模型的mesh边射线到对应物体的投影区域来绘制。那么最简单的，对于2d的图像，我们也可以mesh化图形并且通过连接光源到mesh图形边界的射线来实现。
mesh法
这里就是我们首先想到的方法：图形mesh法。这个思路和对于3d场景投影处理的思路很像，直观的画出来就是如图：
整个计算的图形中，存在三个关键点：
- light：即光源点：
- A：对于光源图形的外边界点，light到A的射线是计算得到阴影边界线的关键点。
- B：如上射线与其他边的交点，这是阴影边界线结束的关键点。
由以上计算路径可知道，计算B的位置是依赖light到A的射线计算的，那么对于所有的从light到mesh的点的射线，到底会有哪些情况呢？
- 就如上图，light到A1的射线，经过A1，打到最近的阻挡物上，得到B1
- 如下图A2，light射到A2的同时，也被阻挡住无法进行下去了，它同时也是B2
- 如下图A3，light在射到A3之前，已经打到前面的障碍物上了，得到了B2
因此得到我们mesh法最粗暴的解决方案：
- 前提是我们所有计算阴影的区域是由点和线段组成
- 遍历光源到所有点的射线
- 遍历每一条射线和所有的线段的交点
- 找到最近的交点
这样，我们就可以寻找到所有的B类的点了。
射线和线段的交点的算法
这里涉及到一个问题是，我们已知射线[Light,A]和线段[Sa,Sb]，怎样才能快速计算得到他们的交点呢？
我们首先尝试表示出这两组点对应的直线表达式，对于[Light,A]组成的射线，我们表示为直线R，其中任意一点[x,y]可以表示为：
x = Rx + Rdx x T1
y = Ry + Rdy x T1
其中T1为任意值，dx,dy可以通过Light和A两点查来得到，并且显然：
- 当T1为0的时候，Rx，Ry为表达式起始点，也就是射线的起始点，即Light点
- T1为1的时候，即[Rx + Rdx,Ry + Rdy]就是我们的A点
- 那么作为一条射线，只要T1>=0，[x,y]就是这条射线上的点。
同理，我们来看[Sa,Sb]表示的线段S：
x = Sx + Sdx x T2
y = Sy + Sdy x T2
和上面的道理一摸一样，不同的是，作为一点线段：
- 当T2为0，即Sa点，当T2为1，即Sb点
- 那么作为一条线段，只要0<=T2<=1，[x,y]才是线段上的点。
那么简单了，连接两个方程：
Rx + Rdx x T1 = Sx + Sdx x T2
Ry + Rdy x T1 = Sy + Sdy x T2
很容易得到解T1T2，并且T1>=0，0<=T2<=1才是有效解。代入即可得到实际的交点[x, y]了。
//交叉算法
//入参是一条直线和一个线段
let getIntersection = function(ray, segment) {
let r_px = ray.a.x;
let r_py = ray.a.y;
let r_dx = ray.b.x - ray.a.x;
let r_dy = ray.b.y - ray.a.y;
let s_px = segment.a.x;
let s_py = segment.a.y;
let s_dx = segment.b.x - segment.a.x;
let s_dy = segment.b.y - segment.a.y;
if ((r_dx * s_dy) == (r_dy * s_dx)) {
return null;//平行的情况
}
let T2 = (r_dx * (s_py - r_py) + r_dy * (r_px - s_px)) / (s_dx * r_dy - s_dy * r_dx);
let T1;
if (r_dx == 0) {
T1 = (s_py + s_dy * T2 - r_py) / r_dy;
} else {
T1 = (s_px + s_dx * T2 - r_px) / r_dx;
}
if (T1 < 0) return null; //r是射线
if (T2 < 0 || T2 > 1) return null;//s是线段
return {
x: r_px + r_dx * T1,
y: r_py + r_dy * T1,
T1: T1,
T2: T2
};
}后续处理
我们知道了怎么计算一个射线到线段的交点，那综合整个图形，我们怎么才能计算到所有光线/阴影区域的所有AB类边界点，并且知道如何把这些点连接起来呢？
这里，我们采用一个比较投机取巧的办法，如下图
- 我们把每一条射线R1，向正逆时针各偏转一小丢丢，分别拆分为R11与R12射向关节点A
- 那么R11会刚刚好错过A点，打到背后的物体上得到B11
- R12会刚好打到A点旁边的线段上，得到B12
- 并且B11无限趋近于R1的B_r1，B12无限趋近于A_r1
- 并且通过R11与R12的角度，我们可以得到B11与B12的有序连接方式
所以对于这一个完整的图：
我们从顺时针的方向扫描每一条射线打在线段上的点：
- R0在画布右边缘打出了R01，i上打出了R02
- R1在i上打出了R11，item上打出了R12
- R2在item上打出了R21和R22
- R3在item上打出了R31，画布右边缘打出了R32
因此，继续顺时针链接起来所有的点，和整个光线区域的边缘，就能得到我们绘制的光线/应用多边形了。这样就完成了我们实现的目标。
Demo:http://lrdcq.com/test/light-canvas/mesh.html
- 有一个点值得注意的是，因为所有图形都得mesh化，所以demo中的圆肯定是大量边围起来
该方案总结
可以来回尝试试用一下该demo，和demo对应的源码，是有一些值得注意下的地方的：
- 这个方案很明显碰撞测试运算复杂度并不高，最终实现的算法碰撞的计算量为 点数量x边数量x2，因此如果场景中需要测试的边界可以简化，那对应的计算量也会大大减小。但是对应的，如果需要测试的图形是非常非常复杂的，比如场景中有大量的圆，计算量就会被放得超级大，如果有像素级的图形的话，就没法算了，这是该方案最大的问题
- 不过参考3d空间一般会做的深度优化，如果我们光照计算是明显有向的，那对于计算点和边的选取，也可以做相当大的剪枝[比如裁剪逆光向边和点]
- 多尝试上面那个demo，会注意到，如果鼠标移动的那个item和别的item/画布边界有重叠，算出来的光线会有问题。原因如下图：
- 很明显，如果这两个item相交，那相交的到的新mesh新增了两个蓝色的点，而这两个点不在我们计算范围之内的，因此会出现错误。因此显然，如果场景中有item重叠的场景，还是会增加不少计算量
- 整个计算过程虽然快，但是携带的信息量并不多，比如很重要的，实际光线边界/像素距离光源的距离信息和类似等价信息是没有的，如果有相关渲染比如阶梯阴影的需求的话，还得做更多的计算
像素法
上面的mesh法我说最大的问题是，测试图形复杂了或者像素化的，就没法计算。主要原因是，本方案本来就是针对的2d游戏，亲，2d游戏几乎没有mesh一说的，基本上都是矩形的贴图区域加上实际半透明的贴图/逐帧动画组成的，显然对于这样的素材做光线阴影，mesh法是无法做到的，因此第二种方法就是逐像素进行计算。
比如相同的demo，还是中心照射出360的光线，计算过程是：
- 首先以光线照射范围为中心得到光线画布，并且将画布划分为四部分，每个部分进行计算
- 比如如上图的右侧部分，画布边宽是512px
- 那么，我们的计算是，对画布右边界的每个像素，发射一条射线进行碰撞测试。实际的计算方法是从x轴水平推进，当前计算点的y就是对应在画布边界上的y的等比位置。对每个点进行判断是否是遮挡物，记录下每条画布边射线第一个遇到的遮挡物的距离信息，就可以了。如下图，通过从左到右的计算，我们为Ya找到了B点，并且储存max[Ya]=len(B)
//计算放射线每个方向的最小遮挡物距离
for (let y = 0; y < width; y++) {
maxLengthRight[y] = Number.MAX_SAFE_INTEGER;
for (let x = halfWidth - 1; x >= 0 ; x--) {
let ty = (((y - halfWidth) * (halfWidth - x) / halfWidth >> 0) + halfWidth);
let tx = width - x - 1;
if (data[(ty * width + tx) * 4 + 3]) {//这里的判断条件是aplha通道是否为0
maxLengthRight[y] = (halfWidth - tx) * (halfWidth - tx) + (halfWidth - ty) * (halfWidth - ty);
break;
}
}
}- 那么经过四个方向的计算，我们得到四个数组，分布储存了画布每个边方向的最近的光线照射距离
- 最后渲染像素点的时候，判断每个像素对应的边界点，再去看当前像素点的距离信息是不是比记录的远，如果是更远的点，就是没有被光线照射到，否则是光线照射区域。如下图，对于任意点X，我们可以计算到它对应画布边界Ya，然后到max[Ya]去查距离信息，如果len(X)>max[Ya]，就是如图情况，就是光线照射不到的区域，否则能照射到。依据这个判断和正好有的距离信息去渲染就好了。
let fillImageLR = function(data, x, y, offset, maxOffset, array) {
let i = y * width + x;
if (!data[i * 4 + 3]) {
let length = (halfWidth - x) * (halfWidth - x) + (halfWidth - y) * (halfWidth - y);
if (length <= array[offset * width / maxOffset >> 0]) {
//执行渲染
}
}
}
//main
for (let x = 0; x < halfWidth; x++) {
let maxY = width - x * 2;
for (let y = 0; y < maxY; y++) {
fillImageLR(data, x, x + y, y, maxY, maxLengthLeft);
fillImageLR(data, width - x - 1, x + y, y, maxY, maxLengthRight);
}
}Demo:http://lrdcq.com/test/light-canvas/pixel.html
- 里面包含了一个mesh法做不到的，即透半明贴图级像素光线碰撞测试
- 里面的圆也是arc画的了，不是模拟的了
- 结合距离信息，这个demo的光线会随着距离衰弱
该方案总结
- 相对于像素法，该方法明显比mesh法消耗更多更多的性能，通过demo就能看出来。但是该方法的计算量不是随着测试物体的复杂度增加的，而是随着测试范围大小增加的。举一个实际场景，比如我是计算一个路灯下一个人的贴图的阴影，那么我只需要计算路灯的底部方向的贴图最大像素数即可：
显然，大部分游戏内都是类似的非四向光照的场景，同时由于是像素即贴图级别的计算，可以做一定的倍率缩放，只是缩放一倍，计算量也少了很多。
- 同时，由于计算的结果是携带距离信息的，就很容易做出如demo的光线进深和层次的效果，不需要做额外的计算；另外，碰撞测试是以像素为单位，那么碰撞的测试条件也相对自由，如demo直接alpha过滤也是非常快。
- 最后，该方法设计的既然是像素级扫描，当然是可以放到gpu中运算的，相关浮点运算的性能也能有较大的提升。
结论
本次测试验证了两种在Canvas中绘制2D动态光照的方法：
- Mesh法适合用在碰撞图形简单，但是碰撞测试范围大的场景，首要选择该方案，比如一些矢量化的二维游戏。
- 像素法适合在碰撞图形复杂/无法mesh化的场景，比如贴图拼装的一些游戏。
另外，验证了canvas绘制，而不是webgl/shader绘制的可行性～
渝公网安备 