汉字笔顺动画C端实现&B端原理 - [大力智能 前端]

973次阅读  |  发布于3年以前

一、简介

笔顺后台的目标是只要对于给定的字体文件（WOFF, OTF, TTF ）以及需要的字形（汉字，字母 or 其他各国的语言），就能产出与之对应的笔顺动画数据。是对开源项目Make me han zi[1]的实践。

二、效果演示

展示效果

大力硬件端展示效果

后台数据资源

后台产出笔顺动画的 json 文件，并通过 CDN 资源分发。确定字体的情况下，一个字形对应唯一一个数据资源（字形通过encodeURI，并去除"%"进行编码，即"我" -> "E68891"）。业务方可以通过拼接 URL 直接获取到对应的笔顺静态资源。

亮点功能一

|笔画的拆解

亮点功能二

|笔顺方向调节

亮点功能三

|缩放&平移功能

三、动画实现介绍

这里主要是解释如何去使用笔顺后台生产的数据

/** 笔顺动画原数据 */

{"strokes":["M 350 571 Q 380 593 449 614 Q 465 615 468 623 Q 471 633 458 643 Q 439 656 396 668 Q 381 674 370 672 Q 363 668 363 657 Q 364 621 200 527 Q 196 518 201 516 Q 213 516 290 546 Q 303 550 316 556 L 350 571 Z","M 584 466 Q 666 485 734 497 Q 746 496 754 511 Q 755 524 729 533 Q 693 554 622 527 Q 598 520 575 511 L 537 499 Q 518 495 500 488 Q 442 472 386 457 L 337 446 Q 327 446 179 416 Q 148 409 173 392 Q 212 365 241 376 Q 287 389 339 404 L 387 416 Q 460 438 545 457 L 584 466 Z","M 386 457 Q 387 493 398 517 Q 405 535 390 548 Q 371 564 350 571 C 323 583 303 583 316 556 Q 315 556 316 555 Q 338 519 337 478 Q 337 462 337 446 L 339 404 Q 340 343 339 289 L 338 241 Q 337 180 334 133 Q 333 115 323 109 Q 317 105 250 119 Q 238 122 239 114 Q 240 108 249 100 Q 309 42 328 6 Q 341 -10 357 3 Q 390 36 390 126 Q 387 169 387 265 L 387 306 Q 387 355 387 416 L 386 457 Z","M 339 289 Q 254 261 161 229 Q 139 222 101 221 Q 86 220 85 207 Q 84 192 94 184 Q 119 166 157 147 Q 169 144 182 154 Q 239 199 338 241 L 387 265 Q 477 314 484 318 Q 499 327 498 337 Q 492 343 479 340 Q 434 324 387 306 L 339 289 Z","M 635 195 Q 690 75 797 -14 Q 876 -62 898 -47 Q 920 -37 914 3 Q 905 34 899 152 Q 900 174 894 178 Q 890 179 884 160 Q 857 75 838 60 Q 823 56 785 88 Q 710 155 670 226 L 644 279 Q 599 381 584 466 L 575 511 Q 547 659 576 752 Q 586 779 543 805 Q 509 827 489 825 Q 470 824 479 795 Q 503 752 507 707 Q 517 601 537 499 L 545 457 Q 573 334 612 245 L 635 195 Z","M 612 245 Q 558 197 452 138 Q 442 132 448 128 Q 455 124 468 126 Q 523 135 574 160 Q 608 175 635 195 L 670 226 Q 706 260 747 317 Q 762 336 778 354 Q 788 361 785 374 Q 781 386 753 410 Q 734 428 723 428 Q 708 427 707 411 Q 701 354 644 279 L 612 245 Z","M 687 669 Q 718 648 754 623 Q 770 613 786 615 Q 798 618 801 632 Q 802 648 789 678 Q 780 697 746 708 Q 665 726 651 715 Q 647 711 651 697 Q 655 687 687 669 Z"],"medians":[[[458,627],[392,631],[336,588],[274,552],[258,550],[253,542],[220,530],[212,532],[203,522]],[[174,404],[215,398],[241,402],[672,514],[742,512]],[[323,556],[351,542],[365,522],[361,116],[340,67],[246,113]],[[100,206],[124,195],[163,189],[492,334]],[[492,807],[537,760],[538,627],[569,435],[612,299],[676,170],[717,112],[779,48],[817,22],[859,12],[880,78],[891,140],[886,147],[894,173]],[[723,412],[737,365],[664,259],[594,198],[489,142],[454,132]],[[657,710],[750,668],[781,634]]],"strokeInfos":[{"strokeMode":29,"strokeName":"撇"},{"strokeMode":27,"strokeName":"横"},{"strokeMode":40,"strokeName":"竖钩"},{"strokeMode":1,"strokeName":"提"},{"strokeMode":4,"strokeName":"斜钩"},{"strokeMode":29,"strokeName":"撇"},{"strokeMode":31,"strokeName":"点"}]}

如何渲染字形

原数据中strokes对应的字形中每一笔的笔画轮廓数据

<svg version="1.1" viewBox="0 0 1024 1024">
    {/* 田字格绘制 */}
    <g
        key="wordBg"
        stroke="var(--color-text-4)"
        strokeDasharray="1,1"
        strokeWidth="1"
        transform="scale(4, 4)"
     >
        <line x1="0" y1="0" x2="256" y2="0"></line>
        <line x1="0" y1="0" x2="0" y2="256"></line>
        <line x1="256" y1="0" x2="256" y2="256"></line>
        <line x1="0" y1="256" x2="256" y2="256"></line>
        <line x1="0" y1="0" x2="256" y2="256"></line>
        <line x1="256" y1="0" x2="0" y2="256"></line>
        <line x1="128" y1="0" x2="128" y2="256"></line>
        <line x1="0" y1="128" x2="256" y2="128"></line>
    </g>
    {/* 文字svg路径 */}
    <g transform="scale(1, -1) translate(0, -900)">
        {strokes.map((strokePath, idx) => (
           <path key={strokePath} d={strokePath} />
        ))}
    </g>
</svg>

这里为什么不是移动 1024 单位长度呢？因为，TTF字体规范中有一个baseline的概念；在当前的坐标系里面，红色线为字体的基准线；yMax = 900， yMin=-124。因此，需要将字形往下移动到baseline的位置。 从图中坐标系（原点在baseline与左边界的交点处，y 轴正方向朝上）可以看出，跟svg原本的坐标系（原点在左上角，y 轴正方向朝下）是有差别的，所以一开始需要transform的变换，对齐我们选择的标准字体的坐标系。

如何做出动画效果

const lengths = medians
    .map((x) => getMedianLength(x))
    .map(Math.round);
let totalDuration = 0;
for (let i = 0; i < medians.length; i++) {
    const offset = lengths[i] + kWidth;
    const duration = (delay + offset) / speed / 60;
    const fraction = Math.round((100 * offset) / (delay + offset));
    animations.push({
      animationId: `animation-${i}`,
      clipId: `clip-${i}`,
      keyframeId: `keyframes${i}`,
      path: paths[i],
      delay: totalDuration,
      duration,
      fraction,
      length: lengths[i],
      offset,
      spacing: 2 * lengths[i],
      stroke: strokes[i],
      width: kWidth,
    });
    totalDuration += duration;
}
const animationStyle = `@keyframes ${keyframeId} {
        0% {
            stroke: blue;
            stroke-dashoffset: ${animation.offset};
            stroke-width: ${animation.width};
        }
        ${animation.fraction}% {
            /* animation-timing-function: step-end; */
            stroke: blue;
            stroke-dashoffset: 0;
            stroke-width: ${animation.width};
        }
        100% {
            stroke: var(--color-text-1);
            stroke-width: ${STANDARD_LEN};
        }
    }
    #${animationId} {
        animation: ${keyframeId} ${duration}s linear ${delay}s both;
    }
`;
<g key={`${animationId}${playCount}`}>
    <style>{animationStyle}</style>
    <clipPath key={clipId} id={clipId}>
        <path d={stroke} />
    </clipPath>
    <path
        id={animationId}
        clipPath={`url(#${clipId})`}
        d={path}
        fill="none"
        strokeDasharray={`${length} ${spacing}`}
        strokeLinecap="round"
    />
</g>

四、数据生产原理

字形点位信息获取

TTF 字体文件规范

利用开源工具opentype.js[5]解析 TTF 字体文件

笔画拆分

之前提到过，TTF字形只会包含多个轮廓，并不感知当前字形具体的笔画细分。下图释义了当前轮廓点将和后面哪一个轮廓点连接成一条路径

因此，这里我们希望在笔画交界处让路径横穿过去，于是需要其他的方法来将我们需要的汉字笔画拆解出来。将笔画拆解出来的关键是要识别笔画公共交界处。

提取 corner 点位

深度学习拿到corners之间的匹配度

const getFeatures = (ins: EndPoint, out: EndPoint) => {
  const diff = out.subtract(ins);
  const trivial = diff.equal(new Point([0, 0]));
  const angle = Math.atan2(diff[1], diff[0]); // 两点之间斜率的弧度
  const distance = Math.sqrt(out.distance2(ins)); // 两点之间的距离
  return [
    subtractAngle(angle, ins.angles[0]),
    subtractAngle(out.angles[1], angle),
    subtractAngle(ins.angles[1], angle),
    subtractAngle(angle, out.angles[0]),
    subtractAngle(ins.angles[1], ins.angles[0]),
    subtractAngle(out.angles[1], out.angles[0]),
    trivial ? 1 : 0,
    distance / MAX_BRIDGE_DISTANCE,
  ];
};
const input = new convnetjs.Vol(1, 1, 8 /* feature vector dimensions */ );
const net = new convnetjs.Net();
net.fromJSON(NEURAL_NET_TRAINED_FOR_STROKE_EXTRACTION);
const weight = 0.8;
const trainedClassifier = (features: number[]) => {
  input.w = features;
  const softmax = net.forward(input).w;
  return softmax[1] - softmax[0];
};

笔画拆分算法

现在我们通过生成bridge，能够识别出了笔画的公共交界处了，下一步就需要借助bridge来对笔画进行拆分。【下面通过代码片段，以及对应的动画进行解释】

...
const visited = [];
while (true) {
    /**
 * 直接将目前的路径片段添加到result中
 */
    result.push(paths[current[0]][current[1]]);
    /** 记录当前这一笔visited过的点，到一个局部变量中 */
    visited[get2LenArrKey(current)] = true;
    /** 去到下一个片段路径的起始点 */
    current = advance(current);
    const key = get2LenArrKey(current);
    /** 判断是否是bridge */
    if (bridgeAdjacency.hasOwnProperty(key)) {
      endpoint = endpointMap[key];
      /**
       * 如果当前点位是多个bridge的公共点，
       * 则按照“bridge的切线，直线的切线的斜率等于自己的斜率”与“当前路径前进的切线方向”角度差大小 从小到达排列，
       * 优先选择与当前路径方向切线角度差最小的
       */
      const options = bridgeAdjacency[key].sort(
        (a, b) => angle(endpoint!.pos, a) - angle(endpoint!.pos, b),
      );
      const next = options[0];
      ...
      result.push({
        start: current,
        end: next,
        control: undefined,
      })
      /**
        * 这里要注意一个点，current被加入到了路径中，但是没有被打上visited标签就直接到下一个点了，
        * 目的是拆解下一笔的时候，这个bridge点就是下一笔的起始点
        */
      current = next;
    }
    const newKey = get2LenArrKey(current);
    if (comp2LenArr(current, start)) {
      /** 当走回到start的点的时候，这一笔就结束了 */
      let numSegmentsOnPath = 0;
      /** 局部visited 同步到 全局的vistied中 */
      for (const index in visited) {
        extractedIndices[index] = true;
        numSegmentsOnPath += 1;
      }
      /** 只有一个点的时候，不形成笔画 */
      if (numSegmentsOnPath === 1) {
        return undefined;
      }
      return result;
    } else if (extractedIndices[newKey] || visited[newKey]) {
      /** 访问过的点直接跳过，在这里判断是不允许以被访问过的点开启一下次局部循环判断 */
      return undefined;
    }
  }
...

原始轮廓指令有一个默认的顺序【严格有序，ttf保证】，所以对于不是bridge的点，很容易知道当前点的下一个点是哪一个

  1. 蓝色点代表被标记为visited的点【首次碰到bridge的一个端点的时候，直接将此点加入路径，并跳过visited标记，然后走到下一个点】
  2. 当遇到的corner点处有多个bridge的时候，选择bridge的斜率角度应该与当前笔画路径前进方向的切线斜率角度差最小
  3. 红色的bridge可以让笔画直接穿过笔画交界处，并以**线段（Line）**将bridge的两点相连

笔画修复

通过bridge将笔画拆分以后，可以得到下图的展示，看似完美的背后其实还是有一点儿小瑕疵的：那是因为在bridge连接的地方都是通过直线连接，会导致笔锋的位置看上去好像被刀削过一样

  1. L1与以P1为终点的上一条路径片段相切于P1点
  2. L2与以P2为起点的下一条路径片段相切于P2点
  3. L1与L2交于CP点
  4. MP1为P1与CP间的中点；MP2为P2与CP间的中点。这两点将作为贝塞尔曲线的控制点
  5. 画三次贝塞尔曲线，即字形图中黑色的曲线

笔顺动画

拆分完笔画以后，此时便到了确定笔顺动画的时候

获取笔画中位线骨干

export function getPolygonApproximation(
  path: SVGPathType[],
  approximationError = 64,
): PolygonType {
  const result: Point[] = [];
  for (const segment of path) {
    const control = segment.control || segment.start.midpoint(segment.end);
    const distance = Math.sqrt(segment.start.distance2(segment.end));
    const numPoints = Math.floor(distance / approximationError);
    for (let i = 0; i < numPoints; i++) {
      const t = (i + 1) / (numPoints + 1)
      const s = 1 - t;
      result.push(
        new Point([
          s * s * segment.start[0] +
            2 * s * t * control[0] +
            t * t * segment.end[0],
          s * s * segment.start[1] +
            2 * s * t * control[1] +
            t * t * segment.end[1],
        ]),
      );
    }
    result.push(segment.end);
  }
  return result;
}

  1. 蓝色点为笔画轮廓上的轮廓点（也相当于泰森多边形的采样点）
  2. 泰森多边形中每一个多边形内的点到对应的采样点的距离是最短的；也就是说多个多边形的交界点是距离这些多边形中采样点的距离都最短的一个点（也就是图中黑色的点）
  3. 留下所有笔画内的黑色点，连接黑色点便可以形成控制该笔画方向的中位线

4 . 控制中位线中关键点的数量（保证中位线长度最长，但是点位尽量最少），最终形成下图

笔顺动画排序

当拿到所有笔画对应的方向中位线以后，还需要确定笔顺的先后顺序

编码字符意义例字序列U+2FF0⿰两个部件由左至右组成相⿰ 木目U+2FF1⿱两个部件由上至下组成杏⿱ 木口U+2FF2⿲三个部件由左至右组成衍⿲ 彳氵亍U+2FF3⿳三个部件由上至下组成京⿳ 亠口小U+2FF4⿴两个部件由外而内组成回⿴ 囗口U+2FF5⿵三面包围，下方开口凰⿵ 几皇U+2FF6⿶三面包围，上方开口凶⿶ 凵㐅U+2FF7⿷三面包围，右方开口匠⿷ 匚斤U+2FF8⿸两面包围，两个部件由左上至右下组成病⿸ 疒丙U+2FF9⿹两面包围，两个部件由右上至左下组成戒⿹ 戈廾U+2FFA⿺两面包围，两个部件由左下至右上组成超⿺ 走召U+2FFB⿻两个部件重叠巫⿻ 工从

编码 字符 意义 例字 序列
U+2FF0 ⿰ 两个部件由左至右组成 相 ⿰ 木目
U+2FF1 ⿱ 两个部件由上至下组成 杏 ⿱ 木口
U+2FF2 ⿲ 三个部件由左至右组成 衍 ⿲ 彳氵亍
U+2FF3 ⿳ 三个部件由上至下组成 京 ⿳ 亠口小
U+2FF4 ⿴ 两个部件由外而内组成 回 ⿴ 囗口
U+2FF5 ⿵ 三面包围，下方开口 凰 ⿵ 几皇
U+2FF6 ⿶ 三面包围，上方开口 凶 ⿶ 凵㐅
U+2FF7 ⿷ 三面包围，右方开口 匠 ⿷ 匚斤
U+2FF8 ⿸ 两面包围，两个部件由左上至右下组成 病 ⿸ 疒丙
U+2FF9 ⿹ 两面包围，两个部件由右上至左下组成 戒 ⿹ 戈廾
U+2FFA ⿺ 两面包围，两个部件由左下至右上组成 超 ⿺ 走召
U+2FFB ⿻ 两个部件重叠 巫 ⿻ 工从

1 . 将所有子结构的medians添加到一个集合（按照结构的拆解顺序加入）， 方便和当前字形生成的medians做对比

2 .对比子字形结构和当前字形结构的medians，并对应打上匹配分数， 转换成带权重的二分图匹配问题

  const scoreMedians = (median1: number[][], median2: number[][]) => {
  assert(median1.length === median2.length);
  /** 这里要记两个分值，因为对比的两个median可能刚好只是顺序反了，最后取距离差最小的那个 */
  let option1 = 0;
  let option2 = 0;
  range(median1.length).forEach((i) => {
    option1 -= dist2(median1[i], median2[i]);
    option2 -= dist2(median1[i], median2[median2.length - i - 1]);
  });
  return Math.max(option1, option2);
};

3 . 利用匈牙利算法，找出最大权重匹配关系，拿到该字形相对子字形结构的笔画顺序排列。

五、总结

  1. 通过上述算法过后，可以将笔顺数据生成为 json 格式的文件并存储在 CDN 上，文件的平均大小在 4 kB 左右。
  2. 笔顺动画数据的生产过程中，用了比较多的推测对比算法，能满足很多字形的 case；但是依然不能百分之百保证数据的准确性（字形复杂的时候，算法很容易误判）。所以，在新字体的数据生成过程中，依然需要人工干预的方式去保证数据的准确性。
  3. 目前笔顺后台也是提供了半自动半人工的方式去生产给定字体以及给定字形情况下的笔顺数据。为了降低人工成本，需要探索纠错算法；这样在做批量生成的时候，可以有针对性的进行错误定位。

Copyright© 2013-2020

All Rights Reserved 京ICP备2023019179号-8