(57)【要約】【課題】効率的に高品質なポリゴンデータの生成することが可能な画像処理装置、画像処理方法、およびコンピュータが実行可能なプログラムを提供することを目的とする。【解決手段】格子生成部１２は、３Ｄ曲面モデルの全体を囲むバウンディングボックスを生成し、当該バウンディングボックスを複数の立方体格子に分割し、交点検出部１３は、３Ｄ曲面モデルと各立方体格子の線分との交点を検出し、ポリゴン生成部１４は、立方体格子毎に、検出した交点を結線して多角形平面要素を生成して、ポリゴンデータを生成する。【選択図】      図１
2011013784.tif 000002
【特許請求の範囲】
【請求項１】
３Ｄ曲面モデルをポリゴンデータに変換する画像処理装置において、
前記３Ｄ曲面モデルの全体を囲むバウンディングボックスを生成し、当該バウンディングボックスを複数の立方体格子に分割する格子生成手段と、
前記３Ｄ曲面モデルと各立方体格子の線分との交点を検出する交点検出手段と、
前記立方体格子毎に、検出した交点を結線して多角形平面要素を生成して、ポリゴンデータを生成するポリゴン生成手段と、
を備えたことを特徴とする画像処理装置。
【請求項２】
前記ポリゴンデータの輪郭を補正する輪郭補正手段を備えたことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記輪郭補正手段は、前記交点検出手段で検出された交点に対して、立方体格子の交点の数が２以下または全ての交点が同一直線上に存在するものがある場合には、輪郭として検出することを特徴とする請求項２に記載の画像処理装置。
【請求項４】
前記輪郭補正手段は、前記輪郭を検出した場合には、３Ｄ曲面式から輪郭線上に頂点を作成し、結線できなかった交点に当該頂点を加えて結線して、多角形平面を作成することを特徴とする請求項３に記載の画像処理装置。
【請求項５】
前記３Ｄ曲面は、ＮＵＲＢＳ曲面、Ｂｅｚｉｅｒ曲面、またはＢ−ｓｐｌｉｎｅ曲面であることを特徴とする請求項１〜請求項４のいずれか１つに記載の画像処理装置。  
【請求項６】
前記立方体格子の基本幅は、任意に設定可能であることを特徴とする請求項１〜請求項５のいずれか１つに記載の画像処理装置。
【請求項７】
３Ｄ曲面モデルをポリゴンデータに変換する画像処理装置に搭載されるプログラムにおいて、
コンピュータを、
前記３Ｄ曲面モデルの全体を囲むバウンディングボックスを生成し、当該バウンディングボックスを複数の立方体格子に分割する格子生成手段と、
前記３Ｄ曲面モデルと各立方体格子の線分との交点を検出する交点検出手段と、
前記立方体格子毎に、検出した交点を結線して多角形平面要素を生成して、ポリゴンデータを生成するポリゴン生成手段として機能させることを特徴とするコンピュータが実行可能なプログラム。
【請求項８】
さらに、コンピュータを、前記ポリゴンデータの輪郭を補正する輪郭補正手段として機能させることを特徴とする請求項７に記載のコンピュータが実行可能なプログラム。
【請求項９】
前記輪郭補正手段は、前記交点検出手段で検出された交点に対して、立方体格子の交点の数が２以下または全ての交点が同一直線上に存在するものがある場合には、輪郭として検出することを特徴とする請求項８に記載のコンピュータが実行可能なプログラム。
【請求項１０】
前記輪郭補正手段は、前記輪郭を検出した場合には、３Ｄ曲面式から輪郭線上に頂点を作成し、結線できなかった交点に当該頂点を加えて結線して、多角形平面を作成することを特徴とする請求項９に記載のコンピュータが実行可能なプログラム。
【請求項１１】
前記３Ｄ曲面は、ＮＵＲＢＳ曲面、Ｂｅｚｉｅｒ曲面、またはＢ−ｓｐｌｉｎｅ曲面であることを特徴とする請求項７〜請求項１０のいずれか１つに記載のコンピュータが実行可能なプログラム。
【請求項１２】
前記立方体格子の基本幅は、任意に設定可能であることを特徴とする請求項７〜請求項１１のいずれか１つに記載のコンピュータが実行可能なプログラム。
【請求項１３】
３Ｄ曲面モデルをポリゴンデータに変換する画像処理装置において、
前記３Ｄ曲面モデルの全体を囲むバウンディングボックスを生成し、当該バウンディングボックスを複数の立方体格子に分割する格子生成工程と、
前記３Ｄ曲面モデルと各立方体格子の線分との交点を検出する交点検出工程と、
前記立方体格子毎に、検出した交点を結線して多角形平面要素を生成して、ポリゴンデータを生成するポリゴン生成工程と、
を備えたことを特徴とする画像処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置、画像処理方法、およびコンピュータが実行可能なプログラムに関し、詳細には、ＮＵＲＢＳ曲面をポリゴンデータに変換する画像処理装置、画像処理方法、およびコンピュータが実行可能なプログラムに関する。
【背景技術】
【０００２】
工業製品の設計工程において利用される３次元形状モデルとして、ポリゴンメッシュ、ＮＵＲＢＳ（ＢｅｚｉｅｒとＢ−ｓｐｌｉｎｅを含む）曲面がある。ポリゴンメッシュは、形状表現の厳密さを追及するのではなく、形状を多面体として簡略化し、表示を高速化するために用いられるとともに、解析用のモデルとしてＣＡＥ等において利用される。これに対して、ＮＵＲＢＳ曲面は、複雑な自由曲面を含む３次元形状を厳密に表現することを目的として利用される。これらの特徴の相違のため、ＮＵＲＢＳ曲面とポリゴンメッシュ間ではデータ変換がよく行われる。ＮＵＲＢＳ曲面をポリゴンメッシュに変換する方法として、例えば、特許文献１が公知である。
【０００３】
しかしながら、従来技術では、ＮＵＲＢＳ形状が複雑な場合、すなわち、複数のＮＵＲＢＳ  Ｓｕｒｆａｃｅ（ＮＵＲＢＳ  Ｓｕｒｆａｃｅとは、１Ｔｒａｎｓｆｏｒｍノードに複数のＮｕｒｂｓ  Ｓｕｒｆａｃｅが存在しているデータに対して、１Ｔｒａｎｓｆｏｒｍノードに属するＳｕｒｆａｃｅの複合体をオブジェクトと表現、すなわち、オブジェクトとは人間が見た目の１パーツとなる。）が接し合って一つの形状を成しているオブジェクトの場合は、ＮＵＲＢＳ  Ｓｕｒｆａｃｅ毎にポリゴン化する必要があるため、隙間や穴空きが発生し、レンダリングした際に滑らかな連続した表面にならないという問題がある。
【０００４】
また、従来技術では、ＮＵＲＢＳ  Ｓｕｒｆａｃｅ（曲面定義）毎にポリゴン化する必要があるため、図１５に示すように、ＮＵＲＢＳ  Ｓｕｒｆａｃｅ毎に独立したポリゴンデータ（以下、「Ｍｅｓｈデータ」と称する場合もある）が存在するという構造であり、ＮＵＲＢＳ  Ｓｕｒｆａｃｅ毎に、ポリゴンデータの３Ｄ空間上の位置を決定する行列（以下「Ｔｒａｎｓｆｏｒｍデータ」と称する）が存在することになるため（Ｍｅｓｈ０，１，２，・・・毎に、Ｔｒａｎｓｆｏｒｍ０，１，２・・・が必要）、データ構造が複雑な形態となっていた。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平８−１３８０８３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は、上記に鑑みてなされたものであって、効率的に高品質なポリゴンデータの生成することが可能な画像処理装置、画像処理方法、およびコンピュータが実行可能なプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上述した課題を解決し、目的を達成するために、本発明は、３Ｄ曲面モデルをポリゴンデータに変換する画像処理装置において、前記３Ｄ曲面モデルの全体を囲むバウンディングボックスを生成し、当該バウンディングボックスを複数の立方体格子に分割する格子生成手段と、前記３Ｄ曲面モデルと各立方体格子の線分との交点を検出する交点検出手段と、前記立方体格子毎に、検出した交点を結線して多角形平面要素を生成して、ポリゴンデータを生成するポリゴン生成手段と、を備えたことを特徴とする。
【０００８】
また、本発明の好ましい態様によれば、前記ポリゴンデータの輪郭を補正する輪郭補正手段を備えることが望ましい。
【０００９】
また、本発明の好ましい態様によれば、前記輪郭補正手段は、前記交点検出手段で検出された交点に対して、立方体格子の交点の数が２以下または全ての交点が同一直線上に存在するものがある場合には、輪郭として検出することが望ましい。
【００１０】
また、本発明の好ましい態様によれば、前記輪郭補正手段は、前記輪郭を検出した場合には、３Ｄ曲面式から輪郭線上に頂点を作成し、結線できなかった交点に当該頂点を加えて結線して、多角形平面を作成することが望ましい。
【００１１】
また、本発明の好ましい態様によれば、前記３Ｄ曲面は、ＮＵＲＢＳ曲面、Ｂｅｚｉｅｒ曲面、またはＢ−ｓｐｌｉｎｅ曲面であることが望ましい。
【００１２】
また、本発明の好ましい態様によれば、前記立方体格子の基本幅は、任意に設定可能であることが望ましい。
【００１３】
上述した課題を解決し、目的を達成するために、本発明は、３Ｄ曲面モデルをポリゴンデータに変換する画像処理装置に搭載されるプログラムにおいて、コンピュータを、前記３Ｄ曲面モデルの全体を囲むバウンディングボックスを生成し、当該バウンディングボックスを複数の立方体格子に分割する格子生成手段と、前記３Ｄ曲面モデルと各立方体格子の線分との交点を検出する交点検出手段と、前記立方体格子毎に、検出した交点を結線して多角形平面要素を生成して、ポリゴンデータを生成するポリゴン生成手段として機能させることを特徴とする。
【００１４】
また、本発明の好ましい態様によれば、さらに、コンピュータを、前記ポリゴンデータの輪郭を補正する輪郭補正手段として機能させることが望ましい。
【００１５】
また、本発明の好ましい態様によれば、前記輪郭補正手段は、前記交点検出手段で検出された交点に対して、立方体格子の交点の数が２以下または全ての交点が同一直線上に存在するものがある場合には、輪郭として検出することが望ましい。
【００１６】
また、本発明の好ましい態様によれば、前記輪郭補正手段は、前記輪郭を検出した場合には、３Ｄ曲面式から輪郭線上に頂点を作成し、結線できなかった交点に当該頂点を加えて結線して、多角形平面を作成することが望ましい。
【００１７】
また、本発明の好ましい態様によれば、前記３Ｄ曲面は、ＮＵＲＢＳ曲面、Ｂｅｚｉｅｒ曲面、またはＢ−ｓｐｌｉｎｅ曲面であることが望ましい。
【００１８】
また、本発明の好ましい態様によれば、前記立方体格子の基本幅は、任意に設定可能であることが望ましい。
【００１９】
上述した課題を解決し、目的を達成するために、本発明は、３Ｄ曲面モデルをポリゴンデータに変換する画像処理装置において、前記３Ｄ曲面モデルの全体を囲むバウンディングボックスを生成し、当該バウンディングボックスを複数の立方体格子に分割する格子生成工程と、前記３Ｄ曲面モデルと各立方体格子の線分との交点を検出する交点検出工程と、前記立方体格子毎に、検出した交点を結線して多角形平面要素を生成して、ポリゴンデータを生成するポリゴン生成工程と、を含むことを特徴とする。
【発明の効果】
【００２０】
本発明によれば、３Ｄ曲面モデルをポリゴンデータに変換する画像処理装置において、前記３Ｄ曲面モデルの全体を囲むバウンディングボックスを生成し、当該バウンディングボックスを複数の立方体格子に分割する格子生成手段と、前記３Ｄ曲面モデルと各立方体格子の線分との交点を検出する交点検出手段と、前記立方体格子毎に、検出した交点を結線して多角形平面要素を生成して、ポリゴンデータを生成するポリゴン生成手段と、を備えているので、効率的に高品質なポリゴンデータの生成することが可能な画像処理装置、画像処理方法、およびコンピュータが実行可能なプログラムを提供することが可能になるという効果を奏する。
【図面の簡単な説明】
【００２１】
【図１】図１は、本実施の形態に係る画像処理装置の機能構成図である。
【図２】図２は、図１の画像処理装置のハードウェア構成例を示す図である。
【図３】図３は、図１の画像処理装置のポリゴンデータを生成する処理を説明するためのフローチャートである。
【図４−１】図４−１は、球をポリゴン化する場合を説明するための図である。
【図４−２】図４−２は、球をポリゴン化する場合を説明するための図である。
【図４−３】図４−３は、球をポリゴン化する場合を説明するための図である。
【図５】図５は、立方体格子を生成する方法を説明するための図である。
【図６】図６は立方体格子に形成されるポリゴン面の形状を説明するための図である。
【図７】図７は、立方体格子でポリゴン面を生成する処理を説明するための図である。
【図８】図８は、本実施の形態の方法でＮｕｒｂｓ球をポリゴン化した場合の一例を示す図である。
【図９】図９は、本実施の形態の方法でポリゴン化した場合に生じる輪郭を説明するための図である。
【図１０】図１０は、本実施の形態の方法でポリゴン化した場合に生じる輪郭を説明するための図である。
【図１１】図１１は、輪郭補正の方法を説明するための図である。
【図１２】図１２は、輪郭補正の方法を説明するための図である。
【図１３】図１３は、輪郭の再現サンプルの一例を示す図である。
【図１４】図１４は、ポリゴンデータのデータ構造の一例を示す図である。
【図１５】図１５は、従来技術を説明するための図である。
【発明を実施するための形態】
【００２２】
以下に、この発明にかかる画像処理装置、画像処理方法、およびコンピュータが実行可能なプログラムの実施例を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。また、下記実施の形態における構成要素には、当業者が容易に想定できるものまたは実質的に同一のものが含まれる。
【００２３】
図１は、本実施の形態に係る画像処理装置の機能構成図である。本実施の形態の画像処理装置は、３Ｄ曲面で表現されたモデルを、三角形等の多角形平面要素（ポリゴン）からなるポリゴンモデルに変換するポリゴン化機能を備えており、このポリゴン化機能では、隣接する複数の曲面要素を一体としてポリゴン化する機能を実装している。すなわち、本実施の形態では、複数の曲面要素を含むオブジェクトを一体としてポリゴン化することが可能となっており、これにより、効率的に筋や隙間のない高品質なポリゴンデータの生成でき、また、簡単なデータ構造にすることができる。
【００２４】
本実施の形態の画像処理装置は、図１に示すように、３Ｄ曲面モデル入力部１１と、格子生成部１２と、交点検出部１３と、ポリゴン生成部１４と、輪郭補正部１５と、データ保存部１６と、ポリゴン処理部１７とを備えている。
【００２５】
３Ｄ曲面モデル入力部１１は、対象となる３Ｄ曲面モデル（図４−１参照）を入力して、格子生成部１２に出力する。ここで、３Ｄ曲面は、例えば、ＮＵＲＢＳ曲面、Ｂｅｚｉｅｒ曲面、およびＢ−ｓｐｌｉｎｅ曲面である。以下の説明では、一例としてＮＵＲＢＳ曲面について説明する。３Ｄ曲面モデル入力部１１は、例えば、予めＨＤやＵＳＢメモリ等の記憶装置に記憶されている３Ｄ曲面モデルを読み出したり、ネットワークを介して受信した３Ｄ曲面モデルを格子生成部１２に出力することができる。
【００２６】
格子生成部１２は、３Ｄ曲面モデル入力部１１から入力される３Ｄ曲面モデルの全体を囲むバウンディングボックスを生成し、生成したバウンディングボックスを、基本幅Ｗの複数の立方体格子（図４−２参照）に分割する。
【００２７】
交点検出部１３は、３Ｄ曲面モデルと立方体格子の線分（辺）との交点を検出する。ポリゴン生成部１４は、立方体格子毎に、検出された交点を結線して多角形平面要素（ポリゴン面）を生成する（図６，図７参照）。輪郭補正部１５は、ポリゴンデータの輪郭を補正する（図１１参照）。データ保存部１６は、輪郭が補正されたポリゴンデータをメモリ格納する。ポリゴン処理部１７は、データ保存部１６に格納されたポリゴンデータに基づいてレンダリング表示を行ったり、ポリゴンデータを外部出力する等の各種データ処理を行う。
【００２８】
本発明の画像処理装置は、複数の機器（例えば、ホストコンピュータ、インターフェイス機器、スキャナ、プリンタ等）から構成されるシステムに適用しても、１つの機器から構成される装置（ホストコンピュータ等）に適用しても良い。
【００２９】
また、本発明の目的は、上述した画像処理装置の機能を実現するソフトウエアのプログラムコードを記録した記録媒体を、システムまたは装置に供給し、そのシステムまたは装置のコンピュータ（または、ＣＰＵ、ＭＰＵ、ＤＳＰ）が記録媒体に格納されたプログラムコードを実行することによっても達成することが可能である。この場合、記録媒体から読み出されたプログラムコード自体が前述した画像処理装置の機能を実現することになり、そのプログラムコードまたはそのプログラムを記憶した記録媒体は本発明を構成することになる。プログラムコードを供給するための記録媒体としては、ＦＤ、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリ、ＲＯＭなどの光記録媒体、磁気記録媒体、光磁気記録媒体、半導体記録媒体を使用することができる。  
【００３０】
また、コンピュータが読み出したプログラムコードを実行することにより、前述した画像処理装置の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）などが実際の処理の一部または全部を行い、その処理によって前述した画像処理装置の機能が実現される場合も含まれること言うまでもない。
【００３１】
図２は、図１の画像処理装置のハードウェア構成例を示す図である。図１の画像処理装置は、上述したように、コンピュータシステムで構成することができる。同図に示すように、コンピュータシステムは、ＣＰＵ２１，ＲＯＭ２２，ＲＡＭ２３，表示装置２４，印刷装置２５、入力装置２６，ハードディスク２７，ＣＤ−ＲＯＭドライブ２８、通信部２９、ＵＳＢポート３０を備えており、各部はバスを介して互いに接続されている。
【００３２】
ＣＰＵ２１は、バスを介して接続されたハードディスク２７に格納されたＯＳによりノート型パソコン全体の制御を行うとともに、ハードディスク２７に格納された各種のプログラムに基づいて処理を実行する機能を司る。ＲＯＭ２２は、ＢＩＯＳやデータ等を格納している。ＲＡＭ２３は、ＣＰＵ２１による各種プログラムの実行時にワークエリアとして利用されるメモリ機能を有している。
【００３３】
表示装置２４は、例えば、ＬＣＤ、プラズマ、有機ＥＬ、ＣＲＴ等の表示デバイスであり、ＣＰＵ２１の制御に従って画面の表示制御を行い、画面に各種情報を表示する。印刷装置２５は、インクジェット方式や電子写真方式のプリンタである。
【００３４】
入力装置２６は、ユーザが入力操作を行うためのユーザインターフェースであり、文字、コマンド等を入力する各種キーより構成されるキーボードや、画面上のカーソルを移動させたり、各種メニューを選択するマウスおよびスライスパッド等を備えている。  
【００３５】
ハードディスク２７は、例えば、Ｗｉｎｄｏｗｓ（登録商標）  ＯＳ（例えば、Ｗｉｎｄｏｗｓ（登録商標）  ＸＰ、Ｗｉｎｄｏｗｓ（登録商標）  ＶＩＳＴＡ等）のパソコン全体の制御を行うためのＯＳ、各種ドライバ、上記図１の各部（３Ｄ曲面モデル入力部１１と、格子生成部１２と、交点検出部１３と、ポリゴン生成部１４と、輪郭補正部１５と、データ保存部１６と、ポリゴン処理部１７）の機能を実現するためのアプリケーションプログラム等を記憶する機能を有している。
【００３６】
ＣＤ−ＲＯＭドライブ２８は、ＣＤ−ＲＯＭ３１のデータをリードする。ＵＳＢポート３０は、ＵＳＢデバイスを接続するためのポートであり、例えば、ＵＳＢメモリ３２に対して、データのリード／ライトを行う。通信部２９は、インターネット等のネットワークに接続してデータ通信を行ったり、赤外線で他の機器と通信する機能を司る。
【００３７】
図３は、上記図１の画像処理装置のポリゴンデータを生成する処理を説明するためのフローチャート、図４−１〜図４−３は、ＮＵＲＢＳ球をポリゴン化する場合を説明するための図である。図５は、立方体格子を生成する方法を説明するための図である。図６は立方体格子に形成されるポリゴン面の形状を説明するための図である。図７は、立方体格子でポリゴン面を生成する処理を説明するための図である。図８は、本実施の形態の方法でＮＵＲＢＳ球をポリゴン化した場合の一例を示す図である。図９および図１０は、本実施の形態の方法でポリゴン化した場合に生じる輪郭を説明するための図である。図１１および図１２は、輪郭補正の方法を説明するための図である。図１３は、輪郭の再現サンプルの一例を示す図、図１４は、ポリゴンデータのデータ構造の一例を示す図である。
【００３８】
上記図１の画像処理装置のポリゴンデータの生成手順を図３のフローチャートに従って、図４−１〜図１５を参照しつつ説明する。
【００３９】
図３において、３Ｄ曲面モデル入力部１１は、３Ｄ曲面モデルとして、ＮＵＲＢＳ曲面１００（例えば、図４−１に示す球モデル）を入力して、格子生成部１２に出力する（ステップＳ１）。
【００４０】
格子生成部１２は、立方体格子の基本幅Ｗを入力する（ステップＳ２）。立方体格子の基本幅Ｗは、任意に設定可能となっており、例えば、格子生成部１２は、初期値の基本幅Ｗを入力したり、ユーザ操作に応答して、キーボードやマウス等の入力装置から立方体格子の基本幅Ｗを入力することができる。
【００４１】
格子生成部１２は、ＮＵＢＳ曲面要素を一体化してポリゴン化するために、ＮＵＲＢＳ曲面１００の全体を囲むバウンディングボックス２００を生成し、例えば、図５に示すように、その８頂点の座標｛ａ（ｘ０，ｙ０，ｚ０）、ｂ（ｘ１，ｙ１，ｚ１）、ｃ（ｘ２，ｙ２，ｚ２）、ｄ（ｘ３，ｙ３，ｚ３）、ｅ（ｘ４，ｙ４，ｚ４）、ｆ（ｘ５，ｙ５，ｚ５）、ｇ（ｘ６，ｙ６，ｚ６）、ｈ（ｘ７，ｙ７，ｚ７）｝を取得する（ステップＳ３）。格子生成部１２は、バウンディングボックス２００の各辺を基本幅Ｗで分割し、分割した格子の基本となる格子点（頂点）の座標を取得し（ステップＳ４）、全ての格子点をＸ，Ｙ，Ｚ軸と平行に結線し、立方体格子２０１（図４−２参照）を生成する（ステップＳ５）。
【００４２】
交点検出部１３は、立方体格子２０１の線分（格子点間を結ぶ線分）とＮＵＲＢＳ曲面との交点２０２を検出する（ステップＳ６）。ポリゴン生成部１４は、交点２０２を有する全ての立方体格子２０１を抽出し（図４−３参照）し、抽出した立方体格子２０１毎に、検出した交点２０２を頂点として結線して、多角形平面要素（ポリゴン）を生成して、ポリゴンデータを生成する（ステップＳ７）。
【００４３】
立方体格子の線分とＮＵＲＢＳ曲面との交点を結線した多角形平面は、例えば、図６（ａ）〜（ｅ）に示すようなパターンとなる。同図に示す例では、多角形平面は、３角形、４角形（正方形、長方形、台形）、５角形、６角形となる。
【００４４】
ここで、多角形平面要素の具体的な生成方法を図７を参照して説明する。図７は、ＮＵＲＢＳ球に対して適用した例を示している。まず、（１）ある格子点からＮＵＲＢＳ面との交点の検出する経路を定め、（２）８格子点を基準として同様の処理を行い、（３）検出された面が独立した複数の面であるか、重なった面であるかを判断し、重なったものは削除する。
【００４５】
図７を例にすると、Ａを基準とした経路は、以下のようになる。
Ａ−Ｅ−Ｈ−Ｇ  （交点αを検出）
Ａ−Ｅ−Ｆ−Ｇ  （交点αを検出：同一の場合は重複登録しない）
Ａ−Ｂ−Ｆ−Ｇ  （交点βを検出）
Ａ−Ｂ−Ｃ−Ｇ  （交点βを検出：同一の場合は重複登録しない）
Ａ−Ｄ−Ｃ−Ｇ  （交点γを検出）
Ａ−Ｄ−Ｈ−Ｇ  （交点γを検出：同一の場合は重複登録しない）
【００４６】
交点として検出するのはＮＵＲＢＳ表面との交点とする。検出した交点を結線すると表面からみて必ず反時計まわりの頂点順として検出することができる。基準点をＢ〜Ｇまで変化させて同様に、面を検出した場合は、各面を比較して重なっている場合は小さい方を削除する。
【００４７】
図８は、本実施の形態の方法で、ＮＵＲＢＳ球をポリゴン化した場合の一例を示しており、左側はポリゴン数小（立方体格子の基本幅Ｗ＝大）の場合、真ん中はポリゴン数中（立方体格子の基本幅Ｗ＝中）の場合、右側はポリゴン数大（立方体格子の基本幅Ｗ＝小の場合を示している。
【００４８】
図９（ａ）および図１０（ａ）は、ＣＡＤデータを従来技術の方法でポリゴン化した場合を示しており、図９（ｂ）および図１０（ｂ）は、ＣＡＤデータを本実施の形態の方法でポリゴン化した場合を示している。従来技術の方法では、ポリゴン化はＳｕｒｆａｃｅ毎に単独でポリゴン化しているため、図９（ａ）および図１０（ａ）に示すように、筋や隙間が生じているのに対して、本実施の形態の方法では、複数の曲面要素を含むオブジェクトを一体としてポリゴン化しているため、図９（ｂ）および図１０（ｂ）に示すように、筋や隙間が生じていない。しかしながら、同図に示すように、本実施の形態の方法でも、わずかに外側に輪郭が発生している。そこで、本実施の形態では、以下のようにして、輪郭を補正している。
【００４９】
図３に戻り、輪郭補正部１５は、ポリゴンデータの輪郭処理を行う（ステップＳ８〜Ｓ１１）。上記ステップＳ６で検出した全ての交点について以下の判定を行う。まず、立方体格子の交点の数が２以下または全ての交点が同一直線上に存在するものがあるか検出し（ステップＳ９、１０）、立方体格子の交点の数が２以下または全ての交点が同一直線上に存在するものがある場合には（ステップＳ９、１０の「Ｙｅｓ」）、その輪郭を補正する（ステップＳ１１）。このステップＳ８〜Ｓ１１の処理は、上記ステップＳ６で検出した全ての交点について行われる。
【００５０】
図１１および図１２を参照して、輪郭補正の具体例を説明する。図１１に示すように、立方体格子のうち、多角形平面を構成できないＮＵＲＢＳ面１０１との交点２０２を検出した場合（交点が２点以下の場合や全ての交点が同一直線上に存在する場合）には、立方格子点内で多角形平面が切れている、すなわち輪郭を含んでいることになる。そこで、図１２に示すように、交点２０２を検出しているので、ＮＵＲＢＳ曲面式から直接輪郭線上に頂点２０４を作成する。結線できなかった交点２０２に頂点２０４を加えて結線して、多角形平面を作成する。また、抽出したＮＵＲＢＳ輪郭線候補となる線分が立方体格子を通過する場合は、オブジェクトの輪郭となる。オブジェクトの輪郭は格子面と輪郭候補となる線分との交点を結んだものであり、この交点はどの格子内に所属するかは判別できているので、ポリゴン輪郭として結線して、多角形平面を生成することができる。
【００５１】
図１３は、上記輪郭補正を行った場合の例（レンダリング結果）を示しており、ａは上記輪郭補正を行わない場合を示しており、輪郭がきれいな線になっていない。これに対して、ｂは上記輪郭補正を行った場合を示しており、輪郭補正を行った場合は、綺麗な曲線となっている。
【００５２】
図３に戻り、データ保存部１６は、輪郭が補正されたポリゴンデータをメモリに格納する（ステップＳ１２）。図１４は、本実施の形態により処理したポリゴンデータのデータ構造の一例を示している。同図に示すように、本実施の形態では、複数の曲面要素を一体としてポリゴン化しているので、処理対象のポリゴンデータは全て纏まったデータ構造となっており、すなわち、図１５で示したＭｅｓｈ０，１，２，・・・・を全て含んだ１つのＭｅｓｈデータとなるため、データ構造が簡潔で、ポリゴン形状の描画特性等の追加・修正が容易である。
【００５３】
以上説明したように、本実施の形態によれば、格子生成部１２は、３Ｄ曲面モデルの全体を囲むバウンディングボックスを生成し、当該バウンディングボックスを複数の立方体格子に分割し、交点検出部１３は、３Ｄ曲面モデルと各立方体格子の線分との交点を検出し、ポリゴン生成部１４は、立方体格子毎に、検出した交点を結線して多角形平面要素を生成して、ポリゴンデータを生成することとしたので、複数の曲面要素を一体にポリゴン化して、筋や隙間のない高品質なポリゴンデータを効率的に生成することが可能となる。また、これにより、ポリゴンデータのデータ構造を簡素化することが可能となる。
【００５４】
また、本実施の形態では、輪郭補正部１５は、検出された交点に対して、立方体格子の交点の数が２以下または全ての交点が同一直線上に存在するものがある場合には、輪郭として検出し、輪郭を検出した場合には、３Ｄ曲面式から輪郭線上に頂点を作成し、結線できなかった交点に当該頂点を加えて結線して、多角形平面を作成することとしたので、輪郭のない高品質の曲線を再現することが可能となる。
【産業上の利用可能性】
【００５５】
以上のように、本発明にかかる画像処理装置、画像処理方法、およびコンピュータが実行可能なプログラムは、３Ｄ曲面をポリゴンデータに変換する場合に有用である。
【符号の説明】
【００５６】
１１  ３Ｄ曲面モデル入力部
１２  格子生成部
１３  交点検出部
１４  ポリゴン生成部
１５  輪郭補正部
１６  データ保存部
１７  ポリゴン処理部
２１  ＣＰＵ
２２  ＲＯＭ
２３  ＲＡＭ
２４  表示装置
２５  印刷装置
２６  入力装置
２７  ハードディスク
２８  ＣＤ−ＲＯＭドライブ
２９  通信部
３０  ＵＳＢポート
【図１】
2011013784.tif 000003
【図２】
2011013784.tif 000004
【図３】
2011013784.tif 000005
【図４−１】
2011013784.tif 000006
【図４−２】
2011013784.tif 000007
【図４−３】
2011013784.tif 000008
【図５】
2011013784.tif 000009
【図６】
2011013784.tif 000010
【図７】
2011013784.tif 000011
【図８】
2011013784.tif 000012
【図９】
2011013784.tif 000013
【図１０】
2011013784.tif 000014
【図１１】
2011013784.tif 000015
【図１２】
2011013784.tif 000016
【図１３】
2011013784.tif 000017
【図１４】
2011013784.tif 000018
【図１５】
2011013784.tif 000019