【誤訳訂正書】
【提出日】平成24年6月6日(2012.6.6)
【誤訳訂正１】
【訂正対象書類名】特許請求の範囲
【訂正対象項目名】全文
【訂正方法】変更
【訂正の内容】
【特許請求の範囲】
【請求項１】
ローカルグリッドで量子化された場合に隣接する三角形の間に発生する間隙が除去されるように、シーンの三角形を、境界ボリューム階層（ＢＶＨ）のすべてのリーフノードを整列可能であるグローバルグリッド上で量子化する段階と、
可変長のビット列として前記三角形の頂点位置をエンコードする段階と、
エンコードされた前記三角形の頂点位置により前記三角形の接続をモデリングする段階と、
モデリングされた前記三角形の少なくとも一部を表すＢＶＨを構築する段階と
を備え、
グラフィックス処理を実行するプロセッサによって実行され、
前記頂点位置をエンコードする段階は、
各頂点ｉについて、前記頂点を含む境界ボックスの原点からの距離を記述するデルタベクトルＤｉ＝｛ｘｉ，ｙｉ，ｚｉ｝を計算する段階と、
前記境界ボックス内の全ての前記頂点について、前記頂点それぞれの前記デルタベクトルのうち、最大のｘ、ｙおよびｚコンポーネント、ｍａｘ（ｘｉ）、ｍａｘ（ｙｉ）およびｍａｘ（ｚｉ）を決定する段階と、
前記ｍａｘ（ｘｉ）、ｍａｘ（ｙｉ）およびｍａｘ（ｚｉ）をそれぞれエンコードするのに必要なビット数（ｎｘ，ｎｙ，ｎｚ）を決定する段階と、
前記ビット数（ｎｘ，ｎｙ，ｎｚ）をエンコードする段階と
を有し、前記エンコードされた（ｎｘ，ｎｙ，ｎｚ）に前記頂点の前記デルタベクトルが続く方法。
【請求項２】
前記頂点位置をエンコードする段階は、
各頂点ｉについて、前記頂点を含む境界ボックスの原点からの距離を記述するデルタベクトルＤｉ＝｛ｘｉ，ｙｉ，ｚｉ｝を計算する段階と、
前記境界ボックス内の全ての前記頂点について、前記頂点それぞれの前記デルタベクトルのうち、最大のｘ、ｙおよびｚコンポーネント、ｍａｘ（ｘｉ）、ｍａｘ（ｙｉ）およびｍａｘ（ｚｉ）を決定する段階と、
前記ｍａｘ（ｘｉ）、ｍａｘ（ｙｉ）およびｍａｘ（ｚｉ）をそれぞれエンコードするに必要なビット数（ｎｘ，ｎｙ，ｎｚ）を決定する段階と、
前記ビット数（ｎｘ，ｎｙ，ｎｚ）をエンコードする段階と、
ｘｉ、ｙｉおよびｚｉのそれぞれに前記境界ボックスの最近傍の平面を識別する追加の１ビットを加える段階と
を有し、
前記Ｄｉの各コンポーネントは、前記頂点を含む前記最近傍の平面から前記頂点までの距離を前記コンポーネントの軸と共に示し、前記最近傍の平面は、前記軸に垂直であり、原点を含む平面または前記原点を含む前記平面に対向する平面のいずれかであり、前記エンコードされた（ｎｘ，ｎｙ，ｎｚ）に前記頂点の前記デルタベクトルが続く請求項１に記載の方法。
【請求項３】
前記接続をモデリングする段階は、前記三角形それぞれの各頂点を識別する段階を有し、前記三角形の１つの頂点が複数の三角形の頂点である場合は、前記頂点は前記複数の三角形のそれぞれについて個別に識別される請求項１または２に記載の方法。
【請求項４】
前記接続をモデリングする段階は、
各頂点を１回識別する段階と、
インデックスをそれぞれ頂点に関連付ける段階と、
前記三角形の３つの頂点のそれぞれに関連付けられた３つのインデックスをリストすることで前記三角形をそれぞれに識別する段階と
を有する請求項１から３のいずれか１項に記載の方法。
【請求項５】
前記接続をモデリングする段階は、
前記ＢＶＨ内のリーフ毎の三角形の最大数を指定する段階と、
ルックアップテーブル（ＬＵＴ）を構築する段階と、
前記ＬＵＴの各エントリについて、前記三角形の数および前記三角形それぞれの第１の頂点のオフセットを格納する段階と、
前記三角形それぞれの方向を格納する段階と
を有し、前記ＬＵＴの各エントリはストリップ群に関連付けられ、前記ストリップのそれぞれは、１個以上の隣接する三角形のシーケンスを含み、１個の三角形は前記ＬＵＴに１回のみ現れる請求項１から４のいずれか１項に記載の方法。
【請求項６】
前記ＢＶＨを構築する段階は、
各子ノードについて、関連付けられた親ノードの境界ボリュームを基準にして指定された境界ボリュームを定義する段階と、
複数の子ノードをブロックにグループ化する段階と、
前記ブロックのそれぞれについて、前記ブロック内の各子ノードのインデックスを定義する段階と、
リーフを含むブロックそれぞれについて、前記ブロックに関連付けられたリーフデータを前記ブロックの後にリストする段階と、
下部ノードを圧縮形式で格納し、上部ノードの少なくとも一部を非圧縮形式で格納する段階と
を有する請求項１から５のいずれか１項に記載の方法。
【請求項７】
前記ブロック内の子ノードは、フォワーディングノードが前記子ノードの従属サブツリーを指すように前記フォワーディングノードにマッピングされ、前記サブツリーは、異なるブロックに存在する請求項６に記載の方法。
【請求項８】
プロセッサと、
前記プロセッサと通信するメモリとを備えるシステムであって、
前記メモリは複数の処理命令を格納し、前記複数の処理命令は前記プロセッサに、
ローカルグリッドで量子化された場合に隣接する三角形の間に発生する間隙が除去されるようにシーンの複数の三角形を、境界ボリューム階層（ＢＶＨ）のすべてのリーフノードを整列可能であるグローバルグリッド上で量子化させ、
前記三角形の頂点位置を可変長のビット列としてエンコードさせ、
エンコードされた前記三角形の頂点位置により前記三角形の接続をモデリングさせ、
モデリングされた前記三角形の少なくとも一部を表すＢＶＨを構築させるための処理命令であり、
前記プロセッサに頂点位置をエンコードするように指示する前記命令は、前記プロセッサに
各頂点ｉについて、前記頂点を含む境界ボックスの原点からの距離であるデルタベクトルＤｉ＝｛ｘｉ，ｙｉ，ｚｉ｝を計算させ、
前記境界ボックスの全ての頂点について、前記頂点それぞれの前記デルタベクトルのうち、最大のｘ、ｙおよびｚコンポーネント、ｍａｘ（ｘｉ）、ｍａｘ（ｙｉ）およびｍａｘ（ｚｉ）を決定させ、
前記ｍａｘ（ｘｉ）、ｍａｘ（ｙｉ）およびｍａｘ（ｚｉ）をそれぞれエンコードするに必要なビット数（ｎｘ，ｎｙ，ｎｚ）を決定させ、
前記ビット数（ｎｘ，ｎｙ，ｎｚ）をエンコードさせるための命令を有し、
前記エンコードされた（ｎｘ，ｎｙ，ｎｚ）に前記頂点の前記デルタベクトルが続くシステム。
【請求項９】
前記プロセッサに頂点位置をエンコードするように指示する前記命令は、前記プロセッサに
各頂点ｉについて、前記頂点を含む境界ボックスの原点からの距離であるデルタベクトルＤｉ＝｛ｘｉ，ｙｉ，ｚｉ｝を計算させ、
前記境界ボックス内の全ての前記頂点について、前記頂点それぞれの前記デルタベクトルのうち、最大のｘ、ｙおよびｚコンポーネント、ｍａｘ（ｘｉ）、ｍａｘ（ｙｉ）およびｍａｘ（ｚｉ）を決定させ、
前記ｍａｘ（ｘｉ）、ｍａｘ（ｙｉ）およびｍａｘ（ｚｉ）をそれぞれエンコードするに必要なビット数（ｎｘ，ｎｙ，ｎｚ）を決定させ、
前記ビット数（ｎｘ，ｎｙ，ｎｚ）をエンコードさせ、
ｘｉ、ｙｉおよびｚｉに最近傍の平面を識別する追加の１ビットを加えさせるための命令を有し、
前記Ｄｉの各コンポーネントは、前記頂点を含む前記境界ボックスの前記最近傍の平面から前記頂点までの距離を前記コンポーネントの軸と共に示し、前記最近傍の平面は、前記軸に垂直であり、原点を含む平面または前記原点を含む前記平面に対向する平面のいずれかであり、前記エンコードされた（ｎｘ，ｎｙ，ｎｚ）に前記頂点の前記デルタベクトルが続く請求項８に記載のシステム。
【請求項１０】
前記プロセッサに接続をモデリングするように指示する前記命令は、前記プロセッサに
前記三角形それぞれの各頂点を識別させるための命令を有し、前記三角形の１つの頂点が複数の三角形の頂点である場合は、前記頂点は前記複数の三角形のそれぞれについて個別に識別される請求項８または９に記載のシステム。
【請求項１１】
前記プロセッサに接続をモデリングするように指示する前記命令は、前記プロセッサに
各頂点を１回識別させ、
インデックスをそれぞれ頂点に関連付けさせ、
前記三角形の３つの頂点のそれぞれに関連付けられた３つのインデックスをリストすることで前記三角形をそれぞれに識別させるための命令を有する請求項８から１０のいずれか１項に記載のシステム。
【請求項１２】
前記プロセッサに接続をモデリングするように指示する前記命令は、前記プロセッサに、
前記ＢＶＨ内のリーフ毎の三角形の最大数を指定させ、
ルックアップテーブル（ＬＵＴ）を構築させ、
各エントリについて、前記三角形の数および前記三角形それぞれの第１の頂点のオフセットを格納させ、
前記三角形それぞれの方向を格納させるための命令を有し、
前記ＬＵＴの各エントリはストリップ群に関連付けられ、前記ストリップのそれぞれは、１個以上の隣接する三角形のシーケンスを含み、１個の三角形は前記ＬＵＴに１回のみ現れる請求項８から１１のいずれか１項に記載のシステム。
【請求項１３】
前記プロセッサに前記ＢＶＨを構築するように指示する前記命令は、前記プロセッサに
各子ノードについて、関連付けられた親ノードの境界ボリュームを基準にして指定された境界ボリュームを定義させ、
複数の子ノードをブロックにグループ化させ、
前記ブロックのそれぞれについて、前記ブロック内の各子ノードのインデックスを定義させ、
リーフを含むブロックそれぞれについて、前記ブロックに関連付けられたリーフデータを前記ブロックの後にリストさせ、
下部ノードを圧縮形式で格納し、上部ノードの少なくとも一部を非圧縮形式で格納させるための命令を有する請求項８から１２のいずれか１項に記載のシステム。
【請求項１４】
前記ブロック内の子ノードは、フォワーディングノードが前記子ノードの従属サブツリーを指すように前記フォワーディングノードにマッピングされ、前記サブツリーは、異なるブロックに存在する請求項１３に記載のシステム。
【請求項１５】
コンピュータに、
境界ボリューム階層（ＢＶＨ）のすべてのリーフノードを整列可能であるグローバルグリッド上でシーンの複数の三角形を、ローカルグリッドで量子化された場合に隣接する複数の三角形の間に発生する間隙が除去されるように量子化させる手順と、
前記複数の三角形の頂点位置を可変長のビット列としてエンコードさせる手順と、
エンコードされた前記三角形の頂点位置により前記複数の三角形の接続をモデル化させる手順と、
モデリングされた前記三角形の少なくとも一部を表すＢＶＨを構築させる手順と
を実行させるためのプログラムであって
前記頂点位置をエンコードさせる前記手順は、
各頂点ｉについて、前記頂点を含む境界ボックスの原点からの距離を記述するデルタベクトルＤｉ＝｛ｘｉ，ｙｉ，ｚｉ｝を計算させる手順と、
前記境界ボックス内の全ての前記頂点について、前記頂点それぞれの前記デルタベクトルのうち、最大のｘ、ｙおよびｚコンポーネント、ｍａｘ（ｘｉ）、ｍａｘ（ｙｉ）およびｍａｘ（ｚｉ）を決定させる手順と、
前記ｍａｘ（ｘｉ）、ｍａｘ（ｙｉ）およびｍａｘ（ｚｉ）をそれぞれエンコードするに必要なビット数（ｎｘ，ｎｙ，ｎｚ）を決定させる手順と、
前記ビット数（ｎｘ，ｎｙ，ｎｚ）をエンコードさせる手順と
を有し、前記エンコードされた（ｎｘ，ｎｙ，ｎｚ）に前記頂点の前記デルタベクトルが続くプログラム。
【請求項１６】
前記頂点位置をエンコードさせる前記手順は、
各頂点ｉについて、前記頂点を含む境界ボックスの原点からの距離を記述するデルタベクトルＤｉ＝｛ｘｉ，ｙｉ，ｚｉ｝を計算させる手順と、
前記境界ボックス内の全ての前記頂点について、前記頂点それぞれの前記デルタベクトルのうち、最大のｘ、ｙおよびｚコンポーネント、ｍａｘ（ｘｉ）、ｍａｘ（ｙｉ）およびｍａｘ（ｚｉ）を決定させる手順と、
前記ｍａｘ（ｘｉ）、ｍａｘ（ｙｉ）およびｍａｘ（ｚｉ）をそれぞれエンコードするに必要なビット数（ｎｘ，ｎｙ，ｎｚ）を決定させる手順と、
前記（ｎｘ，ｎｙ，ｎｚ）をエンコードさせる手順と、
ｘｉ、ｙｉおよびｚｉに最近傍の平面を識別する追加の１ビットを加えさせる手順と
を有し、
前記Ｄｉの各コンポーネントは、前記頂点を含む前記境界ボックスの前記最近傍の平面から前記頂点までの距離を前記コンポーネントの軸と共に示し、前記最近傍の平面は、前記軸に垂直であり、前記原点を含む平面または前記原点を含む前記平面に対向する平面のいずれかであり、前記エンコードされた（ｎｘ，ｎｙ，ｎｚ）に前記頂点の前記デルタベクトルが続く請求項１５に記載のプログラム。
【請求項１７】
前記接続をモデリングさせる前記手順は、前記三角形それぞれの各頂点を識別させる手順を有し、前記三角形の１つの頂点が複数の三角形の頂点である場合は、前記頂点は前記複数の三角形のそれぞれについて個別に識別される請求項１５または１６に記載のプログラム。
【請求項１８】
前記接続をモデリングさせる前記手順は、
各頂点を１回識別させる手順と、
インデックスをそれぞれ頂点に関連付けさせる手順と、
前記三角形の３つの頂点のそれぞれに関連付けられた３つのインデックスをリストすることで前記三角形をそれぞれに識別させる手順と
を有する請求項１５から１７のいずれか１項に記載のプログラム。
【請求項１９】
前記接続をモデリングさせる手順は、
前記ＢＶＨ内のリーフ毎の三角形の最大数を指定させる手順と、
ルックアップテーブル（ＬＵＴ）を構築させる手順と、
各エントリについて、前記三角形の数および前記三角形それぞれの第１の頂点のオフセットを格納させる手順と、
前記三角形それぞれの方向を格納させる手順と
を有し、前記ＬＵＴの各エントリはストリップ群に関連付けられ、前記ストリップのそれぞれは、１個以上の隣接する三角形のシーケンスを含み、１個の三角形は前記ＬＵＴに１回のみ現れる請求項１５から１８のいずれか１項に記載のプログラム。
【請求項２０】
前記ＢＶＨを構築させる前記手順は、
各子ノードについて、関連付けられた親ノードの境界ボリュームを基準にして指定された境界ボリュームを定義させる手順と、
複数の子ノードをブロックにグループ化させる手順と、
前記ブロックのそれぞれについて、前記ブロック内の各子ノードのインデックスを定義させる手順と、
リーフを含むブロックそれぞれについて、前記ブロックに関連付けられたリーフデータを前記ブロックの後にリストさせる手順と、
下部ノードを圧縮形式で格納し、上部ノードの少なくとも一部を非圧縮形式で格納させる手順と
を有する請求項１５から１９のいずれか１項に記載のプログラム。
【請求項２１】
前記ブロック内の子ノードは、フォワーディングノードが前記子ノードの従属サブツリーを指すように前記フォワーディングノードにマッピングされ、前記サブツリーは、異なるブロックに存在する請求項２０に記載のプログラム。
【誤訳訂正２】
【訂正対象書類名】明細書
【訂正対象項目名】００１４
【訂正方法】変更
【訂正の内容】
【００１４】
図３に、ある実施形態に係る頂点のエンコーディングを示す。ステップ３１０では、各頂点についてデルタベクトル（Ｄｉ＝｛ｘｉ，ｙｉ，ｚｉ｝）が計算されてよい。このベクトルの各コンポーネントは、境界ボックスの原点から頂点までのその軸における距離を示す。ステップ３２０では、Ａｉの全ての頂点について、各軸の最大値が決定されてよい。これらの最大値をｍａｘ（ｘｉ）、ｍａｘ（ｙｉ）およびｍａｘ（ｚｉ）として示す。ステップ３３０では、これらの最大値のそれぞれをエンコーディングするために必要なビット数が決定されてよい。これにより、これらの最大値を表す３つの値（ｎｘ，ｎｙ，ｎｚ）が生じる。ステップ３４０では、これらの値（ｎｘ，ｎｙ，ｎｚ）がビット列で表され、Ａｉの頂点データがこれらに続いてよい。プロセスはステップ３５０で終了してよい。
【誤訳訂正３】
【訂正対象書類名】明細書
【訂正対象項目名】００１６
【訂正方法】変更
【訂正の内容】
【００１６】
したがって、ある実施形態では、デルタベクトルの各コンポーネントについて１ビットを追加してすることで、距離の計測が開始される最近傍の平面を識別してよい。これにより、頂点データの最終的なサイズ、つまりビット数を低減することができる。これは特に、大きな三角形を数多く有するモデルにおいて有効である。図４に示す二次元の例では、頂点Ｄを含む各頂点についてデルタベクトルが作成されてよい。ここではあらゆる頂点について、頂点から４０５で示された原点Ｏまでのｘ方向の距離を示すためにｘｍｉｎが用いられてよい。原点４０５からＤまでのｙ方向の距離を示すために可変のｙｍｉｎが用いられてよい。頂点Ｄにおいては、ｙ軸での最近傍の「平面」は上部境界４１０であり、ｘ軸での最近傍の「平面」は右端境界４２０である。従って、頂点Ｄは（ｘｍａｘＤ，ｙｍａｘＤ）としてエンコードされ、これらの座標はそれぞれ上部境界４１０および右端境界４２０からの距離を表す。その後、各座標に最近傍の境界を識別する１ビットが追加されてよい。追加のビットは、第１座標の場合、上部境界または下部境界のいずれかを意味し、第２座標の場合、右境界または左境界のいずれかを意味する。