使用最少的整数数学渲染图形函数，可驱动 CNC

• 下载源代码 - 383.8 KB

引言

本文描述了一种使用整数运算和极少量操作来渲染二维和三维数学函数的算法。

算法的描述从更简单的二维版本开始，然后扩展到三维。

提供的代码面向 CNC 机床和 3D 打印机，以及在屏幕上表示 2D 原始图形。

包含一个演示程序，可以主动解释算法的运行过程。

算法

我们要利用的是一个非常简单的原理。在一个像素化的世界里，除了像素本身是用整数表示之外，连续函数下一个要绘制的点只能是相邻的像素之一。这限制了候选点的数量为 8。如果我们再加上曲线的方向，这由前一个绘制点决定，那么候选点的数量就减少到 5。这里所做的是计算这 5 个可能的候选点的函数值，选择最佳的一个，然后重复这个过程，直到到达要表示的曲线的终点。

我们这里要利用的是，与传统数学追求精确值不同，该算法只关心模糊的误差，这简化了公式，避免了使用 float，并省去了复杂的运算。

例如，要找到圆的下一个点，我们必须在每个可能的候选点上计算

error ~= x*x + y*y - r*r

其中 x 和 y 是候选点的坐标，r 是圆的半径。

这意味着每个候选点需要三次乘法和两次整数加法，最重要的是，它避免了平方根和除法。

通过使用 codlets，支持新功能只需几行代码。octant.c 文件的头部显示了这一点

经典与像素化数学

我理解经过数百年发展的数学已被用于在粗糙（或像素化）的笛卡尔坐标系中渲染原始图形，但存在细微的差别。

在传统数学中，诸如圆或直线之类的函数由满足特定条件的无限点集组成，即它们是笛卡尔平面的一部分，甚至可能由多个实体构成。

相比之下，光栅化函数是截然不同的。它是一个有限的点集，这些点彼此相关，其中最重要的就是 顺序。

我认为它们在视觉上看起来相同可能导致了混淆。从连续世界过渡到离散世界需要类似于音频系统的模数转换。

演示程序

这是一个 code::blocks 项目，但由于没有依赖项，我包含了 64 位可执行文件。
它具有绘制直线和圆的能力，扩展到其他原始图形也很简单。只有三个文件，因此移植到另一个 IDE 可能是一项轻松的任务。

demo.exe 是可执行文件。

通过键盘使用。有简单的帮助。在左下角，算法相关的 9 个像素显示在一个 3x3 的网格中，对于每个计算出的像素（每次迭代计算 5 个），都会显示函数的误差。系统将选择误差最小的一个作为下一个点。

要使用它，我们必须按下 'x'，这将重启系统。
要开始绘制圆，请按 'c'。要绘制直线，请按 'l'。系统会一个接一个地放置原始图形。请记住，该系统是面向 GCODE 的。
使用 'n' 键，系统将根据屏幕左下角的值计算并绘制下一个点。这是主要的学习键。
按 's' 键可以在屏幕上切换显示信息，内容是在绘制顺序和 CNC 主轴指向的方向之间切换。

使用原始图形

这是圆的原始图形，其中心相对于当前点是相对的

int circleGuess( int * center, int x, int y )  /* x^2 + y^2 - r^2  ~= 0 */
{ x -= center[ 0 ];
  y -= center[ 1 ];

  return( x*x + y*y
        -  ( center[ 0 ] * center[ 0 ] ) 
        -  ( center[ 1 ] * center[ 1 ] ) );
}

每次调用 nextPoint 时，ptCur 都将更新

int params[ 2 ]= { x, y };  // x and y passed as parameters to the function

ptCur= nextPoint( circleGuess, params
                , ptCur.heading
                , ptCur.x, ptCur.y );

就是这么简单吗？这是事件驱动编程，因此可读性较差。尽管如此，添加新的原始图形也很容易。第一个参数是指针，其中包含函数所需的参数（二次贝塞尔曲线比圆需要更多参数），另外两个参数是待测试的点。ptCur 保存当前指针以及曲线的朝向。

正如承诺的，只使用了整数加法和乘法。

现在，三维

在三维版本中，事情变得复杂了。二维版本中使用的简单 3x3 像素正方形变成了 3x3x3 的“魔方”，并且为了找到下一个点而进行的导航必须考虑更多的选项。然而，我提供了功能代码，以便可以包含它。只需说这是二维代码的扩展，并使用查找表来简化计算。

Route3d.exe 演示了三维线段的渲染。
gcode.exe 使用该算法从 gcode 渲染一个硬编码的对象（wheel.c）到步进电机运动。

它曾经工作过吗

答案是肯定的

stm32 nucleo 未存在。

未来

此算法可以简化两个典型问题。最重要的是在 CNC 路由器上使用旋转工具。

该算法可以大大简化 CNC 路由器在切割零件时对刀具半径的“计数”，以及行进路径。如果感兴趣，我将发布相关代码。

另一个是屏幕渲染的“廉价”抗锯齿。通过获取不同像素的误差值，可以根据误差率对颜色进行比例分配。

历史

• 2023 年 6 月 30 日：初始版本