分形/擾動

快速深度縮放

擾動方法

"我們稱之為擾動 的東西包括兩件事：用高精度計算一個畫素，並將其作為所有其他畫素的參考。

然而，這種方法將會失敗，但是多虧了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