为什么Bresenham直线算法比朴素算法更高效？

Question

在我的图形课程中，我们学习了Naive线条光栅化算法和Bresenham线条绘制算法。我们被告知计算机是整数机器，这就是为什么我们应该使用后者的原因。

1. 如果我们假设在软件层面上没有进行任何优化，对于具有MMX和其他指令集的现代CPU来说，这是真的吗？因为我查看了英特尔的64-ia-32-architectures-optimization-manual.pdf，发现对于MMX，浮点数的加减乘法延迟与整数相同或更好。

2. 如果算法在GPU中执行，这会有影响吗？因为我检查了NVIDIA CUDA Programming Guide 1.0 (pdf)，第41页，整数和浮点数的时钟周期相同。

3. 将浮点数转换为整数的效率降低了多少？载入-命中-存储停顿是否是一个真正的问题？

4. 四舍五入数字的函数有多有效？（我们可以考虑C++ STL中的实现）

5. Bresenham算法获得的效率是由于内循环中使用了加法而不是乘法吗？

- Jan Omer

---

在你说GPU之前，先决定一下你是否想要用它来绘制锯齿线。 :) - Henrik Erlandsson

Answer 1

计算机被称为整数机有点误导人，但这种说法大多数情况下是正确的。据我所知，CPU使用整数寄存器来生成内存地址以读取和写入。在线绘制期间，将线条绘制保留在整数寄存器中意味着您避免了从其他寄存器复制到整数寄存器以生成内存地址以写入像素时产生的开销。

至于您的具体问题：

1. 由于需要使用通用目的寄存器来访问内存，在计算内存偏移量（指针）时使用SSE或FPU仍然会有将数据从这些寄存器传输到通用寄存器的开销。因此，它取决于从一个寄存器集转移到另一个寄存器集的开销是否大于使用特定指令集的性能。

2. GPU倾向于拥有统一的寄存器集，因此影响不会太大。

3. 将浮点数强制转换为整数本身不是很耗费资源。开销来自将数据从一组寄存器传输到另一组寄存器。通常必须通过内存完成这项工作，如果CPU存在load-hit-store惩罚，则此传输是其中重要的来源。

4. 舍入上取整或下取整的性能取决于CPU和编译器。在慢的一端，MSVC曾经使用一个函数来进行舍入到零，这会改变FPU控制字。在快的一端，您可以使用直接处理舍入的特殊CPU指令。

5. Bresenham的线段绘制算法之所以快，是因为它将确定在线上绘制点的位置从朴素的y= m*x + b公式简化为加法和分支（通过众所周知的无分支整数技术可以消除分支）。 Brensenham的运行切片版本的线段绘制算法甚至可以更快，因为它直接确定具有相同分量的像素的“运行”，而不是迭代绘制每个像素。

- MSN