Document

Rendering 24-ary Grids for Rectangular
Solid Dissections
24分格子グラフによる直方体分割の描画
岸良智, 杉田公生, 土田賢省,
野牧賢志, 本橋友江 , 夜久竹夫
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
1
Introduction
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
2
Background
 直方体分割のグラフ表現モデルとして、
octrees が知られている
（Jackins and Tanimoto, 1980）
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
3
Motivation
 Octreeでは問題によって
 計算時間がかかる
 解像度低減が不十分
 プログラムが作りにくい
以上を解決
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
4
Purpose and Results
Purpose
 問題点を解決するために、octgrids を一般
化する
Results
 24分格子グラフによる直方体分割を導入
 24分格子グラフのセルの合併を導入
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
5
24分格子グラフ
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
6
直方体分割の例不均一にも対応
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
7
直方体分割のグラフ例
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
8
 D = {S1, S2, ..., SN} とするとき、D に対
する24分格子 tetraicosa-grid は以下で定
義されるラベル付き多重辺グラフGD = (VD,
L, ED, A) である。
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
9
 (1) VD は“直方体s ∈ Dのとき vs ∈ VD ”で
定める。
 (2) L =
{EquivalentUpwardNorthEastCornerPo
le, ...,
EquivalentForwardCeilingNorthBeam,
...,
EquivalentBackwardFloorWestBeam}
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
10
 (3) ED ⊆ VD × L × VD は以下で定められる
ラベル付き無向辺の集合：
s と t が共通の下方南側梁を持つ最も近い直
方体ならば
[s, EquivalentForwardFloorSouthBeam, t]
は ED に属する。
EquivalentForwardFloor
SouthBerm
上
北
西
東
南
ｓ
ｔ
下
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
vs
vt
11
 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
vt
EquivalentForwardFloorSouthBeam,
forward, vt ) ∈EDD
(vs,
backward
vs
2008/12/17
(vs,
vt
EquivalentForwardFloorSouthBeam,
backward, vt ) ∈EDD
数理モデル化と問題解決研究会
大阪大学基礎工学部
12
 (4) A は色などのセルの属性を表す集合で
ある。
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
13
 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(k2)(l-2) + 20×2(l-2)(m-2) +
20×2(m-2)(l-2) + 24 i
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
14
H9CODE
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
15
4．１ H9CODEの作成
 H3CODE [9] の仕様を拡張
 H3CODEの対象：矩形分割
↓
 H9CODEの対象：直方体分割
 H9CODEは直交座標を利用
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
16
 1 ヘッダー部
表の基本情報、３つのフィールドからなる（予備フィールドを除く）。
 2 リスト部
この表のセルを表す。セル数と等しい数のレコードからなる。
１レコード当たり48フィールドとする。
 3 コンテンツ部
セルに付随する、文字列、画像などの情報を格納する。
１コンテンツ当たり8つのフィールドからなる（予備フィールドを除く）。
 4 表レイヤー部
複数の表を管理するための情報を表す
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
17
＜H3CODEと共通＞
第１ブロック、各フィールドの内容。（１～8）





１．バージョン情報
２．行数
３．列数
４．段数
５～８．予備
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
18
＜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
数理モデル化と問題解決研究会
大阪大学基礎工学部
19






9. ewe_lower
10. wwe_lower
11. north_wall
12. south_wall
13. east_wall
14. west_wall
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
20
 15. content_id
 16. content_align
 17. E_point
＜拡張部分＞
 18. upper_wall
 19. lower_wall
 20-32. 予備
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
21
＜拡張部分＞
各フィールドの内容。（33～40）
 33.EquivalentUpwardNorthEastCornerPole
：上方への北東角ポールの等値リンク
 上方で同じ平面座標の北東角のポールを持つ直近
のボクセルへのリンク（ボクセル同士のサイズは異
なってもよい）
上
北
西
東
南
下
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
22
 34. EquivalentDownwardNorthEastCornerPole
上
北
西
東
南
下
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
23
 35. EquivalentUpwardNorthWestCornerPole
 36. EquivalentDownwardNorthWestCornerPole
36
35
上
北
西
東
南
2008/12/17
下
数理モデル化と問題解決研究会
大阪大学基礎工学部
24
 37. EquivalentUpwardSouthEastCornerPole
 38. EquivalentDownwardSouthEastCornerPole
37
38
上
北
西
東
南
2008/12/17
下
数理モデル化と問題解決研究会
大阪大学基礎工学部
25
 39. EquivalentUpwardSouthWestCornerPole
 40. EquivalentDownwardSouthWestCornerPole
39
40
上
北
西
東
南
2008/12/17
下
数理モデル化と問題解決研究会
大阪大学基礎工学部
26
各フィールドの内容。（41～56）
 ４１. EquivalentForwardCeilingNorthBeam
：天井側北梁の東への等値リンク
上
北
西
東
南
下
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
27
 42. EquivalentBackwardCeilingNorthBeam
上
北
西
東
南
下
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
28
 43. EquivalentForwardCeilingSouthBeam
 44. EquivalentBackwardCeilingSouthBeam
44
43
上
北
西
東
南
2008/12/17
下
数理モデル化と問題解決研究会
大阪大学基礎工学部
29
 45. EquivalentForwardFloorNorthBeam
 46. EquivalentBackwardFloorNorthBeam
46
45
上
北
西
東
南
2008/12/17
下
数理モデル化と問題解決研究会
大阪大学基礎工学部
30
 47. EquivalentForwardFloorSouthBeam
 48. EquivalentBackwardFloorSouthBeam
47
48
上
北
西
東
南
2008/12/17
下
数理モデル化と問題解決研究会
大阪大学基礎工学部
31
 49. EquivalentForwardCeilingEastBeam
 50. EquivalentForwardCeilingWestBeam
50
49
上
北
西
東
南
2008/12/17
下
数理モデル化と問題解決研究会
大阪大学基礎工学部
32
 51. EquivalentBackwardCeilingEastBeam
 52. EquivalentBackwardCeilingWestBeam
51
52
上
北
西
東
南
2008/12/17
下
数理モデル化と問題解決研究会
大阪大学基礎工学部
33
 53. EquivalentForwardFloorEastBeam
 54. EquivalentForwardFloorWestBeam
54
53
上
北
西
東
南
2008/12/17
下
数理モデル化と問題解決研究会
大阪大学基礎工学部
34
 55. EquivalentBackwardFloorEastBeam
 56. EquivalentBackwardFloorWestBeam
55
56
上
北
西
東
南
2008/12/17
下
数理モデル化と問題解決研究会
大阪大学基礎工学部
35
＜H3CODEと共通＞
第3ブロック、各フィールドの内容。
以下の８フィールドの繰り返し
 1. Content id
 2. Content type
文字列、ＨＴＭＬ情報、画像などを識別
 3. object
文字列、画像コンテンツ等へのリンク
 4.～予備
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
36
＜H3CODEと共通＞
第4ブロック、各フィールドの内容。
 1~8 未定
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
37
セルの合併
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
38
UNIFYVOLUME CELL
 INPUT
 GD : 直方体分割Dの24分格子グラフ
 vc : GDのセル
 vd : vcと水平方向に隣接するGDのセル
 OUTPUT
 GE : 直方体分割Eの24分格子グラフ
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
39
セル合併の入出力
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
40
 Method
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
41
 Method
1. x軸のリンクを
張り替える
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
42
 Method
1. x軸のリンクを
張り替える
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
43
 Method
2. y軸のリンクを
張り替える
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
44
 Method
2. y軸のリンクを
張り替える
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
45
 Method
3. z軸のリンクを
張り替える
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
46
 Method
3. z軸のリンクを
張り替える
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
47
 Method
4. dを削除
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
48
 Method
4. dを削除
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
49
 Method
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
50
 c とd の周辺リンクの数が96 = 48 × 2 に
押さえられるので、アルゴリズムの計算量が
O(1) になることに注意
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
51
H9CODEによる描画
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
52
 座標からH9CODEを作成するプログラム




名称 : cv2h9
入力 : 座標
出力 : H9CODE
プログラミング言語 : C
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
53
 H9CODEからVRMLへ変換するプログラ
ム
 名称 : h92vrml
 入力 : H9CODE
 出力 : VRML
 プログラミング言語 : C
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
54
H9CODEを用いて生成される球の出力イメージ
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
55
Conclusion
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
56
Conclusion
 ボリュームグラフィックスのための新しいグラフ
表現として“tetraicosa-grid” を紹介
 tetraicosa-grid のデータフォーマットである
H9CODE とH9CODEを用いたセルの合併
方法を紹介
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
57
 24分格子グラフのためのレンダリングシステ
ムの実装とセルの合併の実装を目指す。
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
58
END
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
59
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
60
EquivalentForwardFloor
SouthBerm
ｓ
ｔ
vs
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
vt
61
2008/12/17
数理モデル化と問題解決研究会
大阪大学基礎工学部
62

Download Report