Mandelbrot 집합의 플롯 알고리즘

이것은 교과서의 어조나 문체가 위키백과에서 사용되는 백과사전의 어조를 반영하지 못할 수도 있다는 것과 같다. 제안사항은 위키피디아의 더 나은 기사 작성 안내서를 참조하십시오.(2021년 7월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

Mandelbrot 세트와 다른 프랙탈을 플로팅하는 데 사용되는 많은 프로그램과 알고리즘이 있으며, 그 중 일부는 프랙탈 생성 소프트웨어에 설명되어 있다.이러한 프로그램들은 개별 픽셀의 색상을 효율적으로 결정하기 위해 다양한 알고리즘을 사용한다.

탈출 시간 알고리즘

맨델브로트 집합의 표현을 생성하기 위한 가장 간단한 알고리즘은 "탈출 시간" 알고리즘으로 알려져 있다.반복 계산은 플롯 영역의 각 x, y 지점에 대해 수행되며, 해당 계산의 동작에 기초하여 해당 픽셀에 대해 색상이 선택된다.

최적화되지 않은 navve 탈출 시간 알고리즘

최적화되지 않고 최적화된 탈출 시간 알고리즘에서 각 점의 x와 y 위치는 반복 또는 반복 계산에서 시작 값으로 사용된다(아래에 자세히 설명됨).각 반복의 결과는 다음 반복의 시작 값으로 사용된다.이 값은 반복할 때마다 점검하여 위험 "탈출" 또는 "배출" 상태에 도달했는지 여부를 확인한다.그 조건에 도달하면 계산이 중지되고 픽셀이 그려지며 다음 x, y 포인트를 검사한다.일부 시작 값의 경우, 적은 횟수의 반복 후에 탈출이 빠르게 발생한다.세트에서 매우 가깝지만 그렇지 않은 시작 값의 경우, 탈출하는 데 수백 또는 수천 번의 반복이 필요할 수 있다.Mandelbrot 집합 내의 값의 경우 탈출은 절대 발생하지 않는다.프로그래머나 사용자는 그들이 검토하기를 원하는 반복 횟수 또는 "깊이"를 선택해야 한다.최대 반복 횟수가 많을수록 최종 영상에서 디테일과 미묘함이 나타나지만 프랙탈 영상을 계산하는 데 시간이 더 오래 걸린다.

탈출 조건은 간단하거나 복잡할 수 있다.실제 또는 가상 부분이 2보다 큰 복잡한 숫자는 세트의 일부가 될 수 없기 때문에 일반적인 구제금융은 어느 한 계수가 2를 초과할 때 탈출하는 것이다.좀 더 계산적으로 복잡한 방법으로 탈출을 더 빨리 감지하는 방법은 피타고라스 정리, 즉 복합수의 절대값, 즉 계수를 결정하여 원점으로부터의 거리를 계산하는 것이다.실제 부분과 가상 부분의 제곱합이 4를 초과할 때 이 값이 2를 초과하거나 동등하게 되면 그 지점은 탈출에 도달한 것이다.보다 계산적으로 집약적인 렌더링 변형에는 탈출점을 찾아 반복 좌표를 그리는 부처브로트 방법이 포함된다.

각 점의 색은 값이 탈출점에 얼마나 빨리 도달했는지를 나타낸다.종종 검은색은 반복 한계 이전에 빠져나가지 못하는 값을 나타내기 위해 사용되며, 점차 밝은 색상은 탈출하는 포인트에 사용된다.이것은 탈출 조건에 도달하기 전에 얼마나 많은 사이클이 필요했는지 시각적으로 보여준다.

그러한 이미지를 렌더링하기 위해 우리가 고려하고 있는 복잡한 평면의 영역은 일정한 픽셀 수로 세분된다.이러한 픽셀의 색상을 지정하려면 $c{\displaystyle }$ ${\displaystyle c}$을(를) 해당 픽셀의 중간점으로 설정하십시오$$.이제 각 단계에서 궤도 지점이 2보다 큰 계수를 가지고 있는지 확인하면서$$$P{\displaystyle {}_{}}$ ${\displaystyle c_{}}$ ${\$ 아래에 임계 지점 0을 반복한다.이럴 때 $c{\displaystyle }$ ${\displaystyle c}$이(가) 맨델브로트 세트에 속하지 않는다는$$ 것을 알고, 우리는 알아내기 위해 사용한 반복 횟수에 따라 픽셀에 색칠을 한다.그렇지 않으면, 우리는 정해진 수의 스텝까지 반복하고, 그 후에 우리는 우리의 파라미터가 만델브로트 세트에서 "가능성" 또는 적어도 그것과 아주 가까운 곳에 있다고 판단하고 픽셀을 검은색으로 색칠한다.

유사 코드에서 이 알고리즘은 다음과 같이 보일 것이다.알고리즘은 복잡한 숫자를 사용하지 않고 복잡한 데이터 유형을 가지고 있지 않은 사람들을 위해 두 개의 실제 숫자를 사용하여 복잡한 숫자 연산을 수동으로 시뮬레이션한다.프로그래밍 언어가 복잡한 데이터 유형 연산을 포함하는 경우 프로그램을 단순화할 수 있다.

화면에 각 픽셀(기흉, Py) 들어니 x0:=픽셀(그 맨들 브로트 X스케일에 눕는 기어 올라가(-2.00에서 0.47))y0의 좌표 x:)y 픽셀(그 맨들 브로트 Y규모에 눕는 기어 올라가(, 1.12-1.12)의 좌표 조정 기어 올라가)x:=0.0는 y:=0.0반복:=0max_iteration:=1000는 동안(x*x+y*y ≤ 2*2 및 반복<>어머니.x_iteration) do xtemp := x*x - y*y + x0 y := 2*x*y + y0 xtemp 반복 := 반복 + 1 colority := 팔레트[iteration] 플롯(Px, Py, color)

여기서 유사 코드를 $c{\displaystyle }$ ${\displaystyle c$ $z{\displaystyle }$ ${\displaystyle z}$ 및 ${\displaystyle P_{}}$ c ${\$에$$관련 :

• $(\displaystyle z=x+iy\ }$
• ${\displaystyle z^{}}$ ${\displaystyle {2\mathrm{}}^{}}$= x ${\displaystyle {2\mathrm{}}^{}}$+ 2 ${\displaystyle i}$ ${\displaystyle y}$ ${\displaystyle z^{2}=x^{2}+2ixy}$ $$- ${\displaystyle {y\mathrm{}}^{}}$ $2{\displaystyle {}^{}}$ $displaystyle$ y$^{2}\}$
• ${\displaystyle c=x_{0}+iy_{0}\ }$

따라서 x와 y의 계산에서 가성 코드에서 볼 수 있듯이:

• ${\displaystyle x=\mathop {\mathrm {Re} } (z^{2}+c)=x^{2}-y^{2}+x_{0}}$ and ${\displaystyle y=\mathop {\mathrm {Im} } (z^{2}+c)=2xy+y_{0}.$$\ }$

세트의 다채로운 이미지를 얻기 위해 실행된 반복 횟수의 각 값에 색상을 할당하려면 다양한 기능(선형, 지수 등) 중 하나를 사용하여 수행할 수 있다.계산을 늦추지 않고 실행된 반복 횟수를 시작 시 초기화된 팔레트에 대한 항목으로 사용하는 것이 한 가지 실용적인 방법이다.예를 들어, 색상표에 500개의 항목이 있는 경우, 색상 선택 항목은 n mod 500이며, 여기서 n은 반복 횟수임.

최적화된 탈출 시간 알고리즘

앞 절의 코드는 명확성을 위해 최적화되지 않은 내측과 루프를 사용한다.최적화되지 않은 버전에서는 반복당 5회의 곱셈을 수행해야 한다.곱셈의 수를 줄이기 위해 루프를 사용하는 동안 내측에 대해 다음과 같은 코드를 대신 사용할 수 있다.

x2 := 0 y2 := 0, (x2 + y2 ≤ 4 및 반복 <max_iteration) x := x := x2 - y2 + x0 y := w - x2 - y2 + y2 := x x x x2 := y : (x + y) x (x + y) × (x + y) 반복 : 1을 한다.

위의 코드는 복잡한 곱셈의 대수적 단순화를 통해 작동된다.

${\displaystyle {\displaystyle}(iy+x)^{2}}&=-y^{2}+2iyx+x^{2}}\\&=x^{2}-y^{2}+2iyx\ended}}}$

위의 아이덴티티를 이용하면 5개가 아닌 3개로 승수를 줄일 수 있다.

위와 같은 내측과 루프는 w로 확장하여 더욱 최적화할 수 있다.

${\displaystyle w=x^{2}+2xy+y^{2}}}$

w를 $y$로 대체 =${\displaystyle w}$- ${\displaystyle {x\mathrm{}}^{}}$ ${\displaystyle {}^{}}$- y ${\displaystyle {2\mathrm{}}_{}{}^{}}$+ y ${\displaystyle {}_{}}$ ${\$$}}$ $수율$ y = ${\displaystyle 2}$ ${\displaystyle x}$y + y ${\displaystyle {0\mathrm{}}_{}}${\$displaystyle$y=$2xy+y_{0}}$이므로 w 계산은 더 이상 필요하지 않다.

상기에 대해 더욱 최적화된 유사성 부호는 다음과 같다.

x2 := 0 y2 := 0, (x2 + y2 ≤ 4 및 반복 <max_iteration) y := 2 x x x x × y + y0 := x2 - y2 + x0 x 2 := x x x x 2 : = y × 반복 := 1

위의 유사 코드에서 $2{\displaystyle \mathrm{}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle 2xy}$이(${\displaystyle 가}$) 승수 수를 1 증가시키는 것처럼 보이지만$$, 2가 ${\displaystyle \mathrm{승수}}$이기 때문에 (${\displaystyle }$x${\displaystyle }$+${\displaystyle x}$ ) y$${\$displaystyle (x+x)y}$를 통해 코드를 최적화할 수 있다$.$

컬러링 알고리즘

세트를 플롯하는 것 외에도, 세트를 미적으로 기분 좋게 효율적으로 색칠할 수 있는 다양한 알고리즘이 개발되었다.

히스토그램 색상

이 섹션은 검증을 위해 추가 인용구가 필요하다. 관련 토론은 토크 페이지에서 찾을 수 있다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다.(2019년 6월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

보다 복잡한 컬러링 방법은 각 픽셀을 탈출/구제 전에 해당 픽셀의 최대 반복 횟수와 짝을 이루는 히스토그램을 사용하는 것을 포함한다.이 방법은 동일한 전체 영역에 색상을 균등하게 분배하며, 중요한 것은 선택한 최대 반복 횟수와 무관하다.^[1]

이 알고리즘은 4개의 패스를 가지고 있다.첫 번째 패스는 각 픽셀과 관련된 반복 횟수를 계산하는 것이다(그러나 어떤 픽셀도 플로팅되지 않음).이들은 IterationCounts[x][y]라고 하는 배열로 저장되며, 여기서 x와 y는 각각 해당 픽셀의 x와 y 좌표 입니다.

맨 위 행은 각각 픽셀당 10000, 1000 및 100개의 최대 반복에 대한 탈출 시간 알고리즘을 사용하는 일련의 플롯이다.맨 아래 행은 동일한 최대 반복 값을 사용하지만 히스토그램 색상 방법을 사용한다.히스토그램 색상 방법 그림에서 다른 최대 반복 횟수에 따라 색상 변화가 얼마나 적은지 확인하십시오.

두 번째 패스의 첫 번째 단계는 최대 반복 카운트인 n 크기의 배열을 만드는 것이다.NumIterationsPerPixel이라는 어레이를 다음으로 픽셀 반복 카운트 쌍의 어레이인 IterationCounts[][]에 반복하고 각 픽셀의 저장된 반복 카운트를 예를 들어, i = IterationCounts[x][y]를 통해 검색해야 한다.각 픽셀의 반복 횟수 i를 검색한 후에는 numItreationsPerPixel을 i로 인덱싱하고 인덱스 값(처음에는 0임)을 증가시켜야 한다.NumITerationsPerPixel[i] = NumITerationsPerPixel[i] + 1 .

(x = 0; x < 너비; x++)에 대해 (y = 0; y < 높이; y++) i := IterationCounts[x][y] NumIterationsPerPixel[i]++) 수행

세 번째 통과는 NumItreationsPerPixel 어레이를 통해 반복되며 저장된 모든 값을 합산하여 총계적으로 저장된다.어레이 지수는 구제금융 전에 반복 카운트에 도달한 픽셀 수를 나타낸다.

총 := 0 (i = 0; i < max_iterations; i++) 총 작업 += NumIterationsPerPixel[i]

이후 네 번째 패스가 시작되고 IterationCounts 어레이의 모든 값이 인덱싱되며, 각 픽셀과 연결된 각 반복 카운트 i에 대해 카운트는 NumIterationsPerPixel 어레이에서 1부터 i까지의 모든 반복 카운트의 전역 합에 추가된다.이 값은 합계를 앞에서 계산한 총값으로 나누어 정규화한다.

hue[][] := 0.0 for (x = 0; x < width; x++) do for (y = 0; y < height; y++) do         iteration := IterationCounts[x][y]         for (i = 0; i <= iteration; i++) do             hue[x][y] += NumIterationsPerPixel[i] / total /* Must be floating-point division. */ ... color = 팔레트[m, n] ... 

마지막으로, 계산된 값은 색상 팔레트에 대한 색인으로 사용된다.

이 방법은 보다 미적으로 만족스러운 이미지를 위해 아래의 부드러운 색칠 방법과 결합할 수 있다.

연속(매끄러운) 컬러링

이스케이프 타임 알고리즘은 단순성으로 인기가 있다.그러나, 그것은 일종의 앨리어싱으로서 이미지의 미적 가치를 떨어뜨릴 수 있는 색깔의 띠를 만든다.이는 "정상화된 반복 횟수"^[2][3]라고 알려진 알고리즘을 사용하여 개선할 수 있으며, 이 알고리즘은 반복 간의 색상의 원활한 전환을 제공한다.알고리즘은 반복 번호와 잠재적 함수의 연결을 사용하여 실제 숫자 $\nu {\displaystyle }$ ${\displaystyle \nu }$을(를) z의 각 값과$$ 연결한다.이 기능은 다음에 의해 주어진다.

${\displaystyle \phi(z)=\lim _{n\to \infit }(\log z_{n} /P^{n}),}$

여기서 z는_n n번 반복 후 값이고 P는 mandelbrot 세트 방정식(z_n+1 = z_n^P + c, P는 일반적으로 2)에서 z가 상승하는 힘이다.

대규모 구제금융 반경 N(예: 10¹⁰⁰)을 선택한다면, 우리는 그런 것을 갖게 된다.

${\displaystyle \log z_{n} /P^{n}=\log(N)/P^{\nu(z)}}}$

일부 실제 $번호{\displaystyle }$ ${\displaystyle (}$ (${\displaystyle z}$ )$${\$displaystyle \nu (z$의 경우,

${\displaystyle \nu(z)=n-\log _{P}(\log z_{n} /\log(N)),}$

그리고 n은 z_n > N과 같은 첫 번째 반복 번호로서, n에서 빼는 숫자는 간격 [0, 1]에 있다.

색상의 경우 주기적인 색상 척도(예를 들어 수학적으로 구성)가 있어야 하며 0에서 H - 1(예: H = 500) 사이의 H 색상을 포함해야 한다.실제 숫자 $\nu {\displaystyle }$( $){\displaystyle \nu (z)}$에 사진 속 색의 밀도를 결정하는 고정된 실제 숫자를 곱하여 이 숫자 modulo H의 적분 부분을 취하여 색상표에서 해당 색상을 찾는 데 사용한다.

예를 들어, 위의 가성형을 수정하고 선형 보간 개념을 사용하게 되면

for each pixel (Px, Py) on the screen do     x0 := scaled x coordinate of pixel (scaled to lie in the Mandelbrot X scale (-2.5, 1))     y0 := scaled y coordinate of pixel (scaled to lie in the Mandelbrot Y scale (-1, 1))     x := 0.0     y := 0.0     iteration := 0     max_iteration := 1000     // Here N = 2^8 is chosen as a reasonable bailout radi우리. x*x+y*y ≤(1<><>16)와 반복<>max_iteration니 xtemp:)x*x-y*y+x0는 y:=2*x*y+y0 x:=xtemp 반복:)반복+1// 사용되지 않도록 부동 소수 점 문제로 점수 안에 집합입니다. 만약 반복<>max_iteration 다음//sqrt의 내항을 제거를 사용하여 로그 단순화 지내.쒸르.log_zn := log(x*x + y*y) / 2 nu := log(log_zn / log(2) //전위함수 재배열// 구제 반경이 아닌 // 전체 팔레트를 // 중심에서 반경 2까지 범위가 되도록 하기 때문에 로그(N = 1<8) // 대신 로그(2)로 나누는 것.반복 :==반복 + 1 - nu color1 := 팔레트[바닥(반복)] 색2 := 팔레트[바닥(반복) + 1] //반복 % 1 = 반반복의 부분.color := linear_interpolate(color1, color2, 반복 % 1) 플롯(Px, Py, color)

고급 플로팅 알고리즘

이미 논의된 간단하고 느린 탈출 시간 알고리즘 외에도, 플로팅 프로세스의 속도를 높이는 데 사용할 수 있는 더 많은 고급 알고리즘이 있다.

거리 추정치

만델브로트 집합의 경계에서 c 지점(외부 또는 내부)에서 가장 가까운 지점까지의 거리를 계산할 수 있다.^[4]

외부 거리 추정

$실제로{\displaystyle }$ 만델브로트 집합의 연결성에 대한 증거는 M ${\displaystyle M}($및 이 맵의 파생 모델)의 보완 지도의 통일화 공식을 제공한다.코에베 쿼터 정리에 의해, 우리는 우리 픽셀의 중간점과 4배수로 설정된 맨델브로트 사이의 거리를 추정할 수 있다.

즉, 최대 반복 횟수가 충분히 높은 경우, 다음 특성을 가진 만델브로트 세트의 사진을 얻는다.

1. 만델브로트 세트의 한 점을 담은 픽셀은 모두 검은색으로 칠해져 있다.
2. 검은색으로 칠해진 모든 픽셀은 만델브로트 세트에 가깝다.

Mandelbrot 세트에서 픽셀 c(복잡한 숫자)의 거리 추정치에 대한 하한 b는 다음과^[5][6] 같다.

${\displaystyle b=\lim _{n\to \inflat }{{p_{c}^{n}(c) \cdot \ln {P_{c}^{n}}}}}{2}{\frac {\partial {c}{c}}}^{n}}}}}},}}}}}}}}}}},}}}}}}}}}}}}}}}}}}}}}},},},},},},},},},}$

어디에

• ${\displaystyle P_{}}$ ${\displaystyle c_{}}$( ${\displaystyle z}$) ${\$은(는) 복합 2차 다항식을 의미한다$$.
• ${\displaystyle P_{c}^{n}(c)}$ stands for n iterations of ${\displaystyle P_{c}(z)\to z}$ or ${\displaystyle z^{2}+c\to z}$, starting with ${\displaystyle z=c}$: ${\displaystyle P_{c}^{0}(c)=c}$, ${\displaystyle P_c^{n+1}(c)=P_c^n(c}$${\displaystyle P_{c}^{n+1}(c)=$$P_{c}^{n}(c)^{2}+c}$;
• ${\displaystyle \frac{\mathrm{\partial }}{}}$ ${\displaystyle \frac{\partial \mathrm{}}{}}$ ${\displaystyle \frac{c}{}{}_{}^{}}$ ${\displaystyle c{}_{}^{}}$( c${\displaystyle }$) ${\displaystyle {\frac {\partial }{\c}P_{c}^{n}(c)}}$은 c에 $대한$ ${\displaystyle P_{}^{}}$ ${\displaystyle {}_{}^{}}$ ($){\displaystyle P_{c}^{n}(c)}$의 파생어다$$.This derivative can be found by starting with ${\displaystyle {\frac {\partial }{\partial {c}}}P_{c}^{0}(c)=1}$ and then ${\displaystyle {\frac {\partial }{\partial {c}}}P_{c}^{n+1}(c)=2\cdot {}P_{c}^{n$$}}(c)\cdot {\frac {\partial }{\partial {c}P_{c}^{n}(c)+1$}$$.이것은 파생상품에 대한 체인 룰을 사용하면 쉽게 검증할 수 있다.

이 공식의 이면에 있는 아이디어는 간단하다.When the equipotential lines for the potential function ${\displaystyle \phi (z)}$ lie close, the number ${\displaystyle \phi '(z) }$ is large, and conversely, therefore the equipotential lines for the function ${\displaystyle \phi (z)/ \phi '(z) }$ should lie approxima규칙적으로

수학자의 관점에서 이 공식은 n이 무한대로 가는 한계에서만 작동하지만, 주 루프가 나간 후 몇 번의 추가 반복만으로 매우 합리적인 추정치를 찾을 수 있다.

코에베 1/4 테오렘은 거리 추정치의 하한 b를 계산하는 데 사용된다.^[7]상한 B = 2b의 계산에 대한 유사 코드 예를 여기서 볼 수 있다.^[8]좌표계에 설정된 만델브로트의 지도와 비교해 보면, 상한 B = 2b가 실제 거리를 약 2배 초과한다는 것을 알 수 있다.sinh 함수를 추정할 때의 오류로 인해 B = 4b(B = 2b가 아닌)가 정확한 상한(하한 b는 공식에서 잊혀진 인자 2 덕분에 여전히 정확함)으로 보인다.^[5]어느 경우든 하한 b가 더 나은 거리 추정치가 된다.

거리 추정은 만델브로트 집합의 경계를 그리는 데 사용될 수 있다. 줄리아 집합 기사를 참조하라.이 접근법에서는 M에 충분히 가까운 픽셀을 다른 색상을 사용하여 그린다.이것은 만델브로트 세트의 얇은 "필라멘트"를 쉽게 볼 수 있는 도면을 만든다.이 기법은 '프랙탈의^[9] 미학'과 '프랙탈 이미지의 과학'이라는 책에 나오는 만델브로트의 B&W 영상에 좋은 영향을 미치기 위해 사용된다.^[10]

다음은 거리 추정치를 사용하여 렌더링한 샘플 B&W 이미지:

거리 추정을 사용하여 Mandelbrot 및 Julia 세트의 3D 영상을 렌더링할 수도 있음

내부 거리 추정

만델브로트 집합의 경계까지 한계 주기적(즉, 쌍곡선) 점의 거리를 추정할 수도 있다.거리 추정치의 하한 b는 다음과 같다^[4].

${\displaystyle b={\frac {1-\left {{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})}\right ^{2}}{4\left {{\frac {\partial }{\partial {c}}}{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})+{\frac {\partial }{\partial {z}}}{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0}){\frac {{\frac {\partial }{\partial {c}}}P_{c}^{p}(z_{0})}{1-{\frac {\partial }{\partial{z}}P_{c}^{p}(z_{0}}}}}}}\오른쪽 },}$

어디에

• ${\displaystyle p}$ $[\displaystyle p}$이(가) 기간이고
• ${\displaystyle c}$ $[\displaystyle c}$은(는) 추정해야 할 지점이다.
• ${\displaystyle P_{}}$ ${\displaystyle c_{}}$( ${\displaystyle z}$) ${\displaystyle P_{c}(z)}$은(는) 복합 2차 다항식 $P{\displaystyle {}_{}}$ ${\displaystyle c_{}}$ ${\displaystyle z}$)${\displaystyle }$= z ${\displaystyle {2\mathrm{}}^{}}$+ ${\displaystyle c}$ ${\displaystyle P_{c}(z)=z^{2}+c}$
• ${\displaystyle P_{c}^{p}(z_{0})}$ is the ${\displaystyle p}$-fold iteration of ${\displaystyle P_{c}(z)\to z}$, starting with ${\displaystyle P_{c}^{0}(z)=z_{0}}$
• ${\displaystyle z_{0}}$ is any of the ${\displaystyle p}$ points that make the attractor of the iterations of ${\displaystyle P_{c}(z)\to z}$ starting with ${\displaystyle P_{c}^{0}(z)=c}$; ${\displaystyle z_{0}}$ satisfies ${\displaystyle z_0=P_c^p(z_0)}$${\displaystyle z_{0}=P_{c}^{p}(z_{0$
• ${\displaystyle {\frac {\partial }{\partial {c}}}{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})}$, ${\displaystyle {\frac {\partial }{\partial {z}}}{\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})}$, ${\displaystyle \frac{\mathrm{\partial }}{\mathrm{\partial }c}{P}_c^p}$${\displaystyle {\frac {\partial }{\partial {c}}}P_{c}^{p}(z_{0})}$ and ${\displaystyle {\frac {\partial }{\partial {z}}}P_{c}^{p}(z_{0})}$ are various derivatives of ${\displaystyle P_{c}^{p}(z)}$, evaluated at ${\displaystyle z_{0}}$.

외부 케이스와 유사하게, 일단 b가 발견되면, 우리는 C에서 B = 4b를 초과하는 모든 지점이 Mandelbrot 세트 밖에 있다는 것을 안다.

내부 거리 추정에는 두 가지 현실적인 문제가 있는데, 첫째, ${\displaystyle {z\mathrm{}}_{}}$ 0 ${\$을 정확하게$$ 찾아야 하고, 둘째, $p{\displaystyle }$ ${\displaystyle p}$을(를) 정확하게$$ 찾아야 한다.$z{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$의 문제는 P ${\displaystyle c_{}(z}$ $){\displaystyle p_{0}}$을 반복함으로써$$ $z{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$에 대한 수렴은 이론적으로 무한정 많은 연산을 요구한다는$$ 것이다$$.주어진 $p{\displaystyle }$ ${\displaystyle p}$의 문제는 반올림 오류로 인해 기간이 실제 기간의 정수 배수로 잘못 식별되는 경우가 있다는 것이다$$(예: 86의 기간이 검출되는 반면 실제 기간은 43=86/2에 불과하다).이러한 경우 거리가 과대평가된다. 즉, 보고된 반지름에 맨델브로트 집합 외부의 지점이 포함될 수 있다.

흉부/전구 검사

계산을 개선하는 한 가지 방법은 주어진 지점이 흉부외과 내에 있는지 아니면 기간-2 전구에 있는지 미리 알아보는 것이다.이스케이프 시간 알고리즘을 통해 복합 값을 전달하기 전에 먼저 다음 사항을 확인하십시오.

$displaystyle$$}}}}$,

${\displaystyle x}$ ${\displaystyle \le }$ ${\displaystyle p}$- ${\displaystyle 2}$ ${\displaystyle \frac{\mathrm{p}}{}}$ 2${\displaystyle {}^{}}$+ ${\displaystyle 1\frac{\mathrm{}}{}}$ 4 ${\$

${\$$}}\leq {\frac {1}{16$

여기서 x는 점의 실제 값을 나타내고 y는 가상 값을 나타낸다.처음 두 방정식은 점이 마지막 주기-2 전구인 심근경색 내에 있다는 것을 결정한다.

심근 검사는 제곱근 없이 동등하게 수행될 수 있다.

${\displaystyle q=\왼쪽(x-{\frac {1}{4}\오른쪽)^{2}+y^{2},}$

${\displaystyle q\left(q+\왼쪽)(x-{\frac {1}{4}\오른쪽)\leq {\frac {1}{4}y^{2}.}$

3차 이상의 꽃봉오리는 완벽하게 원형이 아니기 때문에 동등한 테스트를 하지 않는다.^[11]단, 이 고차 전구 안에 새겨진 원 안에 점이 있는지 확인할 수 있어 전부는 아니지만 많은 점들이 반복되지 않도록 한다.

주기성 검사

세트 내 포인트에 대해 엄청난 횟수의 반복을 하지 않도록 주기성 검사를 할 수 있다.픽셀 반복에서 한 점에 도달했는지 확인하십시오.만약 그렇다면 픽셀은 분리될 수 없으며 세트 안에 있어야 한다.

주기적인 점검은 물론 절충이다.포인트를 기억해야 하는 필요성은 메모리 및 데이터 관리 지침을 비용이 드는 반면, 계산 지침은 절약된다.

그러나 이전 반복 단 한 번만 점검하면 성능 오버헤드가 거의 없는 많은 기간을 감지할 수 있다.예를 들어, 위의 가성 코드의 중간 루프 내에서 다음과 같이 수정하십시오.

Xold:=0yold:=0기간:=0반면(x×x+y×y ≤ 2×2와 반복<>max_iteration)xtemp니:)x×x-y×y+x0는 y:=2×x×y+y0 x:=xtemp 반복:)반복+1if)과 y≈ xold ≈ yold 다음 반복:)max_iteration 및 우리는 Mandelb 안의 색 구상*/방학 및 와에 맥스로 설정합니다.썩음set, while 루프 */ period := period + period > 20이면 period := 0 xold := x yold := y

위의 코드는 새로운 x와 y 값을 20:th 반복마다 저장하므로 최대 20 포인트 길이의 기간을 탐지할 수 있다.

테두리 추적/엣지 검사

만델브로트 세트에 모든 테두리 색상이 동일한 솔리드 형상을 그릴 수 있다면 그 형상을 그 색상으로 채울 수 있다는 것을 알 수 있다.만델브로트 세트가 단순하게 연결된 결과다.보더 트레이싱은 세트 곳곳의 다양한 반복 수준(색채 밴드)의 레미네이케이트를 따라 한 번에 밴드 전체를 채우는 방식으로 진행된다.이것은 많은 수의 포인트를 건너뛸 수 있다는 것을 의미하기 때문에 좋은 속도 증가가 될 수 있다.^[12]그림에서 DE(거리 추정치) 또는 잠재적(굴절 반복) 값을 계산하는 경우 세트 밖의 픽셀 대역을 식별하는 데 테두리 추적을 사용할 수 없다는 점에 유의하십시오.

테두리 추적은 픽셀이 M에 있다고 판단하려면 최대 반복 횟수를 계산해야 하기 때문에 만델브로트 집합(M)의 일부인 플롯의 큰 영역을 건너뛰는 데 특히 유용하다.

다음은 국경 추적을 사용하여 렌더링된 Mandelbrot 집합의 예:

이것은 최대 반복 횟수가 1000회인 단순 탈출 시간 렌더링을 사용한 400x400 픽셀 플롯이다.국경 추적이 없다면 필요했을 총 반복 횟수의 6.84%만 계산하면 되었다.느리게 렌더링된 엔진을 사용해 렌더링 공정을 충분히 느리게 만들어 렌더링에 6.05초가 걸렸다.동일한 플롯이 느린 동일한 렌더링 엔진으로 테두리 추적이 꺼진 상태로 렌더링하는 데 117.0초가 걸렸다.

부분 반복 값(경계 추적이 비 Mandelbrot 점을 추적하지 못하도록 방지하는)을 계산하도록 설정을 변경하더라도 맨델브로트 점을 식별하려면 항상 최대 반복 횟수가 필요하기 때문에 경계 추적 알고리즘은 7.10초 내에 이 그래프를 렌더링한다는 점에 유의하십시오.최대 반복 횟수가 많을수록 맨델브로트 점을 식별하는 비용이 더 많이 들기 때문에 국경 추적이 제공하는 편익이 더 크다.

즉, 외부 영역이 매끄러운/연속적인 색상을 사용하더라도 국경 추적이 여전히 Mandelbrot 세트의 값비싼 내부 영역을 가속화할 것이다.내부 영역도 내부 거리 추정과 같은 부드러운 색칠 방법을 사용하지 않는 한.

직사각형 검사

국경 추적보다 더 오래되고 구현하기 쉬운 방법은 직사각형을 사용하는 것이다.직사각형 방법에는 여러 가지 변화가 있다.이들 모두는 결국 더 많은 픽셀을 계산하게 되기 때문에 국경 추적보다 더 느리다.

기본 방법은 8x8픽셀의 박스 테두리 픽셀을 계산하는 것이다.전체 상자 테두리의 색상이 같다면 상자 안에 있는 36픽셀(6x6)을 계산하는 대신 같은 색상으로 채우십시오.(마리아니의 알고리즘).^[13]

더 빠르고 조금 더 발전된 변형은 우선 25x25 픽셀처럼 더 큰 박스를 계산하는 것이다.전체 상자 테두리의 색상이 같으면 같은 색상으로 상자를 채우십시오.그렇지 않은 경우 상자를 13x13 픽셀의 상자 4개로 분할하여 이미 계산된 픽셀을 외부 테두리로 재사용하고 내부 "크로스" 픽셀을 내부 박스 간에 공유하십시오.다시 한 번, 테두리 색상이 하나만 있는 상자에 채워 넣으세요.그리고 그렇지 않은 상자를 7x7 픽셀 박스 4개로 나누십시오.그리고 4x4 박스에 "실패"한 것들.(마리아니-실버 알고리즘).

더 빠른 것은 상자를 네 개의 상자로 나누는 것이 아니라 반으로 나누는 것이다.그렇다면 A3 용지를 A4 용지, A5 용지로 접는 것처럼 분할할 수 있도록 가로 세로 비율이 1.4:1인 박스를 사용하는 것이 가장 적합할 수 있다.(DIN 접근법)

한 변종이 각 상자의 모서리 픽셀을 계산한다.그러나 이것은 모든 박스 테두리 픽셀을 계산하는 것보다 더 자주 손상된 사진을 야기한다.따라서 6x6 픽셀의 작은 박스만 사용하고 더 큰 박스에서는 재귀가 되지 않는 경우에만 합리적으로 잘 작동한다. (프랙틴트법)

경계선 추적과 마찬가지로 사각형 검사는 한 개의 분리된 색상의 영역에서만 작동한다.그러나 외부 영역이 부드러운/연속적인 색상을 사용하더라도 직사각형 검사로 인해 Mandelbrot 세트의 값비싼 내부 영역이 계속 빨라진다.내부 영역도 내부 거리 추정과 같은 부드러운 색칠 방법을 사용하지 않는 한.

대칭 활용도

Mandelbrot 세트의 수평 대칭은 최종 영상에 실제 축이 있을 때 렌더링 프로세스의 일부를 생략할 수 있다.그러나 미러링되는 부분에 관계없이 동일한 수의 포인트가 렌더링된다.

줄리아 세트는 기원을 중심으로 대칭을 이루고 있다.이것은 사분면 1과 사분면 3이 대칭이고 사분면 2와 사분면 4가 대칭임을 의미한다.Mandelbrot와 Julia 세트 모두에 대해 대칭을 지원하려면 두 가지 다른 유형의 그래프에 대해 대칭을 다르게 처리해야 한다.

멀티스레딩

Mandelbrot와 Julia 세트의 탈출 시간 렌더링은 병렬 프로세싱에 매우 적합하다.멀티 코어 기계에서 플롯할 영역은 일련의 직사각형 영역으로 나눌 수 있으며, 이 영역은 렌더링 스레드 풀에 의해 렌더링될 일련의 작업으로 제공될 수 있다.이것은 당황스러울 정도로 병렬^[14] 컴퓨팅 문제다.(먼저 그래프의 대칭 영역을 제외한 다음 나머지 고유 영역을 직사각형 영역으로 나누면 최상의 속도를 얻을 수 있다는 점에 유의하십시오.)^[15]

다음은 Mandelbrot 세트가 멀티스레딩과 대칭을 사용하여 렌더링되지만 경계가 없는 것을 보여 주는 짧은 동영상이다.

마지막으로, 다음은 멀티스레딩, 대칭 및 경계를 사용하여 렌더링되는 동일한 Mandelbrot 세트 이미지를 보여주는 비디오 입니다.

섭동 이론 및 직렬 근사치

매우 고도로 확대된 이미지는 대부분의 하드웨어 부동 소수점 장치가 제공하는 표준 64–128비트 이상의 정밀도를 요구하기 때문에 렌더러는 느린 "BigNum" 또는 "임의 정밀도" 수학 라이브러리를 사용하여 계산해야 한다.그러나 이것은 섭동 이론의 착취에 의해 가속될 수 있다.주어진

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

반복으로, 그리고 작은 엡실론과 델타로서, 그것은 다음과 같은 경우다.

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

또는

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

그래서 만약 어떤 사람이 정의한다면

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

엡실론 0이 0으로 설정된 엡실론에 대해 다양한 초기 오프셋 델타 + 위의 반복의 관점에서 단일 지점(예: 영상의 중심)을 계산하면 된다.대부분의 반복에서 엡실론은 16개 이상의 유의미한 수치를 필요로 하지 않으며, 결과적으로 하드웨어 부동점을 사용하여 대부분 정확한 이미지를 얻을 수 있다.^[16]종종 지점의 궤도가 기준 궤도에서 충분히 이탈하여 해당 지점에 추가 정밀도가 필요하거나 또는 국소 고정밀 계산 기준 궤도를 추가로 필요로 하는 영역이 있을 것이다.기준점과 계산점 사이의 궤도 거리를 낮은 정밀도로 측정함으로써, 점을 정확하게 계산할 수 없다는 것을 감지할 수 있고, 계산을 중지할 수 있다.이러한 부정확한 점들은 나중에 다른 더 가까운 기준점에서 다시 계산할 수 있다.

또한 잘린 테일러 시리즈로 정밀도가 낮은 지점의 시작 값을 대략적으로 추정할 수 있어 상당한 양의 반복을 건너뛸 수 있는 경우가 많다.^[17]이러한 기법을 구현하는 렌더러는 공개적으로 사용할 수 있으며, 약 2배까지 고도로 확대된 이미지에 대한 속도 향상을 제공한다.^[18]

위에 대한 대체 설명:

디스크 $c{\displaystyle }$ ${\displaystyle c}$과(와)의 중심점 ${\displaystyle z_{}}$n {\$displaystyle z_{$n}과$($와) $디스크{\displaystyle }$ c +${\displaystyle \Delta }$ ${\displaystyle$ c$+\delta }$의 임의점 및 그 반복점 ${\displaystyle z_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$에 대해 다음과 같은 반복 관계를 정의할 수 있다$.$

${\displaystyle z'_{n}=z_{n}+\epsilon _{n}}}$

$ϵ{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$= ${\displaystyle \Delta }$ ${\displaystyle \epsilon _{1}=\delta }.$$ϵ{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$의 연속 반복은 다음을 사용하여 확인할 수 있다$$.

${\displaystyle z'_{n+1}={z'_{n}^{2}+(c+\property )}$

${\displaystyle z'_{n+1}=(z_{n}+\epsilon _{n}^{2}+c+\messages }}$

${\displaystyle z'_{n+1}={z_{n}^{2}+c+2z_{n}\epsilon _{n}+{n}}{n}^{n}+\n}}}$

${\displaystyle z'_{n+1}=z_{n+1}+2z_{n}\epsilon _{n}+{n}}{n}+{n}^{n}+\n3}}$

이제 원래 정의에서 보자면:

${\displaystyle z_{}^{}}$ ${\displaystyle n_{}^{}}$+ ${\displaystyle 1_{}^{}}$ ${\displaystyle {}_{}^{}}$= ${\displaystyle z_{}}$ n${\displaystyle {}_{}}$+ ${\displaystyle 1_{}}$+ ${\displaystyle {ϵn}_{}}$+ ${\displaystyle 1_{}}$ + 1 ${\$

그 다음은 다음과 같다.

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

반복관계는 매우 작은 변화 ${\displaystyle \delta }$에 의해 임의의 지점을 중심점에 연관시키므로,$$${\displaystyle {ϵn}_{}}$ ${\$의 반복도 대부분 작으며$$ 부동소수 하드웨어를 사용하여 계산할 수 있다.

그러나 디스크의 임의 지점마다 ${\displaystyle {forn}_{}}$${\$ $\epsilon_$${n}$의 시퀀스를 반복하지 않고도 주어진$$ ${\displaystyle {givenn}_{}}$ ${\$ $\$$epsilon$_{n}을 ${\displaystyle \epsilon_$${n}$의 파워 시리즈로$$ 표현함으로써 계산이 가능하다$.$$}$.

$\displaystyle \epsilon _{n}=A_{n}\delta +B_{n}\delta ^{2}+C_{n}\delta ^{3}+\dotsc }}$

$A{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$= ${\displaystyle 1}$,${\displaystyle {B\mathrm{}}_{}}$ ${\displaystyle {}_{}}$= 0${\displaystyle ,}$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$= ${\displaystyle 0,}$… ${\displaystyle A_{1}=1,B_{1}=0,C_{1}=0,\dotsc$ $\}.$

이제 $ϵ{\displaystyle }$ ${\displaystyle \epsilon }$의 반복 방정식을 고려할 때$,$ 각 $ϵ{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$ :에 대한 일련의 계수 계산이 가능하다.

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

${\displaystyle \epsilon _{n+1}=2z_{n}(A_{n}\delta +B_{n}\delta ^{2}+C_{n}\delta ^{3}+\dotsc )+(A_{n}\delta +B_{n}\delta ^{2}+C_{n}\delta ^{3}+\dotsc )^{2}+\delta }$

${\displaystyle \epsilon _{n+1}=(2z_{n}A_{n}+{n}B_{n}+{A_{n}^{n}}}\delta ^{2}+{2}+{n_{n}C_{n}}+2}\delta ^{n}+2}A_{n}B_{n}\delta ^{3}+\dotsc }$

따라서 다음과 같다.

${\displaystyle A_{n+1}=2z_{n}A_{n}+1}$

${\displaystyle B_{n+1}=2z_{n}B_{n}+{A_{n}}^{2}}$

${\displaystyle C_{n+1}=2z_{n}C_{n}+2A_{n}B_{n}}}$

$\displaystyle \vdots }$

파워 영상 시리즈의 계수는 중앙 지점의 $반복{\displaystyle }$ z ${\displaystyle$ z$\}$의 값만 사용하여 반복 영상 시리즈로 계산할 수 있으며 디스크의 임의 지점에 대해서는 변경되지 않는다.$\Delta {\displaystyle }$ ${\displaystyle \delta }$이(가) 매우 작을 경우, $\Delta {\displaystyle {}_{}}$ ${\displaystyle n_{}}${\$displaystyle \epsilon_{n}$은(는) 전력 시리즈의 몇 항만 사용하여 충분한 정확도로 계산할 수 있어야$$ 한다.만델브로트 탈출 등고선은 복잡한 평면에 걸쳐 '연속적'이므로, 점 탈출 시간이 계산된 경우, 해당 점 주변의 탈출 시간은 유사해야 한다.인접 지점의 보간 작업을 통해 ${\displaystyle {nn}_{}}${\$displaystyle \epsilon_{n}$ 시리즈에서$$ 시작할 위치를 충분히 추정할 수 있어야 한다.

또한 실제 축 점과 가상 축 점을 분리하여 보간하면 계산되는 점에 대해 상한과 하한을 모두 제공해야 한다.두 결과가 같을 경우(즉, 모두 탈출하거나 탈출하지 않을 경우) ${\displaystyle \mathrm{\Delta n}}$ ${\displaystyle \Delta n}$ 차이를 사용하여 상한과 하한을 모두 설정할 수 있을 때까지 재사용할 수 있다$$.부동 소수점 하드웨어를 사용하여 $ϵ{\displaystyle }$ ${\displaystyle \epsilon }$ 시리즈를$$ 반복할 수 있는 경우, 주어진 ${\displaystyle {ϵ}_{}}$ n ${\$을 계산하는 데 BigNum 소프트웨어를 사용하는 데 걸리는 시간 내에 얼마나 많은 반복을 달성할 수 있는지와 관계가 있다$.$ 경계 간의 차이가 ip 개수보다 큰 경우용어는 BigNum 소프트웨어를 사용하여 바이너리 검색을 수행할 수 있으며, 플로팅 포인트 하드웨어를 사용하여 이스케이프 값을 찾는 것이 더 시간 효율적이 될 때까지 연속적으로 간격을 절반으로 줄인다.

참조