有哪些辦法繪製分形?

背後的數學原理是什麼?


1. escaping time

諸如Mandelbrot set, Julia set, Mandelbulb等分形所基於的數學方法,

也就是等式:z_{n} = z_{n-1}^p + c

理論基礎是dynamical system,迭代等式一定次數之後,z仍然收斂就將z認為是分形集合的一部分。這時候這個集合叫做repeller,對應於IFS中的attractor。

二維的Mandelbrot set 和Julia set等的繪製非常簡單,將每個點代入迭代,計算出escape radius進行著色即可,請參考這裡的推導:Renormalizing the Mandelbrot Escape

但是要想得到更cool的結果還需要採用orbit trap的方法進行著色。

每次迭代中, z對應於orbit中的一點,最簡單直接的orbit trap就是計算orbit中每個點到某一個固定點(原點?)的平均距離,然後根據距離值到color table中取顏色。

也可以採用更複雜的orbit trap來獲得更impressive的著色,比如計算orbit到某函數曲線的距離等。

下圖是計算了orbit到sin曲線的距離得到的圖像,這是一個Julia set

對於三維空間中的Mandelbulb來說,難以定義一個完備的復空間,事情就變得麻煩了一點,但是我們經常可以做一些數學上不正確的事情來把東西渲染得漂亮。

Daniel Nylander找到一個方法,將z看作球面坐標。

對複平面而言:

z = r * (cos(theta) + i sin(theta))

那麼可以對於3維復空間:

z = r*(sin(theta)cos(phi) + i cos(theta) + j sin(theta)sin(phi)

So:

z^n = r^n * (sin(n*theta)*cos(n*phi) + i cos(n*theta) + j sin(n*theta)*sin(n*theta)

可以看出,每次迭代,只需要將半徑power,角度加倍。

有了這個公式,就可以通過計算三維空間中每個點是否在Mandelbulb中了,不過這種方法過於brute force,通常只針繪製對無法找到distance estimator的分形。

所以通常的繪製都是基於raymarching,判斷到Mandelbulb的距離,而距離的計算又有很多可以深入挖掘的地方,請參考John Hart的這篇paper,有所有你需要的東西:Ray tracing deterministic 3-D fractals。

順便也丟一張我的Mandelbulb:

然後附上一段示例代碼吧,48行c代碼,也是繪製一個mandelbulb,不過這種東西還是shader寫著方便:)

#include &
#include & struct vec {
double x, y, z;
vec(double r=0, double g=0, double b=0){ x=r; y=g; z=b; }
vec operator+(const vec b) const { return vec(x+b.x,y+b.y,z+b.z); }
vec operator*(double b) const { return vec(x*b,y*b,z*b); }
vec norm(){ return *this*(1/sqrt(x*x+y*y+z*z)); }
vec operator%(vecb){return vec(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);}
};
static vec map(vec p) {
vec z=p, dz=vec(0.0, 0.0, 0.0);
double power=8.0, r, tta, phi, dr=1.0, t0=1.0;
for(int i=0;i&<7;++i) { if((r=sqrt(z.x*z.x+z.y*z.y+z.z*z.z)) &> 2.0) break;
tta=acos(z.y/r)*power; phi=atan(z.z/z.x)*power;
// spherical
dr=pow(r, power-1.0)*dr*power+1.0;
// derevative
r=pow(r, power);
z=vec(sin(tta)*cos(phi), cos(tta), sin(tta)*sin(phi))*r+p;
t0=t0&

2.IFS(iterated function system)

它的數學推導,簡單來說就是:

屬於一個分形圖形的點的集合,叫做attractor,

S是一個變換,兩點經過S變換後距離縮小,那麼S就是一個contractor。

於是我們反覆的迭代的應用S來逼近attractor,就得到了分形圖形。

什麼sierpinski,menger sponge,coch 雪花等等都是這一類。

通常兩種方法來繪製這樣的分形:

Attractive method:就是根據定義反覆變換

Chaos game:隨機方法,每次隨機選擇集合中的點進行變換。

3.KIFS (Kaleidoscopic IFS)

這是Knighty提出的一個更有意思的方法來計算IFS,就是space folding,就像我們做剪紙。

Kaleidoscopic (escape time) IFS

可以產生出一大批奇特的分形。

比如這個最簡單的menger sponge的變形:

4.Hybrid

就是多種方法,多種分形的結合了,

經典的如Mandelbox,就是escaping time和space folding的完美結合,

更複雜的諸如Spudsville,Pseudo Kleinian等,都是在已有分形方法上進行組合,通常在這上面最能產生最具創意的分形,這裡就不詳細說了。

其實還有很多類型的分形,也有很多繪製的方法,不必拘泥於經典方法,比如menger_sponge完全可以通過一些trick在cube上迭代挖洞(raymarching的特性讓挖個洞額外簡單啊)來進行繪製,只要你想得到。如果想要更詳細了解這些分形演算法,有不少軟體可以利用,比如最經典的Mandelbulb 3D, Mandelbulber(開源), Fragmentarium(我最喜歡的,提供了幾乎所有的分形的例子)。

Welcome to Fractal Forums 這裡有最深入討論和最新的發現。


如果你說的並非簡單的幾何分形而是那種漂亮的圖片的話,我不是很建議自己造輪子, 因為你至少要懂分形,還要硬性計算寫代碼寫到瘋,搞優化瘋了繼續搞...

然而並沒有什麼卵用,丑的懷疑人生,因為你還需要一個成熟的渲染方案...

網上(比如Wiki)很多漂亮的分形圖是用 Ultra Fractal 畫出了來的......


先歪個樓,說點別的,沒有對比就沒法認識到這個軟體的強大...

很久以前幾何畫板火遍各大學校,一般認為幾何畫板只能畫畫軌跡, 但是...牛人永遠喪心病狂的牛...

那時有個整合版,裡面有非常多不可思議的實例,有專門的一個分形文件夾,一百多個範例,打開是這個樣子的:

這樣子逐點掃描,一張圖要15分鐘到兩小時不等......

然後...這個整合版被某個大盜竊國的漢奸公司給整了,那麼多作品就此蒸發...

開源的Geogebra據我所知只能畫簡單的幾何分形......

不過運行效率比幾何畫板高...這一定是假的Java程序...


10.0版本(2014)後Mathematica陸續加入了一些分形函數,雖然默認染色很迷,一點都不好看啊...

市面上的MMA教材書上都會有畫分形的代碼,其實寫的都不咋的...

當然你要我寫個很咋滴的代碼我也寫不出來,因為 用MMA硬計算是錯誤的使用方法...

正確方法是寫OpenCL或者現在的話用CUDA單元...或者 Wolfram 自帶的 LibraryLink 跑C庫 ...


好,開始正文,來說 Ultra Fractal ,雖然這個軟體快10年沒更新了...有漢化破解版:分形藝術網

接下來手把手教你創造一張分形圖片(非內置).

  • 打開軟體

Aha,一個曼德布羅特集合...現在我們來學習這樣一張圖片是什麼東西.

中間黑色的一大片,有人說像個甲蟲,有人說像個卧佛,這不重要...

學名叫不動點或者迭代收斂域.

考慮遞推數列: z_{n+1}=z_n^2+c ,有的點,比如原點 c=0 吧,一個數迭代無限次以後還是本身不會變成無窮大.於是就把這個點塗黑.

但是有的迭代,比如 z_{n+1}=z_n^2+2 ,任何初值開始迭代都會發散到無窮大,那麼就根據發散速度染色.

但是呢...有個問題啊,計算機還能計算無限次迭代?計算機還能計算無限個點?

所以實際上都是按照某種方式採樣,然後進行有限迭代,然後根據各種策略染色...

採樣,計算,渲染...這是計算機圖形老生常談的三大難題啊...

大多數情況下不用寫代碼, 新建里有很多的範例,直接往上加濾鏡就行了,如果你研究的分形很冷門裡面沒有怎麼辦?

  • OK,我們來創造一種分形.

考慮著名的考拉茲迭代:

a_{n+1} = egin{cases} a_n/2 mbox{if } a_n equiv 0 \ 3a_n+1  mbox{if } a_nequiv 1 end{cases} pmod{2}

使用奇偶合併公式解析延拓到 mathbb C 上變成:

f(z)=frac{1}{4}(1 + 4z - (1 + 2z)cos(pi z))

可以驗證這個公式仍然是偶數變一半,奇數三加一.

新建一個圖案,點擊公式編輯按鈕:

然後隨便在那個地方插入代碼:

Collatz {
init:
z = #pixel
loop:
z = (1+4*z-(1+2*z)*cos(pi*z))/4
bailout:
|z| &<= @bailout default: title = "Collatz" param bailout caption = "迭代檢測" default = 10000.0 endparam }

其實就是輸個公式,然後新建一個圖案就能找到.

剩下的就是加濾鏡,調參數什麼的,不用寫任何代碼...

不用考慮採樣,計算,渲染三大難題...

當然這個圖還比較丑...因為這個函數迭代收斂比曼德布羅特快得多得多...要改染色尺,然後加個濾鏡...

最終大概可以調成這個樣子,有點點星空的感覺haha...


高級技巧,使用圖片作為分形元,你還看得出來這是曼德布羅特集的一部分嗎?

更多技巧可以參考上面列出的那個分形藝術網...

不過他們不喜歡放代碼......如果懂英文還是到外站去看比較好,代碼比較全...

那個網上還有其他分形軟體,我就不介紹了......

PS:如果感興趣的人多的話我就寫一下我當初研究了啥...


1. 曼德勃羅集

import numpy as np
import pylab as pl
import time
from matplotlib import cm

def iter_point(c):
z = c
for i in xrange(1, 100): # 最多迭代100次
if abs(z)&>2: break # 半徑大於2則認為逃逸
z = z*z+c
return i # 返回迭代次數

def draw_mandelbrot(cx, cy, d):
"""
繪製點(cx, cy)附近正負d的範圍的Mandelbrot
"""
x0, x1, y0, y1 = cx-d, cx+d, cy-d, cy+d
y, x = np.ogrid[y0:y1:200j, x0:x1:200j]
c = x + y*1j
start = time.clock()
mandelbrot = np.frompyfunc(iter_point,1,1)(c).astype(np.float)
print "time=",time.clock() - start
pl.imshow(mandelbrot, cmap=cm.jet, extent=[x0,x1,y0,y1])
pl.gca().set_axis_off()

x,y = 0.27322626, 0.595153338

pl.subplot(231)
draw_mandelbrot(-0.5,0,1.5)
for i in range(2,7):
pl.subplot(230+i)
draw_mandelbrot(x, y, 0.2**(i-1))
pl.subplots_adjust(0.02, 0, 0.98, 1, 0.02, 0)
pl.show()

2. 分形樹葉

import numpy as np
import matplotlib.pyplot as pl
import time

# 蕨類植物葉子的迭代函數和其概率值
eq1 = np.array([[0,0,0],[0,0.16,0]])
p1 = 0.01

eq2 = np.array([[0.2,-0.26,0],[0.23,0.22,1.6]])
p2 = 0.07

eq3 = np.array([[-0.15, 0.28, 0],[0.26,0.24,0.44]])
p3 = 0.07

eq4 = np.array([[0.85, 0.04, 0],[-0.04, 0.85, 1.6]])
p4 = 0.85

def ifs(p, eq, init, n):
"""
進行函數迭代
p: 每個函數的選擇概率列表
eq: 迭代函數列表
init: 迭代初始點
n: 迭代次數

返回值: 每次迭代所得的X坐標數組, Y坐標數組, 計算所用的函數下標
"""

# 迭代向量的初始化
pos = np.ones(3, dtype=np.float)
pos[:2] = init

# 通過函數概率,計算函數的選擇序列
p = np.add.accumulate(p)
rands = np.random.rand(n)
select = np.ones(n, dtype=np.int)*(n-1)
for i, x in enumerate(p[::-1]):
select[rands&

??

3. 其它分形圖(科赫曲線、分形龍、謝爾賓斯基三角等)

from math import sin, cos, pi
import matplotlib.pyplot as pl
from matplotlib import collections

class L_System(object):
def __init__(self, rule):
info = rule["S"]
for i in range(rule["iter"]):
ninfo = []
for c in info:
if c in rule:
ninfo.append(rule[c])
else:
ninfo.append(c)
info = "".join(ninfo)
self.rule = rule
self.info = info

def get_lines(self):
d = self.rule["direct"]
a = self.rule["angle"]
p = (0.0, 0.0)
l = 1.0
lines = []
stack = []
for c in self.info:
if c in "Ff":
r = d * pi / 180
t = p[0] + l*cos(r), p[1] + l*sin(r)
lines.append(((p[0], p[1]), (t[0], t[1])))
p = t
elif c == "+":
d += a
elif c == "-":
d -= a
elif c == "[":
stack.append((p,d))
elif c == "]":
p, d = stack[-1]
del stack[-1]
return lines

rules = [
{
"F":"F+F--F+F", "S":"F",
"direct":180,
"angle":60,
"iter":5,
"title":"Koch"
},
{
"X":"X+YF+", "Y":"-FX-Y", "S":"FX",
"direct":0,
"angle":90,
"iter":13,
"title":"Dragon"
},
{
"f":"F-f-F", "F":"f+F+f", "S":"f",
"direct":0,
"angle":60,
"iter":7,
"title":"Triangle"
},
{
"X":"F-[[X]+X]+F[+FX]-X", "F":"FF", "S":"X",
"direct":-45,
"angle":25,
"iter":6,
"title":"Plant"
},
{
"S":"X", "X":"-YF+XFX+FY-", "Y":"+XF-YFY-FX+",
"direct":0,
"angle":90,
"iter":6,
"title":"Hilbert"
},
{
"S":"L--F--L--F", "L":"+R-F-R+", "R":"-L+F+L-",
"direct":0,
"angle":45,
"iter":10,
"title":"Sierpinski"
},

]

def draw(ax, rule, iter=None):
if iter!=None:
rule["iter"] = iter
lines = L_System(rule).get_lines()
linecollections = collections.LineCollection(lines)
ax.add_collection(linecollections, autolim=True)
ax.axis("equal")
ax.set_axis_off()
ax.set_xlim(ax.dataLim.xmin, ax.dataLim.xmax)
ax.invert_yaxis()

fig = pl.figure(figsize=(7,4.5))
fig.patch.set_facecolor("papayawhip")

for i in xrange(6):
ax = fig.add_subplot(231+i)
draw(ax, rules[i])

fig.subplots_adjust(left=0,right=1,bottom=0,top=1,wspace=0,hspace=0)
pl.show()

代碼取自張若愚老師的教材


這兩天用Matlab畫了一堆,正好看到了這個問題。

畫分形圖,基本都是按照其自相似性畫。

在Matlab中有兩種常見的畫法,一種是迭代法,一種是Lindenmayer系統。

如繪製如下常見圖形

  • Koch雪花

  • 樹圖1

  • 樹圖2

  • 樹圖3(蕨類植物)

  • Sierpinski三角形

對於複變函數迭代

Z_{k+1}=Z^m_{k}+C

C 為常數,稱為Julia集( m=2m>2 稱為廣義Julia集)

  • Julia集

C 不為常數時,比如 C=Z ,稱為Mandelbort集

  • Mandelbort集

發一個迭代的代碼(Koch雪花)

new=[0,1,1/2+1i*sqrt(3)/2,0];

subplot(2,3,1);

plot(new),axis equal;

for k=1:5

old=new;

n=length(new)-1;

diff=(old(2:n+1)-old(1:n))/3;

new(1:4:4*n-3)=old(1:n);

new(2:4:4*n-2)=old(1:n)+diff;

new(3:4:4*n-1)=new(2:4:4*n-2)+diff*exp(-1i/3*pi);

new(4:4:4*n)=old(1:n)+diff+diff;

new(4*n+1)=old(n+1);

subplot(2,3,1+k);

plot(new),axis equal

end

一個L系統的代碼(Sierpinski三角形)

S="F+F+F"; p="F+F+F+FF"; %初始元與生成元

a=2*pi/3; z=0; A=eps; %轉角、起點與方向

for k=2:4 %迭代次數

S=strrep(S,"F",p); %用生成元替代初始元

n=(1/3)^(k-1); %壓縮比

end

figure;axis equal;hold on

for k=1:length(S)

switch S(k)

case "F", plot([z,z+n*exp(1i*A)],"linewidth",2); z=z+n*exp(1i*A);

case "+", A=A+a;

otherwise

end

end


常見的編程語言都可以啊,Python、Mathematica、Matlab等都比較好用,

個人推薦Mathematica,寫出的代碼往往簡潔高效

http://hi.baidu.com/van_der_kommu 這個博客裡面有許多畫分形的Mathematica代碼

下面是幾個簡單例子:

Mandelbrot set

動態放大,

http://static.oschina.net/uploads/img/201303/28153512_CrWV.gif

sierpinski triangle

sierpinski pyramid


分形啊,參考作為一名交互設計師應該如何學習Processing?最後一段,還有The nature of code的這一章啦The Nature of Code。

怎麼畫啊,目前我找到視覺效果最好的就是Mandbulb 3D啦,在http://fractalforum.com有詳細教程。或者自己找一些論文,寫代碼畫。


貼一個C++版的:

QtCore 5.0: Mandelbrot Example

網址內有源碼,是Qt給QThread寫的demo,OS Independent,在大多數情況下請隨意編譯運行。

縮放的時候效率挺高的,只是代碼略長,主要:

renderthread.cpp中的RenderThread::run()負責線程繪製;

renderthread.cpp中的RenderThread::rgbFromWaveLength(double wave)負責上色;

mandelbrotwidget.cpp是窗口代碼,非核心。

效果圖如下:


javascript+html5的實現:

Julia Map

源碼直接在網頁上。

-----------------------------

js真是神器


自己編程序,VB, C/C++, Java, Python,任何一種你會的語言,帶有繪圖功能的。

分形的數學原理就是滿足一定參數範圍內的無窮迭代和反饋。

塞爾斌斯基三角形,J集、M集這些程序從網上都能找到。

更多的可以參考一些書,比如:

分形演算法與程序設計:用Visual C++實現

分形藝術程序設計


往簡單說:遞歸。


自己用c++寫的繪製程序


用R語言,用R來玩分形 | COS論壇

或者Mathematica http://www.oftenpaper.net/sierpinski.htm


這個問題我之前想過,不過發現研究分形重點不在這裡吧。

如果你想畫分形圖,主流的科學計算軟體都夠用的了。如Mathematica,Matlab,C,C++等的都可以了,不過你要比較專業的話,就還有一個比較好上手的,Ultra fractal,你不妨一試。

分形幾何的世界非常美妙,很多國外的大學都有專門的頁面,不妨上去找找看看,不過分形圖的好壞跟你構造的函數有一定關係哦。所以你在作圖的時候需要注意。

希望對你有所幫助。


貼一個自己十幾年前剛學編程時候做的分形畫版 支持自定義公式。。代碼有點爛 看看就好。。https://github.com/waruqi/fractal


介紹一個簡單的軟體,幾何畫板。


除了上面提到的C/C++/Java/Python, 其實還可以用 js 在photoshop 裡面畫,畫完還可以用PS來調色,工具ExtendScript Tool ,ps自帶的


MATLAB


推薦閱讀:

工作6年的程序員,還在原地踏步怎麼辦?
透視裁剪到底發生在哪個階段?
海島奇兵中海邊的浪花是如何實現的,使用shader還是序列幀動畫?
手遊程序員想學習圖形學知識,圖形學、GL/DX、Shader這些有什麼合適的學習順序嗎?

TAG:數學 | 編程 | 分形理論 | 計算機圖形學 | 複數 |