(57)【要約】Ｐ０，Ｐ１，Ｐ２を３頂点とする三角形と、Ａ，Ｂを結ぶ線分との交点を計算する方法。Ｐ０を原点、Ｐ０Ｐ１を第一軸（Ｕ軸）の単位長さ、Ｐ０Ｐ２を第二軸（Ｖ軸）の単位長さ、Ｐ０Ｐ１×Ｐ０Ｐ２の単位ベクトルを第三軸（Ｎ軸）とする座標系Ｒを設定し、通常の座標系での点の座標を座標系Ｒの座標値に変換する変換マトリックスＭを計算し、線分の両端Ａ，Ｂのｕ，ｖ，ｎ座標値を演算する。また、両端Ａ，Ｂのｕ，ｖ，ｎ座標値から三角形との交差の有無を判断し、交差する場合にその交点のｕ，ｖ座標値を演算し、交点のｕ，ｖ座標値から三角形内の交点の有無を判断する。
2004053741.tif 000002
【特許請求の範囲】
【請求項１】
Ｐ０，Ｐ１，Ｐ２を３頂点とする三角形と、Ａ，Ｂを結ぶ線分との交点を計算する方法において、
Ｐ０を原点、Ｐ０Ｐ１を第一軸（Ｕ軸）の単位長さ、Ｐ０Ｐ２を第二軸（Ｖ軸）の単位長さ、Ｐ０Ｐ１×Ｐ０Ｐ２の単位ベクトルを第三軸（Ｎ軸）とする座標系Ｒを設定する座標系設定ステップ（Ａ）と、
通常の座標系での点の座標を座標系Ｒの座標値に変換する変換マトリックスＭを計算する変換マトリックス計算ステップ（Ｂ）と、
線分の両端Ａ，Ｂのｕ，ｖ，ｎ座標値を演算する線分端座標演算ステップ（Ｃ）と、
両端Ａ，Ｂのｕ，ｖ，ｎ座標値から三角形との交差の有無を判断する交差判断ステップ（Ｄ）と、
交差する場合にその交点のｕ，ｖ座標値を演算する交点座標演算ステップ（Ｅ）と、
交点のｕ，ｖ座標値から三角形内の交点の有無を判断する交点判断ステップ（Ｆ）と、を備えることを特徴とする三角形と線分の交点計算方法。
【請求項２】
前記変換マトリックス計算ステップ（Ｂ）において、変換マトリックスＭは、Ａｆｆｉｎｅ変換マトリックスである、ことを特徴とする請求項１に記載の三角形と線分の交点計算方法。
【請求項３】
線分端座標演算ステップ（Ｃ）において、ｕ，ｖ，ｎ座標値を式（８）で求める、
ＰＵＶＮ＝ＭＰｘｙｚ・・・（８）
ことを特徴とする請求項１に記載の三角形と線分の交点計算方法。
【請求項４】
交差判断ステップ（Ｄ）において、（１）片方の点のｎ座標が線分の長さ以上であれば交点無しと判断し、及び／又は、（２）２点のｎ座標が同符号であれば交点なし、異符号であれば交点ありと判断する、ことを特徴とする請求項１に記載の三角形と線分の交点計算方法。
【請求項５】
交差判断ステップ（Ｄ）において、（１）２点ともｕ座標が０以下又は１以上、（２）２点ともｖ座標が０以下、又は（３）２点ともｕ座標＋ｖ座標が１以上の場合、交点は三角形外と判断する、ことを特徴とする請求項１に記載の三角形と線分の交点計算方法。
【請求項６】
交点座標演算ステップ（Ｅ）において、両端Ａ，Ｂのｎ座標の値で内分した点を交点とし、そのｕ，ｖ座標値を演算する、ことを特徴とする請求項１に記載の三角形と線分の交点計算方法。
【請求項７】
交点判断ステップ（Ｆ）において、交点のｕ，ｖ座標値が、［数１］の式（１３）を満たす場合に、三角形の内部と判断する、
【数１】
2004053741.tif 000010
ことを特徴とする請求項１に記載の三角形と線分の交点計算方法。
【請求項８】
コンピュータに、Ｐ０，Ｐ１，Ｐ２を３頂点とする三角形と、Ａ，Ｂを結ぶ線分との交点を計算させるためプログラムであって、
Ｐ０を原点、Ｐ０Ｐ１を第一軸（Ｕ軸）の単位長さ、Ｐ０Ｐ２を第二軸（Ｖ軸）の単位長さ、Ｐ０Ｐ１×Ｐ０Ｐ２の単位ベクトルを第三軸（Ｎ軸）とする座標系Ｒを設定する座標系設定ステップ（Ａ）と、
通常の座標系での点の座標を座標系Ｒの座標値に変換する変換マトリックスＭを計算する変換マトリックス計算ステップ（Ｂ）と、
線分の両端Ａ，Ｂのｕ，ｖ，ｎ座標値を演算する線分端座標演算ステップ（Ｃ）と、
両端Ａ，Ｂのｕ，ｖ，ｎ座標値から三角形との交差の有無を判断する交差判断ステップ（Ｄ）と、
交差する場合にその交点のｕ，ｖ座標値を演算する交点座標演算ステップ（Ｅ）と、
交点のｕ，ｖ座標値から三角形内の交点の有無を判断する交点判断ステップ（Ｆ）と、を実行させるためのプログラム。
【発明の詳細な説明】
発明の背景
発明の技術分野
本発明は、三角形と線分の交点計算方法とそのプログラムに関する。
関連技術の説明
形状と物性を統合した実体データを小さい記憶容量で記憶することができ、これにより、物体の形状・構造・物性情報・履歴を一元的に管理し、設計から加工、組立、試験、評価など一連の工程に関わるデータを同じデータで管理することができ、ＣＡＤとシミュレーションを一元化することできる実体データの記憶方法として、［特許文献１］が開示されている。
【特許文献１】    特開２００２−２３００５４号公報
［特許文献１］の「形状と物性を統合した実体データの記憶方法」は、図１に示すように、外部データ入力ステップ（Ａ）、八分木分割ステップ（Ｂ）、及びセルデータ記憶ステップ（Ｃ）からなり、外部データ入力ステップ（Ａ）では、外部データ取得ステップＳ１で取得した対象物の境界データからなる外部データ１２をこの発明の方法を記憶したコンピュータ等に入力し、八分木分割ステップ（Ｂ）では、外部データ１２を八分木分割により境界平面が直交する直方体のセルに分割し、セルデータ記憶ステップ（Ｃ）では、各セル毎に種々の物性値を記憶するものである。
上述した［特許文献１］の発明は、対象物の形状データからなる外部データを、八分木分割により境界平面が直交する直方体のセルに分割し、各セル毎に種々の物性値を記憶するものである。分割された各セルは対象物の内側に位置する内部セルと、境界面を含む境界セルとからなる。また、内部セルは、属性として１種の物性値を持ち、境界セルは、対象物の内側と外側の２種の物性値をもつものである。
以下、この方法によるデータを「Ｖ−ＣＡＤデータ」と呼び、このデータを用いた設計やシミュレーションを「ボリュームＣＡＤ」又は「Ｖ−ＣＡＤ」と呼ぶ。図１において１４がＶ−ＣＡＤデータである。
図２は、［特許文献１］に基づいて外部データからＶ−ＣＡＤデータを作成する手順を示す図である。この図に示すように、Ｓ−ＣＡＤデータや三角形パッチデータに対して、ＳＴＥＰ−１でボクセル空間を定義し、ＳＴＥＰ−２で幾何形状と各セルの稜線との交点計算（セル切断点の取得）を行い、ＳＴＥＰ−３でセル毎の切断点情報からセル内面の外周ループを作成し、ＳＴＥＰ−４で元の幾何形状を参照しつつ外周ループ内を三角形分割し、ＳＴＥＰ−５でセルの媒質値を設定することで、Ｖ−ＣＡＤデータが作成される。
上述した［特許文献１］の方法では、図１の八分木分割ステップ（Ｂ）、および図２のＳＴＥＰ−２において、外部データである幾何形状を定義する三角形と各セルの稜線である線分との交点を求める計算を繰り返し膨大な回数行う必要が生じる。
かかる三角形と線分との交点計算方法として、従来から、［非特許文献１］〜［非特許文献３］が知られている。
【非特許文献１】  Ｍｏｌｌｅｒの方法（Ｊｏｕｒｎａｌ  ｏｆ  ｇｒａｐｈｉｃｓ  ｔｏｏｌｓ，２（１）：２１−２８  １９９７）．
【非特許文献２】  Ｂａｄｏｕｅｌの方法（Ｇｒａｐｈｉｃ  Ｇｅｍｓ，Ａｃａｄｅｍｉｃ  Ｐｒｅｓｓ  Ｐ２１−２８  １９９０）．
【非特許文献３】  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｇｅｏｍｅｔｒｙ  ｉｎ  Ｃ：Ｊｏｓｅｐｈ  Ｏ’Ｒｏｕｒｋｅ／Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ  Ｐ２３９）
三角形と線分との交点計算については、さまざまな方法が存在しており、その多くは無限平面と無限直線との交点を計算し、その交点が平面内の閉領域としての三角形内に含まれているか否かを判断する方法である。そのような方法は計算コストが高く、Ｖ−ＣＡＤシステムで今後推定されるように、多数回の計算を繰り返す場合の改善策が必要であった。
［非特許文献１］のＭｏｌｌｅｒの方法では、［数２］の式（１）のベクトル計算式を利用することで、比較的低コストで計算が可能である。
【数２】
2004053741.tif 000003
しかし、この方法においては、同一の三角形に対して異なる複数の線分との交点を求める際にも、全ての計算式を改めて計算する必要があるため、「同一の三角形」という条件下で交点計算のメリットが発生せず、高速化を図ることが困難であるという問題点があった。
［非特許文献２］のＢａｄｏｕｅｌの方法では、図３において、平面の基準点ＰＰｉｎと法線ベクトルＶＮｒｍ、直線の基準点ＰＬｉｎを利用して以下ように求める。
［数３］の式（２）として、直線の基準点と平面の距離はｄｓｔ＝ＶＮｒｍ・ＶＰｎｔ（ＶＮｒｍは単位ベクトル）で求まるので、交点の座標はＰＩｎｔ＝ＰＬｉｎ＋ＶＬｉｎ・ｄｓｔ／（ＶＬｉｎ・ＶＮｒｍ）で計算できる。
続いて、三角形の各頂点、および平面と直線の交点を座標平面（ｘｙ平面、ｙｚ平面、ｚｘ平面）のいずれかに投影し、この平面上で、［数３］の式（３）となるα、βを計算する。
α、βの計算方法は、図４において、ｘｙ平面上に投影した場合、Ｐ１（ｘ１，ｙ１，ｚ１）、Ｐ２（ｘ２，ｙ２，ｚ２）、Ｐ３（ｘ３，ｙ３，ｚ３）、ＰＩｎｔ（ｘ，ｙ，ｚ）として、各頂点のＺ座標を省略した一次変換の式（［数３］の式（４））の逆変換を作成すればよい。
【数３】
2004053741.tif 000004
無限平面と直線の交点計算の方法はＢａｄｏｕｅｌの方法で記述したものと同じであるが、交点と三角形の内外判定方法には他にも以下の様な方法が挙げられる。
［非特許文献３］の角度を計算する方法では、図５Ａと図５Ｂにおいて、個々の頂点に向けたベクトル同士の内積をそれぞれ取り、それから求めた角度の和が０となるか、３６０度となるかによって判断する。すなわち、図５Ａでは式（５）が成り立ち、図５Ｂでは式（６）が成り立つ。
θ１２＋θ２３＋θ３１＝２ＰＩ・・・（５）
θ１２θ２３＋θ３１＝０・・・（６）
その他に、図６Ａと図６Ｂに示すように、交点から三角形に各頂点に向けたベクトルの外積を［数４］の式（７）で求め、これらが同じ方向を向くか否かで判断する外積を利用する方法もある。
【数４】
2004053741.tif 000005
図６Ａでは、ＶＮｒｍ１２、ＶＮｒｍ２３、ＶＮｒｍ３１、とも同じ方向を向き、図６Ｂでは、ＶＮｒｍ３１は逆方向を向く。
ただし、外積を利用する方法では、明らかに計算負荷がかかることが予想される。
上述したように、従来の三角形と線分との交点計算手段では、同一の三角形に対して異なる複数の線分との交点を求める場合に、その都度ほとんど全ての計算式を改めて計算する必要があるため、全体として計算時間が長くなり、高速化を図ることが困難であるという問題点があった。
発明の要約
本発明は、かかる問題点を解決するために創案されたものである。すなわち、本発明の目的は、同一の三角形に対して異なる複数の線分との交点を求める場合に、計算時間を短縮し高速化を図ることができる三角形と線分の交点計算方法とそのプログラムを提供することにある。
本発明によれば、Ｐ０，Ｐ１，Ｐ２を３頂点とする三角形と、Ａ，Ｂを結ぶ線分との交点を計算する方法において、Ｐ０を原点、Ｐ０Ｐ１を第一軸（Ｕ軸）の単位長さ、Ｐ０Ｐ２を第二軸（Ｖ軸）の単位長さ、Ｐ０Ｐ１×Ｐ０Ｐ２の単位ベクトルを第三軸（Ｎ軸）とする座標系Ｒを設定する座標系設定ステップ（Ａ）と、通常の座標系での点の座標を座標系Ｒの座標値に変換する変換マトリックスＭを計算する変換マトリックス計算ステップ（Ｂ）と、線分の両端Ａ，Ｂのｕ，ｖ，ｎ座標値を演算する線分端座標演算ステップ（Ｃ）と、両端Ａ，Ｂのｕ，ｖ，ｎ座標値から三角形との交差の有無を判断する交差判断ステップ（Ｄ）と、交差する場合にその交点のｕ，ｖ座標値を演算する交点座標演算ステップ（Ｅ）と、交点のｕ，ｖ座標値から三角形内の交点の有無を判断する交点判断ステップ（Ｆ）と、を備えることを特徴とする三角形と線分の交点計算方法が提供される。
また、本発明によれば、コンピュータに、Ｐ０，Ｐ１，Ｐ２を３頂点とする三角形と、Ａ，Ｂを結ぶ線分との交点を計算させるためプログラムであって、Ｐ０を原点、Ｐ０Ｐ１を第一軸（Ｕ軸）の単位長さ、Ｐ０Ｐ２を第二軸（Ｖ軸）の単位長さ、Ｐ０Ｐ１×Ｐ０Ｐ２の単位ベクトルを第三軸（Ｎ軸）とする座標系Ｒを設定する座標系設定ステップ（Ａ）と、通常の座標系での点の座標を座標系Ｒの座標値に変換する変換マトリックスＭを計算する変換マトリックス計算ステップ（Ｂ）と、線分の両端Ａ，Ｂのｕ，ｖ，ｎ座標値を演算する線分端座標演算ステップ（Ｃ）と、両端Ａ，Ｂのｕ，ｖ，ｎ座標値から三角形との交差の有無を判断する交差判断ステップ（Ｄ）と、交差する場合にその交点のｕ，ｖ座標値を演算する交点座標演算ステップ（Ｅ）と、交点のｕ，ｖ座標値から三角形内の交点の有無を判断する交点判断ステップ（Ｆ）と、を実行させるためのプログラムが提供される。
上記本発明の方法とプログラムによれば、同一の三角形に対して異なる複数の線分との交点を求める場合に、同一の三角形に対する変換マトリックスＭは、常に同一であり、異なる複数の線分に対して、線分端座標演算ステップ（Ｃ）を行うだけで、線分の両端Ａ，Ｂのｕ，ｖ，ｎ座標値を演算することができる。従って、従来の方法に比べて、異なる線分に対して再計算が少なくなり、計算時間を短縮し高速化を図ることができる
本発明の好ましい実施形態によれば、前記変換マトリックス計算ステップ（Ｂ）において、変換マトリックスＭは、Ａｆｆｉｎｅ変換マトリックスである。
Ａｆｆｉｎｅ変換マトリックスにより、三角形に対して変換マトリックスＭを短時間に容易に計算することができる。
また、線分端座標演算ステップ（Ｃ）において、ｕ，ｖ，ｎ座標値を式（８）で求める、
ＰＵＶＮ＝ＭＰｘｙｚ・・・（８）。
式（８）により、異なる複数の線分に対して、線分の両端Ａ，Ｂのｕ，ｖ，ｎ座標値を短時間に容易に計算することができる。
また、交差判断ステップ（Ｄ）において、（１）片方の点のｎ座標が線分の長さ以上であれば交点無しと判断し、及び／又は、（２）２点のｎ座標が同符号であれば交点なし、異符号であれば交点ありと判断する。
この判断により、交点の有無を、容易かつ短時間に判断できる。
また、交差判断ステップ（Ｄ）において、（１）２点ともｕ座標が０以下又は１以上、（２）２点ともｖ座標が０以下、又は（３）２点ともｕ座標＋ｖ座標が１以上の場合、交点は三角形外と判断する。
この手段により、交点となりうる点と三角形との内外判定を、容易かつ短時間にでき、実際の交点を求める以前に、明らかに三角形内に交点を持たない線分を除外し、不必要な計算を省略することができる。
また、交点座標演算ステップ（Ｅ）において、両端Ａ，Ｂのｎ座標の値で内分した点を交点とし、そのｕ，ｖ座標値を演算する。
この手段により、交点のｕ，ｖ座標値を、容易かつ短時間に、計算できる。
また、交点判断ステップ（Ｆ）において、交点のｕ，ｖ座標値が、［数１］の式（１３）を満たす場合に、三角形の内部と判断する。
この手段で、交点と三角形との内外判定を、容易かつ短時間にでき、実際の交点を求める以前に、三角形内に交点を持たない線分を除外し、不必要な計算を省略することができる。
本発明のその他の目的及び有利な特徴は、添付図面を参照した以下の説明から明らかになろう。
【図面の簡単な説明】  図１は、先行出願の実体データの記憶方法のフロー図である。
図２は、先行出願の実体データの記憶方法の別のフロー図である。
図３は、従来の方法を示す模式図である。
図４は、従来の方法を示す別の模式図である。
図５Ａと図５Ｂは、従来の方法を示す別の模式図である。
図６Ａと図６Ｂは、従来の方法を示す別の模式図である。
図７は、本発明の方法を実行するための装置の構成図である。
図８は、本発明の方法とそのプログラムのフロー図である。
図９は、本発明による座標系Ｒを示す模式図である。
図１０は、本発明による処理方法を具体的に示すフロチャートである。
図１１は、本発明の第１の実施例を示すフロー図である。
図１２は、入力三角形の表示を示す画像である。
図１３は、セルとセル内面で構成されるＶ−ＣＡＤデータを示す画像である。
図１４は、入力データとセル稜線の交点計算により発生したセル切断点を示す画像である。
図１５は、本発明の第２の実施例を示すフロー図である。
図１６は、形状変換処理後のＶ−ＣＡＤデータを示す画像である。
好ましい実施例の説明
以下、本発明の好ましい実施形態を図面を参照して説明する。
図７は、本発明の方法を実行するための装置構成図である。この図に示すように、この装置１０は、入力装置２、外部記憶装置３、内部記憶装置４、中央処理装置５および出力装置６を備える。
入力装置２は、例えばキーボードであり、対象物１の形状データからなる外部データ１２を入力する。外部記憶装置３は、ハードディスク、フロピィーディスク、磁気テープ、コンパクトディスク等であり、形状と物理量を統合した実体データとその記憶演算プログラムを記憶する。内部記憶装置４は、例えばＲＡＭ，ＲＯＭ等であり、演算情報を保管する。中央処理装置５（ＣＰＵ）は、演算や入出力等を集中的に処理し、内部記憶装置４と共に、記憶プログラムを実行する。出力装置６は、例えば表示装置とプリンタであり、記憶した実体データと記憶プログラムの実行結果を出力するようになっている。
図８は、本発明の交点計算方法とそのプログラムのフロー図である。この図に示すように、本発明の交点計算方法とそのプログラムは、座標系設定ステップ（Ａ）、変換マトリックス計算ステップ（Ｂ）、線分端座標演算ステップ（Ｃ）、交差判断ステップ（Ｄ）、交点座標演算ステップ（Ｅ）、及び交点判断ステップ（Ｆ）からなる。
本発明の交点計算方法は、Ｐ０，Ｐ１，Ｐ２を３頂点とする三角形と、Ａ，Ｂを結ぶ線分との交点を計算する方法であり、本発明のプログラムは、コンピュータに、Ｐ０，Ｐ１，Ｐ２を３頂点とする三角形と、Ａ，Ｂを結ぶ線分との交点を計算させるためプログラムである。
座標系設定ステップ（Ａ）では、Ｐ０を原点、Ｐ０Ｐ１を第一軸（Ｕ軸）の単位長さ、Ｐ０Ｐ２を第二軸（Ｖ軸）の単位長さ、Ｐ０Ｐ１×Ｐ０Ｐ２の単位ベクトルを第三軸（Ｎ軸）とする座標系Ｒを設定する。
変換マトリックス計算ステップ（Ｂ）では、通常の座標系での点の座標を座標系Ｒの座標値に変換する変換マトリックスＭを計算する。
線分端座標演算ステップ（Ｃ）では、線分の両端Ａ，Ｂのｕ，ｖ，ｎ座標値を演算する。
交差判断ステップ（Ｄ）では、両端Ａ，Ｂのｕ，ｖ，ｎ座標値から三角形との交差の有無を判断する。
交点座標演算ステップ（Ｅ）では、交差する場合にその交点のｕ，ｖ座標値を演算する。交点判断ステップ（Ｆ）では、交点のｕ，ｖ座標値から三角形内の交点の有無を判断する。
以下、本発明を詳細に説明する。
１．  ボリュームＣＡＤの開発において、入力としての表面形状に多用される三角形パッチと線分（セル稜線）との交点計算を繰り返し行う。三角形と線分との交点計算は平面と直線との交点計算の後、直線上の有効領域にあるか、平面上の有効領域にあるかという内外判定を行うこととなり、ベクトル演算を多用するため計算負荷が高くなる。例えば、入力の三角形パッチ群は１種で有るのに対し、Ｖ−ＣＡＤなどのボリュームデータ（三次元の広がり全体を表現するデータ、ＣＴやＭＲＩ、ボリュームレンダリング用のデータなど）に変換する際に、分割数や分解能を変更したり、Ｏｃｔｒｅｅ化、多重ボクセル化などの階層性を持つ格子データに変換したりするケースでは、１つのサーフェスデータに対して格子の稜線との交点計算が同時に、或いは繰り返し、大量に行われることになる。従って、以下に述べる従来技術では効率が悪く、大幅な効率化を達成できる手法が必要となる。また、ボリュームＣＡＤに限らずとも、情報量の豊富さから今後ボリュームデータが幅広く流通されると予想されるが、そのような場面においても、処理や制御のしやすさから三角形パッチとボリュームデータの併用が必要となり、その際に本発明の技術は不可欠となる。
本発明では入力データをコンピュータ上での形状表示などに一般に利用されているＡｆｆｉｎｅ変換マトリックスに変換しておくことで、交点計算および内外判定を高速に、かつ安定して行える。特に同一の三角形に対して繰り返し交点計算を行う場合には、以前に作成した三角形固有のマトリックスを再利用することで、計算コストの大幅な低減が可能となる。例えば、機械部品などでは、平面で構成される面が多く、入力の表面形状として使われる三角形は大きなものが多い。その結果、同じ三角形とセル稜線との交点計算が多数回行われるため、本発明の利点が際立つこととなる。
２．本発明では、図９に示すように、三角形の２辺を第一軸、第二軸、法線ベクトルを第三軸とし、第一軸と第二軸に共通する頂点を原点とする空間座標系Ｒを設定する。
正規直交座標系と上記座標系の変換を行うために、計算機上での画像表示などに利用されるＡｆｆｉｎｅ変換マトリックスを計算し、三角形との対応付けを行う。
交点計算を行う線分の両端の座標を上記マトリックスにより空間座標系Ｒに変換し、それらの値から、交点の有無や交点の三角形に対する内外判定、ならびに交点の座標計算を行う。
上記のような手段を用いることにより、以下の利点が発生する。
（１）既存の手段では、２段階で行われていた交点の計算と内外判定を一段階で行えることとなり、記憶容量の増加を必要とせず、高速に計算できる。
（２）同一の三角形に対して多数の線分との交点計算を行う際に、予め準備された幾何量を利用することで計算コストが低く抑えられる。
（３）座標変換と点の内分という簡易なアルゴリズムであるため、実装が容易である。
（４）座標変換の結果に符合付距離を含むため、Ｖｏｌｕｍｅデータの属性データとしての元曲面からの距離の計算や、面の表裏方向の確認に利用することができる。
３．  図１０は、本発明による処理方法を具体的に示すフロチャートである。この図において、Ｐ０，Ｐ１，Ｐ２を３頂点とする入力三角形の３次元座標データを入力し、これから、上述した座標系設定ステップ（Ａ）において、Ｐ０を原点、Ｐ０Ｐ１を第一軸（Ｕ軸）の単位長さ、Ｐ０Ｐ２を第二軸（Ｖ軸）の単位長さ、Ｐ０Ｐ１×Ｐ０Ｐ２の単位ベクトルを第三軸（Ｎ軸）とする座標系Ｒを設定する。
次に、Ｓ１において、三角形に応じた座標系Ｒに対応するマトリックスを算出する。このステップは、上述した変換マトリックス計算ステップ（Ｂ）に相当する。
次に、Ｓ２において、交差計算対象線分の両端Ａ，Ｂのｕｖ座標、符号付距離をＡｆｆｉｎｅ変換演算により求める。このステップは、上述した線分端座標演算ステップ（Ｃ）に相当する。
次に、Ｓ３において、符号付距離とｕｖ座標により、三角形との交差の有無を判断する。このステップは、上述した交差判断ステップ（Ｄ）に相当する。
次に、Ｓ４において、交点を計算する。このステップは、上述した交点座標演算ステップ（Ｅ）に相当する。
次に、Ｓ５において、ＵＶ値から三角形内の交点の有無を判断する。このステップは、上述した交点判断ステップ（Ｆ）に相当する。
４．１  以下、計算フローの詳細を説明する。
４．１．１  三角形に応じた座標系と対応するマトリックス
図９に示すように、三角形の頂点をＰ０，Ｐ１，Ｐ２とした時に、Ｐ０を原点、Ｐ０Ｐ１を第一軸（Ｕ軸）の単位長さ、Ｐ０Ｐ２を第二軸（Ｖ軸）の単位長さ、Ｐ０Ｐ１×Ｐ０Ｐ２の単位ベクトルを第三軸（Ｎ軸）とするような座標系Ｒを考える。
通常の直交座標系での点の座標をこの座標系での座標値に変換するマトリックスをＭとすると、
ＰＵＶＮ＝ＭＰｘｙｚ・・・（８）
の式で変換された座標値は三角形によって定まる座標表面上のＵＶ値と、三角形からの符合付距離がそれぞれｕ，ｖ，ｎ座標として計算される。
これにより、任意の点の三角形に対する位置関係（符号付距離、三角形上に垂直投影できるか否か）などが計算でき、また同一の三角形に対して多数回の交点計算を行う際には、行列をそのまま利用できるので、計算負荷の低減が可能となる。その結果、より高速な交点計算が可能となる。
この変換マトリックスは、スケーリング、回転、座標軸の変形、平行移動を含むため、４×４の通常、ＣＧの表示などに利用されているＡｆｆｉｎｅ変換とよばれる変換マトリックスを使用する。
スケーリングマトリックス、平行移動のマトリックスについては、各軸方向の縮尺をｘＳｃａｌｅ，ｙＳｃａｌｅ，Ｚｓｃａｌｅ，平行移動ベクトルを（ｘＭｏｖｅ，ｙＭｏｖｅ，ｚＭｏｖｅ）として、［数５］の式（９）（１０）のように表すことができる。
また、回転および座標軸変形のマトリックスについては、ｕｖｎ座標系での各軸方向の単位ベクトルがそれぞれＶｃｌｅ，Ｖｅｃ２，ＶｅｃＮとなることから、各ベクトルの成分を（ｖｘ１，ｖｙ１，ｖｚ１）、（ｖｘ１，ｖｙ１，ｖｚ１）、（ｖｘｎ，ｖｙｎ，ｖｚｎ）として、［数４］の式（１１）のように表現できる。これらを統合して［数５］の式（１２）と計算する。
【数５】
2004053741.tif 000006
４．１．２  直線の両端点の座標変換（符号付距離、ｕｖ座標の算出）
始点・終点の座標を上記のマトリックスでＡｆｆｉｎｅ変換する。
但し、Ａｆｆｉｎｅ変換の４×４行列のうち、１行目〜３行目の４カラム目は移動量であるので、掛け算の対象は必ず１であり、また４行目については、１〜３カラム目が０．４カラム目が１．４カラム目の掛け算の対象は１であるので、かならず計算結果は１となる。従って、汎用の行列計算用の計算でなく、Ａｆｆｉｎｅ変換専用の計算を行えば、掛け算を必要とするのは、１〜３行目、１〜３カラム目の９回だけで済むことになり、より高速な計算が可能になる。
４．１．３  変換後の２点の座標を見て、交点の有無を判断する。
・  片方の点のｎ座標が線分の長さ以上であれば交点無し、
・  ２点のｎ座標が同符号であれば、交点無し異符号であれば交点あり
４．１．４  変換後の２点のｕ座標、ｖ座標から、交点となりうる点と三角形との内外判定を行う。
・  ２点とも、ｕ座標が０以下または１．０以上の時、交点は三角形外
・  ２点とも、ｖ座標が０．０以下の時、交点は三角形外
・  ２点とも、ｕ座標＋ｖ座標が１．０以上の時、交点は三角形外
上記の条件を元に実際の交点の値を求める以前に、明らかに三角形上に交点を持たない線分を除外する。
４．１．５  両端のｎ座標の値で内分した点を交点とし、ｕｖ座標を求める。
４．１．６  交点のｕ座標、ｖ座標を以下の基準により、三角形との内外判定を行う。
三角形の内部にあるための条件は、［数６］の式（１３）に示す３項目となる。
【数６】
2004053741.tif 000007
４．２  計算コストと計算結果
Ｍｏｌｌｅｒの手法と本発明の計算コストを比較する。
まず、Ｍｏｌｌｅｒの手法では、［数７］の式（１４）が２回ずつでてくるので、それぞれベクトルＰ、Ｑとして計算しておき、また割り算を行う部分も予め逆数を［数７］の式（１５）で計算しておく。
この場合、ベクトルＰの計算コストが掛け算６回、ベクトルＱの計算コストが掛け算６回であり、ｔを求めるまでの計算コストは、それぞれベクトルともう一つのベクトルの内積計算、逆数計算と、逆数との掛け算で、掛け算が１９回、割り算が１回となる。
ｕを求める為には、これに４回の掛け算が追加され、ｖの計算にも４回の掛け算が必要となる。
これに対して本発明の場合には、両端の符号付距離とｕｖ値を求めるまでに１８回の掛け算が必要となる。両端の符号付距離が同符号であればｔ＜０またはｔ＞１と同値であり、線分の有効範囲に交点が無いことが分かるので、この時点で掛け算１回と割り算１回の計算コストの節約となる。
交点のｕｖ値を求めるためには、［数７］の式（１６）といった計算が必要になるので、ｕ値を求めるまでに、１回の割り算と２回の掛け算、ｖ値を求めるまでに、さらに２回の掛け算が必要になる。但し、始点・終点のＵ値、Ｖ値がともに０未満であったり、１以上であったり、Ｕ値＋Ｖ値が１以上の場合には、交点のＵ値、Ｖ値の計算を行うことなく、交差しないという判定が可能である。
【数７】
2004053741.tif 000008
従って交点計算のステップとして、
Ｓｔｅｐ１  線分の有効区間での交差確認（ｔＶａｌｕｅ）
Ｓｔｅｐ２  交点のｕ値での有効／無効判定
Ｓｔｅｐ３  交点のｖ値での有効／無効判定
といった手順を踏むとすると、各条件のもとでの交差を行うまでに、表１に示すような計算コストがかかることが分かり、本発明の方が高い計算効率であることが分かる。
【表１】
2004053741.tif 000009
４．３  実施例
４．３．１  実施例１
図１１に、外部データの取得からＶ−ＣＡＤデータ作成までのフローを示す。図１１においては、上述した交点計算を行う前に、幾何形状（Ｓ−ＣＡＤデータ、三角形パッチ）を各セルにマッピングする処理を行った。この処理を行うことにより、交差対象線分（セルの稜線）の候補を絞り込むことができるため、計算時間を短縮し、高速化を図ることが可能となる。マッピング処理を行わない場合は、全ての線分を探索しなくてはならず、計算時間がかかるため、本実施例のように交点計算前にマッピング処理を行うことが好ましい。
図１２〜１４は、図１１の処理を行った場合の表示画面を示している。すなわち、図１２は、ＳＴＥＰ（Ｔ２）において入力する三角形の表示画面、図１３は、ＳＴＥＰ（Ｔ１３）において作成されたＶ−ＣＡＤデータの表示画像である。図１４は、図１３の一部を拡大したものであり、入力データとセル稜線の交点計算により発生したセルの切断点が表示してある。
本発明により、ベンチマークでは最大３０％程度の高速化が達成できた。
４．３．２  実施例２
図１５は、本発明の手法を形状変形処理の際の干渉チェックに応用した場合のフローである。ＳＴＥＰ（Ｕ４）において、図１１の一連の処理を行う前の前処理として、交点計算（図１１のＳＴＥＰ（Ｔ５）から（Ｔ１１）の処理）を行い、自己干渉のチックを行った。その後、図１１の一連の処理を行うことによって（ＳＴＥＰ（Ｕ５）に相当）、変形後の形状を表示することができる。図１６にその表示画像を示す。
４．３．３
上述したように、本発明の三角形と線分の交点計算方法とそのプログラムは、同一の三角形に対して異なる複数の線分との交点を求める場合に、計算時間を短縮し高速化を図ることができる等の優れた効果を有する。
なお、本発明をいくつかの好ましい実施例により説明したが、本発明に包含される権利範囲は、これらの実施例に限定されないことが理解されよう。反対に、本発明の権利範囲は、添付の請求の範囲に含まれるすべての改良、修正及び均等物を含むものである。
【図１】
2004053741.tif 000011
【図２】
2004053741.tif 000012
【図３】
2004053741.tif 000013
【図４】
2004053741.tif 000014
2004053741.tif 000015
2004053741.tif 000016
【図７】
2004053741.tif 000017
【図８】
2004053741.tif 000018
【図９】
2004053741.tif 000019
【図１０】
2004053741.tif 000020
【図１１】
2004053741.tif 000021
【図１２】
2004053741.tif 000022
【図１３】
2004053741.tif 000023
【図１４】
2004053741.tif 000024
【図１５】
2004053741.tif 000025
【図１６】
2004053741.tif 000026
【国際調査報告】
2004053741.tif 000027
2004053741.tif 000028