可视化分形

• 下载 Fractal_Runtime.zip - 2.6 MB
• 下载源代码 - 608.5 KB

引言

Richard T. Stevens所著的《Turbo Pascal中的分形编程》（ISBN 1-55851-106-7）一书，正式将我引入了奇妙而神秘的分形世界。我之前唯一接触它们的地方是Lucasfilm公司的一款名为“Fractalus救援”的视频游戏，至今我仍怀念它。该书附带了一个源代码磁盘，在1994年价值20美元，其中包含源代码。

Fractalus救援

得益于现代的Commodore 64模拟器，我至今仍能玩《Fractalus救援》，这让我想起了往昔的美好时光。

当时，PCX格式是流行的图像格式。当我翻开书开始阅读时，一个全新的世界为我个人的探索打开了大门。这本书提供了一个对物理学、哲学和计算机系统领域主流思潮的绝佳历史视角，这些思潮是如何被拉到一起，在痛苦挣扎中研究混沌理论的。

分形

尽管如此，到第19页，分形一词被定义了。“分形 - 对所有豪斯多夫-贝西科维奇维度大于其欧几里得维度的曲线的描述。” 引言继续用一个例子来解释这个概念。“为了理解这个概念，先在一张纸上画一条线，然后围绕着纸张蜿蜒，但不要交叉，直到填满整张纸。欧几里得几何学说这仍然是一条线，但我们的视觉感官和直觉告诉我们这远不止于此，它具有二维性。” - Stevens 页码 25

软件实现

本文介绍的软件及其源代码，可以生成曼德勃罗集和朱利亚分形。朱利亚分形是生成经典曼德勃罗集方程的另一种表达形式。“曼德勃罗集构成了所有可能朱利亚集合的某种地图。” Stevens - 305。如果您查看朱利亚集合的关注点并放大到那些坐标的曼德勃罗集，那么足够放大后，朱利亚集合的图像就会开始出现。该软件不仅允许您可视化分形，还可以动画化颜色调色板，并选择性地将动画记录为AVI文件。好奇的读者请参见源代码中的AVI.h和AVI.cpp。其中包含用于创建和访问DIBSECTION（设备无关位图）的源代码。AVI在较低分辨率下记录效果最好。320 x 200分辨率的分形将能良好地记录。

这本书继续对方程族进行了更实际的分析。分形具有自相似的特性。这种自相似性可以通过几何学和几何替换来理解。创建自相似性需要两部分：生成器和起始器。几何形状成为生成器。现在，我们将生成器的每一条线段替换成另一组具有相同长度的线段。这些线段称为起始器。也可以有其他几何形状。这个过程会重复无限次。这就是豪斯多夫-贝西科维奇维度概念的由来。拥有“N条线段，每条长度为r，其中r是所替换线段的一小部分……然后可以证明，所得分形曲线的豪斯多夫-贝西科维奇维度D为：D = log N / log (1/r)” - Stevens 页码 28-29。

曼德勃罗集基于方程Zn+1 = Zn² + c。在此方程中，当n趋于无穷时，Z的值要么趋于无穷，要么保持在X² + Y² < 4的轨道内。Z和C是复数，X和Y由该方程的实部和虚部得出。保持在轨道内的值是集合中的点。有趣的是，我们最常识别为曼德勃罗集的正是那些不在集合中的值的可视化，而实际上它是“非曼德勃罗集”。改编自维基百科关于曼德勃罗集的文章。

本程序使用MFC类来构建程序的基本结构。该系统使用MDI架构。这使得每个方程的可视化都存在于自己的文档中，并拥有自己的视图。程序还允许选择视图中的矩形区域进行放大、添加文本或在分形上叠加图像，并允许不同级别的透明度与分形混合。装饰性文本可以通过用鼠标拖动来编辑和移动，当光标变为手形时。背景图像可以在渲染分形时融入其中。有两种选择：与基底混合，即不趋于无穷的坐标；或在“分形”中混合。缩放到朱利亚集合稍微有些限制。只要矩形区域包含朱利亚焦点，就可以实现缩放。在朱利亚分形中，还有一个上下文菜单中的2倍缩放选项。此外，每个可视化都可以保存为一个可重新加载的文档，或者保存为图像文件格式的图像。程序不限制您使用显示器的分辨率。您可以创建高达28,800 x 16,200像素的图像。您可以滚动文档以查看如此图像的细节。您也可以通过缩小来获得“全景”，以查看整个图像，并将其适应文档的视图。坐标会回显在状态栏中，并且从任何曼德勃罗分形中，您可以从当前鼠标光标位置生成一个朱利亚集合。在曼德勃罗分形中右键单击并选择朱利亚集合。

有许多缩放选项。您可以直接缩放到拖出的矩形区域。您可以通过指定缩放时要走的跳数来“飞入”该区域。您还可以进行小幅缩放或连续小幅缩放。小幅缩放将以最小增量进行缩放。连续小幅缩放将以这种方式持续缩放，让您飞入分形。

着色

有一些着色选项，允许在分形渲染之前或之后分配和编辑颜色。通过按下编辑颜色按钮并在新的分形对话框中双击颜色进行更改来完成颜色编辑。渲染后颜色编辑是通过在渲染的分形上右键单击并从上下文菜单中选择编辑颜色来完成的。此编辑颜色会修改创建分形的新分形对话框的调色板。颜色的基本应用使用逃逸轨道数对颜色数取模，以表示从0到所需分形颜色数的值。这用作颜色的红、绿、蓝值。结果是黑白渐变。此外，还可以应用每个颜色通道值的偏移量，使图像具有漂亮的色彩可视化。屏幕渐变条将向您显示分形中将存在的颜色。随机按钮为每个通道生成一个随机比例。该对话框还允许选择六种颜色来表示渐变中的一组颜色。当勾选渐变复选框时，随机按钮会创建一个随机渐变，并添加可选的比例。轨道可以根据出现次数着色。按较少轨道排序会将调色板按出现次数最少的轨道到出现次数最多的轨道进行排序。按较多轨道排序会将调色板按出现次数最多的轨道到出现次数最少的轨道进行排序。渲染分形后，您可以编辑颜色来更改它。此颜色将与分形文档一起保存，并在下次加载文档时重新加载。通过勾选红、绿、蓝复选框，您可以限制出现的颜色通道。基本颜色，或最后一个颜色，始终表示集合解的值。轨道永远不会逃逸。您可以通过勾选该选项并选择颜色来自定义此基本颜色。此外，还可以选择背景图像在基本颜色和分形颜色所在的位置进行混合。使用此选项可以实现漂亮的效果。例如，在水或天空上渲染分形。不透明度输入为0到100的百分比，其中0表示根本不混合，100表示仅显示图像。介于两者之间的值将导致图像和分形部分被组合。

角度分解

有一些着色选项允许使用角度分解进行着色。角度分解获取函数的X和Y值并将其转换为一个角度。然后将此角度缩放到迭代次数，这决定了颜色计数，然后将该值用作颜色。通过正常着色与角度分解的组合可以产生非常有趣的结果。要进行二进制分解，请选择一个2色调色板。尝试使用2色、16次迭代、二进制分解的分形。

分形的细节

分形的细节主要由算法的迭代次数控制。检测一个点不在解中的迭代次数称为逃逸轨道。逃逸轨道测试的上限越大，分形的细节就越精细。在此系统中，当您放大坐标时，更多的迭代次数可以产生更多细节。因此，如果您放大到一个小的坐标空间，较少的迭代次数将产生少得多的细节。有时，找到迭代次数和坐标之间的正确平衡是一种艺术，并能产生极其有趣的照片。参见接下来的两张图片。创建它们的 the 分形文档包含在EXE zip 下载包中。对于朱利亚分形，最好的图像通常是用较少的迭代次数生成的。颜色数量将迭代次数划分为同色组。当颜色数量等于迭代次数时，每个迭代都有其自己的颜色。

阶梯效果和平滑

系统允许您为分形添加阶梯效果，以及使用菜单选项平滑任何分形。平滑器是一个低通滤波器，它使用像素周围3x3区域的平均颜色作为新像素的颜色。阶梯效果增强了颜色之间的区域，以提供类似3D的效果。在新的分形对话框中，可以输入0到10的值。0等同于未使用。

基本工作部分是主菜单，允许您创建、保存、打印和加载文档。它允许您缩小并从视图菜单中查看全景，以防您想模拟一个像德克萨斯州一样大的屏幕。在每个文档中，您可以按住鼠标左键并拖出一个矩形区域，您想要缩放到该区域。这些是系统的基本工作部分，现在让我们来看一些代码！

图 5 - 类架构包含 3 个主要类

CFractalBase - 保持参数的基类

// Class for calculating the mandelbrot set
class CFractalBase
{
public:
    CFractalBase(CFractalParm FractalParm);
    virtual ~CFractalBase();
    virtual void operator() (int RowBeg,int RowEnd);

protected:
    virtual void Apply(int Iteration,int Column,int Row);

protected:
    CFractalParm m_FractalParm;
};

CFractalCanvas - 将像素放置到DIBs的派生类

// Base derived class for holding the canvas (DIB + colors)
class CFractalCanvas : public CFractalBase
{
public:
    CFractalCanvas(CFractalParm FractalParm,CDIBFrame * pBaseDIB,
                   CDIBFrame * pFractalDIB,CDIBFrame * pDisplayDIB);
    virtual ~CFractalCanvas();
    std::vector<CIteration> GetIterations();

protected:
    virtual void Apply(int Iteration,int Column,int Row);

protected:
    CDIBFrame * m_pBaseDIB;
    CDIBFrame * m_pFractalDIB;
    CDIBFrame * m_pDisplayDIB;
    std::vector<std::vector<BYTE> > m_RGB;
    int m_nMaxIterations,m_nMaxCalc;
    bool m_bModulo;
    std::vector<CIteration> m_Iterations;
};

CRenderMandelbrotFractal - 计算曼德勃罗方程的派生类

// Class for rendering the mandelbrot fractal without angular decomposition (main case)
class CRenderMandelbrotFractal : public CFractalCanvas
{
public:
    CRenderMandelbrotFractal(CFractalParm FractalParm,
           CDIBFrame * pBaseDIB,CDIBFrame * pFractalDIB,CDIBFrame * pDisplayDIB);
    virtual ~CRenderMandelbrotFractal();
    virtual void operator() (int RowBeg,int RowEnd);
};

每种分形类型都按照上述方案派生。渲染类从canvas类派生，并实现函数运算符。渲染类对方法是通用的，Apply()方法有一个通用的实现。

多线程

由于工作的主要部分围绕多线程，并且MFC MDI架构、曼德勃罗集的数学和方程方面已经有很多现成的资料，我将只关注代码的这一方面。希望读者在执行过程中能够跟踪代码，设置断点，以便“顺应潮流”。有一个类封装了系统的多线程方面。这就是CDriveMultiThreadedFractal类。

此类是CWinThread的派生类，它驱动一组点在集合中的渲染工作。此类是计算的导演；它驱动实际工作。线程驱动程序使用CFractalBase类进行初始化，该类是多态系统的基类，可以轻松添加新的分形类型。（将UI连接起来还有更多工作，但这也不算太难。）系统确定可用的总执行线程数，然后根据行分区来划分工作。这遵循并行for循环的设计模式。这种多线程模式对于可以分割和合并的工作的基于数学的问题非常有效。出于调试目的，或者只是为了让调试器更容易观察流程，系统被简化为单个工作线程。在发布版本中，系统会扩展到尽可能多的线程。

工作被分发到执行线程。对于系统中的每个CPU，会创建两个工作线程。操作系统管理哪个CPU获得执行线程。工作是根据要渲染的图像高度来划分的。对于单核系统，将有两个执行线程。每个线程获得图像的1/2。对于双核系统，每个线程获得图像的1/4。这是多线程设计的优势。代码重用是并发发生的。

图 7 - 委托工作的驱动类

// Driver thread that carries out the function
class CDriveMultiThreadedFractal : public CWinThread
{
	DECLARE_DYNCREATE(CDriveMultiThreadedFractal)

private:
	CDriveMultiThreadedFractal() : m_phHandle(NULL) {};

public:
	CDriveMultiThreadedFractal(HANDLE * phHandle,CFractalBase * pFractal);
	virtual ~CDriveMultiThreadedFractal();
	virtual BOOL InitInstance();
	virtual BOOL PumpMessage();
	virtual int ExitInstance();

protected:
	HANDLE m_hPump;
	bool m_bPumpMessage;
	HANDLE * m_phHandle;
	CFractalBase * m_pFractal;

public:
	CFractalBase * GetFractal() {return m_pFractal;}

protected:
	DECLARE_MESSAGE_MAP()

protected:
	afx_msg void OnDoWork(WPARAM wParam,LPARAM lParam);
	afx_msg void OnEndThread(WPARAM wParam,LPARAM lParam);
};

当我第一次使用这类线程时，我偶尔会遇到一个问题，即消息未能分发，工作函数未被调用。我学到的是，线程的消息泵尚未启动，我发布的到线程的消息未能分发。为了解决这个问题，我重写了PumpMessage，并让它在准备好时发出信号。构造函数在退出前等待信号。这意味着一旦定义了线程对象的实例后构造函数返回，就可以立即将消息发布到其消息泵。这是一种处理关注点分离的好方法。线程委托工作，但它只做等待工作完成的事情。可以将此类与执行工作的类合并，但这样就会丢失关注点分离，代码将更难维护，更难为未来的设计构想进行构建。要使用此对象，我们定义自定义线程消息，例如WM_DOWORK，然后将这些消息发布到线程。请参见图7中的代码。处理自定义消息的每个函数都以相同的方式声明，形式为

afx_msg void OnFunction(WPARAM wParam,LPARAM lParam);

线程的消息映射将这些消息映射到其感兴趣的函数。可以使用WPARAM和LPARAM变量传递补充信息。

// These functions are called by PostThreadMessage
BEGIN_MESSAGE_MAP(CDriveMultiThreadedFractal, CWinThread)
    ON_THREAD_MESSAGE(WM_DOWORK,&CDriveMultiThreadedFractal::OnDoWork)
    ON_THREAD_MESSAGE(WM_ENDTHREAD,&CDriveMultiThreadedFractal::OnEndThread)
END_MESSAGE_MAP()

void CDriveMultiThreadedFractal::OnDoWork(WPARAM wParam,LPARAM lParam)
{
    // Do the work
    int RowBeg = (int)wParam;
    int RowEnd = (int)lParam;
    try
    {
        // Carry out the work for this range
        m_pFractal->operator()(RowBeg,RowEnd);
    }
    catch (...)
    {
    }

    // Signal completion
    HANDLE & hHandle = *m_phHandle;
    SetEvent(hHandle);
}

void CDriveMultiThreadedFractal::OnEndThread(WPARAM wParam,LPARAM lParam)
{
    // Delete the work object
    if (m_pFractal)
        delete m_pFractal;

    // End the thread
    PostQuitMessage(0);
}

为了完成工作，必须存在一个能够容纳工人的工厂。我们提前知道我们有多少个工人线程，所以我们创建一个能够容纳这些工人数量的工厂。

// Construct the factory that does the work
CDriveMultiThreadedFractal ** ppDriveMultiThreadedFractal = 
                              new CDriveMultiThreadedFractal * [nTotalThreads];

现在我们想创建我们的工人。我们的工人可以是任何一种我们支持的分形类型，因为我们使用的是一个通用的基类和接口来表示我们如何完成任务。

for (int iHandle = 0;iHandle < nTotalThreads;++iHandle)
{
    // Construct the objects that do the work
    CFractalBase * pMultiThreadedFractal = NULL;
        if ()
            pMultiThreadedFractal = new Fractal1();
        else if ()
            pMultiThreadedFractal = new Fractal2();
        else if ()
            pMultiThreadedFractal = new Fractal3();
        etc...

现在我们在工厂中构造我们的工作场所，并将我们的工人在他们的工作区就位，准备开始他们的任务。

// Construct the Fractal thread driver
CDriveMultiThreadedFractal * 
      & pDriveMultiThreadedFractal = ppDriveMultiThreadedFractal[iHandle];
pDriveMultiThreadedFractal = new CDriveMultiThreadedFractal
                                 (&arrReadHandle[iHandle],pMultiThreadedFractal);

现在我们将工作分发给我们的工人，并等待他们完成任务。

// Process the number of segments that make up the Fractal
int MRPT = MR / nTotalThreads + 1;

// Process the number of threads of work
for (int iThread = 0;iThread < nTotalThreads;iThread++)
{
	// Set the range of rows to process
	int nBegRow = iThread * MRPT + 1;
	int nEndRow = min(nBegRow + MRPT - 1,MR);

	// Perform the work for this range
	CDriveMultiThreadedFractal * pDriveMultiThreadedFractal = 
                                    ppDriveMultiThreadedFractal[iThread];
	pDriveMultiThreadedFractal->PostThreadMessage(WM_DOWORK,nBegRow,nEndRow);
}

// Wait for all the work to complete for this set of ranges, the driver signals these events
WaitForMultipleObjects(nTotalThreads,&arrReadHandle[0],TRUE,INFINITE);

消息映射处理两个重要的线程消息。它处理工作消息和退出消息。消息本身声明如下。

#define WM_DOWORK (WM_APP + 100)
#define WM_ENDTHREAD (WM_APP + 101)

将它们声明为大于WM_APP且小于等于WM_APP + 0xBFFF的值很重要。

其余代码基于一个通用的实现，该实现将工作单元分发到它所持有的对象。这种设计模式的优点在于，像这样的通用多线程驱动类可以适应委托工作给任何实现函数运算符的对象。对我来说，函数运算符作用于代表我想计算的方程部分的数值范围。比我更擅长编程的人可以巧妙地使用模板化这个驱动类来持有任意类型的对象T，并将其用作工作工厂设计模式。我使用这种设计模式的其他方式包括图像数据的多线程处理。CColorOp类再次演示了这种模式。

更新

• 已上传到Git。 https://github.com/andybantly/MFC-Fractal
• 2017年9月20日 - 修复了轨道陷阱中的一个bug
• 2016年6月25日 - 添加了微小缩放和连续微小缩放。文件格式的小改动，以默认嵌入图像，方便与可能未添加图像的文档共享。
• 2016年6月18日 - 包含源代码的所有分形类型。增加了支持透明颜色的图像图片框。图片和文本框大小调整。使用从CDocManager派生的新类打开多个文档。飞入效果更流畅，并与消息泵相连。修复了bug和文件格式更改。
• 2013年10月24日 - 在分形创建对话框中添加了轨道陷阱（选择茎）
• 2013年5月9日 - 添加了PayPal捐赠按钮
• 2013年5月5日 - 对方程 AX²+/- BY² < Bailout Radius 中的发散测试进行了精细控制。
  • 模式1是 AX² + BY² < R。
  • 模式2是 AX² - BY² < R。
  • 模式3是 BY² - AX² < R。
  • 模式4是 |AX² - BY²| < R。
• 2013年5月3日 - 完全的颜色编辑，可以在分形渲染之前和/或之后进行。
• 2013年4月19日 - 提高了Buddhabrot的性能
• 2013年4月18日 - 添加了Buddhabrot和Anti-Buddhabrot分形。Buddhabrot在高度为4096时，颜色和迭代次数设置为8192或更高时，看起来非常棒。警告，渲染将耗费大量时间！
• 2013年4月14日 - 更新了源代码，见下文
• 2013年4月13日 - 性能增强
• 2013年4月8日 - 添加了曼德勃罗凤凰2.0分形。
• 2013年4月7日 - 添加了朱利亚凤凰分形。朱利亚分形对话框允许手动编辑边界坐标，从而可以手动缩放到有趣的坐标。
• 2013年4月6日 - 添加了朱利亚龙分形
• 2013年4月6日 - 修复了角度分解的调色板选择错误，当基本颜色固定在一个在渲染过程中不应该出现的常规调色板颜色时。
• 2013年4月5日 - 新的基于角度分解的着色方案，看起来更自然，数学上也更令人愉悦。
• 2013年4月4日 - 首次仅二进制更新系统，包含龙和凤凰曼德勃罗式曲线。在现有文档中飞入缩放。更新了捆绑文档，包括4条有趣的龙曲线。请参见Dragon.frc、Dragon II.frc、Dragon III.frc和Dragon IV.frc。注意 - 这些与现有源代码不兼容。
• 2013年4月14日 - 更新了增强版源代码，但仅包含曼德勃罗集和朱利亚集。其他类型仅在二进制版本中可用。源代码包含着色bug修复和优化的类架构。
• 2013年4月4日 - 现有文档中的飞入缩放bug修复。最后一次源代码更新。
• 2013年4月3日 - 计算和颜色应用的算法变更。
• 2013年4月1日 - 编辑颜色和文本。将颜色数量与迭代次数分离。
• 2012年11月22日 - 将颜色动画保存为AVI文件
• 2012年11月20日 - 改变了阶梯颜色，以及更快、更平滑的颜色动画
• 2012年11月12日 - 文本现在可以在没有背景色的情况下绘制
• 2012年11月11日 - 添加了在分形中添加装饰性文本的功能
• 2012年11月4日 - 修复了保存和加载包含嵌入图像的文档时的bug
• 2012年11月3日 - 改进了混合功能，以便基本颜色和分形颜色可以选择性地以不同不透明度（alpha混合）与图像混合。
• 2012年6月23日 - 线程稳定性。我发现并非所有CPU都喜欢执行线程清理的代码，因此在向线程消息泵发布WM_ENDTHREAD消息后，逻辑上有一些小的调整。
• 2012年4月15日 - 3D效果和图像平滑
• 2012年4月12日 - 基于角度分解的着色
• 2012年4月10日 - 更多动画选项
• 2012年4月8日 - 增加了动画化颜色调色板的能力。请参见低分辨率视频ColorBleed.mp4。
• 2012年4月7日 - 添加了朱利亚分形类型，并能够从曼德勃罗集中的一个点渲染它。还增加了设置背景图像以在基本颜色处显示的功能。