绘制在不连续的步骤

下午好，绘制在不连续的步骤

背景
我的问题涉及使用不连续的步骤在空间中的任意圆弧绘制的弧。然而，这是独一无二的，因为我不是以典型的意义来画画。我正在设计的固件是用于CNC磨机的gcode解释器，它将命令转换为步进电机运动。现在，我已经在这个网站上发现了一个类似的问题，但是建议的方法论（Bresenham算法）似乎不适用于在空间中移动对象，因为它只依赖于计算圆的一个八分圆，然后镜像关于剩余的对称轴。此外，在两个任意角度之间计算弧线的规定方法依赖于三角函数（我正在微控制器上实现，如果可能的话，希望避免代价高昂的触发函数），并且不会采取超出范围的步骤。最后，该算法仅被设计为在一个旋转方向上工作（例如逆时针）。

问题
因此，在实际的问题：有谁知道可以用“画”在不连续的步骤任意圆弧，同时还给予对于角方向的通用算法（CW/CCW）？最终的实现将使用C语言完成，但是针对该问题的语言是无关紧要的。

预先感谢您。

参考
SO张贴上绘制采用布氏算法的简单循环：描述布氏算法
"Drawing" an arc in discrete x-y steps

维基页面一圈
http://en.wikipedia.org/wiki/Midpoint_circle_algorithm

G代码指令执行（见。 G2和G3）
http://linuxcnc.org/docs/html/gcode.html

来源

2011-06-24 phobos51594

没有微控制器已经在硬件支持浮点运算？ – titus

是和不是。我目前支持的控制器没有硬件FP，但确实有适度优化的软件FP库（AVR Mega32）。我一直在考虑升级到支持硬件FP的更强大的32位AVR之一。我实际上已经计划通过将坐标转换为整数步来解决大部分FP问题，并且只有在事件不与电机步骤“对齐”时才会采用FP错误累加器。尽管如此，我仍然乐于接受任何事情。将有4000步/英寸，如果它有任何区别。 – phobos51594

哦，另外，固定点也是一种选择，因为考虑到我使用的廉价机械部件，我甚至可以看到0.005的分辨率。过去的一些地方是可能比我的汽车花费更多并且可能足以产生错误积累的机器的领域。 – phobos51594

您可以将其转换为一个合理的贝塞尔曲线，然后应用德卡斯特里奥算法准确，迅速地为任意的有理曲线解决此问题。这可以很容易像圆和双曲线圆锥曲线完成：

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/NURBS/RB-conics.html

一旦你有一个理性的贝塞尔曲线，重新采样曲线成离散的步骤，您应该德卡斯特里奥算法使用。该算法使用动态编程，速度非常快，数值稳健。如果你还没有听说过，我真的建议学习它，因为它是一个相当聪明的小算法：

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/de-casteljau.html

有几种方法，你就可以使用德卡斯特里奥算法得到离散抽样你的曲线。首先，您可以天真地将其应用于以均匀增量评估沿其参数空间的曲线。如果增量必须均匀分布的，你必须改变你的插补坐标转换成圆弧的长度单位：

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/curves/continuity.html#Arc-Length-Parameterization

这种技术的细化，而不是转换成弦长参数其中接近弧长参数随着时间的推移：

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/INT-APP/PARA-chord-length.html

最后，如果你需要一分不少的曲线，你可以申请德卡斯特里奥算法为角切割程序的初始控制点矢量提炼成一个极限p olygon任意地接近你想要的曲线了一些用户指定的公差：

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/bezier-sub.html

这些说明从C.K.教授采取Shene的课程笔记，这是了解样条曲线和曲面细分一个很好的资源：

http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/

来源

2011-06-25 00:41:52 Mikola

感谢您的所有链接，你可以适应它在32K。我特别喜欢它如何轻松地扩展以处理任何可表示的曲线。 – phobos51594

np，这几乎是当今所有工业CAD软件包使用的标准技术。有一个原因，NURBS已经取代了所有其他基元作为代数表面的主要表示形式:) – Mikola

这是一个愚蠢的想法，但它可能只是工作
计算机上的每个可能的半径的计算圈，并将这些信息保存在microcotroller内存中。
假设您的圆圈半径为1至1000像素。即1000 *（1000 + 1）/ 2 * 2 * pi =所有圆圈上的300万点
对于您实际只需要偏离前一点的每个点，就有8种情况，这些可以用3位编码
取决于你的微控制器有多少位，比如说8/16位，有2个像素/字节或者5个像素/字
你需要1.5MB的内存在8位微处理器上，而在16位微处理器上需要1.2MB。
您可以存储具有半径k像素增量的圆圈，并且只能使用1.5MB/k的内存。
另一种优化方法是将圆形建模为具有多边的多边形，但不保留到前一点的偏移，而是保留两步或更多的点，并以某种方式插入其间的像素。
如果你持有偏移像素的两个步骤，你有16个案例，编码在4位=> 3/2million点=> 750KBytes
如果你每步拥有像素你有s * 8个可能性，可以编码为3 + log2（s）位。
LE：
像素每32steps/8mils => 10英寸半径的圆10 * 4000 * 2 * PI/32steps * 1字节= 7.85KB，像素每128steps/32mils => 10英寸半径的圆10 * 4000 * 2 * PI/128 * 10位= 19634Kbits = 2.4KB
LLE： 你居然没有S * 8点的可能性，还有比这更少，因为在放大的圆圈是直线
这一切都归结到如何以及你可以打包的数据，或使用外部存储器
另一种优化：只存储象限或八分圆，并从其余的对称中找出其余的优点 LLLE： 每

来源

2011-06-24 23:23:04 titus

嗯，有趣的想法。不幸的是，由于我的电机/丝杠选择使我每4000英寸有4000步（像素，真的），所以我不得不拥有超过1000个像素。更不用说有问题的微控制器总共有32K的闪存。但绝对不是我曾考虑过的事情。 – phobos51594

圆半径分布可能是指数而不是线性的，所以1,2,4,8,16，...而不是4,8,12,16，...;我认为如果你同时使用两个优化 – titus

绘制在不连续的步骤

回答

相关问题