Lab 9-1: Complex 的應用與 Mandelbrot 圖形界面

   
實習目標 使用實習 3-1, 4-2 中的Complex 類別
做一個 Mandelbrot 碎形圖形
練習與基本圖形界面的合作

練習視窗界面程式的 debug
   
步驟一 請執行 Mandelbrot02a 程式

這個程式會顯示 Mandelbrot 碎形 (fractal) 圖形如下圖 (mandelbrot.mp4):

這個碎形圖形其實是根據複數平面上每個複數點 c 的一個特別性質畫出來的, 對於任意一個複數 c, 可以定義一個數列 z0 = 0, zi = (zi-1)2 + c; 如果我們規定複數 zi實部或是虛部的絕對值超過 2 就稱為 "發散", 對於每一個複數 c 來說都會存在一個 i 值, 只要大於這個 i, zi就會發散, 如此每一個複數點 c 都有一個對應的 i 值, 將這些 i 值在視窗中用不同的顏色表示出來就出現上面這張圖, 例如上圖中外圈草綠色部份的那些點所對應的 i 值都是相同的, 外圈的 c 離原點比較遠, | c | 的值比較大, 所以數列比較快發散, i 可能是 2 或 3 吧。

參考資料 Mandelbrot set, Julia set, Fatou set

Online generation: Mandelbrot set, Julia set

Mandelbrot zoom to 10198 (9 分 10 秒的視訊, 看一下, 讚嘆一下, 看完了嗎? 剪下幾張回顧一下 1, 2, 3, 4, 5, 6, 有沒有覺得 全面啟動 inception 裡面的夢境層數太少了?)

Mandelbrot zoom to 10225, Mandelbrot zoom to 106044


簡單的互動程式 1015, ↑↓← → 可以移動觀看區域, z 可以放大, s 可以縮小; 繪圖是用簡單的 SFML 做的

步驟二 這個程式因為使用視窗的界面, 所以你沒有辦法用 cout, cin 來偵錯, 如果程式不幸出錯或是沒有顯示的話你還是需要一步一步地 debug, 當然你可以用 VC 的 source debugger 一步一步執行來找錯誤, 不過這是最慢的方法, 同時在過程中你也會看到一大堆根本不是你寫的程式... 很困擾呢...

在使用 Microsoft Foundation Class (MFC) 製作視窗界面時, 我們常用一個 TRACE 巨集來取代 cout, TRACE 的用法和 printf 很像, 相信你還沒有忘記怎樣用 printf, 例如:

    TRACE("m_data=%d\n", m_data);
    TRACE("m_doubleData=%f\n", m_doubleData);
這些敘述的輸出會到哪裡去呢?

如果你用 debug 模式(偵錯/開始偵錯 F5)執行的話, 會跑到 output 視窗中, 如果你是正常執行(偵錯/啟動但不偵錯 Ctrl-F5)的話, 可以開啟 dbwin32 程式來顯示偵錯的結果

步驟三

接下來我們介紹如何一步一步地產生這個碎形圖形, 首先你需要把繪圖座標對應到複數平面, 例如將畫面上 500 x 500 像素 (pixel) 的區域對應到複數平面上 (-1.65, -1.15)-(0.65, 1.15) 的方形區域上, 一般在繪圖的系統中橫軸是 x 軸, 向右是正的方向, 縱軸是 y 軸, 向下是正的方向, 所以視窗左上角是 (0,0), 右上角是 (499, 0), 左下角是 (0, 499), 右下角是 (499, 499); 複數平面就是數學上的定義, 實數軸向右是正的, 虛數軸向上是正的:

上圖中視窗左上角的像素 (0, 0) 對應的複數座標為 (-1.65, 1.15), 視窗左下角的點座標 (0, 499) 對應的複數座標為 (-1.65, -1.15), 視窗右上角的點座標 (499, 0) 對應的複數座標為 (0.65, 1.15), 視窗右下角的點座標 (499, 499) 對應的複數座標為 (0.65, -1.15), 你可以用一個簡單的計算來求出所有 500x500 個點個別的複數座標, 例如:

    int i, j;
    Complex c;
    double step = range / (windowSize-1);
    for (i=0; i<windowSize; i++)
        for (j=0; j<windowSize; j++)
            c = Complex(centerX-range/2.0+i*step, 
                        centerY+range/2.0-j*step);
上面迴圈中每一次算出來的複數 c 就是每個座標點 (i, j) 所對應的複數 c 的值。

接下來我們需要測試繪圖區域內每一個點, 看看在下列的測試公式下, 每一個 c 值發散的狀況:

    令複數 z 的初始值為 0+0i
    令每一個點的複數座標為 c
    
    重複計算
            z = z * z + c

    每次運算後, 如果 z 的實部或是虛部的絕對值超過 2
    的話, 就表示已經發散掉了, 此時請記錄由開始到
    發散需要計算上式幾次, 通常在前 50 次計算中,
    會發散的點就已經有百分之九十九都發散掉了, 
    剩下的也幾乎不會發散了
上圖中同一顏色的那些點代表它們都在算到相同次數時發散掉的 (實部或是虛部不在 2 與 -2 之間的)

上面是一個很漂亮的圖形, 而且如果放大來看的話, 它會不斷重複類似的圖案, 請執行 Mandelbrot03a, 在自然界中這種圖形很多, 這種圖形也常常可以用簡單的數學公式描述出來

如果發散的條件改成 "當 z 的實部和虛部的絕對值超過 2" 的話, 還是一個碎形圖形, 但是看起來有點醜, 沒有那麼賞心悅目了

如果你等一下子實作時看到像底下這樣子的圖

這是 Complex 的實作出了一點問題

步驟四

請下載圖形界面程式碼 Mandelbrot02b_vc2010.rar, 解壓縮出來到硬碟中(請不要放在隨身碟裡, 隨身碟的檔案系統是FAT32或是FAT16, vc2010 的圖形介面程式碼需要放在NTFS的檔案系統裡, 才能順利用debug模式編譯測試!), 請編譯並且執行

請一定要先編譯並且執行, 解壓縮出來的程式碼至少有 1000 列以上, 如果沒有辦法編譯的話, 你需要先處理, 不要等你增加了一些程式碼以後, 弄不清楚到底是你的問題還是系統安裝的問題 (VC 2010 必須要裝 service pack 1 以後才能在這個專案中順利運作, VC 2010 / 2012 / 2013 Express 也沒有辦法開發 MFC GUI 程式)

執行起來以後你應該可以看到顯示的視窗中是全部空白的, 選單中有 檔案/ MaxIteration 設定的選項, 這個選項可以讓使用者在專案中應用你先前寫的 Complex 類別來撰寫程式, 請下載你先前製作好的 Complex 類別的程式碼 (請注意, 大家寫的 Complex 類別基本介面都是一樣的,如果你發現你的 Complex 物件表現不太對,可以借用別人的來測試比較看看, 這是物件化的程式一個很重要的好處)

步驟五 在類別檢視視窗中你可以找到 Mandelbrot 類別, 打開這個類別你可以看到下列類別的定義以及空的成員函式:
    class Mandelbrot  
    {
    public:
    	Mandelbrot(double centerX, double centerY, double range);
    	void generateData(int ** &data, 
    	                  int windowSize, 
    	                  int maxIterations);
    	void deleteData(int ** &data, int windowSize);
    private:
        ...
    };

你可以在建構元

    Mandelbrot::Mandelbrot(double centerX, double centerY, double range) 
    {
    }
函式中加一列敘述 TRACE("Mandelbrot::Mandelbrot() is called\n");, 記得執行 dbwin32, 然後編譯執行這個程式, 看到列印出來的訊息, 你會發現這個建構元函式已經被呼叫過了, 也就是說這個物件已經產生了, 這個 Mandelbrot 類別的物件最主要負責計算每一個複數點所對應發散的 i 值, 用來告訴圖形界面程式該顯示什麼, 你剛才下載的圖形界面程式執行起來時會自動建構一個這個類別的物件

傳入建構元函式的參數是繪圖區域中心點的複數座標, 例如 (-0.5, 0), 以及繪圖區域的寬與高 (目前所畫的是一個方形區域), 例如 2.3, (你可以用 TRACE 敘述看一下), 傳進來的資料請在 Mandelbrot 類別中設計資料成員記錄下來

步驟六 接下來我們看到 generateData() 這個成員函式, 圖形介面程式每次需要計算整個平面的複數對應的 i 值時就會呼叫這個函式, 它應該要配置如下圖的資料陣列, 計算每個點的 i 值, 並且將陣列的記憶體起始位址放在 data 變數內:

void generateData(int ** &data, int windowSize, int maxIterations);

這個成員函式應該要檢查傳入的指標, 如果是 0 的話, 代表這個函式第一次被呼叫到, 需要動態地配置一塊二維的整數 (int) 陣列, 其架構如下圖

上圖中陣列的大小都是 windowSize, 下一個步驟裡會在這個陣列裡填入資料, 傳回去給繪圖的程式碼使用, 不過這個陣列是你配置的, 繪圖程式碼並沒有幫你刪除, 習慣上還是留給配置者自己刪除比較有道理, 所以請在這個函式下次被呼叫到時 (傳進來的指標不是 0 的時候), 先刪除所指到的記憶體以後再重新配置, 然後才計算每一個 i 值。

為什麼需要刪除再重新配置呢? 為什麼不直接用上一回配置的陣列就好了? 這其實是擔心圖形介面呼叫這個 generateData() 函式時如果傳入的 windowSize 會變動, 前一次如果配置的陣列比較小時就會發生記憶體的存取錯誤!! (不是說好 windowSize 是 500 的嗎?? 如果這麼相信它, 你就直接用 500 囉, 不要在意傳進來的 windowSize 是多少了, 這是理想狀況, 萬一不是這樣呢? 這個 gennerateData 訊息是別的物件傳遞給 Mandelbrot 物件的, 主控權不是 Mandelbrot, 所以還是尊重一下傳進來的數值吧, 不要做太多的假設)

你可以先把配置好的陣列的每一個元素都設成一個固定的數值 (例如 data[i][j] = 10;) 然後編譯和測試, 不必等到算出發散的 i 值都算出來了才開始測試。

步驟七 這個 data 陣列的每一個元素代表繪圖區域中一個像素 (pixel), 依照一般的慣例, data[0][0] 代表視窗的左上角, data[0][windowSize-1] 代表右上角, data[windowSize-1][0] 代表左下角, data[windowSize-1][windowSize-1] 代表右下角, 你需要計算那個點的複數座標, 依照步驟三中的公式算算看在做到第幾次時 z 的實部或是虛部的絕對值超過 2, 然後記錄在 data[i][j] 中, 請注意傳入的 maxIterations 數值是你在測試時的最大次數 , 如果超過這個數值還沒有發散, 就不要再做下去了, 都當成是 maxIterations 時會發散

在你真正去算 z 的運算式並且算出 data[i][j] 之前, 你可以先把 data[i][j] 設定成一些簡單的圖樣來測試一下, 例如 (直紋):

    for (i=0; i<windowSize; i++)
        for (j=0; j<windowSize; j++)
            data[i][j] = i%256;
或是 (矩形)
    int i, j, min_i, min_j;
    for (i=0; i<windowSize; i++)
        for (j=0; j<windowSize; j++)
        {
            min_i = i<(windowSize-i) ? i : windowSize-i;
            min_j = j<(windowSize-j) ? j : windowSize-j;
            data[i][j] = min_i<min_j ? min_i : min_j;
        }
請注意 data[i][j] 的數值一定要維持在 [0, 255] 間,否則繪圖程式會當掉 (這是這個繪圖程式和你之間定義的介面)
步驟八 上面計算步驟中你需要用到 Complex 的複數類別, 同時類別中要提供
    Complex add(const Complex &rhs);
    Complex multiply(const Complex &rhs);
兩個成員函式, 這兩個成員函式我們在前面的實習中定義過類似的東西, 不過那時定義的是 add(const Complex &rhs)實際上也許叫做 addEqual(const Complex &rhs) 比較貼切, 也就是把 rhs 的複數物件和自己這個物件加起來, 並且修改自己這個物件的內容, 你可以直接用上次寫的成員函式來實作 z = z * z + c, 程式碼看起來如下
    z.multiplyEqual(z);
    z.addEqual(c)
你也可以修改你的函式 addEqual() 為沒有 side effect 的 add(), 讓它在把兩個複數加起來以後, 不要修改自己那個物件, 而是以傳值 (call by value) 的方式把一個 Complex 的物件傳回, 如此你在實作 z = z * z + c 時可以用類似下列的敘述:
    z = c.add(z.multiply(z));
或是
    tmp = z.multiply(z);
    z = tmp.add(c);
請注意因為我們現在做的事情是運用 MFC 撰寫視窗應用程式, 如果你直接將前面實習的 Complex.cpp 和 Complex.h 拷貝進來的話, 請在你的 Complex.cpp 檔案的第一列加入 #include "stdafx.h" 如此 compiler 才不會跟你抱怨說它找不到 pch (precompile header) 檔案
步驟九 void deleteData(int ** &data, int windowSize);

函式中需要實作將步驟六中配置的二維陣列刪除的程式碼

一切順利的話你的執行畫面上應該可以看到 Mandelbrot 的顯示了

步驟十 請測試一下選單 "檔案/MaxIterations" 設定, 當使用者更改過這個設定值 (10~120) 後, 你提供的 generateData 會重新被呼叫到, (你可以用 TRACE 敘述驗證這件事) 同時 maxIterations 參數會有新的數值傳入

由於你在這個程式中有動態配置記憶體, 請特別在 dbwin32 視窗中確定一下程式結束時有沒有 memory leakage (請注意, 你不需要使用先前介紹的 memory_leak.h memory_leak.cpp , 使用MFC dll 的程式自動會把記憶體遺漏的訊息顯示在 dbwin32 視窗中, 你可以試著配置一小塊記憶體, 程式結束前不要刪除, 看看是否會偵測到)

步驟十一 請助教檢查後, 將所完成的 專案 (只需保留 .cpp, .h, .sln 以及 .vcxproj 檔案即可; 刪除掉 .suo, .sdf, .filters, .users, debug\ 資料匣, 以及 ipch\資料匣下的所有內容) 壓縮起來, 選擇 Lab9-1 上傳, 後面的實習課程可能需要使用這裡所完成的程式
偵錯 有的時候同學在做這個實習的時後, 會遇見不太容易找的 bug, 使得圖形顯示錯誤, 到底是哪裡錯了, 是 Complex 裡面寫錯了? 還是 Mandelbrot 這裡的程式寫錯了? 因為計算過程中都是浮點數, 常常看到了有錯誤的東西也不容易察覺出來, 這是很討厭的狀況。

不過因為我們現在有封裝良好的物件, 如果你懷疑物件的功能有問題, 例如 Complex 物件, 最簡單的方法就是換一個相同規格的物件來測試比對一下, 例如你可以下載 ComplexObj.rar, 先把你的 Complex.cpp 和 Complex.h 由專案中移除 (不是刪除喔!), 把 ComplexObj.rar 裡面的 Complex.h Complex.obj 運用 "加入現有項目" 加到專案裡面, 稍微調整一下Mandelbrot 裡面的程式來運用這個 Complex 物件的介面, 然後編譯測試, 看看結果是不是對的? 如果換過以後發現結果是對的, 糟糕, 那就表示你原來用的 Complex 類別裡面的功能有一些問題...
 

再給大家一點點 MFC GUI 的範例

  1. 簡單的表單應用程式
    範例程式碼
    , 完整程式製作過程 (android com.adobe.flashplayer.apk) ,
    範例二
    , 範例二程式碼

  2. MFC SDI 應用程式: GUIComplexCalc, 完整程式製作過程 (android com.adobe.flashplayer.apk)

  3. BattleShip, 範例, (原始程式)
  4. 簡易計算機 範例 介面 (原始程式)
  5. 接龍 範例1 範例2 (介面原始程式 vc6)
  6. 貪食蛇, 範例(沒有偵測障礙物) (原始程式)
  7. 踩地雷 範例 (原始程式) 介面 (介面原始程式)

C++ 物件導向程式設計課程 首頁

製作日期: 04/11/2013 by 丁培毅 (Pei-yih Ting)
E-mail: pyting@mail.ntou.edu.tw TEL: 02 24622192x6615
海洋大學 電機資訊學院 資訊工程學系 Lagoon