JPH0769972B2 - 画像生成方法 - Google Patents
画像生成方法Info
- Publication number
- JPH0769972B2 JPH0769972B2 JP62176099A JP17609987A JPH0769972B2 JP H0769972 B2 JPH0769972 B2 JP H0769972B2 JP 62176099 A JP62176099 A JP 62176099A JP 17609987 A JP17609987 A JP 17609987A JP H0769972 B2 JPH0769972 B2 JP H0769972B2
- Authority
- JP
- Japan
- Prior art keywords
- ray
- intersection
- displayed
- cell
- rectangular parallelepiped
- 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.)
- Expired - Lifetime
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T15/00—Three-dimensional [3D] image rendering
- G06T15/06—Ray-tracing
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T15/00—Three-dimensional [3D] image rendering
- G06T15/10—Geometric effects
- G06T15/40—Hidden part removal
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S359/00—Optical: systems and elements
- Y10S359/90—Methods
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Computer Graphics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Geometry (AREA)
- Image Generation (AREA)
Description
【発明の詳細な説明】 A.産業上の利用分野 本発明は、光線追跡法を用した画像生成方法に関する。
B.従来技術 B.1.光線追跡法の概要 まず、例えばTurner Whitted著、“An Improved Illumi
nation Model for Shaded Display",Com.of the ACM、1
980年６月、第23巻第６号に記載された光線追跡法の概
要を説明する。光線追跡法では、第２図に示すように
（説明の便宜上、投影面と一致させた）スクリーン10上
の各画素（i,j）ごとに視点12から発せられる光線Ｌ
（視線）を考え、その光線Ｌと交差する物体表面を探索
する。光線Ｌの交差する物体14、16のうち視点から物体
表面までの距離の一番小さな物体14が最初に見える。
nation Model for Shaded Display",Com.of the ACM、1
980年６月、第23巻第６号に記載された光線追跡法の概
要を説明する。光線追跡法では、第２図に示すように
（説明の便宜上、投影面と一致させた）スクリーン10上
の各画素（i,j）ごとに視点12から発せられる光線Ｌ
（視線）を考え、その光線Ｌと交差する物体表面を探索
する。光線Ｌの交差する物体14、16のうち視点から物体
表面までの距離の一番小さな物体14が最初に見える。
いま、第３図に示すように、物体14の外表面のうちの光
線Ｌと物体14との交点18が存在する領域の光学的性質に
より、交点18を基点とする反射光線S1と屈折光線T1が存
在するとしよう。この場合、光線S1、T1のそれぞれにつ
いて、これらの光線と交差する物体表面が存在するか否
かを探索する。第３図の例では、光線S1は物体20と交点
22にて交わる。交点22を基点として反射光線S2と屈折光
線T2が存在すれば、これらについて交差する物体表面の
存否を探索する。一方、光線T1は交点24で物体14と再び
交わる。物体14の内表面のうちの交点24が存在する領域
の光学的性質により、交点24を基点とする反射光線が存
在し得ないか、あるいは考慮するに値しない場合は、屈
折光線T3についてだけ交差する物体表面の存否を探索す
る。このように、視線と表示対象の物体表面との交点が
１度見つかると、該交点を新たな基点として次々と光線
の追跡が行われる。なお、第２図において、N1、N2、N3
は、それぞれ交点18、22、24における法線ベクトルを示
している。
線Ｌと物体14との交点18が存在する領域の光学的性質に
より、交点18を基点とする反射光線S1と屈折光線T1が存
在するとしよう。この場合、光線S1、T1のそれぞれにつ
いて、これらの光線と交差する物体表面が存在するか否
かを探索する。第３図の例では、光線S1は物体20と交点
22にて交わる。交点22を基点として反射光線S2と屈折光
線T2が存在すれば、これらについて交差する物体表面の
存否を探索する。一方、光線T1は交点24で物体14と再び
交わる。物体14の内表面のうちの交点24が存在する領域
の光学的性質により、交点24を基点とする反射光線が存
在し得ないか、あるいは考慮するに値しない場合は、屈
折光線T3についてだけ交差する物体表面の存否を探索す
る。このように、視線と表示対象の物体表面との交点が
１度見つかると、該交点を新たな基点として次々と光線
の追跡が行われる。なお、第２図において、N1、N2、N3
は、それぞれ交点18、22、24における法線ベクトルを示
している。
ここで、上記のような光線の追跡をほとんど無限に近く
繰り返しても差し支えないわけだが、画像生成に要する
時間を考慮して、通常は光線の追跡を適当に打ち切るよ
うにしている。説明の便宜上、第２図の例において、光
線S2、T2、T3については表示対象の物体表面との交差の
有無の探索を行わないものとする。
繰り返しても差し支えないわけだが、画像生成に要する
時間を考慮して、通常は光線の追跡を適当に打ち切るよ
うにしている。説明の便宜上、第２図の例において、光
線S2、T2、T3については表示対象の物体表面との交差の
有無の探索を行わないものとする。
さて、交点18の色、輝度等は、交点18における物体14の
外表面の固有の色、反射係数、凹凸といった属性の他
に、当然、交点22における物体20の外表面の属性と交点
24における物体14の内表面の属性を反映したものにな
る。したがって、これらの交点における表示対象物体の
属性を考慮して、スクリーン10上の画素（i,j）（第１
図）に割り当てる色、輝度等の光学的情報を決定するこ
とにより、きわめてリアルな画像を生成することができ
る。
外表面の固有の色、反射係数、凹凸といった属性の他
に、当然、交点22における物体20の外表面の属性と交点
24における物体14の内表面の属性を反映したものにな
る。したがって、これらの交点における表示対象物体の
属性を考慮して、スクリーン10上の画素（i,j）（第１
図）に割り当てる色、輝度等の光学的情報を決定するこ
とにより、きわめてリアルな画像を生成することができ
る。
B.2.交点計算 光線と各物体表面との交点計算の方法は、対象とする物
体の形状によって代数的な方法と数値解析の方法に分け
られる。
体の形状によって代数的な方法と数値解析の方法に分け
られる。
ここで代数的な方法とは、解の公式により交点を方程式
の解として直接求める方法である。
の解として直接求める方法である。
また、数値解析による方法とは、第４図に示すように交
点の存在する領域をまず光線上Ｌの点をサンプリングす
ることにより調べる方法である。物体26の表面28を表わ
す等関数値曲面の式がＦ（X,Y,Z）＝Ｃで表されるとす
ると、サンプリングされた点ごとに｛Ｆ（X,Y,Z）−
Ｃ｝の符号のチェックを行ない、交点が存在する領域、
つまり上記符号が変化する領域（第４図の例では、サン
プリング点30、32の間）を発見する。つぎにその領域に
対して、２分法あるいはニュートン法を用いて交点を計
算する。表示対象の物体の表面が、５次以上の高次の関
数Ｆ（X,Y,Z）＝Ｃなる式によって表わされる場合、上
記サンプリングを交えた数値解析的な手法は必須であ
る。
点の存在する領域をまず光線上Ｌの点をサンプリングす
ることにより調べる方法である。物体26の表面28を表わ
す等関数値曲面の式がＦ（X,Y,Z）＝Ｃで表されるとす
ると、サンプリングされた点ごとに｛Ｆ（X,Y,Z）−
Ｃ｝の符号のチェックを行ない、交点が存在する領域、
つまり上記符号が変化する領域（第４図の例では、サン
プリング点30、32の間）を発見する。つぎにその領域に
対して、２分法あるいはニュートン法を用いて交点を計
算する。表示対象の物体の表面が、５次以上の高次の関
数Ｆ（X,Y,Z）＝Ｃなる式によって表わされる場合、上
記サンプリングを交えた数値解析的な手法は必須であ
る。
光線追跡法は、一般に高品質な画像を生成することが出
来るが、画素単位で各々の物体表面との交点を求めるた
めに計算量が膨大になる。このため、次のような高速化
の方法が、例えば藤本彰等著“Accelerated Ray−Traci
ng Systm"IEEECG＆Ａ、1986年４月号、または特開昭61
−139890号公報に開示されている。
来るが、画素単位で各々の物体表面との交点を求めるた
めに計算量が膨大になる。このため、次のような高速化
の方法が、例えば藤本彰等著“Accelerated Ray−Traci
ng Systm"IEEECG＆Ａ、1986年４月号、または特開昭61
−139890号公報に開示されている。
（Ｉ）第５図に示すような格子空間33を考え、該格子空
間を分割することによって得られた直方体（セル）34の
中にどの物体が存在するかの情報を記憶手段の中にテー
ブル35の形で保持しておく。
間を分割することによって得られた直方体（セル）34の
中にどの物体が存在するかの情報を記憶手段の中にテー
ブル35の形で保持しておく。
（II）各光線に関してまず格子空間との交差の有無を判
定し、格子空間と交差する光線についてはどの直方体と
交差するかを判定し、最後に直方体に含まれる物体の表
面との交差判定を行なう。
定し、格子空間と交差する光線についてはどの直方体と
交差するかを判定し、最後に直方体に含まれる物体の表
面との交差判定を行なう。
第６図に示す例に即して説明すると、光線Ａは、物体が
存在する直方体（例えば物体36の存在する直方体38）と
交差するが、光線Ｂは物体が存在する直方体と交差しな
いので物体表面との交点計算を行なわなくてすむ。物体
を含まない直方体に対しては各物体表面との交点計算を
行なう必要がないため、交点計算の回転を減少させるこ
とが出来る。なお、第６図の中の40は投影面である。
存在する直方体（例えば物体36の存在する直方体38）と
交差するが、光線Ｂは物体が存在する直方体と交差しな
いので物体表面との交点計算を行なわなくてすむ。物体
を含まない直方体に対しては各物体表面との交点計算を
行なう必要がないため、交点計算の回転を減少させるこ
とが出来る。なお、第６図の中の40は投影面である。
ここで、第３図ないし第６図がそうであったように、説
明の都合で２次元的に表面した図面を用いて、本発明な
らびに従来技術の説明を進めることをことわっておく。
明の都合で２次元的に表面した図面を用いて、本発明な
らびに従来技術の説明を進めることをことわっておく。
B.3.光線と直方体の交差判定 光線と格子空間とが交差するかどうかは、直方体状の格
子空間の表面を形成している６平面との交点を求め、そ
の交点が格子空間に含まれるかどうかを調べる。格子空
間に含まれる交点がある場合、その中で視点に最も近い
交点より、最初に光線のはいる直方体が決まる。光線が
次にはいる直方体は、最初の直方体と光線の傾きから増
分計算のみで求めることが出来る。以下、第７図を用い
て説明する。光線の傾きをｖ、光線の切片をｓ、直線パ
ラメータをｔとすると光線の方程式は、vt＋ｓで表され
る。さらにＸ、Ｙ、Ｚグリッド間の光線に沿った距離を
dtx、dty、dtz、光線が次に横切るＸ、Ｙ、Ｚグリッド
上のｔパラメータをtx、ty、tzとする。説明の都合上、
２次元的に示した第７図に示すように、光線が次にはい
る直方体（ｉ′,j′,k′）は、現在の直方体（i,j,k）
に対して、現在のtx、ty、tzのうち最小の値を持つ軸ｌ
（ｌ＝x,y,z）を＋１増分（傾きが正なら＋１、負なら
−１）させればよい。いったん、次の直方体に移行する
とその軸のｔパラメータ、tl（ｌ＝x,y,z）にdtl（ｌ＝
x,y,z）を加算しておく。以下、同様の処理を行なうこ
とにより次々と直方体を横断していくことが出来る。
子空間の表面を形成している６平面との交点を求め、そ
の交点が格子空間に含まれるかどうかを調べる。格子空
間に含まれる交点がある場合、その中で視点に最も近い
交点より、最初に光線のはいる直方体が決まる。光線が
次にはいる直方体は、最初の直方体と光線の傾きから増
分計算のみで求めることが出来る。以下、第７図を用い
て説明する。光線の傾きをｖ、光線の切片をｓ、直線パ
ラメータをｔとすると光線の方程式は、vt＋ｓで表され
る。さらにＸ、Ｙ、Ｚグリッド間の光線に沿った距離を
dtx、dty、dtz、光線が次に横切るＸ、Ｙ、Ｚグリッド
上のｔパラメータをtx、ty、tzとする。説明の都合上、
２次元的に示した第７図に示すように、光線が次にはい
る直方体（ｉ′,j′,k′）は、現在の直方体（i,j,k）
に対して、現在のtx、ty、tzのうち最小の値を持つ軸ｌ
（ｌ＝x,y,z）を＋１増分（傾きが正なら＋１、負なら
−１）させればよい。いったん、次の直方体に移行する
とその軸のｔパラメータ、tl（ｌ＝x,y,z）にdtl（ｌ＝
x,y,z）を加算しておく。以下、同様の処理を行なうこ
とにより次々と直方体を横断していくことが出来る。
C.発明が解決しようとする問題点 ところで、上記（Ｉ）、（II）からなる従来方法の場
合、表示対象の物体に完全に包含される直方体において
は、光線と物体表面の交点が存在し得ないにもかかわら
ず、かかる直方体が登録され、サンプリングの対象とな
ってしまう。すなわち、第８図に示すように格子空間42
中の直方体を複数個所有する透明な物体44の中を光線が
通過する場合、交点を求めるための処理が不必要な直方
体46、48に対してもサンプリングを行なうことになり、
それだけ無駄な時間を費すことになる。多数の透明な物
体の画像を生成しようとする場合、特にこの問題は著し
くなる。
合、表示対象の物体に完全に包含される直方体において
は、光線と物体表面の交点が存在し得ないにもかかわら
ず、かかる直方体が登録され、サンプリングの対象とな
ってしまう。すなわち、第８図に示すように格子空間42
中の直方体を複数個所有する透明な物体44の中を光線が
通過する場合、交点を求めるための処理が不必要な直方
体46、48に対してもサンプリングを行なうことになり、
それだけ無駄な時間を費すことになる。多数の透明な物
体の画像を生成しようとする場合、特にこの問題は著し
くなる。
D.問題点を解決するための手段 本発明の画像生成方法では、表示対象の物体44を内包す
る領域42を分割して得たセルのうち、第１図に示すよう
に物体44の表面50を含むセルだけを登録しておく。交点
計算は、この表面の存在する直方体のみについて行な
う。よって、物体44の表示に要する時間を減少させるこ
とができる。
る領域42を分割して得たセルのうち、第１図に示すよう
に物体44の表面50を含むセルだけを登録しておく。交点
計算は、この表面の存在する直方体のみについて行な
う。よって、物体44の表示に要する時間を減少させるこ
とができる。
なお、本発明では、表示対象の物体を内包する領域、お
よびこれを分割したセルは、どちらも必ずしも直方体状
でなくて差し支えないが、実現のしやすさを考慮する
と、直方体状であることが有利である。以下でも、前者
を単に格子空間、後者を単に直方体と呼ぶ。
よびこれを分割したセルは、どちらも必ずしも直方体状
でなくて差し支えないが、実現のしやすさを考慮する
と、直方体状であることが有利である。以下でも、前者
を単に格子空間、後者を単に直方体と呼ぶ。
E.実施例 物体の表面が１つの等関数値曲面として表わされる場合
を例にとって説明する。等関数値曲面とは、与えられた
空間上の関数Ｆ（X,Y,Z）に対し、Ｆ（X,Y,Z）＝Ｃを満
たす点の集合である。まず、各画素に対して光線と等関
数値曲面の最も視点に近い交点を見つけなければならな
い。これは、光線の方程式vt＋ｓと等関数値曲面Ｆ（X,
Y,Z）＝Ｃから Ｆ（vxt＋sx,vyt＋sy,vzt＋sz）＝Ｃ （１） を満たす最も小さいパラメータｔを求めることである。
（１）式は、ｔを変数とする方程式となる。このとき、
（１）式が１元２次方程式の場合、その根は公式により
簡単に求めることができる。しかし、５次以上になると
一般に代数的な方法で解を求めることは不可能であり、
数値解析の手法により求めることになる。本発明が対象
とするのは、数値解析の手方により交点計算を行う光線
追跡法である。
を例にとって説明する。等関数値曲面とは、与えられた
空間上の関数Ｆ（X,Y,Z）に対し、Ｆ（X,Y,Z）＝Ｃを満
たす点の集合である。まず、各画素に対して光線と等関
数値曲面の最も視点に近い交点を見つけなければならな
い。これは、光線の方程式vt＋ｓと等関数値曲面Ｆ（X,
Y,Z）＝Ｃから Ｆ（vxt＋sx,vyt＋sy,vzt＋sz）＝Ｃ （１） を満たす最も小さいパラメータｔを求めることである。
（１）式は、ｔを変数とする方程式となる。このとき、
（１）式が１元２次方程式の場合、その根は公式により
簡単に求めることができる。しかし、５次以上になると
一般に代数的な方法で解を求めることは不可能であり、
数値解析の手法により求めることになる。本発明が対象
とするのは、数値解析の手方により交点計算を行う光線
追跡法である。
E.1.前処理 以下で説明する手法は、等関数値曲面がＦ（x,y,z）＝
Ｃの形式で与えられること、その等関数値曲面の存在領
域（Xmin,Ymin,Zmin≦X,Y,Z≦Xmax,Ymax,Zmax）を利用
者が与えることを前提としている。
Ｃの形式で与えられること、その等関数値曲面の存在領
域（Xmin,Ymin,Zmin≦X,Y,Z≦Xmax,Ymax,Zmax）を利用
者が与えることを前提としている。
前処理により、空間領域分割は直方体分割により行な
う。直方体分割を使用した理由は、八分木構造に比べて
格子空間の横断計算が少ないからである。ここで格子点
は（i,j,k）（ｉ＝1,Ni,j＝1,Nj,K＝1,Nk;Ni、Nj、Nkは
各ｘ、ｙ、ｚ方向の格子数）で表されている。また直方
体（i,j,k）というとき、（i,j,k）、（ｉ＋1,j,k）、
（i,j＋1,k）、（i,j,k＋１）、（ｉ＋1,j＋1,k）、
（ｉ＋1,j,k＋１）、（i,j＋1,k＋１）、（ｉ＋1,j＋1,
k＋１）を頂点とする直方体をさす。まず、利用者が与
える等関数値曲面の存在領域（Xmin,Ymin,Zmin≦X,Y,Z
≦Xmax,Ymax,Zmax）をNi×Nj×Nk個に分割する。次に各
直方体を ＊等関数値曲面の存在空間 ＊等関数値曲面の非存在空間 の二つに分ける。この判定は、次の方法で行なう。
う。直方体分割を使用した理由は、八分木構造に比べて
格子空間の横断計算が少ないからである。ここで格子点
は（i,j,k）（ｉ＝1,Ni,j＝1,Nj,K＝1,Nk;Ni、Nj、Nkは
各ｘ、ｙ、ｚ方向の格子数）で表されている。また直方
体（i,j,k）というとき、（i,j,k）、（ｉ＋1,j,k）、
（i,j＋1,k）、（i,j,k＋１）、（ｉ＋1,j＋1,k）、
（ｉ＋1,j,k＋１）、（i,j＋1,k＋１）、（ｉ＋1,j＋1,
k＋１）を頂点とする直方体をさす。まず、利用者が与
える等関数値曲面の存在領域（Xmin,Ymin,Zmin≦X,Y,Z
≦Xmax,Ymax,Zmax）をNi×Nj×Nk個に分割する。次に各
直方体を ＊等関数値曲面の存在空間 ＊等関数値曲面の非存在空間 の二つに分ける。この判定は、次の方法で行なう。
各格子点（i,j,k）上の関数値Ｆ（x,y,z）を求め、格子
点を頂点とする直方体（i,j,k）に等関数値曲面が存在
するか調べる。これは、直方体内の各関数値と定数Ｃと
の大小関係から決まる。つまり、直方体（i,j,k）の８
頂点に対して、Ｆ−Ｃを計算し一つでも異符号が含まれ
ている場合、その直方体（i,j,k）は、等関数値曲面の
存在空間とする。すべて、同符号の場合、さらにMi×Mj
×Mk個に再分割しながら、再分割後の各頂点のＦ−Ｃを
計算する。計算された各頂点に一つでも異符号が含まれ
ていることがわかった段階で、その直方体（i,j,k）を
等関数値曲面の存在空間として登録する。再分割後の各
頂点もすべて同符号なら、等関数値曲面の非存在空間と
する。
点を頂点とする直方体（i,j,k）に等関数値曲面が存在
するか調べる。これは、直方体内の各関数値と定数Ｃと
の大小関係から決まる。つまり、直方体（i,j,k）の８
頂点に対して、Ｆ−Ｃを計算し一つでも異符号が含まれ
ている場合、その直方体（i,j,k）は、等関数値曲面の
存在空間とする。すべて、同符号の場合、さらにMi×Mj
×Mk個に再分割しながら、再分割後の各頂点のＦ−Ｃを
計算する。計算された各頂点に一つでも異符号が含まれ
ていることがわかった段階で、その直方体（i,j,k）を
等関数値曲面の存在空間として登録する。再分割後の各
頂点もすべて同符号なら、等関数値曲面の非存在空間と
する。
各直方体（i,j,k）をいくつに分割するかは、等関数値
曲面の局所性にも依存するが、一般にNi,Nj,Nkの値が大
きく（Ni,Nj,Nk＞20）、存在領域の指定が適当な場合
は、第９図に示すような直方体52の８分割（Mi＝Mj＝Mk
＝２）、Ni,Nj,Nkの値が小さい場合は、第10図に示すよ
うな27分割（Mi＝Mj＝Mk＝３）程度で十分である。第11
図に示すような等関数値曲面54の局所性が著しい場合、
Mi、Mj、Mkの値を大きくする。
曲面の局所性にも依存するが、一般にNi,Nj,Nkの値が大
きく（Ni,Nj,Nk＞20）、存在領域の指定が適当な場合
は、第９図に示すような直方体52の８分割（Mi＝Mj＝Mk
＝２）、Ni,Nj,Nkの値が小さい場合は、第10図に示すよ
うな27分割（Mi＝Mj＝Mk＝３）程度で十分である。第11
図に示すような等関数値曲面54の局所性が著しい場合、
Mi、Mj、Mkの値を大きくする。
E.2.光線と格子空間との交差判定 格子空間は、６個の平面の式、Ｘ＝Xmin、Ｙ＝Ymin、Ｚ
＝Zmin、Ｘ＝Xmax、Ｙ＝Ymax、Ｚ＝Zmaxで囲まれるの
で、光線と各平面の交点を代数的に求め、その値が格子
空間に含まれているかどうかを調べればよい。格子空間
に含まれる交点の中で視点に最も近い交点をもって、光
線の最初に入る直方体が決定される。
＝Zmin、Ｘ＝Xmax、Ｙ＝Ymax、Ｚ＝Zmaxで囲まれるの
で、光線と各平面の交点を代数的に求め、その値が格子
空間に含まれているかどうかを調べればよい。格子空間
に含まれる交点の中で視点に最も近い交点をもって、光
線の最初に入る直方体が決定される。
E.3.格子空間の横断 光線とどの直方体とが交差するかどうかは、最初の直方
体と光線の傾きから増分計算のみで行なうことができ
る。これについては、すでに従来技術の欄で説明したの
で省略する。等関数値曲面の存在する直方体に対して
は、直方体に含まれる光線上の点をサンプリングし、各
点に対して関数値Ｆを計算していく。サンプリング幅
は、経験上、直方体の最大幅の1/20程度以下で十分であ
った。
体と光線の傾きから増分計算のみで行なうことができ
る。これについては、すでに従来技術の欄で説明したの
で省略する。等関数値曲面の存在する直方体に対して
は、直方体に含まれる光線上の点をサンプリングし、各
点に対して関数値Ｆを計算していく。サンプリング幅
は、経験上、直方体の最大幅の1/20程度以下で十分であ
った。
E.4.格子空間を利用した画像生成アルゴリズム 第12図に全体の流れを示す。以下、この画像生成アルゴ
リズムを第13図を用いて詳細に説明する。前処理によ
り、格子空間に含まれる直方体を等関数値曲面の存在し
ない直方体と存在する直方体に分ける。視点Ｑからの光
線Ｉ、II、III、IVを例にアルゴリズムの流れを示す。
なお、この例では、画面56（第13図）の画素に割り当て
る光学的情報としては色だけを考えるものとする。
リズムを第13図を用いて詳細に説明する。前処理によ
り、格子空間に含まれる直方体を等関数値曲面の存在し
ない直方体と存在する直方体に分ける。視点Ｑからの光
線Ｉ、II、III、IVを例にアルゴリズムの流れを示す。
なお、この例では、画面56（第13図）の画素に割り当て
る光学的情報としては色だけを考えるものとする。
（ケース1:光線Ｉ） 光線Ｉは、格子空間と交わらないためブロック70→71→
72→73→84の流れにより処理される。ブロック84でスタ
ックされた情報から色計算を行ない終了する。ここでは
格子空間と交差しないので背景色となる。そして、次の
光線の処理に移る。
72→73→84の流れにより処理される。ブロック84でスタ
ックされた情報から色計算を行ない終了する。ここでは
格子空間と交差しないので背景色となる。そして、次の
光線の処理に移る。
（ケース2:光線II） 光線IIは格子空間とは交わるが等関数値曲数の存在する
直方体と交わらないため、ブロック70→71→72→74（直
方体106の取りだし）→75→76→74（直方体107の取りだ
し）→以下、ブロック75→76→74→...の流れが繰返さ
れ、ブロック75で取り出す直方体がなくなるとブロック
73にはいって背景色であることをスタックしてブロック
84にはいる。そして、次の光線の処理に移る。
直方体と交わらないため、ブロック70→71→72→74（直
方体106の取りだし）→75→76→74（直方体107の取りだ
し）→以下、ブロック75→76→74→...の流れが繰返さ
れ、ブロック75で取り出す直方体がなくなるとブロック
73にはいって背景色であることをスタックしてブロック
84にはいる。そして、次の光線の処理に移る。
（ケース3:光線III） 光線IIIについては、ブロック70→71→72→74→75→76
の流れより直方体116が取り出され、等関数値曲面の有
無が調べられる。直方体116は、等関数値曲面が存在し
ないのでブロック74→75→76の流れにより次の直方体11
7が取り出される。直方体117には等関数値曲面が存在す
るので、ブロック77にはいってサンプリングが行なわれ
る。この場合、光線IIIと直方体117の等関数値曲面とは
交差しないので符号の変更はないためブロック78から同
74→75→76の流れにより直方体118が取り出される。直
方体118にも等関数値曲面が存在するのでブロック77に
はいってサンプリングが行なわれるが、この場合サンプ
リングの途中で符号が変更するのでブロック79にはい
る。中間値の定理よりこの領域に解が存在するので２分
法、ニュートン法等により交点Ｘを求める。
の流れより直方体116が取り出され、等関数値曲面の有
無が調べられる。直方体116は、等関数値曲面が存在し
ないのでブロック74→75→76の流れにより次の直方体11
7が取り出される。直方体117には等関数値曲面が存在す
るので、ブロック77にはいってサンプリングが行なわれ
る。この場合、光線IIIと直方体117の等関数値曲面とは
交差しないので符号の変更はないためブロック78から同
74→75→76の流れにより直方体118が取り出される。直
方体118にも等関数値曲面が存在するのでブロック77に
はいってサンプリングが行なわれるが、この場合サンプ
リングの途中で符号が変更するのでブロック79にはい
る。中間値の定理よりこの領域に解が存在するので２分
法、ニュートン法等により交点Ｘを求める。
物体が反射、透過しない場合は、ブロック81にはいって
交点の情報をスタックし、ブロック84にはいる。
交点の情報をスタックし、ブロック84にはいる。
物体が反射あるいは透過する場合は、交点Ｘからその反
射あるいは透過する方向に光線III′を考え、その光線
に対して先に述べた光線IIIと同様の処理を行なう。第1
3図の物体が透明である場合を例にとって本発明による
交点計算の処理を説明すると、透過光線III′は、交点
Ｘから始まって直方体118、124、125を横断する。従っ
て、ブロック80からの流れはブロック82→83（IIIとは
若干向きの異なる屈折光線III′の取り出し）77→78の
流れを経て、ブロック74にはいり直方体124が取り出さ
れるが、直方体124は等関数値曲面の存在空間でないの
で無駄なサンプリングはせずにブロック75→76→74の流
れで直方体125が取り出される。直方体125は等関数値曲
面の存在空間なのでブロック76→77→78→79と流れ、新
しい交点Ｙが求まる。ブロック80でさらに透過光の計算
があるので、ブロック82にはいって交点Ｙの情報をスタ
ックしてブロック83→77→78→74→75と流れる。ブロッ
ク75では次の直方体がないので流れはブロック73にはい
り、最終的にスタックされた交点情報（ここでは、交点
Ｘ、交点Ｙ、背景の情報）によりブロック84で色計算が
行なわれる。そして、次の光線IVの処理に移る。
射あるいは透過する方向に光線III′を考え、その光線
に対して先に述べた光線IIIと同様の処理を行なう。第1
3図の物体が透明である場合を例にとって本発明による
交点計算の処理を説明すると、透過光線III′は、交点
Ｘから始まって直方体118、124、125を横断する。従っ
て、ブロック80からの流れはブロック82→83（IIIとは
若干向きの異なる屈折光線III′の取り出し）77→78の
流れを経て、ブロック74にはいり直方体124が取り出さ
れるが、直方体124は等関数値曲面の存在空間でないの
で無駄なサンプリングはせずにブロック75→76→74の流
れで直方体125が取り出される。直方体125は等関数値曲
面の存在空間なのでブロック76→77→78→79と流れ、新
しい交点Ｙが求まる。ブロック80でさらに透過光の計算
があるので、ブロック82にはいって交点Ｙの情報をスタ
ックしてブロック83→77→78→74→75と流れる。ブロッ
ク75では次の直方体がないので流れはブロック73にはい
り、最終的にスタックされた交点情報（ここでは、交点
Ｘ、交点Ｙ、背景の情報）によりブロック84で色計算が
行なわれる。そして、次の光線IVの処理に移る。
E.5.本手法の評価 本発明を次の等関数値曲面に対して適用し、各分割数毎
に、データを読み込ませてからメイン・メモリ上に画像
データが生成されるまでのCPU時間を計測した。使用さ
れた関数曲面は、 F(X、Y、Z)=(X２+Y２-1)２+4*Z２+0.5*X=C である。
に、データを読み込ませてからメイン・メモリ上に画像
データが生成されるまでのCPU時間を計測した。使用さ
れた関数曲面は、 F(X、Y、Z)=(X２+Y２-1)２+4*Z２+0.5*X=C である。
第14図にその処理時間を示す。画面の画素数は、512×5
12であり、分割数Ni＝Nj＝Nkを、０、４、８、15、30、
45、60として計測した。分割数０とは、本発明の手法を
使用せずに直接、光線追跡法を使用した場合である。本
手法により、高品質な画像がより高速に表示できること
がわかる。また、本発明の手法は、簡単なのでハードウ
ェア化が容易である。
12であり、分割数Ni＝Nj＝Nkを、０、４、８、15、30、
45、60として計測した。分割数０とは、本発明の手法を
使用せずに直接、光線追跡法を使用した場合である。本
手法により、高品質な画像がより高速に表示できること
がわかる。また、本発明の手法は、簡単なのでハードウ
ェア化が容易である。
E.6.その他の適用例 以上、物体の表面が１つの等関数値曲面として表される
場合について説明したが、物体の表面が場所によって異
なる複数の等関数値曲面から構成される場合についても
本発明は適用可能である。
場合について説明したが、物体の表面が場所によって異
なる複数の等関数値曲面から構成される場合についても
本発明は適用可能である。
また、第15図に示すように非等分割方式、つまり、物体
の表面が存在する直方体についてはそうでない直方体よ
りもさらに細かく分割して該表面の有無を調べることに
よって、物体の表面に関する情報を取得してもよい。
の表面が存在する直方体についてはそうでない直方体よ
りもさらに細かく分割して該表面の有無を調べることに
よって、物体の表面に関する情報を取得してもよい。
F.発明の効果 本発明によれば、従来手法に比べて高速な光線追跡が行
なえるようになる。本発明は、透明な等関数値曲面を持
つ物体表示して、シミュレーションの解析等を行う際に
特に有効である。
なえるようになる。本発明は、透明な等関数値曲面を持
つ物体表示して、シミュレーションの解析等を行う際に
特に有効である。
第１図は、本発明による格子空間に関する物体情報の持
ち方を説明した図である。第２図は、光線追跡法の概念
を説明した図である。第３図は、物体表面での反射、屈
折光線の追跡を示した図である。第４図は、数値解析の
方法によるサンプリングを２次元で示した図である。第
５図は、分割された格子空間に関する物体情報の持ち方
を２次元で示した図である。第６図は、格子空間にある
物体との交差判定を２次元で示した図である。第７図は
光線と直方体との交差判定の概念図である。第８図は、
従来の格子空間に関する物体情報の持ち方を説明した図
である。第９図は直方体を８分割した場合を示す斜視図
である。第10図は直方体を27分割した場合を示す斜視図
である。第11図は、等関数値曲面の局所性が著しい場合
を２次元で説明した図である。第12図は、本発明による
手法の全体の流れを示すフローチャートである。第13図
は、等関数値曲面の存在する格子空間を切断して表示し
た図である。第14図は、本発明による処理時間を、格子
空間の分割数を変えて示すグラフである。第15図は、格
子空間を非等分割した場合を２次元的に示す説明図であ
る。
ち方を説明した図である。第２図は、光線追跡法の概念
を説明した図である。第３図は、物体表面での反射、屈
折光線の追跡を示した図である。第４図は、数値解析の
方法によるサンプリングを２次元で示した図である。第
５図は、分割された格子空間に関する物体情報の持ち方
を２次元で示した図である。第６図は、格子空間にある
物体との交差判定を２次元で示した図である。第７図は
光線と直方体との交差判定の概念図である。第８図は、
従来の格子空間に関する物体情報の持ち方を説明した図
である。第９図は直方体を８分割した場合を示す斜視図
である。第10図は直方体を27分割した場合を示す斜視図
である。第11図は、等関数値曲面の局所性が著しい場合
を２次元で説明した図である。第12図は、本発明による
手法の全体の流れを示すフローチャートである。第13図
は、等関数値曲面の存在する格子空間を切断して表示し
た図である。第14図は、本発明による処理時間を、格子
空間の分割数を変えて示すグラフである。第15図は、格
子空間を非等分割した場合を２次元的に示す説明図であ
る。
Claims (4)
- 【請求項１】演算処理手段、表示手段、および記憶手段
を備えた画像生成システムにおいて、投影面と対応づけ
られた上記表示手段の画面上に少なくとも１つの物体の
上記投影面への投影像を生成する際に、（ａ）（a1）視
点を設定するとともに、 上記画面上の各画素毎に該視点と上記画面上の画素に対
応する投影面上の点とを結ぶ光線を想定し、 各想定された光線について、上記視点の最も近くで上記
表示対象の物体の表面と交わる交点を探索し、 （a2）求める交点が得られれば、 直前に得られた交点を基点とする反射光線または上記物
体を透過する光線の少なくとも一方を想定するととも
に、該直前に得られた交点の最も近くで該想定された光
線が上記表示対象の物体の表面と交わる交点を探索する
ことを含むステップ を少なくとも１回実行し、 （ｂ）上記視点と上記画面上の１つの画素に対応する投
影面上の点とを結ぶ上記想定された光線に関して、該光
線から始まる上記（ａ）のような交点探索を行った結
果、上記表示対象の物体の表面との交点が１つ以上得ら
れた場合は、各得られた交点における上記物体表面の属
性を勘案して上記光線に関連する画素に割り当てる光学
的情報を決定し、上記表示対象の物体の表面との交点が
得られなかった場合は、上記光線に関連する画素に上記
物体の背景に相当する光学的情報を割り当てる 光線追跡法を用いた画像生成方法において、 （Ｉ）上記（a1）のステップに先立って、 （ｉ）上記表示対象の物体を内包する空間領域を設定
し、 （ii）上記空間領域を複数個のセルに分割し、 （iii）上記空間領域の各セルについて上記表示対象の
物体の表面の存否を判断し、上記物体の表面を含むセル
は上記記憶手段の中に設けたテーブルに登録しておき、 （II）上記（a1）の段階では、上記想定された各光線に
ついて上記表示対象の物体の表面との交点を計算する前
に上記空間領域との交差の有無を算出し、上記空間領域
と交差しない光線については、上記物体の表面と交差す
ることはないと判断して交点探索を終了し、 （III）上記（a1），（a2）の段階を通じて、上記空間
領域と交差する光線については、上記表示対象の物体の
表面との交点を計算する前に該光線が交差するセルを算
出し、かつ算出されたセルを上記テーブルと照合し、そ
の結果、該算出されたセルが上記表示対象の物体の表面
を含む場合は、該セルにおいて該光線と上記物体の表面
との交点をサンプリングを交えて数値解析的に探索し、
該算出されたセルが上記物体の表面を含まない場合は、
該セルにおいて該光線が上記物体の表面と交差すること
はないと判断して該セルにおける交点探索を終了する ことを特徴とする方法。 - 【請求項２】上記（ii）の段階で、上記空間領域を複数
個の直方体状のセルに等分割する ことを特徴とする特許請求の範囲第１項記載の方法。 - 【請求項３】上記（iii）の段階で、上記表示対象の物
体の表面を含むセルについては、該セルをさらに小さな
直方体状のセルに再分割し、再分割されたセルの各々に
ついて上記物体の表面の存否を判断し、再分割されたセ
ルのうち上記表面を含むものだけを上記テーブルに登録
する ことを特徴とする特許請求の範囲第１項または第２項の
何れかに記載の方法。 - 【請求項４】上記各画素に割り当てられる光学的情報
は、色および輝度である 特許請求の範囲第１項ないし第３項の何れかに記載の方
法。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62176099A JPH0769972B2 (ja) | 1987-07-16 | 1987-07-16 | 画像生成方法 |
| US07/215,007 US4865423A (en) | 1987-07-16 | 1988-07-05 | Method for generating images |
| CA000571400A CA1304525C (en) | 1987-07-16 | 1988-07-07 | Method for generating images |
| EP19880306457 EP0299769A3 (en) | 1987-07-16 | 1988-07-14 | Method for generating images using ray-tracing |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62176099A JPH0769972B2 (ja) | 1987-07-16 | 1987-07-16 | 画像生成方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS6431279A JPS6431279A (en) | 1989-02-01 |
| JPH0769972B2 true JPH0769972B2 (ja) | 1995-07-31 |
Family
ID=16007679
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP62176099A Expired - Lifetime JPH0769972B2 (ja) | 1987-07-16 | 1987-07-16 | 画像生成方法 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US4865423A (ja) |
| EP (1) | EP0299769A3 (ja) |
| JP (1) | JPH0769972B2 (ja) |
| CA (1) | CA1304525C (ja) |
Families Citing this family (28)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| NL8901447A (nl) * | 1989-06-07 | 1991-01-02 | Volvo Car Bv | Werkwijze voor het weergeven van zichtvelden van een spiegel. |
| US5265034A (en) * | 1991-05-13 | 1993-11-23 | The United States Of America As Represented By The Administrator Of The National Aeronautics And Space Administration | Feedback controlled optics with wavefront compensation |
| GB9315852D0 (en) * | 1993-07-30 | 1993-09-15 | Video Logic Ltd | Shading three-dimensional images |
| US5729672A (en) * | 1993-07-30 | 1998-03-17 | Videologic Limited | Ray tracing method and apparatus for projecting rays through an object represented by a set of infinite surfaces |
| US5488700A (en) * | 1993-07-30 | 1996-01-30 | Xerox Corporation | Image rendering system with local, adaptive estimation of incident diffuse energy |
| US5619627A (en) * | 1994-05-03 | 1997-04-08 | Loral Aerospace Corp. | Multiple-level occulting using a mask buffer |
| US6445807B1 (en) * | 1996-03-22 | 2002-09-03 | Canon Kabushiki Kaisha | Image processing method and apparatus |
| WO1998000811A1 (en) * | 1996-06-28 | 1998-01-08 | Resolution Technologies, Inc. | Fly-through computer aided design method and apparatus |
| US6767286B1 (en) | 1996-11-22 | 2004-07-27 | Kabushiki Kaisha Sega Enterprises | Game device, picture data forming method and medium |
| US6234901B1 (en) * | 1996-11-22 | 2001-05-22 | Kabushiki Kaisha Sega Enterprises | Game device, picture data and flare forming method |
| US6023279A (en) * | 1997-01-09 | 2000-02-08 | The Boeing Company | Method and apparatus for rapidly rendering computer generated images of complex structures |
| CN1095146C (zh) | 1997-08-25 | 2002-11-27 | 颜嘉涵 | 利用蜂巢式单元构造实体图形的方法 |
| US6674922B1 (en) * | 1999-03-26 | 2004-01-06 | Canon Kabushiki Kaisha | Image processing method, image processing apparatus, and storage medium |
| US6574360B1 (en) * | 1999-07-23 | 2003-06-03 | International Business Machines Corp. | Accelerated occlusion culling using directional discretized occluders and system therefore |
| DE10106562B4 (de) | 2001-02-13 | 2008-07-03 | Rodenstock Gmbh | Verfahren zur Demonstration des Einflusses einer bestimmten Brillenfassung und der in diese Brillenfassung eingesetzten optischen Gläser |
| IL143255A (en) | 2001-05-20 | 2015-09-24 | Simbionix Ltd | Endoscopic ultrasonography simulation |
| US20040243364A1 (en) * | 2002-05-22 | 2004-12-02 | Wendelin Timothy J. | Method and system for modeling solar optics |
| US7850456B2 (en) | 2003-07-15 | 2010-12-14 | Simbionix Ltd. | Surgical simulation device, system and method |
| US20060268297A1 (en) * | 2005-05-25 | 2006-11-30 | Lexmark International, Inc. | Method for constructing a lookup table for converting data from a first color space to a second color space |
| US7737986B2 (en) * | 2006-08-29 | 2010-06-15 | Texas Instruments Incorporated | Methods and systems for tiling video or still image data |
| US8543338B2 (en) | 2007-01-16 | 2013-09-24 | Simbionix Ltd. | System and method for performing computerized simulations for image-guided procedures using a patient specific model |
| US8500451B2 (en) | 2007-01-16 | 2013-08-06 | Simbionix Ltd. | Preoperative surgical simulation |
| US8400448B1 (en) | 2007-12-05 | 2013-03-19 | The United States Of America, As Represented By The Secretary Of The Navy | Real-time lines-of-sight and viewsheds determination system |
| US8325178B1 (en) | 2007-12-05 | 2012-12-04 | The United States Of America, As Represented By The Secretary Of The Navy | Lines-of-sight and viewsheds determination system |
| JP6039042B1 (ja) | 2015-11-20 | 2016-12-07 | 株式会社スクウェア・エニックス | 描画処理プログラム、描画処理装置、描画処理方法、発音処理プログラム、発音処理装置、及び、発音処理方法 |
| US11095307B2 (en) | 2019-09-03 | 2021-08-17 | Nvidia Corporation | Performing cyclic redundancy checks using parallel computing architectures |
| US12518468B2 (en) * | 2019-09-23 | 2026-01-06 | Nvidia Corporation | Spatial search using ray tracing |
| CN113267813A (zh) * | 2021-06-18 | 2021-08-17 | 重庆大学 | 一种速度结构和震源位置联合反演的方法、系统、终端及可读存储介质 |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4185918A (en) * | 1975-08-27 | 1980-01-29 | Solid Photography Inc. | Arrangement for sensing the characteristics of a surface and determining the position of points thereon |
| US4126395A (en) * | 1977-05-25 | 1978-11-21 | Solid Photography, Inc. | Method for determining the spatial location of points on a specular surface |
| US4654872A (en) * | 1983-07-25 | 1987-03-31 | Omron Tateisi Electronics Co. | System for recognizing three-dimensional objects |
| JPS61139890A (ja) * | 1984-12-13 | 1986-06-27 | Fujitsu Ltd | 光線追跡画像生成処理方式 |
| JPS63196988A (ja) * | 1987-02-10 | 1988-08-15 | Fujitsu Ltd | 三次元物体表示方式 |
-
1987
- 1987-07-16 JP JP62176099A patent/JPH0769972B2/ja not_active Expired - Lifetime
-
1988
- 1988-07-05 US US07/215,007 patent/US4865423A/en not_active Expired - Fee Related
- 1988-07-07 CA CA000571400A patent/CA1304525C/en not_active Expired - Lifetime
- 1988-07-14 EP EP19880306457 patent/EP0299769A3/en not_active Withdrawn
Also Published As
| Publication number | Publication date |
|---|---|
| JPS6431279A (en) | 1989-02-01 |
| EP0299769A2 (en) | 1989-01-18 |
| CA1304525C (en) | 1992-06-30 |
| EP0299769A3 (en) | 1991-08-28 |
| US4865423A (en) | 1989-09-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0769972B2 (ja) | 画像生成方法 | |
| US5579454A (en) | Three dimensional graphics processing with pre-sorting of surface portions | |
| US5509110A (en) | Method for tree-structured hierarchical occlusion in image generators | |
| US6300965B1 (en) | Visible-object determination for interactive visualization | |
| US6392647B1 (en) | System and method for computer modeling of 3D objects or surfaces by mesh constructions having optimal quality characteristics and dynamic resolution capabilities | |
| CA2225017C (en) | Method and apparatus for rapidly rendering computer generated images of complex structures | |
| US5442733A (en) | Method and apparatus for generating realistic images using a discrete representation | |
| EP0311081B1 (en) | Displaying method and apparatus for three-dimensional computer graphics | |
| CA2060975C (en) | Scientific visualization system | |
| Arnaldi et al. | A new space subdivision method for ray tracing CSG modelled scenes | |
| US6208997B1 (en) | Rapid production of optimal-quality reduced-resolution representations of very large databases | |
| JPH06223198A (ja) | 光線追跡による画像生成装置及び方法 | |
| JPH07120434B2 (ja) | ボリュームレンダリングを行う方法及び装置 | |
| JPH07152926A (ja) | ３次元像を陰影付けする方法 | |
| CN100418108C (zh) | 三维扫描系统中的图形重构方法 | |
| US20040068530A1 (en) | Implicit function rendering method of nonmanifold, direct drawing method of implicit function curved surface and programs thereof | |
| JP2003330976A (ja) | 境界データの内外判定方法とそのプログラム | |
| US7050053B2 (en) | Geometric folding for cone-tree data compression | |
| Kumar | Interactive rendering of parametric spline surfaces | |
| US6587103B1 (en) | Method and apparatus for determining coincident lines | |
| KR100372901B1 (ko) | 지.에프-버퍼를 이용하여 광선추적법의 속도를 개선하는방법 | |
| KR930003811B1 (ko) | 3차원도형 처리방법 및 그 장치 | |
| Marschner et al. | Ray tracing | |
| JPH03123985A (ja) | 輪郭線および／または稜線の描画方法 | |
| JP2624675B2 (ja) | 三次元形状表示方式 |