问题标签 [bresenham]

我正在使用中点圆算法（也称为 Bresenham 算法）来绘制同心圆。每个圆的半径与下一个圆的半径之差始终为 1，因此最终结果应该是一个完整的圆形区域。

但是，有些像素是空的，如附图所示。

我正在使用 Javascript 在 HTML5 画布上绘画，操作 canvas.getContext("2d").getImageData(...).data 数组。

圆圈交替为白色和红色，空像素为黑色。您可能需要放大才能正确理解我的意思。

我正在尝试向算法添加一些代码，以便在绘制相应的弧线时填充这些像素。这些像素中的任何一个似乎都没有理由属于一个弧而不是下一个，所以我不在乎它们是否与具有偶数半径的弧或具有奇数半径的弧一起填充（我希望我说清楚）。

像素似乎遵循一种模式，但我对那可能是什么一无所知。谁能帮我找到它？

过去一个小时左右我环顾四周，但在这个问题上找不到任何帮助。我正在尝试将此伪代码转换为 java 并且无法弄清楚我做错了什么（它曾经打印过任何东西）。

我的转换是：

有人可以帮忙吗？

对于碰撞测试，我需要光栅一条线。bresenham 算法几乎可以按预期工作，但存在如下缺陷：

我需要：

我当前的实现（基于http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#Simplification）：

有没有我可以使用的其他线光栅化算法，或者有人知道如何修改 bresenham？

使用中点圆算法，您可以绘制对称圆，每个像素只访问一次。由于算法的性质，它只能绘制奇数直径（2 * r + 1）的圆。是否可以扩展此算法，使其可以成功绘制直径为偶数像素的圆？

算法的一些要求：

• 像素只能绘制一次。
• RAM非常昂贵。

如果确实不能修改中点圆算法来处理这个问题，那么下面的解决方案就可以了：

我正在开发第一人称 3D 游戏。关卡完全基于立方体，墙壁/地板/等都只是平铺的立方体（1x1x1）。

我目前正在使用相机位置和相机的旋转来获取方向来创建射线。然后我想将光线投射到第一个不为空的立方体上（或者当光线从网格上掉下来时）。很多时候，这些是方向向量，例如 0,0,1 或 1,0,0。

我在找到适用于方向矢量而不是起点/终点的 Bresenham 线条绘制算法时运气不佳。特别是考虑到方向向量不仅仅包含整数。

所以，对于一个特定的问题，我想我想问是否有人可以解释我是否接近以正确的方式解决这个问题，以及是否有人可能会详细说明无论如何应该如何完成。

Bresenham 的浮点算法中有一些东西让我很恼火。

算法如下：

假设我们要绘制Y=0.6X。因此，在 x=0 的第一步中：错误将设置为 0.6，我们将运行 if 语句并且 y 会增加。并且错误将设置为-0.4。-0.4 将如何帮助我们下一步？

所以我的问题是这行代码：

为什么我们应该将错误减少 1 ？我读过我们这样做是因为重新调整！它对我们有何帮助？

我目前已经为我正在开发的基于图块的世界编辑器实现了 Bresenham 线算法。对于Shift+Click功能，我想根据图块集中的选择矩形渲染一条线。point1这很简单，因为我可以使用算法找到线上的点point2并在每个点处绘制选择。

The issue with this is that the points overlap when the selection rectangle is larger than one tile. 结果如下所示。

我的问题是给出一条线上的所有点，以及选择大小，我怎样才能得到这样的结果？请注意，一旦选择过去，我想停止绘制选择point2。

这是我目前用于渲染线条而不考虑选择大小的内容。

如果您需要我的代码的更多上下文，请发表评论。

Bresenham 有一个众所周知的画线算法，维基百科有很好的关于它的文章：http ://en.wikipedia.org/wiki/Bresenham's_line_algorithm 。

主循环根据需要通过加或减 1 来迭代计算 x 或 y 坐标。

给定 start-point x1、y1、 end-pointx2和y2一些y（y1<= y<= y2），是否可以直接计算xrow 处活动像素的所有坐标y？

例如，假设我使用标准 Bresenham 方法画一条线：

所以为此y我想得到一个[x1+11, x1+12, x1+13].

我不确定是否甚至可以像上面那样修改布雷森汉姆，所以如果事实证明这是不可能的，是否有任何其他方法可以获得看起来与布雷森汉姆计算的序列完全相同的序列？我不在乎它是快还是慢，是否使用浮点数，只要可以直接评估即可。

提前致谢！

编辑：为了能够比较我写了一个简单的参考测试的想法：

打字：

印刷：

我有一个程序，它使用Bresenham 的线算法来扫描一行中的像素。这是读取像素而不是写入像素，在我的特定情况下，读取它们的成本很高。

但是，我可以确定不需要读取某些像素范围。它看起来像这样：

中间的间隙要快得多，因为我可以遍历像素而不读取它们。

但是，我可以以任何方式修改循环，直接在循环内向前跳转 100 个像素，直接在行算法中提前 100 步计算所需的值吗？

我有一个视线问题，我需要通过访问两个（非网格对齐）点之间的 3D 体素空间中的所有可能的单元格来解决。

我考虑过使用 3D Bresenham 算法，但它会跳过一些单元格。

一个天真的实现可能只是以比体素网格更高的分辨率检查沿线的点，但我希望有一个更智能的解决方案。

有人有线索吗？