コンピュータサイエンス専攻 1年 200920741 土肥 雅志 指導教官：三谷 純 福井 幸男 実世界指向の 　　　3D形状データ変換手法の提案 コンピュータサイエンス専攻　1年 200920741　土肥 雅志 指導教官：三谷　 純 福井 幸男

目次 1.研究背景 2.既存研究 3.提案手法 4.結果 5.まとめ

研究背景 近年、3D形状データを扱うことが容易になった これらの形状を実物として作成することで 更なるデータの有効活用が可能 個人が作成した形状データの増加 ウェブ上で3D形状を検索できるシステム これらの形状を実物として作成することで 更なるデータの有効活用が可能 近年、３D形状データを扱うことがとても容易になった。 左の図のような、個人で3D形状を作成できるソフトの増加や、作成する形状データの増加がまずひとつ挙げられる 右の図のような、グーグルギャラリーという3D形状を検索できるサービスの存在があげられる このように3D形状データはとても多く扱われているといえる しかし、これらは物理演算に用いることなどを除いて、パソコンの画面に表示するだけを目的としてとどまっている そこで、これらの形状を実物として作成することで、更なるデータの有効活用が可能であると考えられる (http://sketchup.google.com/3dwarehouse/) これらは、画面に表示することだけを目的としている 3 3

画面に表示することだけを目的としているため適切でない形状であることが多い 研究背景 現実世界での作成方法 厚みの無視できる板状の素材を用いる 画面に表示することだけを目的としているため適切でない形状であることが多い

研究背景 現実世界での作成方法 そのままでは実際に作成できない形状であることが多い これらの問題を自動的に修復するシステムが必要 どのように形状データを実際に作成するか？ 本研究では厚みを無視できる板状の素材を使用する場合を対象とする 具体的には形状の展開図を作成して、板状の素材で組み立てることで作成を行う しかし、ひとつ前のスライドにあったように、多くの形状は画面に表示することだけを目的としているので、 そのままでは実際に作成できない形状であることが多くなっている 左の図：形状表面の小さな穴や溝があるばあい 右の図：面同士の交差があるばあい。これは、素材同士が交差することになり、組み立てることができないということが起こる そこで、これらの問題を自動的に修復するシステムが必要となる これらの問題を自動的に修復するシステムが必要 5 5

目次 1.研究背景 2.既存研究 既存研究 既存研究を用いた場合の問題点 3.提案手法 4.結果 5.まとめ

Automatic Restoration of Polygon Models 既存研究 問題を解決できるシステムとして Automatic Restoration of Polygon Models (Stephan Bischoffら, ACM Transactions on Graphics,2005) 入力形状の意図しない小さな穴や溝を修復 形状の内側にある不要な面を削除 交差した面の解消 形状を位相的に閉じた形状として作り直す 今あげた問題を解決できるシステムとして、ARPMという2005に提案されたシステムがあげられる システムの特徴 最も大きな点として、形状を位相的に閉じた形状として作り直す、ということが上げられる システムの大まかな流れとしては 入力形状をまず3パートに分けてボクセル表現する その後、3パートに分けて形状を再構築を行い、問題を解消した形状を出力する ボクセル化 形状再構築 7 7

既存研究 Automatic Restoration of Polygon Models 実際の出力形状の画像 左の画像は外から見た図なので違いはわからないが 右の図は形状を内側から見た図で、交差した面や内部の余分な形状が消えていることがわかる 図は Automatic Restoration of Polygon Models より 8 8

既存研究の手法を用いた場合の問題点 Automatic Restoration of Polygon Models すべての形状を位相的に閉じた形状にしてしまう 1枚の素材で済む形状を、2枚の重複した面で構成してしまう 今あげた関連研究のシステムの問題点として、 すべての形状を位相的に閉じた形状にしてしまうことがあげられる これにより、1枚の素材で済む形状を、2枚の重複した面で構成してしまうことになる 図のような形状が存在したときに、青のような位相的に閉じた形状として出力されてしまうので 実際に紙で作成した場合、この様になってしまう この写真では面が二重になっている部分があり、無駄となっている そこで本研究では、このシステムを元に上記の問題を解決したシステムの作成を目的とする このシステムを元に上記の問題を解決したシステムの作成 9 9

目次 1.研究背景 2.既存研究 3.提案手法 ボクセル化、モルフォロジー演算 形状再構築 不要な穴の削除 4.結果 5.まとめ

形状のボクセル化 八分木によりボクセル化 形状全体をルートセルで囲む セル内に面が複数ある場合はセルを8つに分割 形状表面の位相を正しく取れるように、ボクセルをさらに分割する

ボクセルのモルフォロジー演算 セルのモルフォロジー演算 セルの情報を拡張することで、形状の内側と外側を区別する 青：空セル 青：EMPTY 薄緑：FULL 白：OUTSIDE 深緑：SHELL 青：空セル 薄緑：形状を含んだセル 形状の外側から、形状を　含むセルに当たるまで　　　　モルフォロジー演算 深緑：外形を構成するセル これらのセル情報を用いて形状再構築を行う

ボクセル情報からの形状再構築 形状再構築 外側と内側を区別する SHELLセル同士をつなげる 各セル内で、元の形状に近くなる位置に頂点を移動

ボクセル情報からの形状再構築 余分な面が発生しないための形状再構築 セル内で頂点の位置を調整し 入力形状に最も近くなる位置に 新しい頂点を設置する 新しい面に、新しい頂点を参照させ 位相的に開いた状態で形状再構築 が行われる 各SHELLセルに新しい頂点を作成 隣接したSHELLセルの間に 新しい面を作成 提案したシステムの修正後の形状再構築では まず同じ入力形状に対して、 先に新しい頂点を、セル内に1つずつになるように発生させる それからセルの隣接情報を元に各頂点をつないで新しい面を作成する このとき、同じ頂点群から発生する面があった場合は、面をどちらか一方削除する この操作により、余分な面を発生させず、1枚の素材で済む形状は1枚の面で構成されるようになった 14

不要な穴の削除 組み立てる上で必要のない穴 提案したシステムの修正後の形状再構築では まず同じ入力形状に対して、 先に新しい頂点を、セル内に1つずつになるように発生させる それからセルの隣接情報を元に各頂点をつないで新しい面を作成する このとき、同じ頂点群から発生する面があった場合は、面をどちらか一方削除する この操作により、余分な面を発生させず、1枚の素材で済む形状は1枚の面で構成されるようになった 15

不要な穴の削除 組み立てる上で必要のない穴 面の交差がない限り、なるべく不要な穴は避けたい 提案したシステムの修正後の形状再構築では まず同じ入力形状に対して、 先に新しい頂点を、セル内に1つずつになるように発生させる それからセルの隣接情報を元に各頂点をつないで新しい面を作成する このとき、同じ頂点群から発生する面があった場合は、面をどちらか一方削除する この操作により、余分な面を発生させず、1枚の素材で済む形状は1枚の面で構成されるようになった 面の交差がない限り、なるべく不要な穴は避けたい 16

不要な穴の削除 組み立てる上で必要のない穴の定義 組み立てた際に外側から見えない 展開図上で、一平面上に存在する 入力形状で、同じ場所に面が存在する これらの場合のみ、不要な穴として削除を行う 提案したシステムの修正後の形状再構築では まず同じ入力形状に対して、 先に新しい頂点を、セル内に1つずつになるように発生させる それからセルの隣接情報を元に各頂点をつないで新しい面を作成する このとき、同じ頂点群から発生する面があった場合は、面をどちらか一方削除する この操作により、余分な面を発生させず、1枚の素材で済む形状は1枚の面で構成されるようになった

不要な穴の削除 外形の再構築を行う 新しい頂点をFULLセルにも作成する FULLセル同士、もしくはFULLセルとSHELLセルが隣接するセルエッジ上に、新しい面を作成する 余分に穴の修復を行っている

不要な穴の削除 正しい穴の修復の選択 FULLセルで発生した頂点をSHELLセルで分割する 分割された頂点群が、平面を形成しているかを以下の数式により求める。 提案したシステムの修正後の形状再構築では まず同じ入力形状に対して、 先に新しい頂点を、セル内に1つずつになるように発生させる それからセルの隣接情報を元に各頂点をつないで新しい面を作成する このとき、同じ頂点群から発生する面があった場合は、面をどちらか一方削除する この操作により、余分な面を発生させず、1枚の素材で済む形状は1枚の面で構成されるようになった nを法線とし、平面からの二乗距離の和を誤差関数とする 頂点の共分散行列を求め、その最小固有ベクトルを形成する平面の法線とする 19

目次 1.研究背景 2.既存研究 3.提案手法 4.結果 評価実験 5.まとめ

評価実験 出力された形状を実際に作成し評価 展開図を印刷して組み立てる 評価実験では、出力された形状を実際に作成し、評価を行った 作成する素材は、厚みを無視できる板状の素材として紙を用いた 21

評価実験 提案したシステムによる出力 まず提案したシステムによる結果の図 左が入力形状 右が出力形状となる 22

評価実験 展開図を作成し、紙を用いて作成 次に紙を用いて作成した図 左の図は、システムの出力形状に対してメッシュの削減を行っている その展開図を作成し、組み立てたのが右の写真 23

評価実験 問題点の解消(面の交差) 形状の問題点の解消をそれぞれ確認する 形状の煙突の部分は、屋根の面と煙突の面で面の交差が発生していた 出力形状では、屋根の面と煙突の面は位相的につながっており、面の交差は解消されている 24

評価実験 問題点の解消(重複面の解消) 重複面の解消は、 図のような柵と床板の面が、両面にならずに正しく出力されているのがわかる 25

評価実験 不要な穴の修正 重複面の解消は、 図のような柵と床板の面が、両面にならずに正しく出力されているのがわかる 26 26

評価実験 複数の形状による出力結果 また、いくつかの形状を用いて実験を行った すべての形状で、面の交差などの問題は解消されていた 27

評価実験 複数の形状による出力結果 また、いくつかの形状を用いて実験を行った すべての形状で、面の交差などの問題は解消されていた 28 28

目次 1.研究背景 2.既存研究 3.提案手法 4.結果 5.まとめ

まとめ 3D形状を板状の素材を用いて実体化した 今後の課題 不適切な形状を自動的に修正した 面の重複を回避した 組み立てる際に不必要な穴を修正した 今後の課題 修正できる穴のバリエーションの増加

ありがとうございました

評価実験 複数の形状による出力結果 290 14994 8(128^3) 139304 57124 9(256^3) 3856 349684 処理前面数 処理後面数 最大セル分割レベル 290 14994 8(128^3) 139304 57124 9(256^3) 3856 349684 10(1024^3) また、いくつかの形状を用いて実験を行った すべての形状で、面の交差などの問題は解消されていた 32

Automatic Restoration of Polygon Models 形状を八分木でボクセル表現 隣接したセルの情報から 新しく面と頂点を作成 ボクセル表現の細密化 新しい頂点の位置決定 モルフォロジー演算による 穴の修復、内外の判定 ６パート ３パートずつ、ボクセル化と形状再構築に分けられる １，２はボクセルに分割するだけ ３パートから、説明する スムージングフィルターや ファイル出力の後処理 ボクセル化 形状再構築 33 33

八分木細分化の基準 隣接したセル内に異なる面が存在しないようにする 34

ボクセルのモルフォロジー演算 モルフォロジー演算により穴や溝の修復、内外の判定を行う 前段階により、形状はボクセル表現されている 境界のボクセルから モルフォロジー演算を行う 外側セルから拡張された形状に対して指定回数の モルフォロジー演算を行う ボクセル全体の外側から 空のセルに対して モルフォロジー演算を行う 形状がボクセル表現されている状態 水色：　　 空ボクセル 緑色：　　 形状を含むボクセル オレンジ：形状の境界 ボクセル化されている形状 ピンク： 拡張されたボクセル 白： 形状の外側 35 35

ボクセル情報からの形状再構築 この時点で余分な面が発生している (1枚で構成されるべき面が重複している) ボクセル情報を元に、新しく面と頂点を作成 各セル内のpiercing pointを、セル内で反時計周りの順になるように並び替える piercing pointをつなげ、面の隣接情報を作成する 外側セルに隣接した内側セルグリッドの辺ごとにpiercing pointを作成 piercing pointは新しい面の基準となる 繋いだpiercing point毎に新しく頂点を作成する この時点で頂点の詳細な位置は決定しない 形状の内側と外側が分かれている状態 この時点で余分な面が発生している (1枚で構成されるべき面が重複している) 白四角：形状の外側 緑四角：形状の内側(外側セル以外のセル) 赤点：piercing point ピンク線：新しい面の隣接情報 青点：新しい頂点 36 36