为什么 Bresenham 直线算法比 Naive 算法更有效
在我的图形课程中，我们学习了 Naive 线光栅化算法，然后是 Bresenham 的线绘制算法。我们被告知计算机是整数机器，这就是为什么我们应该使用后者。
如果我们假设没有软件级别的优化，对于具有 mmx 和其他指令集的现代 CPU 来说也是如此吗？正如我查看过 Intel 的 64-ia-32-architectures-optimization-manual.pdf 一样，与 mmx 的 int 相比，加减乘法的延迟与 float 相同或更好。
如果算法在 GPU 中执行，这会重要吗？已检查NVIDIA CUDA 编程指南 1.0 (pdf)，第 41 页，int 和 float 的时钟周期相同。
将 float 转换为 int 的效率低下是什么？ load-hit-storestall 对我们来说是一个真正的问题吗？
向上/向下舍入数字的函数的效率如何？ （我们可以想到c++ stl中的实现）
- 内循环中使用的乘法
For my graphics course we were taught the Naive line rasterizing algorithm then Bresenham's line drawing algorithm. We were told computers are integer machines which is why we should use the latter.
If we assume no optimization on software level is this true for modern cpus with mmx and other instruction sets ? As I have looked at Intel’s 64-ia-32-architectures-optimization-manual.pdf and the latency for addition subtraction multiplication is the same or better for float compared to int for mmx.
If the algorithm is executed in the gpu should this matter ? As having checked NVIDIA CUDA Programming Guide 1.0 (pdf), page 41, the clock cycles for int and float are the same.
What is the de-efficiency of casting float to int? is load-hit-store stall a real issue for us?
How efficient are functions which round up/down numbers? (we can think of the implementation in c++ stl)
Is the efficiency gained from Bresenham algorithm due to addition instead of the multiplication used in the inner loop?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
将计算机称为整数机器有点误导，但这种观点大多是正确的。据我所知，CPU 使用整数寄存器来生成要读取和写入的内存地址。将线条绘制保留在整数寄存器中意味着您可以避免从其他寄存器复制到整数寄存器以生成线条绘制期间写入像素的内存地址的开销。
至于您的具体问题：
It's a little misleading to call computers integer machines, but the sentiment is mostly true. Since as far as I know, CPUs use integer registers to generate memory addresses to read from and write to. Keeping line drawing in integer registers means you avoid the overhead of copying from other registers into integer registers to generate the memory address to write pixels to during line drawing.
As for your specific questions:
y= m*x + bformula to an addition plus a branch (and the branch can be eliminated through well know branchless integer techniques). The run-slice version of Brensenham's line drawing algorithm can be even faster as it determines "runs" of pixels with the same component directly rather than iterating.