岸良智, 杉田公生, 土田賢省, 野牧賢志, 本橋友江 , 夜久竹夫 Rendering 24-ary Grids for Rectangular Solid Dissections 24分格子グラフによる直方体分割の描画 岸良智, 杉田公生, 土田賢省, 野牧賢志, 本橋友江 , 夜久竹夫 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 １ 　　　　　　Introduction First, I will speak about Introduction and background of this research 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 Background 直方体分割のグラフ表現モデルとして、octrees が知られている　 　（Jackins and Tanimoto, 1980） 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 Motivation Octreeでは問題によって 計算時間がかかる 解像度低減が不十分 プログラムが作りにくい 以上を解決 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 Purpose and Results Purpose 問題点を解決するために、octgrids を一般化する Results 24分格子グラフによる直方体分割を導入 24分格子グラフのセルの合併を導入 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 ２ 24分格子グラフ 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 直方体分割の例　不均一にも対応 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 直方体分割のグラフ例 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 D = {S1, S2, ..., SN} とするとき、D に対する24分格子 tetraicosa-grid は以下で定義されるラベル付き多重辺グラフGD = (VD, L, ED, A) である。 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 (1) VD は“直方体s ∈ Dのとき vs ∈ VD ”で定める。 (2) L = {EquivalentUpwardNorthEastCornerPole, ..., EquivalentForwardCeilingNorthBeam, ..., EquivalentBackwardFloorWestBeam} 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 (3) ED ⊆ VD × L × VD は以下で定められるラベル付き無向辺の集合： 　s と t が共通の下方南側梁を持つ最も近い直方体ならば [s, EquivalentForwardFloorSouthBeam, t] は ED に属する。 EquivalentForwardFloorSouthBerm 上 北 西 ｓ ｔ 東 vs vt 南 下 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 If [s, EquivalentForwardFloorSouthBeam, t] is in ED, then (ⅰ) (s, EquivalentForwardFloorSouthBeam, Forward, t) is in EDD and (ⅱ) (s, EquivalentForwardFloorSouthBeam, Backward, t) is in EDD 　　　　　　(sx ≧ tx) EDD ⊆VD×L ×Direction×VD forward (vs, EquivalentForwardFloorSouthBeam, forward, vt ) ∈EDD (vs, EquivalentForwardFloorSouthBeam, backward, vt ) ∈EDD vs vt ｓ ｔ backward vs vt 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 (4) A は色などのセルの属性を表す集合である。 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 D ：幅k、奥行きl、高さm の直方体分割 GD：D に対する24分格子グラフ i ： D の内部セルの個数 2 |ED| = 12×8 + 16×4(k-2) + 16×4(l-2) + 16×4(m-2) +20×2(k-2)(l-2) + 20×2(l-2)(m-2) + 20×2(m-2)(l-2) + 24 i 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 ３ H9CODE 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 4．１　H9CODEの作成 H3CODE [9] の仕様を拡張 H3CODEの対象：矩形分割 　　　　　　　　↓ H9CODEの対象：直方体分割 H9CODEは直交座標を利用 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 1 ヘッダー部 表の基本情報、３つのフィールドからなる（予備フィールドを除く）。 2 リスト部 この表のセルを表す。セル数と等しい数のレコードからなる。 １レコード当たり48フィールドとする。 3 コンテンツ部 セルに付随する、文字列、画像などの情報を格納する。 １コンテンツ当たり8つのフィールドからなる（予備フィールドを除く）。 4 表レイヤー部 複数の表を管理するための情報を表す 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

＜H3CODEと共通＞ 第１ブロック、各フィールドの内容。（１～8） １．バージョン情報 ２．行数 ３．列数 ４．段数 ５～８．予備 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

＜H3CODEと共通＞ 第２ブロック （それぞれ整数値が入る） 1.node id 2.cell type 3. new_right 4. new_left 5. swe_right 6. swe_left 7. ewe_upper 8. wwe_upper 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 9. ewe_lower 10. wwe_lower 11. north_wall 12. south_wall 13. east_wall 14. west_wall 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 15. content_id 16. content_align 17. E_point ＜拡張部分＞ 18. upper_wall 19. lower_wall 20-32. 予備 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 ＜拡張部分＞ 各フィールドの内容。 （33～40） 33.EquivalentUpwardNorthEastCornerPole：上方への北東角ポールの等値リンク 上方で同じ平面座標の北東角のポールを持つ直近のボクセルへのリンク（ボクセル同士のサイズは異なってもよい） 上 北 西 東 南 下 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 34. EquivalentDownwardNorthEastCornerPole 上 北 西 東 南 下 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 35. EquivalentUpwardNorthWestCornerPole 36. EquivalentDownwardNorthWestCornerPole 35 36 上 北 西 東 南 下 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 37. EquivalentUpwardSouthEastCornerPole 38. EquivalentDownwardSouthEastCornerPole 37 38 上 北 西 東 南 下 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 39. EquivalentUpwardSouthWestCornerPole 40. EquivalentDownwardSouthWestCornerPole 39 40 上 北 西 東 南 下 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 各フィールドの内容。 （41～56） ４１. EquivalentForwardCeilingNorthBeam ：天井側北梁の東への等値リンク 上 北 西 東 南 下 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 42. EquivalentBackwardCeilingNorthBeam 上 北 西 東 南 下 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 43. EquivalentForwardCeilingSouthBeam 44. EquivalentBackwardCeilingSouthBeam 43 44 上 北 西 東 南 下 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 45. EquivalentForwardFloorNorthBeam 46. EquivalentBackwardFloorNorthBeam 45 46 上 北 西 東 南 下 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 47. EquivalentForwardFloorSouthBeam 48. EquivalentBackwardFloorSouthBeam 47 48 上 北 西 東 南 下 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 49. EquivalentForwardCeilingEastBeam 50. EquivalentForwardCeilingWestBeam 49 50 上 北 西 東 南 下 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 51. EquivalentBackwardCeilingEastBeam 52. EquivalentBackwardCeilingWestBeam 51 52 上 北 西 東 南 下 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 53. EquivalentForwardFloorEastBeam 54. EquivalentForwardFloorWestBeam 53 54 上 北 西 東 南 下 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 55. EquivalentBackwardFloorEastBeam 56. EquivalentBackwardFloorWestBeam 55 56 上 北 西 東 南 下 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

＜H3CODEと共通＞ 第3ブロック、各フィールドの内容。 以下の８フィールドの繰り返し 1. Content id 2. Content type 文字列、ＨＴＭＬ情報、画像などを識別 3. object 文字列、画像コンテンツ等へのリンク 4.～　予備 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

＜H3CODEと共通＞ 第4ブロック、各フィールドの内容。 1~8　未定 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 ４ セルの合併 First, I will speak about Introduction and background of this research 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 UNIFYVOLUME CELL INPUT GD : 直方体分割Dの24分格子グラフ vc  : GDのセル vd : vcと水平方向に隣接するGDのセル   OUTPUT GE  : 直方体分割Eの24分格子グラフ 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 セル合併の入出力 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 Method 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 Method 1. x軸のリンクを張り替える 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 Method 1. x軸のリンクを張り替える 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 Method 2. y軸のリンクを張り替える 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 Method 2. y軸のリンクを張り替える 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 Method 3. z軸のリンクを張り替える 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 Method 3. z軸のリンクを張り替える 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 Method 4. dを削除 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 Method 4. dを削除 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 Method 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部 50

数理モデル化と問題解決研究会 大阪大学基礎工学部 c とd の周辺リンクの数が96 = 48 × 2 に押さえられるので、アルゴリズムの計算量が O(1) になることに注意 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 ５ H9CODEによる描画 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 座標からH9CODEを作成するプログラム 名称 : cv2h9 入力 : 座標 出力 : H9CODE プログラミング言語 : C 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 H9CODEからVRMLへ変換するプログラム 名称 : h92vrml 入力 : H9CODE 出力 : VRML プログラミング言語 : C 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

H9CODEを用いて生成される球の出力イメージ 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 ６ Conclusion 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 Conclusion ボリュームグラフィックスのための新しいグラフ表現として“tetraicosa-grid” を紹介 tetraicosa-grid のデータフォーマットであるH9CODE とH9CODEを用いたセルの合併方法を紹介 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 24分格子グラフのためのレンダリングシステムの実装とセルの合併の実装を目指す。 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 END 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 EquivalentForwardFloorSouthBerm ｔ ｓ vs vt 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部

数理モデル化と問題解決研究会 大阪大学基礎工学部 2008/12/17 数理モデル化と問題解決研究会　　　　　大阪大学基礎工学部