2012年2月29日水曜日

COLLADA (2)メッシュ表示

想像以上にイライラするフォーマットという印象。
メッシュの抜き出しに関してはようやく目処がついた。

仕様書にある
(1) <vertices>が存在しないケース
(2) 1つの<source>を全てが間接的に参照しているケース
(3) <vertices>内の<input>が複数あるケース
(4) オフセットの計算(連続する名無し<param>の考慮)
(5) 名無しの<param>
(6) マルチテクスチャ
これらも一応考慮しておいた。

色々考察した結果、エクスポータ依存によるところが非常に大きい。
キチガイ少し風変わりな出力がされている場合、それ即ちヘボいエクスポータということになる。

で、先に進める前に抜き出したメッシュがどんな具合かテストを行うためにOpenGL環境を用意。
メッシュ自体を表示することはできたが、1つ問題が出てきた。

<triangles>にある<p>、つまりインデクス。
当然そのままじゃ使えない。

頂点バッファに押し込みたいので一段噛ます必要があるようだ。



[追記]
と書きつつ気になったので少し古いが資料を発掘。
ディスプレイリストでもいい気がしてきた。
GLES側にはないらしいので、そっちはその時に考えるかな。

[追記その2]
ディスプレイリストで描画。


何の面白みもないただのトーラス。
*.daeが入出力可能かつフリーなソフトがBlenderしか見つけられなかったため。
本当は3DCGといえばティーポットだろうといいたいところだが我慢。
余談ではあるがBlender進化し過ぎ。
10年前くらいは特に見向きもしなかったが何だこれ!?
UIが無駄にかっこいい&操作性がぶっ飛んでいる!!
LightWaveや3DSなら普通に操作できるがこれはちょっと出来ん・・・。

2012年2月27日月曜日

COLLADA (1)準備

ふとCOLLADAでも読んでやるかと思った。XMLパーサ書くの面倒だなと調べたらCOLLADA DOMていう専用のパーサがありましたと。
バカでかいのはこの際いいとしても、初見じゃビルドできないときた。
グーグル先生に聞いたら素敵なサイトを教えてくれた。

v1.5という形式がどうやら最新の形式であることが判明。
というわけでこの環境を構築したわけだが・・・。

試しにネットから拾ってきたCOLLADAファイル(*.dae)をロードしてみる。
すると、ロードエラーで躓くときた。
原因はどうもDOMのバージョンとCOLLADAファイルのバージョンに差異があるということで
これで弾かれているらしい。
なんてこった!

そこでDOMを騙してやる作戦としてCOLLADAファイルのバージョンを変更してみた。
ロードは成功したが、特定のエレメント名に対するオブジェクトが生成されないと警告が出る。

仕方ないのでv1.4の環境を用意することにした・・・。

というのもお手軽にファイルを入手できるGoogle 3Dギャラリーで何ファイルか摘んでみると
どれもv1.4だったからという・・・。

ただ、DOMをv1.4、ファイルをv1.4にしても警告が完全に無くならないファイルもあるわけだが。
見なかったことにしよう。

で、とりあえず見ているわけだが、<geometry><mesh>~</mesh></geometry>内部にある
<source>~</source>
最大でも位置、法線、テクスチャ座標、色が入るということだろう(最低は1)。
疑問点は、
(1)並び順
固定?
数少ないサンプルファイルしか見てないので断定もできない。
ただ、XMLということを考慮すると固定というわけでもない気がするのと
エクスポータ次第な気もするんだけど。

(2)source要素の意味
つまり、取得したsource要素が頂点、法線、テクスチャ座標、色の内どれなのか。
あるファイルには
<source id="***-position">
<source id="***-Position">
<source id="***-Normals">
<source id="***-normal">
<source id="***-UV">
<source id="***-uv">
なんて記述されている。
これも仕様かどうかは調べないといけないが、ハイフン以降で判別自体はできるってことなのか?
では大文字、小文字は百歩譲って、Normalsとnormalの違いってどこから来てるんだろう。
バージョン差異ならまぁいいとしてもエクスポータ次第なら困るとこ。

[追記その1]
COLLADA 1.5.0 Specification in Japanese (Last updated: May 2009) *NEW*
のaccessor項目を見るとどうも違うらしい。
(1) ネーミングが異なる(2) Textureが2個ある

(1)は良く分からんな・・・やっぱりエクスポータ次第か?
とすると、純粋に何かという判別は、各プリミティブにあるsemanticでしか
判別できないということになり、そうすると存在するプリミティブをすべて見ないといけない
ことになる。

(2)はマルチテクスチャを考慮するとテクスチャが複数あるのは自然
だけど、他の要素については重複云々については特に触れていない。
ということは極端な話、POSITIONが複数あってもフォーマット的には問題ないということか。

で、pdfを見ていると分かったことが1つ。
vertices、オフセット、ストライド、最低でもこれらを全て考慮しないといけない。

柔軟にも程がある!

[追記その2]
<mesh>周りのまとめ

<mesh>
<source> ... 出現回数1以上
<vertices>  ... 出現回数1
<lines> ... 出現回数0以上
<linestrips> ... 出現回数0以上
<polygons> ... 出現回数0以上
<polylist> ... 出現回数0以上
<triangles> ... 出現回数0以上
<trifans> ... 出現回数0以上
<tritristrips> ... 出現回数0以上
<extra> ... 出現回数0以上

<vertices>
<input> ... 出現回数1以上
<extra> ... 出現回数0以上

<accessor>のサンプルを見ると<mesh>に<vertices>が存在しないケースがあるが
これは矛盾していないのだろうか?

またその際、<triangles>の<input>のsemanticは"POSITION"。
<vertices>の解説では1つの<input>要素は semantic="POSITIONを指定する必要がある
と明記されている。
この解説が正しいならprimitive_typesの中に出現する<input>のsemanticにはPOSITIONが
出現することはないと思うのだが。


また<vertices>の<input>出現回数が1以上ということは

<vertices id="verts">
  <input semantic=~POSITION" source="#position"/>
</vertices>
<triangles>
   <input semantic=~VERTEX" source="#verts"/ offset=0> 
   <input semantic=~NORMAL" source="#nrms"/ offset=1>
   <input semantic=~TEXCORD" source="#tc/" offset=2>
</triangles>

 と

<vertices id="verts">
  <input semantic=~POSITION" source="#position"/ offset=0>
<input semantic=~NORMAL" source="#nrms"/ offset=1>
  <input semantic=~TEXCORD" source="#tc/" offset=2>

</vertices>
<triangles>
   <input semantic=~VERTEX" source="#verts"/> 
</triangles>


<vertices id="verts">
  <input semantic=~POSITION" source="#position"/>
</vertices> <triangles>
   <input semantic=~VERTEX" source="#verts"/ offset=0> 
<input semantic=~NORMAL" source="#position"/ offset=0>
  <input semantic=~TEXCORD" source="#position/" offset=0>
</triangles> ※最後は各<source>内部でストライドを調整しているケース

同じ意味を指すケースもあるわけだろうか?

・・・ないとは言い切れないだろうなぁ。
あらゆる可能性(仕様の範囲内) を想定して上手くロードすることはできるのだろうか・・・。

2012年2月25日土曜日

小町算

ひょんなことから小町算をするハメになった。
条件次第では結構面倒くさい。
"+"、"-"だけなら直ぐなんだけど、"×"、"÷"と拡張していくと・・・。

面倒くさいから逆ポーランド記法に変換して突っ込むことにした。
数式の表現として扱えるのは、"=", "+", "-", "*", "/", "%", "^", "!", "(", ")"。
べき乗と階乗は今回はいいやということで未実装。
エラー処理も手抜き。

ソースはこちら

2012年2月19日日曜日

マークスイープGC

本棚本(表紙的に・・・)の著者の一人の中村成洋氏のミニGC
ミニGCの作り方
githubのソース

を参考にシングルスレッド版(Windows7 32bit)のマークスイープGCを作ってみた。
ルーツ選択部分はBoehmGCを参考にした。
レジスタ、スタック、グローバル変数の動作を慎重に吟味。
正しく動作している!のは当然として、参照が外れた時の動作がイメージ通りでなんか感動。
GC面白いなぁ・・・他のアルゴリズムなんかも実装してみたいところだけどちょっと時間がないや。
それにしても氏のソースは少しバグが多い気がする。

2012年2月17日金曜日

YEBIS


西川善司の3Dゲームファンのための「YEBIS」講座
“KAWASE式”のあの人が手がける「ポストエフェクト・ミドルウェア」の神髄に迫る!


Masaさんとか懐かしい。
DOUBLE S.T.E.A.LはCEDEC2次会かなんかで鍋つつきながらスクリーンショットを見せて貰った記憶がある。
水面に映る夕日のあまりの綺麗さに当時はえらい衝撃を受けたものだ。
この頃というかこの少し前の3Dシーン界隈は熱かったなぁ・・・。

2012年2月10日金曜日

Syntax Highlighter

ブログにコードを貼り付けるの面倒だな

個人情報云々の件もあるしBlogger止めるか

お、なんかいいのある!

というわけで忘れそうなのでメモメモ。

How to Add Syntax Highlighter(v3) to Blogger Blogs

(1)How to Install Syntax Highlighter in Blogger?GENERATE SCRIPTSボタンをクリック
(2)Select a Themeでテーマを選択
(3)Select Brushesで適用したい言語を選択(複数可)
(4)Generateボタンをクリック
(5)Copy To ClipBoardボタンをクリック
(6)Bloggerの[デザイン]→[HTMLの編集]


(7)テンプレートを編集のところから</head>を見つけて直前に(5)の内容をコピペ
</b:template-skin>
    <link href='http://alexgorbatchev.com/pub/sh/current/styles/shCore.css' rel='stylesheet' type='text/css'/>
    <link href='http://alexgorbatchev.com/pub/sh/current/styles/shThemeDefault.css' rel='stylesheet' type='text/css'/>
    <script src='http://alexgorbatchev.com/pub/sh/current/scripts/shCore.js' type='text/javascript'/>
    <script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushCpp.js' type='text/javascript'/>
    <script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushCss.js' type='text/javascript'/>
    <script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushJava.js' type='text/javascript'/>
    <script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushPlain.js' type='text/javascript'/>
    <script src='http://alexgorbatchev.com/pub/sh/current/scripts/shBrushXml.js' type='text/javascript'/>
    <script language='javascript' type='text/javascript'>
        SyntaxHighlighter.config.bloggerMode = true;
        SyntaxHighlighter.all();
    </script>
</head>

(8)テンプレートを保存ボタンをクリック

※デザインを変更すると(1)からやり直し

あとはブログを投稿する際にコード部分を下記のように記述。

<pre class='brush:[brushname];'>
    <!--Put Your Code Here (must be HTML escaped)-->
</pre>

オプション部分に関しては下記が参考になった。
SyntaxHighlighter - ソースコードを見やすく表示させるJavaScript

※"<"や">"は"&lt;"や"&gt;"にしておく(&は半角)

BoehmGC(3)

Windows7 32bit 環境での GC_register_dynamic_libraries() より抜粋。
抜粋というと語弊があるのでルーツ選別部分を出力してみた。

*** SYSINFO ***
oem id                : 0
page size             : 4096 bytes
min app address       : 0x00010000
max app address       : 0xbffeffff
active processor mask : 0xff
number of processors  : 8
processor type        : 0x24a
allocation granularity: 65536 bytes
processor level       : 6
processor revision    : 0x1a05

process id: 5908(current)
No  Addr       Size(bytes)  Pages  AllocBase  状態      アクセス許可          タイプ/モジュール名
===================================================================================================
000 0x00000000       65536     16  0x00000000 フリー    アクセス不可                      
001 0x00010000       65536     16  0x00010000 コミット  読み書き可            マップ      
002 0x00020000       65536     16  0x00020000 コミット  読み書き可            マップ      
003 0x00030000     1003520    245  0x00030000 予約                            プライベート
004 0x00125000        4096      1  0x00030000 コミット  読み書き可(ガード)    プライベート
005 0x00126000       40960     10  0x00030000 コミット  読み書き可            プライベート
006 0x00130000       16384      4  0x00130000 コミット  読み込みのみ可        マップ      
007 0x00134000       49152     12  0x00000000 予約余り  アクセス不可                      
008 0x00140000        4096      1  0x00140000 コミット  読み込みのみ可        マップ      
009 0x00141000       61440     15  0x00000000 予約余り  アクセス不可                      
010 0x00150000        4096      1  0x00150000 コミット  読み書き可            プライベート
011 0x00151000       61440     15  0x00000000 予約余り  アクセス不可                      
012 0x00160000      421888    103  0x00160000 コミット  読み込みのみ可        マップ      
013 0x001c7000       36864      9  0x00000000 予約余り  アクセス不可                      
014 0x001d0000      131072     32  0x00000000 フリー    アクセス不可                      
015 0x001f0000       20480      5  0x001f0000 コミット  読み書き可            プライベート
016 0x001f5000       45056     11  0x001f0000 予約                            プライベート
017 0x00200000      131072     32  0x00000000 フリー    アクセス不可                      
018 0x00220000      262144     64  0x00220000 コミット  読み書き可            プライベート
019 0x00260000      786432    192  0x00220000 予約                            プライベート
020 0x00320000      917504    224  0x00000000 フリー    アクセス不可                      
021 0x00400000        4096      1  0x00400000 コミット  読み込みのみ可        イメージ    
022 0x00401000        4096      1  0x00400000 コミット  実行/読み込みのみ可   イメージ    
023 0x00402000        4096      1  0x00400000 コミット  読み込みのみ可        イメージ    
024 0x00403000        4096      1  0x00400000 コミット  読み書き可            イメージ     ※
025 0x00404000        4096      1  0x00400000 コミット  読み込みのみ可        イメージ    
026 0x00405000       45056     11  0x00000000 予約余り  アクセス不可                      
027 0x00410000     1572864    384  0x00000000 フリー    アクセス不可                      
028 0x00590000       12288      3  0x00590000 コミット  読み書き可            プライベート
029 0x00593000       53248     13  0x00590000 予約                            プライベート
030 0x005a0000  1742536704 425424  0x00000000 フリー    アクセス不可                      
031 0x68370000        4096      1  0x68370000 コミット  読み込みのみ可        イメージ    
032 0x68371000      405504     99  0x68370000 コミット  実行/読み込みのみ可   イメージ    
033 0x683d4000      176128     43  0x68370000 コミット  読み込みのみ可        イメージ    
034 0x683ff000        4096      1  0x68370000 コミット  読み書き可            イメージ     ※
035 0x68400000        4096      1  0x68370000 コミット  書き込み時コピー      イメージ    
036 0x68401000        4096      1  0x68370000 コミット  読み書き可            イメージ     ※
037 0x68402000        4096      1  0x68370000 コミット  書き込み時コピー      イメージ    
038 0x68403000       12288      3  0x68370000 コミット  読み書き可            イメージ     ※
039 0x68406000       20480      5  0x68370000 コミット  読み込みのみ可        イメージ    
040 0x6840b000       20480      5  0x00000000 予約余り  アクセス不可                      
041 0x68410000   221380608  54048  0x00000000 フリー    アクセス不可                      
042 0x75730000        4096      1  0x75730000 コミット  読み込みのみ可        イメージ    
043 0x75731000      274432     67  0x75730000 コミット  実行/読み込みのみ可   イメージ    
044 0x75774000        8192      2  0x75730000 コミット  読み書き可            イメージ     ※
045 0x75776000       16384      4  0x75730000 コミット  読み込みのみ可        イメージ    
046 0x7577a000       24576      6  0x00000000 予約余り  アクセス不可                      
047 0x75780000     5636096   1376  0x00000000 フリー    アクセス不可                      
048 0x75ce0000        4096      1  0x75ce0000 コミット  読み込みのみ可        イメージ    
049 0x75ce1000      806912    197  0x75ce0000 コミット  実行/読み込みのみ可   イメージ    
050 0x75da6000        4096      1  0x75ce0000 コミット  読み書き可            イメージ     ※
051 0x75da7000       53248     13  0x75ce0000 コミット  読み込みのみ可        イメージ    
052 0x75db4000       49152     12  0x00000000 予約余り  アクセス不可                      
053 0x75dc0000    19726336   4816  0x00000000 フリー    アクセス不可                      
054 0x77090000        4096      1  0x77090000 コミット  読み込みのみ可        イメージ    
055 0x77091000      651264    159  0x77090000 コミット  実行/読み込みのみ可   イメージ    
056 0x77130000        4096      1  0x77090000 コミット  読み書き可            イメージ     ※
057 0x77131000        4096      1  0x77090000 コミット  書き込み時コピー      イメージ    
058 0x77132000        8192      2  0x77090000 コミット  読み書き可            イメージ     ※
059 0x77134000       12288      3  0x77090000 コミット  書き込み時コピー      イメージ    
060 0x77137000       20480      5  0x77090000 コミット  読み込みのみ可        イメージ    
061 0x7713c000       16384      4  0x00000000 予約余り  アクセス不可                      
062 0x77140000     2228224    544  0x00000000 フリー    アクセス不可                      
063 0x77360000        4096      1  0x77360000 コミット  読み込みのみ可        イメージ    
064 0x77361000      876544    214  0x77360000 コミット  実行/読み込みのみ可   イメージ    
065 0x77437000        4096      1  0x77360000 コミット  読み書き可            イメージ     ※
066 0x77438000        8192      2  0x77360000 コミット  書き込み時コピー      イメージ    
067 0x7743a000        4096      1  0x77360000 コミット  読み書き可            イメージ     ※
068 0x7743b000        4096      1  0x77360000 コミット  書き込み時コピー      イメージ    
069 0x7743c000        8192      2  0x77360000 コミット  読み書き可            イメージ     ※
070 0x7743e000        8192      2  0x77360000 コミット  書き込み時コピー      イメージ    
071 0x77440000      376832     92  0x77360000 コミット  読み込みのみ可        イメージ    
072 0x7749c000       16384      4  0x00000000 予約余り  アクセス不可                      
073 0x774a0000     1048576    256  0x00000000 フリー    アクセス不可                      
074 0x775a0000        4096      1  0x775a0000 コミット  読み込みのみ可        イメージ    
075 0x775a1000       61440     15  0x00000000 予約余り  アクセス不可                      
076 0x775b0000   135528448  33088  0x00000000 フリー    アクセス不可                      
077 0x7f6f0000       20480      5  0x7f6f0000 コミット  読み込みのみ可        マップ      
078 0x7f6f5000     1028096    251  0x7f6f0000 予約                            マップ      
079 0x7f7f0000     8126464   1984  0x00000000 フリー    アクセス不可                      
080 0x7ffb0000      176128     43  0x7ffb0000 コミット  読み込みのみ可        マップ      
081 0x7ffdb000       20480      5  0x00000000 予約余り  アクセス不可                      
082 0x7ffe0000        4096      1  0x7ffe0000 コミット  読み込みのみ可        プライベート
083 0x7ffe1000       61440     15  0x7ffe0000 予約                            プライベート
084 0x7fff0000       57344     14  0x00000000 フリー    アクセス不可                      
085 0x7fffe000        4096      1  0x7fffe000 コミット  読み書き可            プライベート
086 0x7ffff000        4096      1  0x7ffff000 コミット  読み書き可            プライベート
087 0x80000000  1073676288 262128  0x80000000 予約                            プライベート
0xbfff0000     --- アクセス不許可
---------------------------------------------------------------------------------------------------

※が付いている箇所がルーツ対象。

Stack: 0x0012ff4c No:005
Stack: 0x0012ff50 No:005
Stack: 0x0012ff44 No:005
BSS  : 0x00403378 No:024
Data : 0x00403018 No:024
BSS  : 0x004033a8 No:024
Data : 0x0040301c No:024
Stack: 0x0012ff40 No:005
Heap : 0x001f12a0 No:015

下記の順番で No はマッピングされた番号。
・main 関数の引数 int argc
・main 関数の引数 char* argv[]
・main 関数内の自動変数
・未初期化外部変数
・初期化済外部変数
・未初期化静的変数
・初期化済静的変数
・main 関数内の自動変数
・ヒープ

なるほど!

2012年2月8日水曜日

BoehmGC(2)

GC_push_roots から辿れる部分を追ってみた。
・・・改めてBoehmGCの偉大さを痛感した。
なんというべきか、あらゆるCPUとOSの歴史だなこれは。
windowsのみに着目しても頭痛がしそうだ(汗

テストプログラムを書くにしても、何のcpuか何のOSかスレッドの有無を
限定しないと話が進みそうにもないや。

とりあえずVCでもインストールするか。

2012年2月7日火曜日

Notepad++ コンテキストメニューの拡張

ソースコードなんかを追う時に、ずぼらな人なので右手だけで操作したい。
ということで、キーワードを右クリックでGrepできないかなと思っていたら
コンテキストメニューの拡張でできたのでメモ。

(1) [設定]→[Edit Popup ContextMenu] で contextMenu.xml を開く
(2) nativeLang.xmlを開く
ここに各機能に対するidが記載されている

contextMenu.xml の <Scintillacontextmenu>~</ScintillaContextMenu> 間に Item を追加。

検索とファイル内の検索なら次の2行を追加。
<item MenuEntryName="Edit" id="43001"/>
<item MenuEntryName="Edit" id="43013"/>


便利便利。

BoehmGC

Ubuntu側に落として簡単な動作確認。
参照が途切れるタイミングを見ていたが、当然の如くスタックもグローバル変数もバッチリ。

となると、実装方法は1つ。
念のためソースコードを追ってみるとコンパイルスイッチの嵐。
ざっくり見た感じだとデータセグメントを操作している。
x86の実装部分はまだ少し追ってみないと良く分からない部分があるけども。

2012年2月5日日曜日

メモリとか

とある分厚い本を読了。
海の向こうの技術はやっぱり凄いわ・・・。

直接関係はないがメモリー関連の本が欲しいなと物色したら
省メモリプログラミング―メモリ制限のあるシステムのためのソフトウェアパターン集
というものがあったので購入し読了。
非常によくまとまった良書と感じた。

続けてガベージコレクションに興味が沸く。
というのもGCについては上辺程度のことしか知らない。
Androidの場合だとDalvikさんがよろしくやってくれるので最低限のことしか気にしていなかったが
そもそものコンセプトであるメモリ管理に煩わされなくていいよと言われて、はいそうですかというのも
やっぱり気持ち悪い。
そんなわけで取っ掛かりとして
ガベージコレクションのアルゴリズムと実装
を購入しざっくり読了。
非常に分かりやすい解説でアルゴリズムはすんなりと頭に入った。

ただ、実装すると仮定した場合のルートについては理解が不十分なのでメモ書き。
■ヒープ
 これはアロケータも含めての話となるのでルートとすることは簡単。
■スタック(関数の引数とかローカル変数)
 GC初期化~直前のローカル変数のアドレス間を操作。
■レジスタ
 GC直前にアセンブリかsetjmpでレジスタ取得を行い操作。
 環境依存を考慮すると後者が一般的。

スタックとレジスタについては若干悩んだが、
・GCは不要とされるオブジェクトを破棄する
・GCされることで実行コード(スタックやレジスタ)に影響があっては困る
という点から、スタックやレジスタが有効とされるアドレスを参照しているならば
GCには破棄させないということで操作については納得した。

グローバル変数については気になることが色々あるのでオープンソースな実装を読んでいる。
Rubyの場合はrb_gc_register_addressで内部で保持するリストに登録してる感じのようだ。
C/C++ネイティブなものも知る必要があるのでBoehmGCも併読。