openGL - 何時該用glPushMatrix() 和 glPopMatrix()

這問題困擾了我一陣子，有很大的因素是被這學期的圖學作業影響...
回到正提，這問題在"openGL編程指南"中說的有點隱晦(個人認為)。

這問題是發生在我使用了gluLookAt()函式後發現的，從書中範例我們可以感受一件事，glPushMatrix()和glPopMatrix()的目的是為了讓編程過程變得簡單且容易了解，但我似乎無法清楚定義"應該在何時加入這兩個函數會讓程式變得容易理解"。


首先要先認清一件事，openGL FAQ 8.010開宗明義即說明：在openGL中的攝影機，永遠都在原點(0,0,0)的位置，openGL為了假裝出移動攝影機的樣子，必須移動場景對整個世界場景做攝影機的逆空間轉換。(OpenGL FAQ and Troubleshooting Guide - Q8)，而gluLookAt()函式，是個工具函式，意思就是它包裝了一些openGL的基本函式在內，並不是一個原生函式，套用上面說的話，表示gluLookAt()中使用了一些glTranslate()或glRotate()等類型的函式，所以如果程式中寫了一行gluLookAt(0,0,3,0,0,0,0,1,0)，實際上是把所有的物體都先往-Z軸推離攝影機3的距離，才繼續之後的轉換。

那麼現在來想一個簡單的程式，我希望攝影機放在(0,0,3) 且朝著(0,0,-5)看著，而有一個球可以在(0,0,-4)的位置自轉，因此球和攝影機應該要相距7的距離，程式可能如下：


glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
gluLookAt(0,0,3,0,0,-5,0,1,0);
glLoadIdentity();
glTranslatef(0,0,-4);
glRotatef(year,0,1,0);
glutSolidSphere(1,40,40);

老師說做任何事之前要先將當前矩陣(current matrix, CM)清空，確保轉換正確，所以第4行的glLoadIdentity()做了這件事。但是別忘記第3行的gluLookAt()先把東西都推離了3的距離，再把球更推離了4的距離，而這個glLoadIdentity()的存在，抹殺了gluLookAt()的目的，導致球只離攝影機4的距離，結果錯誤。

因此，你可以說：" 那我把glLoadIdentity()拿掉吧! "，會造成什麼結果? 結果就是每次球旋轉時，也相對的更遠了一點，結果還是錯。

從這邊可以發現，其實，我們並不是要一個會把CM完全清空的方法，也不是放任不管，而是我們需要一個手段可以"記錄CM的樣子"，並且在事情做完後，CM可以回復到"之前記憶的樣子"，而這就是glPushMatrix()和glPopMatrix()的功能!!

glPushMatrix()將當前矩陣push入一個stack，反之glPopMatrix()取出stack頂端的矩陣，因此我們就可以"記憶gluLookAt()後的CM長像"，並且在所有轉換都做完之後，又再度回到"gluLookAt()後的CM長像"，而且重點是這兩個函數是硬體實作且hard dependent，速度更快，因此可以用一句話形容：

glPushMatrix()是記住自己現在的位置，而glPopMatrix()是回到之前記住的位置!!


所以當你需要記住目前位置，且要再回到原位，而撰寫程式時不想要一直考慮CM有沒有跑掉的時後，就是使用這兩個函數的時機點了。


而stack的深度與硬體有關，可以用glGetIntegerv(GL_MAX_MODELVIEW_STACK_DEPTH, *GLint *params)來查詢，或者到OpenGL capabilities report: GL_MAX_MODELVIEW_STACK_DEPTH查詢你的顯示卡/顯示晶片是否是常見的32深度。

[心得] 盜墓筆記

        話說我這個人其實很少看小說，我還記得上一本小說叫做"藍熊船長的奇幻大冒險"，聽名子就覺得有點幼稚XD，那是我好幾年前看的小說了，而今天我要說的是這本很有名的盜墓筆記。

        這一系列的小說是同學推薦的，不然我想我也不會特別去注意有沒有新小說。盜墓筆記源自網路小說，作者為"南派三叔"，後來出成書，我個人認為前中段內容十分的精彩! 內容是講述盜墓者吳三邪的故事，七星魯王宮、血屍墓、雲頂天宮、張家古樓等等，太多太多的主題使整篇故事內容豐富，作者文筆也十分了得，在勾勒場景上非常生動，無論是激烈的逃命奔跑，還是一翻兩瞪眼的生死關卡，亦或是闡述似是非是的古史神化，都有種讓讀者身歷其境的臨場感，甚至講到可怕之處，你還會不時的回頭看看身後的陰暗處，是不是也有如同小說中的妖魔鬼怪XD。

        此外這篇受人推崇的還有一個原因，就是文中所使用的專有名詞、術語，有許多都是真有其事，或是真有其人，曾有書評寫到："除非你真的是盜過墓，否則豈能知曉這些古玩器具"，不過作者到是一直否認啦~只說自己是個骨董商。我想故事之所以吸引人，就是讓讀者有那種真真假假，假假真真，彷彿故事是真的，但卻又讓你感到疑惑；而在你感到疑惑的瞬間，追求未知的欲望又席捲你的全身，讓你一頁一頁不停的翻下去，我不知道為了讀到最後，熬了多少夜阿(笑)。

        這不是什麼勵志小說，我把它歸類為閒書。如圖所示，到雲頂天宮之前非常的精彩，作者有用不完的點子，扣不完的連環謎團，此外，最後的張家古樓也是非常的精彩，我覺得不要去探究小說中那些人物是否真偽，單純的享受三叔給你的不安與恐懼就好XD

        但很可惜的我不得不說，結尾收的不好，有太多的連鎖迷團，作者後來都沒辦法釐清了，無法給讀者一個完整的交待，此外結局的鋪陳屬於悲劇英雄式的開放結局，由最佳男配角悶油瓶進入地底青銅巨門後畫下終點，個人認為這結局不具凝聚力，不是大眾所習慣的"長篇小說後應該會有個happy ending"，留給讀者的是失落的主角以及文中所宣告的"10年"，算是比較可惜的，不過...好歹這個網路連載前前後後也搞的5年!! 也真他X的久阿...

最後感想就是，這是一套可以讓你發洩平日壓力的優良小說XD

ALGO-maxnum sum of sub matrix/sub array

題目：

Given an n by n two-dimensional array arr (1 < = n < = 100) of arbitrary integers, find the maximum sub-array. Maximum sub-array is defined to be the sub-array whose sum of integer elements are the maximum possible.

想法：

以暴力法思考：

int sum=0;

for(i=0~n-1)

    for(j=0~n-1)

        for(p=0~n-1)

            for(q=0~n-1)

                for(s=i~p)

                    for(t=j~q)

                        sum = sum+M[s][t];

若是窮舉n*n中所有的子矩陣和，時間複雜度是O(n^6)。

但這是一個DP approach題目(對不起...我不知道什麼是DP approach...)。

假設給予一個n*n矩陣M，element值可正可負，則我創建另一n*n矩陣S，其中S[i][j]值為M[0][0]~M[i][j]所有元素的和：S[i][j] = M[i][j]+S[i-1][j]+S[i][j-1]-S[i-1][j-1]，若i-1<0或j-1<0則該項忽略，初始值S[0][0]=M[0][0]。

for(i=0~n-1)

    for(j=0~n-1)

        S[i][j] = M[i][j]+S[i-1][j]+S[i][j-1]-S[i-1][j-1];

則問題演變成：右圖是一矩陣M，紅色區域是任取一個想要計算的範圍(i,j)~(p,q)，可以看成從藍色方塊-兩個綠色方塊+橘色方塊，而這些方塊的和已經在S中，則計算從任意(i,j)~(p,q)子矩陣和的方法 = S[p][q]-S[p][j-1]-S[i-1][q]+S[i-1][j-1]

演算法：

for(i=0~n-1)

    for(j=0~n-1)

        for(p=0~n-1)

            for(q=0~n-1)

                sum = S[p][q]-S[p][j-1]-S[i-1][q]+S[i-1][j-1];

複雜度：

1.建立S矩陣 : O(n^2)

2.DP計算最大子矩陣和 : O(n^4)

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

+                                     = O(n^4)

類似問題：最大/最小子矩陣和

UVa108