关于研究鼠标绘制平滑曲线的阶段总结

做桌面应用这么多年,一直想寻找一个好的实时手绘平滑的实现或者开源库。实在是个人数学不怎么样,而这方面可用资料实在太少,断断续续找了好些年。最近也算有点收获,写篇文章对这段经历做个总结,整理一下。

(本文不涉及对具体算法的分析,有兴趣的可以对提到的开源方案进行研究)

(以前也写过一篇曲线平滑的文章,后来觉得太蠢了,就删掉了)

1. 调研初期

刚开始尝试寻找曲线平滑的算法,主要分两种方案。一是曲线连接方案,主要是一些插值算法。例如要连接A,B两点,一般会根据A,B和前后的点计算一条插值曲线,使得A、B点不会太“生硬”,比如贝塞尔。二是曲线拟合方案,是寻找多个连续的曲线,使得所有离散点“看起来”距离曲线都很近。由于不要求曲线经过所有点,所以可以适应任意密度的坐标点。

鼠标坐标点通常都是整数坐标,如果移动比较慢,坐标点会非常紧密。比如想将鼠标指针从(0,0)移动到(1,1),中间可能会经过(0,1)或(1,0),此时曲线连接方案是没办法生成可用曲线的, 这样的抖动需要通过合适的算法消除,曲线拟合方案是比较合适的。

这个阶段对鼠标绘制过程没有概念,盲目去搜索各种各样的拟合方案。也尝试通过采样来减少抖动,再利用曲线连接方案,有些效果但没什么价值。

2. 初见突破

一次使用某软件,发现单次绘制结束后,会有一次平滑过程,虽然不是实时的。通过各种方式搜索,找到了 Paper.js 路径简化示例。实现原理大概是:

  • 选择起始点和终点,作为拟合范围
  • 对该拟合范围,计算一条Bezier曲线
  • 对该范围内的点,计算点与曲线的误差
  • 如果误差都在期望范围内,结束。
  • 否则,选择误差最大的点,作为分割点,将该拟合范围的离散点分割成两段,分别拟合。

将该方案应用到鼠标绘制,由于新增坐标点会影响分段,对所有坐标拟合的话,每次的曲线都不一样,整条路径都在抖动。考虑过一个方案是,按时间或距离强制插入一个分段点,避免靠前的路径抖动。效果提升明显,但没什么实际用途。

至此告一段路,之后很长时间都没再继续研究。

3. 新的发现

最近体验Leonardo绘图软件时,里面的平滑线条非常符合个人的预期,但软件不开源,尝试猜测原理,但数学能力实在不行,遂放弃。此时,终于开窍,开始尝试找一些开源软件。

期间在Blender这款3D建模软件的github提交里,发现了曲线拟合相关的内容,将对应源码下载下来使用,原理应该跟paper.js一样,接口似乎是支持指定某些个坐标点是折角,类似强制插入一个分段点。

(其实这些年搜索方案有一个最大的障碍就是,根本不知道应该相关的英文关键字是哪些,搜索出来距离期望差距太大,一直以为啥都没有)

4. 正确的方向

在搜索开源软件的过程中,发现了这个网站 Excalidraw ,使用鼠标绘制比较平滑的线条,去Github上下载了源码,编译后用浏览器调试,发现了入口。使用的是 perfect-freehand, 这个库提供了一个在线的测试网站,使用提供的接口可以生成包围坐标点的闭合SVG路径,绘制一些好看的艺术字。

研究perfect-freehand的源码发现提供了 getStrokePoints 接口对做坐标点进行防抖处理,函数很简单,将其改为C++使用Qt测试,效果完爆之前的方案。防抖算法思路大概是:

  • 假设A, B, C, D, E四个坐标点,A作为起始点不变
  • 在A和B坐标之间按固定比例,取一个中间点作为新坐标B′,
  • 在B′和C坐标之间按同样固定比例,取一个中间点作为新坐标C′
  • 重复,E坐标为最后一个坐标,将其作为终点

这样生成出一组新的坐标序列,再以此序列生成连续的二次Bezier曲线,生成过程很简单,可以参考在线示例。到此,平滑效率、效果都基本满足了期望。

5. 用Google的开源库告一段落

实际之前的寻找方向,忽略了一个非常重要的因素——速度。速度可以用来推测操作者的期望,以上面的鼠标缓慢移动为例,可能操作者确实是有一个将鼠标从(0,0)移动到(1,0)的过程,如果不考虑速度,算法是不可能推测出相对准确的结果的。

换了一些搜索关键字,找到了来自Google的 ink-stroke-modeler ,看描述是支持根据坐标移动速度来自适应平滑策略,以达到美观的效果。具体原理和算法超出了个人的理解能力,有兴趣的可以参考提供的数学公式研究。

将代码下载下来尝试编译,平时主要用IDE创建项目,对于CMake完全不熟,好在项目比较简单,胡乱测试,终于使用nmake编译成功。

将库引入Qt项目,使用提供的参数配置,监听鼠标事件不断插入新的坐标和时间,这个过程会生成新的坐标序列,仅需要直线连接绘制即可,效果非常棒。目前还看不懂那些参数代表什么意思,具体修改后是否要做其他适配,如何适配没有测试,待以后有机会了再研究。

在这里插入图片描述

ink-stroke-modeler确实没什么其他的参考资料,Readme里提到最低是C++17标准,估计Windows有些支持不完整,需要C++20,也有一些bug。

6. 总结

到目前为止,关于鼠标实时绘制平滑曲线的研究终于告一段路,个人能力有限,不足以研究出更好的平滑算法,只能依靠开源的库。

这篇文章算是做个索引,给各位开发者提供一些思路,少走些弯路。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码

)">
< <上一篇
下一篇>>