以离散步骤绘制弧

Question

下午好,

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

问题
那么,关于实际问题:有没有人知道一种通用算法可用于在离散步骤中"绘制"任意弧,同时仍然给出角度方向(CW/CCW)？最终的实现将在C中完成,但出于问题目的的语言是无关紧要的.

先感谢您.

参考文献
SO使用Bresenham算法绘制一个简单的圆圈:
在离散的xy步骤中"绘制"弧

Wiki页面描述了Bresenham的圆形算法
http://en.wikipedia.org/wiki/Midpoint_circle_algorithm

要实现的Gcode指令(参见.G2和G3)
http://linuxcnc.org/docs/html/gcode.html

Answer 1

通过将其转换为有理Bezier曲线,然后应用de Casteljau算法,您可以准确快速地解决任意有理曲线的问题.对于像圆圈和双曲线这样的圆锥曲线,这很容易做到:

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

一旦有了理性的Bezier曲线,要将曲线重新采样为离散步骤,就应该使用de Casteljau算法.该算法使用动态编程,并且非常快速且数值稳健.如果您之前没有听说过,我建议您继续学习它,因为它是一个相当聪明的小算法:

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

有几种方法可以使用de Casteljau的算法来获得曲线的离散采样.首先,您可以天真地应用它以统一增量沿其参数空间评估曲线.如果增量需要均匀间隔,则必须将插值坐标更改为弧长单位:

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

最后,如果曲线上需要很多点,则可以将de Casteljau算法应用为角切割程序,将初始控制点矢量细化为极限多边形,任意近似所需曲线,直至某个用户指定的公差:

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

这些笔记来自CK Shene教授的课程笔记,这是学习样条曲线和细分曲面的重要资源:

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