用于 C/Objective-C/Swift 的 atan2() 的快速、粗略版本？

Question

我正在编写一些图形代码，用于实时绘制平滑连续曲线。我想添加对羽化笔刷的支持。为此，我需要能够计算“法线”，即垂直于构成我的曲线的线段的线。

纯数学方法是使用反正切函数来找到线段的角度，旋转90度，并使用正弦和余弦来找到我的法线的x和y偏移量。一旦我有了我的角度，使用查找表替换正弦和余弦会很容易，但编写一个性能高、精度低的 atan2()似乎很棘手。

我的法线（垂直线）的长度和角度不需要精确。如果差十分之一也没关系。

你们中有没有开发出高速、粗糙版本的atan2()用于此类图形工作？优化这种性能事项是烦琐且耗时的。

我正在使用Swift 3，但我是“多语言”的。我可以很好地集成用C/Objective-C编写的代码。 （或者将其转换为Swift。）

编辑：

更多细节：

该项目涉及手绘图，提供一系列点，如果用户快速拖动手指，则有时相距很远，并使用Catmull-Rom样条添加中间点以创建一系列线段，使其足够小，看起来像平滑曲线。

（Catmull-Rom样条是一种类似于较为知名的Bezier曲线的曲线，但曲线的所有控制点都位于曲线上，因此可以使用输入顶点来平滑用户“自由绘制”的曲线。）

（从现在开始，我将引用“曲线”，但实际上我指的是由线段组成的多段折线，线段长度很短，看起来像平滑曲线）

我已经将代码分解，只生成更改部分的样条曲线。现在速度非常快，可以创建与您绘制速度相同的美丽平滑曲线。主观上，似乎我正在绘制沿着您的手指轨迹逐点跟随的曲线，没有在点之间跳动。

下一个目标是能够使用软边刷绘图。为此，我想要在用户手指轨迹的左右找到与曲线平行的曲线。然后，我将使用OpenGL创建三角形带来定义左右线之间的粗曲线，并使用多边形着色从沿用户手指轨迹曲线不透明到左右平行曲线透明地模糊曲线。

假设我想要绘制一条6点宽的软边曲线。跟随用户手指轨迹的左侧和右侧的曲线都需要从用户曲线延伸3个点。

我计划通过查找垂直于用户手指轨迹的线段的线段，这些线段通过手指轨迹的顶点并向左右延伸所需线宽的1/2来找到左右曲线的端点的顶点。

下面是程序当前版本绘制的曲线的屏幕截图，其中输入顶点绘制为蓝色钻石，我添加的平滑点绘制为空心正方形。（我减少了添加的平滑点数量，以便您更好地了解情况。）

想象一下，通过每个顶点绘制一系列“哈希标记”，每个标记长6个点，以其中一个顶点为中心，垂直于平滑曲线的第一条线段，该线段以该顶点结束。

正如彼得·O在他的答案中指出的那样，找到与任何特定线段垂直的线段很容易 - 只需倒置斜率。但是，我想要特定长度的线段。（在我的示例中，6个点，每个顶点两侧各3个点。）我正在寻找快速的方法来实现这一点。我可以使用三角函数或平方根来计算我的法线的端点，但这两种方法都非常慢。

- Duncan C

---

我不够聪明来回答你的问题，但这似乎是一个非常有趣的话题。你引起了我的兴趣。 - temp

@AntonínLejsek，请查看我的编辑。 - Duncan C

只是好奇，atan2函数从math.h桥接到Darwin后速度不够快吗？ - JAL

Answer 1

针对您的问题，如果您只是想要找到与另一条线垂直的线，甚至不需要使用atan2；您可以改用以下方法。假设 (x1, y1) 和 (x2, y2) 是输入的线段。

// Find deltas
dx=x2-x1
dy=y2-y1
// Find perpendicular vector to (dx, dy)
 pdx=-dy
 pdy=dx
 // Normalize the vector to a unit vector
 length=sqrt(pdx*pdx+pdy*pdy)
 if(length!=0){
    invlength=1.0/length
// Scale the vector as desired
    invlength*=scale
    pdx*=invlength
   pdy*=invlength
 }
 // Now, find a line segment parallel to the vector
 x2=x1+pdx
 y2=y1+pdy

或者，如果您坚持使用atan2，我知道有一个公共领域的实现，在http://www.dspguru.com/dsp/tricks/fixed-point-atan2-with-self-normalization上。尝试两种方法，看哪种更适合您的目的。

通常，如果您发现自己调用atan2(dy,dx)只是为了得到cos和sin的正确角度，您通常可以使用规范化的(dx, dy)向量的x和y分量来分别获得余弦和正弦。

- Peter O.

---

Peter，我知道使用斜率的倒数可以给我一个垂直于输入线段的线段，但我需要一个固定长度的垂直线段，其中源线段将是任意长度。 - Duncan C

要将(dx, dy)转换为单位向量，这正是您所想的。找到sqrt(dx*dx+dy*dy)，然后将(dx, dy)除以结果即可。现在您有了一个垂直的单位向量(dx, dy)，可以重新调整大小以达到所需的长度。 - Peter O.

或者，如果您坚持使用atan2，我知道一个公共领域的实现，位于http://www.dspguru.com/dsp/tricks/fixed-point-atan2-with-self-normalization。尝试两种方法，看看哪种更适合您的目的。 - Peter O.

彼得，我明白你的意思。然而，计算机上的平方根是最慢的函数之一。我正在寻找一个足够高效的算法来计算这些单位法线，并在用户绘制时“实时”绘制平滑边缘曲线。你的解决方案涉及平方根（非常慢）和除法（性能不错，但比乘法和加法慢）。 - Duncan C

我开始认为基于查表的平方根算法可能是可行的。（在表项之间进行线性插值。） - Duncan C