点击蓝字 关注我们
✦
✦
板书,是课堂内容的精华提炼,亦是帮助学生理解的重要工具,好比课堂上的明珠。能否成为一堂好课,教师绘制板书的质量与效率自然是一项关键性的因素。
随着在线教育课堂的高速发展,相关的电子板书工具也在不断演进。板书工具从传统的 黑板+粉笔 组合,变身为 移动设备的屏幕 + 手写笔 组合。而在线课堂打破了地理上的限制,教师在课堂上的一笔一划轻松地走进了千家万户之中,传到了全国各地的学生面前。
学而思网校课堂的涂鸦画板工具,亦应运而生。经历多版的迭代,目前已成为网校初高中教学课堂中的一项高频使用工具。研发出准确、高效的板书工具,提高一线教师的教学体验成为网校技术团队在开发画板功能的核心目标。
有别于传统板书工具,电子板书具有轻松、快速进行大批量的绘制和编辑的能力,能直接提高教师授课的体验以及整体的课堂质量。而套索工具,便是实现上述快速批量编辑功能的关键,亦是网校涂鸦画板众多工具之中的核心。
套索工具能够帮助教师快速地批量编辑绘制和书写的内容,教师可以一次性选中多个图形,进行批量的移动,旋转,缩放,复制,修改样式等操作。
学而思网校的板书工具,采用“一端绘制,多端同步”的模式。教师在 iPad 教师端绘制的内容,能够实时同步到不同设备的学生端上,其中包括了 IOS、Android、PC、Web 浏览器。
(iPad教师端 )
(优网Web学生端)
Web应用平台无关,具有快速启动、快速迭代的特点和丰富的社区资源,且随着浏览器版本的不断迭代、API的不断丰富以及前端的语言工具不断更新之下,Web 端和各原生客户端上的能力差距也越来越小,在浏览器上亦能实现媲美原生客户端的复杂功能。
本文对套索变换功能在Web浏览器端实现的原理进行了基本的讲解、对套索状态的保持和存储提出了方案,以及对该绘制和存储方案的优化作出了探索。希望耐心的读者您能大致了解Web端套索功能实现背后的思路,及能给在开发类似图形工具的开发者一些帮助。
在开始介绍变换原理之前,这里先对HTML Canvas元素的相关概念和下文中频繁使用的API作简单介绍:
CanvasRenderingContext2D
HTML Canvas 元素的绘制上下文,它为 canvas
元素构建出一层用于承载 2D内容的绘制表面。所有绘制的图形均由它承载,同时它向我们暴露了用于绘图、变换等操作的功能性 API。为书写方便,下文均使用 ctx
代指CanvasRenderingContext2D
的实例。
ctx.translate(x,y)
移动 canvas
原点,横向 x 像素,纵向 y 像素。
ctx.rotate(radius)
以 canvas
原点为中心,旋转一定角度(弧度单位)。
ctx.scale(sx,sy)
¨C48C 以 ¨C8C 原点为中心,分别以 ¨C9C 的缩放比拉伸 ¨C10C 方向。
我们的最终目标是把图形和笔迹按以下的方式旋转,因此,旋转缩放图形时,我们所有操作的中心须为套索的中心点。
但在 HTML Canvas 的变换 API 中,所有的操作都是基于画布的原点进行操作。因此如果无外加处理,图形将以画布的原点为中心旋转缩放。尽管角度和缩放比正确,但位置会产生错误的偏移,下图应该很清楚地表明,这并不是我们想要的结果。因此,有多个角度和缩放比时,不能把旋转角度和缩放比进行直接的应用。
既然 canvas
的变换是以画布原点为中心,那么,如果我们先移动画布的中心,使画布中心和套索中心重合,再进行旋转缩放的操作,那么旋转画布的中心点就一定是我们想要的套索中心了!
但是问题又出现了,旋转完成后,我们还能以图形的原坐标进行画图吗?很明显是不能的。
原因是偏移完套索中心之后,所有的绘制坐标都被加上了偏移量。因此在使用原来的坐标进行绘制之前,应该减去原来的我们预先施加的偏移量进行修正。而这里采取的操作是对套索原点施加反向的偏移量,以抵消我们第一步增加的额外偏移。
如此看来,我们想要的功能——以套索为中心的旋转缩放,就已经达到了。
若套索还涉及到套索的平移,只需在旋转和缩放前再平移画布原点即可。
既然单次的套索操作由 5个
基本操作构成,那么两次套索的叠加呢?聪明的您一定想到了,就是 5 X 2 = 10
次操作了。
换言之,假如一个图形被变换了 N 次,
那么我们可以用一个 N 项的数组来记录:
因此,我们就可以用一个数组来表示一个图形的变换状态了。
变换的保持和记录
Canvas 绘制是被动的,图形一旦被画到了 canvas
之上,就再也不能访问和操作了。
形象地说,图形画到了Canvas之中,仿佛墨水画到纸上,再也不能把它“拎起”再重新“放下”了。那么,如果我们想要对“画纸”上的墨点进行变换,就要重新拿一张白纸,再画一次。
在 Canvas 上的操作也是一样的,每次的变换操作之前,都必须把画面上的所有图形全部清空,再重新画上变化后的图形。在清屏过后,没被套索选中的图形,应该能保持清除前的状态;被套索选中的图形,应该在清除前记录的基础上新添加变换。
因此,核心的问题就显现出来了——如何在清屏之后恢复清屏前的状态呢?
为解决这个问题,我们需要对套索的变换记录进行保存。
正如上一节所分析,对于一个图形的变换状态即为一个存有变换记录的数组。那么,我们可以维护对应图形的状态记录表,来帮助我们恢复变换状态。如下图所示:
在清屏后,我们只要对在每个图形进行绘制之前,按顺序遍历和应用其状态数组即可。
那么新加的套索如何处理呢?也是十分简单,只需把新添的记录向数组拼接即可。
而为了展示图形的绘制过程,套索操作并不是一次到位,而是以断点形式分成许多次发送。例如一次90度的图形旋转,其会分解为若干次小角度的旋转, 分开多次发送。而当我们接收到分次发送、具有相同id的套索信息时,只需把对应的记录从数组中移出,替换成最新的记录,就能完成图形变换的更新。
提到撤销与重做,您脑内可能会瞬时想到两个组合键:ctrl + Z
和 ctrl + shift + z
。在图形的变换操作不理想时,用户亦希望能”一键撤销“。因此我们套索亦需要支持此项功能。
在套索中,要想实现这个功能,核心的问题有两个:
如何对前后套索记录进行保存?
如何回退到特定的步数前,并应用当时的变换状态?
实现记录的管理往往使用传统的栈结构,通过出入栈来维护最新状态。在套索的场景中,最终使用的是类似双向链表的数据结构来维护套索记录。使用链表,能使我们在找回上一个变换记录时,能直接取出和一次性替换当前生效的记录,而无需经历额外的遍历过程。
撤销和重做时,只要根据 previous
和 next
指引向前或后移动指针,把对应的记录直接套用上去即可。
优化前后的性能比较
在说明主要的原理前,我们先看一看经过优化后的套索性能吧。
为此,我们特地对优化前后的绘制性能做了对比实验:
实验1:
在画板上绘制了 50条
长涂鸦,在预先应用了 15次
套索的基础上进行测试。
选中所有长涂鸦,套索旋转 90度
,统计从收到 IRC 信令到重绘完成的时间:
实验结论:单次更新绘制平均耗时降低 64.65%
实验2:
在画板上绘制了 25条
长涂鸦,在预先应用了 20次
套索的基础上进行测试。
选中所有长涂鸦,套索旋转 180度
,统计从收到 IRC 信令到重绘完成的时间:
实验结论:单次更新绘制平均耗时降低 90.18%
可见,优化方案的成果是十分惊人的。那么接下来我们将逐步介绍复杂度分析,以及背后的实现原理。
首先是时间复杂度,设当前画布上有 n个
图形,平均每图形中已操作 t次
。
那么每次对画布的刷新,在清屏重绘之时,对画布的操作次数是:
而空间复杂度,设总的套索操作次数为 m
,画布上的图形数为 n
,每个图形被已操作 t次
。
那么存储记录整体的时间复杂度为:
而 JavaScript 的对象为引用类型,相同的对象不会反覆地被创建,而是一同引向堆内存中的同一对象。把这个因素考虑进来,实际的空间复杂度应为:
若能把某个图形的所有历史变换进行预先的计算, 把所有的记录压缩成一个,在操作前知道这系列操作的最终结果,那无论其以前操作了多少次,对画布的操作都只需要一次,去除了对数组的遍历操作,那我们的时间复杂度就能大大缩减。这就是整个优化的中心思想。
简单地来说,就是把多次的套索记录,合成一个大套索,对整个存储记录进行降维。这个大套索,代表了最终变换状态。因此我们只要应用和记住这一个套索,就能使图形变换到正确的位置。
结合以下的动画,希望您能更好的理解:
在进入套索的具体应用之前,我们先来了解一下变换矩阵的相关概念。
无论是 2D 图形还是 3D 图形,它们的变换都可以分为三大类:
平移 Translation
旋转 Rotation
缩放 Scale
它们相对于原点,对某个图形的改变,这个过程可被叫作基本变换,而这三种基本变换均可以由以下三种 3x3
的矩阵表示,它们也被叫作变换矩阵(`Transformation Matrix):
您可能会有疑问,明明用简单的数字就可以了,为何要使用一个如此复杂的矩阵来表示呢?
假如我们想对某个(2D)图形的某个特征点进行一系列的变换,可把一某点以行向量表示,再以矩阵的相乘操作代替之。
可见,使用矩阵,只是改变了一种表达和计算的方式,它对最终数据点的计算结果是没有影响的。矩阵承担处理点坐标的中间件角色,原始点坐标为输入值,变换后的坐标为输出值。
但利用矩阵的运算,后续能更方便地进行操作合并。当我们应用依顺序应用多个变换时,只要把对应的矩阵相乘,就能把相应的图形得以变换。
回到我们套索的场景中,再简单回顾下,一次完整套索可以解为以下基本操作:
移动原点至套索中心
应用该套索的变换
回退套索中心的偏移距离
而它们都由最基本的变换组成,因此可把它们使用矩阵表示:
其中, Lx
为套索的中心点,Tx Ty
为套索的平移量 , s
为缩放比, θ
为转角。
把这五个矩阵进行乘法运算,可把它们进行合成一个矩阵:
套索的五次操作均聚合到了一个矩阵上,那么,我们就只要记住这一个矩阵,就可以还原对应的套索操作了。
此时您可能又有一个疑问了,就算得出了这个矩阵,和我们的 Canvas 操作有什么关系呢?
如果我们把这个最终的矩阵进行分解,它可以分解为以下三个矩阵:
canvas
上进行操作了。到这里,您可能觉得这比较抽象难懂,因
此接下来我们以一个实际数据作为例:
我们能把变换操作的代码,对应成变换矩阵。
它们的聚合再分解,就能把套索中心的变换整合到平移之中。
套索矩阵之间的聚合
我们之所以要把套索的数据使用矩阵来表示,只是为了方便计算得出多个套索的最终展示结果。
既然单个套索均可由五个矩阵相乘的结果表示,那如果我们有两个套索先后作用,不就相当于有五个矩阵先作用,另外五个矩阵后作用了吗?
那么这十个矩阵按照一定的次序相乘,“合十为一”,这两次结果就都合成在了这一个矩阵上了!
下面是聚合操作的计算示意:
事实上,无论一个图形被不同的套索操作多少次,有多少次变换,经过上述的运算,都可以整合成三次基本操作。由此,我们就达到了聚合套索记录的目的。
由此,我们在新添套索记录之时,只需对之前的变换记录进行一次增量运算,即可得出最新的变换状态。
而在最后的记录之时,无需再保存对每个图形保存整个变换数组,记录下压缩后的rotation
,scale
,Tx,Ty
便可一步完成套索的复现。
HTML Canvas 的绘制是被动的,任何图形一旦被绘制上去就没有任何修改的方法。因此想要实现变换,只能完全清除 Canvas 内容,改变图形的原始数据或做出一定变换后,再把所有图形进行重绘;
一次套索的变换由以下基本操作组成:
偏移画布到套索中心
应用套索平移
应用套索旋转和缩放
回退套索初始偏移量
所有的变换操作均可由3x3基本变换矩阵表示,连续的变换操作可等价于一系列的基本变换矩阵相乘。矩阵相乘的结果亦是3x3的变换矩阵,能集中表示一系列操作的最终结果。
往期 · 推荐
致力于互联网教育技术的
创新和推广
微信公众号 @学而思网校技术团队