文摘

我们现在和研究现有数字微分分析器(DDA)为圆生成算法,包括改进的两步DDA算法可以实现完全的基本变化,加法和减法。

1。介绍

数字插值算法广泛应用于数控机床,图形显示和策划者,和操纵机器人。圆和圆弧频繁出现在计算机图形学中,计算机控制的印刷,和自动控制;参见[1]。一代的最流行的方法之一圆和弧称为数字微分分析器(DDA)。数字循环插入器(或角扫发电机)基于DDA方法广泛应用(2- - - - - -6]。有很多论文是插入器等特点研究结果系统化(7,8]。

本文的新改进的两步算法基于圆代。在文献[9]Nystrom两步方案应用到圆的想法代首次出现。我们的下一个文献[10)开发理论和几何方面的这种方法。在本文,我们专注于实践和实验的问题。此外,我们考虑任意半径的圆 ,而在9,10我们假定 。

该方法的精度高于其他已知算法的准确性。是因为它的简单性(它只使用基本的转变,加法和减法);这个方法也可以用于数控,规划机制,等等。

2。DDA算法

DDA算法的一般类圆代是基于明显的三角转换描述旋转向量 在坐标平面上 - - - - - - (图1); DDA算法的优点包括简单和高速生成圆点坐标 , 。


图1
旋转矢量 在坐标平面上 - - - - - - 。

替换 ,在那里 是一个整数(通常是 ),我们重写(1), 显然,可以由一个旋转矩阵来表达 :

为了避免昂贵的三角函数计算DDA算法使用简单的(便宜)表达式代替 和 。例如,通过更换三角函数的泰勒级数截断得到所谓的同时DDA算法(3]。旋转矩阵的行列式为1。DDA算法有不同的决定因素和矩阵 只是大约。越近,= 1循环插入器(更精确的是相应的2]。近似 和 ,得到最简单的(和最精确的)DDA算法(2,11]: 更准确的算法得到使用 和 (7,12,13]: 近似 和 与前两个泰勒级数,我们获得以下算法(14]: 另一个二阶计划,不同截断泰勒级数形式,提出了(2]: 上述所有DDA算法每一步有系统的径向误差,定义为 在[7),考虑到递归关系没有径向误差的算法 然而,这些算法的实现需要浮点运算(7]。替换的系数(9)与泰勒级数的前两项2),我们得到 由于我们获得,显然,算法给出的(7)。

较低水平的径向误差与更简单的硬件实现可以通过使用下面的算法(3,13]: 另一个方案值得被提及的是所谓的“神奇圈”插入器(5,7,15]: 这比最简单的方案(插入器更准确4),只需要使用两个乘数。然而,实际上它不是用于大 ,因为生成的“圈”变成了椭圆(2,15]。

还有一组连续的DDA算法(12]。这里是其中一些: 两步算法: 初始条件: , , , ,被称为“直接”或biquad形式的循环插入器(14]。请注意,它的实现只需要两个乘数。

循环过程中分代径向误差积累,积累的法律是特定于给定的算法。注意,在大多数情况下,圆的半径是选择满足条件 (2,12,15]。很明显,最大的错误就会发生 。在表1我们给绝对径向系统误差的最大值 和 为完整的循环,即一代。初始条件选择 , 。

表1
绝对的径向误差的最大值( )。

除了径向误差的一个重要的角色在这样的设备(特别是计算机数控(CNC)插入器)是由弦演奏的错误 (7),不应超过一个基本长度单位(客人)。与径向误差不同,弦误差不积累。在[7)结果表明,为更快的循环点代最精确的方法(5)- (7),(9) 从条件可以选择吗 在 (我们回想一下, );这是 由于数控系统半径可以达到的价值 布鲁数控插入器的角度范围 ,在那里 重叠的所有可能的半径值范围(尽管采用算法可以在工作 )。

在表2我们给绝对径向系统误差的最大值为最精确的算法 。

表2
绝对的径向误差的最大值( )。

从这些结果我们看到算法(11)是最准确的。因此,在接下来的部分我们选择算法(11)为了比较这两个新的循环插入器中引入[10]。

3所示。新DDA算法

提出了两步DDA算法的值 和 是由以下公式: 这是一个精确的算法,可以得到如下(另一种方法,请参阅[10])。我们考虑的旋转点 , 来 , ;参见图2。因此,我们得到以下方程: 从(20.我们获得的值 和 : 用给出的值(21)(20.),我们得到 我们认识到精确的经典谐振子方程的离散化16,17]。从(22), 用获得的值(21),我们得到 这可以很容易地减少 也就是说,(18)。该算法适用于初始条件: , , , ,在那里 ( 是一个整数)。近似 一个可以改变(18)到另一个两步算法: 与 , , , 。这个算法是首次提出在9];参见[10]。


图2
3代的后续点沿圆。

功能图插入器的繁殖(26)如图3。插入器包含6寄存器(寄存器,寄存器,寄存器3,寄存器4,输出- 和输出, ),2乘数(右移位寄存器1右移位寄存器2),减法器和加法器。


图3
循环插入器功能图(26)。

在这个方案中,一开始(在插入器开始前)的值 和 分别记录在寄存器2和4,而值 和 记录在寄存器1和3。然后,值 和 存储在寄存器1和2,值吗 和 。存储在寄存器3和4。右移位寄存器1和右移位寄存器2执行乘法运算的值 和 通过 。因此,减法器的输出和加法器并行二进制编码形成符合(26)。的值被记录在输出 和输出 。

表3包含绝对径向系统误差的最大值的算法,由(26),完整的循环后仿真 在哪里 结构元素datapath公司(位)和 的迭代次数。表4包含相同的数据情况 。注意,表中给出的结果1和2不包括舍入错误;因此他们不依赖 。

表3
绝对的径向误差的最大值( )算法(26)。
表4
绝对的径向误差的最大值( )算法(26)。

类比(算法给定的数据11)表5(我们认为,和之前一样,27))。表6包含相同的数据 。

表5
绝对的径向误差的最大值( )算法(11)。
表6
绝对的径向误差的最大值( )算法(11)。

比较表中的错误3和5,在表4和6,我们看到的绝对径向误差算法(26)(表3和4)小于著名算法的错误(11)(见表5和6)。例如,我们可以比较值的错误 和 表中给出3和5。因此,我们将得到一个绝对的径向误差更小 次了。

我们也看到,较小的 之间的区别是,两种算法的相应的错误。例如,对于 和 我们得到一个绝对的径向误差更小 次了。

最后,数据4,5,6,7现在的数量正确的函数 ,因为 和 和 和 ,分别。


图4
的结果正确的比特数的函数 在 和 。

图5
的结果正确的比特数的函数 在 和 。

图6
的结果正确的比特数的函数 在 和 。

图7
的结果正确的比特数的函数 在 和 。

提出了数据清楚地表明,该算法(26)收益率更多正确的比特算法相比11)。

4所示。结论

一个新的圆生成DDA算法提出了。在硬件实现和精度圆代提出的DDA算法圆插入器与现有的算法相比更有效率。我们希望该算法能找到一些应用程序在计算机图形学中(显示屏),计算机控制的印刷,自动控制,等等。

利益冲突

作者宣称没有利益冲突有关的出版。

承认

第二作者(Jan l . Cieśliński)部分是由美国国家科学中心(NCN)批准号2011/01 / B / ST1/05137。