[go: up one dir, main page]

JP2010165344A - ボリュームデータの実時間レンダリング方法及び装置 - Google Patents

ボリュームデータの実時間レンダリング方法及び装置 Download PDF

Info

Publication number
JP2010165344A
JP2010165344A JP2009278407A JP2009278407A JP2010165344A JP 2010165344 A JP2010165344 A JP 2010165344A JP 2009278407 A JP2009278407 A JP 2009278407A JP 2009278407 A JP2009278407 A JP 2009278407A JP 2010165344 A JP2010165344 A JP 2010165344A
Authority
JP
Japan
Prior art keywords
resolution
block
main memory
blocks
frame
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP2009278407A
Other languages
English (en)
Other versions
JP5419044B2 (ja
Inventor
Yasushi Yamaguchi
泰 山口
Hiroki Takasao
大樹 高棹
Takashi Kanai
崇 金井
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
University of Tokyo NUC
Original Assignee
University of Tokyo NUC
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by University of Tokyo NUC filed Critical University of Tokyo NUC
Priority to JP2009278407A priority Critical patent/JP5419044B2/ja
Publication of JP2010165344A publication Critical patent/JP2010165344A/ja
Application granted granted Critical
Publication of JP5419044B2 publication Critical patent/JP5419044B2/ja
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Landscapes

  • Image Generation (AREA)

Abstract

【課題】
PC環境上で、大規模ボリュームデータの実時間表示を実現する。
【解決手段】
ボリュームデータの実時間レンダリング方法において、LOD制御によって各ブロックの第１の解像度を決定すると共に、第１の解像度のブロックが主メモリに存在しない場合に、より低い第２の解像度のブロックをバックアップブロックとして用意する。各フレームにおいて、次フレームの描画において必要となる第１の解像度のブロックで主メモリ上に存在しないブロックを外部記憶装置から主メモリに読み込み要求すると共に、要求された第１の解像度のブロックに対応するバックアップブロックを当該第１の解像度のブロックに優先させて外部記憶装置から主メモリに読み込む。各フレームにおいて描画の欠けが生じないように、第１の解像度のブロックないしバックアップブロックを主メモリからテクスチャメモリに読み込んで描画する。
【選択図】図６

Description

本発明は、大規模ボリュームデータの実時間レンダリング方法及び装置に関するものである。
近年の計測装置の高度化に伴い、それらから得られる膨大な数値情報を視覚的にわかりやすく表現する可視化(visualization)への関心は高まる一方である。その中でも画像内に、より多くの情報を持たせることができるボリュームレンダリングへの期待は大きく、医療現場など実際に利用される分野も多彩である。
また近年におけるGPU(Graphics Processing Unit)の発展は目覚しい。特に、そのプログラム性は飛躍的に進歩しており、ボリュームレンダリングの主要計算をGPU上で行うことが可能になった。その結果、GPUの長所である並列計算性を享受でき、ボリュームレンダリングの表示速度は飛躍的に向上している。
しかし、計測装置の高度化は、データの巨大化という新たな問題も生み出した。このようなデータの容量はグラフィックスボード上のテクスチャメモリの容量どころか、PCの主メモリのそれをも上回ることもあり、従来の描画手法を用いることは難しい。
PCは、描画に関連して、ハードディスク、主メモリ、そしてグラフィックスボード上のテクスチャメモリという3つの記憶領域を持つ。描画の際、ファイルとしてハードディスクに格納されているボリュームデータは、まず主メモリに読込まれる。その後、三次元テクスチャとしてテクスチャメモリに転送され、グラフィックスボード上でレイキャスティング法等の描画処理が行われる。
各領域の容量はハードディスクが最も大きく、主メモリ、テクスチャメモリという順に小さくなる。したがって、大規模ボリュームデータとして、ハードディスク上には格納可能であるが、主メモリの容量を大幅に超えるものをどのように扱うかが問題となる。
巨大データを表示する場合、まず行わなければならないことはデータのブロック化である。データを主メモリに載る程度の複数のブロックに分割し、これらブロックの描画を個別に行い、それらを合成することで全体の像を得る。
また、描画に用いるブロック数を削減する目的で一般的に用いられる方法が視錐台カリングである。視錐台カリングではグラフィックスAPIが定義する視錐台と同じものをCPU上でも定義し、GPUと同じ判定を行うことで、表示に不必要なブロックをクリッピングするだけでなく主メモリに読込むことも省略できる。図２に簡便のため二次元上での視錐台カリングを示す。濃色のブロックは視錐台の内部、もしくは交差しているのでメモリへ読込まれたのち描画されるが、淡色のブロックにはこれらの処理は行われない。
また、視錐台カリングと共に、ブロック数を削減する目的で用いられる方法がLOD(Level of Detail)制御である。LaMarら（非特許文献１）は低解像度データを段階的に作成し、図３に示すようなoctree構造を形成することで、ボリュームレンダリングのLOD制御を提案した。特許文献１にもoctree構造を用いた類似の技術が開示されている。非特許文献２、非特許文献３には、ウェーブレットを用いたボリュームレンダリングが開示されている。
一方、Mullerら（非特許文献４）やStrengertら（非特許文献５）は複数のPCを並列結合させPCクラスタを形成することで、主メモリ、テクスチャメモリの容量を増大させているが、一般にこれらの装置は高価であり、広く普及することは困難という欠点をもつ。
特表２００３−５１２６８５ Eric Lamar,et.al. Multiresolution techniques for interactive texture-based volumevisualization. In Proceedings of IEEE Visualization, pp.355-362, 1999 Chaoli Wangand Han-Wei Shen. A Framework for Rendering Large Time-Varying Data UsingWavelet-Based Time-Space Partitioning (WTSP) Tree, Technical ReportOSU-CISRC-1/04-TR05, Department of Computer and Information Science, The OhioState University, 8 pages, Jan 2004. Jinzhu Gao,Chaoli Wang, Liya Li, and Han-Wei Shen. A Parallel Multiresolution VolumeRendering Algorithm for Large Data Visualization Parallel Computing(Special Issue on Parallel Graphics and Visualization), 31(2):185-204, Feb2005. C.Muller,et.al. Optimized Volume Raycasting for Graphics-Hardware-based Cluster Systems.In Eurographics Symposium on Parallel Graphics and Visualization (EGPGV06),pp.59-66. Eurographics Association, 2006. MagnusStrengert, et.al. Hierarchical Visualization and Compression of Large VolumeDatasets Using GPU Clusters. In Eurographics Symposium on Parallel Graphics andVisualization (EGPGV04), pp.41-48. Eurographics Association, 2004.
本発明は、上述のＬＯＤ制御を用いた手法をさらに改良するものであり、PC環境上で、大規模ボリュームデータの実時間表示をより確実に実現する方法および装置を提供することを目的とする。
本発明は、外部記憶装置に格納されているボリュームデータを分割してなるブロックを、主メモリを経由してテクスチャメモリに転送して描画するボリュームデータの実時間レンダリング方法であって、
階層毎に異なる解像度を備えたツリー状の階層構造を用いたLOD制御によって各ブロックの第１の解像度を決定し、
第１の解像度のブロックが主メモリに存在しない場合に、当該第１の解像度よりも低い第２の解像度のブロックを当該第１の解像度のブロックに対応するバックアップブロックとして定義し、
各フレームにおいて、次フレームの描画において必要となる第１の解像度のブロックで主メモリ上に存在しないブロックを外部記憶装置から主メモリに先行読み込み要求すると共に、要求された第１の解像度のブロックに対応するバックアップブロックを当該第１の解像度のブロックに優先させて外部記憶装置から主メモリに読み込むことで、描画に先行してバックアップブロック、あるいは、バックアップブロック及び第１の解像度のブロックを主メモリに読み込み、
各フレームにおいて描画の欠けが生じないように、現フレームの描画に必要となる第１の解像度のブロックないしバックアップブロックを主メモリからテクスチャメモリに読み込んで描画する、
ボリュームデータの実時間レンダリング方法、である。
本発明は、また、外部記憶装置（典型的にはハードディスク）と、主メモリ（典型的にはＲＡＭ）と、テクスチャメモリと、プロセッサ（典型的にはマルチコアＣＰＵ）と、ディスプレイとを備えたコンピュータからなり、外部記憶装置に格納されているボリュームデータを分割してなるブロックを、主メモリを経由してテクスチャメモリに転送してディスプレイ上に描画するボリュームデータの実時間レンダリング装置であって、
前記プロセッサは、
階層毎に異なる解像度を備えたツリー状の階層構造を用いたLOD制御によって各ブロックの第１の解像度を決定し、
第１の解像度のブロックが主メモリに存在しない場合に、当該第１の解像度よりも低い第２の解像度のブロックを当該第１の解像度のブロックに対応するバックアップブロックとして定義し、
各フレームにおいて、次フレームの描画において必要となる第１の解像度のブロックで主メモリ上に存在しないブロックを外部記憶装置から主メモリに先行読み込み要求すると共に、要求された第１の解像度のブロックに対応するバックアップブロックを当該第１の解像度のブロックに優先させて外部記憶装置から主メモリに読み込むことで、描画に先行してバックアップブロック、あるいは、バックアップブロック及び第１の解像度のブロックを主メモリに読み込み、
各フレームにおいて描画の欠けが生じないように、現フレームの描画に必要となる第１の解像度のブロックないしバックアップブロックを主メモリからテクスチャメモリに読み込んで描画する、
ボリュームデータの実時間レンダリング装置、である。
本発明は、前記プロセッサを実行させるためのコンピュータプログラム、または、前記プロセッサを実行させるためのコンピュータプログラムを記録したコンピュータ可読媒体としても提供される。
１つの態様では、前記第２の解像度は、１フレームにおいて外部記憶装置から主メモリに読み込むことができるブロックの最大数Ｍｍａｘ＿ｐｅｒ＿ｆｒａｍｅを越えないように決定される。
１つの態様では、前記第２の解像度の決定は、
前記第１の解像度より１段階低い解像度のバックアップブロックを用意し、
フレーム毎に、主メモリに読み込むバックアップブロック数ＢＭ＿ｌｏａｄと１フレームあたりに主メモリに読み込めるブロックの最大数Ｍｍａｘ＿ｐｅｒ＿ｆｒａｍｅが以下の関係（０≦α≦１）を満たすかを判定し、
式を満たさない場合には、１段階低減した前記解像度をさらに１段階低解像度にして判定を繰り返し、式を満たした時の解像度を前記第２の解像度とする。
１つの態様では、前記ブロックの最大数Ｍmax_per_frameは、１ブロックあたりのハードディスク-主メモリ間の読込みに掛かる時間の平均値tM、１フレームを描画するのに要する時間の平均値tRから
で取得する。
１フレームを描画するのに要する時間の平均値tRは、前ｎフレーム（ｎ＝1,2,3・・・）で測定された１フレームを描画するのに要した時間の平均値である。
１つの態様では、外部記憶装置から主メモリへのブロックの読み込みの優先度は、
第１の解像度のブロックよりも第２の解像度のバックアップブロックの優先度が高いことに加えて、
視点からより近い領域内に存在するブロックほど、および／あるいは、スクリーン中心に近いブロックほど優先度が高い。
１つの態様では、主メモリからテクスチャメモリへのブロックの読み込みの優先度は、第２の解像度のバックアップブロックよりも第１の解像度のブロックを優先して読み込む。
１つの態様では、主メモリからテクスチャメモリへのブロックの読み込みの優先度は、テクスチャメモリの容量に余裕がある場合には第２の解像度のバックアップブロックよりも第１の解像度のブロックを優先して読み込み、テクスチャメモリの容量に余裕がない場合には第１の解像度のブロックよりも第２の解像度のバックアップブロックを優先して読み込む。
１つの態様では、１フレーム毎に、主メモリからテクスチャメモリへ読み込む第１の解像度のブロックの数ＮＴ＿ｌｏａｄおよびバックアップブロックの数ＢＴ＿ｌｏａｄの合計と、１フレーム間に主メモリからテクスチャメモリに読み込むことができるブロックの最大数Ｔｍａｘ＿ｐｅｒ＿ｆｒａｍｅとを比較して以下の関係を満たすか判定し、
式を満たす場合には、要求されたブロックをそのまま主メモリからテクスチャメモリへ読み込み、
式を満たさない場合には、第２の解像度のバックアップブロックを優先して主メモリからテクスチャメモリへ読み込む。描画に必要な第１の解像度のブロックがテクスチャメモリに読込まれていなければ、描画に必要な第１の解像度のブロックが主メモリに読み込まれていたとしても、主メモリに読み込まれている第２の解像度のバックアップブロックを優先してテクスチャメモリに読み込むことによって、描画の欠けが生じることを防止する。
１つの態様では、前記ブロックの最大数Ｔｍａｘ＿ｐｅｒ＿ｆｒａｍｅは、１フレームを描画するのに要する時間の平均値ｔＲ、1ブロックあたりの主メモリからテクスチャメモリへの読込みに掛かる時間の平均値ｔＴ、使用者が設定した1フレームの描画に費やすことができる最大時間ｔｍａｘ、前フレーム描画時にテクスチャメモリに読込まれた現解像度ブロック数ＮＴ＿ｌｏａｄ＿ｐｒｅｖ、前フレーム描画時にテクスチャメモリに読込まれたバックアップブロック数ＢＴ＿ｌｏａｄ＿ｐｒｅｖから、
で取得する。
すなわち、実測値tM、ｔＲ、ｔＴを利用して、ユーザが指定できる値ｔｍａｘを保証するようにバックアップブロックの解像度、主メモリからテクスチャメモリへの読み込みの優先度を制御する。
１つの態様では、使用者が設定した1フレームの描画に費やすことができる最大時間ｔｍａｘは、フレームレート（より具体的にはフレームレートの逆数）に基づいて設定される。
１つの態様では、前記次フレームの描画において必要となる第１の解像度のブロックで主メモリ上に存在しないブロックの読み込み要求は、
視錐台カリング用の描画用視錐台に加えて、読み込み要求を発行するための読み込み用視錐台を定義し、前記描画用視錐台と前記読み込み用視錐台は同形であり、
フレーム間での描画用視錐台の位置の変化から、次フレームでの描画用視錐台の位置を予測して、予測位置に読み込み用視錐台を配置し、
読み込み用視錐台内にあり、かつ主メモリに存在しないブロックに対して読み込み要求を発行する。
１つの態様では、現フレームの描画に必要な第１の解像度のブロックがテクスチャメモリに存在するか判定し、存在する場合にはテクスチャメモリに存在する第１の解像度のブロックを描画し、
第１の解像度のブロックがテクスチャメモリに存在しない場合に、当該第１の解像度のブロックが主メモリに存在するか判定し、存在する場合には第１の解像度のブロックあるいはバックアップブロックを主メモリからテクスチャメモリに読み込んで描画する。
主メモリに関しては、第1解像度ブロックが存在する場合には、必ずバックアップブロックが存在する。
テクスチャメモリに関しては、第１の解像度ブロックだけしかない場合、バックアップブロックだけしかない場合、両方が存在する場合のいずれもあり得る。第１の解像度ブロックとバックアップブロックが両方が存在する場合には、第1の解像度ブロックが描画に利用される。
「第１の解像度」は、何等かの手法で望ましい解像度として決定された解像度であり、従来のLOD制御により取得された解像度であってよい。
１つの態様では、前記第１の解像度の決定は、
スクリーン上に投影されたボクセルの大きさが１ピクセルよりも小さくなる直前の解像度を最適解像度と定義し、
フレーム毎に最適解像度ブロックの数とテクスチャメモリに読み込むことができるブロックの最大数とを比較し、最適解像度ブロックの数が最大数以下となるまで最適解像度ブロックの解像度を低減させた時の解像度を第１の解像度とする。
１つの態様では、前記第１の解像度の決定は、
フレーム毎に最適解像度ブロックの数を取得し、
最適解像度ブロックの数とテクスチャメモリに読み込むことができるブロックの最大数とを比較し、
最適解像度ブロック数が最大ブロック数を越える場合には、最適解像度ブロックの解像度を１段階低解像度に更新すること、を備え、
前記比較と前記更新を、最適解像度ブロックの数が最大ブロック数以下になるまで繰り返した時の解像度を第１の解像度とする。
１つの態様では、前記最適解像度の決定は、
ツリー状の階層構造の中で低い解像度を備えたブロックにおいて、視点から最も離れているブロックの中で、その中でも最も離れているボクセルを透視投影しスクリーン上の大きさを計算し、
スクリーン上での大きさが下記式を満たすか否かを判定し、満たす場合には一段階高解像度のノードを探索し、この判定を繰り返して最適解像度を決定する。
１つの態様では、毎回最低の解像度(ツリー状の階層構造の根)から辿っていく。また、実際に利用している最適解像度から出発して、その前後を探ってもよい。
１つの態様では、前記LOD制御による各ブロックの第１解像度の決定は、視点から各ブロックまでの距離及びテクスチャメモリの容量に基づいて行なわれる。
１つの態様では、前記ツリー状の階層構造は、ｏｃｔｒｅｅである。
１つの態様では、前記ツリー状の階層構造は、ウェーブレット木(wavelet tree)である。ウェーブレットを用いた解像度の決定については、当業者に知られており、例えば、非特許文献２、非特許文献３を参照することができる。
また、本明細書において、解像度を１段階「上げる」、「下げる」とは、ツリー状の階層構造の階層を「下げる」、「上げる」ことを意味する。
本発明では、描画に先立って望ましい解像度である第１解像度のブロックに対応するバックアップブロックを優先的に主メモリに読み込んでおくことによって、テクスチャメモリの容量の余裕に応じてバックアップブロックを用いて描画することで各フレームにおける描画の欠けを防止することができる。
本発明では、バックアップブロックの解像度、主メモリからテクスチャメモリへの読み込みの優先度を制御することで、各フレームにおける描画の欠けを防止する。
本発明のその他の効果は、請求項に記載の構成、明細書に記載の事項から当業者において認識される。
［Ａ］本発明の背景技術
本発明の背景となる一般的な概念および手法について説明する。これらの概念および手法は本発明の従来技術であると同時に、本発明の実施形態を実施する上でも用いられ得る技術である。
［Ａ−１］ボリュームレンダリング
ボリュームレンダリングはCTやMRIなどを用いた計測や、シミュレーションなどから得られるボリュームデータを直接スクリーンに投影する手法の総称である。等値面表示とは異なり、視線上のデータの積分値を表示することが特徴である。近年ではボリュームレンダリングの主要計算をGPU(Graphics Processing Unit)上で行うことが主流となっている。GPUを用いてボリュームレンダリングの計算を行うことによる最大の利点は、GPUの持つ並列性を享受できる点である。
GPUを用いたボリュームレンダリングには、主にテクスチャベース法、スプラッティング法、そしてレイキャスティング法がある。本発明の実施形態では、レイキャスティング法を採用しているが、本発明で用いられるボリュームレンダリングはレイキャスティング法に限定されるものではない。
［Ａ−２］巨大データの表示に用いられる一般的な概念および手法
［Ａ−２―１］ＰＣ内の記憶領域とデータの流れ
一般的に、ＰＣはハードディスク、主メモリ、そしてグラフィックスボード上のビデオメモリという3つの記憶領域を持つ。描画の際、ファイルとしてハードディスクに格納されているデータは、まず主メモリに読込まれる。その後、ビデオメモリに転送され、グラフィックスボード上で描画処理が行われる。
ビデオメモリへの読込みはOpenGL等のグラフィックスAPIが提供する機能を用いて実行される。OpenGLを用いる際、ポリゴンデータの読込みは、通常VBO(Vertex Buffer Object)という拡張機能によってビデオメモリ内にバッファーオブジェクトと呼ばれる領域を確保することで実現される。一方、ボリュームレンダリングを行う際には、ボリュームデータを3次元テクスチャとして扱い、ビデオメモリ内のテクスチャメモリと呼ばれる領域に読込んだ後、レイキャスティング法等を用いて描画される。
これら各領域の容量はハードディスクが最も大きく、主メモリ、テクスチャメモリという順に小さくなる。本実施形態で対象とする大規模ボリュームデータは、ハードディスク上には格納可能であるが、主メモリおよびテクスチャメモリの容量を超えるため読込むことができないものとする。
［Ａ−２−２］ブロック化
主メモリに乗り切らないデータを扱う際に、まず行わなければならないことはデータのブロック化である。データを主メモリに載る程度の複数のブロックに分割し、これらブロックの描画を個別に行い、それらを結合することで全体の像を得る。
ボリュームデータに対してブロック化を施す際には、各ブロックの境界データを重複させて持たせておく必要がある。なぜなら、トリリニア補間を施す際、重複させていないブロックを用いると境界付近の補間計算を正しく行えないからである。したがって、重複させないブロックのｘ，ｙ，ｚ方向のボクセル数をそれぞれNx，Ny，Nzとすると、実際のブロックの大きさは両端1ボクセルを重複させるのでNx+2，Ny+2，Nz+2（ボリュームデータ全体での境界に位置するブロックならNx+1，Ny+1，Nz+1)となる。
また、ブロック化したデータを用いてボリュームレンダリングを行うためには上述のように各ブロック内だけでなく、ブロック間においてもfront-to-back方式、またはback-to-front方式に則って処理を行う必要がある。そのため、ボリュームを見る角度が変化する毎に、各ブロックを視点からの距離をもとにソーティングしなければならない。
［Ａ−２−３］カリング
上述のブロック化を施すことで、主メモリの容量を超えた大きさのデータも表示することが可能になる。しかし、ただ単純にデータをブロック化しただけではデータの総容量に変化はない。それどころか、ボリュームデータを扱う場合では上述のようにブロックに要素を重複させて持たせているため、表示に必要な総データ量は増加してしまう。したがって、この総データ量が主メモリよりも大きい場合、表示を行うたびにブロックを主メモリに入れ替えなければならず、表示速度は総データ量が主メモリよりも小さい場合と比べて大幅に遅くなってしまう。そこで、表示に不必要なブロックは主メモリへの読込みを行わないようにするための機構がカリングである。よく用いられるカリングには、視錐台カリングやオクルージョンカリングなどが存在する。視錐台カリング、オクルージョンカリングは共に、大規模なポリゴンデータのレンダリングに有効な手法であり、そのままボリュームレンダリングにも適用することが可能である。
［Ａ−２−３−１］視錐台カリング
視錐台とは視線ベクトル、画角、ウィンドウのアスペクト比、前方クリッピング面、後方クリッピング面から定義される立体であり、ボリュームレンダリングに限らずコンピュータグラフィックス全般で用いられる（図１）。視錐台の内部に存在するオブジェクトのみが最終的にウィンドウに表示される。通常、視錐台はGPU上で定義され、視錐台に含まれないオブジェクトの非表示（クリッピング）を担当する。
視錐台カリングでは同じものをCPU上でも定義し、GPUと同じ判定を行うことで、表示に不必要なブロックをクリッピングするだけでなく主メモリに読込むことを防ぐことができる。図２に簡便のため二次元上での視錐台カリングを示す。濃色のブロックは視錐台の内部、もしくは交差しているのでメモリへ読込まれたのち表示されるが、淡色のブロックにはこれらの処理は行われない。
視錐台カリングを行う際に必要な、オブジェクト-視錐台間の位置関係の計算方法には様々なものがあるが、Ulfらは視錐台と、ワールド座標系の座標軸に沿って向きが整列されたバウンディングボックス(Axis Aligned Bounding Box :AABB)との位置関係の計算の高速化を提案している（Ulf Assarsson and
Tomas Moller. Optimized view frustum culling algorithms for bounding boxes.
journal of graphics tools, Vol. 5, No. 1, pp. 9.22, 2000.）。ボリュームレンダリングでは、ブロックの幾何情報をそのままAABBに適用して用いることが可能なので、この手法はとても扱いやすい。
［Ａ−２−３−２］オクルージョンカリング
オクルージョンカリングとは、複数のオブジェクトが存在する際に、オブジェクトの影に隠れて見えない（オクルージョンの状態）オブジェクトの読込み、計算を省略するための処理である。オクルージョンカリングを用いることによって、メモリへの読込み、頂点処理、フラグメント処理等の全ての処理を省略できるという利点がある。オクルージョンカリングの実装には、OpenGLの拡張機能であるARB_occlusion_queryを用いる。この機能は簡単に言うと、奥行きテストやアルファテストを通過して実際に描画に採用されるフラグメント数を、CPU側に通知する機能である。
オクルージョンカリングを行うためには、視点に近いオブジェクトから順次表示を行わなければならないため、各オブジェクトを視点からの距離を基にソーティングする。つまりfront-to-back方式で表示を行う。各オブジェクトの処理は二段階で行われる。まず、オブジェクトを完全に包含するバウンディングボックスを描画し、ARB_occlusion_queryで表示に採用されるフラグメント数を計測する。もしこのフラグメント数がゼロであったら、このオブジェクトの処理を行ったとしてもスクリーンには表示されないと判断できるのでカリングできる。
ボリュームレンダリングにおいても、メッシュのレンダリングの場合とほぼ同様の処理を行うことができる。すなわち、ブロックの持つ幾何情報と同一のものを、一段階目のバウンディングボックスとして用いることができる。しかし一つだけ異なることは、フレームバッファのアルファ値を見てフラグメントの採用、不採用を判定しなければならない点である。この問題はOpenGLの関数であるglAlphaFunc(GL_LESS,threshold)を用いることで解決できる。バウンディングボックスのアルファ値をフレームバッファのそれに設定することで、フレームバッファのアルファ値がまだthresholdより小さい場合にのみフラグメントは採用される。つまり、フレームバッファのアルファ値がまだ小さいため、ブロックの表示が最終的な表示に貢献すると判断できる。
［Ａ−２−３］木構造を用いたLOD制御
上述のカリングを用いることによって、表示に必要なブロックのみをメモリに読込むことが可能になる。しかし大規模データの持つ高解像度性をそれほど必要としない場合、たとえば視点との距離が大きく離れており表示される像がとても小さい場合には、このデータを用いることは読込みの非効率を招くばかりか、エイリアスの原因にもなってしまう。
そこで一般的に用いられる方法がLOD(Level of Detail)制御である。ポリゴンモデルを用いる際は、まず前処理で、与えられたモデルから頂点数の少ないデータを段階的に作成後、それらを用いて木構造を形成する。表示の際には、この木構造を用いて深さ優先探索を行い、適切な解像度のモデルを選択して描画を行う。LOD制御を用いることで、描画に不必要なデータの読込みが抑えられる。
LaMarらは与えられたボリュームデータから低解像度データを段階的に作成し、これらを用いて図３に示すようなoctree構造を形成することで、ボリュームレンダリングのLOD制御を提案した（非特許文献１）。octreeのトラバース時に、各ノードで探索判定を行うが、その結果は以下の三通りのいずれかになる。
（１）このノードに対応するブロックを描画せず、子ノードの探索も行わない。たとえばカリングが行われた場合がこれに当たる。
（２）このノードに対応するブロックを描画し、子ノードの探索は行わない。
（３）このノードに対応するブロックを描画せず、子ノードの探索のみを行う。
また探索判定は通常、視点とブロックの中心座標との距離や、図４のように画角αとブロックの両端点と視点がつくる角βとの比を用いて行われる。
［Ａ−２−４］データのキャッシング
上述のように、大規模なデータを描画するためには複数のブロックに分割することが必要である。また視錐台カリングを用いることで主メモリおよびビデオメモリへの読込み、そして描画を行うブロックの数を制限することが可能になった。このとき、視錐台カリングを免れるブロックは、よほど視錐台の位置が急激に変化しない限り、１フレーム前でのそれとほぼ同一である。そのためフレーム毎にそれらのブロックをハードディスクから取り出してくることは無駄であり、主メモリ、ビデオメモリ上にキャッシュとして保管しておくことで効率的なブロック読込みが可能になる。
GPU上でボリュームレンダリングの計算を行う場合、対象となるブロックをGPUのテクスチャメモリに保管しておく方が、主メモリからの転送時間が省略できるため効率的である。しかしテクスチャメモリの容量は一般的に主メモリのそれよりも小さい。たとえば、NVIDIA社のGPUであるGeForce 8800 Ultraは現行機の中で最もハイスペックなものの一つ（2008年2月時点）であるが、ビデオメモリの容量は768MBであり、その部分領域であるテクスチャメモリの容量は、ギガバイト単位の容量が当たり前になっている主メモリと比較するとやはり小さい。したがって、CPUのL1、L2キャッシュのように二段階でキャッシュ構造を構成し、より描画に用いられる可能性があるものほどテクスチャメモリに保管する方法が取られる。また、キャッシュメモリ内でのブロックの管理のために、LRU(Least Recently Used)等のOSのメモリ管理のような機構が必要になる。
［Ｂ］本発明に係るシステム及び方法の実施形態
上述のLOD制御を用いた手法は有用であり表示の効率性の向上を期待できるが、以下に示す問題点が依然として残っている。
（ア）全体の描画速度は描画するブロックの数に概ね比例するため、ブロックの解像度変更と描画速度には密接な関係が存在する。また、ブロックの解像度はスクリーンの解像度に依存するべきであるが、上記LOD制御を用いた探索判定法はこのことを考慮しておらず、結果として、描画と描画速度のトレードオフを調整することが困難である。
（イ）ハードディスクからのブロック読込みに掛かる時間は一般的に描画速度に比べて非常に大きいものであり、読込みの間に描画を止めたとすると、動きが間歇的になってしまう。
（ウ）描画に必要なブロック数はカリング、LOD制御の持つパラメータによって大きく変化する。しかし、このブロック数はこれらの要因だけでなく、主メモリ、テクスチャメモリ内に読込むことができるブロックの最大数、または読込みに掛かる時間を考慮して決定されるべきである。
本実施形態は課題（ア）を解決するために「スクリーンの解像度を考慮した探索判定法」、課題（イ）の解決に「マルチコアCPUを利用するマルチスレッド化」、課題（ウ）を解決する方法として「実行環境を考慮したブロック解像度制御」を提案する。上述の従来の手法に加えて、これらの提案手法を実装することで、より実用的なボリュームレンダリングシステムの実現が可能になる。
［Ｂ−１］スクリーンの解像度を考慮したLOD制御
描画対象データのLODを制御するためのoctreeの探索判定法として、視点とブロックの中心座標との距離や、画角とブロックの両端点と視点がつくる角との比が用いられることを述べた。これらLOD制御の計算は比較的単純であり扱いやすいため、広く用いられているが、スクリーンの解像度に非依存である。しかしながら、スクリーンの解像度とブロックの解像度は本来密接な関係がある。たとえば、ブロック解像度＞スクリーン解像度、の場合は、スクリーン上の1ピクセルの大きさより1ボクセルが小さくなってしまいエイリアスの原因となってしまう。そこで本実施形態では新たにスクリーンの解像度を考慮した探索判定法を提案する。
探索判定の際、まずブロックを一段階高解像度なブロックに分割する。次に図５に示すように、分割された高解像度ブロックにおいて、視点から最も離れているブロックの中で、その中でも最も離れているボクセルを透視投影しスクリーン上の大きさを計算する。このスクリーン上での大きさが式(1)を満たした場合にのみ、実際に一段階高解像度のノードを探索する。
このとき、Ｖｓｉｚｅはスクリーン上でのボクセルの大きさ、Ｐｓｉｚｅは1ピクセルの大きさを表す。この判定を繰り返すことで解像度(LOD)を制御する。つまりブロックの解像度を、投影されたボクセルの大きさが1ピクセルより小さくなる直前まで上げるため、この解像度がエイリアスを発生させない範囲での最高解像度であるといえる。このときのブロックの持つ解像度を最適解像度、これらのブロックを最適解像度ブロックと呼ぶことにする。スクリーンの解像度に合わせた最適解像度ブロックを用いることで、描画の画質を常に最高のものに保つことができる。
しかし、スクリーン解像度が非常に高い場合、当然描画に用いられる最適解像度ブロックの数も多くなるが、その数がテクスチャメモリ容量、すなわち、テクスチャメモリにブロックを読込むことができる最大数を超えてしまう恐れがある。このような状態に陥ると、描画に必要な最適解像度ブロック数とテクスチャメモリに搭載できる最大ブロック数との差分を、1フレーム描画する毎に読込まなくてはならず、描画速度は著しく低下してしまう。
そこで、このような場合では、ブロックの解像度を最適解像度から適切な段階まで低くし、描画に用いるブロックの数をテクスチャメモリに載り切るまで少なくすることで対処する。この処理を行った後、描画に用いられるブロックを現解像度ブロックと呼ぶことにする。
現解像度ブロックの具体的な計算法は、［Ｂ−３］で詳述するが、以下に簡単に述べる。まずフレーム毎に、最適解像度ブロックの数を得る。そしてその結果をＮｎｅｅｄ、テクスチャメモリに読込むことができるブロックの最大数をＴｍａｘとし、以下の式を満たすかどうか検査する。
式(2)を満たさない場合、ブロックの解像度を1段階低解像度にし、再度検査する。この検査は式(2)を満たすまで繰り返し行われる。この処理を行った後、描画に用いられるブロックを現解像度ブロックと呼ぶことにする。これによって、描画時にテクスチャメモリの容量超えに伴う、テクスチャメモリへのブロック読込みを防ぐことができ、描画速度を安定化できる。
［Ｂ−２］マルチコアCPUによるマルチスレッド化
現在市場で流通しているCPUは、デュアルコア等複数のプロセッサを一つのダイに搭載した、いわゆるマルチコアCPUが主流である。また、近年のCPUはマルチスレッドプログラミングに対応していることが当然であり、一つのプログラム内で複数のスレッドによる処理が可能である。さらに、マルチコアCPUを利用してマルチスレッドプログラミングを行うと、スレッド数がコア数以下であれば、各スレッドはコアを単独で使用することができ、完全な並列計算が可能になる。尚、クワッドコアCPUやコアを10〜100個搭載するメニイコアを用いることで、ブロックの主メモリへの読込み要求処理の増大を回避できると考えられる。
本実施形態ではOpenGLを用いているが、実験が行なわれた時点ではOpenGL自体はマルチスレッドに対応しておらず、複数のスレッドからGPUへOpenGL命令を発行することは不可能である。そこで本実施形態では以下に示す2つのスレッドを定義し、お互いに独立して処理を行うことで効率化を図る（尚、Microsoft社が開発しているグラフィックスAPIであるDirectX 10はマルチスレッドに対応しているため、これを利用することで、ブロックのテクスチャメモリへの読込みと描画を別スレッドで実行する等の効率化を図れる。）。
読込みスレッド：ハードディスクから主メモリへのブロックの読込みを行う。主メモリ-テクスチャメモリ間の読込みはOpenGLの関数を用いなければならないため、担当しない。
描画スレッド：主メモリ-テクスチャメモリ間のブロックの読込みおよび描画を行う。
読込みスレッド、描画スレッドの他に、両スレッドからもアクセスできる共有メモリを設ける。なおこの共有メモリは主メモリ上のキャッシュと同一の働きをするものである。
また、両スレッドはブロック自体のデータが格納される領域だけでなく、共有メモリ内のどの位置にどのブロックが格納されているかというブロック情報も共有する。ブロック情報は、読込みスレッドによって、ブロック読込み完了時または共有メモリからの消去時に更新される。描画スレッドは、ブロック情報を参照することにより、所望のブロックが共有メモリに読込まれているか否かを随時知ることができる。図６にマルチスレッド化による処理の流れを示す。
描画スレッドは、まず描画に必要な現解像度ブロックがテクスチャメモリに存在するか否かを確認し、存在するならそのまま描画（図６、1-1）、しないなら主メモリ（共有メモリ）を見る（図６、1-2）。当該現解像度ブロックが主メモリ（共有メモリ）に載っているなら、そのブロックをテクスチャメモリに読込んだ後に描画を行うが、主メモリ（共有メモリ）上にも存在しない場合には描画を行わない。
さらに描画スレッドは、次のフレームで必要となるブロックで、主メモリ（共有メモリ）上に存在しないものをハードディスクから主メモリへ読込むように、読込みスレッドに要求を出す（図６、2）。
読込みスレッドは、要求を出されたブロックのうち、優先度の値の高いものから順に主メモリ（共有メモリ）へ読込む。優先度の計算法は［Ｂ−４−１］で述べる。
このように処理を分割することで、描画の際にハードディスクから主メモリへの読込みを待つ必要がなくなり、大幅な描画速度の向上が得られる。
［Ｂ−２−１］ブロックの先行読込み
描画スレッドがブロックの読込み要求を発行するタイミングは、そのブロックを正に描画する時では遅い。なぜなら、描画スレッドは要求を発行後、即座に次のブロックの処理に移るため、そのフレームにおいては、要求したブロックを描画することはできないからである。
そこで、ブロックの読込み要求を描画に対し先回りして行うことでこの問題に対処する。具体的には、まず、既に述べた視錐台カリングのために用意する視錐台に加えて、読込み要求を発行するための視錐台を定義する。前者を描画用視錐台、後者を読込み用視錐台と呼び、両者とも同形とする。
つまり、図７のように、グラフィックスAPI（OpenGL）が定義する視錐台と全く同じ形のものを、CPU上に2つ用意する。そして、フレーム間での描画用視錐台の位置の変化から、次フレームでの描画用視錐台の位置を予測し、その位置に読込み用視錐台を配置する。読込み用視錐台内にあり、かつ主メモリ（共有メモリ）に存在しないブロックに対して読込み要求を発行することで、描画に先行して主メモリへの読込みを行う。
［Ｂ−２−２］低解像度ブロックを用いたバックアップ
一般的に、ハードディスクからの読込みに掛かる時間は、CPU上での処理に掛かる時間に比べて圧倒的に長いため、先行してブロックの要求を行ったとしても、描画に間に合わない可能性がある。その結果、描画が図８のように欠ける状態が生じてしまう。特に、視錐台が大きく移動した場合や解像度の変更が行われた際に、新たに大量の現解像度ブロックを主メモリに読込む必要があるため、このような欠損が大きく目立つ。
そこで、現解像度ブロックより1段階低解像度なブロックを予めバックアップとして主メモリに読込んでおく。描画に必要な現解像度ブロックが主メモリに読込まれていない場合には、このブロックを代わりに用いることで、結果が欠けてしまう事態を防ぐ。現解像度ブロックよりも低い解像度であるために、生成される画質は劣るが、全く欠けているよりは自然な結果が得られる。この低解像度ブロックを用いた描画を行う処理のことをバックアップ処理、また補完に用いられる低解像度ブロックをバックアップブロックと呼ぶことにする。
また、バックアップブロックの解像度は、現解像度ブロック同様、実行環境（例えば、移動量）に従って変化させる必要がある。視錐台の移動が大きくなるにしたがって、バックアップブロックが主メモリにキャッシングされている可能性が小さくなり、ハードディスクから読込む数が増える。バックアップブロックの読込みは現解像度ブロックよりも優先されるが、このような場合、新たに主メモリに読込むバックアップブロックの数がハードディスク-主メモリ間の転送率を超えてしまう可能性がある。その結果として、バックアップブロックの読込みが間に合わず、バックアップの機能が働かずに、欠けている箇所が目立ってしまう。そこで、バックアップブロックの解像度を低くすることで、新たに読込むバックアップブロックの数を減らし、このような事態を未然に防ぐ。
バックアップブロックの具体的な計算法の詳細は、［Ｂ−３−２］に述べるが、以下に簡単に記載する。まずフレーム毎に、主メモリに読込むバックアップブロックの数ＢＭ＿ｌｏａｄを求める。そしてプログラム起動時に算出される、1フレームあたりに主メモリに読込めるブロックの最大数Ｍｍａｘ＿ｐｅｒ＿ｆｒａｍｅを用いて、以下の式を満たすかどうか検査する。
αは、０≦α≦１の範囲を持つパラメータである。式(6)を満たさない場合、解像度を1段階低解像度にして、再度検査を行う。この検査は、式(6)を満たすまで繰り返し行われる。この手法によって、予測できない視錐台の変化にも柔軟に対処することが可能になる。
［Ｂ−３］実行環境を考慮したブロック解像度制御
［Ｂ−１］で現解像度ブロック、また［Ｂ−２−２］でバックアップブロックの解像度を変化させることの必要性を述べたが、これらの問題は、記憶領域の容量や、記憶領域間の転送率等のシステムを作動させる環境に大きく依存する。そこで、記憶領域内に読込めるブロックの最大数の取得は勿論のこと、描画処理全体に掛かる時間や、ハードディスク-主メモリ間および主メモリ-テクスチャメモリ間のブロックの読込みに掛かる時間等を常に監視し、それらの情報を元に、現解像度ブロック、バックアップブロックの解像度を変化させることで、読込むブロックの数を調整する。
［Ｂ−３−１］現解像度ブロックの解像度調整
解像度の調整は、現解像度ブロックから先に行われる。まずフレーム毎に、［Ｂ−１］の探索判定法で計算された最適解像度ブロックが、描画にいくつ必要であるかを、octreeを探索することで調べる。そしてその結果をNneed、プログラム起動時に取得したテクスチャメモリに読込むことができるブロックの最大数をTmaxとし、以下の式を満たすかどうか検査する。
式(2)を満たさない場合、最適解像度ブロックを1段階低解像度にしたブロックをoctreeで探索し、その後再度検査する。この調査は式(2)を満たすまで繰り返し行われる。そして、式を満たした段階の解像度のブロックを現解像度ブロックとし、主メモリに読込む。
この手法を用いることで、テクスチャメモリの容量を考慮して、描画に必要な現解像度ブロックの数を決定することができる。これによって、描画時にテクスチャメモリの容量超えに伴う、テクスチャメモリへのブロック読込みを防ぐことができ、安定した描画速度が得られる。
［Ｂ−３−２］バックアップブロックの解像度調整
つづいて、バックアップブロックの解像度調整について議論する。現解像度ブロックのときと同様、フレーム毎にoctreeを探索し、必要なバックアップブロックの数Bneed、および既に主メモリに読込まれている数BM_existを取得する。すると、これから主メモリに読込まなくてはならないバックアップブロックの数BM_loadは以下の式から得られる。
バックアップブロックも現解像度ブロック同様、主メモリに収める必要があるので、主メモリに読込むことができるブロックの最大数をMmaxとすると、既に求められた描画に必要な現解像度ブロックの数Nneedを用いて、以下の式を満たす必要がある。
次に、１フレームあたりに主メモリに読込むことができるブロックの最大数Mmax_per_frameは、１ブロックあたりのハードディスク-主メモリ間の読込みに掛かる時間の平均値tM、前フレームで測定された１フレームを描画するのに要する時間tRから以下の式で得ることができる。
したがって、安定したバックアップブロックの読み込みを行うためには、以下の式を満たす必要がある。
ここでαは、0≦α≦1の範囲を持つパラメータである。バックアップブロックの解像度を変更した直後は、新たな解像度のバックアップブロックは主メモリには1つもキャッシングされていないので、全てのブロックを読込む必要がある（以前にそのブロックを読んだことがあり、たまたま主メモリ上に残っている場合もあるが）。よって、バックアップブロックの解像度変更を、ハードディスク−主メモリ間の転送速度ぎりぎりのところで行ってしまうと、変更直後に大量のバックアップブロックを読むことになってしまい、全てを読込むために大きな時間が掛かってしまう可能性がある。そこで、パラメータαを用いてMmax_per_frameの値をある程度小さくすることで、解像度変更後のバックアップブロックの読込み量を抑えることが可能になる。式(4)、(6)を満たさない場合、バックアップブロックの解像度を1段階低解像度にし、octreeを探索しブロック数を取得後、再度検査する。この調査は、現解像度ブロックのときと同様、式(4)、(6)を満たすまで繰り返し行われる。
この手法によって、バックアップブロックの解像度を変化させ、読込むブロックを調節することで、予測できない視錐台の変化にも柔軟に対処することが可能になる。
［Ｂ−４］ブロックの読込み優先度計算
ここまでの段階で、現解像度ブロック、バックアップブロックの解像度を決定することができた。つぎに、具体的にこれらのブロックを主メモリ、テクスチャメモリに読込む際に行われる処理について述べる。
［Ｂ−４−１］ハードディスクから主メモリへの読込みにおける優先度計算
主メモリへの読込みにおける優先度の計算は、ビット演算を用いて行う。描画スレッドによって、あるブロックの読込み要求が出された際、読込みスレッドがそのブロックを読込むために必要な情報（階層、ブロックが表す位置等）が、読込み待ちセットに登録される。
読込み待ちセットは配列で実装されており、ブロック情報が登録される要素一つ一つに64ビットのビット配列が関連付けられている。ビット配列は図９のように、5ビット単位で管理される。ブロック情報が読込み待ちセットに登録された際、その格納先に関連付けられたビット配列の先頭５ビットが図９に従って更新される。
左端の1ビットは、通常解像度のブロックとバックアップブロックを区別するためのものである。バックアップは現解像度ブロックが主メモリに存在しない場合に行う処理であるため、バックアップブロックは当然現解像度ブロックに対して優先的に読込む必要がある。したがって、主メモリへの読込みにおける優先度計算では、バックアップブロックの優先度を高める工夫が施される必要がある。よって、バックアップブロックには1、現解像度ブロックには0を割り当てる。
右側の4ビットは、要求を受けたブロックが、視錐台のどの位置に存在するのかを表す。一般的にハードディスクからの読込みは時間が掛かるため、要求を受けたブロックを全て読込むためには相当な時間が必要となる。そこで、描画結果に影響を与えやすいブロックから優先的に読込みを行わせるため、ブロック要求の優先度を視錐台内の位置に従って調節する。
ボリュームレンダリングは半透明な描画を行うが、前方のブロックを描画することで不透明度の累積値が大きくなるため、後方に位置するブロックほど最終的な描画結果に貢献する可能性は少ない。
そこでクリッピング面に平行な面を用いて視錐台を複数の領域に分割し、視点からより近い領域内に存在するブロックほど読み込みの優先度を高くする。この分割を距離分割と呼ぶ。
また、スクリーン中心に近いブロックほど使用者が注目しているという仮定のもと、視錐台を複数の円錐台を用いて分割する。この分割法はスクリーン中心分割と呼ぶ。
図１０に分割された視錐台を示す。ブロックが存在する位置が、図内に示されている領域1であれば11、領域2であれば10、そして領域3であれば01で、距離分割とスクリーン分割に対応する各2ビットを更新する。
なお、ここで説明した5ビットの更新は、ブロック情報を読込み待ちセットに登録した段階だけでなく、既に読込み待ちセットに登録されたブロック情報に対しても、そのブロックの位置が視錐台内であれば適用される。
読込みスレッドは、読込み待ちセット内のビット配列を整数値に置き換えて比較を行い、値が最も大きいビット配列に関連付けられたブロックを共有メモリ内の空いている領域に読込む。読込みが完了した後、読込み待ちセット内の全ビット配列に5ビット右にシフト演算が施される。また、読込み待ちセットだけでなく、共有メモリの制御にもここで述べた同様のビット演算が用いられている。読込みの際、共有メモリに空きがない場合は、共有メモリ内のビット配列を比較し、最も値が小さいブロックに上書きを行う。ここで、主メモリ、テクスチャメモリに共通して、各スレッドがデータを読み込もうとした際に、空き領域がなくなると、必要性の低い領域に上書きを行なう。その際に、不要なブロックの情報が消滅する。
［Ｂ−４−２］主メモリからテクスチャメモリへの読込みにおける優先度計算
既述のように、バックアップブロックは通常、欲しい現解像度ブロックがテクスチャメモリおよび主メモリのいずれにもない場合にのみ、テクスチャメモリに読込まれる。したがって、テクスチャメモリへ読込む際の優先度は、現解像度ブロックが高く、バックアップブロックが低いといえる。
しかし、この関係がプログラム実行時に常に固定であると、好ましくない事態が起こってしまう。なぜなら、たとえば描画の際、テクスチャメモリに読込まれていないが主メモリには存在する現解像度ブロックが大量に存在すると、1フレーム間にこのようなブロック全てをテクスチャメモリに読込むことになってしまい、読込みに費やされる時間が描画速度を圧迫してしまう恐れがある。
そこで、1フレーム毎に、テクスチャメモリへ読込む、現解像度およびバックアップブロックの数の合計と、主メモリ-テクスチャメモリ間の転送速度を比較し、読込むブロックの数が多すぎると判断した場合には、現解像度ブロックに代わりバックアップブロックを優先的に読込むようにする。
バックアップブロックを読込むことによって、描画に必要なブロック数を抑えることができ、ブロックの読込みに掛かる時間が描画速度を圧迫してしまう事態を防ぐことができる。
具体的な流れを説明すると、まずプログラムはフレーム毎にoctreeを探索することで、テクスチャメモリに読込む現解像度ブロックの数ＮＴ＿ｌｏａｄ、ならびにバックアップブロックの数ＢＴ＿ｌｏａｄをそれぞれ取得する。
ＮＴ＿ｌｏａｄは描画に必要な現解像度ブロックの中で、テクスチャメモリにはまだないが、主メモリには既に読込まれているものの合計である。また、ＢＴ＿ｌｏａｄは現解像度ブロックが主メモリにも読込まれていない場合に、バックアップのため主メモリからテクスチャメモリに読込まれるバックアップブロックの合計である。
比較対象である、１フレーム間にテクスチャメモリへ読込むことができるブロックの最大数Ｔｍａｘ＿ｐｅｒ＿ｆｒａｍｅは以下のようにして求める。前フレームの描画に掛かった時間をｔＲ、1ブロックあたりの主メモリ−テクスチャメモリ間の読込みに掛かる時間の平均値をｔＴ、使用者が設定した1フレームの描画に費やすことができる最大時間をｔｍａｘとする。ここでｔＲには主メモリからテクスチャメモリへのブロック読込みの時間も含まれていることを考慮して、を以下の式で定義する。
ただし、ＮＴ＿ｌｏａｄ＿ｐｒｅｖ、ＢＴ＿ｌｏａｄ＿ｐｒｅｖはそれぞれ、前フレーム描画時にテクスチャメモリに読込まれた現解像度ブロック、バックアップブロックの数である。
そして、得られた、ＮＴ＿ｌｏａｄ、ＢＴ＿ｌｏａｄ、Ｔｍａｘ＿ｐｅｒ＿ｆｒａｍｅを用いて以下の不等式を満たすか否か検証を行う。
式(8)を満たしている場合と、そうでない場合ではこれから先の処理の流れが異なる。それぞれ異なる流れを以下に示す。
式(8)を満たしている場合
現解像度ブロックおよびバックアップブロックのテクスチャメモリへの読込みが、描画速度を圧迫することはないと判断できる。よって、通常通りこれらのブロックを読込み、その後描画を行う。
式(8)を満たしていない場合
テクスチャメモリへのブロック読込みによって、描画速度が低下してしまうと判断できる。このような場合には、現解像度ブロックの読み込みは諦めて、バックアップブロックのみの読み込みを行う。具体的には、再度octreeを探索し、描画に必要な現解像度ブロックがテクスチャメモリに読込まれていなければ、現解像度ブロックが主メモリに読込まれているか否かにかかわらず、バックアップブロックをテクスチャメモリに読込む。
このとき、テクスチャメモリに読込むバックアップブロックの数は、式(8)内のものよりも大きくなる可能性がある。よって、
となることも考えられるが、このような場合にはＴｍａｘ＿ｐｅｒ＿ｆｒａｍｅを超えない数だけバックアップアップブロックを読込むようにすることで対処する。逆に、式(9)を満たさない場合には、バックアップブロックの読み込みだけではまだ余裕があると考えられるので、Ｔｍａｘ＿ｐｅｒ＿ｆｒａｍｅ−ＢＴ＿ｌｏａｄだけ、現解像度ブロックを読込む。
［Ｃ］提案システムの実験と考察
［Ｃ−１］実行結果
本システムの実行結果を述べる。本システムを構築するにあたって用いたPCのCPUは、Intel
Core2Duo6600 2.40GHz、主メモリの容量は2GBであり、GPUはNVIDIA GeForce 8800 GTX、グラフィックスボードに搭載されているビデオメモリ容量は768MBである。また、開発言語はC言語、グラフィックスAPIはOpenGL、そしてシェーダ言語はCgを用いた。また、ここで表示しているボリュームデータは、vertebral body（2048×2048×970格子、1ボクセルあたり32ビット浮動小数点、容量約15GB）である。［Ａ−２−２］で議論した重複を含めて66×66×66格子を最小のブロックとしてブロック化し、5階層のoctreeを構成した。
ボリュームを囲んでいるワイヤフレームの立方体は1ブロックを表している。ブロックはそれぞれ現解像度ブロックで描画されているが（尚、中央部分の幾つかのワイヤフレームはオクルージョンカリングされていて、テクスチャメモリに読込まれなかったブロックを示している。）、octree上の解像度は異なる。これは、奥行き差が探索判定の結果に影響を与えたためである。この時、ウィンドウサイズは640×640、描画されたブロック数は約226個で、フレームレートは約3.16フレーム毎秒であった。
［Ｃ−２］バックアップ処理の性能評価
次に、実験を通して、［Ｂ−４−２］で述べたバックアップ処理の性能について議論する。バックアップ処理とは、低解像度ブロックをバックアップブロックとして予め読込んでおくことで、視点の移動が激しい等の理由で描画に必要な現解像度ブロックの読込みが間に合わなかった場合に、描画の欠けを防ぐ処理である。つまり、バックアップ処理の性能は、ブロックの描画率によって評価できる。描画に必要とされる現解像度ブロックの総数をN、これらのうち現解像度ブロックを用いて実際に描画できた数をNnormal、バックアップブロック用いて描画できた現解像度ブロックの数をNbackupとし、これらを測定することで描画率を求められる。Snormalは現解像度ブロックのみの描画率、Sbackupをバックアップも含めたブロックの描画率とすると、これらは以下のように定義できる。
また、今回の実験は以下の手順で行った。
（i）ブロック読込み、描画は行わず、処理に掛かる時間分だけプログラムを待ち状態にする。主メモリおよびテクスチャメモリへの読込み速度（ハードディスク-主メモリおよび主メモリ-テクスチャメモリ間の転送率）は、実行環境自体が行うキャッシングによって、プログラムを実行するたびに大きく変化する。また、1ブロックを描画するために要する時間は、レイキャスティング法の特性上、ブロック内のデータに依存する。今回の実験はバックアップ処理自体の性能を評価するためのものであるので、実際の読込みおよび描画は行わず、これら処理に要する平均時間を用いてシミュレートした。また、オクルージョンカリングは無効にする。
（ii）描画対象のボリューム全体は(-1、-1、-1)、(1、1、1)であり、それに対して現解像度ブロックのサイズは1/16×1/16×1/16とする。視錐台が常に完全にボリューム内に含まれるように視点を配置するために、視点をｙ軸を中心とした半径1.0の円周上で1秒毎に角度で回転させる。
（iii）視錐台は、画角30度、アスペクト比1.0、前方クリッピング面0.3、後方クリッピング面を0.7とする。
（iv）視点が移動した度にNnormal、Nbackup、Nを測定し、これらの平均をもとにSnormal、Sbackupを計算する。なお、Nの平均値は約256であった。
ハードディスク−主メモリ間における１ブロックの読込みに掛かる時間を30[msec]、主メモリ-テクスチャメモリ間の読込み時間を2[msec]、そして1ブロックの描画に掛かる時間を3[msec]とし、角速度を変化させた場合の、Snormal、Sbackupを図１２に示す。このとき、式(5)のα値は0.6、式(7)のtmaxは1000[msec]とした。なお、比較として、バックアップを用いない場合の描画率も示す。
このグラフを見ると、バックアップを用いることで描画率が飛躍的に向上していることがわかる。角速度が毎秒50度以上という激しい回転下でも、Sbackupは70〜80%以上と高い描画率を誇っている。一方、角速度が10〜20[度/秒]を見ると、バックアップを用いた場合のSnormalは、バックアップを用いない場合と比べて小さくなっている。これは、バックアップブロックの読み込みが行われるため、現解像度ブロックの読込みが多少遅れるのが原因と考えられる。しかし、そこから角速度が増すと、バックアップブロックを用いない場合のSnormalは非常に小さくなってしまう。これは、以下に示す原因によるものと考えられる。まず、描画されたブロックが少ないため1フレームを描画するために要する時間がとても小さくなる。この結果、［Ｂ−２−１］で述べたように、前もってブロックの読込みを行うとしても、読込みに利用される時間が短いため、実際に読込めるブロック数が少なくなるためであると推測される。
つぎに、α値を変化させたときの描画率Sbackupを図１３に、そのときのバックアップブロックの階層と、現解像度ブロックの階層との差を図１４に示す。図１４から、角速度の上昇に伴う読込みブロックの増加に対して、提案手法がバックアップブロックの解像度を上げることで対処していることがわかる。また、図１３を見ると、αの値が小さくなるにつれて描画率Sbackupの値が改善されているが、それはより低い解像度のブロックをバックアップブロックに用いているからと考えられる。一方、より低解像度なブロックをバックアップに用いることで、現解像度ブロックで描画されたブロックとの画質の差が拡大してしまうという問題もある。したがって、画質と描画率とのトレードオフを解消するようにブロック読込みパラメータαの最適値を決定することが望ましい。
以上述べてきたように、本発明の実施形態では、PC環境下で大規模なボリュームデータの実時間表示を実現する方法及びシステムを構築した。具体的にはスクリーンの解像度を考慮した探索判定法、マルチコアCPUを利用するマルチスレッド化、そして実行環境を考慮したブロック解像度制御について提案した。
大規模ボリュームデータを多重解像度のブロックに分割し、octree表現を用いてデータの管理を実現した。まず、スクリーンの解像度を考慮した探索判定法では、octreeをトラバースする際の探索判定計算に、スクリーンの1ピクセルの大きさと、投影された1ボクセルの大きさの比を用いた。この結果、エイリアスの発生を防ぐとともに、使用者が得たい描画解像度を探索判定計算に直接反映させることを可能にした。
マルチコアCPUを利用するマルチスレッド化では読込みスレッドと描画スレッドの2つのスレッドを作成し、それぞれ1つのコアを独占して処理することで完全な並列計算を実現する。前者はブロックをハードディスクから主メモリに読込むスレッドであり、後者は主メモリに読込まれたブロックをテクスチャメモリに読込み描画するスレッドである。この結果としてフレームレートの大幅な改善を図れた。また、バックアップとして、現解像度ブロックより低解像度なブロックを用いることで、描画の欠けを埋める手法も考案した。
実行環境を考慮したブロック解像度制御では、プログラム実行時に得られる、記憶領域の容量や転送率等のデータをもとに、通常の描画に用いられる現解像度ブロック、ならびに現解像度ブロックの読込みが間に合わないときに代わりに用いられるバックアップブロックの解像度を変化させ、主メモリやテクスチャメモリへのブロック読込みの適切な制御を実現した。
本発明は、膨大な数値情報の実時間ボリュームレンダリングに利用することができる。
視錐台を示す図である。 視錐台カリングを示す図である。 octree構造を用いたＬＯＤ制御を示す図である。 角度の比を用いた探索判定を示す図である。 スクリーンの解像度を考慮した探索判定法を示す図である。 マルチスレッド化による処理の流れを示す図である。 ブロックの先読み要求を説明摺る図である。 欠けた描画結果を示す図である。 要求の状況を表すビッド列を示す図である。 視錐台の分割を示す図である。 実行結果を示す図である。 角速度を変化させた場合の描画率を示す図である。 α値を変化させた場合の描画率を示す図である。 α値を変化させたバックアップブロックの解像度を示す図である。

Claims (36)

  1. 外部記憶装置に格納されているボリュームデータを分割してなるブロックを、主メモリを経由してテクスチャメモリに転送して描画するボリュームデータの実時間レンダリング方法であって、
    階層毎に異なる解像度を備えたツリー状の階層構造を用いたLOD制御によって各ブロックの第１の解像度を決定し、
    第１の解像度のブロックが主メモリに存在しない場合に、当該第１の解像度よりも低い第２の解像度のブロックを当該第１の解像度のブロックに対応するバックアップブロックとして定義し、
    各フレームにおいて、次フレームの描画において必要となる第１の解像度のブロックで主メモリ上に存在しないブロックを外部記憶装置から主メモリに先行読み込み要求すると共に、要求された第１の解像度のブロックに対応するバックアップブロックを当該第１の解像度のブロックに優先させて外部記憶装置から主メモリに読み込むことで、描画に先行してバックアップブロック、あるいは、バックアップブロック及び第１の解像度のブロックを主メモリに読み込み、
    各フレームにおいて描画の欠けが生じないように、現フレームの描画に必要となる第１の解像度のブロックないしバックアップブロックを主メモリからテクスチャメモリに読み込んで描画する、
    ボリュームデータの実時間レンダリング方法。
  2. 前記第２の解像度は、１フレームにおいて外部記憶装置から主メモリに読み込むことができるブロックの最大数Ｍｍａｘ＿ｐｅｒ＿ｆｒａｍｅを越えないように決定される、請求項１に記載のボリュームデータの実時間レンダリング方法。
  3. 前記第２の解像度の決定は、
    前記第１の解像度より１段階低い解像度のバックアップブロックを用意し、
    フレーム毎に、主メモリに読み込むバックアップブロック数ＢＭ＿ｌｏａｄと１フレームあたりに主メモリに読み込めるブロックの最大数Ｍｍａｘ＿ｐｅｒ＿ｆｒａｍｅが以下の関係（０≦α≦１）を満たすかを判定し、
    式を満たさない場合には、１段階低減した前記解像度をさらに１段階低解像度にして判定を繰り返し、式を満たした時の解像度を前記第２の解像度とする、
    請求項２に記載のボリュームデータの実時間レンダリング方法。
  4. 前記ブロックの最大数Ｍmax_per_frameは、１ブロックあたりのハードディスク-主メモリ間の読込みに掛かる時間の平均値tM、１フレームを描画するのに要する時間の平均値tRから
    で取得する、請求項２、３いずれかに記載のボリュームデータの実時間レンダリング方法。
  5. 外部記憶装置から主メモリへのブロックの読み込みの優先度は、
    第１の解像度のブロックよりも第２の解像度のバックアップブロックの優先度が高いことに加えて、
    視点からより近い領域内に存在するブロックほど、および／あるいは、スクリーン中心に近いブロックほど優先度が高い、
    請求項１乃至４いずれかに記載のボリュームデータの実時間レンダリング方法。
  6. 主メモリからテクスチャメモリへのブロックの読み込みの優先度は、第２の解像度のバックアップブロックよりも第１の解像度のブロックを優先して読み込む、請求項１乃至５いずれかに記載のボリュームデータの実時間レンダリング方法。
  7. 主メモリからテクスチャメモリへのブロックの読み込みの優先度は、テクスチャメモリの容量に余裕がある場合には第２の解像度のバックアップブロックよりも第１の解像度のブロックを優先して読み込み、テクスチャメモリの容量に余裕がない場合には第１の解像度のブロックよりも第２の解像度のバックアップブロックを優先して読み込む、
    請求項１乃至５いずれかに記載のボリュームデータの実時間レンダリング方法。
  8. １フレーム毎に、主メモリからテクスチャメモリへ読み込む第１の解像度のブロックの数ＮＴ＿ｌｏａｄおよびバックアップブロックの数ＢＴ＿ｌｏａｄの合計と、１フレーム間に主メモリからテクスチャメモリに読み込むことができるブロックの最大数Ｔｍａｘ＿ｐｅｒ＿ｆｒａｍｅとを比較して以下の関係を満たすか判定し、
    式を満たす場合には、要求されたブロックをそのまま主メモリからテクスチャメモリへ読み込み、
    式を満たさない場合には、第２の解像度のバックアップブロックを優先して主メモリからテクスチャメモリへ読み込む、
    請求項１乃至７いずれかに記載のボリュームデータの実時間レンダリング方法。
  9. 前記ブロックの最大数Ｔｍａｘ＿ｐｅｒ＿ｆｒａｍｅは、１フレームを描画するのに要する時間の平均値ｔＲ、1ブロックあたりの主メモリからテクスチャメモリへの読込みに掛かる時間の平均値ｔＴ、使用者が設定した1フレームの描画に費やすことができる最大時間ｔｍａｘ、前フレーム描画時にテクスチャメモリに読込まれた現解像度ブロック数ＮＴ＿ｌｏａｄ＿ｐｒｅｖ、前フレーム描画時にテクスチャメモリに読込まれたバックアップブロック数ＢＴ＿ｌｏａｄ＿ｐｒｅｖから、
    で取得する、請求項８に記載のボリュームデータの実時間レンダリング方法。
  10. 前記次フレームの描画において必要となる第１の解像度のブロックで主メモリ上に存在しないブロックの読み込み要求は、
    視錐台カリング用の描画用視錐台に加えて、読み込み要求を発行するための読み込み用視錐台を定義し、前記描画用視錐台と前記読み込み用視錐台は同形であり、
    フレーム間での描画用視錐台の位置の変化から、次フレームでの描画用視錐台の位置を予測して、予測位置に読み込み用視錐台を配置するステップと、
    読み込み用視錐台内にあり、かつ主メモリに存在しないブロックに対して読み込み要求を発行するステップ、
    からなる請求項１乃至９いずれかに記載のボリュームデータの実時間レンダリング方法。
  11. 現フレームにおいて描画するステップは、
    現フレームの描画に必要な第１の解像度のブロックがテクスチャメモリに存在するか判定し、存在する場合にはテクスチャメモリに存在する第１の解像度のブロックを描画し、
    第１の解像度のブロックがテクスチャメモリに存在しない場合に、当該第１の解像度のブロックが主メモリに存在するか判定し、存在する場合には第１の解像度のブロックあるいはバックアップブロックを主メモリからテクスチャメモリに読み込んで描画する、
    請求項１乃至１０いずれかに記載のボリュームデータの実時間レンダリング方法。
  12. 前記第１の解像度の決定は、
    スクリーン上に投影されたボクセルの大きさが１ピクセルよりも小さくなる直前の解像度を最適解像度と定義し、
    フレーム毎に最適解像度ブロックの数とテクスチャメモリに読み込むことができるブロックの最大数とを比較し、最適解像度ブロックの数が最大数以下となるまで最適解像度ブロックの解像度を低減させた時の解像度を第１の解像度とする、請求項１乃至１１いずれかに記載のボリュームデータの実時間レンダリング方法。
  13. 前記第１の解像度の決定は、
    フレーム毎に最適解像度ブロックの数を取得するステップと、
    最適解像度ブロックの数とテクスチャメモリに読み込むことができるブロックの最大数とを比較するステップと、
    最適解像度ブロック数が最大ブロック数を越える場合には、最適解像度ブロックの解像度を１段階低解像度に更新するステップと、を備え、
    前記比較ステップと前記更新ステップを、最適解像度ブロックの数が最大ブロック数以下になるまで繰り返した時の解像度を第１の解像度とする、請求項１２に記載のボリュームデータの実時間レンダリング方法。
  14. 前記最適解像度の決定は、
    ツリー状の階層構造の中で低い解像度を備えたブロックにおいて、視点から最も離れているブロックの中で、その中でも最も離れているボクセルを透視投影しスクリーン上の大きさを計算し、
    スクリーン上での大きさが下記式を満たすか否かを判定し、満たす場合には一段階高解像度のノードを探索し、この判定を繰り返して最適解像度を決定する、
    請求項１２、１３いずれかに記載のボリュームデータの実時間レンダリング方法。
  15. 前記LOD制御による各ブロックの第１解像度の決定は、視点から各ブロックまでの距離及びテクスチャメモリの容量に基づいて行なわれる、請求項１乃至１４いずれかに記載のボリュームデータの実時間レンダリング方法。
  16. 前記ツリー状の階層構造は、ｏｃｔｒｅｅである、請求項１乃至１５いずれかに記載のボリュームデータの実時間レンダリング方法。
  17. 前記ツリー状の階層構造は、ウェーブレット木である、請求項１乃至１５いずれかに記載のボリュームデータの実時間レンダリング方法。
  18. 外部記憶装置と、主メモリと、テクスチャメモリと、プロセッサと、ディスプレイとを備えたコンピュータからなり、外部記憶装置に格納されているボリュームデータを分割してなるブロックを、主メモリを経由してテクスチャメモリに転送してディスプレイ上に描画するボリュームデータの実時間レンダリング装置であって、
    前記プロセッサは、
    階層毎に異なる解像度を備えたツリー状の階層構造を用いたLOD制御によって各ブロックの第１の解像度を決定し、
    第１の解像度のブロックが主メモリに存在しない場合に、当該第１の解像度よりも低い第２の解像度のブロックを当該第１の解像度のブロックに対応するバックアップブロックとして定義し、
    各フレームにおいて、次フレームの描画において必要となる第１の解像度のブロックで主メモリ上に存在しないブロックを外部記憶装置から主メモリに先行読み込み要求すると共に、要求された第１の解像度のブロックに対応するバックアップブロックを当該第１の解像度のブロックに優先させて外部記憶装置から主メモリに読み込むことで、描画に先行してバックアップブロック、あるいは、バックアップブロック及び第１の解像度のブロックを主メモリに読み込み、
    各フレームにおいて描画の欠けが生じないように、現フレームの描画に必要となる第１の解像度のブロックないしバックアップブロックを主メモリからテクスチャメモリに読み込んで描画する、
    ボリュームデータの実時間レンダリング装置。
  19. 前記第２の解像度は、１フレームにおいて外部記憶装置から主メモリに読み込むことができるブロックの最大数Ｍｍａｘ＿ｐｅｒ＿ｆｒａｍｅを越えないように決定される、請求項１８に記載のボリュームデータの実時間レンダリング装置。
  20. 前記第２の解像度の決定は、
    前記第１の解像度より１段階低い解像度のバックアップブロックを用意し、
    フレーム毎に、主メモリに読み込むバックアップブロック数ＢＭ＿ｌｏａｄと１フレームあたりに主メモリに読み込めるブロックの最大数Ｍｍａｘ＿ｐｅｒ＿ｆｒａｍｅが以下の関係（０≦α≦１）を満たすかを判定し、
    式を満たさない場合には、１段階低減した前記解像度をさらに１段階低解像度にして判定を繰り返し、式を満たした時の解像度を前記第２の解像度とする、
    請求項１９に記載のボリュームデータの実時間レンダリング装置。
  21. 前記ブロックの最大数Ｍmax_per_frameは、１ブロックあたりのハードディスク-主メモリ間の読込みに掛かる時間の平均値tM、１フレームを描画するのに要する時間の平均値tRから
    で取得する、請求項１９、２０いずれかに記載のボリュームデータの実時間レンダリング装置。
  22. 外部記憶装置から主メモリへのブロックの読み込みの優先度は、
    第１の解像度のブロックよりも第２の解像度のバックアップブロックの優先度が高いことに加えて、
    視点からより近い領域内に存在するブロックほど、および／あるいは、スクリーン中心に近いブロックほど優先度が高い、
    請求項１８乃至２１いずれかに記載のボリュームデータの実時間レンダリング装置。
  23. 主メモリからテクスチャメモリへのブロックの読み込みの優先度は、第２の解像度のバックアップブロックよりも第１の解像度のブロックを優先して読み込む、請求項１８乃至２２いずれかに記載のボリュームデータの実時間レンダリング装置。
  24. 主メモリからテクスチャメモリへのブロックの読み込みの優先度は、テクスチャメモリの容量に余裕がある場合には第２の解像度のバックアップブロックよりも第１の解像度のブロックを優先して読み込み、テクスチャメモリの容量に余裕がない場合には第１の解像度のブロックよりも第２の解像度のバックアップブロックを優先して読み込む、
    請求項１８乃至２２いずれかに記載のボリュームデータの実時間レンダリング装置。
  25. １フレーム毎に、主メモリからテクスチャメモリへ読み込む第１の解像度のブロックの数ＮＴ＿ｌｏａｄおよびバックアップブロックの数ＢＴ＿ｌｏａｄの合計と、１フレーム間に主メモリからテクスチャメモリに読み込むことができるブロックの最大数Ｔｍａｘ＿ｐｅｒ＿ｆｒａｍｅとを比較して以下の関係を満たすか判定し、
    式を満たす場合には、要求されたブロックをそのまま主メモリからテクスチャメモリへ読み込み、
    式を満たさない場合には、第２の解像度のバックアップブロックを優先して主メモリからテクスチャメモリへ読み込む、
    請求項１８乃至２４いずれかに記載のボリュームデータの実時間レンダリング装置。
  26. 前記ブロックの最大数Ｔｍａｘ＿ｐｅｒ＿ｆｒａｍｅは、１フレームを描画するのに要する時間の平均値ｔＲ、1ブロックあたりの主メモリからテクスチャメモリへの読込みに掛かる時間の平均値ｔＴ、使用者が設定した1フレームの描画に費やすことができる最大時間ｔｍａｘ、前フレーム描画時にテクスチャメモリに読込まれた現解像度ブロック数ＮＴ＿ｌｏａｄ＿ｐｒｅｖ、前フレーム描画時にテクスチャメモリに読込まれたバックアップブロック数ＢＴ＿ｌｏａｄ＿ｐｒｅｖから、
    で取得する、請求項２５に記載のボリュームデータの実時間レンダリング装置。
  27. 前記次フレームの描画において必要となる第１の解像度のブロックで主メモリ上に存在しないブロックの読み込み要求は、
    視錐台カリング用の描画用視錐台に加えて、読み込み要求を発行するための読み込み用視錐台を定義し、前記描画用視錐台と前記読み込み用視錐台は同形であり、
    フレーム間での描画用視錐台の位置の変化から、次フレームでの描画用視錐台の位置を予測して、予測位置に読み込み用視錐台を配置し、
    読み込み用視錐台内にあり、かつ主メモリに存在しないブロックに対して読み込み要求を発行する、
    請求項１８乃至２６いずれかに記載のボリュームデータの実時間レンダリング装置。
  28. 前記プロセッサは、
    現フレームの描画に必要な第１の解像度のブロックがテクスチャメモリに存在するか判定し、存在する場合にはテクスチャメモリに存在する第１の解像度のブロックを描画し、
    第１の解像度のブロックがテクスチャメモリに存在しない場合に、当該第１の解像度のブロックが主メモリに存在するか判定し、存在する場合には第１の解像度のブロックあるいはバックアップブロックを主メモリからテクスチャメモリに読み込んで描画する、
    請求項１８乃至２７いずれかに記載のボリュームデータの実時間レンダリング装置。
  29. 前記第１の解像度の決定は、
    スクリーン上に投影されたボクセルの大きさが１ピクセルよりも小さくなる直前の解像度を最適解像度と定義し、
    フレーム毎に最適解像度ブロックの数とテクスチャメモリに読み込むことができるブロックの最大数とを比較し、最適解像度ブロックの数が最大数以下となるまで最適解像度ブロックの解像度を低減させた時の解像度を第１の解像度とする、請求項１８乃至２８いずれかに記載のボリュームデータの実時間レンダリング装置。
  30. 前記第１の解像度の決定は、
    フレーム毎に最適解像度ブロックの数を取得し、
    最適解像度ブロックの数とテクスチャメモリに読み込むことができるブロックの最大数とを比較し、
    最適解像度ブロック数が最大ブロック数を越える場合には、最適解像度ブロックの解像度を１段階低解像度に更新すること、を備え、
    前記比較と前記更新を、最適解像度ブロックの数が最大ブロック数以下になるまで繰り返した時の解像度を第１の解像度とする、請求項２９に記載のボリュームデータの実時間レンダリング装置。
  31. 前記最適解像度の決定は、
    ツリー状の階層構造の中で低い解像度を備えたブロックにおいて、視点から最も離れているブロックの中で、その中でも最も離れているボクセルを透視投影しスクリーン上の大きさを計算し、
    スクリーン上での大きさが下記式を満たすか否かを判定し、満たす場合には一段階高解像度のノードを探索し、この判定を繰り返して最適解像度を決定する、
    請求項２９、３０いずれかに記載のボリュームデータの実時間レンダリング装置。
  32. 前記LOD制御による各ブロックの第１解像度の決定は、視点から各ブロックまでの距離及びテクスチャメモリの容量に基づいて行なわれる、請求項１８乃至３１いずれかに記載のボリュームデータの実時間レンダリング装置。
  33. 前記ツリー状の階層構造は、ｏｃｔｒｅｅである、請求項１８乃至３２いずれかに記載のボリュームデータの実時間レンダリング装置。
  34. 前記ツリー状の階層構造は、ウェーブレット木である、請求項１８乃至３２いずれかに記載のボリュームデータの実時間レンダリング装置。
  35. 請求項１８乃至３４いずれかに記載された装置のプロセッサを実行させるためのコンピュータプログラム。
  36. 請求項１８乃至３４いずれかに記載された装置のプロセッサを実行させるためのコンピュータプログラムを記録したコンピュータ可読媒体。
JP2009278407A 2008-12-20 2009-12-08 ボリュームデータの実時間レンダリング方法及び装置 Expired - Fee Related JP5419044B2 (ja)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP2009278407A JP5419044B2 (ja) 2008-12-20 2009-12-08 ボリュームデータの実時間レンダリング方法及び装置

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
JP2008324804 2008-12-20
JP2008324804 2008-12-20
JP2009278407A JP5419044B2 (ja) 2008-12-20 2009-12-08 ボリュームデータの実時間レンダリング方法及び装置

Publications (2)

Publication Number Publication Date
JP2010165344A true JP2010165344A (ja) 2010-07-29
JP5419044B2 JP5419044B2 (ja) 2014-02-19

Family

ID=42581415

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2009278407A Expired - Fee Related JP5419044B2 (ja) 2008-12-20 2009-12-08 ボリュームデータの実時間レンダリング方法及び装置

Country Status (1)

Country Link
JP (1) JP5419044B2 (ja)

Cited By (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20110074775A (ko) * 2008-10-21 2011-07-01 코닌클리케 필립스 일렉트로닉스 엔.브이. 장면의 층상 깊이 모델을 제공하기 위한 방법 및 디바이스
JP2014035722A (ja) * 2012-08-10 2014-02-24 Omron Corp データ表示装置、方法、プログラム
JP2017516209A (ja) * 2014-04-21 2017-06-15 クアルコム，インコーポレイテッド レイトレーシングアプリケーションにおけるツリー横断のための開始ノード決定
WO2018173207A1 (ja) * 2017-03-23 2018-09-27 株式会社ソニー・インタラクティブエンタテインメント 情報処理装置
US10140677B2 (en) 2014-11-27 2018-11-27 Samsung Electronics Co., Ltd. Graphics processing unit and device employing tessellation decision
JP2020015314A (ja) * 2018-07-27 2020-01-30 株式会社ソニー・インタラクティブエンタテインメント 塗りつぶしの並列方法および装置
JP2021002402A (ja) * 2020-10-06 2021-01-07 株式会社ソニー・インタラクティブエンタテインメント 情報処理装置
CN116166257A (zh) * 2021-11-25 2023-05-26 华为技术有限公司 界面生成方法及电子设备

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2002520748A (ja) * 1998-07-16 2002-07-09 ザ リサーチ ファウンデーション オブ ステイト ユニヴァーシティ オブ ニューヨーク リアルタイム・ボリューム処理およびユニバーサル３ｄレンダリングのための装置および方法
JP2003505957A (ja) * 1999-07-20 2003-02-12 テレメディア システムズ リミテッド デジタルデータ記憶の方法及び装置
JP2003512685A (ja) * 1999-10-18 2003-04-02 フラウンホーファー−ゲゼルシャフト ツール フエルデルング デア アンゲヴァンテン フォルシュング エー．ファオ． 大ボリュームデータ量の実時間レンダリング方法

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2002520748A (ja) * 1998-07-16 2002-07-09 ザ リサーチ ファウンデーション オブ ステイト ユニヴァーシティ オブ ニューヨーク リアルタイム・ボリューム処理およびユニバーサル３ｄレンダリングのための装置および方法
JP2003505957A (ja) * 1999-07-20 2003-02-12 テレメディア システムズ リミテッド デジタルデータ記憶の方法及び装置
JP2003512685A (ja) * 1999-10-18 2003-04-02 フラウンホーファー−ゲゼルシャフト ツール フエルデルング デア アンゲヴァンテン フォルシュング エー．ファオ． 大ボリュームデータ量の実時間レンダリング方法

Cited By (15)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101689343B1 (ko) 2008-10-21 2016-12-23 코닌클리케 필립스 엔.브이. 장면의 계층화 깊이 모델을 제공하기 위한 방법 및 디바이스
KR20110074775A (ko) * 2008-10-21 2011-07-01 코닌클리케 필립스 일렉트로닉스 엔.브이. 장면의 층상 깊이 모델을 제공하기 위한 방법 및 디바이스
JP2014035722A (ja) * 2012-08-10 2014-02-24 Omron Corp データ表示装置、方法、プログラム
JP2017516209A (ja) * 2014-04-21 2017-06-15 クアルコム，インコーポレイテッド レイトレーシングアプリケーションにおけるツリー横断のための開始ノード決定
US10140677B2 (en) 2014-11-27 2018-11-27 Samsung Electronics Co., Ltd. Graphics processing unit and device employing tessellation decision
JPWO2018173207A1 (ja) * 2017-03-23 2019-11-07 株式会社ソニー・インタラクティブエンタテインメント 情報処理装置
WO2018173207A1 (ja) * 2017-03-23 2018-09-27 株式会社ソニー・インタラクティブエンタテインメント 情報処理装置
CN110431601A (zh) * 2017-03-23 2019-11-08 索尼互动娱乐股份有限公司 信息处理装置
EP3605469A4 (en) * 2017-03-23 2021-03-03 Sony Interactive Entertainment Inc. INFORMATION PROCESSING DEVICE
US11107276B2 (en) 2017-03-23 2021-08-31 Sony Interactive Entertainment Inc. Scaling voxels in a virtual space
JP2020015314A (ja) * 2018-07-27 2020-01-30 株式会社ソニー・インタラクティブエンタテインメント 塗りつぶしの並列方法および装置
JP7308088B2 (ja) 2018-07-27 2023-07-13 株式会社ソニー・インタラクティブエンタテインメント 塗りつぶしの並列方法および装置
JP2021002402A (ja) * 2020-10-06 2021-01-07 株式会社ソニー・インタラクティブエンタテインメント 情報処理装置
JP7044846B2 (ja) 2020-10-06 2022-03-30 株式会社ソニー・インタラクティブエンタテインメント 情報処理装置
CN116166257A (zh) * 2021-11-25 2023-05-26 华为技术有限公司 界面生成方法及电子设备

Also Published As

Publication number Publication date
JP5419044B2 (ja) 2014-02-19

Similar Documents

Publication Publication Date Title
JP5419044B2 (ja) ボリュームデータの実時間レンダリング方法及び装置
US11954759B2 (en) Tile-based graphics
KR101800987B1 (ko) 계층적 z-컬링을 수행하기 위한 부분적으로-커버된 타일들의 선택적 병합
US8704826B1 (en) Primitive re-ordering between world-space and screen-space pipelines with buffer limited processing
Corrêa et al. Visibility-based prefetching for interactive out-of-core rendering
Hadwiger et al. Interactive volume exploration of petascale microscopy data streams using a visualization-driven virtual memory approach
Hadwiger et al. SparseLeap: Efficient empty space skipping for large-scale volume rendering
US9779533B2 (en) Hierarchical tiled caching
US10055883B2 (en) Frustum tests for sub-pixel shadows
US20140049549A1 (en) Efficient placement of texture barrier instructions
US20190206018A1 (en) Multi-gpu frame rendering
Corrêa et al. iWalk: Interactive out-of-core rendering of large models
US9401046B2 (en) Micropolygon splatting
US11532066B2 (en) Reduced bandwidth tessellation factors
Leven et al. Interactive visualization of unstructured grids using hierarchical 3D textures
Johnson et al. The irregular z-buffer and its application to shadow mapping
US20170330304A1 (en) Graphics processing unit and method of controlling cache bypass thereof
US12346255B2 (en) Providing counters in a data processor
US20240169464A1 (en) Graphics processing systems
US20240169465A1 (en) Graphics processing systems
CN119068099A (zh) 一种光线堆栈管理器、图形处理方法及系统
Bennett Massive model visualization: An investigation into spatial partitioning
Paulin GigaVoxels: A voxel-based rendering pipeline for efficient exploration of large and detailed scenes

Legal Events

Date Code Title Description
A621 Written request for application examination

Free format text: JAPANESE INTERMEDIATE CODE: A621

Effective date: 20121205

A977 Report on retrieval

Free format text: JAPANESE INTERMEDIATE CODE: A971007

Effective date: 20131007

A01 Written decision to grant a patent or to grant a registration (utility model)

Free format text: JAPANESE INTERMEDIATE CODE: A01

Effective date: 20131024

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20131112

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

LAPS Cancellation because of no payment of annual fees