Apr 1

尝试在Canvas中绘制2D动态光照

Lrdcq , 2018/04/01 11:08 , 程序 , 閱讀(5286) , Via 本站原創
现在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]了。

//交叉算法
//入参是一条直线和一个线段
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绘制的可行性~
关键词:canvas
logo