从js的canvas开始展开，我们知道js的canvas中对图像的变换是非常有限的，移动旋转缩放，本质上是一个二维的变换矩阵，即transform方法对应的功能，对应的是a,b,c,d,e,f,0,0,1的矩阵，其实这也不是完全的二维变换矩阵，完整的参看这里。而同理，3d的变换矩阵，参看这里，canvas显然是不支持的，不止是js的canvas，大部分ui的framework的canvas都不支持3d变换的，毕竟实际贴图cpu计算图像拉伸成本太高。

需求

然而总有一些场景，我们需要涉及到除了二维变换之外的图形处理方式，比如我想得到这样的处理效果：



显然，这明显就是3d变换才能得到的东西，2d变换根本不可能实现，除非自己逐个像素点采样并且渲染（threejs的canvas渲染器就是这样实现的）。而显然，实际需求场景中，性能奇低就没有意义了，如果真有那么高的性能，当然也不用顾忌直接上webgl了。

最后得出结论是，不要拉伸，用投机取巧的方式来实现这个需求。

解决方案

其实参考普通的图形学原理和android中类似的需求场景，很快就有了可行的解决方案：绘制三角形组合。什么情况呢，看下图：



这看起来是一个扭曲的图片，但是拆分开仔细看，只是将两个二维变换的图片裁剪出的三角形拼接在一起了而已。非常投机取巧的实现了这个效果，并且如果没有和正常的拉伸图作对比，或者图片是非常整齐的网格图的话，只要不是拉伸得太过分，用户其实很难察觉出这个拉伸的不合理之处。

那么最基本的，我们要实现如何从一张图片中绘制出任意三角形。幸运的找到了使用相同方案的人，因此算法也就有了：

// uses affine texture mapping to draw a textured triangle
// at screen coordinates [x0, y0], [x1, y1], [x2, y2] from
// img *pixel* coordinates [u0, v0], [u1, v1], [u2, v2]
function drawTexturedTriangle(img, x0, y0, x1, y1, x2, y2,
                                   u0, v0, u1, v1, u2, v2) {
 
  ctx.beginPath();
  ctx.moveTo(x0, y0);
  ctx.lineTo(x1, y1);
  ctx.lineTo(x2, y2);
  ctx.closePath();
 
  x1 -= x0;
  y1 -= y0;
  x2 -= x0;
  y2 -= y0;
 
  u1 -= u0;
  v1 -= v0;
  u2 -= u0;
  v2 -= v0;
 
  var det = 1 / (u1*v2 - u2*v1),
 
      // linear transformation
      a = (v2*x1 - v1*x2) * det,
      b = (v2*y1 - v1*y2) * det,
      c = (u1*x2 - u2*x1) * det,
      d = (u1*y2 - u2*y1) * det,
 
      // translation
      e = x0 - a*u0 - c*v0,
      f = y0 - b*u0 - d*v0;
 
  ctx.save();
  ctx.transform(a, b, c, d, e, f);
  ctx.clip();
  ctx.drawImage(img, 0, 0);
  ctx.restore();
}

可以看到，由于canvas并没有提供变换位图绘制的方法，其实我们做的是变换整个画布到需要的位置，并且通过clip功能事先绘制裁剪区域把需要绘制的三角形绘制确定，最后绘制出来。这个算法的入参也很清晰，即三角形3点的xy位置和uv贴图位置，虽然uv实际传的是图片中的坐标，不是0-1的标准uv，不过这个算法也是万能的了。

细分

就像上面那个博客中的一样，真正的拉伸场景下，总会有视角让我们觉得很奇怪，如下图：



那咋办，向博客中那样，继续切割图片细分呗。

当然，最粗暴但是有效的方法，不用像博客中那样画x，而是单纯的细分网格就行了。同样的图片拉伸，我们来对比一下1x1和2x2和4x4和8x8的网格绘制的图片：




显然，随着图片的切割和细分，到4x4开始，就几乎看不出图像中存在棱角了。当然，这种方式的渲染，随着分割次数的增加，性能消耗有可能会平方级的上升（不确定），不过肯定远比真实的拉伸性能好很多。

另外需要注意的是，这里的网格划分是用的等分划分，而等分划分是不符合透视规则的，比如看8x8的网格，就会明显看出这个面就像是凹下去的一样。如果需要做看起来更合理的拉伸，还是需要真正的3d透视变换，下文再谈。

另外划分网格这种方案其实更多用在图片扭曲等场景中，和容易对齐的是安卓的canvas的drawBitmapMesh这个方法，它的效果就是把一个位图绘制在任意的网格上，之前有过相关讨论（Android简单实现界面扭曲与简单的物理效果实现）。不过那个方法的循环绘制是在安卓底层(c/cpp)实现的，性能当然随便干过我们js写的这玩意儿。

缝隙

注意看到上面参考的那个博客和上面的部分图片，在实际使用三角形拼接成大面积图像的时候，会出现比较明显的拼接缝隙。检查三角形的数据，数据是肯定没问题的，有可能是canvas的clip功能固有的特性（平滑锯齿）带来的负面影响，那么我们如何处理呢？

最显而易见的方法，即拓展三角形。并不是让三角形变大，三角形变大会导致图像变形，当然不合理，而是基于我们在canvas中的实现，让我们裁剪三角形的区域变大。

对于扩大三角形的算法，我们针对每一个角使用通用的算法，即向外拓展。另外，我们不用追求规则的拓展，只要能拓展开一丢丢就可以了。因此理论上，拓展的点只需要都在两条边“外”，即红色的区域即可，如下图：



怎么找一个刚刚在红色区域的点呢？最简单的方法，当然是用两条边的向量和，再限定到刚刚超出去的位置即可，实际算法如下：

 const DRAW_IMAGE_EXTEND_EX = 3;

 static extendVert(x0, y0, x1, y1, x2, y2) {
  var x = 2*x0 - x1 - x2, y = 2 * y0 - y1 - y2;
  var d = Math.sqrt(DRAW_IMAGE_EXTEND_EX / (x * x + y * y));
  return [x0 + x * d, y0 + y * d];
 }
 
  //use width DRAW_IMAGE_EXTEND to fix gap in images
  var s0 = Vert2D.extendVert(x0, y0, x1, y1, x2, y2);
  var s1 = Vert2D.extendVert(x1, y1, x0, y0, x2, y2);
  var s2 = Vert2D.extendVert(x2, y2, x1, y1, x0, y0);
  //fix end

  ctx.beginPath();
  ctx.moveTo(s0[0], s0[1]);
  ctx.lineTo(s1[0], s1[1]);
  ctx.lineTo(s2[0], s2[1]);
  ctx.closePath();

其中对于每一个点，计算的延伸距离是根号3的像素，实际边延伸距离平均不会超过一个像素，但是已经可以刚好掩盖住缝隙了。当然，在循环中大量调用Math.sqrt会十分影响性能，如果不会出现特别小的vert的话，可以把sqrt给省略掉。另外中间涉及到的临时变量考虑转移到外部作缓存区，来避免重复申请空间带来的消耗。

最后，我们获得的算法是：

 static drawImageToContextWithPoints(img ,ctx ,x0 ,y0 ,x1 ,y1 ,x2 ,y2 ,u0 ,v0 ,u1 ,v1 ,u2 ,v2) {
  u0 *= img.width;
  u1 *= img.width;
  u2 *= img.width;
  v0 *= img.height;
  v1 *= img.height;
  v2 *= img.height;

  //use width DRAW_IMAGE_EXTEND to fix gap in images
  s0 = Vert2D.extendVert(x0, y0, x1, y1, x2, y2);
  s1 = Vert2D.extendVert(x1, y1, x0, y0, x2, y2);
  s2 = Vert2D.extendVert(x2, y2, x1, y1, x0, y0);
  //fix end

  ctx.beginPath();
  ctx.moveTo(s0[0], s0[1]);
  ctx.lineTo(s1[0], s1[1]);
  ctx.lineTo(s2[0], s2[1]);
  ctx.closePath();
 
  x1 -= x0;
  y1 -= y0;
  x2 -= x0;
  y2 -= y0;
 
  u1 -= u0;
  v1 -= v0;
  u2 -= u0;
  v2 -= v0;
 
  det = 1 / (u1*v2 - u2*v1);
  a = (v2*x1 - v1*x2) * det;
  b = (v2*y1 - v1*y2) * det;
  c = (u1*x2 - u2*x1) * det;
  d = (u1*y2 - u2*y1) * det;
  e = x0 - a*u0 - c*v0;
  f = y0 - b*u0 - d*v0;
 
  ctx.save();
  ctx.transform(a, b, c, d, e, f);
  ctx.clip();
  ctx.drawImage(img, 0, 0);
  ctx.restore();
 }

数据结构

前面都说到mesh，vert这样的概念了，熟悉3d编程和图形学相关的童鞋应该也知道了，这个结构就是一个标准的3d模型数据结构。因此最基本的，是如下3个类型结构：

class Point2D {
 constructor(x, y, u, v) {
  this.x = x;
  this.y = y;
  this.u = u;
  this.v = v;     
 }
}

class Point3D {
 constructor(x, y, z, u, v) {
  this.x = x;
  this.y = y;
  this.z = z;
  this.u = u;
  this.v = v;     
 }
}

class Vert {
 constructor(p0, p1, p2) {
  this.p0 = p0;
  this.p1 = p1;
  this.p2 = p2;
 }
}

class Mesh {
 constructor() {
  this.points = [];
  this.verts = [];
 }
}

除了2d和3d的点，vert是值得三角形，但是里面只需要记录每个点在一个list中的id就可以了，毕竟点会有重复的，记录对象虽然是引用，也还是不科学并且不可序列化。至于mesh，当然是点和三角形的集合啦，只有通过mesh才能构成完整的图形并且渲染出来。

3d变换

有了完整的数据结构，我们再来做3d的变换就是轻而易举的了，毕竟一切看起来是拉伸的图形，都可以通过正矩形的网格mesh进行变换来实现。生成一个等分网格的方法当然很简单：

 static createMapMesh(width, height, divW, divH) {
  var m = new Mesh2D();
  var widthSingle = width/divW ,heightSingle = height/divH;
  var uSingle = 1/divW ,vSingel = 1/divH;
  for (var i=0 ;i<=divH; i++) {
   for (var j=0 ;j<=divW; j++) {
    m.points.push(new Point3D(j*widthSingle ,i*heightSingle ,0 ,j*uSingle ,i*vSingel));
   }
  }
  for (var i=0 ;i<divH; i++) {
   for (var j=0 ;j<divW; j++) {
    var startPoint = (divW + 1) * i + j;
    m.verts.push(new Vert(startPoint+1, startPoint, startPoint+divW+1));
    m.verts.push(new Vert(startPoint+divW+1, startPoint+divW+2, startPoint+1));
   }
  }
  return m;
 }

然后做变换，本质上就是1x4和4x4的矩阵做乘法咯。矩阵运算的死板代码就不用贴了，只是对mesh中的每一个点做多次矩阵乘法就可以了。位移旋转缩放和必不可少的透视矩阵，都是图形学的知识反正知道就好，如果确实想细看的话，建议看看threejs的Matrix代码。最后看实际变换的结果如下，这次的拉伸看起来就是平整合理的了吧。



其他

当然，mesh图像绘制的用处除了单纯的静态拉伸，还有很多更实用的作用，比如完成各种各样酷炫的动画和动效了，最后在这里抛砖引玉举一个demo吧。



这个鲤鱼旗地址：http://lrdcq.com/test/canvas_mesh_fish.html
另一个鲤鱼demo地址：http://lrdcq.com/test/canvas_mesh_fishbg.html
另另一个鲤鱼demo地址：http://lrdcq.com/test/canvas_mesh_fish3d.html
跪求更多实用场景！