2008年12月26日 星期五

UVa 110 Meta-Loopless Sorts

相當有趣的一題....寫程式產生器
用自創的Modified-Permutation Algo ( ̄▽ ̄#)﹏﹏
第一次寫有點痛苦,過了幾天醞釀過想法後,寫起來很順很快就AC了
距離連號解題剩下最後一題107了..

2008年12月21日 星期日

I have a dream

I have a dream.....


就是....一次AC.....


最好不是渣渣題....


到底什麼時候才能達成呢?

2008年12月14日 星期日

UVa 109 SCUD Busters

解題策略

典型的凸包 (Convex Hull ) 問題。我是採用 Graham's Scan 來解。作法可以參考維基條目 Graham's Scan,我就是照著條目裡的算法原封不動實做的。

本題要找出所有被飛彈摧毀的王國的國土面積總和。過程中一共有兩件事要解決,第一個要知道每個王國的國土面積,第二個要能判斷飛彈落點有沒有打中王國。

求國土面積,要先對王國內的所有的發電廠位置求凸包,然後由凸包去計算多邊形面積 (題目頁有給多邊形面積公式) 。 判斷飛彈落點是否落在國土內,也是以凸包為基礎,沿著凸包的每個邊判斷,如果飛彈落點都在邊的左側,那就表示打中了!

注意

使用Graham's Scan 時要特別注意共線問題,尤其是起始點三點共線,例如 (0,0) (1,1) (2,2) (1,3) ,求出來的凸包應該是 (0,0) (2,2) (1,3)。

閒聊

@2011.10.07
有點囉嗦的題目。2008年底我第一次解這題,因為過程有點曲折,所以花了好幾天才解出來,而且一直搞不定 std::sort( ) 的判斷函數,現在重寫一遍,感覺比較清爽一些了!

2008年12月9日 星期二

線性代數的世界作者 Dr. Strang 妙語如珠

  1.  "you can't add apples and oranges."「你不能把蘋果和橘子加在一起」
    --談為什麼需要向量

  2. The central porblem of linear algebra is to solve a system of equations.
    線性代數的核心問題就是要解方程組!

  3. It is also common sense: If you put on socks and then shoes, the first to be taken off are the ___.
    常識也告訴我們:假如你先穿襪子再穿鞋,那麼脫的時候,首先該脫掉___。
    --談為何AB的反矩陣是B-1A-1

  4. Ax combines the columns of A while xTAT combines the rows of AT
    Ax線性組合了A的諸行,而xTAT線性組合了AT的諸列。
    --談為何(AB)T = BTAT

最近看Gilbert Strang寫的『Introduction to Linear Algebra』,Strang教授講法生動,不論是趣味的例子,或者是一句話直搗觀念核心,都常讓我拍案叫絕。

比起補習班名師的講義,研讀起來樂趣大多了。有機會再補上更多句子。

2008年12月5日 星期五

UVa 476 Points in Figures: Rectangles

渣渣題三號

判斷點是否在矩形內。在頭腦不清的凌晨三點,犯了一些低級錯誤,還好很快就AC了。
我最近的休閒娛樂就是寫渣渣題....

2008年12月4日 星期四

UVa 458 The Decoder


Buffered加速版 0.020s。看到很多0.000s,這我真的不知道怎麼做了....
該不會是用組語寫吧...這題用組語寫似乎很簡單....

2008年12月3日 星期三

2008年12月2日 星期二

UVa 104 Arbitrage

解題策略

Some Hints about uVA 104 
gits大大說得很清楚,我就不囉唆作法了。

閒聊

苦思良久的UVa 104終於在 gits 幾乎手把手的帶領下寫出來了,了結了多天以來的心中懸念。XDDD稍微變化題,馬上就把我土法煉鋼學會的Floyd-Warshall 打回原型。連F-W要用二維還是三維陣列來建表都搞不清楚,唉,由這題可以知道我的DP/Graph有待磨練。

只有與問題面對面的對決,在測資跟Bug中打滾一番後,才能對Algorithm有更深刻的體會吧。這也是我寫ACM的目的與樂趣所在。不過...這題還是有點心虛阿.....orz 只能說敗給你了Modified Floyd-Warshall,還未夠班....總有一天我要能秒殺這題。


[原始碼已經隱藏]

2008年12月1日 星期一

[ACM] Some hints about uva 104 (Modified Floyd-Warshall)

by gits
Original Thread http://online-judge.uva.es/board/viewtopic.php?t=7292

Well, I'll assume you understand what the problem asks. You have to find the shortest sequence that yelds a profit (not the one with the greatest profit!). If there is more then one sequence with the same length, any of those is valid.

Now, you can't just try with brute force (trying all combinations) because it'll be too slow and you'll get Time Limit Exceeded. However, there's a well known algorithm, Floyd-Warshall, which will find all the shortest paths between every node to the others in just O(n^3) time. You can find more info about F-W in the net. In my previous post I said how you have to change the general F-W algorithm to work for this particular problem...

As for floating point errors, most numbers representation isn't totally acurate; for instance, 0.1 is usually stored as 0.10000000000000001. After some operations, the error may influence the final result. Again, search the net for floating point errors. However, you won't have to deal with these errors to solve this problems (at least I didn't).

Hope this helps


=================================
Floyd-Warshall finds all the mininum paths between every vertex and all the other vertexes. However, in this problem you not only have to find the shortest path, it also has to make a profit of more than 1%.

Simple F-W goes like this:
// initialization
for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      best[i][j] = path[i][j];
      path[i][j] = i;
    }
}

for (k = 0; k < n; k++) {
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (best[i][k] + best[k][j] < best[i][j]) {
                best[i][j] = best[i][k] + best[k][j];
                path[i][j] = k;
            }
        }
   }
}

For this problem, instead of having best[i][j] and path[i][j] I have best[i][j][s] and path[i][j][s], which means "best path from i to j in s steps". I also have an outer loop, representing the number of steps.
// initialization
best[i][j][s] = 0, for all i,j,s
best[i][j][1] = input for the program
best[i][i][1] = 1, for all i
path[i][j][1] = i, for all i, j

for (steps = 2; steps <= n; steps++)
    for k...
        for i..
            for j..
                tmp = best[i][k][steps-1] * best[k][j][1]
                if (tmp > best[i][j][steps]) {
                    best[i][j][steps] = tmp;
                    path[i][j][steps] = k;
                }
What we are doing is to find the most profitable way to go from i to j in "steps" steps, trying for each to use k as the point just before j. As you can see, this is O(n^4) but since max n is 20 it's ok.

After this, you scan though best[i][i][s] (best way to go from i to i again, in s steps). Remember that you want the minimum number of steps that yields a profit; so it's this:
for (steps = 2; steps <= n; steps++)
    for (i = 0; i < n; i++)
        if (best[i][i][steps] > 1.01) {
            // score!
        }
If the "if" never matches, then there is no arbitrage sequence. If it matches, you have to print the path. To print the path, use path[i][i][steps], which is the vertex just before the last (i).

For instance, if i is 1 and steps is 4. Check path[1][1][4]. Suppose it is 2. So the path ends with "... 2 1". Now check path[1][2][3]. Supposing it's 4, the path ends with "... 4 2 1". Now check path[1][4][2]. If it's 5, the path is "... 5 4 2 1". Finally check path[1][5][1], which will be obviously 1. So the complete path is "1 5 4 2 1" (exactly 4 steps).

Just remember that path[i][j][s] is the vertex which is before the last one in a path from i to j in s steps. If s is 1, the path is simply "i j". In this problem you have to start and finish in the same currency; that's why we only search in best[i][i][steps].

Hope this helps, I almost wrote the complete program!

You could also stop the algorithm as soon as you found a solution. In other posts, some people talked about a O(n^3) solution but I can't figure it out... if someone has such a solution please mail it to me, I would love to learn how to do this in a better way.

Good luck and happy coding!

2008年11月25日 星期二

UVa 112 Tree Summing

終於AC了..這次最大的心得就是,腦袋不清楚的時候不要寫程式。如果沒辦法理清思路,找出邏輯上的漏洞,那麼debug也只是亂試一通而已,一點幫助都沒有(只有浪費時間)。寫到後來連錯誤的測資也在試,現在想起來真是笨阿

我用recursive的方法去追蹤整顆樹。測資是pre-order sequence
所以遞回順序是root ,left-child , right-child

很不清楚核心Algo:
int traversal(int sum, int target){
    抓左括號
    抓root
    lc = traversal(int sum+root, int target) //向left-child遞回
    rc = traversal(int sum+root, int target) //向right-child遞回  
    抓右括號

    如果是Leaf? 判斷總和相不相等?
    如果是Internal Node,將子樹的結果繼續往上回傳。
}

另外一提,這次我參考了某份AC Code,用non-recursive(Stack)作法,但是因為用了STL stack;,最後執行時間0.510s,慢了我五倍之多。我用Recursive反而執行時間只有0.100s(Ranking 90,再進百大XDDDD)有點意外。證明一件事:Recursive不一定慢,但是STL=慢。

2008年11月24日 星期一

UVa 108 Maximum Sum

解題策略

這題AC的關鍵是時間,用暴力法O(n6) 六層迴圈去解鐵定超時。已知最佳的解法是 O(n3) ,不過一般用O(n4) 就可以通過了。

我也是用 O(n4) 的解法,首先用四層迴圈窮舉子矩陣的左上角(x1,y1) 跟右下角 (x2,y2) 的位置,一旦給定了子矩陣後,就要 O(1) 時間得到子矩陣的和。

要達成這個目標可以透過 sum table 來達成,我說明一下我的方法, sum table ( i, j ) 每個位置儲存的值的是原矩陣 (1,1) ~ (i, j) 之間的元素總和。像下圖的 sum table ( 2, 3 ) 的值就是 原矩陣 (1, 1) ~ (2, 3) 之間的元素和。


一旦建好 sum table,那接下來就可以簡單透過這 D - B -C + A 這四個sum table的元素直接得到子矩陣的和了。

閒聊

最後執行時間0.052 過關....改天再將作法補完,我好睏....晚安。原本用暴力法去跑 100x100 的矩陣,竟然要253秒(大汗)。

2008年11月22日 星期六

UVa 10751 Chess Board v.2

解題策略


注意

修正了兩個問題,終於AC了
1. 雖然題目頁說只要印小數點後三位,但其實要印四位。
2. 各個output case"之間",要隔一個blank line。
但只有case間要空行,最後一個case印完後不能有多餘的空行。 (很嚴格的的格式要求...)

新版的AC Code

2008年11月16日 星期日

UVa 111 History Grading

這題說穿就是LIS,對於已經精通LIS的我自然是小菜一碟(咦?)
不過這題有個陷阱,如果沒仔細讀懂題目的話,會以為只要做一次轉換,其實上要做兩次轉換。
第一次把rank轉成真正的event sequence,(rank[] => seq[])
第二次才轉成可以做LIS的形式。(seq[] => seq2[])
剛開始送了兩個WA,後來看事有悉蹺,(sample output怪怪的),改了一下就AC了。

2008年11月10日 星期一

UVa 103 Stacking Boxes

題目講解

這題給你一堆多維的箱子,要找出最長的裝箱序列,這個最常裝箱序列就是像俄羅斯娃娃那樣,大箱子裡面放入小箱子,一層包一層,必須要可以裝最多層這樣。

這題的麻煩就是各個箱子之間不一定有的大小關係 (數學上打這叫偏序集 Partial Order Set ,不過這兒我們先不管 ),比方說有兩個三維箱子 BoxA(1,4,5) 、BoxB(2,4,6) ,B箱比較大,所以 BoxA 可以裝進 BoxB 裡,那麼我們說 BoxA < BoxB 。

但來看 BoxC(1,5,6) 跟 BoxD (2,4,5) 呢? 我們既不能說BoxC < BoxD ,也不能說 BoxC > BoxD,BoxC 與 BoxD 兩者之間就沒有大小關係。

一個簡單的表示法就是有向圖(Directed Graph)
比如說 A(1,2,3) B(2,4,6) C(2,3,7) D(50,50,50) E(10,10,100) 的有向圖表示法:



到此為止,本題的最長裝箱序列,已經有兩種解法,第一個方法就是找圖的最長路徑,稍微修改 Warsahll algorithm 來解,第二個方法是跑 LIS 。

我這裡用 LIS(最長上昇子串列) 解法。

//先定義一個box struct
struct Box {
    int no;
    int edge[10];
};

Box box[30]; 

LIS 法的關鍵是要先對箱子排序,確保小箱子一定在大箱子前,至於沒有大小關係箱子的就隨便放沒關係。這個排序以圖的角度是拓樸排序,以字串的角度是字典排序,兩者都行。

sort(box[i].edge) for all i  //先對箱子內部的邊長排序

int lexico_less(const Box& a, const Box& b) {
    for(int i=0;i<dimension;++i)
        if( !(a.edge[i]<=b.edge[i]) )
            return false;
    return true;
}
sort(box) by lexico_less(); //再用字典序排箱子
一切都準備好後,就可以直接套用LIS解了。
// LIS
int length[MAX_BOX];
int   prev[MAX_BOX];

length[i] = 1  for all i;
  prev[i] = -1 for all i;

for(int i=0;i<num_box;++i)
    for(int j=i+1;j<num_box;++j) {
        if( box[i]<box[j] ) {
            if(length[i]+1 > length[j] ){
                length[j] = length[i]+1;
                prev[j] = i;
            }
        }
    }
輸出結果
    int max = max_element(length, length+num_box) - length;
    //print the result
    printf("%d\n", length[max]);

    int output_seq[MAX_BOX];
    int size = 0;

    int cur = max;
    do {
        output_seq[size++] = box[cur].no;
        cur = prev[cur];
    } while( cur!= -1 );

    for(int i=size-1;i>0;--i)
        printf("%d ", output_seq[i]);
    printf("%d\n", output_seq[0]);
}

碎碎念

值得慶賀的事,Ranking 進世界百大!!!! 我相信這是誤打誤撞XDDD,不過真的蠻爽的。 @2008.11.10

[Algo] String Matching - KMP Algorithm

看了兩次,可是每次都忘記,所以做個筆記
s: input string
p: pattern

Failure Function的值k,就是下次要從p(k)開始matching

舉例

Pattern A B C A B C D
failure -1-1-1 0 1 2-1

Case I:
Input string
ABCDADFGACEDAABBBB
ABCABCD

紅色=not matching
step1: 看最後一個matching字元 (綠色的字) 的failure function value= f
step2: 將p(f)對齊綠色的位置 ( p(i)代表p的第i個字元 )

ex. f(C) = -1 ,所以p(-1)對齊上面那排的C
ABCDADFGACEDAABB
>>>ABCABCD

Case II:
ABCABCEACAADDBBBABCABC
ABCABCD

f(C)=2 ,所以p(2)對齊上面那排的綠色C

ABCABCEACAADDBBBABCABC
>>>ABCABCD


講的不是很有條理,不過我先給自己看懂就好= =
改天再來整理的清楚一些

2008年10月29日 星期三

[MASM] IO Patterns

讀取一串由空格分隔的整數 ex. 10 20 30 40 50

.data
buffer BYTE 512 DUP(0)
array DWORD 30 DUP(0)
len DOWRD 0 ;//陣列長度

.code
mov edx,OFFSET buffer
mov ecx, (SIZEOF buffer)
call ReadString          ;//Read string to buffer

mov esi,OFFSET buffer
mov edi,OFFSET intArray    ;//set addr, esi=buffer, edi=array

mov eax,0 ;//init eax

start:
movzx edx,BYTE PTR[esi]

cmp edx,0  ;//end of string
je over
cmp edx,32 ;//compare to space
je stateB
jmp stateA

stateA: ;//is digit
sub edx,48 ;//ascii edx-'0'

mov ebx,edx ;//because mul use edx, back up edx
mov ecx,10
mul ecx ;//eax=eax*10
mov edx,ebx
add eax,edx

inc esi
jmp start
stateB: ;//is space
mov [edi],eax ;//把eax存進array裡
mov eax,0
add edi,4
inc esi
inc len
jmp start
over:
mov [edi],eax
inc len

觀念很簡單
edx是Input String的位址,結果則是存在eax裡
每次從edx抓一個byte進來,判斷是1.數字 或2.空白
1.如果是數字就跳到 StateA,把eax原來的數字x10,然後加上新的數
2.如果是空白,代表一個整數結束,跳到StateB,將eax存進intArray裡,重新開始另一個循環直到edx讀到0,也就是字串的結尾為止。

2008年10月27日 星期一

Assembly Language Patterns

計算陣列長度

list Byte 10,20,30,40 //list 是array的起始位址
ListSize = ($ - list) //ListSize是一個Constant
//$代表Current Location counter

list DWORD 1000,2000,3000
ListSize = ($-list)/4 //DWORD大小是4Byte,所以除以四

雙層迴圈

mov ecx,5  //外圈次數
L1:
    mov count,ecx
    mov ecx, 7   //內圈次數
    L2:
      //do something here
      loop L2
      mov ecx,count
loop L1


if statement

if (op1==op2){ statement1; }
else {statement2; }

cmp op1,op2 // op1==op2
je _true     // jump if equal 相等的話就跳TRUE label
jmp _false   // 否則就無條件跳到FALSE label
_true:
    //statement1
    jmp next //跳過False部份
_false:
    //statement2
next:

While loop

while( var1>var2 ){
//statement
}
mov eax,var1
_while:
    cmp eax,var2
    jle endwhile //jmp if less and equl
    //原本是var1>var2,條件成立就進while
    //這裡改成var1<=var2,條件成立就離開while     
    //statement     
    jmp _while 
_endwhile:  

for loop

for(int i=0;i<9;i++){ statement; }
mov ecx,0 //把ecx當作計數器i
_for:
    cmp ecx,9
    jge _endfor //jump if greater & equal
    //statement;
    inc ecx     //ecx++
    jmp _for
_endfor:

2008年9月30日 星期二

[ACM] 自己整理一些有用的網站


=解題提示=

UVa官方論壇:
全世界UVa討論的集散地,當你題目解不出來時,第一件事就該來這裡搜尋該題目的討論串,通常會找到很多好心人提供的測資跟提示。
Methods to Solve
全世界最大的UVa解題提示網站,收錄的題目數量很多,品質也不錯。
Algorismist
這是一個關於演算法的維基網站,也有收錄 UVa 的解題提示,如果你有能力可以參與編輯條目,讓它變得更好。
UVa Toolkit
一般來講UVa題目頁上的範例測資都太簡單,聊勝於無。而 UVa Toolkit 這工具恰好補足了這方面的缺憾,你可以餵給它任何測資,並取得正確的對應輸出,對釐清題意很有幫助。
uHunt
非常非常好用的 UVa 解題工具網頁,可以很輕鬆的搜尋題目,安排自己解題的方向,瀏覽自己過去的解題紀錄等等。

=題目中譯=

Lucky貓
著名的ACM題目中譯網,及解題提示。
Lucky貓Mirror站
同上,有難度提示。
ACM中譯
少量題目中譯。
ZeroJudge
ZeroJudge是非常優秀的國產程式解題網,裡面有一區專門收錄UVa題目中譯。

=算法教學=

DJWS的網路日誌
資源豐富的網站,整理了很多的算法教學,以及各種ACM競賽的資料。
C語言考古題 & C的解題
大量題目教學
Art of Programming Contest for uva
淺顯的ACM入門書,免費線上版。
NACOW
對岸關於程式設計與解題的wiki
Infinite Loop
提供許多教學及ACM Tips, Sources。

=API Reference=

Cplusplus.com
簡潔清楚的C/C++標準函式參考手冊,範例碼清楚實用,值得看看,我自己把這兒當後花園逛了。

=題目列表=

ACM熱題排行榜
芭樂題排行榜,有哪些熱門題你還沒解過呢XD

=討論論壇=

NPSC補完計畫
針對NPSC的解題網站
OIBH
對岸關於資訊奧林匹亞競賽討論的論壇
algogeeks
Google group about algorithms.

=解題強者=

這部分網站就請各位審慎參觀了,大部分ACMer的程式碼都寫得不太好讀。
心如止水
350+題目解答,有基本的題目分類。
Nothing is Everything
少量UVa Source,品質不錯
小璋丸UVa解答 Java版
JAVA解題的強者。
摸索C語言
英雄出少年,解題高手,以Zero Judge為主。
朱色虫居
少量UVa解答,品質不錯
YT's ACM
高手解題夥伴YT的站
Kaipeng Liu's Column
大量UVa解答
Eddy's Blog
來自對岸的強者,解題不分國家呀。

2008年9月26日 星期五

[ACM] 加速法

觀念

有修過OS應該都知道,因為執行IO動作會牽涉到interupt、system call 等等機制,花掉非常多的時間。所以對大部分的ACM題目來說,減少IO的次數是加速的好方法。

關鍵點 : 「減少IO次數」


  1. Buffered Input: 不要用scnaf() 或者cin,用fgets一次讀進來,再parse字串。
  2. Buffered Outout: 先用StringStream輸出至memory,最後再一次印出。
  3. Buffered大小約在5000Byte左右,不要太小,也不要太大,導致Memory要做Swapping或paging。

其他小方法:

1. CPU通常會對4Bytes運算做最佳化(現在的32bit系統,應該也是對4Byte資料做運算最快),所以處理資料盡量用4Bytes當一個單位。

2. 但是超過一定的資料量大小,通常長度超過十萬的陣列,那麼整個陣列的體積反而影響比較大,這時能用char, short 比較快。

2008年5月31日 星期六

C & C++ 字串兩三事

  1. strlen( ) 不算'\0' ,但是會算'\n'。所以strlen("hello") 結果是5,strlen("hello\n") 結果是6。換行符號也算一個char,很容易被遺忘。
  2. 宣告string的時候,通常用的格式 char[MAXLINE+1],最後那個1,就是拿來放字串的結尾'\0'的。
  3. 從stdin讀字串的方法:
    cin>>s; 讀一個單字,遇到空格or換行停止,空格or換行不會存進字串s。
    cin.getline(s, length) 讀一行,遇到換行才停。
    fgets(s, sizeof(s), stdin) 最後那個'\n'也會被包含在輸入字串裡。
    cin.getline(s,length)則不會包含'\n'

2008年3月20日 星期四

JOGL - Java與OpenGl(四)

準備實戰

當你熟悉了前面的例子以後,我們來畫一張漂亮的圖。

這就是你接下來的程式。請確保你輸入了所有的code到你的編輯器中。調校這些程式可以使你快速地明白它們的工作原理。

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.media.opengl.*;

/**
* This is a basic JOGL app. Feel free to reuse this code or modify it.
* 這是個基礎的JOGL程序,你可以隨意重用該代碼或者修改它。
*/
public class SecondJoglApp extends JFrame {

    public static void main(String[] args) {
        final SecondJoglApp app = new SecondJoglApp();

        // show what we've done
        // 看一下我們做了什麼
        SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                app.setVisible(true);
            }
        });
    }

    public SecondJoglApp() {
        // set the JFrame title
        // 設置JFrame標題
        super("Second JOGL Application");

        // kill the process when the JFrame is closed
        // 當JFrame關閉的時候,結束程式
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        // only three JOGL lines of code ... and here they are
        // 只有三行JOGL code ... 如下
        GLCapabilities glcaps = new GLCapabilities();
        GLCanvas glcanvas = new GLCanvas(glcaps);
        glcanvas.addGLEventListener(new SecondGLEventListener());

        // add the GLCanvas just like we would any Component
        // 像其它元件一樣把GLCanvas加入
        getContentPane().add(glcanvas, BorderLayout.CENTER);
        setSize(500, 300);

        // center the JFrame on the screen
        // 使JFrame顯示在銀幕中央
        centerWindow(this);
    }

    public void centerWindow(Component frame) {
        Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize();
        Dimension frameSize = frame.getSize();

        if (frameSize.width > screenSize.width)
            frameSize.width = screenSize.width;
        if (frameSize.height > screenSize.height)
            frameSize.height = screenSize.height;
        frame.setLocation((screenSize.width - frameSize.width) >> 1,
                (screenSize.height - frameSize.height) >> 1);
    }
}



請注意這個class相較於前一個class只有少許的修改、class名稱、frame名稱、以及GLEventListener名稱。希望你能夠讀一讀code中的註解,否則你會搞不清它要做什麼。

我們實做的GLEventListener介面有了改進,可以畫出比上次漂亮一些的圖來。

import javax.media.opengl.*;
import javax.media.opengl.glu.*;

/**
 * For our purposes only two of the GLEventListeners matter. Those would be init() and display(). 
 * 對於我們來說,GLEventListener中只有兩個方法有用。 它們是init()和display()。
 */
public class SimpleGLEventListener implements GLEventListener {

    /**
     * Take care of initialization here. 注意這兒,初始化。
     */
    public void init(GLAutoDrawable gld) {
        GL gl = gld.getGL();
        GLU glu = new GLU();

        gl.glClearColor(0.0f, 0.0f, 0.0f, 1.0f);

        gl.glViewport(0, 0, 500, 300);
        gl.glMatrixMode(GL.GL_PROJECTION);
        gl.glLoadIdentity();
        glu.gluOrtho2D(0.0, 500.0, 0.0, 300.0);
    }

    /**
     * Take care of drawing here. 注意這兒,繪圖的地方。
     */
    public void display(GLAutoDrawable drawable) {
        float red = 0.0f;
        float green = 0.0f;
        float blue = 0.0f;

        GL gl = drawable.getGL();

        gl.glClear(GL.GL_COLOR_BUFFER_BIT);
        gl.glPointSize(5.0f);

        for (int i=0; i<50; i++){
            red -= .09f;
            green -= .12f;
            blue -= .15f;

            if (red < 0.15) red = 1.0f;
            if (green < 0.15) green = 1.0f;
            if (blue < 0.15) blue = 1.0f;
            gl.glColor3f(red, green, blue);
            gl.glBegin(GL.GL_POINTS);
            gl.glVertex2i((i*10), 150);
            gl.glEnd();
        }
    }

    public void reshape(GLDrawable drawable, int x, int y, int width, int height) {
    }

    public void displayChanged(GLDrawable drawable, boolean modeChanged,
            boolean deviceChanged) {
    }
}

以上就是我們第一個有趣的JOGL程式。下圖是輸出,有很多好看的顏色。


當你看到GLEventListener的實做時,可能會感到不知所措。如果你有用C寫OpenGL的經驗的話,你也許能猜出一些。如果你覺得茫然,別擔心,也不要煩惱我會叫你記住這些東西,至少現在還不用。本書接下來的篇幅將會對SecondGLEventListener作出解釋。現在,你只需要試著去猜。試著去修改code,產生兩行,或者一行斜的,而不是一行水平線;或是讓所有的點都變成藍色或紅色。享受一下,這就是你接下來學習JOGL的方式。

JOGL - Java與OpenGl(三)

一個好用的程式樣板

讓我們繼續來看兩個class,當你對JOGL感到有點頭昏腦脹時,你也許會發現這個程式樣板相當好用。我已經不止一次把它們當成樣板用了。你可以隨意地使用它們。

這個樣板由兩個class組成。第一個是如下所示的SimpleJoglApp,在簡短說明之後,第二個是SimpleGLEventListener。你必須建立兩個class來編譯樣板。主程式如下:

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.media.opengl.*;

/**
* This is a basic JOGL app. 
* Feel free to reuse this code or modify it.
* 這是個基本的JOGL程式,你可以隨意重用或修改它。
*/
public class SimpleJoglApp extends JFrame {
    public static void main(String[] args) {
        final SimpleJoglApp app = new SimpleJoglApp();

        // show what we've done
        // 看一下我們做了什麼
        SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                app.setVisible(true);
            }
        });
    }

    public SimpleJoglApp() {
        // set the JFrame title
        // 設置JFrame標題
        super("Simple JOGL Application");

        // kill the process when the JFrame is closed
        // 當JFrame關閉的時候,結束程式
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        // only three JOGL lines of code ... and here they are
        // 只有三行JOGL code ... 如下
        GLCapabilities glcaps = new GLCapabilities();
        GLCanvas glcanvas = new GLCanvas(glcaps);
        glcanvas.addGLEventListener(new SimpleGLEventListener());

        // add the GLCanvas just like we would any Component
        // 像其它組件一樣把GLCanvas加入
        getContentPane().add(glcanvas, BorderLayout.CENTER);
        setSize(500, 300);

        // center the JFrame on the screen
        // 使JFrame顯示在螢幕中央
        centerWindow(this);
    }

    public void centerWindow(Component frame) {
        Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize();
        Dimension frameSize = frame.getSize();

        if (frameSize.width > screenSize.width)
            frameSize.width = screenSize.width;
        if (frameSize.height > screenSize.height)
            frameSize.height = screenSize.height;

        frame.setLocation((screenSize.width - frameSize.width) >> 1,
        (screenSize.height - frameSize.height) >> 1);
    }
}



code就是這些。讓我們把注意力集中在第一個class中與JOGL相關的三行code上。首先:
這決定了我們的JOGL Library和JVM可以使用哪些OpenGL/圖形特性。

接著:

GLCanvas glcanvas = new GLCanvas(glcaps);

我們創建了可以在上面畫畫的GLCanvas。如果我們不想用AWT,改用Swing,則可以 new GLJPanel()。
注意我們把先前創建的GLCapabilities物件傳了進去,這使我們的GLDrawable(這裡指GLCanvas)適當建立。

最後,我們準備在GLCanvas上加入GLEventListener。

我們實現GLEventListener介面的class是SimpleGLEventListener。當它收到GLDrawable或 GLCanvas的呼叫時,它會注意所需要完成的繪圖工作。如你所見,我不打算在這個程式裡畫東西。下面是GLEventListener的code:

import javax.media.opengl.GLAutoDrawable;
import javax.media.opengl.GLEventListener;

/**
 * For our purposes only two of the GLEventListeners matter. 
 * Those would be init() and display(). 
 * 為了達到我們的目的,GLEventListener中只有兩個方法有用。
 * 它們是init()和display()。
 */
public class SimpleGLEventListener implements GLEventListener {

    /**
     * Take care of initialization here. 注意這兒,我們初始化的地方。
     */
    public void init(GLAutoDrawable drawable) {
    }

    /**
     * Take care of drawing here. 
     * 注意這兒,繪圖的地方。
     */
    public void display(GLAutoDrawable drawable) {
    }

    /**
     * Called when the GLDrawable (GLCanvas or GLJPanel) has changed in size. 
     * We won't need this, but you may eventually need it -- just not yet.
     * 當GLDrawable(GLCanvas或GLJPanel)大小改變時被呼叫。 
     * 我們不需要它,但你可能最後會用到 — 雖然現在並不需要。
     */
    public void reshape(GLAutoDrawable drawable, int x, int y, 
    int width, int height) {
    }

    /**
     * If the display depth is changed while the program is running this method
     * is called. Nowadays this doesn't happen much, unless a programmer has his
     * program do it. 
     * 當程序運行中顯示設定被改變時,會調用此方法。 
     * 現在這種事發生得不多,除非我們在程式裡面刻意觸發此事。
     */
    public void displayChanged(GLAutoDrawable drawable, boolean modeChanged, boolean deviceChanged) {
    }
}



以上就是我們要完成的JOGL核心工作。注意下面的UML圖。SimpleJoglApp是一個JFrame。它包含了GLDrawable,實際上是一個GLCanvas(但別那樣叫它)。我們加入了 SimpleGLEventListener。SimpleGLEventListener實現了相對於GLCanvas的 GLEventListener介面,這樣當它想執行任何的OpenGL工作時,GLCanvas就可以知道。GLDrawables能自動執行,所以你確實得使你的GLEventListener最優化。



這個程式跑起來可能會根據你的作業系統而顯得有點亂七八糟。這是預料中事,因為你在這裡只是在銀幕顯示隨機的內容。所以恭喜你,現在具備基本了繪圖能力了。

JOGL - Java與OpenGl(二)


Hello World!


我是一個傳統的人,所以我們理所當然從「Hello World」開始。這個「Hello World」程式將檢驗我們的安裝是否全部或只有一部分安裝正確。回憶一下安裝JOGL的2個部分,分別是jar文件裡的Java Library以及其它的Native code。

以下就是我們的程式:
import javax.media.opengl.*;

public class HelloWorld {
    public static void main (String args[]) {
        try {
            System.loadLibrary("jogl");
            System.out.println("Hello World! (The native libraries are installed.)");
            GLCapabilities caps = new GLCapabilities();
            System.out.println("Hello JOGL! (The jar appears to be available.)");
       } catch (Exception e) {
            System.out.println(e);
       }
    }
}

首先,這個程式測試 Native code 和 Java library 是否已經安裝正確了。只有當jogl.jar和Native code(諸如gluegen-rt.dll或者 jogl.dll)兩者都安裝好了的時候,JOGL才算安裝完全。如果native code不可用,程式會拋出 java.lang.UnsatisfiedLinkError例外。如果classpath裡沒有安裝JAR,程序則根本編譯都過不了。Javac編譯器會報諸如此類的錯「javax.media.opengl Package不存在」。當這個程序編譯通過且運行起來沒有異常的話,你可以繼續學習JOGL了。

(按:已修改為相容JOGL 2008的code)

JOGL - Java與OpenGl(一)

在這篇文章裡,摘錄了《學習Java對於OpenGL的綁定》。作者Gene Davis解釋了如何開始用Java對於OpenGl的綁定開發圖形增強的程式。

這些年來,為了創建一個圖形增強的程式,從而出售給使用各種不同操作系統的用戶,程式員有一個選擇——OpenGL。GL代表圖形庫(graphics library)。OpenGL是SGI(美國圖形工作站生產廠商)的註冊商標。OpenGL顯示了它是一個跨平台的C語言編程API。但是事實上,在程式介面上,它是一個獨立於硬體的規格。

OpenGL用於繪圖,速度非常快。大多數場合下,它使用硬體加速。似乎OpenGL可以實現一切你想要完成的圖形界面。

不幸的是,OpenGL是為C語言而寫的。不得不承認,C語言不是用來編寫複雜應用程式的流行語言。關於OpenGL一個最大的缺點就是:如果你不創建一個視窗(用來把你的圖形放入其中),你就什麼都做不了。但是OpenGL沒有提供給你創建視窗的方法。這使得OpenGL對於初學者來說顯得比較難。

幸運地是,出現了GLUT (OpenGL Utility Toolkit)(OpenGL工具包)。它被用來輕鬆應對視窗、按鈕以及使用者事件。儘管如此,對於想要使用物件導向的程式員來說,學習用C或者C++來寫OpenGL程式仍然是一件痛苦的事。


然後出現了JOGL

Java 也許是最流行的真正物件導向程式語言。有許多用Java去結合OpenGL的嘗試,但是第一個被大家認可並注意的OpenGL的Java綁定 (Java Bindings for OpenGL), 或者稱為JOGL。因為它得到Sun(Java的創建者)和SGI(OpenGL的創建者)的支持。

如今,Sun的遊戲開發小組正在開發JOGL。它以肯·拉塞爾和克里斯·克蘭開發的Jungle開始。拉塞爾是Sun的員工,研發「HotSpot虛擬機器」,擁有多年的3D經驗。克蘭則研發「荒謬的遊戲」,對3D圖學也相當有經驗。

我個人對他們以及所有其它在JOGL上工作的人表示感謝。曾經有許多人嘗試通過友好的Java API來使用OpenGL——其中包括Java 3D, OpenGL for Java Technology (gl4java)(給Java技術的OpenGL),Lightweight Java Game Library (LWJGL)(輕量級的Java遊戲庫)。JOGL第一個使我感到滿意。

JOGL是由Sun支持的、OpenGL的Java class綁定。哇!這句話說得太妙了。

OpenGL 被用來展示3D模型。它強大、快速,而且可能是自Swing出現以來最棒的一樣東西。通過JOGL來使用OpenGL,你可以製作出很酷的遊戲或是模型位置什麼的,而在這之前創建它們需要非常昂貴的成本。有人寫了很厚很厚的書來描述OpenGL,當你熟悉了它們以後這些書會很有用,但現在不行。你必須學習 展現在你面前的OpenGL是如何使用Java API的。同樣你還得看一下關於javax.media.opengl的基礎介紹,可能還得複習一下數學知識。



獲取JOGL?

如果你想使用JOGL,你需要jogl.jar以及附帶的Native code。我希望有一天它可以成為Java的標準,但現在它只是一個夢想。

第一步要找到你的作業系統對應的壓縮檔,並進行解壓縮。我是在https://jogl.dev.java.net/上找到的。不同的作業系統有所區別,但需要安裝2個部分。系統的環境變數classpath裡 一定要有jogl.jargluegen-rt.jar。我們的第一個sample code特別用來測試環境是否安裝正確,所以對於測試安裝你不必緊張。
(按:這裡已經修改為2008新版JOGL安裝方法)


JOGL的Javadocs

同樣可以在和JOGL的發佈位置獲得Javadocs。Javadocs會命名成類似jogl-1.0-usrdoc.tar的名字。

如果你瀏覽一下Package:javax.media.opengl,你很快會注意到有些class非常大。GL便是一個顯著的例子。別被嚇跑了,你很快會發現只需一點點JOGL的知識,就可以完成一些相當複雜的事了。現在你需要掃視一下的class有:
*GLDrawable
*GLCanvas
*GLJPanel
*GLCapabilities
*GLDrawableFactory

這些是進入圖形世界基本介面。如果你還記得,前面我提到初學OpenGL的人有一個大麻煩,那就是缺乏標準的視窗系統。對於C語言,GLUT起了相當大作用。而我們則有Swing和AWT。很可能你已經用過AWT或者Swing了,所以你不會覺得自己從頭學起。這非常好。在很短的介紹,關於把JOGL組件放到屏幕上以後,我們不需要多長時間就可以跑一個相當酷而且流行的程式了。


GlueGen...幾乎和JOGL一樣酷?

你應該意識到,OpenGL是為了C程式員而寫的。這意味著 Java 要利用它,必須要用到本機介面。用不怎麼有趣的 JNI (Java本機介面) 進行連接。然而 OpenGL太大了,手寫所有的連接太費時。想稍微做出一點複雜的程式,有許多特別的特性,OpenGL則保持改進,那意味著得有相應的變化來 跟上OpenGL的步伐。簡而言之,對於任何試著寫與OpenGL保持同步,包含所有Java到本機介面的程式碼的嘗試,非常困難。

讓我們進入JOGL家族看看。他們打算利用C頭文件寫一些程式碼來實現一切 JNI 做的事。他們管這個叫做 GlueGen。GlueGen解析C頭文件然後魔法般地創建出Java和JNI代碼以便連接到本機函數庫。這意味著OpenGL的升級可以迅速地在JOGL裡體現。