(57)【特許請求の範囲】
【請求項１】
ｘ軸とｙ軸の平面座標に対する値域がｚ軸として与えられる三次元座標点群を三角被覆法で近似したデータ曲面を任意の視点から見たときの隠れ線を抽出する装置であって、
視点からデータ曲面の座標点を見る視線と前記データ曲面の各エッジの交点の形態から当該曲面のエッジ上の２つの座標点ｐt，ｑtが見えるか否かを判定する手段と、
前記２つの座標点ｐt，ｑtの両方が見えないときは当該エッジを描画しないで２つの座標点ｐt，ｑtについての隠れ線追跡を終了する手段と、
前記２つの座標点ｐt，ｑtの両方が見えるときは当該エッジを描画する手段と、
前記２つの座標点ｐt，ｑtの一方が見えるときは見える座標点と他方の座標点との中間点ｒtとの間の距離が一定値以下のときに描画し、かつ中間点を一方の新たな座標点ｐtとして他方の座標点ｑtとの間で隠れ線を追跡して行く手段と、
の繰り返しによって隠れ線を抽出することを特徴とする隠れ線の抽出装置。
【請求項２】
前記２つの座標点ｐt，ｑtが見えるか否かを判定する手段は、
視点からデータ曲面を見たときの交点が格子点上又は中間になるｚ値のエッジ及び投影視線と投影エッジの交点の形態から前記エッジの近傍になる４種類の近傍エッジを定める手段と、
２つの座標点ｐt，ｑtをもつエッジを該当エッジとし、このエッジの前記近傍エッジを次のエッジとし、視線の高さｈと前記該当エッジの高さｈ1と前記次のエッジの高さｈ2の比較により判定する手段と、
によって判定することを特徴とする請求項１記載の隠れ線の抽出装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、与えられた三次元座標点群を通る曲面を任意の視点から見たときの隠れ線の抽出装置に係り、特に曲面をエッジ群で近似する三角被覆法による曲面における隠れ線の抽出装置に関する。
【０００２】
【従来の技術】
三次元座標点を（ｘi，ｙi，ｚi）で表し、ｚ値は変数ｘ，ｙに関する一値関数ｚ＝ｆ（ｘ，ｙ）で表されるとし、この関数を「データ曲面」と呼ぶ。曲面は、十分に滑らかであると仮定する。つまり、任意の自然数ｎについて、関数ｆはｎ階連続微分可能であるとする。
【０００３】
図１０に示すように、定義域を（ｘmin，ｘmax）×（ｙmin，ｙmax）とすると、一般に、与えられた座標点は、ｘ軸に関して（Ｎ−１）等分、ｙ軸に関して（Ｍ−１）等分した格子点状にとられることが多い。つまり、与えられた座標点群は、（ｘi，ｙj，ｚij）のＮ×Ｍ個の点からなり、（ｘi+1−ｘi）は一定値（ｆｏｒ  ｉ＝１，…，Ｎ）、（ｙj+1−ｙj）は一定値（ｆｏｒ  ｙ＝１，…，Ｍ）という条件を満たすものである。
【０００４】
また、ある視点からある座標点（ｘ，ｙ，ｚ）を見たデータ曲面を描画するのに、図１０に示すように、視点から曲面に至る線分（視線）がデータ曲面と交差するとき、すなわち視点から見て曲面の陰になる座標点（ｘ2，ｙ2，ｚ2）は「視点からは見えない」、データ曲面と交差しないとき、すなわち視点から見て曲面の「おもて面」になる座標点（ｘ1，ｙ1，ｚ1）は「視線から見える」というように判定してデータ曲面を描画する場合がある。
【０００５】
この描画処理には、対象となる座標点をデータ曲面上にとり、データ曲面を描画する際に、曲面の位置部が見えるかどうかの判定を「隠れ線抽出処理」として実行する。
【０００６】
【発明が解決しようとする課題】
実際の計測データで、体積（ｘ軸）と圧力（ｙ軸）の関係から温度（ｚ軸）変化が知られている事例について考えることにする。このとき、問題は、温度勾配を表現する曲面のどの部分が見えて、どの部分が見えないかを判定することである。
【０００７】
しかし、従来技術の手法を適用するとき、その前提となる「定義域は、格子点上にある」という条件は、現実的ではない。つまり、体積軸、圧力軸を均等に等分して、その測定条件のすべての組み合わせで温度を測定してデータを用意しなければならない。この条件は、不便である。
【０００８】
これら不便さを解消する方法の１つとして、データ補間がある。与えられた座標点列が、必ずしも格子点状に無い場合、データ補間を施すことで格子点上にある座標点のｚ値を推定する方法である。
【０００９】
この補間法には、近似関数、内挿、外挿といった種々の方法がある。しかし、ここで変換されたデータ点列は、必ずしも与えられたデータ点列に忠実である保証はなく、したがって、得られる隠れ線の判定は、元のデータ曲面を忠実に反映しているかどうかの保証はない。
【００１０】
この点、データ曲面をエッジ群で近似する三角被覆法によると、「定義域が格子点上にある」という制限がなくなり、等高線も元のデータ曲面を忠実に反映できることになる。この三角被覆法によるデータ曲面は、図１１に示すように、ｘ軸とｙ軸の座標は、データを取得したときの任意の間隔で格子点を定義し、この各格子点における各ｚ値間をエッジで接続した表現になる。この三角被覆法によるデータ曲面では、隠れ線の抽出もｚ値をエッジと超平面の交点として追跡、さらには補間することが可能となる。
【００１１】
本発明の目的は、三角被覆法で近似するデータ曲面の隠れ線抽出を、必要最小限の計算量にしながら確実、容易にする隠れ線の抽出装置を提供することにある。
【００１２】
【課題を解決するための手段】
本発明は、ｘ軸とｙ軸の格子点について開始格子点と終了格子点を持つｚ値のエッジと、この各エッジに対して近傍になる４種類の近傍エッジを定め、これらエッジをもつ曲面と視線との交点の形態と高さ位置から当該エッジ及び曲面が視点から見えるか見えないかを判定し、見えない部分を隠れ線として描画せず、見える部分を描画するようにしたもので、以下の装置を特徴とする。
【００１３】
（第１の発明）
ｘ軸とｙ軸の平面座標に対する値域がｚ軸として与えられる三次元座標点群を三角被覆法で近似したデータ曲面を任意の視点から見たときの隠れ線を抽出する装置であって、
視点からデータ曲面の座標点を見る視線と前記データ曲面の各エッジの交点の形態から当該曲面のエッジ上の２つの座標点ｐt，ｑtが見えるか否かを判定する手段と、
前記２つの座標点ｐt，ｑtの両方が見えないときは当該エッジを描画しないで２つの座標点ｐt，ｑtについての隠れ線追跡を終了する手段と、
前記２つの座標点ｐt，ｑtの両方が見えるときは当該エッジを描画する手段と、
前記２つの座標点ｐt，ｑtの一方が見えるときは見える座標点と他方の座標点との中間点ｒtとの間の距離が一定値以下のときに描画し、かつ中間点を一方の新たな座標点ｐtとして他方の座標点ｑtとの間で隠れ線を追跡して行く手段と、
の繰り返しによって隠れ線を抽出することを特徴とする。
【００１４】
（第２の発明）
前記２つの座標点ｐt，ｑtが見えるか否かを判定する手段は、
視点からデータ曲面を見たときの交点が格子点上又は中間になるｚ値のエッジ及び投影視線と投影エッジの交点の形態から前記エッジの近傍になる４種類の近傍エッジを定める手段と、
２つの座標点ｐt，ｑtをもつエッジを該当エッジとし、このエッジの前記近傍エッジを次のエッジとし、視線の高さｈと前記該当エッジの高さｈ1と前記次のエッジの高さｈ2の比較により判定する手段と、
によって判定することを特徴とする。
【００１５】
【発明の実施の形態】
本実施形態では、便宜上、定義域をｘ軸とｙ軸とし、値域をｚ軸とする一値関数ｚ＝ｆ（ｘ，ｙ）で説明する。
【００１６】
データ曲面の測定点は、（ｘi，ｙj，ｚij）で与えられるとして、定義域の条件ｘi＜ｘi+1（ｆｏｒ  ｉ＝１，…，Ｎ）、ｙj＜ｙj+1（ｆｏｒ  ｊ＝１，…，Ｍ）を満たすものとする。区間の長さ（ｘi+1−ｘi）や（ｙj+1−ｙj）は、必ずしも一定値でなくてもよく、データ取得時の任意の格子点間隔に合わせる。
【００１７】
実施形態の説明の前に、隠れ線の抽出のためのｚ値間を結ぶエッジ（辺）等の定義を以下に説明する。
【００１８】
（定義１）エッジ
開始格子点：（ｉ1，ｊ1）、但し、ｉ1＝１，…，Ｎ、ｊ1＝１，…，Ｍ
終了格子点：（ｉ2，ｊ2）、但し、ｉ2＝１，…，Ｎ、ｊ2＝１，…，Ｍ
交点の形態：「格子点範囲内」ｏｒ「格子点範囲外」ｏｒ「格子点上」ｏｒ「エッジ上」
交点の位置：ｚ値間距離を１とし０〜１の間
視点の距離：０〜無限大
なお、交点の形態は、図３に示すように、視点から見た三角被覆曲面の交点Ａが４つの格子点で囲まれる範囲内になるときを「格子点範囲内」、範囲外になるときを「格子点範囲外」、格子点の上になるときを「格子点上」、格子点間を結ぶエッジ上になるときを「エッジ上」とする。
【００１９】
上記の定義により、測定点の定義域から構成されるｚ値のエッジを定める。例えば、ｘ軸とｙ軸の格子点（ｉ，ｊ）を開始格子点にもつｚ値のエッジは図４に示すように、次の３種類がある。
【００２０】
場合（１）：エッジの開始（ｉ，ｊ）−終了（ｉ＋１，ｊ＋１）
場合（２）：エッジの開始（ｉ，ｊ）−終了（ｉ，ｊ＋１）
場合（３）：エッジの開始（ｉ，ｊ）−終了（ｉ＋１，ｊ）
但し、定義域の境界を越える格子点又はエッジについては考えないことにする。
【００２１】
（定義２）エッジの近傍エッジ…エッジと「交点の形態」により、図５の（ａ）〜（ｄ）に示すように分けて定義する。但し、定義域の境界を越える格子点又はエッジについては考えないことにする。
【００２２】
（１）交点の形態が「格子点範囲内」のとき、以下の４つのエッジが近傍エッジである（図５のａ）。
【００２３】
エッジ開始（ｉ，ｊ）−終了（ｉ，ｊ＋１）
エッジ開始（ｉ，ｊ）−終了（ｉ＋１，ｊ）
エッジ開始（ｉ，ｊ＋１）−終了（ｉ＋１，ｊ＋１）
エッジ開始（ｉ＋１，ｊ）−終了（ｉ＋１，ｊ＋１）
（２）交点の形態が「格子点上」のとき、以下の８つのエッジが近傍エッジである（図５のｂ）。
【００２４】
エッジ開始（ｉ−１，ｊ−１）−終了（ｉ，ｊ−１）
エッジ開始（ｉ−１，ｊ−１）−終了（ｉ−１，ｊ）
エッジ開始（ｉ−１，ｊ）−終了（ｉ−１，ｊ＋１）
エッジ開始（ｉ−１，ｊ＋１）−終了（ｉ，ｊ＋１）
エッジ開始（ｉ，ｊ＋１）−終了（ｉ＋１，ｊ＋１）
エッジ開始（ｉ＋１，ｊ）−終了（ｉ＋１，ｊ＋１）
エッジ開始（ｉ＋１，ｊ−１）−終了（ｉ＋１，ｊ）
エッジ開始（ｉ，ｊ−１）−終了（ｉ＋１，ｊ−１）
（３）交点の形態が「エッジ上」でエッジが開始（ｉ，ｊ）−終了（ｉ＋１，ｊ）のとき、以下の６つのエッジが近傍エッジである（図５のｃ）。
【００２５】
エッジ開始（ｉ，ｊ）−終了（ｉ，ｊ＋１）
エッジ開始（ｉ，ｊ＋１）−終了（ｉ＋１，ｊ＋１）
エッジ開始（ｉ＋１，ｊ）−終了（ｉ＋１，ｊ＋１）
エッジ開始（ｉ，ｊ−１）−終了（ｉ，ｊ）
エッジ開始（ｉ，ｊ−１）−終了（ｉ＋１，ｊ−１）
エッジ開始（ｉ＋１，ｊ−１）−終了（ｉ＋１，ｊ）
（４）交点の形態が「エッジ上」でエッジが開始（ｉ，ｊ）−終了（ｉ，ｊ＋１）のとき、以下の６つのエッジが近傍エッジである（図５のｄ）。
【００２６】
エッジ開始（ｉ−１，ｊ）−終了（ｉ，ｊ）
エッジ開始（ｉ−１，ｊ）−終了（ｉ−１，ｊ＋１）
エッジ開始（ｉ−１，ｊ＋１）−終了（ｉ，ｊ＋１）
エッジ開始（ｉ，ｊ）−終了（ｉ＋１，ｊ）
エッジ開始（ｉ，ｊ＋１）−終了（ｉ＋１，ｊ＋１）
エッジ開始（ｉ＋１，ｊ）−終了（ｉ＋１，ｊ＋１）
（命題３）ある座標点Ａ（ｘ，ｙ，ｚ）が与えられたとき、この座標点Ａから視点（ｘvp，ｙvp，ｚvp）へと至るｘ，ｙ平面への投影エッジの線分と任意のエッジの投影エッジとの交わり方は、図６に示す位置関係から以下の５種類しかない。
【００２７】
（１）投影エッジの線分と投影視線が並行で、交わらない（図６のａに示す投影エッジｅ3，ｅ1、但し、ｅ3とｅ1は並行となる）。
【００２８】
（２）投影エッジの線分と投影視線が並行で、２つが重なる（図６のｂに示す投影エッジｅ1）。
【００２９】
（３）投影エッジの線分の延長部分で投影視線と交わる（図６のｃに示す投影エッジｅ5の延長部分）。
【００３０】
（４）投影エッジの線分のいずれかの端点で投影視線と交わる（図６のｄに示す投影エッジｅ1の一方の端点）。
【００３１】
（５）投影エッジの線分の内部で投影視線と交わる（図６のａに示す投影エッジｅ4）。
【００３２】
（定義４）エッジの状態変数になる「交点の形態」と「交点の位置」と「視点の距離」の求め方。…上記命題３の（１）から（５）の場合について別々に定義する。
【００３３】
0003932646.tif 000002
但し、交点が（ｉ1，ｊ1）のとき、ｉ2＝ｉ1，ｊ2＝ｊ1とする。
【００３４】
交点が（ｉ2，ｊ2）のとき、ｉ1＝ｉ2，ｊ1＝ｊ2とする。
【００３５】
場合（５）交点の形態＝エッジ上
交点の位置＝ｓ
視点の距離＝ｔ
上記の（４）と（５）の場合、交点の位置ｓと視点の距離ｔは次の式で与えられる。なお、表記を簡単にするため、（ｐx，ｐy，ｐz）＝（ｘi1，ｙj1，ｚi1j1）、（ｑx，ｑy，ｑz）＝（ｘi2，ｙj2，ｚi2j2）、（ｔx，ｔy，ｔz）＝（ｘvp−ｘ，ｙvp−ｙ，ｚvp−ｚ）とおく。これらは、図７に示すように、（ｐx，ｐy，ｐz）と（ｑx，ｑy，ｑz）は、格子点（ｉ1，ｊ1）と（ｉ2，ｊ2）における格子点の座標値であり、（ｔx，ｔy，ｔz）はある座標（ｘ，ｙ）から視点へと至る線分ベクトルである。これらの関係から、
ｕ＝（ｑx−ｐx）×ｔy−（ｑy−ｐy）×ｔx
ｓ1＝（ｘ×ｔy−ｙ×ｔx）−（ｐx×ｔy−ｐy×ｔx）
ｔ1＝（ｐy−ｙ）×（ｑx−ｐx）−（ｐx−ｘ）×（ｑy−ｐy）
とおくと、交点の位置ｓ及び視点の距離ｔは次の演算で求められる。なお、エッジと視線は並行ではないため、ｕは零でない。
【００３６】
ｓ＝ｓ1／ｕ
ｔ＝ｔ1／ｕ
（定義５）ある座標点（ｘ，ｙ，ｚ）とデータ曲面ｚij＝ｆ（ｘi，ｙj）が与えられたとき、この座標点を含むエッジを場合（１）〜（５）として次のように定めると、エッジは一意に決まる。
【００３７】
場合（１）：ｘ＝ｘi、ｙ＝ｙjとなる格子点（ｉ，ｊ）があるときは、図８の４つのエッジｅ1〜ｅ4になる。
【００３８】
開始格子点：（ｉ，ｊ）
終了格子点：（ｉ，ｊ）
状態変数「交点の形態」：格子点上
状態変数「交点の位置」：格子点上（＝０）
状態変数「視点の距離」：０
場合（２）：線分（ｘi，ｙj）−（ｘi，ｙj+1）上に座標点があるような格子点（ｉ，ｊ）があるときは、図８のエッジｅ4になる。
【００３９】
開始格子点：（ｉ，ｊ）
終了格子点：（ｉ，ｊ＋１）
状態変数「交点の形態」：エッジ上
状態変数「交点の位置」：（ｙ−ｙj）／（ｙj+1−ｙj）
状態変数「視点の距離」：０
場合（３）：線分（ｘi，ｙj）−（ｘi+1，ｙj）上に座標点があるような格子点（ｉ，ｊ）があるときは、図８のエッジｅ1になる。
【００４０】
開始格子点：（ｉ，ｊ）
終了格子点：（ｉ＋１，ｊ）
状態変数「交点の形態」：エッジ上
状態変数「交点の位置」：（ｘ−ｘi）／（ｘi+1−ｘi）
状態変数「視点の距離」：０
場合（４）：４つの点（ｘi，ｙj）、（ｘi+1，ｙj）、（ｘi，ｙj+1）、（ｘi+1，ｙj+1）で囲まれる凸四辺形の内部に座標点があるような格子点（ｉ，ｊ）があるときは、図８の曲面ｚij上になる。
【００４１】
開始格子点：（ｉ，ｊ）
終了格子点：（ｉ，ｊ）
状態変数「交点の形態」：格子点範囲内
状態変数「交点の位置」：無し
状態変数「視点の距離」：０
場合（５）：上記のいずれの場合でもないとき、図８の曲面ｚijの範囲外になる。
【００４２】
開始格子点：未定義
終了格子点：未定義
状態変数「交点の形態」：格子点範囲外
状態変数「交点の位置」：無し
状態変数「視点の距離」：０
（定義６）ある座標点（ｘ，ｙ，ｚ）とデータ曲面ｚij＝ｆ（ｘi，ｙj）、視点（ｘvp，ｙvp，ｚvp）及びエッジが与えられたとき、このエッジがもつ交点が視線より上にあるか、または下にあるか、「高さの判定」を次のように定める。感覚的に言えば、この上下は、ｚ軸に関する大小関係である。
【００４３】
ここで、定義域の上限下限を（ｘmin，ｘmax）および（ｙmin，ｙmax）と略記する。例えば、ｘmin＝ｘ1、ｘmax＝ｘNである。また、値域の境界をｚminおよびｚmaxで与える。但し、値域の境界は、描画上の便宜を考えたときの表示範囲に関係する値であり、任意に与えられる。図９にはｘ−ｚ平面で視線とエッジの関係を示し、ｈtは対象とするエッジに対する視線の高さ、ｈsは対象とするエッジの高さになる。
【００４４】
場合（１）：エッジの状態変数「交点の形態」が「格子点上」のとき。
【００４５】
もし、ｈt＜ｚminならば、下限値範囲外とする。
【００４６】
もし、ｈt＞ｚmaxならば、上限値範囲外とする。
【００４７】
もし、ｈt＝ｈsならば、同位置とする。
【００４８】
もし、ｈｔ＞ｈｓならば、オーバーとする。
【００４９】
もし、ｈt＜ｈsならば、アンダーとする。
【００５０】
場合（２）：エッジの状態変数「交点の形態」が「エッジ上」のとき。
【００５１】
上記の場合（１）と同じ。
【００５２】
場合（３）：エッジの状態変数「交点の形態」が「格子点範囲内」のとき。
【００５３】
判定不能とするとする。
【００５４】
場合（４）：エッジの状態変数「交点の形態」が「格子点範囲外」のとき。
【００５５】
判定不能とするとする。
【００５６】
上記の（１）と（２）の場合、高さｈｓ，ｈｔは次の式で与えられる。なお、表記を簡単にするために、（ｐx，ｐy，ｐz）＝（ｘi1，ｙj1，ｚi1j1）、（ｑx，ｑy，ｑz）＝（ｘi2，ｙj2，ｚi2j2）、（ｔx，ｔy，ｔz）＝（ｘvp−ｘ、ｙvp−ｙ、ｚvp−ｚ）とおく。それぞれは、格子点（ｉ1，ｊ1）と（ｉ2，ｊ2）におけけ座標値、およびある座標から視点へと至る線分ベクトルである。
【００５７】
ｈs＝ｐz＋交点の位置×（ｑz−ｐz）
ｈt＝ｚ＋視点の距離×（ｚvp−ｚ）
（算法７）ある座標点（ｘ，ｙ，ｚ）とデータ曲面ｚij＝ｆ（ｘi，ｙj）が与えられたとき、この座標点から視点（ｘvp，ｙvp，ｚvp）へと至る線分が、データ曲面と交差するか否か、つまり「見える」か「見えない」かを判定する手順は以下の通りである。
【００５８】
手順１：与えられた座標点（ｘ，ｙ，ｚ）を含むエッジを（定義５）により求め、この該当エッジに対して、以下の手順２を適用する。ここで、（定義６）により、該当エッジの高さの判定結果をｈとおく。
【００５９】
手順２：該当エッジの近傍エッジで、以下の性質を満たすものを「次のエッジ」と呼ぶ。もし、そのようなエッジがない場合は、以下の手順５へ移り、判定の手順を終了する。
【００６０】
・先ず、該当エッジの近傍エッジｅ1，…，ｅk（ｋ＝４，６，８）を求める。
【００６１】
・各々の近傍エッジｅkについて、定義４によりそのエッジｅkの変数「交点の形態」、「交点の位置」、「視点の距離」を求める。
【００６２】
・ここで、近傍エッジｅｋの「交点の形態」が「格子点上」又は「エッジ上」、かつ、その「視点の距離」が、該当エッジの「視点の距離」よりも大であるものが、求める「次のエッジ」である。もしこのようなエッジが存在すれば、それは一意に決まる。
【００６３】
手順３：定義６により、該当エッジの高さの判定結果をｈ1、次のエッジの高さの判定結果をｈ2とおく。
【００６４】
場合（１）ｈ1＝同位置なら、手順５に進む。
【００６５】
場合（２）ｈ1＝ｈ2ならば、手順５に進む。
【００６６】
場合（３）場合（１）でもなく（２）でもないならば、ｈの値を格子点で置き換えて、手順５へ進み、判定の一連の手順を終了する。
【００６７】
手順４：ｈの値をｈ2の値で置き換え、また、このエッジを「次のエッジ」で置き換えて、手順２から繰り返す。
【００６８】
手順５：ここで得られるｈが、最終的な高さの判定値である。
【００６９】
ｈが格子点なら、視線はデータ曲面と交差する。このときは「見えない」。
【００７０】
ｈが同位置なら、視線はデータ曲面と一致する。このときは「見える」。
【００７１】
ｈがオーバなら、視線はデータ曲面より上にある。このときは「見える」。
【００７２】
ｈがアンダーなら、視線はデータ曲面より下にある。このときは「見える」。
【００７３】
以上までの各定義及びエッジと視線との関係の基に、以下に隠れ線抽出の実施形態を説明する。
【００７４】
（実施形態１）本実施形態は、２つの座標点ｐt＝（ｘ1，ｙ1，ｚ1）とｑt＝（ｘ2、ｙ2、ｚ2）が与えられたとき、この線分を描画するときに、隠れ線部分を抽出してその部分を除いて描画する。この処理フローを図１に示す。
【００７５】
２つの座標点ｐt＝（ｘ1，ｙ1，ｚ1）とｑt＝（ｘ2，ｙ2，ｚ2）を読み出し（Ｓ１）、視点から座標点ｐt及びｑtが見えるか否かを判定する（Ｓ２）。この判定は、算法７により行う。
【００７６】
場合（１）ｐtとｑtが共に見えないとき、この線分全体は見えないとして、描画しない（Ｓ３）。
【００７７】
場合（２）ｐtとｑtが共に見えるとき、この線分全体は見えるとして、描画する（Ｓ４）。
【００７８】
場合（３）ｐtが見えて、ｑtが見えないとき。
【００７９】
手順１：２つの座標点ｐtとｑtの中間点をｒt＝（（ｘ1＋ｘ2）／２，（ｙ1＋ｙ2）／２，（ｚ1＋ｚ2）／２）とする。もし、２つの座標点ｐtとｒt間の距離があらかじめ設定した一定値以下か否かを判定し（Ｓ５）、一定値以下ならば、手順３（Ｓ６）へ進み、分割手順を終了する。
【００８０】
手順２：座標点ｒtが見えるか否かを判定し（Ｓ７）、見えるときはｐtをｒtで置き換え（Ｓ８）、手順１を繰り返す。座標点ｒtが見えないときは、ｑtをｒtで置き換え（Ｓ９）、手順１を繰り返す。
【００８１】
手順３：最初の座標点ｐtと、ここで求めた中間点ｒtを結ぶ線分は見えるとして、描画する。中間点ｒtと最初の座標点ｑtを結ぶ線分は見えないとして、描画しない（Ｓ６）。
【００８２】
場合（４）ｐtが見えなくて、ｑtが見えるとき、上記の場合（３）でｐtとｑtを読み替えて、中間点ｒtを求める（Ｓ１０）。
【００８３】
このような処理により、２つの座標点間の線分のうち、ｐt−ｒt間は描画せず、ｒt−ｑt問は描画する。そして、この処理を中間点を一方の座標点として他方の座標点を２つの新たな座標点として追跡して行く隠れ線処理を行う。
【００８４】
（実施形態２）本実施形態は、データ曲面ｚij＝ｆ（ｘi，ｙj）の定義域と値域に境界を定めて、与えられた座標点（ｘ，ｙ，ｚ）から視点（ｘvp，ｙvp，ｚvp）へと至る視線が境界に到達したとき、その時点で、見えるまたは見えないの判断をする。但し、６面の境界面は、透明であるとする。図２に処理フローを示す。
【００８５】
手順１：与えられた座標点（ｘ，ｙ，ｚ）を含む該当エッジを求める（Ｓ１１）。前記の算法７の手順１と同じ。
【００８６】
手順２：手順１で求めた該当エッジの近傍エッジから次のエッジを求める（Ｓ１２）。前記の算法７の手順２と同じ。
【００８７】
手順３：前記の定義６にしたがって、視点の高さｈ及び該当エッジの高さの判定結果ｈ1、次のエッジの高さの判定結果ｈ2を求める（Ｓ１３）。
【００８８】
場合（１）ｈ2＝上限範囲外、かつｈ＝アンダー、かつｚvp＞ｚならば手順５（Ｓ１４）へ進み、判定の一連の手順を終了する。
【００８９】
場合（２）ｈ2＝下限範囲外、かつｈ＝オーバ、かつｚvp＜ｚならば、手順５へ進み、判定の一連の手順を終了する。
【００９０】
場合（３）ｈ1＝同位置なら、手順５に進む。
【００９１】
場合（４）ｈ1＝ｈ2ならば、手順５に進む。
【００９２】
場合（５）場合（１）でもなく（２）でもないならば、ｈの値を格子点で置き換え（Ｓ１５）、手順５へ進み、判定の一連の手順を終了する。
【００９３】
手順４：前記の算法７の手順４と同じに、ｈの値をｈ2の値で置換し、次のエッジに置き換え、手順２を繰り返す。
【００９４】
手順５：前記の算法７の手順５と同じに、ｈが格子点上なら「見えない」、ｈが同位置なら「見える」、ｈがオーバーなら「見える」、ｈがアンダーなら「見えない」とし、「見える」場合はその描画を行う（Ｓ１４）。
【００９５】
このように、エッジの両端が見えるか否かの判定は、視線の高さｈと該当エッジの高さｈ1と次のエッジの高さｈ2の比較により判定していく。
【００９６】
（実施形態３）本実施形態は、データ曲面ｚij＝ｆ（ｘi，ｙj）の定義域と値域に境界を定めて、与えられた座標点（ｘ，ｙ，ｚ）から視点（ｘvp，ｙvp，ｚvp）へと至る視線が境界に到達したとき、その時点で、見える又は見えないの判断処理をする。但し、６面の境界面のうち、データ曲面と交わる点よりｚ軸に関して下側の部分は不透明であるとする。上側の部分は透明であるとする。本実施形態は、実施形態２とでは６面の境界面の下側を不透明とするため、手順３が異なる。
【００９７】
手順１：前記の算法７の手順１と同じ。
【００９８】
手順２：前記の算法７の手順２と同じ。
【００９９】
手順３：前記の定義６に従って、視点の高さｈ及び該当エッジの高さの判定結果ｈ1、次のエッジの高さの判定結果ｈ2を求める。
【０１００】
場合（１）ｈ2＝上限範囲外、かつｈ＝アンダー、かつｚvp＞ｚならば、ｈの値を格子点で置き換えて手順５へ進み、判定の一連の手順を終了する。
【０１０１】
場合（２）ｈ2＝下限範囲外、かつｈ＝オーバー、かつｚｖｐ＜ｚならば、ｈの値を格子点で置き換えて手順５へ進み、判定の一連の手順を終了する。
【０１０２】
場合（３）ｈ1＝同位置なら、手順５に進む。
【０１０３】
場合（４）ｈ1＝ｈ2ならば、手順５に進む。
【０１０４】
場合（５）場合（１）でもなく（２）でもないならば、ｈの値を格子点で置き換えて、手順５へ進み、判定の一連の手順を終了する。
【０１０５】
手順４：前記の算法７の手順４と同じ。
【０１０６】
手順５：前記の算法７の手順５と同じ。
【０１０７】
【発明の効果】
以上のとおり、本発明によれば、ｘ軸とｙ軸の格子点について開始格子点と終了格子点を持つｚ値のエッジと、この各エッジに対して近傍になる４種類の近傍エッジを定め、これらエッジをもつ曲面と視線との交点の形態と高さ位置から当該エッジ及び曲面が視点から見えるか見えないかを判定することで隠れ線を抽出するようにしたため、以下の効果がある。
【０１０８】
（１）エッジとその近傍エッジを定義したため、必要最小限の計算量で隠れ線を抽出できる。
【０１０９】
（２）各エッジと視線との交わり方とそれぞれの高さ比較から２つの座標点を結ぶ線分が見える、見えないの判定をするため、隠れ線抽出処理が確実、容易になる。
【０１１０】
（３）境界面が透明な場合と不透明な場合のいずれの場合でも隠れ線抽出と描画ができる。
【図面の簡単な説明】
【図１】本発明の実施形態を示す隠れ線追跡処理フロー。
【図２】実施形態における視点から見える／見えないの判定処理フロー。
【図３】三角被覆法により近似した曲面と視線の交点の形態。
【図４】３種類のエッジ。
【図５】４種類の近傍エッジ。
【図６】エッジと投影視線の交わり方。
【図７】視線とエッジの交点位置と距離。
【図８】座標点とエッジの位置関係。
【図９】ｘ−ｚ平面上の視線とエッジの関係。
【図１０】曲面と隠れ線の説明。
【図１１】三角被覆法による曲面。
【図１】
0003932646.tif 000003
【図２】
0003932646.tif 000004
【図３】
0003932646.tif 000005
【図４】
0003932646.tif 000006
【図５】
0003932646.tif 000007
【図６】
0003932646.tif 000008
【図７】
0003932646.tif 000009
【図８】
0003932646.tif 000010
【図９】
0003932646.tif 000011
【図１０】
0003932646.tif 000012
【図１１】
0003932646.tif 000013