本作品为七牛云2022年1024创作节校园黑客马拉松参赛作品

需求分析

基本绘图功能

作为一个在线协作白板,离线的本地化的白板是一切功能的前提。本地白板中需要包含所有白板绘图相关的基本功能。

分页展示

白板需要支持分页显示,每一页都有其独立标题,用户能够切换当前页面,增加新页面,删除非当前页面,需要保证项目至少存在一页

1
2
3
4
5
6
7
8
9
10
11
12
@startuml
left to right direction

usecase 使用分页 as usePage
User --> usePage
usecase 切换当前页面 as switchPage
usecase 增加新页面 as addPage
usecase 删除非当前页 as deletePage
usePage <-- switchPage: <<extends>>
usePage <-- addPage: <<extends>>
usePage <-- deletePage: <<extends>>
@enduml

创建图元

用户可以在白板上创建各式各样的图形元素,至少需要包含直线、矩形、椭圆、文本框、自由路径的绘制等等。

1
2
3
4
5
6
7
8
9
10
11
12
13
left to right direction
usecase 创建图形元素 as createComponent
User --> createComponent
usecase 创建直线 as createLine
usecase 创建矩形 as createRect
usecase 创建椭圆 as createOval
usecase 创建文本框 as createText
usecase 创建自由路径 as createPath
createComponent <-- createLine: <<extends>>
createComponent <-- createRect: <<extends>>
createComponent <-- createOval: <<extends>>
createComponent <-- createText: <<extends>>
createComponent <-- createPath: <<extends>>

操作历史

用户能够操作历史线,实现回滚重做功能。

1
2
3
4
5
6
7
left to right direction
usecase 操作历史 as controlHistory
User --> controlHistory
usecase 回滚 as undo
usecase 重做 as redo
controlHistory <-- undo: <<extends>>
controlHistory <-- redo: <<extends>>

工程化

白板若要真正具备实用价值,必然需要实现持久化存储,用户能够保存当前白板工程文件,打开载入一个白板工程文件,另存为白板工程文件。

1
2
3
4
5
6
7
8
9
left to right direction
usecase 操作工程文件 as project
User --> project
usecase 保存工程 as save
usecase 另存为工程 as saveAs
usecase 打开工程 as open
project <-- save: <<extends>>
project <-- saveAs: <<extends>>
project <-- open: <<extends>>

操作图元

添加的图形元素的各个属性需要支持再编辑,如选中直线能够修改其线宽、颜色,选中文本框能够修改其对齐方式, 背景,边框等等。

每个添加的图形都需要能够支持移动、缩放、旋转等变换。

每个添加的图形还需要能够支持修改层叠关系和删除图形的操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
left to right direction

usecase 操作图形 as controlCompoonent
User --> controlCompoonent
usecase 编辑图形元素 as editComponent
controlCompoonent <-- editComponent: <<extends>>
usecase 编辑直线 as editLine
editComponent <-- editLine: <<extends>>
usecase 修改线宽 as modifyLineWidth
usecase 修改颜色 as modifyLineColor
editLine <-- modifyLineWidth: <<extends>>
editLine <-- modifyLineColor: <<extends>>

usecase 编辑文本框 as editText
editComponent <-- editText: <<extends>>
usecase 修改对齐方式 as modifyTextAlign
usecase 修改背景颜色 as modifyBackgroundColor
usecase 修改边框属性 as modiifyBorder
editText <-- modifyTextAlign: <<extends>>
editText <-- modifyBackgroundColor: <<extends>>
editText <-- modiifyBorder: <<extends>>


usecase 变换图形 as transform
controlCompoonent <-- transform: <<extends>>
usecase 移动图形 as move
usecase 缩放图形 as scale
usecase 旋转图形 as rotate
transform <-- move: <<extends>>
transform <-- scale: <<extends>>
transform <-- rotate: <<extends>>

usecase 修改层叠关系 as modifyStack
controlCompoonent <-- modifyStack: <<extends>>
usecase 置顶 as bringToTop
usecase 置底 as bringToBottom
modifyStack <-- bringToTop: <<extends>>
modifyStack <-- bringToBottom: <<extends>>

usecase 删除图形 as delete
controlCompoonent <-- delete: <<extends>>

扩展绘图功能

富文本展示

支持一定的展示富文本的功能,如支持HTML文档Markdown文档

图片展示

支持插入位图并能够修改其填充方式

支持插入矢量图并能够修改其填充方式覆盖颜色等操作。

插入附件

支持插入附件类型,用户可上传文件并生成外链到白板内并支持再次下载已上传的附件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
left to right direction

usecase 创建导入第三方素材 as importAssets
User --> importAssets
usecase 导入渲染富文本 as showRichText
importAssets <-- showRichText: <<extends>>
usecase 导入渲染HTML文档 as showHtml
usecase 导入渲染Markdown文档 as showMD
showRichText <-- showHtml: <<extends>>
showRichText <-- showMD: <<extends>>

usecase 导入显示位图 as showImage
importAssets <-- showImage: <<extends>>
usecase 导入显示矢量图 as showSvg
importAssets <-- showSvg: <<extends>>
usecase 导入上传附件文件 as uploadFile
importAssets <-- uploadFile: <<extends>>
usecase 下载已上传的附件文件 as downloadFile
importAssets <-- downloadFile: <<extends>>

多人协同功能

创建与加入房间

每个人都可以一键快速创建一个白板,创建者称为该房间的主持人

主持人进入白板后可点击复制当前房间ID并分享给其他人。

其他人输入房间ID即可加入该白板所在的房间,加入房间的人称为该房间的一个成员

协作与只读模式

房间中的白板分为协作模式只读模式

只有主持人可随时修改白板模式。

只读模式

在只读模式下,所有成员均无法编辑且视角和页面必须与房间主持人保持同步跟随

协作模式

在协作模式下,所有成员都具有自己的独立视角独立的页面,均可实现独立编辑

UML用例分析

从多人协同功能中我们可抽取出三种角色actor,分别为主持人,普通成员,用户,其中主持人与普通成员均为用户,用户能够使用所有基本和扩展功能,主持人与普通成员均有自身特有的功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
left to right direction

actor 主持人 as Owner
Owner --|> User
usecase 创建进入白板房间 as createAndEnter
usecase 复制房间id as copyId
usecase 修改白板模式 as modifyMode
Owner --> createAndEnter
Owner --> copyId
Owner --> modifyMode

actor 普通成员 as Member
Member --|> User
usecase 加入白板房间 as enter
usecase 查看同步画板 as look
Member --> enter
Member --> look

最终完整的功能性需求的UML用例图可总结如下:

非功能性需求

跨平台

白板需要实现跨平台,目前用户场景的设备或运行环境主要分为以下环境:

PC桌面端:Windows,MacOS,Linux

移动端:Android,iOS

网页端:Web

考虑到目前本人手头上已有的设备,暂时只优化Windows端Android端的使用体验,其他端如Linux,MacOS,iOS,Web端尽可能实现。跨平台要求除了能够实现基本的运行外,还需分别为PC端键鼠移动端触屏进行单独的适配以实现更好的用户体验,如PC端使用滚轮缩放视图,移动端使用手势缩放视图,PC端需要适配鼠标右键弹出菜单,移动端适配长按弹出菜单

性能需求

尽量降低多人协同场景下的网络延迟,尽量降低软件中潜在的性能问题

这意味着我们需要设计一些较巧妙的算法来避免相对暴力的解决方案。如使用diff算法实现增量同步,优化序列化反序列化开销等手段。

可维护与可扩展性

随着白板的功能演进,白板中的图形元素未来必然会持续丰富,需要支持良好的可扩展性以实现更加方便地扩展白板具备的功能。

考虑到其实我们这个白板系统完全可抽取出独立的白板SDK供第三方软件进行直接接入使用,故需要尽可能的抽象并开放出白板中公共的可定制化的接口,以便于第三方软件可借助白板SDK灵活定制和扩展白板的新功能。

故我们可以实现一套插件系统,扩展新功能时仅新增插件代码添加插件注册点代码而不是需要到处修改代码,良好地符合了开闭原则。

开发方案选择

出于跨平台的考虑,目前较热门的技术分别是Web开发Flutter客户端开发,考虑到团队已掌握技术栈的熟练程度,最终选择了Flutter客户端开发

起初,我们尝试使用Flutter的CustomPaint这个控件基于Canvas进行自绘。也实现了像矩形,文本框,直线等基本图元的绘制。后来我们发现,为了优化用户体验,我们需要在Canvas绘制好的图形上再自己绘制很多ui元素,还需要手动实现将Canvas的全局事件分发各个图元交互事件,这其实已经类似自己写了一个GUI框架了,感觉会相当麻烦,出于时间和精力的考虑,暂时放弃这种自己造轮子的想法。

经过调研发现,原来在Web领域有KonvaFabric.js这样的Canvas绘图框架,完全能够满足绘图需求。可惜Flutter生态里缺乏类似框架(或许以后有功夫可以自己造一个类似框架)。

实际上,Flutter自身就是基于Skia2D绘图引擎通过自绘实现的一套GUI框架,一切控件的底层均归结到基本的skia绘图指令。于是我想,Flutter本身这不就是我们要找的绘图框架吗?假如我们直接依靠Flutter自身的控件系统完成白板系统,那么既省时省力又可以相当灵活地拥抱Flutter生态下的任何ui组件库。

白板组件设计实现

白板容器

为了使用Flutter自身的控件系统实现白板的大体框架,我们首先面临的需求如下:

设计一个布局容器,满足如下需求:

  1. 无限大的,可自由拖动,缩放可见视角

  2. 某个控件位置由一个绝对坐标来定位

  3. 其中的每个孩子需要有一定的尺寸约束,尺寸约束包含了最大尺寸和最小尺寸,用于实现图元的大小控制。

实际上在Flutter中有一个叫做Stack的组件,Flutter中的Stack控件可基于父容器的边缘位置的偏移量实现定位。Flutter中还自带另一个组件InteractiveViewer可实现对某个Widget进行手势缩放与拖动,若将两者进行结合不就能实现我们的预期效果了吗?

完成Stack布局代码如下,可以放置三个尺寸为(100,100)的盒子并且坐标分别为(0,0), (120,100),(50,50)颜色分别为红色,绿色,黄色。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class MyWidget extends StatelessWidget {
@override
Widget build(BuildContext context) {
return Container(
child: Stack(
children: [
Positioned(
left: 0,
top: 0,
child: Container(
width: 100,
height: 100,
color: Colors.red,
),
),
Positioned(
left: 120,
top: 100,
child: Container(
width: 100,
height: 100,
color: Colors.green,
),
),
Positioned(
left: 50,
top: 50,
child: Container(
width: 100,
height: 100,
color: Colors.yellow,
),
),
],
),
);
}
}

此时运行结果如下:

在外层再套一个InteractiveViewer即可实现可自由缩放平移的效果了

1
2
3
4
5
6
7
8
9
10
class MyInteractiveWidget extends StatelessWidget {
@override
Widget build(BuildContext context) {
return Sizedbox.expand(
child: InteractiveViewer(
child: MyWidget(),
);
);
}
}

但是此时我们会发现这里的Viewer的视角其实仅限于其原始的父容器尺寸的可视范围,并无法实现无限大的范围,此时我们再为InteractiveViewer设置一个属性为

1
boundaryMargin: const EdgeInsets.all(double.infinity),

即可实现无限大的平移缩放效果了。

为了方便观察,将调试模式中的控件边框打开,从运行结果我们可以看出,整个Stack的大小其实还是原来的Stack所占据的父容器空间的大小,并没有发生任何改变。

若将红色盒子的left和right分别设为-50, -50,则呈现如下效果:

可以发现红色盒子越界部分将被裁剪。

我们可以设置Stack组件的clipBehavior属性以取消默认的裁剪行为

1
clipBehavior: Clip.none,

看起来现在一切都很完美了,我们拥有了一个看起来是无限大的布局容器,能够进行的自由平移,缩放。

现在让我们为每个矩形尝试添加事件监听器GestureDetector(),修改MyWidget代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class MyWidget extends StatelessWidget {
@override
Widget build(BuildContext context) {
return Stack(
clipBehavior: Clip.none,
children: [
[-50.0, -50.0, 100.0, 100.0, Colors.red, '红色'],
[120.0, 100.0, 100.0, 100.0, Colors.green, '绿色'],
[50.0, 50.0, 100.0, 100.0, Colors.yellow, '黄色'],
].map((e) {
return Positioned(
left: e[0] as double,
top: e[1] as double,
child: GestureDetector(
onPanDown: (d) {
print('${e[5]}被按下: ${d.localPosition}');
},
child: Container(
width: e[2] as double,
height: e[3] as double,
color: e[4] as Color,
),
),
);
}).toList(),
);
}
}

此时我们会发现红色越界部分始终无法响应任何触摸事件,这不符合我们的需求。有关这个问题,我们可以在flutter官方仓库中的issues中找到相关讨论

https://github.com/flutter/flutter/issues/19445

这个问题在Github上有相当激烈的讨论,大概原因就是如果hitTest不对超出边界的点击事件进行预判断并裁剪,那么会相当地耗性能。我们可以通过重构代码的方式来避免这个越界裁剪的问题。

经过研究,我们发现了这个点击裁剪原来是对于所有继承于RenderBox抽象类的一个默认行为。一种较为优雅的解决方案,就是通过继承RenderStack类重写hitTest删除边界裁剪代码,再创建自己的Stack组件继承自Stack组件并重写其中的createRenderObject方法为自己的重写的RenderStack

如下代码即为前后的核心代码的改动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  @override
  bool hitTest(BoxHitTestResult result, {required Offset position}) {
    // 原本的RenderBox的点击判定的源码需要进行box边界裁剪
    // if (_size!.contains(position)) {
    //   if (hitTestChildren(result, position: position) || hitTestSelf(position)) {
    //     result.add(BoxHitTestEntry(this, position));
    //     return true;
    //   }
    // }

    // 修改后的代码
    if (hitTestChildren(result, position: position) || hitTestSelf(position)) {
      result.add(BoxHitTestEntry(this, position));
      return true;
    }
    return false;
  }

项目中有关白板容器组件的实现如下在代码路径:

board_front/lib/component/interactive_infinity_layout at master · SIT-board/board_front (github.com)

该组件完全可分离为一个独立的flutter package供任何第三方项目所使用。

白板存储结构设计

既然我们白板显示的内容完全是基于Flutter自身的控件系统完成开发的,那么白板中的一个个图形元素自然就是一个个Widget。在传统的Flutter App开发中,这些ui控件的状态信息要么是由外部数据传入一个StatelessWidget组件,要么是StatefulWidget组件中自己维护自己的状态变量。

考虑到由于这些白板及白板元素的状态数据需要支持持久化操作,需要支持序列化反序列化操作,需要支持diff操作等等,故我们需要将需要这些操作的状态变量分离出一个独立的Data类单独存放。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class RectModelData {
Offset position;
Size size;
Color color;

RectModelData(this.position, this.size, this.color);

factory RectModelData.createDefault() => RectModelData(
position: Offset(0, 0),
size: Size(100, 100),
color: Colors.blue,
);

factory RectModelData.fromJson(Map<String, dynamic> json) => RectModelData(
position: ((e)=>Offset(e[0], e[1]))(json['offset']),
size: ((e)=>Size(e[0], e[1]))(json['size']),
color: Color(json['color']),
);

Map<String, dynamic> toJson() => <String, dynamic>{
'position': [position.dx, position.dy],
'size': [size.dx, size.dy],
'color': color.value,
};
}

上述代码为典型的json_model序列化反序列化代码,由于flutter不支持运行时反射机制,故必须写出上述这种代码,可以看出这种代码较为繁琐且无趣。

不过事实上我们也是能够使用第三方的代码生成工具去根据json生成上述代码,flutter官方也提供了一种叫做build_runner的代码分析与生成工具,能够实现通过编写第三方插件实现这种代码的生成。

当我们编写diff算法时,我们接收到其他人发来的白板数据更新信息,这种更新信息能够精确到具体的model中的某一个字段,故我们还需要实现修改某个key对应的值这种操作。一个暴力的解决方案就是先整体model序列化本地存储的数据,经过修改某个字段后再整体model反序列化回去。不难发现这种实现方案的时间空间开销很明显具有相当大的优化空间,但是由于flutter不支持反射,故难以实现根据字符串名修改某个字段的值和类型。

那么是否能够自己编写build_runner代码生成工具来通过编译期生成代码实现反射呢?这从理论上感觉应该可行,不过我们想到了另一种解决方案:

其实我们直接将所有状态变量存储在HashMap里不就行了?看起来完全没有必要定义一个单独的数据类再实现序列化和反序列化和根据字符串修改字段等方法,直接使用HashMap,构造Widget时再去读取HashMap里的值不就行了?于是我们的数据类可改造为以下写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
abstract class HashMapData {
Map map;
HashMapData(this.map);
String toJsonString() => jsonEncode(toJson());
}

class RectModelData extends HashMapData{
Offset get position => ((e) => Offset(e[0], e[1]))(map['position'] ??= [0, 0]);

// 上述一行代码等价于下面繁琐的代码
// Offset get position {
// var p = map['position'];
// if(p == null) {
// var p1 = [0, 0];
// map['position'] = p1;
// p = p1;
// }
// return Offset(p[0], p[1]);
//}

set position(Offset v) => map['position'] = [v.dx, v.dy];

Size get size => ((e) => Size(e[0], e[1]))(map['size'] ??= [0, 0]);
set size(Size v) => map['size'] = [v.width, v.height];

Color get color => Color(map['color'] ??= Color.blue.value);
set color(Color v) => map['color'] = v.value;

RectModelData(super.map);

factory RectModelData.createDefault() => RectModelData({});
}

实际上,这就相当于对HashMap进行了一层封装抽象,基于HashMap抽象出该图形元素的数据读写类。这就像c语言结构体的底层存储是原始的二进制内存数据,但是上层的使用经过了结构化抽象

此时我们仍然像之前一样可以使用这个数据类,但是完全不再需要使用build_runner生成序列化反序列化代码,因为底层直接就是一个HashMap,序列化可以直接使用底层的map,反序列化直接构造该数据类即可,当我们需要根据字符串修改某个特定的值时,也能够轻松直接修改底层的map中的数据。

白板数据结构设计

我们采用自底向上的分析方式对数据结构的设计进行分析。首先,我们称一个个的图形元素为模型Model。

CommonModelData

首先根据需求分析,我们的每个图形都能够支持移动,缩放,旋转的变换,能够修改图层层叠关系,故可抽取如下公共属性:

其中constraints属性有四个分量表示了其尺寸缩放的最大与最小尺寸

1
2
3
4
5
6
7
8
9
10
11
12
13
CommonModelData {
// 旋转角
angle: double
// 位置,分别为x,y坐标
position: array<double>[2]
// 大小,分别为width与height
size: array<double>[2]
// 层叠关系,越大越靠前
index: int
// 约束关系,由minWidth,maxWidth,minHeight,minWidth四个分量构成
// 用于确定该模型能够拉伸的最大与最小尺寸
constraints: array<double>[4]
}

SpecialModelData

SpecialModelData类型是一个泛指类型,不同类型的Model具有不同的data类型,其存放了图形元素自身的内部特有的属性。

RectModelData

RectModelData类型为矩形元素的特有数据,根据需求分析,存在文本框这种图形元素,故我们可以直接将文本框和矩形组件合并为一种图形元素。

故我们可抽象出如下的矩形/文本框的数据结构:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
RectModelData {
// 背景颜色
color: Color
// 背景形状 0表示矩形,1表示圆形
backgroundShape: int
// 边框属性
boarder: BorderModelData {
// 边框颜色
color: Color
// 边框的宽度
width: double
// 边框的圆角半径
radius: double
}
// 矩形内部的文本属性
text: TextModelData {
// 文字内容
content: string
// 文字颜色
color: Color
// 文字大小
fontSize: double
// 对齐方式
// 水平对齐有三个方式分别为左对齐,居中对齐,右对齐
// 分别对应数字-1,0,-1
// 垂直对齐有三个方式分别为上对齐,居中对齐,右对齐
// 分别对应数字-1,0,-1
// 水平与垂直对齐对应的数字即为最终alignment的值
alignment: array<int>[2]
// 是否加粗
bold: bool
// 是否斜体
italic: bool
// 是否下划线
underline: bool
}
}

FreeStyleModelData

FreeStyleModelData为自由画板插件的数据类型定义,考虑到需求分析中能够绘制自由曲线,故设计该图形元素为自由绘制的画板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
FreeStyleModelData {
// 路径id列表
pathIdList: array<int>
// 路径字典
pathMap: map<int, FreeStylePathModelData>
// 路径颜色
backgroundColor: Color
// 当前画笔状态属性
paint: Paint
}

Paint {
// 画笔颜色
color: Color
// 画笔宽度
stokeWidth: double
// 抗锯齿
isAntiAlias: bool
}
FreeStylePathModelData {
// 路径id
id: int
// 路径点,分别对应x,y坐标
points: array<array<double>[2]>
// 路径画笔
paint: Paint
}

其他图形元素类型

同样还有其他图形元素的特有的数据结构,具体可参考代码 component/board/plugins 中data.dart的定义与实现。

Model

Model类型定义了某个白板中的模型,其数据类型定义如下:

1
2
3
4
5
6
7
8
9
10
Model {
// 模型id
id: int
// 模型类型
type: string
// 模型数据,由模型类型决定不同数据类型
data: <SpecialModelData>
// 模型公共属性
common: CommonModelData
}

BoardViewModel

BoardViewModel定义了一个白板的视图模型,一个白板可看做由若干个模型的集合及视角数据所构成。

视角数据可由一个4x4矩阵所表示。

为什么是4x4矩阵?

在Flutter中一切ui元素均可定义在三维空间中的某个平面,这样我们便可以方便地对某个ui元素进行更丰富的三维变换了,例如我们可以实现三维空间中绕x,y,z轴的旋转,可以实现x, y, z轴上的平移等变换。

3x3矩阵实际上只能够描述任意三维空间图形的线性变换,如缩放,旋转,错切等。

4x4矩阵实际上可以描述任意三维空间下图形的仿射变换,能够在线性变换的基础上外加实现平移变换。

白板数据结构定义如下:

1
2
3
4
5
6
7
8
BoardViewModel {
// 视口变换矩阵, 为4x4矩阵
viewerTransform: array<double>[16]
// 模型id列表
modelIdList: array<int>
// 模型字典
modelMap: map<int, Model>
}

BoardPageViewModel

根据需求分析中,白板需要支持分页展示,且每一页均有独立标题,那么BoardPageViewModel数据类型定义了某一页的数据,数据定义如下:

1
2
3
4
5
6
7
8
BoardPageViewModel {
// 页面标题
title: string
// 页面id
pageId: int
// 白板数据
board: BoardViewModel
}

BoardPageSetViewModel

根据需求分析中,白板能够实现分页展示,能够切换当前页面,故需要存储当前页面的id,设计数据结构如下:

1
2
3
4
5
6
7
8
BoardPageSetViewModel {
// 页面数
pageIdList: array<int>
// 页面字典,存储了所有页面信息
pageMap: map<string, BoardPageViewModel>
// 当前页面id
currentPageId: int
}

SBP文件

sbp文件为SIT-board的工程文件。实际上sbp文件就是以文本形式存放的最顶层BoardPageSetViewModel对象的json序列化格式。

或许可以重构成二进制方式存放的更加紧凑的文件格式,或者直接使用BSON库。

JsonDiff算法设计实现

Diff算法可通过比较计算得到某个对象在不同状态之间的差异,还可将这种差异应用到前一个状态上来计算得出后一个状态。我们将该差异记做一个补丁patch

Diff算法的基本运算规则如下:

初始状态:State0 = {}

目标状态:State1 = {e1:1, e2:2}

目标到初始的差异:Patch1 = State1 – State0 = {add: {e1:1, e2:2}}

若已知差异补丁:Patch2 = {update: {e1:2}, remove: {e2}}

计算可得目标状态:State2 = State1 + Patch2 = {e1: 2}

以上过程可得出UML状态图如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
@startuml E
[*] --> State0
State0--> State1: add: e1 = 1,e2=2
State1: e1=1 \ne2=2

State1 --> State2: update: e1 = 2 \n remove e2
State2: e1=2

State2 --> State3: remove: e1

State2 <-- State3: add: e1 = 2
State1 <-- State2: update: e1 = 1 \n add: e2 = 2
State0 <-- State1: remove: e1,e2
@enduml

UndoRedo算法设计实现

那么我们是如何基于Diff算法实现UndoRedo的呢?

方案一

当新增数据时,即State0转换到State1后,我们计算出其Patch1,

State0—>State1

State0 = {},State1 = {e1:1, e2:2}

Patch1 = State1 - State0 = {add: {e1:1, e2:2}}

我们将Patch1放入一个栈S1中。

S1: Patch1

再从State1转换到State2,计算出Patch2 = {update: {e1:2}, remove: {e2}}

我们将Patch2放入栈S1中

S1: Patch1 Patch2

再从State2转换到State3,计算出Patch3 = { remove: {e1} }

我们将Patch3放入栈S1中

S1: Patch1 Patch2 Patch3

此时已经存在了三个Patch了。

当我们需要执行Undo撤销操作时,我们需要弹出栈顶的Patch并反向计算Patch的逆,一个Patch的逆实际上为其逆变换。比如Patch1的add的属性将变为remove的属性。然后我们在当前状态上应用Patch的逆实际上就实现了Undo操作

Patch1的逆: -Patch1 = {remove: {e1:1, e2:2}}

Undo操作: State0 = State1 + (-Patch1)

Redo操作: State1 = State0 + Patch1

注意:为了保证每一步的Patch均为可逆的,故我们需要存放一些冗余数据,如记录remove操作仍需记录remove的状态变量的状态值,这样可直接计算出remove对应的逆操作add操作。

为了实现Redo操作,我们Undo时弹出栈的的那个Patch也不能够丢弃,它将进入另一个栈S2中用于实现Redo操作。

当我们当前状态处于State3时,此时无法继续redo,但是能够undo。

流程

于是我们进行Undo撤销操作,此时状态为State3,目标状态为State2,我们undo操作流程如下:

  1. 从S1中弹出栈顶的Patch3

  2. 计算出-Patch3

  3. -Patch3应用到当前状态后得到State2 = State3 + (-Patch3)

  4. 将Patch3加入栈S2

此时又可以undo又可以redo,此时的状态为State2,目标状态为State3,我们的redo操作流程如下:

  1. 从S2中弹出栈顶的Patch3

  2. Patch3应用到当前状态后得到State3 = State2 + Patch3

  3. 将Patch3加入栈S1

我们可以得出如下判定条件:

可实现Undo:S1不为空

可实现Redo:S2不为空

若栈S1和栈S2均不为空,即做了若干操作过后进行撤销到一半,若此时发生了新的变更,则UML状态图上将会出现非线性的分支branch。那么这种情况如何处理呢?目前采取的策略是新操作将会清空S2栈

方案二

还有第二种方式为使用双向链表来实现Undo Redo。起初存在一个CurrentState指针指向链表的头结点,当我们每次发生变更后新增的Patch将插入到CurrentState指针的下一条位置,并且CurrentState指针向后移动指向本次变更新增的Patch。

当我们进行Undo操作时,我们仅需要取得CurrentState指针指向的Patch,并将该Patch的逆应用到当前状态,然后CurrentState指针后退,即可实现Undo操作。

当我们进行Redo操作时,我们需要前进CurrentState指针到后继Patch并将其应用到当前状态,即可实现Redo操作。

我们可以得出如下判定条件:

可实现Undo:CurrentState未指向头结点

可实现Redo:CurrentState未指向尾节点

在本项目中,我们是使用了顺序存储的列表+索引值来实现这些操作。CurrentState为一个int值的索引。当CurrentState == -1时代表指向了头结点。

Package

我们已将其算法封装为一个独立的package可随时被任何第三方项目所引用。

这是它的单元测试用例。

首先初始化一个空的state,使用我们封装的UndoRedoManager类包裹state

初始状态State0下,既不能撤销又不能重做。

1
2
3
4
final state = {};
final urm = UndoRedoManager(state);
expect(urm.canUndo, isFalse);
expect(urm.canRedo, isFalse);

当状态发生改变到达State1时,能够撤销但仍不能重做。

1
2
3
4
5
state['e1']=1; 
state['e2']=2;
urm.store();
expect(urm.canUndo, isTrue);
expect(urm.canRedo, isFalse);

当撤销状态State1时,回到了最初状态State0,无法继续撤销但能够进行重做。

1
2
3
4
urm.undo();
expect(state['e1'], equals(null));
expect(urm.canUndo, isFalse);
expect(urm.canRedo, isTrue);

当重做时,回到了State1状态,此时能够撤销但不能重做

1
2
3
4
urm.redo();
expect(state['e1'], equals(1));
expect(urm.canUndo, isTrue);
expect(urm.canRedo, isFalse);

白板数据同步方案设计实现

那么我们是如何基于Diff算法实现分布式场景下的同步呢?

基于话题的发布订阅通信模型

本项目最初设计讨论时候,我们发现其实这个多人协同的场景实际上就是一种分布式状态同步的场景,首先我们需要解决各个节点之间的通信问题:

  1. 每个用户都是作为一个分布式节点去接收中心服务器上的白板状态数据变更

  2. 每个分布式节点也可将变更上传至服务器并发送到其他各个分布式节点上

BaseMessage

首先设计各个节点之间通信的基本消息类型。

  1. 各个节点具备一个唯一的uuid字符串

  2. 节点要加入的房间也具备一个唯一的uuid字符串。

定义一个BaseMessage消息类型,节点之间的所有通信的消息包必须为BaseMessage消息:

1
2
3
4
5
6
7
BaseMessage {
ts: DateTime
    topic: String
    publisher: String
    sendTo: String
    data: any
}

话题设计

每个节点在某个房间均具备如下行为:

  1. 每个节点都能够send一个BaseMessage对象到另一个uuid为sendTo的节点上。

  2. 每个节点都能够register一个回调函数去接收其他节点传送过来的BaseMessage对象。

  3. 每个节点都能够broadcast一个BaseMessage对象到所有的其他节点上。

于是我们发现这些节点通信的行为实际上完全就可以使用基于话题的发布订阅的机制来实现。

  1. 向某个房间的某节点send一个消息实际上可发布话题${roomId}/node/${otherNodeId}/${topic}

  2. 向某个房间中发布广播消息可发布话题${roomId}/broadcast/${topic}

  3. 房间中的每个节点必须订阅以${roomId}/node/${userNodeId}/开头的所有话题

  4. 房间中的每个节点必须订阅以${roomId}/broadcast/开头的所有话题

此时,一个房间里的用户之间便能够进行一对一通信广播通信了。

MQTT通信

此时我们突然想到,MQTT通信机制不就是这样的一种典型的话题通信的方式么?我们应该完全可以纯前端app直接连接一个MQTT服务器完成基本的分布式通信的目标,而无需重新基于WebSocket再造一遍话题通信的轮子。

而且如果前端直接使用MQTT作为分布式同步的通信方式,用户使用起来就像是使用一些开源软件那样,其中提供的那些需要后端提供支持的服务可通过自己配置任意的第三方服务器而实现。如类似于Typora,一些VSCode插件那样写Markdown时候可以自己在设置中配置图床服务器。我们的白板用户也可以自行配置任何第三方MQTT服务器,图床服务器地址等等。

此处列举了一些免费公共MQTT服务器地址,可直接在我们的白板中配置使用这些免费公共的服务器

名称 Broker 地址 TCP TLS WebSocket
EMQ X broker.emqx.io 1883 8883 8083,8084
EMQ X(国内) broker-cn.emqx.io 1883 8883 8083,8084
Eclipse mqtt.eclipseprojects.io 1883 8883 80, 443
Mosquitto test.mosquitto.org 1883 8883, 8884 80
HiveMQ broker.hivemq.com 1883 N/A 8000

在线列表与个性化信息

在实际使用中,我们还会遇到以下的场景需求:

  1. 查看当前房间在线的用户数与用户列表

  2. 辨别当前主持人的是谁

  3. 每个用户能修改自身昵称等个性化信息

为此我们设计了一个特殊的广播消息叫做report广播消息:

  1. 所有加入该房间的用户均需要按照一定的时间间隔循环广播${roomId}/broadcast/report消息

  2. 所有加入该房间的用户均订阅${roomId}/broadcast/report消息,此时我们可以:

    1. 获取到BaseMessage中的publisher,data,ts字段,data字段可设为个性化信息,这里我们使用字符串类型表示用户自定义的昵称username

    2. 更新Map < DateTime, String > _onlineUserIdMap,即_onlineUserIdMap[message.ts] = message.publisher,这里的key为最近一次的report消息的时间

    3. 更新Map < String, String > _onlineUsernameMap 数据,即_onlineUsernameMap[message.publisher] = message.data,这里的key为发布者的uuid

    4. 过滤_onlineUserIdMap得出满足约束当前时间 - 最近一次report时间 < 指定超时时间的所有键值对,其中的values就表示当前在线的用户的uuid所构成的列表

    5. 根据用户的uuid再次查询_onlineUsernameMap即可查询到用户的自定义昵称等个性化信息

分布式同步

同步分为两类角色,第一类为Owner,第二类为Member

  • Owner为会议主持人,其拥有的model为标准的完整model。

  • Member为会议成员,其拥有的model需要从owner处获取。

当Member加入会议时,其需要拿到完整的白板数据,需要先发起广播消息请求需要白板数据,若在等待时间内Member收到了Owner发来的,后续Member将不停地接收Owner的diff结果的Patch包来更新自身的model数据。

若在规定超时时间内Member未收到白板数据的响应,则判定该房间不存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
@startuml D
Member -> Owner: 发起请求
...等待响应...
alt [未收到响应数据]
Member -> Member: 房间号不存在
else [收到全量数据]
Owner -> Member: 全量数据
loop Owner数据存在更新
Owner -> Member: 增量补丁
Member -> Member: 变更本地数据
end
end
@enduml

主持人离场

整个分布式同步的通信图中,存在若干个中心,每个中心就是一个个的Owner,它与各个Member之间进行分布式通信。

当主持人离场或意外掉线后,该房间将被销毁。

当然,由于我们不存在后端服务,故此处的销毁并非显式的销毁api调用。这里的销毁仅仅只是一种逻辑上的概念。实际上,其余Member节点的report的onlineUserId列表中发现若主持人的最新report时间超过了给定的超时时间,则判定为主持人已离场,Member可自动退出房间。

PS: 由于每个人拥有的白板数据均为完整的白板数据,故若主持人掉线,其他成员事实上也是有能力通过投票选举主持人等方式实现转移主持人身份来达到继续维持房间的效果,出于时间原因,该功能暂未实现,目前若主持人离场,会议将自动结束。

插件化方案设计实现

场景概述

我们的模型Model的数据类型定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
enum ModelType {
rect, freeStyle, ...
}

Model {
// 模型id
id: int
// 模型类型
type: ModelType
// 模型数据,由模型类型决定不同数据类型
data: dynamic
// 模型公共属性
common: CommonModelData
}

我们需要渲染该模型,则可能在某个Widget组件中需要写出如下代码:

1
2
3
4
5
6
7
8
9
10
Widget buildModelWidget(Model model) {
switch(model.type) {
case ModelType.rect:
return RectModelWidget(model.data as RectModelData);
case ModelType.freeStyle:
return FreeStyleModelWidget(model.data as FreeStyleModelData);
default:
throw UnimplementionError();
}
}

我们需要设计每个不同类型模型的编辑器的ui界面,可能需要写出下列代码:

1
2
3
4
5
6
7
8
9
10
Widget buildModelEditorWidget(Model model) {
switch(model.type) {
case ModelType.rect:
return RectModelEditorWidget(model.data as RectModelData);
case ModelType.freeStyle:
return FreeStyleModelEditorWidget(model.data as FreeStyleModelData);
default:
throw UnimplementionError();
}
}

我们还需要在右键中的“添加模型“菜单显示模型元素列表,在故需要知道该模型的文字显示,可能需要写出如下代码:

1
2
3
4
5
6
7
8
9
10
String buildModelInMenuText(String modelType) {
switch(modelType) {
case ModelType.rect:
return '矩形';
case ModelType.freeStyle:
return '自由画板';
default:
throw UnimplementionError();
}
}

问题概述

考虑到我们的需求中需要支持很多丰富的图形元素,且未来也有可能需要扩展出更多的未知的图形元素,每当我们扩展新图形时,均需要修改上述的模型渲染组件模型编辑器组件,菜单项等代码中的switch分支,且这些组件还分布在不同的代码文件,不同类,不同函数中,这将会对扩展新图形带来很多麻烦,并不符合开闭原则

抽象插件接口

于是我们就考虑将上述不同种类的模型具有不同的行为实现抽象出来定义成一组抽象接口,形成插件化接口,使得这些不同的模型的行为职责内聚到各自插件类中,提高了内聚性,降低了白板本身与白板插件代码的耦合度。

1
2
3
4
5
6
7
8
9
10
abstract class ModelPluginInterface {
String getTypeName(); // 获取该插件的type
String getInMenuName(); // 获取该插件在菜单中的名称
// 该模型的渲染视图构造
Widget buildModelView(Model model, EvventBus<BoardEvent> eventBus);
// 该模型的编辑器视图构造
Widget buildModelEditor(Model model, EvventBus<BoardEvent> eventBus);
// 创建该类模型时的默认数据类
Model buildDefault();
}

通过定义不同的实现类来实现他们自身的这些行为。

实现插件接口

我们定义一个Markdown插件为插件样例

Data

首先定义Markdown图元的数据类定义:

1
2
3
4
5
class MarkdownModelData extends HashMapData {
MarkdownModelData(super.map);
String get markdown => map['markdown'] ??= '';
set markdown(String v) => map['markdown'] = v;
}

View

定义该Model的渲染组件

1
2
3
4
5
6
7
8
9
class MarkdownModelWidget extends StatelessWidget {
final MarkdownModelData data;
const MarkdownModelWidget({Key? key, required this.data}) : super(key: key);

@override
Widget build(BuildContext context) {
return Markdown(data: data.markdown);
}
}

Editor

定义该Model的编辑器组件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class MarkdownModelEditor extends StatelessWidget {
final Model model;
final EventBus<BoardEventName> eventBus;
const MarkdownModelEditor({
Key? key,
required this.model,
required this.eventBus,
}) : super(key: key);
void refreshModel() => eventBus.publish(BoardEventName.refreshModel, model.id);
void saveState() => eventBus.publish(BoardEventName.saveState);
MarkdownModelData get modelData => MarkdownModelData(model.data);

@override
Widget build(BuildContext context) {
final controller = TextEditingController();
controller.text = modelData.markdown;
controller.addListener(() {
modelData.markdown = controller.text;
refreshModel();
});
return TextField(
minLines: 100,
maxLines: null,
controller: controller,
);
}
}

Entry

定义Markdown插件的入口类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class MarkdownModelPlugin implements BoardModelPluginInterface {
@override
Model buildDefaultAddModel({required int modelId, required Offset position}) {
return Model({})
..id = modelId
..common = (CommonModelData({})..position = position)
..type = modelTypeName
..data = (MarkdownModelData({})..markdown = '# HelloWorld').map;
}

@override
Widget buildModelEditor(Model model, EventBus<BoardEventName> eventBus) {
return MarkdownModelEditor(eventBus: eventBus, model: model);
}

@override
Widget buildModelView(Model model, EventBus<BoardEventName> eventBus) {
return MarkdownModelWidget(data: MarkdownModelData(model.data));
}

@override
String get inMenuName => 'Markdown文档';

@override
String get modelTypeName => 'markdown';
}

注册插件接口

那么白板怎样使用这些插件呢?我们需要引入一个插件容器去注册管理这些插件,定义一个简单的插件容器如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class BoardModelPluginManager {
final Map<String, BoardModelPluginInterface> _plugins = {};

// 构造一个插件管理器
BoardModelPluginManager({
List<BoardModelPluginInterface> initialPlugins = const [],
}) {
initialPlugins.forEach(registerPlugin);
}

// 注册一个插件类
void registerPlugin(BoardModelPluginInterface plugin) {
String typeName = plugin.modelTypeName;
if (_plugins.containsKey(typeName)) {
// 同一个插件重复注册
if (_plugins[typeName] == plugin) return;
// 不同插件但是类型名称相同,抛异常
throw Exception('Board model plugin has been registered $typeName');
}
_plugins[typeName] = plugin;
}

// 通过一个type获取插件
BoardModelPluginInterface getPluginByModelType(String modelType) {
if (!_plugins.containsKey(modelType)) {
throw Exception('Plugin name: $modelType not be registered');
}
return _plugins[modelType]!;
}

// 获取插件名称列表
List<String> getPluginNameList() => _plugins.keys.toList();
}

于是我们可以创建一个插件管理器对象并传入各个插件的定义并在构造白板对象时传入插件管理器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
BoardBodyWidget(
eventBus: eventBus,
boardViewModel: pageSetViewModel.currentPage.board,
pluginManager: BoardModelPluginManager(
initialPlugins: [
RectModelPlugin(),
LineModelPlugin(),
OvalModelPlugin(),
SvgModelPlugin(),
PlantUMLModelPlugin(),
ImageModelPlugin(),
AttachmentModelPlugin(),
FreeStyleModelPlugin(),
HtmlModelPlugin(),
MarkdownModelPlugin(),
SubBoardModelPlugin(),
],
),
)

插件化设计UML

最终插件化的设计UML类图如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
@startuml C
interface ModelPluginInterface {
+ String getTypeName()
+ String getInMenuName()
+ Widget buildModelView()
+ Widget buildModelEditor()
+ Model buildDefault()
}

class ModelPluginManager{
+ void registerPlugin(PluginInterface plugin)
+ ModelPluginInterface getPluginByTypeName(String typeName)
+ List<String> getPluginTypeNameList()
}
class RectPlugin {
+ String getTypeName()
+ String getInMenuName()
+ Widget buildModelView()
+ Widget buildModelEditor()
+ Model buildDefault()
}
' 实现
RectPlugin ..|> ModelPluginInterface

class ImagePlugin {
+ String getTypeName()
+ String getInMenuName()
+ Widget buildModelView()
+ Widget buildModelEditor()
+ Model buildDefault()
}
' 实现
ImagePlugin ..|> ModelPluginInterface

class Menu{}
' 关联
Menu --> ModelPluginManager

class BoardView{}
BoardView --> ModelPluginManager

class Main{}
' 关联
Main --> ModelPluginManager
ModelPluginManager --> ModelPluginInterface
Main --> RectPlugin
Main --> ImagePlugin

@enduml

从UML类图中可以看到,这里的BoardView类为高层模块,插件类实现作为低层模块,两者并没有直接的依赖关系,而是共同依赖了一个ModelPluginInterface的抽象,以一个中间层ModelPluginManager联系了起来,这符合了依赖倒置原则

当我们面临新的图形元素的扩展需求时,仅仅只是增加了一个插件的实现类,在Main中构造这些插件类并传入ModelPluginManager中轻松实现了图元类型的扩展,这符合了开闭原则

插件化设计总结

我们通过抽象出公共接口来实现了一种插件化的设计,符合了开闭原则和依赖倒置原则,内聚了图形元素的行为职责到插件类。不过,当前我们的插件化系统仅仅只能算是一种静态的插件化系统,并不算是一个动态插件化系统,若要实现一个动态插件化系统,我们还需要考虑插件的生命周期,插件的加载与卸载等。

由于Flutter阉割了Dart关于反射与动态化相关的特性,故目前难以实现动态插件化。不过由于我们已经将模型插件的编辑器Editor与视图View的渲染抽象成了Widget组件,将模型插件的数据Data抽象为了HashMap,故仅需引入一种脚本引擎能够动态构造出Widget对象和HashMap即可为动态插件化带来可能。这就属于Flutter动态化相关的知识了。

项目展示

在线运行

https://sit-board.github.io/

注意:受限于时间精力,故未针对Web端做平台相关的适配,可能很多功能在Web端无法使用,若需要完整体验,请下载Release中的客户端进行体验。

Web端仅作为快速体验为目的,请以实际桌面端或移动端平台为准。

浏览器端右键或长按时可能会弹出剪切板权限提示,这是因为软件支持复制粘贴图形对象到本机剪切板。

视频Demo演示

https://www.bilibili.com/video/BV1Wd4y1b7rc/

使用说明

board_front/使用说明.md

项目截图

白板主界面

白板设置

本地白板

如图展示了矩形/文本框插件,椭圆插件,图片插件,自由画板插件,PlantUML插件,Markdown插件,子画板插件的渲染,其中子画板插件为画板本身,类似于网页中的iframe标签元素,且比例为竖屏时自动适配移动端ui。

多人协同

仓库地址

Github 组织地址 https://github.com/SIT-board

项目仓库地址 https://github.com/SIT-board/board_front