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

啦啦涛

Give Me the Font, Back to You the Animation一、简介笔顺后台的目标是只要对于给定的字体文件（WOFF, OTF, TTF ）以及需要的字形（汉字，字母 or 其他各国的语言），就能产出与之对应的笔顺动画数据。是对开源项目Make me han zi[1]的实践。二、效果演示展示效果大力硬件端展示效果后台数据资源后台产出笔顺动画的 json 文件，并通过 CDN 资源分发。确定字体的情况下，一个字形对应唯一一个数据资源（字形通过encodeURI，并去除"%"进行编码，即"我" -> "E68891"）。业务方可以通过拼接 URL 直接获取到对应的笔顺静态资源。亮点功能一|笔画的拆解防止算法生成的笔画数量有误，提供人工干预能力左边图同一颜色代表同一笔可以通过增减右边的红色连线，来做到将字形结构进行笔画的拆解或者是合并亮点功能二|笔顺方向调节防止算法生成的笔画顺序有误，提供人工干预能力可以灵活调节笔顺的先后顺序，或者是描红的方向亮点功能三|缩放&平移功能当字形渲染出来位置或者大小不符合要求的时候，提供人工修改能力字形的大小以及在田字格的位置，在数据生成的时候，已经进行过统一调整拖动右上角红点进行大小缩放拖动字形进行位置平移三、动画实现介绍这里主要是解释如何去使用笔顺后台生产的数据/**笔顺动画原数据*/{"strokes":["M350571Q380593449614Q465615468623Q471633458643Q439656396668Q381674370672Q363668363657Q364621200527Q196518201516Q213516290546Q303550316556L350571Z","M584466Q666485734497Q746496754511Q755524729533Q693554622527Q598520575511L537499Q518495500488Q442472386457L337446Q327446179416Q148409173392Q212365241376Q287389339404L387416Q460438545457L584466Z","M386457Q387493398517Q405535390548Q371564350571C323583303583316556Q315556316555Q338519337478Q337462337446L339404Q340343339289L338241Q337180334133Q333115323109Q317105250119Q238122239114Q240108249100Q309423286Q341-103573Q39036390126Q387169387265L387306Q387355387416L386457Z","M339289Q254261161229Q139222101221Q8622085207Q8419294184Q119166157147Q169144182154Q239199338241L387265Q477314484318Q499327498337Q492343479340Q434324387306L339289Z","M635195Q69075797-14Q876-62898-47Q920-379143Q90534899152Q900174894178Q890179884160Q8577583860Q8235678588Q710155670226L644279Q599381584466L575511Q547659576752Q586779543805Q509827489825Q470824479795Q503752507707Q517601537499L545457Q573334612245L635195Z","M612245Q558197452138Q442132448128Q455124468126Q523135574160Q608175635195L670226Q706260747317Q762336778354Q788361785374Q781386753410Q734428723428Q708427707411Q701354644279L612245Z","M687669Q718648754623Q770613786615Q798618801632Q802648789678Q780697746708Q665726651715Q647711651697Q655687687669Z"],"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路径*/}{strokes.map((strokePath,idx)=>( ))}设置svg的viewBox为"0 0 1024 1024"；因为，在获取TTF字体字形的指令数据的时候，我们将对数据做统一化的处理，将字体单位长度都转化至 1024 单位长度，保证了输出的动画数据在使用的时候不需要再做适配。在绘制文字路径的时候，注意需要做一个变换transform="scale(1, -1) translate(0, -900)"；因为，这里svg的坐标系方向跟字体字形所在的坐标系是不一样的。先放一个不做transform的效果transform="scale(1, -1)"后，会将g内的元素，沿着 x 轴做一个反转，可以看出要将字形移到田字格的中间，还需要将字形下移*transform="scale(1, -1) translate(0, -900)"*后这里为什么不是移动 1024 单位长度呢？因为，TTF字体规范中有一个baseline的概念；在当前的坐标系里面，红色线为字体的基准线；yMax = 900， yMin=-124。因此，需要将字形往下移动到baseline的位置。 从图中坐标系（原点在baseline与左边界的交点处，y 轴正方向朝上）可以看出，跟svg原本的坐标系（原点在左上角，y 轴正方向朝下）是有差别的，所以一开始需要transform的变换，对齐我们选择的标准字体的坐标系。如何做出动画效果通过strokes能够画出字形的轮廓了，然后怎么加入描红效果呢？这个时候需要用到原数据中的medians字段对应的数据了。medians对应的数据，是中位线的数组，而中位线是中点的数组集合。如下图如何将medians数据转换成动画数据呢？计算每个中位线的长度constlengths=medians.map((x)=>getMedianLength(x)).map(Math.round);计算每一笔中位线的动画duration&delaylettotalDuration=0;for(leti=0;i stroke-dashoffset，stroke-dasharray&keyframe动画效果；像是拿了一把大刷子，按照方向一把刷过去。优化动画效果，只需要字形对应的轮廓效果，利用clip-path只保留字形轮廓内的动画效果四、数据生产原理字形点位信息获取TTF 字体文件规范官方-字体配置规定[4]TTF字体生产主要流程（从设计稿原件到数字化字形，再到字体文件中数字化轮廓）每个字体都会规定一个EM基准字体框（虚拟的），这个em框一般为长宽相等的正方形；其中Asecent和Descent分别代表字形相对 baseline 的一个距离同时这里会有一个FUnit，如：512，1024，2048，来描述em框的相对大小。两个 em 方块的网格：左侧每em包含 8 个单位，右侧每em包含 16 个单位。当这个单位数字越大的时候，对应的字体分辨率就越高，越不容易失真TTF的字形由一个或者多个轮廓（contour）组成，例如：对于“我”字，这里有两个contours：绿色部分+蓝色部分将所有的点位，在FUnit坐标系里面进行定位。最终，转换成在对应坐标系下的一系列绘制指令利用开源工具opentype.js[5]解析 TTF 字体文件拿到需求字体的坐标系信息（ascender: 最顶部距离baseline的距离；descender: 最底部距离 baseline 的距离，一般为负数；unitsPerEm:FUnit的单位格子数，也可以认为是TTF字体所在的坐标系大小）获取所有轮廓的点位信息以及点位之间的相连关系 (TTF 连接点位常见命令：MLQZ)统一转换成我们的标准坐标系（1024 * 1024，baseline 到上下距离分别为 900, 124）笔画拆分之前提到过，TTF字形只会包含多个轮廓，并不感知当前字形具体的笔画细分。下图释义了当前轮廓点将和后面哪一个轮廓点连接成一条路径因此，这里我们希望在笔画交界处让路径横穿过去，于是需要其他的方法来将我们需要的汉字笔画拆解出来。将笔画拆解出来的关键是要识别笔画公共交界处。提取 corner 点位通过比较当前点位在前后路径中分别作为终点和起点时候，穿过它的切线角度差（如图中的r1），如果这个角度差大于18°，则将此点判断为拐点（corner），代表字形轮廓在此处有比较大的幅度转折，有一定可能是多笔的交界点。深度学习拿到corners之间的匹配度那么如何判断这个corner点是不是多笔的交界点呢？这个时候需要比较所有corner点，寻找他们之间是否有关联关系。要拿到corners中 点与点的关系，需要借助神经网络（模型下载地址[6]）convnetjs[7]进行深度学习，获取corners之间的匹配度得到corners点与点之间的特征信息constgetFeatures=(ins:EndPoint,out:EndPoint)=>{constdiff=out.subtract(ins);consttrivial=diff.equal(newPoint([0,0]));constangle=Math.atan2(diff[1],diff[0]);//两点之间斜率的弧度constdistance=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]),trivial1:0,distance/MAX_BRIDGE_DISTANCE,];};通过模型训练corners之间的特征信息，得到对应的匹配分数constinput=newconvnetjs.Vol(1,1,8/*featurevectordimensions*/);constnet=newconvnetjs.Net();net.fromJSON(NEURAL_NET_TRAINED_FOR_STROKE_EXTRACTION);constweight=0.8;consttrainedClassifier=(features:number[])=>{input.w=features;constsoftmax=net.forward(input).w;returnsoftmax[1]-softmax[0];};通过上述，最后得到一个带权重的二分图[8]利用匈牙利算法[9]，得到一个最大权重匹配图。当corner点最大匹配的对象不是本身的时候，就将它们连接起来形成一个bridge（两个corner点相连形成的一个线段），当然也要注意去重不要重复连接bridge笔画拆分算法现在我们通过生成bridge，能够识别出了笔画的公共交界处了，下一步就需要借助bridge来对笔画进行拆分。【下面通过代码片段，以及对应的动画进行解释】...constvisited=[];while(true){/***直接将目前的路径片段添加到result中*/result.push(paths[current[0]][current[1]]);/**记录当前这一笔visited过的点，到一个局部变量中*/visited[get2LenArrKey(current)]=true;/**去到下一个片段路径的起始点*/current=advance(current);constkey=get2LenArrKey(current);/**判断是否是bridge*/if(bridgeAdjacency.hasOwnProperty(key)){endpoint=endpointMap[key];/***如果当前点位是多个bridge的公共点，*则按照“bridge的切线，直线的切线的斜率等于自己的斜率”与“当前路径前进的切线方向”角度差大小从小到达排列，*优先选择与当前路径方向切线角度差最小的*/constoptions=bridgeAdjacency[key].sort((a,b)=>angle(endpoint!.pos,a)-angle(endpoint!.pos,b),);constnext=options[0];...result.push({start:current,end:next,control:undefined,})/***这里要注意一个点，current被加入到了路径中，但是没有被打上visited标签就直接到下一个点了，*目的是拆解下一笔的时候，这个bridge点就是下一笔的起始点*/current=next;}constnewKey=get2LenArrKey(current);if(comp2LenArr(current,start)){/**当走回到start的点的时候，这一笔就结束了*/letnumSegmentsOnPath=0;/**局部visited同步到全局的vistied中*/for(constindexinvisited){extractedIndices[index]=true;numSegmentsOnPath+=1;}/**只有一个点的时候，不形成笔画*/if(numSegmentsOnPath===1){returnundefined;}returnresult;}elseif(extractedIndices[newKey]||visited[newKey]){/**访问过的点直接跳过，在这里判断是不允许以被访问过的点开启一下次局部循环判断*/returnundefined;}}...对算法的解释动画原始轮廓指令有一个默认的顺序【严格有序，ttf保证】，所以对于不是bridge的点，很容易知道当前点的下一个点是哪一个蓝色点代表被标记为visited的点【首次碰到bridge的一个端点的时候，直接将此点加入路径，并跳过visited标记，然后走到下一个点】当遇到的corner点处有多个bridge的时候，选择bridge的斜率角度应该与当前笔画路径前进方向的切线斜率角度差最小红色的bridge可以让笔画直接穿过笔画交界处，并以**线段（Line）**将bridge的两点相连笔画修复通过bridge将笔画拆分以后，可以得到下图的展示，看似完美的背后其实还是有一点儿小瑕疵的：那是因为在bridge连接的地方都是通过直线连接，会导致笔锋的位置看上去好像被刀削过一样将所有直线，换用三次贝塞尔曲线替代L1与以P1为终点的上一条路径片段相切于P1点L2与以P2为起点的下一条路径片段相切于P2点L1与L2交于CP点MP1为P1与CP间的中点；MP2为P2与CP间的中点。这两点将作为贝塞尔曲线的控制点画三次贝塞尔曲线，即字形图中黑色的曲线修复后的效果笔顺动画拆分完笔画以后，此时便到了确定笔顺动画的时候获取笔画中位线骨干增加每一笔笔画上的采样点（运用二次贝赛尔曲线公式，拿到更多笔画上的关键点）exportfunctiongetPolygonApproximation(path:SVGPathType[],approximationError=64,)olygonType{constresultoint[]=[];for(constsegmentofpath){constcontrol=segment.control||segment.start.midpoint(segment.end);constdistance=Math.sqrt(segment.start.distance2(segment.end));constnumPoints=Math.floor(distance/approximationError);for(leti=0;i{assert(median1.length===median2.length);/**这里要记两个分值，因为对比的两个median可能刚好只是顺序反了，最后取距离差最小的那个*/letoption1=0;letoption2=0;range(median1.length).forEach((i)=>{option1-=dist2(median1[i],median2[i]);option2-=dist2(median1[i],median2[median2.length-i-1]);});returnMath.max(option1,option2);};利用匈牙利算法，找出最大权重匹配关系，拿到该字形相对子字形结构的笔画顺序排列。五、总结通过上述算法过后，可以将笔顺数据生成为 json 格式的文件并存储在 CDN 上，文件的平均大小在 4 kB 左右。笔顺动画数据的生产过程中，用了比较多的推测对比算法，能满足很多字形的 case；但是依然不能百分之百保证数据的准确性（字形复杂的时候，算法很容易误判）。所以，在新字体的数据生成过程中，依然需要人工干预的方式去保证数据的准确性。目前笔顺后台也是提供了半自动半人工的方式去生产给定字体以及给定字形情况下的笔顺数据。为了降低人工成本，需要探索纠错算法；这样在做批量生成的时候，可以有针对性的进行错误定位。团队招聘我们团队隶属于字节跳动大力智能部门，一方面从事大力智能作业灯/大力辅导APP以及相关海内外教育产品的前端研发工作，业务场景包含 H5，Flutter，小程序以及各种 Hybrid 场景；另外我们团队在 monorepo，微前端，serverless 等各种前沿前端技术也有一定实践与沉淀。常用的技术栈包括但是不限于 React、TS、Nodejs。扫描下方二维码获取内推码：参考资料[1]Make me han zi: https://github.com/skishore/makemeahanzi[2]stroke-dashoffset, stroke-dasharray 解析: https://www.cnblogs.com/daisygogogo/p/11044353.html[3]MDN clip-path 解析: https://developer.mozilla.org/zh-CN/docs/Web/CSS/clip-path[4]官方-字体配置规定: https://docs.microsoft.com/zh-cn/typography/opentype/spec/otff#required-tables[5]opentype.js: https://github.com/opentypejs/opentype.js[6]模型下载地址: https://p3.daliapp.net/obj/character-stroke/net.json[7]convnetjs: https://www.npmjs.com/package/convnetjs-ts[8]二分图: https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E5%9B%BE/9089095fr=aladdin[9]匈牙利算法: https://zhuanlan.zhihu.com/p/96229700[10]voronoijs 泰森多边形 npm 库: https://www.npmjs.com/package/voronoijsactiveTab=readme[11]泰森多边形: https://zh.wikipedia.org/wiki/%E6%B2%83%E7%BD%97%E8%AF%BA%E4%BC%8A%E5%9B%BE[12]表意文字描述字符: https://zh.wikipedia.org/wiki/%E8%A1%A8%E6%84%8F%E6%96%87%E5%AD%97%E6%8F%8F%E8%BF%B0%E5%AD%97%E7%AC%A6[13]汉字结构表: http://p3.daliapp.net/obj/character-stroke/characterdecomposition.csv