15

我正在尝试实现buddhabrot 分形。我无法理解一件事：我检查的所有实现都在图像上选择随机点来计算粒子逃逸的路径。他们为什么这样做呢？为什么不检查所有像素？

随机点有什么作用？更多的点可以拍出更好的照片，所以我认为遍历所有像素可以拍出最好的照片——我错了吗？

根据我的测试数据：

处理 400x400 图片。因此，如果我全部遍历，则要迭代 160 000 像素。

使用随机抽样，图片只有在 100 万个点后才开始成型。好的结果显示大约 10 亿个随机点，这需要数小时来计算。

4

6 回答 6

32

随机抽样优于网格抽样有两个主要原因。首先是因为网格采样会在生成的图像中引入类似网格的伪影。其次是因为网格采样可能无法为您提供足够的样本来获得收敛的结果图像。如果在完成网格传递后，您需要更多样本，则需要使用稍微偏移的网格进行另一次传递（以免重新采样相同的点）或切换到更精细的网格，这可能最终会做比需要更多的工作. 随机采样提供了非常平滑的结果，您可以在图像收敛或对结果满意后立即停止该过程。

我是这项技术的发明者，所以你可以相信我。:-)

于 2009-09-30T02:07:16.840 回答
3

火焰分形也是如此：Buddha brot 是关于寻找“吸引子”，所以即使你从一个随机点开始，它也会很快收敛到这些吸引曲线。无论如何，您通常会避免在迭代中绘制前 10 个像素左右，因此起点并不真正相关，但是，为了避免两次进行相同的计算，随机采样要好得多。如前所述，它消除了人工制品的风险。

但随机抽样最重要的特点是它具有所有级别的精度（至少在理论上）。这对于分形非常重要：它们具有所有精度级别的详细信息，因此也需要所有级别的输入。

于 2009-10-03T07:15:15.763 回答
1

虽然我不是 100% 知道确切的原因是什么，但我认为这与效率有关。如果您要多次遍历每个点，将浪费大量处理周期来获得可能看起来不会好很多的图片。通过进行随机采样，您可以减少需要完成的工作量 - 并且给定足够大的样本量仍然会获得难以“区分”迭代所有像素的结果（从视觉角度来看）。

于 2009-09-29T14:58:33.507 回答
0

Random sampling is used to get as close as possible to the exact solution, which in cases like this cannot be calculated exactly due to the statistical nature of the problem.

You can 'go over all pixels', but since every pixel is in fact some square region with dimensions dx * dy, you would only use num_x_pixels * num_y_pixels points for your calculation and get very grainy results.

Another way would be to use a very large resolution and scale down the render after the calculation. This would give some kind of 'systematic' render where every pixel of the final render is divided in equal amounts of sub pixels.

于 2014-10-03T18:29:16.377 回答
0

这可能是某种蒙特卡罗方法，所以是的，遍历所有像素会产生完美的结果，但会非常耗时。

你为什么不试试看会发生什么？

于 2009-09-29T15:03:21.660 回答
0

我意识到这是一篇旧帖子，但想根据当前项目添加我的想法。

将样本与像素绑定的问题，就像其他人所说的那样：

  • 将您的示例网格与您的视图平面耦合，使其难以进行投影、缩放等

  • 不够忠实。正如其他人所说，随机抽样更有效，因此如果您想使用统一网格进行抽样，则需要更多样本

  • 您更有可能在相同的样本数下看到网格伪影，而随机采样往往在低计数时看起来很粗糙

但是，我正在开发 buddhabrot 的 GPU 加速版本，并遇到了一些特定于随机采样的 GPU 代码的问题：

  • 我在 GPU 代码中遇到了 PRNG 的开销/质量问题，我需要并行生成数千个样本
  • 随机采样会产生高度分散的轨迹，GPU 真的非常希望给定块/扭曲中的线程尽可能地一起移动。在我的测试中，聚集痕迹与分散痕迹的性能差异非常大
  • 现代 GPU 中对高效 atomicAdd 的硬件支持意味着写入全局内存不会成为 GPU buddhabrot 现在几乎一样多的瓶颈
  • 网格采样使得进行两遍渲染变得非常容易，跳过基于低分辨率遍的采样点块，以找到不会逃逸或从未接触到视图平面中的像素的点

长话短说，虽然 GPU 在技术上必须以这种方式完成更多工作以获得同等质量，但实际上它在 AFAICT 实践中更快，而且 GPU 非常快，以至于重新渲染通常只需几秒/分钟而不是几小时（甚至几毫秒）在较低的分辨率/质量水平下，实时 buddhabrot 非常酷）

于 2021-12-08T23:12:30.000 回答