奥斯汀项目第3部分，共6部分：油墨平滑

嗨，我叫埃里克·布鲁默。我是C++编译器优化器上的开发人员，但我花了一些时间来研究项目代码名称奥斯丁，以帮助展示C++在真实世界程序中的能力和性能。关于这个项目的概述，请查看 简介博客文章 .

这篇博文描述了我们如何执行墨迹平滑。

考虑一种简单的墨迹绘制机制：在采样的每个手写笔输入点之间绘制直线。我们在Windows8上使用的设备和驱动程序每秒采样120个输入点。这看起来可能很多，但非常快速的笔划有时会导致明显的直边。以下是应用程序中的一个示例（无墨迹平滑），其中显示了一些直边：

这里是相同的一组笔划，但是笔划平滑了。

样条曲线

我们使用样条线技术来进行实时墨水平滑。考虑了其他选项，但样条曲线（a）可以 这样你画的笔划在新的输入点采样时总是平滑的，（b）在计算上是可行的。

网上有很多关于样条曲线平滑技术的文献，但在我（有限的）研究中，我发现要么描述过于简单，要么描述需要计算机图形学学位才能理解。所以这是我在中间拍摄的照片…

在计算机出现之前，有一种技术被用来创建平滑的曲线，它使用一种叫做 样条曲线 . 这是一种可弯曲的材料（粗绳、一块可弯曲的木头等），可以弯曲成形，但也可以固定在身体的某些部位。例如，您可以取一根较重的绳子，在绳子的不同位置使用一束别针将绳子固定到墙上，然后跟踪弯曲的绳子的轮廓以生成样条曲线平滑的曲线。

快进几十年，现在我们用同样的原理在一组点之间创建一条平滑的线。假设我们有一条有很多点的直线，P0，P1，P2，…要用样条曲线来平滑它，我们取前4个点（P0，P1，P2，P3），画一条经过P1和P2的平滑曲线。然后我们将4个点的窗口移动到（P1，P2，P3，P4），并绘制一条通过P2和P3的平滑曲线。冲洗并重复整个曲线。它之所以是样条线技术，是因为我们认为两点是“固定的”，就像把绳子固定在墙上一样。

在讨论如何在这些点之间绘制平滑线之前，让我们先来看看这些好处：

1. 我们只需要四个点就可以在中间两个点之间画一条平滑的线。当您使用手写笔绘制墨迹笔划时，我们可以不断平滑笔划。也就是说，我们可以做实时平滑。
2. 计算是有界的，通过一些简洁的编译器优化和在绘制平滑线时限制样本数（见下面的第2项），我们可以确保墨水平滑不会处于性能的关键路径上。

有几件事要记住：

1. 我们需要处理在曲线的前两点（P0&P1）之间绘制平滑线，以及在曲线的最后两点之间绘制平滑线。我通过伪造这些点并应用同样的样条技术来实现这些。
2. 我一直在写“在两点之间画一条平滑的线”。我们不能画一条平滑的线；我们只能画一堆看起来很平滑的直线。所以当我说“在两点之间画一条平滑的线”的时候，我的意思是“画许多看起来平滑的连接两点的直线”。我们只是沿着曲线以固定的间隔采样点，这些点在像素级看起来很平滑。

三次样条和基数样条

现在我们来看看数学知识…当一个绘图人员说一条线在一个给定点是光滑的，他们说的是这条线在那个点是连续的，这条线的一阶导数在那个点是连续的，二阶导数在那个点是连续的。抱歉，如果我带回来高中或大学微积分可怕的记忆。

这是五个点的视觉效果，平滑的线条已经用蓝色画出来了。

我们可以将平滑的蓝色曲线的每一段定义为由一个从0到1的参数“t”参数化。因此，蓝色线是4条曲线的串联，如下所示：

P01（t），其中第一段的t范围为0到1（从P0到P1） P12（t），其中对于第二段（P1到P2），t的范围为0到1 …等等…

使用“字符到均值导数”，在每个线段的端点应用平滑的定义，得到一组方程：

P01（t=1）=P12（t=0）                         P`01（t=1）=P`12（t=0）                      P“01（t=1）=P”12（t=0） P12（t=1）=P23（t=0）                         P`12（t=1）=P`23（t=0）                      P“12（t=1）=P”23（t=0） …等等…

解这些方程 确切地 他在努力。看到了吗 样条插值 . 一般来说，如果你要找一个多项式来满足一个二阶导数的方程，你就要买一个3次多项式，也就是三次多项式。因此三次样条曲线中的“三次”。

Wikipedia页面展示了一个拟合平滑度方程的解决方案，但是在这个领域已经做了大量的工作来提出一个新的解决方案 更具计算可行性 解决方案 看起来一样光滑 . 基本上，我们减少二阶导数方程，并说P“01（t=1）~=P”12（t=0），等等。这打开了许多可能性-查找任何三次样条，你会看到许多选项。

经过大量的实验，我发现基数样条曲线最适合我们的笔划。4点P0、P1、P2、P3之间的平滑曲线的基数样条解如下：

系数L用于模拟“重绳中的张力”，可以根据需要进行调整。我们选择了0.5左右的值。如果你有这样的倾向，你也可以写出P23（t），取一组导数，看看这是否符合光滑度方程。如果你是一个高中微积分老师，请不要让你的学生做这个作业。

公式可以用C++表示：

对于（int i=0；i<数量点；i++） { float t=（float）i/（float）（numPoints-1）； 平滑点u X[i]=     (2*t*t*t–3*t*t+1）  * 第2页 +（-2*t*t*t+3*t*t）     * p3x页 +（t*t*t–2*t*t+t）    * L*（p3x-p1x） +（t*t*t–t*t）          * L*（p4x-p2x）；

平滑点=     (2*t*t*t–3*t*t+1）  * 第二年 +（-2*t*t*t+3*t*t）     * p3y公司 +（t*t*t–2*t*t+t）    * L*（p3y-p1y） +（t*t*t–t*t）          * L*（p4y-p2y）； }

numPoints（平滑线上采样的点数）是基于我们认为看起来不错的最小间隔。

性能

就像我之前提到的，我们做实时墨水平滑。也就是说，墨迹笔划在绘制时是平滑的。我们需要确保绘制一条平滑的线不会花费太长时间，否则我们会注意到在墨迹笔划落后于手写笔的地方，帧速率会下降。

在C++中编写这个应用程序的好处之一是编译器优化的机会得以进入。在这种特殊情况下，基数样条方程是由Visual Studio 2012 C++编译器自动矢量化的。这就产生了 性能提升30% 平滑墨迹笔划时，确保我们可以像Windows采样一样快速平滑墨迹点。此外，任何额外的计算时间节省让我们（a）做更多的计算，使应用程序更好，或（b）完成我们的计算，使应用程序睡眠，从而节省能源。

阅读有关自动矢量器的所有信息： http://blogs.msdn.com/b/nativeconcurrency/archive/2012/04/12/auto-vectorizer-in-visual-studio-11-overview.aspx