ソリッド／サーフェースモデルから外形線を抽出する方法及びコンピュータソフトウエアプログラム
【解決課題】 ３次元オブジェクトの外形線を、より少ないコンピュータ資源で高品質に抽出できる方法を提供する。
【解決手段】 ソリッド／サーフェースモデル３次元オブジェクトの３次元形状データを２次元に投影処理し、当該ソリッド／サーフェースモデルの２次元シルエット線を求める工程と、前記３次元形状データを２次元に投影して画像処理し、２次元描画領域の外形を求める工程と、前記で求めた２次元描画領域の外形に基づいて前記２次元シルエット線から当該ソリッド／サーフェースモデルの２次元外形線候補となるシルエット線を絞りこむ工程と、前記各外形線候補のシルエット線に基づき、前記描画領域を囲むポリラインによる閉ループを生成し、当該閉ループを構成するポリラインを前記ソリッド／サーフェースモデルの外形線として特定する工程と、を有する。
【解決手段】 ソリッド／サーフェースモデル３次元オブジェクトの３次元形状データを２次元に投影処理し、当該ソリッド／サーフェースモデルの２次元シルエット線を求める工程と、前記３次元形状データを２次元に投影して画像処理し、２次元描画領域の外形を求める工程と、前記で求めた２次元描画領域の外形に基づいて前記２次元シルエット線から当該ソリッド／サーフェースモデルの２次元外形線候補となるシルエット線を絞りこむ工程と、前記各外形線候補のシルエット線に基づき、前記描画領域を囲むポリラインによる閉ループを生成し、当該閉ループを構成するポリラインを前記ソリッド／サーフェースモデルの外形線として特定する工程と、を有する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ソリッド／サーフェースモデルから外形線を抽出する方法及び、その方法を実施するためのコンピュータソフトウエアプログラムに関する。
【背景技術】
【０００２】
近年、製造業などで３次元ＣＡＤ／ＣＡＭシステム等の普及が進み、３次元データを設計プロセスだけではなく、下流工程の業務プロセスで利用するシーンが増えてきている。
【０００３】
設計プロセス以外で３次元モデルを活用する方法の一つとして、３次モデルから２次元ベクトルデータを生成し、イラスト化するものがある。これによれば、人手によりマニュアル等の挿絵を作成する用途に３次元モデルから自動的に生成した２次元ベクトルデータを利用することが可能となる。また、生成されたベクトルデータを編集ソフトで２次加工し、容易に付加価値を付けることも可能である。
【０００４】
３次元モデルから２次元イラスト図を生成する手法としては、一般的に、スキャンラインアルゴリズム及びＺバッファ法（非特許文献１）を併用して線データを取り出す手法が知られている。しかし、この手法で出力した２次元データにおいては、線群を任意に出力しているだけのものが多く、編集ソフト等でペイントする際に、閉領域が閉領域として認識されずに意図どおりにペイントできないといった問題がある。特に操作説明書や組み立てマニュアル等のマニュアル類で利用されるイラスト図の生成では２次元データ全体の領域にわたって色を塗る用途が最低限必要である。しかし、一般には閉領域を意識してベクトルデータが生成されるわけではないため、ベクトルデータにペイントを施す場合、編集ソフト側で閉領域を構成すると思われる線群を順番に選択し、これを閉領域化するというかなり細かい作業工程が必要となっている。
【０００５】
一方、閉領域を生成するための他の手法として、Freemanのチェインコード（非特許文献２）等を用い、画像データから外形画素を取り出し、それを snakes（非特許文献３）などにより曲線化する方法がある。しかしながら、線を抽出するための元となるデータに画像を用いているため、テクニカルイラストといった精度の求められる用途には利用することはできない。
【０００６】
また、一般的に、３次元モデルから２次元ベクトルデータを正確に生成する場合には、まず、曲面をポリゴン分割し、稜線を示すポリゴンの境界線に対し、面の位置関係を考慮した陰線処理手法を施すことが必要になる。２次元ベクトルデータを生成する技術としては、Linlinら（非特許文献４）の手法は色情報を利用して特徴線を求めているが、この手法も元となるデータは画像データであり、精度を求められる用途には適さない。また、渡辺ら（非特許文献５）の手法は２次元ベクトルデータを取りだす手法ではないが、ポリゴンメッシュから稜線の接続情報を利用して、特徴線を特定する手法である。渡辺らの手法は、３次元データ上で面稜線や、面の端点を特定することは可能であるが、２次元化した図形にはそのままでの利用は不可能である。
【０００７】
他に有効な手段の１つとして、Ｚバッファ法（非特許文献１）の利用例が挙げられる。Ｚバッファ内の２次元空間は一般に、離散的距離でのみ定義可能な距離空間を用いる。複数の要素が、１つの画素内に現れる場合、離散的距離を用いて外形線を特定することは、困難な問題である。例えば図１８では、２本の稜線が近接しており、1つの画素内に含まれている様子である。
【０００８】
このような問題を解決する方法として、画素の解像度を上げることが考えられるが、メモリの消費量・処理速度とトレードオフになる。また、ポリゴンから抽出したポリラインに基づいて、高品質な外形線を抽出する場合には、ポリゴン分割の精度を上げることも必要になるが、こちらメモリの消費量・処理速度とトレードオフになる。
【０００９】
この発明は、このような事情に鑑みてなされたものであり、少ないコンピュータ資源で３次元グラフィックデータから高精度な外形線を抽出するための方法を提供することを目的とするものである。
【００１０】
なお、本願発明と関連する先行特許出願としては下記のものがある。
【００１１】
まず、特許文献１（特開2007-128173号公報 「CADを用いた面積算出方法」）には、外形線を抽出してからその外形線に囲まれる面積を求める方法が開示されている。しかしながら、この発明は、複数の外形線候補からオペレータが手動で正しい線を１以上入力する必要があるアルゴリズムが必須の構成要素であり、その分オペレータに熟練が要求されるという欠点がある。
【００１２】
特許文献２（特開平7-249053号公報 「CAD を用いた投影面積算出方法」）に開示された発明は、上記非特許文献１と同様に外形線を抽出してからその面積を求めるものである。この手法の場合、３次元データを適当な間隔の平面で切断し、その複数の断面上の点をひとつの平面に投影後、頂点を接続することで外形線を求めている。しかしながら、この手法の場合は、３次元データ上にサンプル点を求めてそのサンプル点を補間した外形線を求めていることとなる為、データ精度が離散的になり、外形線の精度が劣る欠点がある。
【００１３】
【特許文献１】特開2007-128173号公報 「CADを用いた面積算出方法」
【特許文献２】特開平7-249053号公報 「CAD を用いた投影面積算出方
【非特許文献１】Ｄ．シェレイナー他（D. Shreiner, M. Woo, J. Neider, and T. Davis）著, "Opengl Programming Guide: The Official Guide to Learning Opengl, Guide 5 edition." Addison-Wesley Professional, 2005.
【非特許文献２】Ｈ．フリーマン（H. Freeman）著: "Computer Processing of Line-Drawring Images", Computing Surveys, Vol.6, No.3, pp313-321, 1991.
【非特許文献３】Ｍ．カス他（M. Kass, A. Witkin, D. Terzopoulos）著, "Snakes: Active Conour models, " Int. J. Comput. Vision., Vol.1, No.3, pp.321-331, 1988.
【非特許文献４】リンリン他（Linlin Jing, Kohe Inoue, Kiichi Urahama）著,"Generationg, Illustration Images with Isoluminant Colors, IWAIT 2006 pp575-596, 2006.
【非特許文献５】渡辺大地、千代倉弘明著:任意三角形メッシュからの特徴稜線抽出, 電子情報通信学会論文誌D-II Vol.J83-D-II No.5, pp. 1344-1352, 2000 年5 月.
【発明の開示】
【課題を解決するための手段】
【００１４】
上記課題を解決するため、本発明の第１の主要な観点によれば、ソリッド／サーフェースモデル３次元オブジェクトの３次元形状データを２次元に投影処理し、当該ソリッド／サーフェースモデルの２次元シルエット線を求める工程と（シルエット線生成部）、前記３次元形状データを２次元に投影して画像処理し、２次元描画領域の外形を求める工程と（画像処理部）、前記で求めた２次元描画領域の外形に基づいて前記２次元シルエット線から当該ソリッド／サーフェースモデルの２次元外形線候補となるシルエット線を絞りこむ工程と（外形線候補絞り込み部）、前記各外形線候補のシルエット線に基づき、前記描画領域を囲むポリラインによる閉ループを生成し、当該閉ループを構成するポリラインを前記ソリッド／サーフェースモデルの外形線として特定する工程と（外形線出力部）を有することを特徴とする方法が提供される。
【００１５】
このような構成によれば、３次元オブジェクトの２次元シルエット線を画像処理を利用して絞り込むようにしたから、前記３次元オブジェクトの外形線を少ないコンピュータ資源で効率良くかつ高品質で抽出することができる。
【００１６】
ここで、この発明の１の実施形態によれば、前記２次元描画領域の外形を求める工程は、形状が描画されている画素と、非描画の画素とを区別可能にメモリ上にプロットし、注目する画素とその８近傍の画素とを反時計／時計回りで比較し、形状が描画されている画素を発見した場合は、その画素を次の注目する画素として逐次追跡を行い、最初に注目した画素を検出するまで検出を続けることで、閉じた描画領域を特定し、それにより描画領域の外形を特定するものである。
【００１７】
また、他の１の実施形態によれば、前記２次元外形線候補となるシルエット線を絞り込む工程は、描画領域の外形を構成する画素の近傍にあるシルエット線を外形線候補として絞り込むものである。
【００１８】
また、さらなる他の１の実施形態によれば、前記外形線を特定する行程は、そのシルエット線を挟む領域のどちら側に描画領域があるかを特定する情報を求める工程をさらに有し、そのシルエット線のどちら側に描画領域があるかの情報に基づき、前記多数のシルエット線から２次元外形線候補となるシルエット線を絞りこむ工程を有するものである。この場合、前記シルエット線を挟む領域のどちら側に描画領域があるかを特定する情報を求める工程は、前記外形線候補のシルエット線に関する交線計算を行い、すべての線分を交点で切断し、その線分およびその線分の頂点にそれらの位置を特定する情報とそのどちら側に描画領域を示すベクトル情報を付加するものであることが望ましい。
【００１９】
さらなる他の１の実施形態によれば、前記外形線を特定する行程は、前記各外形線候補が複数競合する場合、各外形線候補の位置関係に基づいて外形線候補から外形線を特定する工程を有するものである。この場合、頂点から伸びる外形線候補が３以上あるときには、同じ側に描画領域を有する１組の外形線候補を外形線として特定するものである。また、同じ側に描画領域を有する外形線候補が複数組あるときには、描画領域が最大となる組をその頂点に対する１組の外形線候補として出力するものであることが好ましい。また、上記行程は、外形線候補のうち、閉ループを構成する外形線候補を外形線として特定する工程であることがさらに望ましい。
【００２０】
この発明のさらなる他の１の実施形態によれば、この方法はさらに、前記外形線を特定する工程により生成されたポリラインの外形線を曲線に近似する工程を有するものである。この場合、前記曲線に近似する工程は、外形線候補を求める際に、３次元ソリッド／サーフェースモデル中の、前記外形線候補に対応するポリゴンの法線ベクトルを取得し、各外形線候補に対応付けて記憶する工程と、この法線ベクトルから、外形線の接線ベクトルを求める工程と、前記で求めた接戦ベクトル同士を比較することで、接続する複数の外形線が同一の曲線であるかを判断しグループ化し、グループ化したポリラインの頂点と、頂点における接戦ベクトルを求める工程と、上記グループ化したポリラインの頂点と頂点における接線ベクトルに基づいて３次ベジェの複合曲線を生成する工程とを有するものであることが好ましい。
【００２１】
また、この発明の第２の主要な観点によれば、コンピュータハードウエアに読み込まれ実行されることでソリッド／サーフェースモデル３次元オブジェクトの２次元外形線を抽出するコンピュータソフトウエアプログラムであって、前記コンピュタハードウエアに、前記ソリッド／サーフェースモデル３次元オブジェクトの３次元形状データを２次元に投影処理し、当該ソリッド／サーフェースモデルの２次元シルエット線を求めさせる指令を発するシルエット線生成部と、前記３次元形状データを２次元に投影して画像処理し、２次元描画領域の外形を求させる指令を発する画像処理部と、前記で求めた２次元描画領域の外形に基づいて前記２次元シルエット線から当該ソリッド／サーフェースモデルの２次元外形線候補となるシルエット線を絞りこませる指令を発する外形線候補絞り込み部と、前記各外形線候補のシルエット線に基づき、前記描画領域を囲むポリラインによる閉ループを生成し、当該閉ループを構成するポリラインを前記ソリッド／サーフェースモデルの外形線として特定させる指令を発する外形線出力部とを有するコンピュータソフトウエアプログラムが提供される。
【００２２】
この第２の観点による発明によれば、前記第１の観点に係る方法を実施することができる。
【００２３】
この発明の上記した以外の特徴及び顕著な効果は、以下の発明の詳細な説明の項及び図面を参照することにより、当業者にとって容易に理解することができる。
【発明を実施するための最良の形態】
【００２４】
以下、この発明の最良の実施形態をこの明細書に添付した図面を参照して説明する。
【００２５】
図１は、この発明の実施形態を示す外形線抽出システム１を示す概略構成図である。
【００２６】
このシステム１は、ＣＰＵ２、ＲＡＭ３、モデム等の通信デバイス４、入出力装置５（ディスプレイ６、キーボード７、マウス等）が接続されてなるバス９に、データ格納部１０およびプログラム格納部１１が接続されてなる。
【００２７】
前記データ格納部１０およびプログラム格納部１１は、この実施形態では、ハードディスクなどの固定式記憶媒体で構成されており、これらに格納された各データおよびプログラムは、前記ＲＡＭ３上に呼び出されて前記ＣＰＵ２によって実行されることで、この実施形態の機能を発揮する。
【００２８】
前記プログラム格納部１１には、３次元オブジェクト空間制御部１３と、３次元オブジェクト操作部１４と、描画処理部１５と、オブジェクト操作情報入力部１６と、シルエット線生成部１７と、シルエット線情報付加部１８と、外形線候補絞り込み部１９と、外形線特定部２０と、ポリライン曲線化部２１とが格納されている。
【００２９】
またデータ格納部１０には、３次元グラッフィクデータ２３と、外形線候補抽出用画像処理メモリバッファ２４と、処理後の２次元外形線データ２５とが格納される。
【００３０】
以下、この装置の構成及び機能を、その処理動作と共に、図２に示すフローチャートを参照しつつ説明する。図２中の符合Ｓ１〜Ｓ１４は、以下の説明中における各ステップＳ１〜ステップＳ１４に対応する。
【００３１】
３次元グラフィックデータの前処理
まず、ステップＳ１で外形線生成制御情報の取得が行われる。
【００３２】
このステップＳ１においては、まず、３次元オブジェクト空間制御部１３が、３次元オブジェクト操作部１４の指令に基づき、３次元形状データ２３をＣＡＤカーネルに読み込む。そして、前記描画処理部１５が前記ディスプレイ７上に上記３次元グラフィックスデータ２３をレンダリングし、前記３次元グラフィックデータに係る３次元オブジェクトをディスプレイ７上に表示する。図３は、その表示例である。
【００３３】
ここで、ユーザは、例えばマウスポインタ等からなるオブジェクト操作情報入力部１６を操作することで、前記３次元オブジェクト操作部１４を介し、ディスプレイ７上に表示される３次元オブジェクトの姿勢を操作することができる。たとえば、３次元オブジェクトの回転、倍率表示、視点変更等の操作を行うことができる。
【００３４】
このようにして、外形線を取り出すための３次元オブジェクトの姿勢や視点が決まると、描画対象となっている面や稜線の情報が前記空間制御部１３により取得され外形線生成制御情報として出力されることになる。図４は、この状態を示す概念図である。
【００３５】
ついで、ステップＳ２〜Ｓ６で、前記シルエット線生成部１７が、前記外形線生成制御情報に基づいて、３次元グラフィックモデルのシルエット線を取得する。
【００３６】
これらのステップＳ２〜Ｓ６を説明する前に、まず、「外形線」及び「シルエット線」の概念について説明する。
【００３７】
この明細書で「外形線」とは、図５に２６で示すように、２次元空間においての描画領域と非描領域の境界線であると定義される。一方、「シルエット線」とは３次元モデルの可視な部分と不可視な部分の境界線と定義される。例えば、図４に示すような複雑な形状の３次元オブジェクトの場合、突起部分の裏側は不可視な部分となるから、シルエット線は、図５で示す外形線の描画領域２７内に本来多数存在していることになる。したがって、外形線２６は必ず物体のシルエット線から生成され、その部分集合であるということができる。
【００３８】
図６Ａ〜６Ｄは、その概念を分かりやすく示す模式図である。ここで、図６Ａは処理対象の３次元オブジェクト２８、図６Ｂはポリゴン分割を経て特定された線分群、図６Ｃはその線分群から特定されたシルエット線、図６Ｄはシルエット線から絞り込みを経て特定された外形線をそれぞれ表すものである。
【００３９】
この処理で最終的に得たい図形は、図６Ｄに示すような閉ループ・ポリラインからなる外形線で囲まれた図であり、この発明の最も重要な特徴は、図６Ｃに示したシルエット線から図６Ｄの外形線を自動的に求めることにある。
【００４０】
上記シルエット線を得るため、まず、３次元オブジェクト空間制御部１３が前記外形線生成制御情報に基づいて３次元オブジェクト情報（ソリッド及び／又はサーフェースモデル）を取得し（ステップＳ２）、ついで、ポリゴン分割を行う（ステップＳ３）。また、同時に、前記ポリゴンを構成する境界線を分離する。このことで、ポリゴンを構成する各境界線が、始点と終点を持つ線分に分離される。
【００４１】
次に、ステップＳ４で、Ｚバッファ法を用いた陰線処理を行い、見えない位置に隠れた線分（不可視線分）を処理対象から除去する。これにより図６Ｂに示すような結果が得られる。
【００４２】
シルエット線は、このように見える位置にある線分（可視線分）のうち、３次元モデルの可視な部分と不可視な部分を分ける境界線ということであるから、ステップＳ５で、シルエット線生成部１７が隣り合うポリゴン同士の関係から上記の条件を満たす線分をシルエット線として特定する。
【００４３】
以下、このように特定されたシルエット線から、実際の外形線を求めることになるが、前述したように、図４のような実際の３次元グラッフィクモデルの場合、シルエット線は多数であり、すべてを外形線の候補として処理し、最終的に図５に示すような外形線２６を得ようとすると、膨大なコンピュータ資源が必要となり、処理に時間もかかる。
【００４４】
そこで、この発明の方法では、以下のステップを実行する。
【００４５】
（１）シルエット線から画像処理によって外形線候補を絞り込む（ステップＳ６〜Ｓ１１）。
【００４６】
（２）絞り込まれたシルエット線（外形線候補）を閉ループ処理することで、外形線となるポリラインを特定する（ステップＳ１１〜Ｓ１３）。
【００４７】
（３）外形線を構成するポリラインを曲線化する（ステップＳ１４）。
【００４８】
このことで、少ないコンピュータ資源でかつ、３次元グラフィックデータから、自動的に閉ループを構成する外形線を抽出することができることになる。
【００４９】
以下、まず、外形線となるポリラインの取り出しを説明する。ついで、形線となるポリラインを曲線化する手法について述べていく。
【００５０】
シルエット線からの外形線の絞り込み
まず、本手法を利用する前処理として、ポリゴンデータからのＺバッファの構築と、Ｚバッファの画素に描画をした要素IDを格納するメモリバッファ２４の生成はすでに済んでいるものとする。
【００５１】
以下、本手法の手順を説明する。
【００５２】
シルエット線の取り出し
前述したように、図６Ｃは、３次元オブジェクト２７から取り出されたシルエット線を示すものである。
【００５３】
繰り返しになるが、一般に、シルエット線は、３次元モデルの可視な領域と不可視な領域の境界を示す線分なので、多数のシルエット線が外形線で囲まれる描画領域内に存在することがある。特に、図４に示すように、実際の３次元グラフィックの場合、このようにして特定されるシルエット線は膨大な数になるため、まず外形線の対象となるシルエット線を絞り込む必要がある。
【００５４】
シルエット線の向きを特定
したがって、ステップＳ５で特定されたシルエット線から、ステップＳ６〜Ｓ１０で外形線候補を絞り込む。
【００５５】
まず、シルエット線情報付加部１８が、線分を挟むどちら側の領域が可視であるかの情報を、ステップＳ６で設定する。この場合、まず、隣り合う２つのポリゴンが同じ辺を共有している場合、「共有エッジ」と表すことにすると、図７で可視ポリゴンαの外形線となる線分が、この線の裏側にある不可視ポリゴンβとの共有エッジとなっている。このように共有エッジの両側の面の可視・不可視性を利用して、外形線で囲まれた領域の内側方向を示す情報を外形線（共有エッジ）に設定する。
【００５６】
具体的には、外形線を表すポリゴンエッジが共有エッジの場合、共有エッジを境界とする可視となるポリゴンαにおいて、共有エッジの頂点となっていない頂点Ａのある向きを、外形線に対して描画が行われている向きとして、共有エッジに設定する。図７において、太い線の部分を外形線とする、前述した、頂点Ａのある向きを描画領域として外形線に設定するとは、線分Ｐ１−Ｐ２に対して、これと垂直なベクトルであり、Ｐ３（Ａ）側に向かうベクトル（Ｖ）を保存するということである。
【００５７】
ここで、
ＥＶ３＝(Ｐ３−Ｐ２）/｜Ｐ３−Ｐ２｜
ＥＶ１＝(Ｐ２−Ｐ１）/｜Ｐ２−Ｐ１｜
と表す。
【００５８】
Ｅｖ１をＰ１を中心に時計回りにΠ／２回転したベクトルをＥｖ２とすると、Ｐ３の方向を示すベクトルＶは式（１）、（２）のようになる。
【００５９】
Ｖ＝Ｅｖ２ ｉｆ（Ｅｖ２＊Ｅｖ３>＝０） （１）
Ｖ＝−Ｅｖ２ ｉｆ（Ｅｖ２＊Ｅｖ３<０） （２）
ソリッドモデルでは必ず共有エッジを有するが、サーフェスモデルの場合、共有エッジが存在しないものもある。その場合、シルエット線を示すエッジをもつポリゴンのエッジを共有エッジ考えることにより同一の処理を行うことができる。
【００６０】
上記の操作を行うことで、すべてのシルエット線に対し、共有エッジのどちら側に形状が存在するかを得ることができる。
【００６１】
したがって、ステップＳ６で、前記シルエット線情報付加部１８が、すべてのシルエット線に対してこのベクトルの情報を計算して付加する。
【００６２】
シルエット線から外形線候補を選定
次に、ステップＳ７で、前記外形線候補絞り込み部１９がシルエット線の線分ＩＤを格納するメモリバッファと、同一のサイズの２値（０／１値）のメモリバッファ２４をハードディスクに生成する。（形状が描画されている画素を１、非描画の画素を０とする。）
【００６３】
ついで、ステップＳ８で、２値で表わされたＺバッファから画素に基づいて外形線を生成する。この方法を示したのが、図８Ａ〜８Ｆである。
【００６４】
すなわち、図８Ａに示すようなシルエット線を処理対象とする場合、図８Ｂが線分ＩＤを格納するメモリバッファ、図８Ｃが２値のメモリバッファである。ついで、この２値のメモリバッファ（図８Ｃ）を処理対象として、注目する画素とその８近傍の画素とを半時計回りで比較し、値が１の画素を発見した場合は、その画素を次の注目する画素として逐次追跡を行い、最初に着目した画素を検出するまで検索を続けることで閉じた領域を生成する。図８Ｄは閉じた領域を構成する画素のマーキングを示す図である。ついで、画素に基づいた外形線の８近傍に相当するメモリバッファを逐次追跡することにより、外形線となる線分を含む画素を特定する（図８Ｅ、ステップＳ８）。
【００６５】
そしてこのような画像処理の結果と、シルエット線とを比較し、画像処理で示される外形に最も近いシルエット線を、外形線候補として特定する。具体的には、ステップＳ５で特定されたシルエット線を上記画像処理された外形線上に２次元投影し（ステップＳ９）、画像処理による外形線とこの２次元投影されたシルエット線から、外形線に最も近い位置に存在するシルエット線を特定する（ステップＳ１０）。このことによって特定されたシルエット線が外形線の候補として出力される。
【００６６】
ここで、本発明が従来の技術と異なるのは、このような画像処理を外形線そのものを特定するために行うのではなく、シルエット線から外形線候補を絞り込む目的で使用する点である。実際の外形線の特定は、後に説明するステップＳ１１〜Ｓ１３で行われる。
【００６７】
外形線候補からの選択
次に、ステップＳ１１〜Ｓ１３にて、外形線同士を連結する頂点の接続位置関係を表す構造を構築する。
【００６８】
このために、ステップＳ１１で、外形線候補となったポリラインを２次元化したものに対して交線計算を行い、すべての線分を交点で切断する。その後以下の属性情報をそれぞれの頂点、線分に対し付加する。
【００６９】
以下は、この実施形態にてポリラインに付加する外形線抽出用のデータ構造である。
頂点情報：
・頂点座標
・頂点に接続する線分のインデックス
・[頂点位置での可視側の曲面の法線ベクトル]
・[頂点位置での非可視側の曲面の法線ベクトル]
線分情報：
・線分の視点側の頂点インデックス
・線分の終点側の頂点インデックス
・線分に対して領域の内側を表す方向
【００７０】
次に、外形線特定部２０は、ステップＳ１２で、外形線の候補となるポリラインがある頂点から複数本伸びている場合に、描画領域と非描画領域の境界線となる線を特定し、正しい外形線を特定する。すなわち、前記で着目した線分の片側が描画領域、もう片側が非描画領域という特徴を利用して意図する線分を特定する。この実施形態ではまず、ある頂点から伸びている複数本の線分のうち、隣接する線分の描画領域の方向が逆の場合に、そのペアが外形線を示す２本の線分であると判断する。すなわち、ステップＳ６で求めた描画領域を示す方向ベクトルが逆を向いているペアを特定すればよい。
【００７１】
もしこのようなペアが複数存在する場合は、次に示す方法で描画領域が最大となるペアを特定する。図９Ａ，Ｂは、頂点Ａにおいて、隣接する線分の描画領域の方向が逆のペアが複数存在する場合を示している。Ｅｄ０、Ｅｄ１、Ｅｄ２、Ｅｄ３の４本の線分が１つの頂点に接続されている。これらの線分のうちで、描画領域を示す方向ベクトルが逆を向いているペアは、Ｅｄ０・Ｅｄ３と、Ｅｄ１・Ｅｄ２の２つである。この場合、描画領域が最大となるＥｄ０・Ｅｄ３のペアが求めるペアとなり、Ｅｄ１・Ｅｄ２は不要な外形線ということになる。
【００７２】
また、このステップＳ１２では、線分の端点に接続する線分のインデックス数が２つにならないもの（すなわち、どの線分にも接続されていないもの）を線分情報から削除する処理も行う。図１０Ａ，Ｂは、この例を示したものである。図１０Ａでは、線分Ｅｄ３の端点Ｖｘ２及び線分Ｅｄ４の端点Ｖｘ５がそれに相当するから、各線分Ｅｄ３，Ｅｄ４は、不要な枝葉の外形線であるとして除去される。
【００７３】
この後、ステップＳ１４で、再構成したポリラインの頂点・線分情報からポリラインの逐次追跡を行い、最初に選んだ頂点に戻るグラフが存在するものを、閉曲線をなすポリラインとして特定する（図１０Ｂ）。この追跡をすべてポリラインについて行うことで、複数の閉曲線が存在する場合でも発見は可能となる。
【００７４】
ポリラインの曲線化
上記したステップで求めた外形線は折線状のポリラインであるので、この実施形態においては、以下のステップで曲線化する。
【００７５】
具体的には、ステップＳ１３までで生成したポリラインに接線ベクトル等を追加することで３次ベジェの複合曲線を生成する。このために、同一の曲線となる区間を定義し、その区間の点列、接線ベクトルを利用して曲線補間を行う。
【００７６】
以下では特に断りがない限り、法線ベクトルとはポリゴン平面の法線ではなく、元曲面の法線ベクトルを表すことにする。
【００７７】
ステップ１４−Ａ
シルエット線に接線ベクトルを付加するために、３次元オブジェクトの各ポリゴンの法線ベクトルを利用する。具体的には、前記ステップＳ６（図７）において共有エッジを処理する際に、可視ポリゴン及び非可視ポリゴンの元曲面の法線ベクトルも合わせて保存しておく。
【００７８】
ステップ１４−Ｂ
このステップでは、ステップＳ１３にて求めた外形線となるポリラインに対し、ステップ１４−Ａで保持している３次元の法線ベクトルを対応付ける。つまり各ポリラインの両端点での曲面の法線ベクトルが外形線情報に追加されることになる。この状態を示したのが、図１１Ａ、Ｂである。すなわち、外形線のもとになるシルエット線は、可視面と非可視面の境界であるため、線分の視点及び終点において、図１４Ｂに示すように、それぞれ少なくとも２つの面の法線ベクトルが存在するはずである。この情報を外形線（シルエット線）の始点・終点情報に付加する。
【００７９】
ステップ１４−Ｃ
このステップでは、シルエット線の端点が先に行われた陰線処理等によって現れていない場合の補完処理を行う。
【００８０】
すなわち、前記ステップ１４−Ｂの処理は、外形線が生成元となるポリゴンエッジに一致した場合にのみ可能となる。しかし、陰線処理ではポリゴンのエッジが他のポリゴンのエッジに隠されることもあり、外形線の頂点はポリゴンエッジの端点以外の場所であることが多い。また、前記ステップＳ１１にて外形線候補のポリラインは交点で頂点挿入を行うため、途中で切断されているポリラインが存在する。この場合、分断点における、法線ベクトルを算出する必要がある。
【００８１】
図１２Ａ，Ｂは、その例を示したものである。この図１２Ａ，Ｂの拡大した部分（丸で囲んだ部分）では、裏側のシルエット線が手前のポリゴンに隠されて途中で見えなくなっている。このような場合、裏側のシルエット線は上記ポリゴンとの交点で切断され、シルエット線は途中で分断されている。
【００８２】
ここで、図１３のように頂点ｖ１、ｖ２間をｔ：１−ｔに内分する点ｖｘの法線ベクトルｎｘは、ｖ１の法線ベクトルをｎ１、ｖ２の法線ベクトルをｎ２とした場合に、線形補間を利用して 式（３）のように定義できる。
ｎｘ＝（１−ｔ）ｎ１＋ｔ ｎ２ （３）
各ポリラインの端点では表面、裏面の法線ベクトルを保持しているため、このステップＳ１４−Ｃでは、法線ベクトルを利用して表面、裏面とも（３）式で補間しておく。
【００８３】
ステップ１４−Ｄ
次に、法線ベクトルから、２次元における外形線の接線ベクトルを求める。外形線を構成する各ポリラインの両端点は表面、裏面の両方の法線ベクトルを持っている。図１４に示すように、ポリラインの両端点が持つ２つの法線ベクトルの外積ベクトルを、描画平面に射影したベクトルが、各ポリラインの両端点における接線ベクトルとなる。
【００８４】
ベクトルＡ＝ｎ１×ｎ２
ベクトルＢ＝ｎ３×ｎ４
ただし、元の曲面の法線ベクトルは単位ベクトルのため、すべて単位法線ベクトルで計算を行うこととする。また、外形線を境に曲面が折れていない場合、可視面と非可視面の曲面法線ベクトルが一致している。この場合、可視面の法線ベクトルと視線ベクトルとの外積ベクトルで代用する。
【００８５】
ステップ１４−Ｅ
次に、ステップ１４−Ｄにて求めた各ポリラインの接線ベクトルと、ポリラインの接続情報を利用して、ポリラインの端点における接線ベクトルの角度により、ポリラインをグループ化する。本手法では、グループ化されたポリラインごとに曲線列を生成する。これを図１５を参照して説明する。
【００８６】
この図に示すように、各ポリラインは最大２本のポリラインと接続している。ここで、、ポリラインａ、ａの始点側に接続するポリラインｂ、終点側に接続するポリラインｃを例にとって、ステップ１４−Ｄの処理を説明する。
１）ポリラインａの始点側頂点ｖ０と接続しているポリラインｂの接続点ｖ０での接線ベクトルを比較し、トレランス（所定の許容値）以下の差であれば、ポリラインａはポリラインｂと同一の曲線の構成要素であると判断する。トレランス以上の差であれば、ここで曲線の区切りがあると判断する。
２）ポリラインａの終点側頂点v1と接続をしているポリラインｃの接続点ｖ１での接線ベクトルを比較し、トレランス以下の差であれば、ポリラインａはポリラインｃと同一の曲線の構成要素であると判断する。逆にトレランス以上の差であれば、ここで曲線の区切りがあると判断する。
３)ポリラインａの始点ｖ０をポリラインｂのｖ２、ポリラインａの終点ｖ０をポリラインｃのｖ３とし、１）、２）の処理をすべてのポリラインについて行う。
【００８７】
以上の処理により、一本の曲線に統合するべきポリラインがグループ化される。
【００８８】
ステップ１４−Ｆ
次に、前記ステップ１４−Ｅでグループ化したポリラインの頂点と、頂点における単位接線ベクトルを利用して、３次ベジェの複合曲線を生成する。
【００８９】
具体的には、ｎ＋１個の頂点からｎ個の複合曲線を生成する場合に、各頂点での単位接続ベクトルｔｉ（ｉ＝０・・・・ｎ）、それぞれの単位ベクトルの大きさをｘｉ（ｉ＝０・・・・ｎ）、単位法線ベクトルをｎｉ（ｉ＝０・・・・ｎ）、接続点での２曲線の接線ベクトルの比をｋｉ：１、頂点間ベクトルをＡｉ（ｉ＝０・・・・ｎ）とする。このとき、接続点で接続点で接線と曲率ベクトルが連続となる条件を示す下記の関係式（４）を利用する。また、接続点で区間曲線Ｒｉと、こ区間曲線の終点に接続をする曲線Ｒｉ＋１に式（５）の条件を付け加えると条件式（６）が求められる。ただし、｜Ａｉ｜／｜Ａｉ−１｜若しくは１．０とする。
【式１】
【００９０】
そして、すべての接続点に式（３）、両端点に式（６）を利用することで未知数ｘを求めることができる。すなわち、３次ベジエ曲線を求めることができる。
【００９１】
図１６〜１７は、これにしたがって、外形線を曲線化した結果を示すものである。すなわち、図１６に示す３次元モデルを、本実施形態の手法に沿って外形線を抽出した状態を示すものが図１７Ａ、それを曲線化した状態を示すものが１７Ｂである。この図からも、ポリラインの品質が向上しているのがわかる。
【００９２】
以上説明した、本発明の一実施形態によれば、本稿では曲面形状を含むソリッドモデル、サーフェースモデルに対し、それを近似するポリゴンデータを利用し、ポリゴンデータのシルエット線群と画像情報を抽出して、外形線を表す曲線を生成する方法を得ることができる。
【００９３】
なお、この発明は上記一実施形態に限定されるものではなく、この発明の要旨を変更しない範囲で種々変形可能である。
【００９４】
例えば、前記一実施形態は、ソリッドモデルを対象にして説明したが、サーフェースモデルに対しても当然適用可能である。
【図面の簡単な説明】
【００９５】
【図１】図１は、この発明の一実施形態を示す概略構成図である。
【図２】図１は、この発明の一実施形態を示すフローチャートである。
【図３】図３は、処理対象となる３次元オブジェクトの例を示すものである。
【図４】図４は、処理対象となる３次元モデルを２次元に投影した状態を示す説明図である。
【図５】図５は、外形線を示す説明図である。
【図６】図６Ａ〜Ｄは、外形線とシルエット線の関係を説明するための説明図である。
【図７】図７は、シルエット線の処理を説明するための説明図である。
【図８】図８Ａ〜Ｅは、シルエット線を絞り込むための画像処理を示すための説明図である。
【図９】図９Ａ、Ｂは、外形線候補の選択を説明するための説明図である。
【図１０】図１０Ａ，Ｂは、外形線候補の枝葉処理を説明するための説明図である。
【図１１】図１１Ａ，Ｂは、外形線を曲線化するための処理を説明する説明図である。
【図１２】図１２Ａ，Ｂは、外形線を曲線化するための処理を説明する説明図である。
【図１３】図１３は、外形線を曲線化するための処理を説明する説明図である。
【図１４】図１４は、外形線を曲線化するための処理を説明する説明図である。
【図１５】図１５は、外形線を曲線化するための処理を説明する説明図である。
【図１６】図１６は、外形線を曲線化する例を説明するための説明図である。
【図１７】図１７Ａ、１７Ｂは、外形線を曲線化する例を説明するための説明図である。
【図１８】図１８は、従来の外形線抽出方法の欠点を説明するための説明図である。
【技術分野】
【０００１】
この発明は、ソリッド／サーフェースモデルから外形線を抽出する方法及び、その方法を実施するためのコンピュータソフトウエアプログラムに関する。
【背景技術】
【０００２】
近年、製造業などで３次元ＣＡＤ／ＣＡＭシステム等の普及が進み、３次元データを設計プロセスだけではなく、下流工程の業務プロセスで利用するシーンが増えてきている。
【０００３】
設計プロセス以外で３次元モデルを活用する方法の一つとして、３次モデルから２次元ベクトルデータを生成し、イラスト化するものがある。これによれば、人手によりマニュアル等の挿絵を作成する用途に３次元モデルから自動的に生成した２次元ベクトルデータを利用することが可能となる。また、生成されたベクトルデータを編集ソフトで２次加工し、容易に付加価値を付けることも可能である。
【０００４】
３次元モデルから２次元イラスト図を生成する手法としては、一般的に、スキャンラインアルゴリズム及びＺバッファ法（非特許文献１）を併用して線データを取り出す手法が知られている。しかし、この手法で出力した２次元データにおいては、線群を任意に出力しているだけのものが多く、編集ソフト等でペイントする際に、閉領域が閉領域として認識されずに意図どおりにペイントできないといった問題がある。特に操作説明書や組み立てマニュアル等のマニュアル類で利用されるイラスト図の生成では２次元データ全体の領域にわたって色を塗る用途が最低限必要である。しかし、一般には閉領域を意識してベクトルデータが生成されるわけではないため、ベクトルデータにペイントを施す場合、編集ソフト側で閉領域を構成すると思われる線群を順番に選択し、これを閉領域化するというかなり細かい作業工程が必要となっている。
【０００５】
一方、閉領域を生成するための他の手法として、Freemanのチェインコード（非特許文献２）等を用い、画像データから外形画素を取り出し、それを snakes（非特許文献３）などにより曲線化する方法がある。しかしながら、線を抽出するための元となるデータに画像を用いているため、テクニカルイラストといった精度の求められる用途には利用することはできない。
【０００６】
また、一般的に、３次元モデルから２次元ベクトルデータを正確に生成する場合には、まず、曲面をポリゴン分割し、稜線を示すポリゴンの境界線に対し、面の位置関係を考慮した陰線処理手法を施すことが必要になる。２次元ベクトルデータを生成する技術としては、Linlinら（非特許文献４）の手法は色情報を利用して特徴線を求めているが、この手法も元となるデータは画像データであり、精度を求められる用途には適さない。また、渡辺ら（非特許文献５）の手法は２次元ベクトルデータを取りだす手法ではないが、ポリゴンメッシュから稜線の接続情報を利用して、特徴線を特定する手法である。渡辺らの手法は、３次元データ上で面稜線や、面の端点を特定することは可能であるが、２次元化した図形にはそのままでの利用は不可能である。
【０００７】
他に有効な手段の１つとして、Ｚバッファ法（非特許文献１）の利用例が挙げられる。Ｚバッファ内の２次元空間は一般に、離散的距離でのみ定義可能な距離空間を用いる。複数の要素が、１つの画素内に現れる場合、離散的距離を用いて外形線を特定することは、困難な問題である。例えば図１８では、２本の稜線が近接しており、1つの画素内に含まれている様子である。
【０００８】
このような問題を解決する方法として、画素の解像度を上げることが考えられるが、メモリの消費量・処理速度とトレードオフになる。また、ポリゴンから抽出したポリラインに基づいて、高品質な外形線を抽出する場合には、ポリゴン分割の精度を上げることも必要になるが、こちらメモリの消費量・処理速度とトレードオフになる。
【０００９】
この発明は、このような事情に鑑みてなされたものであり、少ないコンピュータ資源で３次元グラフィックデータから高精度な外形線を抽出するための方法を提供することを目的とするものである。
【００１０】
なお、本願発明と関連する先行特許出願としては下記のものがある。
【００１１】
まず、特許文献１（特開2007-128173号公報 「CADを用いた面積算出方法」）には、外形線を抽出してからその外形線に囲まれる面積を求める方法が開示されている。しかしながら、この発明は、複数の外形線候補からオペレータが手動で正しい線を１以上入力する必要があるアルゴリズムが必須の構成要素であり、その分オペレータに熟練が要求されるという欠点がある。
【００１２】
特許文献２（特開平7-249053号公報 「CAD を用いた投影面積算出方法」）に開示された発明は、上記非特許文献１と同様に外形線を抽出してからその面積を求めるものである。この手法の場合、３次元データを適当な間隔の平面で切断し、その複数の断面上の点をひとつの平面に投影後、頂点を接続することで外形線を求めている。しかしながら、この手法の場合は、３次元データ上にサンプル点を求めてそのサンプル点を補間した外形線を求めていることとなる為、データ精度が離散的になり、外形線の精度が劣る欠点がある。
【００１３】
【特許文献１】特開2007-128173号公報 「CADを用いた面積算出方法」
【特許文献２】特開平7-249053号公報 「CAD を用いた投影面積算出方
【非特許文献１】Ｄ．シェレイナー他（D. Shreiner, M. Woo, J. Neider, and T. Davis）著, "Opengl Programming Guide: The Official Guide to Learning Opengl, Guide 5 edition." Addison-Wesley Professional, 2005.
【非特許文献２】Ｈ．フリーマン（H. Freeman）著: "Computer Processing of Line-Drawring Images", Computing Surveys, Vol.6, No.3, pp313-321, 1991.
【非特許文献３】Ｍ．カス他（M. Kass, A. Witkin, D. Terzopoulos）著, "Snakes: Active Conour models, " Int. J. Comput. Vision., Vol.1, No.3, pp.321-331, 1988.
【非特許文献４】リンリン他（Linlin Jing, Kohe Inoue, Kiichi Urahama）著,"Generationg, Illustration Images with Isoluminant Colors, IWAIT 2006 pp575-596, 2006.
【非特許文献５】渡辺大地、千代倉弘明著:任意三角形メッシュからの特徴稜線抽出, 電子情報通信学会論文誌D-II Vol.J83-D-II No.5, pp. 1344-1352, 2000 年5 月.
【発明の開示】
【課題を解決するための手段】
【００１４】
上記課題を解決するため、本発明の第１の主要な観点によれば、ソリッド／サーフェースモデル３次元オブジェクトの３次元形状データを２次元に投影処理し、当該ソリッド／サーフェースモデルの２次元シルエット線を求める工程と（シルエット線生成部）、前記３次元形状データを２次元に投影して画像処理し、２次元描画領域の外形を求める工程と（画像処理部）、前記で求めた２次元描画領域の外形に基づいて前記２次元シルエット線から当該ソリッド／サーフェースモデルの２次元外形線候補となるシルエット線を絞りこむ工程と（外形線候補絞り込み部）、前記各外形線候補のシルエット線に基づき、前記描画領域を囲むポリラインによる閉ループを生成し、当該閉ループを構成するポリラインを前記ソリッド／サーフェースモデルの外形線として特定する工程と（外形線出力部）を有することを特徴とする方法が提供される。
【００１５】
このような構成によれば、３次元オブジェクトの２次元シルエット線を画像処理を利用して絞り込むようにしたから、前記３次元オブジェクトの外形線を少ないコンピュータ資源で効率良くかつ高品質で抽出することができる。
【００１６】
ここで、この発明の１の実施形態によれば、前記２次元描画領域の外形を求める工程は、形状が描画されている画素と、非描画の画素とを区別可能にメモリ上にプロットし、注目する画素とその８近傍の画素とを反時計／時計回りで比較し、形状が描画されている画素を発見した場合は、その画素を次の注目する画素として逐次追跡を行い、最初に注目した画素を検出するまで検出を続けることで、閉じた描画領域を特定し、それにより描画領域の外形を特定するものである。
【００１７】
また、他の１の実施形態によれば、前記２次元外形線候補となるシルエット線を絞り込む工程は、描画領域の外形を構成する画素の近傍にあるシルエット線を外形線候補として絞り込むものである。
【００１８】
また、さらなる他の１の実施形態によれば、前記外形線を特定する行程は、そのシルエット線を挟む領域のどちら側に描画領域があるかを特定する情報を求める工程をさらに有し、そのシルエット線のどちら側に描画領域があるかの情報に基づき、前記多数のシルエット線から２次元外形線候補となるシルエット線を絞りこむ工程を有するものである。この場合、前記シルエット線を挟む領域のどちら側に描画領域があるかを特定する情報を求める工程は、前記外形線候補のシルエット線に関する交線計算を行い、すべての線分を交点で切断し、その線分およびその線分の頂点にそれらの位置を特定する情報とそのどちら側に描画領域を示すベクトル情報を付加するものであることが望ましい。
【００１９】
さらなる他の１の実施形態によれば、前記外形線を特定する行程は、前記各外形線候補が複数競合する場合、各外形線候補の位置関係に基づいて外形線候補から外形線を特定する工程を有するものである。この場合、頂点から伸びる外形線候補が３以上あるときには、同じ側に描画領域を有する１組の外形線候補を外形線として特定するものである。また、同じ側に描画領域を有する外形線候補が複数組あるときには、描画領域が最大となる組をその頂点に対する１組の外形線候補として出力するものであることが好ましい。また、上記行程は、外形線候補のうち、閉ループを構成する外形線候補を外形線として特定する工程であることがさらに望ましい。
【００２０】
この発明のさらなる他の１の実施形態によれば、この方法はさらに、前記外形線を特定する工程により生成されたポリラインの外形線を曲線に近似する工程を有するものである。この場合、前記曲線に近似する工程は、外形線候補を求める際に、３次元ソリッド／サーフェースモデル中の、前記外形線候補に対応するポリゴンの法線ベクトルを取得し、各外形線候補に対応付けて記憶する工程と、この法線ベクトルから、外形線の接線ベクトルを求める工程と、前記で求めた接戦ベクトル同士を比較することで、接続する複数の外形線が同一の曲線であるかを判断しグループ化し、グループ化したポリラインの頂点と、頂点における接戦ベクトルを求める工程と、上記グループ化したポリラインの頂点と頂点における接線ベクトルに基づいて３次ベジェの複合曲線を生成する工程とを有するものであることが好ましい。
【００２１】
また、この発明の第２の主要な観点によれば、コンピュータハードウエアに読み込まれ実行されることでソリッド／サーフェースモデル３次元オブジェクトの２次元外形線を抽出するコンピュータソフトウエアプログラムであって、前記コンピュタハードウエアに、前記ソリッド／サーフェースモデル３次元オブジェクトの３次元形状データを２次元に投影処理し、当該ソリッド／サーフェースモデルの２次元シルエット線を求めさせる指令を発するシルエット線生成部と、前記３次元形状データを２次元に投影して画像処理し、２次元描画領域の外形を求させる指令を発する画像処理部と、前記で求めた２次元描画領域の外形に基づいて前記２次元シルエット線から当該ソリッド／サーフェースモデルの２次元外形線候補となるシルエット線を絞りこませる指令を発する外形線候補絞り込み部と、前記各外形線候補のシルエット線に基づき、前記描画領域を囲むポリラインによる閉ループを生成し、当該閉ループを構成するポリラインを前記ソリッド／サーフェースモデルの外形線として特定させる指令を発する外形線出力部とを有するコンピュータソフトウエアプログラムが提供される。
【００２２】
この第２の観点による発明によれば、前記第１の観点に係る方法を実施することができる。
【００２３】
この発明の上記した以外の特徴及び顕著な効果は、以下の発明の詳細な説明の項及び図面を参照することにより、当業者にとって容易に理解することができる。
【発明を実施するための最良の形態】
【００２４】
以下、この発明の最良の実施形態をこの明細書に添付した図面を参照して説明する。
【００２５】
図１は、この発明の実施形態を示す外形線抽出システム１を示す概略構成図である。
【００２６】
このシステム１は、ＣＰＵ２、ＲＡＭ３、モデム等の通信デバイス４、入出力装置５（ディスプレイ６、キーボード７、マウス等）が接続されてなるバス９に、データ格納部１０およびプログラム格納部１１が接続されてなる。
【００２７】
前記データ格納部１０およびプログラム格納部１１は、この実施形態では、ハードディスクなどの固定式記憶媒体で構成されており、これらに格納された各データおよびプログラムは、前記ＲＡＭ３上に呼び出されて前記ＣＰＵ２によって実行されることで、この実施形態の機能を発揮する。
【００２８】
前記プログラム格納部１１には、３次元オブジェクト空間制御部１３と、３次元オブジェクト操作部１４と、描画処理部１５と、オブジェクト操作情報入力部１６と、シルエット線生成部１７と、シルエット線情報付加部１８と、外形線候補絞り込み部１９と、外形線特定部２０と、ポリライン曲線化部２１とが格納されている。
【００２９】
またデータ格納部１０には、３次元グラッフィクデータ２３と、外形線候補抽出用画像処理メモリバッファ２４と、処理後の２次元外形線データ２５とが格納される。
【００３０】
以下、この装置の構成及び機能を、その処理動作と共に、図２に示すフローチャートを参照しつつ説明する。図２中の符合Ｓ１〜Ｓ１４は、以下の説明中における各ステップＳ１〜ステップＳ１４に対応する。
【００３１】
３次元グラフィックデータの前処理
まず、ステップＳ１で外形線生成制御情報の取得が行われる。
【００３２】
このステップＳ１においては、まず、３次元オブジェクト空間制御部１３が、３次元オブジェクト操作部１４の指令に基づき、３次元形状データ２３をＣＡＤカーネルに読み込む。そして、前記描画処理部１５が前記ディスプレイ７上に上記３次元グラフィックスデータ２３をレンダリングし、前記３次元グラフィックデータに係る３次元オブジェクトをディスプレイ７上に表示する。図３は、その表示例である。
【００３３】
ここで、ユーザは、例えばマウスポインタ等からなるオブジェクト操作情報入力部１６を操作することで、前記３次元オブジェクト操作部１４を介し、ディスプレイ７上に表示される３次元オブジェクトの姿勢を操作することができる。たとえば、３次元オブジェクトの回転、倍率表示、視点変更等の操作を行うことができる。
【００３４】
このようにして、外形線を取り出すための３次元オブジェクトの姿勢や視点が決まると、描画対象となっている面や稜線の情報が前記空間制御部１３により取得され外形線生成制御情報として出力されることになる。図４は、この状態を示す概念図である。
【００３５】
ついで、ステップＳ２〜Ｓ６で、前記シルエット線生成部１７が、前記外形線生成制御情報に基づいて、３次元グラフィックモデルのシルエット線を取得する。
【００３６】
これらのステップＳ２〜Ｓ６を説明する前に、まず、「外形線」及び「シルエット線」の概念について説明する。
【００３７】
この明細書で「外形線」とは、図５に２６で示すように、２次元空間においての描画領域と非描領域の境界線であると定義される。一方、「シルエット線」とは３次元モデルの可視な部分と不可視な部分の境界線と定義される。例えば、図４に示すような複雑な形状の３次元オブジェクトの場合、突起部分の裏側は不可視な部分となるから、シルエット線は、図５で示す外形線の描画領域２７内に本来多数存在していることになる。したがって、外形線２６は必ず物体のシルエット線から生成され、その部分集合であるということができる。
【００３８】
図６Ａ〜６Ｄは、その概念を分かりやすく示す模式図である。ここで、図６Ａは処理対象の３次元オブジェクト２８、図６Ｂはポリゴン分割を経て特定された線分群、図６Ｃはその線分群から特定されたシルエット線、図６Ｄはシルエット線から絞り込みを経て特定された外形線をそれぞれ表すものである。
【００３９】
この処理で最終的に得たい図形は、図６Ｄに示すような閉ループ・ポリラインからなる外形線で囲まれた図であり、この発明の最も重要な特徴は、図６Ｃに示したシルエット線から図６Ｄの外形線を自動的に求めることにある。
【００４０】
上記シルエット線を得るため、まず、３次元オブジェクト空間制御部１３が前記外形線生成制御情報に基づいて３次元オブジェクト情報（ソリッド及び／又はサーフェースモデル）を取得し（ステップＳ２）、ついで、ポリゴン分割を行う（ステップＳ３）。また、同時に、前記ポリゴンを構成する境界線を分離する。このことで、ポリゴンを構成する各境界線が、始点と終点を持つ線分に分離される。
【００４１】
次に、ステップＳ４で、Ｚバッファ法を用いた陰線処理を行い、見えない位置に隠れた線分（不可視線分）を処理対象から除去する。これにより図６Ｂに示すような結果が得られる。
【００４２】
シルエット線は、このように見える位置にある線分（可視線分）のうち、３次元モデルの可視な部分と不可視な部分を分ける境界線ということであるから、ステップＳ５で、シルエット線生成部１７が隣り合うポリゴン同士の関係から上記の条件を満たす線分をシルエット線として特定する。
【００４３】
以下、このように特定されたシルエット線から、実際の外形線を求めることになるが、前述したように、図４のような実際の３次元グラッフィクモデルの場合、シルエット線は多数であり、すべてを外形線の候補として処理し、最終的に図５に示すような外形線２６を得ようとすると、膨大なコンピュータ資源が必要となり、処理に時間もかかる。
【００４４】
そこで、この発明の方法では、以下のステップを実行する。
【００４５】
（１）シルエット線から画像処理によって外形線候補を絞り込む（ステップＳ６〜Ｓ１１）。
【００４６】
（２）絞り込まれたシルエット線（外形線候補）を閉ループ処理することで、外形線となるポリラインを特定する（ステップＳ１１〜Ｓ１３）。
【００４７】
（３）外形線を構成するポリラインを曲線化する（ステップＳ１４）。
【００４８】
このことで、少ないコンピュータ資源でかつ、３次元グラフィックデータから、自動的に閉ループを構成する外形線を抽出することができることになる。
【００４９】
以下、まず、外形線となるポリラインの取り出しを説明する。ついで、形線となるポリラインを曲線化する手法について述べていく。
【００５０】
シルエット線からの外形線の絞り込み
まず、本手法を利用する前処理として、ポリゴンデータからのＺバッファの構築と、Ｚバッファの画素に描画をした要素IDを格納するメモリバッファ２４の生成はすでに済んでいるものとする。
【００５１】
以下、本手法の手順を説明する。
【００５２】
シルエット線の取り出し
前述したように、図６Ｃは、３次元オブジェクト２７から取り出されたシルエット線を示すものである。
【００５３】
繰り返しになるが、一般に、シルエット線は、３次元モデルの可視な領域と不可視な領域の境界を示す線分なので、多数のシルエット線が外形線で囲まれる描画領域内に存在することがある。特に、図４に示すように、実際の３次元グラフィックの場合、このようにして特定されるシルエット線は膨大な数になるため、まず外形線の対象となるシルエット線を絞り込む必要がある。
【００５４】
シルエット線の向きを特定
したがって、ステップＳ５で特定されたシルエット線から、ステップＳ６〜Ｓ１０で外形線候補を絞り込む。
【００５５】
まず、シルエット線情報付加部１８が、線分を挟むどちら側の領域が可視であるかの情報を、ステップＳ６で設定する。この場合、まず、隣り合う２つのポリゴンが同じ辺を共有している場合、「共有エッジ」と表すことにすると、図７で可視ポリゴンαの外形線となる線分が、この線の裏側にある不可視ポリゴンβとの共有エッジとなっている。このように共有エッジの両側の面の可視・不可視性を利用して、外形線で囲まれた領域の内側方向を示す情報を外形線（共有エッジ）に設定する。
【００５６】
具体的には、外形線を表すポリゴンエッジが共有エッジの場合、共有エッジを境界とする可視となるポリゴンαにおいて、共有エッジの頂点となっていない頂点Ａのある向きを、外形線に対して描画が行われている向きとして、共有エッジに設定する。図７において、太い線の部分を外形線とする、前述した、頂点Ａのある向きを描画領域として外形線に設定するとは、線分Ｐ１−Ｐ２に対して、これと垂直なベクトルであり、Ｐ３（Ａ）側に向かうベクトル（Ｖ）を保存するということである。
【００５７】
ここで、
ＥＶ３＝(Ｐ３−Ｐ２）/｜Ｐ３−Ｐ２｜
ＥＶ１＝(Ｐ２−Ｐ１）/｜Ｐ２−Ｐ１｜
と表す。
【００５８】
Ｅｖ１をＰ１を中心に時計回りにΠ／２回転したベクトルをＥｖ２とすると、Ｐ３の方向を示すベクトルＶは式（１）、（２）のようになる。
【００５９】
Ｖ＝Ｅｖ２ ｉｆ（Ｅｖ２＊Ｅｖ３>＝０） （１）
Ｖ＝−Ｅｖ２ ｉｆ（Ｅｖ２＊Ｅｖ３<０） （２）
ソリッドモデルでは必ず共有エッジを有するが、サーフェスモデルの場合、共有エッジが存在しないものもある。その場合、シルエット線を示すエッジをもつポリゴンのエッジを共有エッジ考えることにより同一の処理を行うことができる。
【００６０】
上記の操作を行うことで、すべてのシルエット線に対し、共有エッジのどちら側に形状が存在するかを得ることができる。
【００６１】
したがって、ステップＳ６で、前記シルエット線情報付加部１８が、すべてのシルエット線に対してこのベクトルの情報を計算して付加する。
【００６２】
シルエット線から外形線候補を選定
次に、ステップＳ７で、前記外形線候補絞り込み部１９がシルエット線の線分ＩＤを格納するメモリバッファと、同一のサイズの２値（０／１値）のメモリバッファ２４をハードディスクに生成する。（形状が描画されている画素を１、非描画の画素を０とする。）
【００６３】
ついで、ステップＳ８で、２値で表わされたＺバッファから画素に基づいて外形線を生成する。この方法を示したのが、図８Ａ〜８Ｆである。
【００６４】
すなわち、図８Ａに示すようなシルエット線を処理対象とする場合、図８Ｂが線分ＩＤを格納するメモリバッファ、図８Ｃが２値のメモリバッファである。ついで、この２値のメモリバッファ（図８Ｃ）を処理対象として、注目する画素とその８近傍の画素とを半時計回りで比較し、値が１の画素を発見した場合は、その画素を次の注目する画素として逐次追跡を行い、最初に着目した画素を検出するまで検索を続けることで閉じた領域を生成する。図８Ｄは閉じた領域を構成する画素のマーキングを示す図である。ついで、画素に基づいた外形線の８近傍に相当するメモリバッファを逐次追跡することにより、外形線となる線分を含む画素を特定する（図８Ｅ、ステップＳ８）。
【００６５】
そしてこのような画像処理の結果と、シルエット線とを比較し、画像処理で示される外形に最も近いシルエット線を、外形線候補として特定する。具体的には、ステップＳ５で特定されたシルエット線を上記画像処理された外形線上に２次元投影し（ステップＳ９）、画像処理による外形線とこの２次元投影されたシルエット線から、外形線に最も近い位置に存在するシルエット線を特定する（ステップＳ１０）。このことによって特定されたシルエット線が外形線の候補として出力される。
【００６６】
ここで、本発明が従来の技術と異なるのは、このような画像処理を外形線そのものを特定するために行うのではなく、シルエット線から外形線候補を絞り込む目的で使用する点である。実際の外形線の特定は、後に説明するステップＳ１１〜Ｓ１３で行われる。
【００６７】
外形線候補からの選択
次に、ステップＳ１１〜Ｓ１３にて、外形線同士を連結する頂点の接続位置関係を表す構造を構築する。
【００６８】
このために、ステップＳ１１で、外形線候補となったポリラインを２次元化したものに対して交線計算を行い、すべての線分を交点で切断する。その後以下の属性情報をそれぞれの頂点、線分に対し付加する。
【００６９】
以下は、この実施形態にてポリラインに付加する外形線抽出用のデータ構造である。
頂点情報：
・頂点座標
・頂点に接続する線分のインデックス
・[頂点位置での可視側の曲面の法線ベクトル]
・[頂点位置での非可視側の曲面の法線ベクトル]
線分情報：
・線分の視点側の頂点インデックス
・線分の終点側の頂点インデックス
・線分に対して領域の内側を表す方向
【００７０】
次に、外形線特定部２０は、ステップＳ１２で、外形線の候補となるポリラインがある頂点から複数本伸びている場合に、描画領域と非描画領域の境界線となる線を特定し、正しい外形線を特定する。すなわち、前記で着目した線分の片側が描画領域、もう片側が非描画領域という特徴を利用して意図する線分を特定する。この実施形態ではまず、ある頂点から伸びている複数本の線分のうち、隣接する線分の描画領域の方向が逆の場合に、そのペアが外形線を示す２本の線分であると判断する。すなわち、ステップＳ６で求めた描画領域を示す方向ベクトルが逆を向いているペアを特定すればよい。
【００７１】
もしこのようなペアが複数存在する場合は、次に示す方法で描画領域が最大となるペアを特定する。図９Ａ，Ｂは、頂点Ａにおいて、隣接する線分の描画領域の方向が逆のペアが複数存在する場合を示している。Ｅｄ０、Ｅｄ１、Ｅｄ２、Ｅｄ３の４本の線分が１つの頂点に接続されている。これらの線分のうちで、描画領域を示す方向ベクトルが逆を向いているペアは、Ｅｄ０・Ｅｄ３と、Ｅｄ１・Ｅｄ２の２つである。この場合、描画領域が最大となるＥｄ０・Ｅｄ３のペアが求めるペアとなり、Ｅｄ１・Ｅｄ２は不要な外形線ということになる。
【００７２】
また、このステップＳ１２では、線分の端点に接続する線分のインデックス数が２つにならないもの（すなわち、どの線分にも接続されていないもの）を線分情報から削除する処理も行う。図１０Ａ，Ｂは、この例を示したものである。図１０Ａでは、線分Ｅｄ３の端点Ｖｘ２及び線分Ｅｄ４の端点Ｖｘ５がそれに相当するから、各線分Ｅｄ３，Ｅｄ４は、不要な枝葉の外形線であるとして除去される。
【００７３】
この後、ステップＳ１４で、再構成したポリラインの頂点・線分情報からポリラインの逐次追跡を行い、最初に選んだ頂点に戻るグラフが存在するものを、閉曲線をなすポリラインとして特定する（図１０Ｂ）。この追跡をすべてポリラインについて行うことで、複数の閉曲線が存在する場合でも発見は可能となる。
【００７４】
ポリラインの曲線化
上記したステップで求めた外形線は折線状のポリラインであるので、この実施形態においては、以下のステップで曲線化する。
【００７５】
具体的には、ステップＳ１３までで生成したポリラインに接線ベクトル等を追加することで３次ベジェの複合曲線を生成する。このために、同一の曲線となる区間を定義し、その区間の点列、接線ベクトルを利用して曲線補間を行う。
【００７６】
以下では特に断りがない限り、法線ベクトルとはポリゴン平面の法線ではなく、元曲面の法線ベクトルを表すことにする。
【００７７】
ステップ１４−Ａ
シルエット線に接線ベクトルを付加するために、３次元オブジェクトの各ポリゴンの法線ベクトルを利用する。具体的には、前記ステップＳ６（図７）において共有エッジを処理する際に、可視ポリゴン及び非可視ポリゴンの元曲面の法線ベクトルも合わせて保存しておく。
【００７８】
ステップ１４−Ｂ
このステップでは、ステップＳ１３にて求めた外形線となるポリラインに対し、ステップ１４−Ａで保持している３次元の法線ベクトルを対応付ける。つまり各ポリラインの両端点での曲面の法線ベクトルが外形線情報に追加されることになる。この状態を示したのが、図１１Ａ、Ｂである。すなわち、外形線のもとになるシルエット線は、可視面と非可視面の境界であるため、線分の視点及び終点において、図１４Ｂに示すように、それぞれ少なくとも２つの面の法線ベクトルが存在するはずである。この情報を外形線（シルエット線）の始点・終点情報に付加する。
【００７９】
ステップ１４−Ｃ
このステップでは、シルエット線の端点が先に行われた陰線処理等によって現れていない場合の補完処理を行う。
【００８０】
すなわち、前記ステップ１４−Ｂの処理は、外形線が生成元となるポリゴンエッジに一致した場合にのみ可能となる。しかし、陰線処理ではポリゴンのエッジが他のポリゴンのエッジに隠されることもあり、外形線の頂点はポリゴンエッジの端点以外の場所であることが多い。また、前記ステップＳ１１にて外形線候補のポリラインは交点で頂点挿入を行うため、途中で切断されているポリラインが存在する。この場合、分断点における、法線ベクトルを算出する必要がある。
【００８１】
図１２Ａ，Ｂは、その例を示したものである。この図１２Ａ，Ｂの拡大した部分（丸で囲んだ部分）では、裏側のシルエット線が手前のポリゴンに隠されて途中で見えなくなっている。このような場合、裏側のシルエット線は上記ポリゴンとの交点で切断され、シルエット線は途中で分断されている。
【００８２】
ここで、図１３のように頂点ｖ１、ｖ２間をｔ：１−ｔに内分する点ｖｘの法線ベクトルｎｘは、ｖ１の法線ベクトルをｎ１、ｖ２の法線ベクトルをｎ２とした場合に、線形補間を利用して 式（３）のように定義できる。
ｎｘ＝（１−ｔ）ｎ１＋ｔ ｎ２ （３）
各ポリラインの端点では表面、裏面の法線ベクトルを保持しているため、このステップＳ１４−Ｃでは、法線ベクトルを利用して表面、裏面とも（３）式で補間しておく。
【００８３】
ステップ１４−Ｄ
次に、法線ベクトルから、２次元における外形線の接線ベクトルを求める。外形線を構成する各ポリラインの両端点は表面、裏面の両方の法線ベクトルを持っている。図１４に示すように、ポリラインの両端点が持つ２つの法線ベクトルの外積ベクトルを、描画平面に射影したベクトルが、各ポリラインの両端点における接線ベクトルとなる。
【００８４】
ベクトルＡ＝ｎ１×ｎ２
ベクトルＢ＝ｎ３×ｎ４
ただし、元の曲面の法線ベクトルは単位ベクトルのため、すべて単位法線ベクトルで計算を行うこととする。また、外形線を境に曲面が折れていない場合、可視面と非可視面の曲面法線ベクトルが一致している。この場合、可視面の法線ベクトルと視線ベクトルとの外積ベクトルで代用する。
【００８５】
ステップ１４−Ｅ
次に、ステップ１４−Ｄにて求めた各ポリラインの接線ベクトルと、ポリラインの接続情報を利用して、ポリラインの端点における接線ベクトルの角度により、ポリラインをグループ化する。本手法では、グループ化されたポリラインごとに曲線列を生成する。これを図１５を参照して説明する。
【００８６】
この図に示すように、各ポリラインは最大２本のポリラインと接続している。ここで、、ポリラインａ、ａの始点側に接続するポリラインｂ、終点側に接続するポリラインｃを例にとって、ステップ１４−Ｄの処理を説明する。
１）ポリラインａの始点側頂点ｖ０と接続しているポリラインｂの接続点ｖ０での接線ベクトルを比較し、トレランス（所定の許容値）以下の差であれば、ポリラインａはポリラインｂと同一の曲線の構成要素であると判断する。トレランス以上の差であれば、ここで曲線の区切りがあると判断する。
２）ポリラインａの終点側頂点v1と接続をしているポリラインｃの接続点ｖ１での接線ベクトルを比較し、トレランス以下の差であれば、ポリラインａはポリラインｃと同一の曲線の構成要素であると判断する。逆にトレランス以上の差であれば、ここで曲線の区切りがあると判断する。
３)ポリラインａの始点ｖ０をポリラインｂのｖ２、ポリラインａの終点ｖ０をポリラインｃのｖ３とし、１）、２）の処理をすべてのポリラインについて行う。
【００８７】
以上の処理により、一本の曲線に統合するべきポリラインがグループ化される。
【００８８】
ステップ１４−Ｆ
次に、前記ステップ１４−Ｅでグループ化したポリラインの頂点と、頂点における単位接線ベクトルを利用して、３次ベジェの複合曲線を生成する。
【００８９】
具体的には、ｎ＋１個の頂点からｎ個の複合曲線を生成する場合に、各頂点での単位接続ベクトルｔｉ（ｉ＝０・・・・ｎ）、それぞれの単位ベクトルの大きさをｘｉ（ｉ＝０・・・・ｎ）、単位法線ベクトルをｎｉ（ｉ＝０・・・・ｎ）、接続点での２曲線の接線ベクトルの比をｋｉ：１、頂点間ベクトルをＡｉ（ｉ＝０・・・・ｎ）とする。このとき、接続点で接続点で接線と曲率ベクトルが連続となる条件を示す下記の関係式（４）を利用する。また、接続点で区間曲線Ｒｉと、こ区間曲線の終点に接続をする曲線Ｒｉ＋１に式（５）の条件を付け加えると条件式（６）が求められる。ただし、｜Ａｉ｜／｜Ａｉ−１｜若しくは１．０とする。
【式１】
【００９０】
そして、すべての接続点に式（３）、両端点に式（６）を利用することで未知数ｘを求めることができる。すなわち、３次ベジエ曲線を求めることができる。
【００９１】
図１６〜１７は、これにしたがって、外形線を曲線化した結果を示すものである。すなわち、図１６に示す３次元モデルを、本実施形態の手法に沿って外形線を抽出した状態を示すものが図１７Ａ、それを曲線化した状態を示すものが１７Ｂである。この図からも、ポリラインの品質が向上しているのがわかる。
【００９２】
以上説明した、本発明の一実施形態によれば、本稿では曲面形状を含むソリッドモデル、サーフェースモデルに対し、それを近似するポリゴンデータを利用し、ポリゴンデータのシルエット線群と画像情報を抽出して、外形線を表す曲線を生成する方法を得ることができる。
【００９３】
なお、この発明は上記一実施形態に限定されるものではなく、この発明の要旨を変更しない範囲で種々変形可能である。
【００９４】
例えば、前記一実施形態は、ソリッドモデルを対象にして説明したが、サーフェースモデルに対しても当然適用可能である。
【図面の簡単な説明】
【００９５】
【図１】図１は、この発明の一実施形態を示す概略構成図である。
【図２】図１は、この発明の一実施形態を示すフローチャートである。
【図３】図３は、処理対象となる３次元オブジェクトの例を示すものである。
【図４】図４は、処理対象となる３次元モデルを２次元に投影した状態を示す説明図である。
【図５】図５は、外形線を示す説明図である。
【図６】図６Ａ〜Ｄは、外形線とシルエット線の関係を説明するための説明図である。
【図７】図７は、シルエット線の処理を説明するための説明図である。
【図８】図８Ａ〜Ｅは、シルエット線を絞り込むための画像処理を示すための説明図である。
【図９】図９Ａ、Ｂは、外形線候補の選択を説明するための説明図である。
【図１０】図１０Ａ，Ｂは、外形線候補の枝葉処理を説明するための説明図である。
【図１１】図１１Ａ，Ｂは、外形線を曲線化するための処理を説明する説明図である。
【図１２】図１２Ａ，Ｂは、外形線を曲線化するための処理を説明する説明図である。
【図１３】図１３は、外形線を曲線化するための処理を説明する説明図である。
【図１４】図１４は、外形線を曲線化するための処理を説明する説明図である。
【図１５】図１５は、外形線を曲線化するための処理を説明する説明図である。
【図１６】図１６は、外形線を曲線化する例を説明するための説明図である。
【図１７】図１７Ａ、１７Ｂは、外形線を曲線化する例を説明するための説明図である。
【図１８】図１８は、従来の外形線抽出方法の欠点を説明するための説明図である。
【特許請求の範囲】
【請求項１】
ソリッド／サーフェースモデル３次元オブジェクトの３次元形状データを２次元に投影処理し、当該ソリッド／サーフェースモデルの２次元シルエット線を求める工程と、
前記３次元形状データを２次元に投影して画像処理し、２次元描画領域の外形を求める工程と、
前記で求めた２次元描画領域の外形に基づいて前記２次元シルエット線から当該ソリッド／サーフェースモデルの２次元外形線候補となるシルエット線を絞りこむ工程と、
前記各外形線候補のシルエット線に基づき、前記描画領域を囲むポリラインによる閉ループを生成し、当該閉ループを構成するポリラインを前記ソリッド／サーフェースモデルの外形線として特定する工程と、
を有することを特徴とする方法。
【請求項２】
請求項１記載の方法において、
前記２次元描画領域の外形を求める工程は、
形状が描画されている画素と、非描画の画素とを区別可能にメモリ上にプロットし、
注目する画素とその８近傍の画素とを反時計／時計回りで比較し、形状が描画されている画素を発見した場合は、その画素を次の注目する画素として逐次追跡を行い、最初に注目した画素を検出するまで検出を続けることで、閉じた描画領域を特定し、それにより描画領域の外形を特定するものである。
【請求項３】
請求項１記載の方法において、
前記２次元外形線候補となるシルエット線を絞り込む工程は、
描画領域の外形を構成する画素の近傍にあるシルエット線を外形線候補として絞り込むものである
を有する。
【請求項４】
請求項１記載の方法において、
前記外形線を特定する工程は、
前記シルエット線を挟む領域のどちら側に描画領域があるかを特定する情報を求める工程をさらに有し、
そのシルエット線のどちら側に描画領域があるかの情報に基づき、前記多数のシルエット線から２次元外形線候補となるシルエット線を絞りこむ工程を有する
ことを特徴とする方法。
【請求項５】
請求項４記載の方法において、
前記シルエット線を挟む領域のどちら側に描画領域があるかを特定する情報を求める工程は、
前記外形線候補のシルエット線に関する交線計算を行い、すべての線分を交点で切断し、その線分およびその線分の頂点にそれらの位置を特定する情報とそのどちら側に描画領域を示すベクトル情報を付加するものである
ことを特徴とする方法。
【請求項６】
請求項１記載の方法において、
前記外形線を特定する工程は、
前記各外形線候補が複数競合する場合、各外形線候補の位置関係に基づいて外形線候補から外形線を特定する工程を有する
ことを特徴とする方法。
【請求項７】
請求項６記載の方法において、
頂点から伸びる外形線候補が３以上あるときには、同じ側に描画領域を有する１組の外形線候補を外形線として特定するものである
ことを特徴とする方法。
【請求項８】
請求項７記載の方法において
さらに、同じ側に描画領域を有する外形線候補が複数組あるときには、描画領域が最大となる組をその頂点に対する１組の外形線候補として出力するものである
ことを特徴とする方法。
【請求項９】
請求項６記載の方法において、
外形線候補のうち、閉ループを構成する外形線候補を外形線として特定する工程を有することを特徴とする方法。
【請求項１０】
請求項１記載の方法において、
さらに、
前記外形線を特定する工程により生成されたポリラインの外形線を曲線に近似する工程を有するものであることを特徴とする方法。
【請求項１１】
請求項１０記載の方法において、
前記曲線に近似する工程は、
外形線候補を求める際に、３次元ソリッド／サーフェースモデル中の、前記外形線候補に対応するポリゴンの法線ベクトルを取得し、各外形線候補に対応付けて記憶する工程と、
この法線ベクトルから、外形線の接線ベクトルを求める工程と、
前記で求めた接戦ベクトル同士を比較することで、接続する複数の外形線が同一の曲線であるかを判断しグループ化し、グループ化したポリラインの頂点と、頂点における接戦ベクトルを求める工程と、
上記グループ化したポリラインの頂点と頂点における接線ベクトルに基づいて３次ベジェの複合曲線を生成する工程と
を有するものである
ことを特徴とする方法。
【請求項１２】
コンピュータハードウエアに読み込まれ実行されることでソリッド／サーフェースモデル３次元オブジェクトの２次元外形線を抽出するコンピュータソフトウエアプログラムであって、前記コンピュタハードウエアに、前記ソリッド／サーフェースモデル３次元オブジェクトの３次元形状データを２次元に投影処理し、当該ソリッド／サーフェースモデルの２次元シルエット線を求めさせる指令を発するシルエット線生成部と、前記３次元形状データを２次元に投影して画像処理し、２次元描画領域の外形を求させる指令を発する画像処理部と、前記で求めた２次元描画領域の外形に基づいて前記２次元シルエット線から当該ソリッド／サーフェースモデルの２次元外形線候補となるシルエット線を絞りこませる指令を発する外形線候補絞り込み部と、前記各外形線候補のシルエット線に基づき、前記描画領域を囲むポリラインによる閉ループを生成し、当該閉ループを構成するポリラインを前記ソリッド／サーフェースモデルの外形線として特定させる指令を発する外形線出力部とを有するコンピュータソフトウエアプログラム。
【請求項１３】
請求項１２記載のコンピュータソフトウエアプログラムにおいて、
前記画像処理部は、
形状が描画されている画素と、非描画の画素とを区別可能にメモリ上にプロットし、
注目する画素とその８近傍の画素とを反時計／時計回りで比較し、形状が描画されている画素を発見した場合は、その画素を次の注目する画素として逐次追跡を行い、最初に注目した画素を検出するまで検出を続けることで、閉じた描画領域を特定し、それにより描画領域の外形を特定するものである。
【請求項１４】
請求項１２記載のコンピュータソフトウエアプログラムにおいて、
外形線候補絞り込み部は、
描画領域の外形を構成する画素の近傍にあるシルエット線を外形線候補として絞り込むものである
を有する。
【請求項１５】
請求項１２記載のコンピュータソフトウエアプログラムにおいて、
前記外形線特定部は、
前記シルエット線を挟む領域のどちら側に描画領域があるかを特定する情報を求め、
前記シルエット線のどちら側に描画領域があるかの情報に基づき、前記多数のシルエット線から２次元外形線候補となるシルエット線を絞りこむものである。
【請求項１６】
請求項１５記載のコンピュータソフトウエアプログラムにおいて、
前記外形線特定部は、
さらに、
前記外形線候補のシルエット線に関する交線計算を行い、すべての線分を交点で切断し、その線分およびその線分の頂点にそれらの位置を特定する情報とそのどちら側に描画領域を示すベクトル情報を付加するものである。
【請求項１７】
請求項１２記載のコンピュータソフトウエアプログラムにおいて、
前記外形線特定部は、
前記各外形線候補が複数競合する場合、各外形線候補の位置関係に基づいて外形線候補から外形線を特定するものである。
【請求項１８】
請求項１７記載のコンピュータソフトウエアプログラムにおいて、
頂点から伸びる外形線候補が３以上あるときには、同じ側に描画領域を有する１組の外形線候補を外形線として特定するものである。
【請求項１９】
請求項１８記載のコンピュータソフトウエアプログラムにおいて
さらに、同じ側に描画領域を有する外形線候補が複数組あるときには、描画領域が最大となる組をその頂点に対する１組の外形線候補として出力するものである。
【請求項２０】
請求項１７記載のコンピュータソフトウエアプログラムにおいて、
外形線候補のうち、閉ループを構成する外形線候補を外形線として特定するものである。
【請求項２１】
請求項１２記載のコンピュータソフトウエアプログラムにおいて、
さらに、
前記外形線を特定する工程により生成されたポリラインの外形線を曲線に近似するものである。
【請求項２２】
請求項２１記載のコンピュータソフトウエアプログラムにおいて、
前記曲線近似部は、
外形線候補を求める際に、３次元ソリッド／サーフェースモデル中の、前記外形線候補に対応するポリゴンの法線ベクトルを取得し、各外形線候補に対応付けて記憶させ、
この法線ベクトルから、外形線の接線ベクトルを求めさせ、
前記で求めた接戦ベクトル同士を比較することで、接続する複数の外形線が同一の曲線であるかを判断しグループ化し、グループ化したポリラインの頂点と、頂点における接戦ベクトルを求めさせ、
上記グループ化したポリラインの頂点と頂点における接線ベクトルに基づいて３次ベジェの複合曲線を生成させるものである。
【請求項１】
ソリッド／サーフェースモデル３次元オブジェクトの３次元形状データを２次元に投影処理し、当該ソリッド／サーフェースモデルの２次元シルエット線を求める工程と、
前記３次元形状データを２次元に投影して画像処理し、２次元描画領域の外形を求める工程と、
前記で求めた２次元描画領域の外形に基づいて前記２次元シルエット線から当該ソリッド／サーフェースモデルの２次元外形線候補となるシルエット線を絞りこむ工程と、
前記各外形線候補のシルエット線に基づき、前記描画領域を囲むポリラインによる閉ループを生成し、当該閉ループを構成するポリラインを前記ソリッド／サーフェースモデルの外形線として特定する工程と、
を有することを特徴とする方法。
【請求項２】
請求項１記載の方法において、
前記２次元描画領域の外形を求める工程は、
形状が描画されている画素と、非描画の画素とを区別可能にメモリ上にプロットし、
注目する画素とその８近傍の画素とを反時計／時計回りで比較し、形状が描画されている画素を発見した場合は、その画素を次の注目する画素として逐次追跡を行い、最初に注目した画素を検出するまで検出を続けることで、閉じた描画領域を特定し、それにより描画領域の外形を特定するものである。
【請求項３】
請求項１記載の方法において、
前記２次元外形線候補となるシルエット線を絞り込む工程は、
描画領域の外形を構成する画素の近傍にあるシルエット線を外形線候補として絞り込むものである
を有する。
【請求項４】
請求項１記載の方法において、
前記外形線を特定する工程は、
前記シルエット線を挟む領域のどちら側に描画領域があるかを特定する情報を求める工程をさらに有し、
そのシルエット線のどちら側に描画領域があるかの情報に基づき、前記多数のシルエット線から２次元外形線候補となるシルエット線を絞りこむ工程を有する
ことを特徴とする方法。
【請求項５】
請求項４記載の方法において、
前記シルエット線を挟む領域のどちら側に描画領域があるかを特定する情報を求める工程は、
前記外形線候補のシルエット線に関する交線計算を行い、すべての線分を交点で切断し、その線分およびその線分の頂点にそれらの位置を特定する情報とそのどちら側に描画領域を示すベクトル情報を付加するものである
ことを特徴とする方法。
【請求項６】
請求項１記載の方法において、
前記外形線を特定する工程は、
前記各外形線候補が複数競合する場合、各外形線候補の位置関係に基づいて外形線候補から外形線を特定する工程を有する
ことを特徴とする方法。
【請求項７】
請求項６記載の方法において、
頂点から伸びる外形線候補が３以上あるときには、同じ側に描画領域を有する１組の外形線候補を外形線として特定するものである
ことを特徴とする方法。
【請求項８】
請求項７記載の方法において
さらに、同じ側に描画領域を有する外形線候補が複数組あるときには、描画領域が最大となる組をその頂点に対する１組の外形線候補として出力するものである
ことを特徴とする方法。
【請求項９】
請求項６記載の方法において、
外形線候補のうち、閉ループを構成する外形線候補を外形線として特定する工程を有することを特徴とする方法。
【請求項１０】
請求項１記載の方法において、
さらに、
前記外形線を特定する工程により生成されたポリラインの外形線を曲線に近似する工程を有するものであることを特徴とする方法。
【請求項１１】
請求項１０記載の方法において、
前記曲線に近似する工程は、
外形線候補を求める際に、３次元ソリッド／サーフェースモデル中の、前記外形線候補に対応するポリゴンの法線ベクトルを取得し、各外形線候補に対応付けて記憶する工程と、
この法線ベクトルから、外形線の接線ベクトルを求める工程と、
前記で求めた接戦ベクトル同士を比較することで、接続する複数の外形線が同一の曲線であるかを判断しグループ化し、グループ化したポリラインの頂点と、頂点における接戦ベクトルを求める工程と、
上記グループ化したポリラインの頂点と頂点における接線ベクトルに基づいて３次ベジェの複合曲線を生成する工程と
を有するものである
ことを特徴とする方法。
【請求項１２】
コンピュータハードウエアに読み込まれ実行されることでソリッド／サーフェースモデル３次元オブジェクトの２次元外形線を抽出するコンピュータソフトウエアプログラムであって、前記コンピュタハードウエアに、前記ソリッド／サーフェースモデル３次元オブジェクトの３次元形状データを２次元に投影処理し、当該ソリッド／サーフェースモデルの２次元シルエット線を求めさせる指令を発するシルエット線生成部と、前記３次元形状データを２次元に投影して画像処理し、２次元描画領域の外形を求させる指令を発する画像処理部と、前記で求めた２次元描画領域の外形に基づいて前記２次元シルエット線から当該ソリッド／サーフェースモデルの２次元外形線候補となるシルエット線を絞りこませる指令を発する外形線候補絞り込み部と、前記各外形線候補のシルエット線に基づき、前記描画領域を囲むポリラインによる閉ループを生成し、当該閉ループを構成するポリラインを前記ソリッド／サーフェースモデルの外形線として特定させる指令を発する外形線出力部とを有するコンピュータソフトウエアプログラム。
【請求項１３】
請求項１２記載のコンピュータソフトウエアプログラムにおいて、
前記画像処理部は、
形状が描画されている画素と、非描画の画素とを区別可能にメモリ上にプロットし、
注目する画素とその８近傍の画素とを反時計／時計回りで比較し、形状が描画されている画素を発見した場合は、その画素を次の注目する画素として逐次追跡を行い、最初に注目した画素を検出するまで検出を続けることで、閉じた描画領域を特定し、それにより描画領域の外形を特定するものである。
【請求項１４】
請求項１２記載のコンピュータソフトウエアプログラムにおいて、
外形線候補絞り込み部は、
描画領域の外形を構成する画素の近傍にあるシルエット線を外形線候補として絞り込むものである
を有する。
【請求項１５】
請求項１２記載のコンピュータソフトウエアプログラムにおいて、
前記外形線特定部は、
前記シルエット線を挟む領域のどちら側に描画領域があるかを特定する情報を求め、
前記シルエット線のどちら側に描画領域があるかの情報に基づき、前記多数のシルエット線から２次元外形線候補となるシルエット線を絞りこむものである。
【請求項１６】
請求項１５記載のコンピュータソフトウエアプログラムにおいて、
前記外形線特定部は、
さらに、
前記外形線候補のシルエット線に関する交線計算を行い、すべての線分を交点で切断し、その線分およびその線分の頂点にそれらの位置を特定する情報とそのどちら側に描画領域を示すベクトル情報を付加するものである。
【請求項１７】
請求項１２記載のコンピュータソフトウエアプログラムにおいて、
前記外形線特定部は、
前記各外形線候補が複数競合する場合、各外形線候補の位置関係に基づいて外形線候補から外形線を特定するものである。
【請求項１８】
請求項１７記載のコンピュータソフトウエアプログラムにおいて、
頂点から伸びる外形線候補が３以上あるときには、同じ側に描画領域を有する１組の外形線候補を外形線として特定するものである。
【請求項１９】
請求項１８記載のコンピュータソフトウエアプログラムにおいて
さらに、同じ側に描画領域を有する外形線候補が複数組あるときには、描画領域が最大となる組をその頂点に対する１組の外形線候補として出力するものである。
【請求項２０】
請求項１７記載のコンピュータソフトウエアプログラムにおいて、
外形線候補のうち、閉ループを構成する外形線候補を外形線として特定するものである。
【請求項２１】
請求項１２記載のコンピュータソフトウエアプログラムにおいて、
さらに、
前記外形線を特定する工程により生成されたポリラインの外形線を曲線に近似するものである。
【請求項２２】
請求項２１記載のコンピュータソフトウエアプログラムにおいて、
前記曲線近似部は、
外形線候補を求める際に、３次元ソリッド／サーフェースモデル中の、前記外形線候補に対応するポリゴンの法線ベクトルを取得し、各外形線候補に対応付けて記憶させ、
この法線ベクトルから、外形線の接線ベクトルを求めさせ、
前記で求めた接戦ベクトル同士を比較することで、接続する複数の外形線が同一の曲線であるかを判断しグループ化し、グループ化したポリラインの頂点と、頂点における接戦ベクトルを求めさせ、
上記グループ化したポリラインの頂点と頂点における接線ベクトルに基づいて３次ベジェの複合曲線を生成させるものである。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２００９−１２２９９８（Ｐ２００９−１２２９９８Ａ）
【公開日】平成２１年６月４日（２００９．６．４）
【国際特許分類】
【出願番号】特願２００７−２９６８２９（Ｐ２００７−２９６８２９）
【出願日】平成１９年１１月１５日（２００７．１１．１５）
【出願人】（５９８０７６６０５）ラティス・テクノロジー株式会社 (7)
【Ｆターム（参考）】
【公開日】平成２１年６月４日（２００９．６．４）
【国際特許分類】
【出願日】平成１９年１１月１５日（２００７．１１．１５）
【出願人】（５９８０７６６０５）ラティス・テクノロジー株式会社 (7)
【Ｆターム（参考）】
[ Back to top ]