(57)【特許請求の範囲】
【請求項１】
三角ポリゴンを用いて多面体を生成する多面体生成装置で使用される多面体生成方法であって、
前記三角ポリゴンの法線ベクトルと、前記多面体の内部点から前記三角ポリゴンへのベクトルとの内積が負となる場合は、前記多面体生成装置に前記三角ポリゴンの法線ベクトルを変更させる変更工程を有することを特徴とする多面体生成方法。
【請求項２】
三角ポリゴンを用いて多面体を生成する多面体生成装置で使用される多面体生成方法であって、
前記三角ポリゴンの法線ベクトルと、前記多面体の内部点から前記三角ポリゴンへのベクトルとの内積が負であるか否かに応じて、前記多面体生成装置に前記三角ポリゴンの法線ベクトルを変更させる変更工程を有することを特徴とする多面体生成方法。
【請求項３】
前記多面体生成装置は、３次元レンダリングシステムであることを特徴とする請求項１又は２に記載の多面体生成方法。
【請求項４】
前記多面体の内部点は、前記多面体の重心点であることを特徴とする請求項１から３の何れかに記載の多面体生成方法。
【請求項５】
前記三角ポリゴンの法線ベクトルは、前記三角ポリゴンの頂点の登録順序により定義されることを特徴とする請求項１から４の何れかに記載の多面体生成方法。
【請求項６】
前記多面体生成装置の表示手段に前記多面体を表示させる表示工程をさらに有することを特徴とする請求項１から５の何れかに記載の多面体生成方法。
【請求項７】
座標空間上に点在する点列から前記三角ポリゴンを生成する三角ポリゴン生成工程をさらに有することを特徴とする請求項１から６の何れかに記載の多面体生成方法。
【請求項８】
三角ポリゴンを用いて多面体を生成する多面体生成装置であって、
前記三角ポリゴンの法線ベクトルと、前記多面体の内部点から前記三角ポリゴンへのベクトルとの内積が負となる場合は、前記三角ポリゴンの法線ベクトルを変更することを特徴とする多面体生成装置。
【請求項９】
三角ポリゴンを用いて多面体を生成する多面体生成装置であって、
前記三角ポリゴンの法線ベクトルと、前記多面体の内部点から前記三角ポリゴンへのベクトルとの内積が負であるか否かに応じて、前記三角ポリゴンの法線ベクトルを変更することを特徴とする多面体生成装置。
【請求項１０】
前記多面体生成装置は、３次元レンダリングシステムであることを特徴とする請求項８又は９に記載の多面体生成装置。
【請求項１１】
前記多面体の内部点は、前記多面体の重心点であることを特徴とする請求項８から１０の何れかに記載の多面体生成装置。
【請求項１２】
前記三角ポリゴンの法線ベクトルは、前記三角ポリゴンの頂点の登録順序により定義されることを特徴とする請求項８から１１の何れかに記載の多面体生成装置。
【請求項１３】
前記多面体生成装置の表示手段に前記多面体を表示することを特徴とする請求項８から１２の何れかに記載の多面体生成装置。
【請求項１４】
座標空間上に点在する点列から前記三角ポリゴンを生成することを特徴とする請求項８から１３の何れかに記載の多面体生成装置。
【請求項１５】
三角ポリゴンを用いて多面体の生成する工程と、
前記三角ポリゴンの法線ベクトルと、前記多面体の内部点から前記三角ポリゴンへのベクトルとの内積が負となる場合は、前記三角ポリゴンの法線ベクトルを変更する工程とをコンピュータに実行させるプログラムを記録したことを特徴とする記録媒体。
【請求項１６】
三角ポリゴンを用いて多面体の生成する工程と、
前記三角ポリゴンの法線ベクトルと、前記多面体の内部点から前記三角ポリゴンへのベクトルとの内積が負であるか否かに応じて、前記三角ポリゴンの法線ベクトルを変更する工程とをコンピュータに実行させるプログラムを記録したことを特徴とする記録媒体。
【請求項１７】
前記プログラムは、３次元レンダリングシステムに適用可能なプログラムであることを特徴とする請求項１５又は１６に記載の記録媒体。
【請求項１８】
前記多面体の内部点は、前記多面体の重心点であることを特徴とする請求項１５から１７の何れかに記載の記録媒体。
【請求項１９】
前記三角ポリゴンの法線ベクトルは、前記三角ポリゴンの頂点の登録順序により定義されることを特徴とする請求項１５から１８の何れかに記載の記録媒体。
【請求項２０】
前記多面体生成装置の表示手段に前記多面体を表示させる表示工程をさらに有することを特徴とする請求項１５から１９の何れかに記載の記録媒体。
【請求項２１】
座標空間上に点在する点列から前記三角ポリゴンを生成する三角ポリゴン生成工程をさらに有することを特徴とする請求項１５から２０の何れかに記載の記録媒体。
【請求項２２】
請求項１から７の何れかに記載の多面体生成方法を使用することを特徴とするカラー画像処理装置。
【請求項２３】
請求項８から１４の何れかに記載の多面体生成装置を有することを特徴とするカラー画像処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、多面体生成方法、多面体生成装置、記録媒体、およびカラー画像処理装置に関する。
【０００２】
【従来の技術】
色を構成する要素として３つの属性（明るさ、色相、彩度）があるのは広く知られていることである。こられ３つの属性を各々直交する座標に割り当て、３次元ユークリッド空間で表現する例として、ＲＧＢ色空間やＸＹＺ色空間等が広く用いられている。
【０００３】
様々な色空間の中でも空間内の距離と色差を結び付けたものとして均等知覚色空間というものが存在する。その中でもＣＩＥ１９７６−Ｌａｂ空間（以下、単にＬａｂ色空間）は、色のマッピング状態や各カラーデバイスの色再現領域を解析するために、よく用いられる均等知覚色空間の一つである。色のマッピング状態や各カラーデバイスの色再現領域を解析するためには、カラーデバイスが出力する色（Ｌａｂ値）を測定、又は計算で求め、該Ｌａｂ色空間内にプロットする必要がある。ここで、プロットというのは、グラフにそのデータを記すことを意味する．二変数のプロットであればＸＹ座標等の平面上における座標位置に点列等を記すが、座標が空間として構成される場合は、３Ｄのレンダリング機能を利用しなければならない。
【０００４】
３Ｄのレンダリングシステムは、予め設定された観察位置を通して、ある投影面に写像される画像を生成することで空間上のオブジェクトを疑似的に二次元の画像で再現するものである。さらには、操作する利用者がより詳細にその様子を観察するために、回転や拡大縮小等の機能が付加されている場合も多い。このような機能を用いることで、色空間内に点在する色のデータを可視化することは従来より行なわれている。
【０００５】
【発明が解決しようとする課題】
ところで、前述した３Ｄのレンダリング機能を提供する３次元レンダリングシステムは、多くの種類が存在する。その中でも、隠面処理の都合上、描画する三角ポリゴンの法線ベクトルを一致させなければならないものが存在する。
【０００６】
しかし、従来より三角ポリゴン等で構成された多面体について、該ポリゴン群の法線ベクトルを自動処理によって一致させる手法については何ら技術開示されていない。このため、隠面処理の都合上、描画する三角ポリゴンの法線ベクトルを一致させなければならない３次元レンダリングシステムにおいては、法線ベクトルが不揃いのポリゴン群を描画することは不可能であった。
【０００７】
ここで、３次元レンダリングシステムにおいて、登録する三角ポリゴンの３つ頂点の順番と該三角ポリゴンの法線ベクトルの向きとの関係を、図９に基づいて説明する。
【０００８】
三角ポリゴンにおける法線ベクトルを考えると、長さは一意に求められるが、その向きは必要に応じて明確に定義しなければならない。そこで、登録されている頂点の順番でみたときに、右ネジの進行方向と同じように進む方向を法線ベクトルの向きとして定義する。０４→１９→０５と右回りで登録されている三角ポリゴンの場合は奥方向に法線ベクトルが向いており、ちょうど右ネジが右回転の時に進行する場合と同じである。一方、０４→１１→０５と登録されている三角ポリゴンの場合は手前方向に法線ベクトルが向き、ちょうど右ネジを左回転させた時に進行する方向と同じである。この例から、０４→１９→０５と登録されている三角ポリゴンと、０４→１１→０５と登録されている三角ポリゴンとは、法線ベクトルが一致していないことがわかる。
【０００９】
また、このような法線ベクトルが一致しない三角ポリゴン群を、上記システムにおいて表示すると、本来は描画されるべき三角ポリゴンが表示されなかったりするという問題も生じる。
【００１０】
本発明は、このような不都合を解決することを目的とする。
【００１１】
【課題を解決するための手段】
本発明に係る多面体生成方法は、例えば、三角ポリゴンを用いて多面体を生成する多面体生成装置で使用される多面体生成方法であって、前記三角ポリゴンの法線ベクトルと、前記多面体の内部点から前記三角ポリゴンへのベクトルとの内積が負となる場合は、前記多面体生成装置に前記三角ポリゴンの法線ベクトルを変更させる変更工程を有することを特徴とする。また、本発明に係る他の多面体生成方法は、例えば、三角ポリゴンを用いて多面体を生成する多面体生成装置で使用される多面体生成方法であって、前記三角ポリゴンの法線ベクトルと、前記多面体の内部点から前記三角ポリゴンへのベクトルとの内積が負であるか否かに応じて、前記多面体生成装置に前記三角ポリゴンの法線ベクトルを変更させる変更工程を有することを特徴とする。また、本発明に係るカラー画像処理装置は、例えば、上記の多面体生成方法を使用することを特徴とする。
【００１２】
本発明に係る多面体生成装置は、例えば、三角ポリゴンを用いて多面体を生成する多面体生成装置であって、前記三角ポリゴンの法線ベクトルと、前記多面体の内部点から前記三角ポリゴンへのベクトルとの内積が負となる場合は、前記三角ポリゴンの法線ベクトルを変更することを特徴とする。また、本発明に係る他の多面体生成装置は、例えば、三角ポリゴンを用いて多面体を生成する多面体生成装置であって、前記三角ポリゴンの法線ベクトルと、前記多面体の内部点から前記三角ポリゴンへのベクトルとの内積が負であるか否かに応じて、前記三角ポリゴンの法線ベクトルを変更することを特徴とする。また、本発明に係るカラー画像処理装置は、例えば、上記の多面体生成装置を有することを特徴とする。
【００１３】
本発明に係る記録媒体は、例えば、三角ポリゴンを用いて多面体の生成する工程と、前記三角ポリゴンの法線ベクトルと、前記多面体の内部点から前記三角ポリゴンへのベクトルとの内積が負となる場合は、前記三角ポリゴンの法線ベクトルを変更する工程とをコンピュータに実行させるプログラムを記録したことを特徴とする。また、本発明に係る他の記録媒体は、例えば、三角ポリゴンを用いて多面体の生成する工程と、前記三角ポリゴンの法線ベクトルと、前記多面体の内部点から前記三角ポリゴンへのベクトルとの内積が負であるか否かに応じて、前記三角ポリゴンの法線ベクトルを変更する工程とをコンピュータに実行させるプログラムを記録したことを特徴とする。
【００３０】
【発明の実施の形態】
以下、図面を参照して、本発明を詳細に説明する。
【００３１】
本発明の第１の実施の形態を、図１ないし図６に基づいて説明する。
【００３２】
まず、本発明の概略構成について説明する。図６は、カラー画像処理装置１における３Ｄのレンダリング機能を提供する３次元レンダリングシステム１０（多面体生成装置）の１例を示す。
【００３３】
本３次元レンダリングシステム１０は、データ生成手段１１と、データ変更手段１２と、表示手段１３とを具えている。なお、１４は、生成した多面体のデータを保存するファイルシステムである。１５は、後述する実施の形態で用いるメモリである。
【００３４】
ここで、データ生成手段１１は、座標空間上に点在する点列を取り込み、検索対象辺から三角形を派生させ、該三角形の頂点を多面体を構成する三角ポリゴンのデータ群として生成する。このような多面体の生成処理によって、各三角ポリゴンの頂点を１組のデータ群としてファイルシステム１４に登録してゆく。
【００３５】
データ変更手段１２は、多面体を構成する各三角ポリゴンの法線ベクトルを計算し、必要に応じて該法線ベクトルを適宜変更することにより、多面体を構成する全ての三角ポリゴンの法線ベクトルを一致させる。すなわち、まず、生成された多面体の内部に点を一つ設定する。通常は三角ポリゴン座標より求めた重心点は該多面体の内部に収まるので、該重心点を内部点として用いるが特に重心点である必要はない。次に、登録された三角ポリゴンの頂点データ１組のデータを取り出す。頂点データは、登録されている順序と該頂点の座標データから外積ベクトルを求め、これを法線ベクトルとする。次に、三角ポリゴンの三角形としての重心点を求め、さらに、前記内部点とのベクトルを求めることにより、内部点と三角形としての重心点とを結ぶベクトルを算出する。次に、その算出したベクトルと、前記法線ベクトルとの内積をとり、該求めたスカラー値を用いて必要に応じて、登録されている頂点データの順序を適宜入れ換える。このような処理によって、全ての三角ポリゴンの法線ベクトルを一致させる。
【００３６】
表示手段１３は、多面体を構成する三角ポリゴンの頂点の順序を適宜変更した後の法線ベクトルが全て一致した多面体を表示させる。
【００３７】
以下、図面を参照しながら、本発明に係わる好適な例について詳細に説明する。
【００３８】
図１は、座標空間に点在する点列を取り囲む多面体生成処理を示したフローチャートである。最初に、ステップＳ１１において、初期化処理を行う。ここで最初の三角形の探索を行う。最初の三角形は座標空間上に点在する点列の最大値又は最小値等の極点近傍付近で探索する。次に、ステップＳ１２において、探索対象辺を再編成し、さらに、探索対象となる辺をファイルシステム１４に登録してゆく。
【００３９】
ステップＳ１３では、前記ステップＳ１２において登録された辺を順に調べることで、検索が終了か否かの判断を行う。検索が終了していない場合はステップＳ１４に進み、検索対象辺のアドレスヘアクセスし、ファイルシステム１４に登録された辺の座標データ等を取り出す。
【００４０】
ステップＳ１５では、ファイルシステム１４から取り出された座標データ等をもとに、検索対象辺からの新たな三角形の派生が可能か検証し、新頂点候補を探索する。ステップＳ１６において、新頂点候補が既に登録されたものと重複しないか等を判定した後に、新たな登録対象であった場合には、ステップＳ１７において、ファイルシステム１４に追加登録を行う。このようにして順次探索を行い、各三角形から隣接する新たな三角形を派生させ、これを登録することによって、ポリゴンデータの生成が可能となる。
【００４１】
上述した図２の処理によって、図４および図５で示されるように、座標空間上に点在する点列を取り囲む多面体の生成を自動的に実行することが可能となる。次に、３次元レンダリングシステムにおいて、登録する三角ポリゴンの３つ頂点の順番と該三角ポリゴンの法線ベクトルの向きとの関係を、図３に基づいて説明する。
【００４２】
三角ポリゴンにおける法線ベクトルを考えると、長さは一意に求められるが、その向きは必要に応じて明確に定義しなければならない。そこで、本発明では、登録されている頂点の順番でみたときに、右ネジの進行方向と同じように進む方向を法線ベクトルの向きとして定義し、多面体を構成する全ての三角ポリゴンの法線ベクトルの方向を揃える処理を行う。
【００４３】
前述した図９に示した例では、０４→１９→０５と右回りで登録されている三角ポリゴンの場合は奥方向に法線ベクトルが向いており、２つの三角ポリゴンが隣接しているのに法線ベクトルが互いに全く逆の方向を示している。このような場合において、法線ベクトルの方向を変更する。具体的には、図３に示すように、０４→１９→０５を並び替えて、０４→０５→１９と登録し直すことによって、法線ベクトルの方向を揃える。
【００４４】
多面体を構成する三角ポリゴンの法線ベクトルの方向を全て一致させるためには、全ての三角ポリゴンの法線が外向きに設定させる必要がある。そのためには、多面体の内部の点（内部点又は重心点）から各三角形の重心点に向けてベクトルを求め、該ベクトルと法線ベクトルの内積をとり、該内積値が負数になった場合にその三角ポリゴンの頂点データの登録順序を変更するという処理を行なえばよい。
【００４５】
図１は、多面体を構成する全ての三角ポリゴンの法線ベクトルを一致させるために、各三角ポリゴンのベクトルを調べて頂点の登録順序を変更するデータ変更処理について説明したフローチャートである。
【００４６】
まず、ステップＳ４１１において、初期化の処理を適宜行う。ステップＳ４１２のデータ読込み処理において、ファイルシステム１４に記録されている三角ポリゴンの各データを読み込む。ステップＳ４１３では、読込んだ三角ポリゴンのデータの座標をもとに、多面体の重心点を計算する。ステップＳ４２１の読み出し処理では、改めて頂点座標の読み出しを行う。
【００４７】
ステップＳ４２２のベクトル算出処理では、三角形の重心点を求め、前記ステップ４１３で求めた多面体の重心点から、該三角形の重心点へ向かうベクトルＡを算出する。ステップＳ４２３の法線ベクトル算出処理では、登録されている頂点の順序に基づいて法線ベクトル成分を算出し、ステップＳ４２４の内積計算処理において、該法線ベクトルと前記ベクトルＡの内積計算を行う。
【００４８】
ステップＳ４２５の判定処理では、前記算出された内積値が、負数の時には、ステップＳ４２６の並替え処理へ分岐するよう構成する。ステップＳ４２６の並替え処理では、ファイルシステム１４に登録されている三角ポリゴンの頂点データである２番目と３番目のデータを入れ換える処理を行う。ステップＳ４２７の終了判定処理では、ファイル構造体を参照し、読出しが終了したかの判定を行い、読出しが終了していなければステップＳ４２１の読出し処理へ戻り、終了していればステップＳ４２８の終了処理へ進み、終了処理を行う。
【００４９】
以上の処理のように頂点の登録順序を適宜変更することにより、多面体を構成する全ての三角ポリゴンの法線ベクトルを一致させることができる。
【００５０】
次に、本発明の第２の実施の形態を、図７に基づいて説明する。
【００５１】
本例では、第１の実施の形態の例のように、既にファイルシステム１４等に登録されているデータを読出して処理するのではなく、多面体を生成変更する処理の中で、図６に示したメモリ１５を用いてデータの読出し処理を実行する。
【００５２】
まず、ステップＳ５１１の初期化処理５１１では、適宜初期化処理を行う。ステップＳ１５２のデータ読込み処理では、ファイルシステム１４に記録されている点列データを読み込む。ステップＳ５１３の検索終了判定処理では、図２のステップＳ１３と同様な処理であり、ステップＳ５１４の検索登録処理では、図２のＳ１４からＳ１７までの処理とほぼ同様な処理である。
【００５３】
本例では、ここでファイルシステム１４への登録を行わずに、一旦メモリ１５上にデータを保持したまま、次の処理に移行する。
【００５４】
ステップＳ５１５の重心点算出処理では、メモリ１５上に記録されている三角ポリゴンのデータにアクセスし、多面体の重心点を算出する。ステップＳ５２１の座標取出し処理では、メモリ１５上のデータに再度アクセスし、頂点の座標データを取り出す。ステップＳ５２２のベクトル算出処理では、三角形の重心点を求め、前記ステップＳ５１５で求めた多面体の重心点から、該三角形の重心点へ向かうベクトルＡを算出する。ステップＳ５２３の法線ベクトル算出処理では、登録されている頂点の順序に基づいて法線ベクトル成分を算出し、ステップＳ５２４の内積計算処理において、該法線ベクトルと前記ベクトルＡの内積計算を行う。
【００５５】
ステップＳ５２５の判定処理では、前記算出された内積値が、負数の時にはステップＳ５２６の並替え処理へ分岐する。ステップＳ５２６の並替え処理では、メモリ１５上に登録されている三角ポリゴンの頂点データである二番目と三番目のデータを入れ換える。ステップＳ５２７の終了判定処理では、登録データを参照するポインタ等を参照し、処理が終了したかの判定を行い、終了していなければステップＳ５２１の取出し処理へ戻り、終了していればステップＳ５２８の終了処理へ進み、メモリ１５上のデータの書き出し、保存処理、メモリ１５の解放処理等の終了処理を適宜行う。
【００５６】
次に、本発明の第３の実施の形態を、図８に基づいて説明する。
【００５７】
本例では、図４の点列データを入力した後、図５の多面体を構成する段階で、検索できた三角ポリゴンを表示手段１３に順次表示する処理を備えた場合の例である。
【００５８】
まず、ステップＳ６１１のデータ読込み処理では、ファイルシステム１４に記録されている点列データを読み込む。ステップＳ６１２の中心点算出処理では、各データにおける各座標成分の最大値、最小値等から多面体が構成されたときの中心点（内部点）を計算する。
【００５９】
ステップＳ６１３の検索終了判定処理では、図２のＳ１３に相当する処理であって、処理が終了するまで検索終了の判定処理を繰り返す。ステップＳ６２１の検索処理では、新たに登録すべき三角ポリゴンを検索し、これを一時領域に仮登録する。ステップＳ６２２のベクトル算出処理では、前記ステップＳ６１２で求めた多面体の中心点から、三角ポリゴンを形成する３つの頂点のいずれか一つの点へ向かうベクトルＡを算出する。
【００６０】
ステップＳ６２３の法線ベクトル算出処理では、仮登録されている頂点の順序に基づいて法線ベクトル成分を算出し、ステップＳ６２４の内積計算処理において、該法線ベクトルと前記ベクトルＡの内積計算を行う。
【００６１】
ステップＳ６２５の判定処理では、前記算出された内積値が、負数の時には、ステップＳ６２６の並替え処理へ分岐する。ステップＳ６２６の並替え処理では、メモリ１５上に登録されている三角ポリゴンの頂点データである二番目と三番目のデータを入れ換える。ステップＳ６２７の描画処理では、法線ベクトルが適正化された三角ポリゴンを表示手段１３により追加表示し、全ての検索が終了するまで順次追加作業を繰り返す。
【００６２】
なお、本発明は、複数の機器から構成されるシステムに適用しても、１つの機器からなる装置に適用してもよい。また、本発明はシステム或いは装置にプログラムを供給することによって達成される場合にも適用できることはいうまでもない。この場合、本発明を達成するためのソフトウェアによって表されるプログラムを格納した記憶媒体を該システム或いは装置に読み出すことによって、そのシステム或いは装置が、本発明の効果を享受することが可能となる。
【００６３】
【発明の効果】
本発明によれば、三角ポリゴンの法線ベクトルと、多面体の内部点から前記三角ポリゴンへのベクトルとの内積が負であるか否かに応じて、前記三角ポリゴンの法線ベクトルを変更することができるので、法線ベクトルの向きによって生じる不都合を解決することができる。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態である多面体を構成するポリゴンデータの生成時におけるデータ変更処理を示すフローチャートである。
【図２】多面体を構成するポリゴンデータの生成処理を示すフローチャートである。
【図３】三角ポリゴンの登録する頂点の順序と法線ベクトルとの関係において、法線ベクトルの向きが一致する場合の例を示す説明図である。
【図４】座標空間に点在する点列を示す説明図である。
【図５】座標空間に点在する点列を取り囲む多面体の構成を示す説明図である。
【図６】３次元レンダリングシステムの構成例を示すブロック図である。
【図７】本発明の第２の実施の形態である多面体を構成するポリゴンデータの生成時におけるメモリを用いたデータ変更処理を示すフローチャートである。
【図８】本発明の第２の実施の形態である多面体を構成するポリゴンデータの生成時における描画を行うデータ変更処理を示すフローチャートである。
【図９】三角ポリゴンの登録する頂点の順序と法線ベクトルとの関係において、法線ベクトルの向きが互いに異なる１例を示す説明図である。
【符号の説明】
１０  多面体生成装置（３次元レンダリングシステム）
１１  データ生成手段
１２  データ変更手段
１３  表示手段
１４  ファイル
１５  メモリ
【図１】
0003733207.tif 000002
【図２】
0003733207.tif 000003
【図３】
0003733207.tif 000004
【図４】
0003733207.tif 000005
【図５】
0003733207.tif 000006
【図６】
0003733207.tif 000007
【図７】
0003733207.tif 000008
【図８】
0003733207.tif 000009
【図９】
0003733207.tif 000010