(57)【特許請求の範囲】
【請求項１】
記憶装置から読み出した図形データを用いて図形のブーリアン演算処理を実行する図形処理装置において、
前記記憶装置から読み出した線分に関するデータを用いて、判定対象の線分同士の交差の有無を判定する交差判定手段と、
前記交差判定手段による交差判定で発生した演算誤差を解析して、当該演算誤差が前記交差判定を誤らせる度合を大小判定する誤差調査手段と、
前記誤差調査手段によって前記判定対象の線分同士が近接した位置にあることに起因する演算誤差が交差判定を誤らせる度合が大きいと判定されると、前記判定対象の一方の線分を規定する頂点に接続し、かつ当該線分に最も近い前記判定対象の線分以外の線分を、新たなターゲット線分として選択するターゲット線分選択手段と、
前記判定対象の一方の線分を規定する頂点のうち前記ターゲット線分に接続しない側の頂点と、前記ターゲット線分を規定する頂点のうち前記判定対象の一方の線分に接続しない側の頂点とが、前記判定対象の他方の線分で区画される同じ側の領域にあるか否かを判定する位置判定手段と、
前記誤差調査手段により演算誤差が交差判定を誤らせる度合が小さいと判定されると、前記交差判定手段の判定結果に基づいて、最終的な前記判定対象の線分同士の交差の有無を判定するとともに、前記ターゲット線分選択手段により新たなターゲット線分が選択されていれば、前記位置判定手段の判定結果に基づいて、最終的な前記判定対象の線分同士の交差の有無を判定する最終判定手段とを備えたことを特徴とする図形処理装置。
【請求項２】
交差判定手段は、
記憶装置から読み出した始点と終点で規定される２つの線分に関するデータを用い、判定対象の一方の線分からみた判定対象の他方の線分の始点と終点の位置関係を、前記判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、前記判定対象の線分同士の交差の有無を判定し、
ターゲット線分選択手段は、
前記判定対象の線分のうちの一方の線分の始点が他方の線分に近接した位置にあることで、誤差調査手段により交差判定を誤らせる度合が大きい演算誤差が発生したと判定されると、前記判定対象の一方の線分の終点を始点として接続し、かつ当該線分に最も近い前記判定対象の線分以外の線分を、新たなターゲット線分として選択し、
位置判定手段は、
前記判定対象の一方の線分を規定する始点と前記ターゲット線分の終点とが、前記判定対象の他方の線分で区画される同じ側の領域にあるか否かを判定し、
最終判定手段は、
前記位置判定手段により前記判定対象の一方の線分を規定する始点と前記ターゲット線分の終点とが、前記判定対象の他方の線分で区画される同じ側の領域にあると判定された場合、前記ターゲット線分と前記判定対象の他方の線分とが交差していれば、前記判定対象の線分同士が交差していると最終的に判定し、
前記判定対象の一方の線分を規定する始点と前記ターゲット線分の終点とが、前記判定対象の他方の線分で区画される同じ側の領域にないと判定された場合、前記ターゲット線分と前記判定対象の他方の線分とが交差していなれば、前記判定対象の線分同士が交差していると最終的に判定することを特徴とする請求項１記載の図形処理装置。
【請求項３】
交差判定手段は、
記憶装置から読み出した始点と終点で規定される２つの線分に関するデータを用い、判定対象の一方の線分からみた判定対象の他方の線分の始点と終点の位置関係を、前記判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、前記判定対象の線分同士の交差の有無を判定する第１の交差判定手段と、
前記第１の交差判定手段による交差判定で発生した演算誤差を解析して、当該演算誤差が前記交差判定を誤らせる度合を大小判定する第１の誤差調査手段と、
前記記憶装置から読み出した線分に関するデータを用いて、前記判定対象の各線分上に交点が存在するか否かを判定し、この交点有無の判定結果と前記第１の交差判定手段の交差判定結果に基づいて、前記判定対象の線分同士の交差の有無を判定する交点判定手段とを備えたことを特徴とする請求項１または請求項２記載の図形処理装置。
【請求項４】
第１の交差判定手段は、
判定対象の一方の線分からみた判定対象の他方の線分の始点と終点の位置関係を、前記判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、前記判定対象の線分同士の交差の有無を第１の交差判定として判定し、
前記第１の交差判定で発生した演算誤差が判定を誤らせる度合が小さいと第１の誤差調査手段により判定されると、
前記判定対象の他方の線分からみた前記判定対象の一方の線分の始点と終点の位置関係を、前記判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、前記判定対象の線分同士の交差の有無を第２の交差判定として判定し、
交点判定手段は、交点有無の判定結果と前記第１及び前記第２の交差判定結果に基づいて、前記判定対象の線分同士の交差の有無を判定することを特徴とする請求項３記載の図形処理装置。
【請求項５】
交差判定手段は、
記憶装置から読み出した始点と終点で規定される２つの線分に関するデータを用い、判定対象の一方の線分からみた判定対象の他方の線分の始点と終点の位置関係を、前記判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、前記判定対象の線分同士の交差の有無を判定する第１の交差判定手段と、
前記第１の交差判定手段による交差判定で発生した演算誤差を解析して、当該演算誤差が前記交差判定を誤らせる度合を大小判定する第１の誤差調査手段と、
前記記憶装置から読み出した図形に関するデータを用いて、前記判定対象の一方の線分の頂点が、前記判定対象の他方の線分を構成要素とする図形の内部にあるか外部にあるかを判定し、この頂点の内外判定の結果と前記第１の交差判定手段の交差判定結果に基づいて、前記判定対象の線分同士の交差の有無を判定する頂点内外判定手段とを備えたことを特徴とする請求項１または請求項２記載の図形処理装置。
【請求項６】
第１の交差判定手段は、
判定対象の一方の線分からみた判定対象の他方の線分の始点と終点の位置関係を、前記判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、前記判定対象の線分同士の交差の有無を第１の交差判定として判定し、
前記第１の交差判定で発生した演算誤差が判定を誤らせる度合が小さいと第１の誤差調査手段により判定されると、
前記判定対象の他方の線分からみた前記判定対象の一方の線分の始点と終点の位置関係を、前記判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、前記判定対象の線分同士の交差の有無を第２の交差判定として判定し、
頂点内外判定手段は、頂点の内外判定の結果と前記第１及び前記第２の交差判定結果に基づいて、前記判定対象の線分同士の交差の有無を判定することを特徴とする請求項５記載の図形処理装置。
【請求項７】
交差判定手段は、
記憶装置から読み出した始点と終点で規定される２つの線分に関するデータを用い、判定対象の一方の線分からみた判定対象の他方の線分の始点と終点の位置関係を、前記判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、前記判定対象の線分同士の交差の有無を判定する第１の交差判定手段と、
前記第１の交差判定手段による交差判定で発生した演算誤差を解析して、当該演算誤差が前記交差判定を誤らせる度合を大小判定する第１の誤差調査手段と、
前記記憶装置から読み出した線分に関するデータを用いて、前記判定対象の各線分上に交点が存在するか否かを判定する交点判定手段と、
前記記憶装置から読み出した図形に関するデータを用いて、前記判定対象の一方の線分の頂点が、前記判定対象の他方の線分を構成要素とする図形の内部にあるか外部にあるかを判定し、この頂点の内外判定の結果、前記交点判定手段による交点判定の結果及び前記第１の交差判定手段の交差判定結果に基づいて、前記判定対象の線分同士の交差の有無を判定する頂点内外判定手段とを備えたことを特徴とする請求項１または請求項２記載の図形処理装置。
【請求項８】
第１の交差判定手段は、
判定対象の一方の線分からみた判定対象の他方の線分の始点と終点の位置関係を、前記判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、前記判定対象の線分同士の交差の有無を第１の交差判定として判定し、
前記第１の交差判定で発生した演算誤差が判定を誤らせる度合が小さいと第１の誤差調査手段により判定されると、
前記判定対象の他方の線分からみた前記判定対象の一方の線分の始点と終点の位置関係を、前記判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、前記判定対象の線分同士の交差の有無を第２の交差判定として判定し、
交点判定手段は、交点有無の判定結果、頂点の内外判定の結果、前記第１及び前記第２の交差判定結果に基づいて、前記判定対象の線分同士の交差の有無を判定することを特徴とする請求項７記載の図形処理装置。
【請求項９】
頂点内外判定手段は、
判定対象の一方の線分を規定する各頂点が、前記判定対象の他方の線分を構成要素とする図形の内外に分かれて存在する場合、前記判定対象の線分同士が交差すると判定し、
前記判定対象の一方の線分を規定する各頂点が、前記判定対象の他方の線分を構成要素とする図形の内外の同じ側に存在する場合、前記判定対象の線分同士が交差しないと判定することを特徴とする請求項５から請求項８のうちのいずれか１項記載の図形処理装置。
【請求項１０】
請求項１から請求項９のうちのいずれか１項記載の図形処理装置としてコンピュータを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、画像情報機器等に適用される図形処理装置に係り、特に図形のブーリアン演算処理を実行する図形処理装置及びこの装置としてコンピュータを機能させるプログラムに関するものである。
【背景技術】
【０００２】
Ｍａｙａ（登録商標：以下、記載省略）等に代表されるモデリングソフトウエアの多くは、モデリングに使用するブーリアン演算処理機能が搭載されている。Ｍａｙａによるブーリアン演算処理は、非特許文献１に記載されており、例えば図１２に示すように、図形Ａ及び図形Ｂからブーリアン演算の減算処理で所望の図形を切り出して図形Ｃにすることができる。また、ブーリアン演算を利用して複雑な３次元物体や３次元シーンをある視点から見える部分の多角形形状を抽出する処理を行う場合がある。
【０００３】
例えば、図１３（ａ）に示すように高さの異なる直方体と三角柱があり、視点を右横に設定してこの位置から見える部分の多角形形状の抽出を行う処理がある。この場合、視点から見える多角形を２次元の平面に投影した後、視点から見える面の全てにおいて自分よりも視点に近い面で隠されている部分があるか否かを調べ、隠される部分がある場合にはブーリアン演算処理により隠される部分を取り除く。このようにして視点から見える部分の多角形を、図１３（ｂ）に示すような黒い塗りつぶし部分の形状として切り出すことができる。
【０００４】
【非特許文献１】P. Harovas, J. Kundert-Gibbs, P. Lee,“Mastering Maya Complete 2”, Sybex Inc, 2000/1/4, p.225
【発明の開示】
【発明が解決しようとする課題】
【０００５】
例えば、図１２に示したような従来の一般的なブーリアン演算処理では、面と面が交わる部分が数箇所程度である場合が多く、この場合一つのポリゴンに対して数回のブーリアン演算で図形処理が完了する。しかしながら、図１３に示したような視点から見える部分を切り出す処理の場合、視点とターゲット面との間にあるオブジェクトの全てにブーリアン減算を施す必要があり、一つの面に対する処理が多くなる。
【０００６】
このように、図形と図形のブーリアンによる減算数が非常に多くなると、図形と図形の交わり具合も非常に細かくなる。このため、図形と図形が微小量で交差したり、微少量で離れている状態が小領域内で何重にも発生する場合がある。
【０００７】
ブーリアン演算処理では、図形と図形の交差判定や内包関係に基づいて、図形と図形がどのように交わっているかを調べる。図形の交差判定や内包関係は、図形中の辺の交差の判定結果を集めたものとして扱うことができるが、辺同士が非常に近い位置で交わったり接近していると、辺の交差判定を演算する際の浮動小数点演算の桁落ちが発生し易い。
【０００８】
演算誤差によって幾何学的に不可能な状況が図形に発生した状態で、ブーリアン演算処理を進めると、処理が無限ループになったり、正しい演算結果が得られない。
例えば、図１４に示すように、辺Ｂに対して辺Ａ１と辺Ａ２が微少量で交わっている場合、辺Ａ２と辺Ｂが交わると判定されても、演算誤差によって辺Ａ１と辺Ｂが交わらないと判定されることがある。この場合、頂点ａ２が辺Ｂで区画されたいずれの領域にもあるような幾何学的に不可能な状況になり、正常にブーリアン演算処理を実行することができない。
【０００９】
この発明は、上記のような課題を解決するためになされたもので、図形の交差判定や内包関係の判定における幾何学的に不可能な状況の発生を回避することにより、正常にブーリアン演算処理を実行できる図形処理装置及びこの装置としてコンピュータを機能させるプログラムを得ることを目的とする。
【課題を解決するための手段】
【００１０】
この発明に係る図形処理装置は、記憶装置から読み出した図形データを用いて図形のブーリアン演算処理を実行する図形処理装置において、前記記憶装置から読み出した線分に関するデータを用いて、判定対象の線分同士の交差の有無を判定する交差判定手段と、前記交差判定手段による交差判定で発生した演算誤差を解析して、当該演算誤差が前記交差判定を誤らせる度合を大小判定する誤差調査手段と、前記誤差調査手段によって前記判定対象の線分同士が近接した位置にあることに起因する演算誤差が交差判定を誤らせる度合が大きいと判定されると、前記判定対象の一方の線分を規定する頂点に接続し、かつ当該線分に最も近い前記判定対象の線分以外の線分を、新たなターゲット線分として選択するターゲット線分選択手段と、前記判定対象の一方の線分を規定する頂点のうち前記ターゲット線分に接続しない側の頂点と、前記ターゲット線分を規定する頂点のうち前記判定対象の一方の線分に接続しない側の頂点とが、前記判定対象の他方の線分で区画される同じ側の領域にあるか否かを判定する位置判定手段と、前記誤差調査手段により演算誤差が交差判定を誤らせる度合が小さいと判定されると、前記交差判定手段の判定結果に基づいて、最終的な前記判定対象の線分同士の交差の有無を判定するとともに、前記ターゲット線分選択手段により新たなターゲット線分が選択されていれば、前記位置判定手段の判定結果に基づいて、最終的な前記判定対象の線分同士の交差の有無を判定する最終判定手段とを備えるものである。
【発明の効果】
【００１１】
この発明によれば、判定対象の線分同士が近接した位置にあることに起因する演算誤差が交差判定を誤らせる度合が大きいと判定されると、判定対象の一方の線分を規定する頂点に接続し、かつ当該線分に最も近い判定対象の線分以外の線分を、新たなターゲット線分として選択するとともに、判定対象の一方の線分を規定する頂点のうちターゲット線分に接続しない側の頂点と、ターゲット線分を規定する頂点のうち判定対象の一方の線分に接続しない側の頂点とが、判定対象の他方の線分で区画される同じ側の領域にあるか否かを判定し、上記同じ側の領域にあるか否かの判定結果に基づいて、最終的な判定対象の線分同士の交差の有無を判定する。このように交差判定対象の線分同士が微少量で交差する若しくは近接している場合であっても、交差判定対象の線分以外の近接する線分を新たなターゲット線分として交差の有無を判定することにより、交差判定対象の線分から離れた誤差の少ない箇所を探索して交差判定を行うことができる。これにより、図形の交差判定や内包関係の判定における幾何学的に不可能な状況の発生を回避でき、正常にブーリアン演算処理を実行することができるという効果がある。
【発明を実施するための最良の形態】
【００１２】
実施の形態１．
図１は、この発明の図形処理装置を実現するための装置構成を概略的に示す図である。この発明による図形処理装置は、図１に示すような、演算プロセッサ２及びこれにバス４を介して接続するメモリ３を有するコンピュータで具現化できる。また、メモリ３には、本発明の趣旨に従う図形処理プログラムと、ブーリアン演算に必要な図形データ及びブーリアン演算後の図形データが格納される。
【００１３】
上記の構成において、演算プロセッサ２が、メモリ３に格納された本発明の趣旨に従う図形処理プログラムを読み込んで実行することにより、当該コンピュータ上でソフトウエアとハードウエアとが協働した具体的な手段として、図形処理装置１の各構成（図２を用いて後述する）を実現することができる。
【００１４】
なお、コンピュータ自体の構成及びその基本的な機能については、当業者が当該技術分野の技術常識に基づいて容易に認識できるものであり、本発明の本質に直接関わるものでないので詳細な記載を省略する。
【００１５】
図２は、この発明の実施の形態１による図形処理装置の構成を概念的に示すブロック図であり、図１中の演算プロセッサ２でメモリ３から読み出した図形処理用プログラムを実行することで具現化される図形処理装置１の構成を記載したものである。図２において、実施の形態１による図形処理装置１は、交差判定手段５、誤差調査手段６、座標位置判定手段７、最終判定手段８、及びターゲット線分選択手段９を備える。
【００１６】
交差判定手段５は、メモリ３から読み出された図形データの辺情報を使用して図形の交差判定を行うにあたり、交差判定の対象となる２つの線分の交差状態を判定する。誤差調査手段６は、交差判定手段５の交差判定における演算誤差の当該判定を誤らせる度合を調査する。演算誤差には、浮動小数点演算における桁落ちや情報落ち、丸め誤差がある。
【００１７】
座標位置判定手段７は、誤差調査手段６による誤差の調査結果に基づいて、２つの線分の交差状態を示す最終的な判定結果として交差判定手段５の判定結果を選択したり、ターゲット線分選択手段９で選択されたターゲット線分の終点とこのターゲット線分に接続する交差判定対象の一方の線分の始点とが、交差判定対象の他方の線分で区画されるいずれの領域にあるかを判定する。
【００１８】
最終判定手段８は、交差判定手段５の判定結果と座標位置判定手段７の結果に基づき、交差判定対象の線分の交差判定を実行する。ターゲット線分選択手段９は、誤差調査手段６による誤差の調査結果に基づいて、交差判定対象の線分のうち、誤差の発生原因となった一方の線分に近接（非常に近い状態）して存在する他方の線分の頂点に接続される線分を、新たなターゲット線分として選択する。
【００１９】
次に動作について説明する。
図３は、図２中の図形処理装置によるブーリアン演算処理の流れを示すフローチャートであり、この図に沿って動作の詳細を説明する。なお、図３では、図４に示す多角形Ａと多角形Ｂのブーリアン演算において、多角形Ａの頂点Ａ１と頂点Ａ２からなる線分Ａと、多角形Ｂの頂点Ｂ１と頂点Ｂ２からなる線分Ｂと、の交差を判定する場合を例に挙げている。
【００２０】
先ず、交差判定手段５は、図４に示す多角形Ａ，Ｂに関する図形データの辺情報をメモリ３から読み出し、交差判定の対象となる線分Ａ，Ｂの交差状態を判定する（ステップＳＴ１）。この交差判定は、例えば外積を用いて判定することができる。
【００２１】
具体的には、交差判定手段５が、頂点Ａ１と頂点Ａ２を結ぶベクトルＡ１Ａ２と、頂点Ａ１と頂点Ｂ１を結ぶベクトルＡ１Ｂ１との外積のＺ成分の符号を求め、頂点Ａ１と頂点Ｂ２を結ぶベクトルＡ１Ｂ２とベクトルＡ１Ａ２との外積のＺ成分の符号を求める。これら２つの符号が異なる場合は、線分Ａと線分Ｂが交わる可能性があり、符号が同じ場合は交わらないと判断できる。なお、ベクトルＡ（Ａｘ，Ａｙ，Ａｚ）とベクトルＢ（Ｂｘ，Ｂｙ，Ｂｚ）との外積Ａ×ＢのＺ成分は、Ａｘ×Ｂｙ−Ａｙ×Ｂｘで求まる。
【００２２】
上記と同様に、頂点Ｂ１と頂点Ｂ２を結ぶベクトルＢ１Ｂ２と、頂点Ｂ１と頂点Ａ１を結ぶベクトルＢ１Ａ１との外積のＺ成分の符号を求め、頂点Ｂ１と頂点Ａ２を結ぶベクトルＢ１Ａ２とベクトルＢ１Ｂ２との外積のＺ成分の符号を求めて交差判定を行う。
【００２３】
次に、誤差調査手段６が、交差判定対象の線分に対応するベクトルの外積のＺ成分の算出結果を交差判定手段５から入力し、交差判定手段５の交差判定における演算誤差の発生を調査する（ステップＳＴ２）。例えば、誤差調査手段６が、Ａ×Ｂ−Ｃ×Ｄで得られる外積演算のＺ成分の符号を判定する場合、Ａ×ＢとＣ×Ｄの演算結果に発生する丸め誤差や、Ａ×Ｂ−Ｃ×Ｄの演算における桁落ち、情報落ちの誤差を調べる。
【００２４】
Ａ×Ｂ−Ｃ×Ｄの演算における情報落ちは、Ａ×ＢとＣ×Ｄの一方が非常に大きな値で他方が非常に小さな値である場合に生じる。また、桁落ちは、Ａ×ＢとＣ×Ｄが非常に近い値である場合に発生する。
【００２５】
続いて、誤差調査手段６は、交差判定手段５の交差判定に演算誤差を発見すると、上述のようにしてＡ×Ｂの丸め誤差の大きさとＣ×Ｄの丸め誤差の大きさを求めて、Ａ×ＢとＣ×Ｄの符号と絶対値の大きさを調べ、Ａ×Ｂ−Ｃ×Ｄの符号判定を間違う度合を大小判定する（ステップＳＴ３）。
【００２６】
例えば、Ａ×Ｂ−Ｃ×Ｄで得られる外積演算のＺ成分の符号を判定するにあたり、浮動小数演算上の演算誤差で当該判定を誤る可能性を大小判定する場合、Ａ×ＢとＣ×Ｄの丸め誤差と丸め誤差に関する所定の閾値を比較して丸め誤差がどの程度発生しているかを調べるとともに、外積Ａ×Ｂと外積Ｃ×Ｄの符号と、外積Ａ×Ｂと外積Ｃ×Ｄの絶対値の差を算出する。
【００２７】
ここで、外積Ａ×Ｂと外積Ｃ×Ｄの符号とが異なる場合や外積Ａ×Ｂと外積Ｃ×Ｄの絶対値の差が所定の閾値を超えて大きい場合であれば、Ｚ成分Ａ×Ｂ−Ｃ×Ｄの符号判定に関し、外積Ａ×Ｂと外積Ｃ×Ｄの丸め誤差による影響はないため、当該丸め誤差によってＺ成分Ａ×Ｂ−Ｃ×Ｄの符号判定を誤る度合は小さいと判定する。
【００２８】
一方、外積Ａ×Ｂと外積Ｃ×Ｄの符号とが同じ場合、外積Ａ×Ｂと外積Ｃ×Ｄが非常に近い値（絶対値の差が所定の閾値未満で小さい場合）であり、かつ、外積Ａ×Ｂと外積Ｃ×Ｄの丸め誤差が所定の閾値を超えて大きい場合、当該丸め誤差によってＺ成分Ａ×Ｂ−Ｃ×Ｄの符号判定を誤る度合は大きいと判定する。
【００２９】
ステップＳＴ３において、演算誤差が判定誤りに与える度合が大きいと判定すると、誤差調査手段６は、交差判定（Ｚ成分の符号判定）を誤らせる原因となった演算誤差が発生しているベクトル（以下、ベクトルＯと称す）に関する情報を、座標位置判定手段７へ出力する。座標位置判定手段７は、ベクトルＯに関する情報を受けると、ターゲット線分選択手段９へ出力する。
【００３０】
ターゲット線分選択手段９では、演算誤差の発生しているベクトルＯを規定する頂点（誤差原因の頂点）に接続する隣接ベクトルと、交差判定対象の線分の一方に対応するベクトルとを、交差判定すべきベクトルＮ１及びベクトルＮ２として選択する（ステップＳＴ４）。図４の場合、演算誤差は、例えば頂点Ａ２（交差判定対象の線分Ａを規定する頂点）が線分Ｂ（線分Ｂ１Ｂ２）に非常に近い場合に発生する。
【００３１】
ステップＳＴ３で当該誤差の具合が交差判定を誤らせる大きさであると判定されると（当該演算誤差が判定誤りに与える度合が大きい）、ターゲット線分選択手段９は、頂点Ａ２との位置関係で演算誤差の原因となった線分Ｂ（ベクトルＢ１Ｂ２に対応）に非常に近くに存在する、交差判定対象の他方の線分である線分Ａ（ベクトルＡ１Ａ２に対応）を規定する頂点Ａ２（演算誤差の原因となる頂点）に接続される線分を、新たな交差判定ターゲットの線分として選択する。
【００３２】
つまり、判定対象の線分同士が近接した位置にあることで、誤差調査手段６により交差判定を誤らせる度合が大きい演算誤差が発生したと判定されると、図４に示すように、交差判定対象の一方の線分Ａを規定する頂点Ａ２に接続し、かつ当該線分Ａに最も近い交差判定対象の線分Ａ，Ｂ以外の線分である、頂点Ａ２と頂点Ａ３を結ぶ線分（ベクトルＡ２Ａ３に対応）が、交差判定すべきベクトルＮ１として新たに選択される。また、交差判定対象の線分の一方に対応する線分Ａ１Ａ２（ベクトルＡ１Ａ２に対応）も、交差判定すべきベクトルＮ２として選択される。
【００３３】
ターゲット線分選択手段９は、新たな線分を選択すると、これに対応するベクトルの情報をメモリ３から読み出して交差判定手段５へ出力する。これにより、新たな交差判定対象のベクトルに対して、ステップＳＴ１からの処理が繰り返される。
【００３４】
一方、ステップＳＴ３において、演算誤差が判定誤りに与える度合が大きくないと判定すると、誤差調査手段６は、その旨を座標位置判定手段７へ通知する。座標位置判定手段７は、当該通知を受けると、ステップＳＴ４でターゲット線分選択手段９が既に新たなターゲット線分を選択しているか否かを判定する（ステップＳＴ５）。
【００３５】
ここで、ステップＳＴ４の処理が既に実行されていなければ、座標位置判定手段７は、ステップＳＴ１において交差判定手段５が判定した結果を最終判定手段８へ出力する。これにより、最終判定手段８は、座標位置判定手段７から入力した交差判定結果を用いて、最終的な交差判定を行う。
【００３６】
また、ステップＳＴ４の処理が既に実行されている場合、座標位置判定手段７は、ターゲット線分選択手段９で選択されたターゲット線分（ベクトルＮ１に対応）の終点と、このターゲット線分に接続する交差判定対象の一方の線分（ベクトルＮ２に対応）の始点とが、交差判定対象の他方の線分（ベクトルＰに対応）で区画されるいずれの領域にあるかを算出する（ステップＳＴ６）。
【００３７】
図４では、ターゲット線分選択手段９で選択された新たな線分Ａ２Ａ３（ベクトルＮ１に対応）の終点である頂点Ａ３と、この線分Ａ２Ａ３に接続する交差判定対象の一方の線分Ａ１Ａ２（ベクトルＮ２に対応）の始点である頂点Ａ１とが、交差判定対象の他方の線分Ｂ１Ｂ２（ベクトルＰに対応）で区画されるいずれ側の領域にあるかが算出される。
【００３８】
ベクトルＮ１の終点とベクトルＮ２の始点とがベクトルＰに対してどの位置にあるかを算出すると、座標位置判定手段７は、ベクトルＮ１の終点とベクトルＮ２の始点とが、ベクトルＰで区画される同じ側の領域にあるか否かを判定する（ステップＳＴ７）。このとき、ベクトルＮ１の終点（頂点Ａ３）とベクトルＮ２の始点（頂点Ａ１）とがベクトルＰで区画される同じ側の領域にあると判定されると、座標位置判定手段７は、交差判定手段５により得られた演算誤差の小さい交差判定結果を最終判定手段８へ出力する。
【００３９】
最終判定手段８は、ステップＳＴ１で得られた、演算誤差が発生しているが、この演算誤差が交差判定誤りに与える度合が小さい交差判定結果（以下、演算誤差の小さい交差判定結果と称す）を用いて、線分Ａ２Ａ３（ベクトルＮ１に対応）と交差判定対象の他方の線分（ベクトルＰに対応）とが交差するか否かを判定する（ステップＳＴ８）。
【００４０】
ここで、ベクトルＮ１とベクトルＰが交差する場合、最終判定手段８は、線分Ａ（線分Ａ１Ａ２）と線分Ｂ（線分Ｂ１Ｂ２）が交差すると最終的に判定する。また、ベクトルＮ１とベクトルＰが交差しなければ、線分Ａ，Ｂが交差しないと最終的に判定する。
【００４１】
一方、ステップＳＴ７において、ベクトルＮ１の終点（頂点Ａ３）とベクトルＮ２の始点（頂点Ａ１）とがベクトルＰで区画される同じ側の領域にないと判定されると、座標位置判定手段７は、交差判定手段５により得られた演算誤差の小さい交差判定結果を最終判定手段８へ出力する。
【００４２】
最終判定手段８は、演算誤差の小さい交差判定結果を用いて、ターゲット線分選択手段９で選択された線分Ａ２Ａ３（ベクトルＮ１に対応）と、交差判定対象の他方の線分（ベクトルＰに対応）とが交差するか否かを判定する（ステップＳＴ９）。
【００４３】
ここで、ベクトルＮ１とベクトルＰが交差する場合、最終判定手段８は、線分Ａ（線分Ａ１Ａ２）と線分Ｂ（線分Ｂ１Ｂ２）とが交差しないと最終的に判定する。また、ベクトルＮ１とベクトルＰが交差しなければ、線分Ａ，Ｂが交差すると最終的に判定する。
【００４４】
以上のように、この実施の形態１によれば、判定対象の線分同士が近接した位置にあることに起因する演算誤差が交差判定を誤らせる度合が大きいと判定されると、判定対象の一方の線分を規定する頂点に接続し、かつ当該線分に最も近い判定対象の線分以外の線分を、新たなターゲット線分として選択するとともに、判定対象の一方の線分を規定する頂点のうちターゲット線分に接続しない側の頂点と、ターゲット線分を規定する頂点のうち判定対象の一方の線分に接続しない側の頂点とが、判定対象の他方の線分で区画される同じ側の領域にあるか否かを判定し、上記同じ側の領域にあるか否かの判定結果に基づいて、最終的な判定対象の線分同士の交差の有無を判定する。
特に、交差判定手段５が、メモリ３から読み出した始点と終点で規定される２つの線分に関するデータを用い、判定対象の一方の線分Ａからみた判定対象の他方の線分Ｂの始点と終点の位置関係を、判定対象の線分Ａ，Ｂに対応するベクトルの外積演算で特定した結果に基づいて、判定対象の線分同士の交差の有無を判定し、ターゲット線分選択手段９が、判定対象の線分のうちの一方の線分Ａの始点が他方の線分Ｂに近接した位置にあることで、誤差調査手段６により交差判定を誤らせる度合が大きい演算誤差が発生したと判定されると、判定対象の一方の線分Ａの終点Ａ２を始点として接続し、かつ当該線分に最も近い判定対象の線分Ａ，Ｂ以外の線分Ａ２Ａ３を、新たなターゲット線分として選択し、座標位置判定手段７が、判定対象の一方の線分Ａを規定する始点Ａ１とターゲット線分の終点Ａ３とが、判定対象の他方の線分Ｂで区画される同じ側の領域にあるか否かを判定し、最終判定手段８が、座標位置判定手段７により判定対象の一方の線分Ａを規定する始点Ａ１とターゲット線分の終点Ａ３とが、判定対象の他方の線分Ｂで区画される同じ側の領域にあると判定された場合、新たなターゲット線分と判定対象の他方の線分Ｂとが交差していれば、判定対象の線分同士が交差していると最終的に判定し、判定対象の一方の線分Ａを規定する始点Ａ１と新たなターゲット線分の終点Ａ３とが、判定対象の他方の線分Ｂで区画される同じ側の領域にないと判定された場合、ターゲット線分と判定対象の他方の線分Ｂとが交差していなれば、判定対象の線分同士が交差していると最終的に判定する。
このように２つの線分が微少量で交差する、若しくは近接している場合であっても、交差判定対象の線分のうち、誤差の発生原因となった一方の線分に近接（非常に近い状態）して存在する他方の線分の頂点に接続される線分を新たなターゲット線分とし、この新たなターゲット線分の頂点と交差判定対象の線分の頂点との関係で交差の有無を判定することにより、交差判定対象の線分から離れた上記頂点のような誤差の少ない箇所を探索して交差判定を行うことができ、ブーリアン演算処理を正常に行うことが可能である。
【００４５】
実施の形態２．
この実施の形態２による図形処理装置は、上記実施の形態１の図２で示した構成と基本的に同一であるが、交差判定手段が交差判定にあたり、交点判定を行う構成を有する。
図５は、この発明の実施の形態２による交差判定手段の構成を概念的に示すブロック図であり、例えば図１中の演算プロセッサ２でメモリ３から読み出した図形処理用プログラムを実行することで具現化される構成を記載したものである。図５において、実施の形態２による交差判定手段５は、交差判定手段５ａ、誤差調査手段６ａ、及び交点判定手段１０を備える。
【００４６】
交差判定手段（第１の交差判定手段）５ａは、上記実施の形態１で示した図１のメモリ３から読み出された図形データの辺情報を使用して図形の交差判定を行うにあたり、交差判定の対象となる２つの線分の交差状態を判定する。誤差調査手段（第１の誤差調査手段）６ａは、交差判定手段５ａの交差判定における演算誤差の具合を調査する。演算誤差には、浮動小数点演算における桁落ちや情報落ち、丸め誤差がある。交点判定手段１０は、誤差調査手段６ａの調査結果に応じて、交差判定手段５ａによる交差判定対象の２つの線分の交点が双方の線分上に存在するか否かを判定する。
【００４７】
次に動作について説明する。
図６は、図５中の交差判定手段によるブーリアン演算処理の流れを示すフローチャートであり、上記実施の形態１で説明した図３のステップＳＴ１の処理を詳細に説明するものである。図６においても、上記実施の形態１の図４に示す多角形Ａと多角形Ｂのブーリアン演算において多角形Ａの頂点Ａ１と頂点Ａ２からなる線分Ａと、多角形Ｂの頂点Ｂ１と頂点Ｂ２からなる線分Ｂと、の交差を判定する場合を例に挙げている。
【００４８】
先ず、交差判定手段５ａは、図４に示す多角形Ａ，Ｂに関する図形データの辺情報をメモリ３から読み出し、交差判定の対象となる線分Ａ，Ｂの交差状態を判定する（ステップＳＴ１ａ）。ここでは、ベクトルＡ１Ａ２に対する頂点Ｂ１，Ｂ２の位置関係により線分Ａ，Ｂの交差の有無を判定する。この交差判定は、例えば外積を用いて判定することができる。なお、ベクトルＡ（Ａｘ，Ａｙ，Ａｚ）と、ベクトルＢ（Ｂｘ，Ｂｙ，Ｂｚ）との外積Ａ×ＢのＺ成分は、Ａｘ×Ｂｙ−Ａｙ×Ｂｘで求まる。
【００４９】
具体的には、交差判定手段５ａが、頂点Ａ１と頂点Ａ２を結ぶベクトルＡ１Ａ２と、頂点Ａ１と頂点Ｂ１を結ぶベクトルＡ１Ｂ１と、の外積の符号を求め、頂点Ａ１と頂点Ｂ２を結ぶベクトルＡ１Ｂ２とベクトルＡ１Ａ２との外積の符号を求める。これら２つの符号が異なる場合は、線分Ａと線分Ｂが交わる可能性があり、符号が同じ場合は交わらないと判断できる。
【００５０】
次に、誤差調査手段６ａが、交差判定対象の線分に対応するベクトルの外積の算出結果を交差判定手段５ａから入力し、交差判定手段５ａの交差判定における演算誤差の発生具合を調査する。例えば、誤差調査手段６ａが、交差判定手段５ａによる交差判定におけるＡ×ＢとＣ×Ｄの演算結果に発生する丸め誤差や、Ａ×Ｂ−Ｃ×Ｄの演算における桁落ち、情報落ちの誤差を調べる。
【００５１】
Ａ×Ｂ−Ｃ×Ｄの演算における情報落ちは、Ａ×ＢとＣ×Ｄの一方が非常に大きな値で他方が非常に小さな値である場合に生じる。また、桁落ちは、Ａ×ＢとＣ×Ｄが非常に近い値である場合に発生する。
【００５２】
続いて、誤差調査手段６ａは、交差判定手段５ａの交差判定に演算誤差を発見すると、上述のようにしてＡ×Ｂの丸め誤差の大きさとＣ×Ｄの丸め誤差の大きさを求めて、Ａ×ＢとＣ×Ｄの符号と絶対値の大きさを調べ、Ａ×Ｂ−Ｃ×Ｄの符号判定を間違う度合を大小判定する（ステップＳＴ２ａ）。
【００５３】
例えば、Ａ×Ｂ−Ｃ×Ｄで得られる外積演算のＺ成分の符号を判定するにあたり、浮動小数演算上の演算誤差で当該判定を誤る可能性を大小判定する場合、Ａ×ＢとＣ×Ｄの丸め誤差と丸め誤差に関する所定の閾値を比較して丸め誤差がどの程度発生しているかを調べるとともに、外積Ａ×Ｂと外積Ｃ×Ｄの符号と、外積Ａ×Ｂと外積Ｃ×Ｄの絶対値の差を算出する。
【００５４】
ここで、外積Ａ×Ｂと外積Ｃ×Ｄの符号とが異なる場合や外積Ａ×Ｂと外積Ｃ×Ｄの絶対値の差が所定の閾値を超えて大きい場合であれば、Ｚ成分Ａ×Ｂ−Ｃ×Ｄの符号判定に関し、外積Ａ×Ｂと外積Ｃ×Ｄの丸め誤差による影響はないため、当該丸め誤差によってＺ成分Ａ×Ｂ−Ｃ×Ｄの符号判定を誤る度合は小さいと判定する。
【００５５】
一方、外積Ａ×Ｂと外積Ｃ×Ｄの符号とが同じ場合、外積Ａ×Ｂと外積Ｃ×Ｄが非常に近い値（絶対値の差が所定の閾値未満で小さい場合）であって、かつ、外積Ａ×Ｂと外積Ｃ×Ｄの丸め誤差が所定の閾値を超えて大きい場合、当該丸め誤差によってＺ成分Ａ×Ｂ−Ｃ×Ｄの符号判定を誤る度合は大きいと判定する。
【００５６】
ステップＳＴ２ａにおいて当該誤差の具合が交差判定を誤らせる大きさではないと判定すると（当該演算誤差が判定誤りに与える度合が小さい）、誤差調査手段６ａは、演算誤差が発生しているが、この演算誤差が交差判定誤りに与える度合が小さい交差判定結果（以下、演算誤差の小さい交差判定結果と称す）を用いて、交差判定対象の一方の線分Ａ（ベクトルＡ１Ａ２に対応）と、交差判定対象の他方の線分Ｂ（ベクトルＢ１Ｂ２に対応に対応）と、が交差するか否かを判定する（ステップＳＴ３ａ）。このとき、線分Ａと線分Ｂとが交差しないと判定された場合、誤差調査手段６ａは、線分Ａと線分Ｂとが交差しないと最終的に判定する。つまり、交差判定手段５ａによる判定が正しいと判断する。
【００５７】
また、線分Ａと線分Ｂが交差すると判定した場合、誤差調査手段６ａは、演算誤差の小さい交差判定結果で線分Ａ，Ｂが交差するとの結果が得られた旨を交差判定手段５ａへ通知する。交差判定手段５ａでは、当該通知を受けると、ステップＳＴ１ａで交差判定した線分について始点と終点との関係を入れ替えて同様の交差判定を行う（ステップＳＴ４ａ）。
【００５８】
図４の例では、ベクトルＢ１Ｂ２に対する頂点Ａ１，Ａ２の位置関係により線分Ａ，Ｂの交差の有無を判定する。つまり、頂点Ｂ１と頂点Ｂ２を結ぶベクトルＢ１Ｂ２（線分Ｂに対応）と、頂点Ｂ１と頂点Ａ１を結ぶベクトルＢ１Ａ１との外積の符号を求め、頂点Ｂ１と頂点Ａ２を結ぶベクトルＢ１Ａ２とベクトルＢ１Ｂ２との外積の符号を求めて交差判定を行う。
【００５９】
続いて、誤差調査手段６ａが、上記ベクトルの外積の算出結果を交差判定手段５ａから入力し、交差判定手段５ａの交差判定における演算誤差の発生具合を調査する。ここで、誤差調査手段６ａは、交差判定手段５ａの交差判定に演算誤差を発見すると、上述のようにして演算誤差が判定誤りに与える度合を大小判定する（ステップＳＴ５ａ）。
【００６０】
このとき、演算誤差が判定誤りに与える度合が大きくないと判定すると、誤差調査手段６ａは、交差判定手段５ａによる演算誤差の小さい交差判定結果を用いて、線分Ｂ１Ｂ２と線分Ｂ１Ａ２とが交差するか否かを判定する（ステップＳＴ６ａ）。ここで、線分Ｂ１Ｂ２と線分Ｂ１Ａ２とが交差しないと判定された場合、誤差調査手段６ａは、線分Ａと線分Ｂとが交差しないと最終的に判定する。また、線分Ｂ１Ｂ２と線分Ｂ１Ａ２とが交差すると判定された場合、誤差調査手段６ａは、線分Ａと線分Ｂとが交差すると最終的に判定する。
【００６１】
一方、ステップＳＴ２ａにおいて、演算誤差が判定誤りに与える度合が大きいと判定すると、誤差調査手段６ａは、その旨を交差判定手段５ａへ通知する。交差判定手段５ａでは、当該通知を受けると、頂点Ｂ１と頂点Ｂ２を結ぶベクトルＢ１Ｂ２（線分Ｂに対応）と、頂点Ｂ１と頂点Ａ１を結ぶベクトルＢ１Ａ１との外積の符号を求め、頂点Ｂ１と頂点Ａ２を結ぶベクトルＢ１Ａ２とベクトルＢ１Ｂ２との外積の符号を求めて交差判定を行う（ステップＳＴ７ａ）。
【００６２】
ステップＳＴ５ａで演算誤差が判定誤りに与える度合が大きいと判定されるか、若しくは、ステップＳＴ７ａで交差判定手段５ａによる交差判定がなされると、交点判定手段１０は、誤差調査手段６ａを介して交差判定手段５ａから交差判定の結果を入力するとともに、線分Ａ（ベクトルＡ１Ａ２に対応）と線分Ｂ（ベクトルＢ１Ｂ２に対応）との交点の座標を算出して、この交点が双方の線分Ａ，Ｂ上に存在するか否かを判定する（ステップＳＴ８ａ）。
【００６３】
また、交差判定手段５ａの交差判定で外積関数のＺ成分を求める関数をｃｒｏｓｓとした場合、交点判定手段１０が、誤差調査手段６ａを介して、交差判定手段５ａによって算出された、２つの外積のＺ成分のｃｒｏｓｓ（Ａ１Ａ２，Ａ１Ｂ１）、ｃｒｏｓｓ（Ａ１Ａ２，Ａ１Ｂ２）を入力し、絶対値の算出にａｂｓ関数を用いて下記式から交点の有無を判定するように構成してもよい。この場合、下記式の関係に頂点Ａ１，Ａ２，Ｂ１，Ｂ２がある場合に、線分Ａ，Ｂ上に交点が存在すると判定する。
０．０≦ａｂｓ（ｃｒｏｓｓ（Ａ１Ａ２，Ａ１Ｂ１））／（ａｂｓ（ｃｒｏｓｓ（Ａ１Ａ２，Ａ１Ｂ１））＋ａｂｓ（ｃｒｏｓｓ（Ａ１Ａ２，Ａ１Ｂ２）））≦１．０
【００６４】
上述の交点判定の結果、ステップＳＴ１ａでの交差判定結果、及びステップＳＴ７ａでの交差判定の結果に基づいて、交点判定手段１０は、線分Ａ（ベクトルＡ１Ａ２に対応）と線分Ｂ（ベクトルＢ１Ｂ２に対応）とが交差するか否かを判定する（ステップＳＴ９ａ）。
【００６５】
例えば、交点判定の結果及び上記交差判定の結果において線分Ａと線分Ｂが交差するとの判定結果が多い場合、交点判定手段１０は、線分Ａと線分Ｂが交差すると判定し、実施の形態２による交差判定手段５の最終判定結果とする。一方、線分Ａと線分Ｂが交差するとの判定結果が少なければ、線分Ａと線分Ｂが交差しないと判定し、実施の形態２による交差判定手段５の最終判定結果とする。
【００６６】
上述のようにして得られた交差判定結果は、実施の形態２による交差判定手段５から、図２で示した誤差調査手段６へ出力される。この後の処理は、上記実施の形態１で説明したものと同様である（図３におけるステップＳＴ２以降の処理参照）。
【００６７】
以上のように、この実施の形態２によれば、交差判定手段５が、メモリ３から読み出した始点と終点で規定される２つの線分に関するデータを用い、判定対象の一方の線分Ａからみた判定対象の他方の線分Ｂの始点と終点の位置関係を、判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、判定対象の線分同士の交差の有無を判定する交差判定手段５ａと、交差判定手段５ａによる交差判定で発生した演算誤差を解析して、当該演算誤差が交差判定を誤らせる度合を大小判定する第１の誤差調査手段と、メモリ３から読み出した線分に関するデータを用いて、判定対象の各線分上に交点が存在するか否かを判定し、この交点有無の判定結果と交差判定手段５ａの交差判定結果に基づいて、判定対象の線分同士の交差の有無を判定する交点判定手段１０とを備える。このように構成することにより、交差判定対象の線分同士の交点が各線分上に存在するか否かの判定結果を用いた誤差の少ない交差判定を行うことができ、ブーリアン演算処理を正常に行うことが可能である。
【００６８】
また、この実施の形態２によれば、交差判定手段５ａが、判定対象の一方の線分Ａからみた判定対象の他方の線分Ｂの始点と終点の位置関係を、判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、判定対象の線分同士の交差の有無を第１の交差判定として判定し、第１の交差判定で発生した演算誤差が判定を誤らせる度合が小さいと誤差調査手段６ａにより判定されると、判定対象の他方の線分Ｂからみた判定対象の一方の線分Ａの始点と終点の位置関係を、判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、判定対象の線分同士の交差の有無を第２の交差判定として判定し、交点判定手段１０が、交点有無の判定結果と第１及び第２の交差判定結果に基づいて判定対象の線分同士の交差の有無を判定する。このようにすることで、より正確な交差判定が可能である。
【００６９】
なお、上記実施の形態２では、図２に示す交差判定手段５に図５の構成を適用した場合を示したが、図５に示す構成要素のみを有する図形処理装置を構成し、交差判定手段５ａや交点判定手段１０での判定結果を、図形処理装置の最終的な判定結果としてブーリアン演算処理を行うようにしてもよい。
【００７０】
実施の形態３．
この実施の形態３による図形処理装置は、上記実施の形態１の図２で示した構成と基本的に同一であるが、交差判定手段が交差判定にあたり、頂点の内外判定を行う構成を有する。
【００７１】
図７は、この発明の実施の形態３による交差判定手段の構成を概念的に示すブロック図であり、例えば図１中の演算プロセッサ２でメモリ３から読み出した図形処理用プログラムを実行することで具現化される構成を記載したものである。図７において、実施の形態３による交差判定手段５は、上記実施の形態２の図５で示した交差判定手段５ａ及び誤差調査手段６ａに加え、頂点内外判定手段１１を備える。
【００７２】
交差判定手段５ａは、上記実施の形態１で示した図１のメモリ３から読み出された図形データの辺情報を使用して図形の交差判定を行うにあたり、交差判定の対象となる２つの線分の交差状態を判定する。誤差調査手段６ａは、交差判定手段５ａの交差判定における演算誤差の具合を調査する。演算誤差には、浮動小数点演算における桁落ちや情報落ち、丸め誤差がある。
【００７３】
頂点内外判定手段１１は、誤差調査手段６ａの調査結果に応じて、交差判定手段５ａによる交差判定対象の一方の線分の頂点が、他方の線分を構成要素とする多角形の内部にあるか外部にあるかを判定する。
【００７４】
次に動作について説明する。
図８は、図７中の交差判定手段によるブーリアン演算処理の流れを示すフローチャートであり、上記実施の形態１で説明した図３のステップＳＴ１の処理を詳細に説明するものである。図８においても、上記実施の形態１の図４に示す多角形Ａと多角形Ｂのブーリアン演算において多角形Ａの頂点Ａ１と頂点Ａ２からなる線分Ａと、多角形Ｂの頂点Ｂ１と頂点Ｂ２からなる線分Ｂと、の交差を判定する場合を例に挙げている。
【００７５】
交差判定手段５ａ及び誤差調査手段６ａによるステップＳＴ１ｂからステップＳＴ７ｂまでの処理は、上記実施の形態２の図６で示したステップＳＴ１ａからステップＳＴ７ａまでの処理と同様であるので、説明を省略する。
【００７６】
ステップＳＴ５ｂで演算誤差が判定誤りに与える度合が大きいと判定されるか、若しくは、ステップＳＴ７ｂで交差判定手段５ａによる交差判定がなされると、頂点内外判定手段１１は、メモリ３から多角形Ａ，Ｂに属する頂点に関する情報（座標情報）を入力し、線分Ａを規定する頂点Ａ１，Ａ２が、線分Ｂを構成要素とする多角形Ｂの内部にあるか否かを判定する（ステップＳＴ８ｂ）。
【００７７】
図９は、図４中の多角形における頂点の内外判定を説明するための図である。図９に示すように、頂点内外判定手段１１は、頂点Ａ１が多角形Ｂの内外にあるかの判定を行うにあたり、頂点Ａ１と多角形Ｂの各辺とで作る角度を調べる。例えば、頂点Ａ１と線分Ｂ１Ｂ２との角度は角度α１となり、これはベクトルＡ１Ｂ２とベクトルＡ１Ｂ１の内積演算から算出することができる。
【００７８】
このようにして、頂点内外判定手段１１は、頂点Ａ１との間で多角形Ｂの全辺に対する角度を求め、全てを加算した結果３６０度となる場合は内部にあり、０度になる場合は外部にあると判定する。
【００７９】
ステップＳＴ８ｂにおいて、多角形Ａに属する頂点Ａ１，Ａ２が多角形Ｂの内部と外部に分かれて存在する場合、頂点内外判定手段１１は、線分Ａ（ベクトルＡ１Ａ２に対応）と、交差判定対象の他方の線分Ｂ（ベクトルＢ１Ｂ２に対応に対応）と、が交差する旨の判定を行う。また、上記以外（頂点Ａ１，Ａ２の双方が多角形Ｂの内部か外部のいずれかに存在する）の場合、線分Ａと線分Ｂが交差しないと判定する。
【００８０】
上述の内外判定の結果、ステップＳＴ１ｂでの交差判定結果、及びステップＳＴ７ｂでの交差判定の結果に基づいて、頂点内外判定手段１１は、線分Ａ（ベクトルＡ１Ａ２に対応）と線分Ｂ（ベクトルＢ１Ｂ２に対応）とが交差するか否かを、最終的に判定する（ステップＳＴ９ｂ）。
【００８１】
例えば、内外判定の結果及び上記交差判定の結果において線分Ａと線分Ｂが交差するとの判定結果が多い場合、頂点内外判定手段１１は、線分Ａと線分Ｂが交差すると判定し、実施の形態３による交差判定手段５の最終判定結果とする。一方、線分Ａと線分Ｂが交差するとの判定結果が少なければ、線分Ａと線分Ｂが交差しないと判定し、実施の形態２による交差判定手段５の最終判定結果とする。
【００８２】
上述のようにして得られた交差判定結果は、実施の形態３による交差判定手段５から、図２で示した誤差調査手段６へ出力される。この後の処理は、上記実施の形態１で説明したものと同様である（図３におけるステップＳＴ２以降の処理参照）。
【００８３】
以上のように、この実施の形態３によれば、交差判定手段５が、メモリ３から読み出した始点と終点で規定される２つの線分に関するデータを用い、判定対象の一方の線分Ａからみた判定対象の他方の線分Ｂの始点と終点の位置関係を、判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、判定対象の線分同士の交差の有無を判定する交差判定手段５ａと、交差判定手段５ａによる交差判定で発生した演算誤差を解析して、当該演算誤差が交差判定を誤らせる度合を大小判定する誤差調査手段６ａと、メモリ３から読み出した図形に関するデータを用いて、判定対象の一方の線分Ａの頂点が判定対象の他方の線分Ｂを構成要素とする図形の内部にあるか外部にあるかを判定し、この頂点の内外判定の結果と交差判定手段５ａの交差判定結果に基づいて、判定対象の線分同士の交差の有無を判定する頂点内外判定手段１１とを備える。このように構成することにより、交差判定対象の線分の頂点が交差判定対象の他方の線分を構成要素とする多角形の内部にあるか外部にあるかの判定結果を用いた誤差の少ない交差判定を行うことができ、ブーリアン演算処理を正常に行うことが可能である。
【００８４】
また、この実施の形態３によれば、交差判定手段５ａが、判定対象の一方の線分Ａからみた判定対象の他方の線分Ｂの始点と終点の位置関係を、判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、判定対象の線分同士の交差の有無を第１の交差判定として判定し、第１の交差判定で発生した演算誤差が判定を誤らせる度合が小さいと誤差調査手段６ａにより判定されると、判定対象の他方の線分Ｂからみた判定対象の一方の線分Ａの始点と終点の位置関係を、判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、判定対象の線分同士の交差の有無を第２の交差判定として判定し、頂点内外判定手段１１が、頂点の内外判定の結果と第１及び第２の交差判定結果に基づいて判定対象の線分同士の交差の有無を判定する。このようにすることで、より正確な交差判定が可能である。
【００８５】
なお、上記実施の形態３では、図２に示す交差判定手段５に図７の構成を適用した場合を示したが、図７に示す構成要素のみを有する図形処理装置を構成し、交差判定手段５ａや頂点内外判定手段１１での判定結果を、図形処理装置の最終的な判定結果としてブーリアン演算処理を行うようにしてもよい。
【００８６】
実施の形態４．
この実施の形態４による図形処理装置は、上記実施の形態１の図２で示した構成と基本的に同一であるが、交差判定手段が交差判定にあたり、交点判定と頂点の内外判定を行う構成を有する。
【００８７】
図１０は、この発明の実施の形態４による交差判定手段の構成を概念的に示すブロック図であり、例えば図１中の演算プロセッサ２でメモリ３から読み出した図形処理用プログラムを実行することで具現化される構成を記載したものである。図１０において、実施の形態４による交差判定手段５は、上記実施の形態２の図５で示した交差判定手段５ａ、誤差調査手段６ａ及び交点判定手段１０に加え、頂点内外判定手段１１を備える。
【００８８】
交差判定手段５ａは、上記実施の形態１で示した図１のメモリ３から読み出された図形データの辺情報を使用して図形の交差判定を行うにあたり、交差判定の対象となる２つの線分の交差状態を判定する。誤差調査手段６ａは、交差判定手段５ａの交差判定における演算誤差の具合を調査する。演算誤差には、浮動小数点演算における桁落ちや情報落ち、丸め誤差がある。
【００８９】
交点判定手段１０は、誤差調査手段６ａの調査結果に応じて、交差判定手段５ａによる交差判定対象の２つの線分の交点が双方の線分上に存在するか否かを判定する。頂点内外判定手段１１は、誤差調査手段６ａの調査結果に応じて、交差判定手段５ａによる交差判定対象の一方の線分の頂点が、他方の線分を構成要素とする多角形の内部にあるか外部にあるかを判定する。
【００９０】
次に動作について説明する。
図１１は、図１０中の交差判定手段によるブーリアン演算処理の流れを示すフローチャートであり、上記実施の形態１で説明した図３のステップＳＴ１の処理を詳細に説明するものである。図１１においても、上記実施の形態１の図４に示す多角形Ａと多角形Ｂのブーリアン演算において多角形Ａの頂点Ａ１と頂点Ａ２からなる線分Ａと、多角形Ｂの頂点Ｂ１と頂点Ｂ２からなる線分Ｂと、の交差を判定する場合を例に挙げている。
【００９１】
交差判定手段５ａ及び誤差調査手段６ａによるステップＳＴ１ｃからステップＳＴ７ｃまでの処理は、上記実施の形態２の図６で示したステップＳＴ１ａからステップＳＴ７ａまでの処理と同様であるので、説明を省略する。
【００９２】
ステップＳＴ５ｃで演算誤差が判定誤りに与える度合が大きいと判定されるか、若しくは、ステップＳＴ７ｃで交差判定手段５ａによる交差判定がなされると、交点判定手段１０は、誤差調査手段６ａを介して交差判定手段５ａから交差判定の結果を入力するとともに、線分Ａ（ベクトルＡ１Ａ２に対応）と線分Ｂ（ベクトルＢ１Ｂ２に対応）との交点の座標を算出して、この交点が双方の線分Ａ，Ｂ上に存在するか否かを判定する（ステップＳＴ８ｃ）。
【００９３】
また、上記実施の形態２と同様に、交差判定手段５ａの交差判定で外積関数のＺ成分を求める関数をｃｒｏｓｓとした場合、交点判定手段１０が、誤差調査手段６ａを介して、交差判定手段５ａによって算出された、２つの外積のＺ成分のｃｒｏｓｓ（Ａ１Ａ２，Ａ１Ｂ１）、ｃｒｏｓｓ（Ａ１Ａ２，Ａ１Ｂ２）を入力し、上記実施の形態２で示した上記式から交点の有無を判定してもよい。
【００９４】
ステップＳＴ８ｃで交点判定手段１０による交点判定がなされると、頂点内外判定手段１１は、交点判定手段１０から交点判定結果を入力するとともに、メモリ３から多角形Ａ，Ｂに属する頂点に関する情報（座標情報）を入力して、線分Ａを規定する頂点Ａ１，Ａ２が、線分Ｂを構成要素とする多角形Ｂの内部にあるか否かを判定する（ステップＳＴ９ｃ）。
【００９５】
例えば、上記実施の形態３で示した図９と同様に、頂点内外判定手段１１が、頂点Ａ１が多角形Ｂの内外にあるかの判定を行うにあたり、頂点Ａ１と多角形Ｂの各辺とで作る角度を調べる。頂点Ａ１と線分Ｂ１Ｂ２との角度は角度α１となり、これはベクトルＡ１Ｂ２とベクトルＡ１Ｂ１の内積演算から算出することができる。頂点内外判定手段１１が、頂点Ａ１との間で多角形Ｂの全辺に対する角度を求め、全てを加算した結果３６０度となる場合は内部にあり、０度になる場合は外部にあると判定する。
【００９６】
ステップＳＴ９ｃにおいて、多角形Ａに属する頂点Ａ１，Ａ２が多角形Ｂの内部と外部に分かれて存在する場合、頂点内外判定手段１１は、線分Ａ（ベクトルＡ１Ａ２に対応）と、交差判定対象の他方の線分Ｂ（ベクトルＢ１Ｂ２に対応に対応）と、が交差する旨の判定を行う。また、上記以外（頂点Ａ１，Ａ２の双方が多角形Ｂの内部か外部のいずれかに存在する）の場合、線分Ａと線分Ｂが交差しないと判定する。
【００９７】
次に、頂点内外判定手段１１は、上述の内外判定の結果、交点判定の結果、ステップＳＴ１ｃ及びステップＳＴ７ｃでの交差判定の結果に基づいて、線分Ａ（ベクトルＡ１Ａ２に対応）と線分Ｂ（ベクトルＢ１Ｂ２に対応）とが交差するか否かを、最終的に判定する（ステップＳＴ１０ｃ）。
【００９８】
例えば、内外判定の結果、交点判定の結果及び上記交差判定の結果において、線分Ａと線分Ｂが交差するとの判定結果が多い場合、頂点内外判定手段１１は、線分Ａと線分Ｂが交差すると判定し、実施の形態４による交差判定手段５の最終判定結果とする。一方、線分Ａと線分Ｂが交差するとの判定結果が少なければ、線分Ａと線分Ｂが交差しないと判定し、実施の形態４による交差判定手段５の最終判定結果とする。
【００９９】
上述のようにして得られた交差判定結果は、実施の形態４による交差判定手段５から、図２で示した誤差調査手段６へ出力される。この後の処理は、上記実施の形態１で説明したものと同様である（図３におけるステップＳＴ２以降の処理参照）。
【０１００】
以上のように、この実施の形態３によれば、交差判定手段５が、メモリ３から読み出した始点と終点で規定される２つの線分に関するデータを用い、判定対象の一方の線分Ａからみた判定対象の他方の線分Ｂの始点と終点の位置関係を、判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、判定対象の線分同士の交差の有無を判定する交差判定手段５ａと、交差判定手段５ａによる交差判定で発生した演算誤差を解析して、当該演算誤差が交差判定を誤らせる度合を大小判定する誤差調査手段６ａと、メモリ３から読み出した線分に関するデータを用いて、判定対象の各線分上に交点が存在するか否かを判定する交点判定手段１０と、メモリ３から読み出した図形に関するデータを用いて、判定対象の一方の線分Ａの頂点が、判定対象の他方の線分Ｂを構成要素とする図形の内部にあるか外部にあるかを判定し、この頂点の内外判定の結果、交点判定手段１０による交点判定の結果及び交差判定手段５ａの交差判定結果に基づいて、判定対象の線分同士の交差の有無を判定する頂点内外判定手段１１とを備える。このように構成することで、交差判定対象の線分同士の交点が各線分上に存在するか否かの判定結果と、交差判定対象の線分の頂点が交差判定対象の他方の線分を構成要素とする多角形の内部にあるか外部にあるかの判定結果とを用いた演算誤差の少ない交差判定を行うことができ、ブーリアン演算処理を正常に行うことが可能である。
【０１０１】
また、この実施の形態４によれば、交差判定手段５ａが、判定対象の一方の線分Ａからみた判定対象の他方の線分Ｂの始点と終点の位置関係を、判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、判定対象の線分同士の交差の有無を第１の交差判定として判定し、第１の交差判定で発生した演算誤差が判定を誤らせる度合が小さいと誤差調査手段６ａにより判定されると、判定対象の他方の線分Ｂからみた判定対象の一方の線分Ａの始点と終点の位置関係を、判定対象の線分に対応するベクトルの外積演算で特定した結果に基づいて、判定対象の線分同士の交差の有無を第２の交差判定として判定し、頂点内外判定手段１１が、交点の判定結果、頂点の内外判定の結果、第１及び第２の交差判定結果に基づいて判定対象の線分同士の交差の有無を判定する。このようにすることで、より正確な交差判定が可能である。
【０１０２】
なお、上記実施の形態４では、図２に示す交差判定手段５に図１０の構成を適用した場合を示したが、図１０に示す構成要素のみを有する図形処理装置を構成し、交差判定手段５ａや交点判定手段１０、頂点内外判定手段１１での判定結果を、図形処理装置の最終的な判定結果としてブーリアン演算処理を行うようにしてもよい。
【図面の簡単な説明】
【０１０３】
【図１】この発明の図形処理装置を実現するための装置構成を概略的に示す図である。
【図２】この発明の実施の形態１による図形処理装置の構成を概念的に示すブロック図である。
【図３】図２中の図形処理装置によるブーリアン演算処理の流れを示すフローチャートである。
【図４】多角形のブーリアン演算処理の一例を示す図である。
【図５】この発明の実施の形態２による交差判定手段の構成を概念的に示すブロック図である。
【図６】図５中の交差判定手段によるブーリアン演算処理の流れを示すフローチャートである。
【図７】この発明の実施の形態３による交差判定手段の構成を概念的に示すブロック図である。
【図８】図７中の交差判定手段によるブーリアン演算処理の流れを示すフローチャートである。
【図９】図４中の多角形における頂点の内外判定を説明するための図である。
【図１０】この発明の実施の形態４による交差判定手段の構成を概念的に示すブロック図である。
【図１１】図１０中の交差判定手段によるブーリアン演算処理の流れを示すフローチャートである。
【図１２】ブーリアン演算処理の一例を示す図である。
【図１３】ブーリアン演算処理の他の例を示す図である。
【図１４】演算誤差の発生しやすい図形の関係を示す図である。
【符号の説明】
【０１０４】
１  図形処理装置、２  演算プロセッサ、３  メモリ、４  バス、５  交差判定手段、５ａ  交差判定手段（第１の交差判定手段）、６  誤差調査手段、６ａ  誤差調査手段（第１の誤差調査手段）、７  座標位置判定手段（位置判定手段）、８  最終判定手段、９  ターゲット線分選択手段、１０  交点判定手段、１１  頂点内外判定手段。
【図１】
0004974955.tif 000002
【図２】
0004974955.tif 000003
【図３】
0004974955.tif 000004
【図４】
0004974955.tif 000005
【図５】
0004974955.tif 000006
【図６】
0004974955.tif 000007
【図７】
0004974955.tif 000008
【図８】
0004974955.tif 000009
【図９】
0004974955.tif 000010
【図１０】
0004974955.tif 000011
【図１１】
0004974955.tif 000012
【図１２】
0004974955.tif 000013
【図１３】
0004974955.tif 000014
【図１４】
0004974955.tif 000015