分形/扰动

快速深度缩放

扰动方法

"我们称之为扰动 的东西包括两件事：用高精度计算一个像素，并将其作为所有其他像素的参考。

然而，这种方法将会失败，但是多亏了Pauldelbrot，我们有一种可靠的方法来检测参考未能以硬件精度计算像素的像素。这些像素可以用更靠近这些像素的参考来渲染，因此典型的扰动渲染使用多个参考。这种方法在 10^100 的深度上大约可以提高 10 倍的速度。使用截断的泰勒级数来近似特定迭代的起始值，这样就可以跳过所有以前的迭代。这种方法在 10^100 的深度上通常可以再提高 10 倍的速度，两者加起来通常可以提高 100 倍的速度。我们称之为级数近似，这里存在问题，因为我们没有任何可靠的理论方法来找出何时跳过了过多的迭代 - 对于视图中的所有像素。你在泰勒级数中包含的项越多，你能够跳过的迭代就越多。所以如果你保持在 50 项以下，你不太可能遇到任何问题。因为一些视图可以比每个像素的完全精度快 1000 或 100,000 倍地正确渲染，而且包含了许多项 - 你能想象一个月变成几秒钟吗！震惊 K.I.Martin 最初只使用 3 项 " - Kalles Fraktaler

描述

高度放大的图像需要超过大多数硬件浮点单元提供的标准 64-128 位的精度，要求渲染器使用缓慢的 "bignum" 或 "任意精度" 数学库来计算。然而，这可以通过利用扰动理论 来加速。鉴于

$z_{n+1}=z_{n}^{2}+c$

作为迭代，以及一个小epsilon，这种情况是

$(z_{n}+\epsilon )^{2}+c=z_{n}^{2}+2z_{n}\epsilon +\epsilon ^{2}+c$

或者

$z_{n+1}+2z_{n}\epsilon +\epsilon ^{2}$

所以如果定义

$\epsilon _{n+1}=2z_{n}\epsilon _{n}+\epsilon _{n}^{2}$

可以使用正常的、高精度算术 (z) 计算单个点（例如，图像的中心），从而得到一个参考轨道，然后根据各种初始偏移 epsilon-zero 加上 epsilon 的上述迭代来计算围绕它的许多点。对于大多数迭代，epsilon 不需要超过 16 位有效数字，因此可以使用硬件浮点来获得基本上准确的图像。 通常会有一些区域，其中点的轨道与参考轨道之间的偏差足够大，以至于这些点需要额外的精度，否则需要额外的局部高精度计算的参考轨道。这种渲染方法，特别是对额外参考轨道需求的自动检测以及对参考轨道的最佳选择，是一个正在进行的、活跃的研究领域。实现该技术的渲染器是公开可用的，并且在高度放大的图像中提供数量级的速度提升。

牛顿-拉夫森缩放

可以使用 "牛顿方法来找到并逐步改进模式中心的迷你分形的精度。这允许他们任意选择他们开始的位置和他们计算出的位于该位置中心的最终迷你分形的放大倍数。"

故障

故障

扰动方法中的故障 如何检测故障

• Pauldelbrot 开发的启发式方法 (最常见)
• 使用区间算术开发的启发式方法，由 knighty 开发

如何选择参考点 (由 Claude)

• 简单方法："将第一个参考设置为图像的中心，并纠正由此产生的任何故障 (包括参考过早逸出的故障) ，方法是在故障内添加更多参考，仅重新计算需要它的那些像素。简单的方法仍然可以产生准确的结果，尽管速度并非最优。"
• "尝试周期点 (迷你分形岛屿深处的核) 和前周期点 (螺旋中心的 Misiurewicz 点)，它们都可以通过牛顿方法找到 (找到它们的 (前) 周期有点难，但并非不可能)。周期较高的 "结构性" 迷你分形核似乎是最受欢迎的，因为它们相对容易找到，同时发出比周期较低的核更少的故障像素"

Claude 提出的故障类型： 1. 参考过早逸出，这种类型可以通过选择一个不会逸出的参考来避免 2. 动力学过于不同 (通过 Pauldelbrot 的启发式方法可以轻松检测到，通过 gerrit 的后向误差分析可以准确检测到，认为 knighty 还有另一种方法)。

类型 1 可以通过选择一个随机的故障像素作为新的参考并重试来改进

类型 2 有时可以通过使用故障迭代时具有最小 |z| 的像素来修复（可能使用牛顿法的一步导数使其更接近最小集），但通常选择随机像素效果一样好 - 最小 |z| 的优势在于曼德勃罗集，你不需要从头开始重新迭代，因为最小集是通过 0 周期的，周期是故障迭代（我在我的 mandelbrot-perturbator 中使用这个）

KF 使用一种我不太理解的算法，根据像素区域找到“故障中心”，但也提供了随机选择和最小 |z| 的选项（没有 mandelbrot-perturbator 中的花哨的东西）。位置

• “在非常深的缩放级别下，在 -2+0i 附近的一个微型勃罗特，你很可能会得到一个莫尔星状的混乱，而不是同心光线环（因为光线将被规则地间隔开，比像素间距更精细，从而导致干涉）。"

Knighty's SMB which I think is still a bit faster than KF though being more of a testbed than a usable renderer puts the glitches in distinct sets (G1,.., Gn) with same iteration number where glitch was detected. Next references will then be 1 random pixel from each of the G1,..,Gn and is used only to recalculate the pixels in each set G. Secondary glitches simply generate another set G and you just put then in some queue or stack and keep going at it till no more G sets left. When dealing with glitched pixels you can use the same series expansion as a starting point. ( Gerrit)

重新基准

重新基准 意味着当像素轨道（即 Z+z ，参考值加上增量）接近临界点（如曼德勃罗集的 0+0i）时，将参考迭代重置为开始。如果有多个临界点，则需要从每个临界点开始的参考轨道，并且此测试可以切换到不同的参考轨道。对于这种情况，在当前迭代的参考轨道和迭代次数为 0 的临界点轨道中，选择最小化 |(Z−Zo)+z| 的轨道 o。重新基准意味着你只需要与临界点一样多的参考轨道（对于像曼德勃罗集和燃烧船这样的简单公式，意味着只有一个），并且避免了故障，而不是检测到故障，需要在以后进行校正。这对效率（很好）和正确性（更重要）来说是一个很大的提升。

效果

• 效果

使用级数近似的扰动算法（在 e100 左右的缩放级别上快 100 倍！）

精度

对于更深的缩放，有 3 个选项：

• double/float64（直到 e300 左右，一些硬件的性能比 float32 大大降低）
• float32 + 分离的 int32 指数（“floatexp”）（或者 int16 可以用于中间缩放，直到 e9800 左右）
• 完全软件浮点数（两个 uint32，一个用于尾数，另一个用于符号和指数）
• prec = 53 - log2(view_radius)) 另见代码：code.mathr.co.uk/fractal-bits/mandelbrot-perturbation-error/mandelbrot-perturbation-error.c

历史

• 2 个独立的描述 
  • 由 Sergey Khashin 编写的具有无限分辨率的快速曼德勃罗集（2011 年 7 月 9 日）
  • 由 K.I. Martin 编写的扰动方法（2013-05-18）（仅使用 3 个级数近似项）
• Pauldelbrot 的故障检测方法
• 由 Claude Heiland-Allen 扩展 Martin 的描述以处理内部距离估计

程序

• 由 K.I. Martin 编写的 SuperFractalThing（用 Java）
• 由 Claude Heiland-Allen 编写的 mightymandel
• 由 Claude Heiland-Allen 编写的 mandelbrot-perturbator : http://code.mathr.co.uk/mandelbrot-perturbator/
• persianney : fractalNotes.pdf
• 适用于 Windows 的 Kalles Fraktaler
• perturbation_algebra 和 et
• 交互式 SageMath 工作表，解释它是如何工作的，尝试更改公式
• FractalZoomer
• 由 ShiromMakkad 编写的 MandelbrotPerturbation

比较

• 抛物线扰动
• 参考压缩算法

参考文献

• 2021-05-14 深度缩放理论与实践，作者：Claude
• 2022-02-21_deep_zoom_theory_and_practice_again
• m-perturbation