(57)【特許請求の範囲】
【請求項１】
同一平面上に頂点Ｐ１、Ｐ２、・・・、Ｐｎを有する凸多角形(ｎ＞２の整数)と同じ平面上に存在する視線との交点Ｑが、前記凸多角形の内部に存在するか、前記凸多角形の境界に存在するか、または前記凸多角形の外部に存在するかの判定を行なう領域内外判定を、交点距離検出部と、交点座標算出部と、交差判定部と、隠面消去部と、距離判定条件設定部とを有する構成で行なう図形表示装置において、
前記交差判定部を、
前記交点座標算出部より前記凸多角形の各頂点と前記交点とを結んで形成される各頂点ベクトルが順次供給され、隣接する２頂点間のベクトルの外積がゼロかどうかの判定を行なう第１の交差判定部と、
前記第１の交差判定部の外積がゼロであるとの出力情報と前記頂点ベクトルとが供給され、前記隣接する２頂点間の外積がゼロであるベクトルにおける内積がゼロより大の場合は前記交点は前記凸多角形の外部にあり、前記内積がゼロより小の場合は前記交点は前記凸多角形の２頂点間の境界線上にあるとの判定を行なう第２の交差判定部と、
前記第１の交差判定部の外積が前記凸多角形においてすべてゼロでないとの出力情報と前記交点座標算出部よりの凸多角形の法線ベクトルとが供給され、前記２頂点間のベクトルの外積と前記凸多角形の法線ベクトルとの間の内積がゼロより大の場合はsign=１とし、ゼロより小の場合はsign=−１と判定して、前記隣接するすべての２頂点間で前記signがすべて同一の場合は前記交点は前記凸多角形の内部にあり、前記signに異なるものがある場合は前記交点は前記凸多角形の外部にあるとの判定を行なう第３の交差判定部と
より構成したことを特徴とする図形表示装置。
【請求項２】
請求項１に記載された図形表示装置において、
前記隠面消去部は、前記交点が境界線上にあると判定された場合に限り、前記距離判定条件設定部より前記凸多角形の交点から視点までの距離に一定値を加算する指示が供給され、前記隠面消去部において、それまでに処理した凸多角形における距離とで大小の比較を行ない、より距離の短い前記凸多角形の交点を選択することを特徴とする図形表示装置。
【請求項３】
同一平面上に頂点Ｐ１、Ｐ２、・・・、Ｐｎを有する凸多角形(ｎ＞２の整数)と同じ平面上に存在する視線との交点Ｑが、前記凸多角形の内部に存在するか、前記凸多角形の境界に存在するか、または前記凸多角形の外部に存在するかの判定を行なう領域内外判定を、交点距離検出部と、交点座標算出部と、交差判定部と、隠面消去部と、距離判定条件設定部とを有する図形表示装置に図形表示を行わせる図形表示方法において、
前記交差判定部において、
前記交点座標算出部から前記凸多角形の各頂点と前記交点とを結んで形成される各頂点ベクトルが順次供給され、隣接する２頂点間のベクトルの外積がゼロかどうかの判定を行なう第１の交差判定ステップと、
前記第１の交差判定ステップの外積がゼロであるとの出力情報と前記頂点ベクトルとが供給され、前記隣接する２頂点間の外積がゼロであるベクトルにおける内積がゼロより大の場合は前記交点は前記凸多角形の外部にあり、前記内積がゼロより小の場合は前記交点は前記凸多角形の２頂点間の境界線上にあるとの判定を行なう第２の交差判定ステップと、
前記第１の交差判定ステップの外積が前記凸多角形においてすべてゼロでないとの出力情報と前記交点座標算出ステップよりの凸多角形の法線ベクトルとが供給され、前記２頂点間のベクトルの外積と前記凸多角形の法線ベクトルとの間の内積がゼロより大の場合はsign=１とし、ゼロより小の場合はsign=−１と判定して、前記隣接するすべての２頂点間で前記signがすべて同一の場合は前記交点は前記凸多角形の内部にあり、前記signに異なるものがある場合は前記交点は前記凸多角形の外部にあるとの判定を行なう第３の交差判定ステップと
を有して図形表示を行わせるようにしたことを特徴とする図形表示方法。
【請求項４】
請求項３に記載された図形表示方法において、
前記隠面消去部における隠面消去ステップは、前記交点が境界線上にあると判定された場合に限り、前記距離判定条件設定部における距離判定条件設定ステップより前記凸多角形の交点から視点までの距離に一定値を加算する指示が供給され、前記隠面消去ステップにおいて、それまでに処理した凸多角形における距離とで大小の比較を行ない、より距離の短い前記凸多角形の交点を選択することを特徴とする図形表示方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はＣＡＤやＣＧ（コンピュータグラフィックス）などの図形表示装置など、主に３次元図形の処理表示装置に係り、特にレイトレーシング法を用いてレンダリングを行なう図形表示装置に関する。
【０００２】
【従来の技術】
一般に、３次元図形をコンピュータ画面等の２次元平面上に表示するには、視点から見て図形が奥行き方向に相互に重なっている中から、画像の画素毎に最も手前にある図形を選択して表示する隠面消去処理が必要になる。
この隠面消去処理の方法の１つにレイトレーシング法が知られており、これについて以下に簡単に説明する。
【０００３】
図３のレイトレーシング法の原理図に示されるように、３次元空間に視点Ｒを設定し、この視点Ｒに対しスクリーンＳを設定する。
そして、このスクリーンＳ上の縦横一定間隔おきに画素Ｍを配置し、視点Ｒからこれらの各画素Ｍを通過する視線(レイ)Ｌを順次発生させる。
これらの各視線Ｌは対象とする３次元図形と交差するかどうかを判定し、視線Ｌ上において最も視点Ｒ側にある図形との交点Ｑを検索する方法である。
【０００４】
図５はそのレイトレーシング法による隠面消去処理装置の一例を示すブロック構成図である。
この隠面消去処理装置は、視線（レイ）発生部５１、交差判定・交点検出部
５２、及び輝度算出部５３で構成されている。
視線発生部５１は与えられた視野データから、視線データとなる視点座標及び視線ベクトルを発生させる。
【０００５】
ここで、視線ベクトルは図３に示すように、予め定めたスクリーンＳの大きさの中で、スクリーンＳを通過する視線Ｌを水平・垂直方向とも一定間隔おきに発生させた時の視線Ｌの方向をベクトルで表わしたものである。
視線Ｌの間隔は一般的にはスクリーンＳの画素Ｂの間隔とする場合が多いが、それより細かくする場合もある。
【０００６】
つぎの交差判定・交点検出部５２は、供給される視線データと図形データとより、対象となる３次元図形に対し、各視線Ｌが(スクリーンＳの向こう側で)視点Ｒに最も近い点（Ｑ）で交差する図形を特定し、その交点座標・法線ベクトルを検出する。
【０００７】
更に輝度算出部５３は前記交差判定・交点検出部５２で検出された交点座標・法線ベクトルと供給される図形データとより得られる物体の色・反射率などの交差した図形の特性、光源データなどから、予め定めた方法に基づいて、この視線ＬのスクリーンＳの画素Ｂ上での輝度値を求める。
【０００８】
従来の隠面消去処理装置の交差判定・交点検出部５２の構成の一例を図６に示す。
図６では視線データとして視点座標及び視線ベクトルが視線発生部５１より供給されると共に、別に対象となる各図形の位置・形状を示す図形データが供給される。
この図形データは球・円筒・直方体など、特定の形状に関するデータの場合もあるが、多くの場合は複数の凸多角形で構成され、各凸多角形の図形データはその頂点座標で示される。よって、ここでは凸多角形の場合について以下に説明する。
【０００９】
この交差判定・交点検出部５２は、交点距離検出部６１、交点座標算出部６２、交差判定部６３、及び隠面消去部６４より構成される。
交点距離検出部６１は、凸多角形を順に取り出し、この凸多角形が含まれる無限平面と前記視線との交点Ｑから視点Ｒまでの距離を検出する処理を行なう。
【００１０】
つぎの交点座標算出部６２は、交点Ｑから視点Ｒまでの距離を、視点Ｒと視線ベクトルで示される直線(実際には半直線)の式に代入して交点Ｑの座標を算出する処理を行なう。
更に交差判定部６３は、前記交点Ｑが対象となる凸多角形の内部にあるか外部にあるか、すなわち、視線Ｌがこの凸多角形と前記交点Ｑで交差するか否かの判定を行なう。
【００１１】
更につぎの隠面消去部６４は、前記交点距離検出部６１、交点座標算出部６２、及び交差判定部６３の処理の結果、この凸多角形が視線Ｌと交差する場合には、それまでに処理した凸多角形で得られた交点Ｑから視点Ｒまでの距離とここで得られた距離とを比較して、より距離が短いと判定された場合には、この凸多角形を現時点での交差図形とする。
【００１２】
前記の交点距離検出部６１乃至隠面消去部６４の処理を全ての凸多角形に対して行なうことにより、各視線Ｌに対する交差図形が確定し、結果である交点座標・法線ベクトルと、交差した交差図形・凸多角形の位置情報(どの図形のどの凸多角形に交差したか)などが輝度算出部５３に送られる。
【００１３】
従来の交差判定部６３における判定原理の一例を図７に示す。
交点座標算出部６２において座標が算出された凸多角形を含む無限平面と視線Ｌとの交点Ｑから、凸多角形の各頂点Ｐnへ半直線を引き、各半直線が、対象となる頂点と隣接しない凸多角形の辺と交差するか否かを判定する。
全ての半直線が該当する辺と交差しなければ、前記交点Ｑは凸多角形の内部に存在すると判定する(図７(a))。
【００１４】
１つの半直線でも前記凸多角形の辺と交差すると判定されれば、前記交点Ｑは凸多角形の外部に存在すると判定する(図７(b))。
すなわち、全ての半直線が該当する辺と交差しない場合は視線がこの凸多角形と前記交点Ｑで交差し、1つの半直線でも前記凸多角形の辺と交差した場合は、視線はこの凸多角形と交差しないと判定される。
【００１５】
【発明が解決しようとする課題】
しかし、図７の例では、各半直線と該当する凸多角形の辺との交点を求め、この交点と前記交点Ｑとの位置関係から、この交点が凸多角形上にあるか否かを判定する処理を全ての半直線−辺の組合わせで行なわなければならず、処理が大変に複雑になってしまうという問題があった。
【００１６】
また、従来例においては、図８に示すように２つの凸多角形の境界に視線との交点Ｑが位置するような場合、境界を凸多角形の外部と判定する処理では、境界の位置関係によっては、一部の境界部分が本来なら凸多角形と交差しているにもかかわらず交差しないと判定されて、背景の色がこの境界部分に出てしまうという問題があった。
【００１７】
また、境界を凸多角形の内部と判定する処理では、境界部分は多角形Ｅと多角形Ｆの２つの多角形に重複して隠面消去処理が行なわれるが、視点Ｒと交点Ｑとの距離が多角形Ｅと多角形Ｆでほぼ同じため、演算誤差によってこの境界部分における隠面消去処理の交点−視点間距離判定が、部分的に多角形Ｅと多角形Ｆでばらついてしまい、境界部分で２つの多角形が入り組んで見苦しくなってしまうことがあるといった問題があった。
【００１８】
【課題を解決するための手段】
そこで上記問題点を解決するために、
請求項１の発明は、
同一平面上に頂点Ｐ１、Ｐ２、・・・、Ｐｎを有する凸多角形(ｎ＞２の整数)と同じ平面上に存在する視線との交点Ｑが、前記凸多角形の内部に存在するか、前記凸多角形の境界に存在するか、または前記凸多角形の外部に存在するかの判定を行なう領域内外判定を、交点距離検出部１１と、交点座標算出部１２と、交差判定部１３と、隠面消去部１４と、距離判定条件設定部１５とを有する構成で行なう図形表示装置において、
前記交差判定部１３を、
前記交点座標算出部より前記凸多角形の各頂点と前記交点とを結んで形成される各頂点ベクトルが順次供給され、隣接する２頂点間のベクトルの外積がゼロかどうかの判定を行なう第１の交差判定部２１と、
前記第１の交差判定部の外積がゼロであるとの出力情報と前記頂点ベクトルとが供給され、前記隣接する２頂点間の外積がゼロであるベクトルにおける内積がゼロより大の場合は前記交点は前記凸多角形の外部にあり、前記内積がゼロより小の場合は前記交点は前記凸多角形の２頂点間の境界線上にあるとの判定を行なう第２の交差判定部２２と、
前記第１の交差判定部の外積が前記凸多角形においてすべてゼロでないとの出力情報と前記交点座標算出部よりの凸多角形の法線ベクトルとが供給され、前記２頂点間のベクトルの外積と前記凸多角形の法線ベクトルとの間の内積がゼロより大の場合はsign=１とし、ゼロより小の場合はsign=−１と判定して、前記隣接するすべての２頂点間で前記signがすべて同一の場合は前記交点は前記凸多角形の内部にあり、前記signに異なるものがある場合は前記交点は前記凸多角形の外部にあると判定を行なう第３の交差判定部２３と
より構成したことを特徴とする図形表示装置を提供し、
請求項２の発明は、
請求項１に記載された図形表示装置において、
前記隠面消去部は、前記交点が境界線上にあると判定された場合に限り、前記距離判定条件設定部より前記凸多角形の交点から視点までの距離に一定値を加算する指示が供給され、前記隠面消去部において、それまでに処理した凸多角形における距離とで大小の比較を行ない、より距離の短い前記凸多角形の交点を選択することを特徴とする図形表示装置を提供し、
請求項３の発明は、
同一平面上に頂点Ｐ１、Ｐ２、・・・、Ｐｎを有する凸多角形(ｎ＞２の整数)と同じ平面上に存在する視線との交点Ｑが、前記凸多角形の内部に存在するか、前記凸多角形の境界に存在するか、または前記凸多角形の外部に存在するかの判定を行なう領域内外判定を、交点距離検出部１１と、交点座標算出部１２と、交差判定部１３と、隠面消去部１４と、距離判定条件設定部１５とを有する図形表示装置に図形表示を行わせる図形表示方法において、
前記交差判定部において、
前記交点座標算出部から前記凸多角形の各頂点と前記交点とを結んで形成される各頂点ベクトルが順次供給され、隣接する２頂点間のベクトルの外積がゼロかどうかの判定を行なう第１の交差判定ステップと、
前記第１の交差判定ステップの外積がゼロであるとの出力情報と前記頂点ベクトルとが供給され、前記隣接する２頂点間の外積がゼロであるベクトルにおける内積がゼロより大の場合は前記交点は前記凸多角形の外部にあり、前記内積がゼロより小の場合は前記交点は前記凸多角形の２頂点間の境界線上にあるとの判定を行なう第２の交差判定ステップと、
前記第１の交差判定ステップの外積が前記凸多角形においてすべてゼロでないとの出力情報と前記交点座標算出ステップよりの凸多角形の法線ベクトルとが供給され、前記２頂点間のベクトルの外積と前記凸多角形の法線ベクトルとの間の内積がゼロより大の場合はsign=１とし、ゼロより小の場合はsign=−１と判定して、前記隣接するすべての２頂点間で前記signがすべて同一の場合は前記交点は前記凸多角形の内部にあり、前記signに異なるものがある場合は前記交点は前記凸多角形の外部にあるとの判定を行なう第３の交差判定ステップと
を有して図形表示を行わせるようにしたことを特徴とする図形表示方法を提供し、
請求項４の発明は、
請求項３に記載された図形表示方法において、
前記隠面消去部における隠面消去ステップは、前記交点が境界線上にあると判定された場合に限り、前記距離判定条件設定部における距離判定条件設定ステップより前記凸多角形の交点から視点までの距離に一定値を加算する指示が供給され、前記隠面消去ステップにおいて、それまでに処理した凸多角形における距離とで大小の比較を行ない、より距離の短い前記凸多角形の交点を選択することを特徴とする図形表示方法を提供するものである。
【００１９】
( 作 用 )
本発明は、図２に示すように、まず、凸多角形の頂点Ｐ1、Ｐ2、・・・、Ｐnを同一平面上に一定向き(時計回りまたは反時計回り)に定義し、この凸多角形を含む無限平面と視線Ｌが交点Ｑで交差するとき、前記交点Ｑと前記各頂点Ｐnを結ぶベクトルを順次求め、隣接する２頂点間のベクトル(Ｐ1ＱとＰ2Ｑ、Ｐ2Ｑと
Ｐ3Ｑ、・・・、ＰnＱとＰ1Ｑ)の外積及び内積を求める。
前記２頂点間ベクトルの外積は、これらの２ベクトルの位置関係によって向きが決まる、２ベクトルに垂直なベクトルを示している。
【００２０】
すなわち、図２でＰ1Ｑ×Ｐ2ＱとＰ2Ｑ×Ｐ1Ｑの向きは逆であり、Ｐ1Ｑ×
Ｐ2ＱとＰ3Ｑ×Ｐ4Ｑの向きは図２(a)では同じ向きであるが、図２(b)では逆向きとなる。
各２頂点間の外積ベクトルと、予め求めた凸多角形の法線ベクトルとの間の内積の符号を隣接する各頂点間について調べることにより、前記外積ベクトルと前記法線ベクトルの方向(内積が正なら同方向、負なら逆方向)の同一性が判る。
【００２１】
前記法線ベクトルは共通であり、前記したように外積ベクトルの向きは２頂点間ベクトルの位置関係によって異なるので、全ての組合わせで、２頂点間の外積ベクトルと法線ベクトルとの内積の符号の同一性を調べることにより、交点Ｑと該当する凸多角（四角）形の位置関係を知ることが出来る。
【００２２】
すなわち、前記２頂点間の外積ベクトルと法線ベクトルとの内積の符号が同一ならば交点Ｑは凸多角形の内部にあると判定(図２(a))する。
また、前記２頂点間の外積ベクトルと法線ベクトルとの内積の符号に異なるものがある場合は交点Ｑは凸多角形の外部にあると判定(図２(b))する。
【００２３】
一方、２頂点間ベクトルの外積がほぼ０(誤差の影響を見込んだ０に近い値)の場合は、前記法線ベクトルとの内積の符号で内外判定をすることが出来ない。
この場合には該当する２頂点を通る直線上に交点Ｑが存在しているので、前記２頂点間ベクトルの内積で判定する。
【００２４】
すなわち、２頂点間ベクトルの内積が０より大きい場合(２頂点間ベクトルの成す角＝０)は、交点Ｑはこの２頂点の外側に存在する(図２(d))ため、前記交点Ｑは凸多角形の外部にあると判定する。
【００２５】
また、２頂点間ベクトルの内積が０より小さい場合(２頂点間ベクトルの成す角＝π)は交点Ｑはこの２頂点の内側に存在する(図２(c))ため、前記交点Ｑは凸多角形の境界上にあると判定する。
【００２６】
交点Ｑが凸多角形の境界上にあると判定された時は凸多角形の内部にある場合と同様に、当該凸多角形が視線と交差すると判定して隠面消去部において、それまでに処理した凸多角形で得られた交点から視点までの距離と当該凸多角形における距離とを比較する。
【００２７】
この際に、境界上にあると判定された場合に限り、距離の差が一定範囲内の場合は先に判定した凸多角形を優先して、交差図形の更新を行なわないことにより、境界線上で判定交差図形が同一になり、２つの多角形が入り組んで見苦しくなってしまうことが解消される。
【００２８】
【発明の実施の形態】
図１に本発明の図形表示装置の交差判定・交点検出部の一実施例のブロック構成図を示す。
図１に示される本発明の交差判定・交点検出部の実施例は、交点距離検出部
１１、交点座標算出部１２、交差判定部１３、隠面消去部１４、及び 距離判定条件設定部１５より構成される。
【００２９】
まず、視線データ(視点の座標、視線ベクトル)及び、各凸多角形のデータ(頂点座標・法線ベクトル)が交点距離検出部１１に入力される。
交点距離検出部１１は凸多角形を順に取り出し、凸多角形の含まれる無限平面と視線Ｌとの交点Ｑから視点Ｒまでの距離を検出する処理を行なう。
【００３０】
なお、視線ベクトルと前記無限平面が平行な場合、及び無限平面と視線との交点が予め定めだ図形領域をはみ出すなど、有効な値でない場合は、この凸多角形は視線と交差しないと判断して、当該視線のこの凸多角形に関する以降の判定処理は行なわない。
【００３１】
つぎに、交点座標算出部１２は交点Ｑから視点Ｒまでの距離を、視点Ｒと視線ベクトルで示される直線(実際には半直線)の式に代入して交点Ｑの座標を計算し、視線データ、凸多角形のデータと共に交差判定部１３に送られる。
【００３２】
本発明の従来例と異なる部分は交差判定部１３乃至距離判定条件設定部１５である。
交差判定部１３は、頂点外積判定部２１、頂点内積判定部２２、及び法線内積判定部２３より構成されている。
【００３３】
交差判定部１３には交点座標算出部１２で計算された凸多角形と視線の交点Ｑの座標と、合わせて送られる凸多角形の頂点座標から頂点−交点間(図２のＰk−Ｑ間、k=1・・・n)のベクトル(図２の頂点Ｖ)が求められ、頂点外積判定部２１及び頂点内積判定部２２において隣接する２頂点間のベクトル(図２のＰ1ＱとＰ2Ｑ、Ｐ2ＱとＰ3Ｑ、・・・、ＰnＱとＰ1Ｑ)の外積及び内積を求める。
【００３４】
頂点外積判定部（第１の交差判定部）２１において、２頂点間のベクトルの外積がほぼ０の場合は、次に頂点内積判定部（第２の交差判定部）２２において２頂点間の外積がほぼ０であるベクトルに対して内積による判定が行なわれ、内積が０より大きい場合は、交点Ｑは凸多角形の外部にあると判定される。
内積が０より小さい場合は、交点Ｑは凸多角形の２頂点間の境界上にあると判定される。
【００３５】
一方、２頂点間のベクトルの外積が当該凸多角形についてすべてほぼ０ではない場合は、次に法線内積判定部（第３の交差判定部）２３において、２頂点間のベクトルの外積と凸多角形の法線ベクトルとの間で内積が取られる。
内積が０より大きい場合はsign=1とし、０より小さい場合はsign=‐1であると判別する。
【００３６】
以上の処理を全ての隣接する２頂点間について行ない、
(Ａ) ２頂点間のベクトルの外積がすべて０でない場合で、
(ａ) ２頂点間で前記signがすべて同一（１または−１）である場合・・・交点Ｑは凸多角形の内部にあり、
(ｂ) ２頂点間でsignに異なるものがある場合・・・交点Ｑは凸多角形の外部にあり、
(Ｂ) ２頂点間のベクトルの外積が０となるものがある場合で、
(ｃ) ２頂点間のベクトル内積が０より小の場合・・・交点Ｑは凸多角形の境界上にあり、
(ｄ) ２頂点間のベクトル内積が０より大の場合・・・交点Ｑは凸多角形の外部にある
とした区分条件によって交点Ｑの内外判定を行なう。
【００３７】
なお、１回でも交点Ｑが凸多角形の外部にあると判定した場合は、その時点で当該視線はこの凸多角形と交差しないと判断して、当該視線のこの凸多角形に関する以降の判定処理は行なわない。
【００３８】
交点Ｑが凸多角形の境界上にあると判定された時は凸多角形の内部にある場合と同様に、当該凸多角形が視線と交差するという判定を視線データ、凸多角形のデータと共に隠面消去部１４に送る。
【００３９】
この隠面消去部１４は従来例と同様に、当該多角形における交点から視点までの距離の計算を行ない、ここで得られた距離と、それまでに処理した凸多角形で得られた交点から視点までの距離とを比較することによって、視点に最も近い、すなわち距離の一番短いものを選択する。
【００４０】
ただし、従来例と異なるのは、通常の交差図形に対しては単純な大小判定で距離の比較を行なうが、交点Ｑが境界線上にあると判定された場合に限り、距離判定条件設定部1５より当該凸多角形の交点から視点までの距離に一定値を加算する指示を行ない、それとそれまでに処理した凸多角形における距離とで大小の比較を行なう。
【００４１】
これにより、距離の差が一定範囲内の場合は先に判定した前記の一定値を加算しなかった方の凸多角形が優先され、交差図形の更新を行なわないようにすることにより、これまであつた境界線上で判定交差図形が同一になり、２つの多角形が入り組んで見苦しくなってしまうことが解消される。
【００４２】
なお、以上の説明では対象とする凸多角形は同一平面上に定義された凸ｎ角形(ｎ＞２の整数)を仮定しているが、凸多角形が同一平面上にない場合は、平面を確定出来る三角形に分割して、各々の三角形について同様の処理を行なうことになる。
【００４３】
レイトレーシング法によるレンダリングでは、以上の説明のような視点から発生された視線が最も視点側にある図形との交点を求めてその交点における輝度値を求めるだけでなく、図３に示したように、視線が交差した図形の性質によって、前記交点から視線の反射光・屈折光に相当するレイを飛ばし、各交点の反射光・屈折光に相当するレイについて各々、新たに図形の交点を求めていき、新たな交点における輝度値を求め、更にその交点から反射光・屈折光に相当するレイを飛ばしていく・・・という二分木処理を繰り返し、二分木を構成するレイの各々の交点における輝度値を所定の割合で加算していってスクリーン上の各画素における輝度値を求めていく方法がある。
【００４４】
さらに、各交点における輝度値を求める際に、与えられた光源からの光線ベクトルを遮る図形があるかどうかを判定することにより、表示された図形に影付けを行なって、よりリアルなレンダリングを行なう方法もある。
そうした反射光・屈折光に相当するレイに対する図形の交差判定や、影付けの際の光源からの光線ベクトルを遮る図形に対する交差判定に対しても、本発明を適応することが出来る。
【００４５】
また、これまでの説明ではレイトレーシング法における隠面消去処理に限って説明したが、本発明の交差判定部１３における処理方法はそれに限ったものではなく、凸ｎ角形(ｎ＞２の整数)における領域内外判定手段を必要とするシステム全般に適応可能なものである。
【００４６】
【発明の効果】
本発明によると、レイトレーシング法による隠面消去における視線と凸多角形との間の交差判定などにおいて、凸多角形の頂点を一定向き(時計回りまたは反時計回り)に定義し、凸多角形が存在する平面と視線が交点で交差する場合、交点と頂点を結ぶベクトルを順次求め、隣接する２頂点間のベクトルの内積及び外積、及びその外積と凸多角形の法線ベクトルとの内積によって交点が凸多角形の内部に存在するか、境界に存在するか、外部に存在するかを判定し、交点が凸多角形の内部または境界に存在する場合は当該凸多角形が視線と交差すると判定して隠面消去部による処理を行なうが、境界に存在すると判定された場合には隠面消去処理における距離判定を変更することにより、交差判定の簡略化と、図形表示時における多角形の境界付近における問題を解消することを可能にした。
【図面の簡単な説明】
【図１】本発明の図形表示装置の交差判定・交点検出部の一実施例のブロック構成図を示す。
【図２】本発明の図形表示装置の交差判定部の判定原理を示した図である。
【図３】レイトレーシング法の原理を示した図である。
【図４】反射・屈折及び光源との影判定も考慮したレイトレーシング法の原理を示した図である。
【図５】レイトレーシングシステムのブロック構成を示した図である。
【図６】従来の交差判定・交点検出部のブロック構成の一例を示した図である。
【図７】従来の交差判定部における判定原理の一例を示した図である。
【図８】２つの凸多角形の境界に視線との交点がある場合の一例を示した図である。
【符号の説明】
１１ 交点距離検出部
１２ 交点座標算出部
１３ 交差判定部
１４ 隠面消去部
１５ 距離判定条件設定部
２１  頂点外積判定部（第１の交差判定部）
２２ 頂点内積判定部（第２の交差判定部）
２３ 法線内積判定部（第３の交差判定部）
Ｌ  視線
Ｍ  画素
Ｐ1、Ｐ2、・・・、Ｐn   凸多角形の頂点(ｎ＞２の整数)
Ｑ  交点
Ｒ  視点
Ｓ  スクリーン
【図１】
0003703073.tif 000002
【図２】
0003703073.tif 000003
【図３】
0003703073.tif 000004
【図４】
0003703073.tif 000005
【図５】
0003703073.tif 000006
【図６】
0003703073.tif 000007
【図７】
0003703073.tif 000008
【図８】
0003703073.tif 000009