JPH09305791A - 立体画像生成装置および立体画像生成方法 - Google Patents

Abstract

(57)【要約】 【課題】小規模な記憶領域で陰線陰面消去処理を高速に
行うことのできる立体画像生成装置を提供する。 【解決手段】少なくとも視点位置と視線の方向とを規定
する情報を含んだレンダリングパラメータを入力するレ
ンダリングパラメータ入力手段１０１と、３次元物体を
３次元空間内の多角形の集合体として定義した立体モデ
ルを入力する立体モデル入力手段１０２と、立体モデル
を構成する多角形を３次元空間上で互いに重なることの
ない境界立方体に包含されるまとまりでグループ分けし
て複数の部品とし、視点から見た場合の各部品の重なり
具合の序列、および各部品毎の、視点から見た場合の部
品内の各面の重なり具合の序列を判定する陰線陰面消去
処理手段１０４と、立体モデルの各構成面を、その判定
された序列に従って２次元平面に投影して２次元画像と
して出力する面データ出力手段１０７とを有する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、３次元物体の２次
元投影画像を生成する立体画像生成装置および生成方法
に関し、特に立体化した文字列の２次元投影画像を生成
する立体画像生成装置および生成方法に関する。

【０００２】

【従来の技術】一般に、３次元物体の２次元投影画像を
生成する立体画像生成装置では、３次元空間上の物体を
定義するモデリング処理と、定義された３次元物体に彩
色および陰影付け（シェーディング）を行う処理と、物
体の裏側や他の物体のかげになり視点から見えない線
（陰線）または面（陰面）を２次元投影画像上に反映さ
れないようにする陰線または陰面消去処理を施して２次
元平面に投影することで２次元画像を生成するレンダリ
ング処理とが行われる。

【０００３】レンダリング処理における陰線陰面消去処
理は、３次元画像処理の問題の１つとして認識されてお
り、いくつかの実現方法が知られている。

【０００４】第１の一般的な処理方法の１つとしてＺバ
ッファ法がある。Ｚバッファ法は、フレームバッファ上
の各画素に対応させて奥行きの情報を記憶するＺバッフ
ァを設け、３次元物体の構成面を書き込む際に画素毎に
奥行きの値を計算し、Ｚバッファの奥行きの値と書き込
もうとしている画素の奥行き値とを比較する方法であ
る。Ｚバッファの値よりも書き込む画素の方が手前に位
置する場合には、フレームバッファに画素の値を書き込
み、対応するＺバッファの値も更新する。一方、Ｚバッ
ファの値よりも書き込む画素の方が奥に位置する場合
は、フレームバッファへの書き込みおよびＺバッファの
更新は行わず、画素の値を破棄する。これにより、３次
元物体の全ての表面の書き込みを終えた時点で、フレー
ムバッファには最も手前に位置する画素の値が記憶され
ることになる。

【０００５】第２の方法としてスキャンライン法が知ら
れている。このスキャンライン法では、３次元物体を投
影面と直交する水平面での断面で考える。水平面上では
物体を構成する多角形は線分として示される。さらに、
この水平面上で物体の投影面への投影像を考えると、物
体を構成する多角形は直線上の区間として示される。区
間同士が重なっている場合には、重なり部分を分割して
独立した区間と考える。区間内で対応する元々の３次元
上の多角形の奥行きの順を検査して、一番投影面に近い
多角形を投影像に書き込む。水平面をスクリーンの上か
ら下まで画素の１行分ずつずらして同様の処理を繰り返
すことで、２次元投影像を完成させる。

【０００６】第３の方法として、特開閉5-210745号公報
に開示されている方法がある。位相ソートを効率よく遂
行するために、物体を構成する各多角形に対して着目し
た多角形以外の多角形を、着目した多角形を隠すか否か
で分類し、これをリストにして記憶しておく方法であ
る。この方法では、位相ソートを行う場合には、リスト
を参照することで重なりを生じていない多角形同士の判
定を省くようにしている。

【０００７】

【発明が解決しようとする課題】第１の方法であるＺバ
ッファ法においては、奥行き判定を画素単位で行うため
に単純なアルゴリズムで実現できるものの、フレームバ
ッファの他に奥行き値を記憶するＺバッファが必要とな
る。Ｚバッファとしての記憶領域は、出力する２次元画
像の画素数に比例した大きさが必要であり、精細な画像
を出力する場合には多大な記憶領域を必要とするという
問題があった。また、画素単位の奥行き判定処理が必要
なことと、隠れ面部分の画素に対しても一通りの処理を
必要とするため処理時間も膨大となるという問題点があ
った。

【０００８】第２の方法であるスキャンライン法におい
ては、線分単位で奥行き判定を行うことと、線分単位で
ソートした結果に基づいて、最前部に位置するスキャン
ライン上の区間についてしか書き込み処理を行わないた
めにＺバッファ法と比べると高速であるものの、この方
法も出力画像のライン数に比例して処理回数が増大する
ことと、スキャンライン上の区間に対応した多角形の並
び替えを行うために記憶領域を必要とするという問題点
があった。また、並び替えのための区間を分割する必要
があるなど処理が複雑であり、処理装置の規模が増大す
るという問題点があった。

【０００９】第３の方法である特開閉5-210745号公報に
開示されている方法においては、面単位で着目して位相
ソートを行うために処理回数は出力画像の大きさには依
存しないが、物体を構成する各多角形に対して他の全て
の多角形との位置関係を検査するために処理時間が長く
なることと、位置関係を検査した結果をそれぞれの面に
対応したリストで記憶するために大きな記憶領域を必要
とするという問題点があった。

【００１０】本発明の目的は、かかる問題点を解決し、
小規模な記憶領域で陰線陰面消去処理を高速に行うこと
のできる立体画像生成装置および立体画像生成方法を提
供することにある。

【００１１】

【課題を解決するための手段】上記目的を達成するた
め、本発明の立体画像生成装置は、３次元物体の２次元
投影画像を生成する立体画像生成装置において、少なく
とも視点位置と視線の方向とを規定する情報を含んだレ
ンダリングパラメータを入力するレンダリングパラメー
タ入力手段と、前記３次元物体を３次元空間内の多角形
の集合体として定義した立体モデルを入力する立体モデ
ル入力手段と、前記立体モデルを構成する多角形を前記
３次元空間上で互いに重なることのない境界立方体に包
含されるまとまりでグループ分けして複数の部品とし、
視点から見た場合の各部品の重なり具合の序列、および
各部品毎の、視点から見た場合の部品内の各面の重なり
具合の序列を判定する陰線陰面消去処理手段と、前記立
体モデルの各構成面を、前記陰線陰面消去処理手段にて
判定された序列に従って２次元平面に投影して２次元画
像として出力する出力手段と、を有することを特徴とす
る。

【００１２】上記の場合、前記陰線陰面消去処理手段
を、前記複数の部品に関し、視点から見た場合の各部品
の陰線陰面が消去されるような部品の重ね書きを行うこ
とができる描画順位を決定する部品描画順位決定手段
と、前記複数の部品毎に、視点から見た場合の部品内の
各面の陰線陰面が消去されるような面の重ね書きを行う
ことができる描画順位を決定する面描画順位決定手段
と、により構成し、前記出力手段が、前記部品描画順位
決定手段および面描画順位決定手段にて決定された部品
および面の描画順位に従って、前記立体モデルの各構成
面を２次元平面に投影するようにしてもよい。

【００１３】さらに、前記境界立方体は、前記３次元物
体を空間的な位置関係により複数にグループ分けしたも
のであって、グループ中の全ての多角形を包含し、か
つ、Ｘ−Ｙ平面、Ｙ−Ｚ平面、Ｚ−Ｘ平面に平行な面で
構成されるものであってもよい。

【００１４】本発明の立体画像生成方法は、３次元物体
を３次元空間内の多角形の集合体として定義した立体モ
デルを基に、前記３次元物体の２次元投影画像を生成す
る立体画像生成方法において、前記立体モデルを構成す
る多角形を、前記３次元空間上で互いに重なることのな
い境界立方体に包含されるまとまりでグループ分けして
複数の部品とし、視点から見た場合の各部品の重なり具
合の序列、および各部品毎の、視点から見た場合の部品
内の各面の重なり具合の序列を判定し、該判定された序
列に従って前記立体モデルの各構成面を２次元平面に投
影することにより前記２次元投影画像を得ることを特徴
とする。

【００１５】上記の場合、前記複数の部品について、視
点から見た場合の各部品の陰線陰面が消去されるような
部品の重ね書きを行うことができる部品描画順位を求め
てこれを前記部品の序列とし、さらに各部品毎に、視点
から見た場合の部品内の各面の陰線陰面が消去されるよ
うな面の重ね書きを行うことができる面描画順位を求め
てこれを前記部品の各面の序列とし、これら部品描画順
位および面描画順位に従って前記立体モデルの各構成面
を重ね書きすることにより前記２次元投影画像を得るよ
うにしてもよい。

【００１６】さらに、前記境界立方体は、前記３次元物
体を空間的な位置関係によりグループ分けしたものであ
って、グループ中の全ての多角形を包含し、かつ、Ｘ−
Ｙ平面、Ｙ−Ｚ平面、Ｚ−Ｘ平面に平行な面で構成され
ており、前記部品の重なり具合の序列を、任意の２つの
境界立方体に関して視点から見た場合の重なり具合の序
列をそれぞれの立方体を構成する面の重なり具合を検査
することにより行うようにしてもよい。

【００１７】上記の通りの本発明によれば、立体モデル
を複数の部品に分割し、これら部品の重なり具合の序列
と、各部品毎の、部品内の各面の重なり具合の序列とを
判定することによって、立体モデルの各構成面の序列が
判定される。このように、本発明では、面の重なり具合
の序列の判定が部品毎に行われるので、立体モデルの各
構成面１つ１つに対して重なり具合の序列を全て判定し
ていた従来の場合と比べ、序列の判定の回数は大幅に少
なくなり、高速な陰線陰面消去処理が可能になる。

【００１８】

【発明の実施の形態】次に、本発明の実施例について図
面を参照して説明する。

【００１９】図１は、本発明の一実施例の立体画像生成
装置の概略構成を示すブロック図である。

【００２０】本実施例の立体画像生成装置は、レンダリ
ングパラメータ入力手段１０１、立体モデル入力手段１
０２、立体モデル記憶手段１０３、陰線陰面消去処理手
段１０４、面データ出力手段１０７より構成されてい
る。

【００２１】レンダリングパラメータ入力手段１０１
は、少なくとも視点位置と視線の方向とを規定する情報
を含んだレンダリングパラメータ（ここでは、視点位置
座標および投影面位置）を入力する。

【００２２】立体モデル入力手段１０２は、物体を３次
元空間内の多角形の集合体として定義した立体モデルに
関する情報（ここでは、３次元物体の形状および配置）
を入力する。

【００２３】立体モデル記憶手段１０３は、上記レンダ
リングパラメータ入力手段１０１および立体モデル入力
手段１０２からの入力情報を記憶する。この立体モデル
記憶手段１０３では、詳しくは後述するが、物体を３次
元空間内の多角形の集合体として定義した立体モデル
を、３次元空間上で互いに重なることのない境界立方体
に包含されるまとまりでグループ分けし（以下、グルー
プ分けされた面群を部品と呼ぶ）、部品単位で情報の記
憶が行われる。

【００２４】陰線陰面消去処理手段１０４は、視点から
見た場合の各部品の重なり具合の序列、および各部品毎
の、視点から見た場合の部品内の各面の重なり具合の序
列を判定することにより、立体モデルを表示する際の陰
線陰面消去を行う手段である。その構成は、部品描画順
位決定手段１０５および面描画順位決定手段１０６を備
えている。部品描画順位決定手段１０５は、視点から見
た際の各部品の陰線および陰面が消去されるような、部
品の重ね書きを行うことができる描画順位を決定する。
面描画順位決定手段１０６は、各部品毎に、視点から見
た際の部品内の各面の陰線および陰面が消去されるよう
な、面の重ね書きを行うことができる描画順位を決定す
る。本実施例では、この決定された部品描画順位および
面描画順位に従って描画が行われる。

【００２５】次に、立体モデル記憶手段１０３について
詳しく説明する。立体モデル記憶手段１０３は、図２に
示すように、少なくとも立体モデルデータ記憶部２０１
と、部品データ記憶部２０２と、面データ記憶部２０３
と、３次元頂点データ記憶部２０４と、２次元データ記
憶部２０５と、レンダリングパラメータ記憶部２０６
と、を備えている。

【００２６】立体モデルデータ記憶部２０１は、３次元
頂点データ記憶部２０４に記憶される各頂点要素に関す
る３次元頂点データの先頭アドレスと、２次元頂点デー
タ記憶部２０５に記憶される各頂点要素に関する３次元
頂点データの先頭アドレスと、立体モデルに含まれる部
品の数を記憶する領域と、部品データ記憶部２０２上の
各部品データへのアドレスを部品数分だけ格納する領域
と、を備えている。

【００２７】部品データ記憶部２０２は、個々の部品に
含まれる面データの数を記憶する領域と面データ記憶部
２０３上にある部品に含まれる面のデータのアドレスを
立体モデルに含まれる面の数量分格納する領域とを備え
ている。

【００２８】面データ記憶部２０３は、それぞれの面の
頂点の数と面の頂点に対応した、３次元頂点データ記憶
部２０４および２次元頂点データ記憶部２０５上の座標
値データのアドレスを記憶する領域と、視点から面を見
た場合に面が裏返しになっている場合にその状態を表す
可視フラグを記憶する領域と、を備えている。

【００２９】３次元頂点データ記憶部２０４は、立体モ
デルに含まれる全ての頂点の３次元座標値を記憶する領
域を備え、２次元頂点データ記憶部２０５は、立体モデ
ルに含まれる全ての頂点に対応した投影変換後の２次元
座標値を記憶する領域を備えている。これら３次元頂点
データおよび２次元頂点データの並びは対応しており、
それぞれは配列となっているので、立体モデルデータ記
憶部２０１に記憶されている３次元頂点データおよび２
次元頂点データの各先頭アドレスを基準として、同一配
列要素番号で対応する頂点座標データにアクセスするこ
とが可能になっている。

【００３０】レンダリングパラメータ記憶部２０６は、
入力された視点位置および投影面位置を記憶する。ここ
では、視点のＸ，Ｙ，Ｚ座標値が記憶される。

【００３１】次に、この立体画像生成装置の動作を図３
〜図７を参照して説明する。

【００３２】図３は立体画像生成装置の全体の処理手順
を示すフローチャートである。

【００３３】まず、ステップＳ１０１で、レンダリング
パラメータ入力手段１０１から入力された視点位置座標
および投影面位置、立体モデル入力手段１０２から入力
された立体モデルデータが、立体モデル記憶手段１０３
上に記憶される（ステップ１０１）。この際、面データ
記憶部２０３の全ての可視フラグはＯＮ状態に初期化さ
れる。

【００３４】ここで、立体モデルデータは、例えば図１
０に示すような立体化した文字列を、３次元空間上の複
数の面の集合として定義するものである。このような立
体の文字列は、図８に示すように線分の輪郭線で構成さ
れた２次元の文字列を、奥行き方向に適当な距離をおい
た２つの文字列とし、これら文字列間でそれぞれの線分
の端点同士を結ぶ線分を含んだ、線分で囲まれる多角形
を考えればよい。なお、この際、各文字に相当する線分
の集まりは２次元上で重なる部分を持たない矩形に包含
されており、立体化の操作をした後の各文字を構成する
面群もまた、図９に示すような、３次元空間上では互い
に重なる部分を持たない境界立方体にそれぞれ包含され
る。

【００３５】立体モデル記憶手段１０３上では、図２
（ａ）〜（ｂ）に示すように部品データ、面データ、３
次元頂点データ、レンダリングパラメータで構成された
立体モデルパラメータとして記憶される。

【００３６】ここで、立体モデルの記憶様式に関し、図
１０の例を参照して詳細に説明する。線分の継ぎ目に相
当する頂点の位置座標が順に３次元頂点データ記憶部２
０４上の配列で格納される。図１０に示す立体化した文
字列では、文字の形をした正面と矩形の側面は、それぞ
れ面データであり、３次元頂点データ間をつないででき
る多角形として定義されることから、面データ記憶部２
０３には、各面要素毎に面に含まれる頂点の数と、それ
ら頂点を辿る順番に並んだ３次元頂点データへのアドレ
スが格納されている。ここでは、頂点を辿る順番は、面
を通り、かつ、面に垂直な線上で立体を外部から見た場
合に反時計回りとなるような順番とする。

【００３７】部品データ記憶部２０２には、部品データ
として、面データを参照するためのアドレスなどが記憶
される。ここで、部品は、図１０の個々の文字に相当
し、図９に示す立方体のように互いに重なる部分の無い
立方体で括られる面データのまとまりである。部品デー
タは、それぞれの部品に含まれる面の数と各面データへ
のアドレスを含むデータである。

【００３８】立体モデルデータ記憶部２０１には、部品
の数とそれぞれの部品のデータのアドレスと３次元頂点
データおよび２次元頂点データの先頭アドレスが記憶さ
れている。この立体モデルデータを起点に全ての立体構
成要素を参照できる。

【００３９】上記ステップＳ１０１にて立体モデルデー
タの入力が行われると、次いで、ステップＳ１０２で、
部品を包含し、互いに重なりの無い境界立方体を立体モ
デルとして生成する。立方体の各面は、各部品を構成す
るＸ−Ｙ平面、Ｙ−Ｚ平面、Ｚ−Ｘ平面にそれぞれ投影
した投影像を包含する最小外接矩形として求める。

【００４０】続いて、ステップＳ１０３で、上記ステッ
プＳ１０２で生成した境界立方体に関して並べ替えを行
う。図４は、このステップＳ１０３の詳細な処理手順を
示すフローチャートである。同図では、部品を記号Ｂで
表し、添字は部品配列での要素番号を表す。

【００４１】まず、ステップＳ２０１で、部品データポ
インタａが０に初期化される。次いで、ステップＳ２０
２で、部品データポインタｂが、ａ＋１に設定される。
次いで、ステップＳ２０３で、部品Ｂ「ａ」と部品Ｂ
「ｂ」とで視点からみた場合の重なりの状況を判定す
る。図５は、このステップＳ２０３の詳細な処理手順を
示すフローチャートである。同図では、面データを記号
Ｆで表し、第１番目の添字は面データが属している部品
の番号を示し、第２の添字は面データポインタであり、
部品内での面の番号を示す。例えば、境界立方体は、６
面であるので第２の添字は、０から５の値となる。

【００４２】図５に示すように、まず、ステップＳ３０
１で、面データポインタをｉを０に初期化する。次い
で、ステップＳ３０２で、面データポインタｊを０に初
期化する。次いで、ステップＳ３０３で、面Ｆ［ａ，
ｊ］が面Ｆ［ｂ，ｊ］を隠すかどうかを判断する。この
ステップＳ３０３の結果が偽（ＦＡＬＳＥ）であればス
テップＳ３０７へ進み、真（ＴＲＵＥ）であればステッ
プＳ３０４へ進む。図７は、このステップＳ３０３の詳
細な処理手順を示すフローチャートである。同図では、
面を記号Ｆで表しているが、第１の添字は省略してあ
る。

【００４３】図７に示すように、まずステップＳ５０１
で、面Ｆ［ｉ］と面Ｆ［ｊ］が２次元投影面に投影した
際に重なるかどうかを判断する。重ならない場合は、ス
テップＳ５０７へ進み、戻り値にＦＡＬＳＥを設定して
図５のステップＳ３０３の続きへ戻る。重なる場合は、
ステップＳ５０２へと進む。

【００４４】ステップＳ５０２では、面Ｆ［ｊ］の全て
の頂点が面Ｆ［ｉ］の前方にあるかどうかを検査する。
検査結果がＴＲＵＥである場合には、ステップＳ５０７
へ進み、戻り値にＦＡＬＳＥを設定して図５のステップ
Ｓ３０３の続きへ戻る。ＦＡＬＳＥである場合には、ス
テップ５０３へ進む。

【００４５】ステップＳ５０３では、面Ｆ［ｉ］の全て
の頂点が面Ｆ［ｊ］の後方にあるかどうか検査する。検
査結果がＴＲＵＥである場合には、ステップＳ５０７へ
進み、戻り値にＦＡＬＳＥを設定して図５のステップＳ
３０３の続きへ戻る。ＦＡＬＳＥである場合には、ステ
ップＳ５０４へ進む。

【００４６】ステップＳ５０４では、面Ｆ［ｉ］の全て
の頂点が面Ｆ［ｊ］の前方にあるかどうかを検査する。
検査結果がＴＲＵＥである場合には、ステップＳ５０６
へ進み、戻り値にＴＲＵＥを設定して図５のステップＳ
３０３の続きへと戻る。ＦＡＬＳＥである場合には、ス
テップＳ５０５へ進む。

【００４７】ステップＳ５０５では、面Ｆ［ｊ］の全て
の頂点が面Ｆ［ｉ］の後方にあるかどうかを検査する。
検査結果がＴＲＵＥである場合には、ステップＳ５０６
へ進み、戻り値にＴＲＵＥを設定して図５のステップＳ
３０３の続きへと戻る。ＦＡＬＳＥである場合には、ス
テップＳ５０７へ進み、戻り値にＦＡＬＳＥを設定して
図５のステップＳ３０３の続きへ戻る。

【００４８】以下、再び図５の続きを説明する。

【００４９】ステップＳ３０７へ進んだ場合は、戻り値
にＦＡＬＳＥを設定して図４のステップＳ２０３の続き
へ戻る。ステップＳ３０４へ進んだ場合は、面Ｆ［ｂ，
ｊ］が面Ｆ［ａ，ｊ］を隠すかどうかを検査する。この
ステップＳ３０４の処理では、ステップ３０３の面を入
れ替えて図７のステップＳ５０１〜Ｓ５０７の処理を同
様に行う。

【００５０】上記ステップＳ３０４の検査結果がＴＲＵ
Ｅとなった場合は、ステップＳ３０６へ進み、戻り値に
ＴＲＵＥを設定して図４のステップＳ２０３の続きへ戻
る。検査結果がＦＡＬＳＥとなった場合は、ステップＳ
３０５へ進み、面データポインタｊを１増加する。そし
て、ステップＳ３０８で、面データポインタｊと部品デ
ータ［ｂ］の面数との比較をする。面データポインタｊ
が部品データ［ｂ］の面数より小さい場合は、ステップ
３０２へ戻り、面データポインタｊが部品データ［ｂ］
の面数以上となった場合は、ステップＳ３０９へ進み、
面データポインタｉを１増加する。

【００５１】ステップＳ３０９にて面データポインタｉ
が１増加されると、次いで、ステップＳ３１０で、面デ
ータポインタｉと部品データＢ［ａ］の面数との比較を
する。面データポインタｉが部品データＢ［ａ］の面数
より小さい場合は、ステップＳ３０１へ戻り、面データ
ポインタｉが部品データＢ［ａ］の面数以上となった場
合には、戻り値にＦＡＬＳＥを設定して図４のステップ
Ｓ２０３の続きへ戻る。

【００５２】以下、再び図４の続きを説明する。

【００５３】ステップＳ２０３の結果が、ＴＲＵＥであ
った場合は、ステップＳ２０５へ進む。ステップＳ２０
５では、部品Ｂ［ｂ］を部品Ｂ［ａ］の直前に移動し、
ステップＳ２０１へ戻り、以上に説明した処理を繰り返
す。この際の部品の移動は、立体モデル記憶手段１０３
上にある元々の立体モデルデータの立体モデルデータ記
憶部２０１の部品データへのアドレスの配列に対しても
同時に行う。また、部品データポインタａ，ｂはともに
更新されていないが、データの入れ替えがなされてい
る。

【００５４】ステップＳ２０３の結果が、ＦＡＬＳＥで
あった場合には、ステップＳ２０４へ進み、部品データ
ポインタｂを１増加する。続くステップＳ２０６で、部
品データポインタｂが部品数以上であるかどうかを判定
する。判定結果がＦＡＬＳＥである場合は、ステップＳ
２０２へ戻り、以上で説明した処理を繰り返す。判定結
果がＴＲＵＥである場合には、ステップＳ２０７へ進
み、部品データポインタａを１増加する。

【００５５】続くステップＳ２０８では、部品データポ
インタａが部品数以上であるかどうかを判定する。判定
結果がＦＡＬＳＥである場合は、ステップＳ２０１へ戻
り、以上で説明した処理を繰り返す。判定結果がＴＲＵ
Ｅである場合には、部品ソートの処理を終了する。

【００５６】上述の図４における部品ソートの処理（図
３のステップＳ１０３の処理）の流れを簡単に説明する
と、次のようなことになる。まず、元々の部品の並びの
先頭から順次部品に着目していき、着目した部品とその
他の部品の前後関係を検査して、着目した部品よりも後
方に位置する部品がなかった場合には、着目する部品を
次の部品に移す。一方、着目した部品よりも後方に位置
する部品があった場合には、その部品を着目していた部
品の前に移動して新たな着目部品として処理を行う。こ
うして、一通りの部品の処理が終了した時点では、立体
モデルデータ記憶部２０１上の部品データのアドレスの
配列は、重なりの序列で部品が並べ替えられる。

【００５７】以下、再び図３の続きを説明する。

【００５８】ステップＳ１０３で、上述した部品ソート
の処理が行われると、次いでステップＳ１０４で、不可
視面除去を行う。視点から見て裏返しになっている面は
物体の陰になっているので、最終的な２次元投影画像で
は描画されない。このため、後段の処理の無駄を省くた
めにこの時点で裏返しになっているかどうかを検査し、
可視フラグの値を更新しておく（ここでは、裏返しにな
っている場合は可視フラグがオフにされる）。以降の処
理では、可視フラグがオンになっている面は処理の対象
から外される。

【００５９】続くステップＳ１０５で、面ソートを行
う。立体モデルデータ記憶部２０１に格納されている部
品データのアドレスの順番に従って、順次部品データが
ステップＳ１０５で処理される。図６は、このステップ
Ｓ１０５の詳細な処理手順を示すフローチャートであ
る。同図では、面を記号Ｆで表し、添字は部品データ記
憶部２０２上の面データの配列の要素番号を表す。

【００６０】まず、ステップＳ４０１で面データポイン
タｉが０に初期化される。次いで、ステップＳ４０２
で、面データポインタｊがｉ＋１に設定される。次い
で、ステップＳ４０３で、視点から見た場合に面Ｆ
［ｉ］が面Ｆ［ｊ］を隠すかどうかを検査する。このス
テップＳ４０３の処理は、上述の部品ソート処理で説明
した図７の処理と同様であるので、ここでは詳しい説明
は省略する。

【００６１】上記ステップＳ４０３の戻り値がＴＲＵＥ
であった場合は、ステップＳ４０５へ進む。ステップＳ
４０５では、面Ｆ［ｊ］を面Ｆ［ｉ］の直前に移動した
後、ステップＳ４０１の処理へ戻る。ステップＳ４０３
の戻り値がＦＡＬＳＥであった場合は、ステップＳ４０
４へ進み、ｊを１増加させる。続くステップＳ４０６
で、面データポインタｊと面の数を比較し、面データポ
インタｊの方が小さい場合には、ステップＳ４０２へ戻
り、以上で説明した処理を繰り返し、面データポインタ
ｊの方が大きい場合には、ステップＳ４０７へ進み、ｉ
を１増加させる。

【００６２】続くステップＳ４０８で、面データポイン
タｉと面の数を比較し、面データポインタｉの方が小さ
い場合には、ステップＳ４０１へ戻り、以上で説明した
処理を繰り返し、面データポインタｉの方が大きい場合
には、次の部品データに対して同様の処理を繰り返し、
全ての部品データの処理を終了するまで繰り返す。

【００６３】以上説明したステップＳ１０１〜ステップ
Ｓ１０５の処理で、陰線陰面消去処理手段１０４による
立体モデルデータおよび部品データの内容の並べ替えが
行われる。

【００６４】以下、再び図３の続きを説明する。

【００６５】続くステップＳ１０６では、全ての面に対
して、予め定められた光源位置などのパラメータに従っ
て、グローシェーディンッグ等の方法により面の色が決
められる。このステップＳ１０６でシェーディングが施
された立体モデルデータの頂点データは、レンダリング
パラメータ記憶部２０６の視点座標と投影面の位置を基
に２次元平面上の座標に変換された２次元頂点データ記
憶部２０５へ順次格納される。

【００６６】続くステップＳ１０８で、立体モデルデー
タ記憶部２０１の部品データアドレスの並びに従って、
部品データ記憶部２０２の面データポインタが参照さ
れ、面データポインタは、立体モデルデータ記憶部２０
１の２次元頂点データアドレスを参照して順次頂点座標
を参照して、多角形の出力を行う。この結果、図１１に
示すような２次元投影画像が得られる。

【００６７】全ての部品データおよび面データの出力が
終了した時点で、立体画像の生成処理が終了する。

【００６８】以上説明した本実施例の立体画像生成装置
は、立体化した文字列の２次元投影画像を生成するもの
であったが、本発明はこれに限定されるものではなく、
文字列に代えて種々の３次元物体を適用することが可能
である。

【００６９】

【発明の効果】本発明は以上説明したように構成されて
いるので、以下に記載するような効果を奏する。

【００７０】従来は、任意の２つの面（立体モデルを構
成する面）に関して視点から見た場合の重なり具合の序
列を判定するといった処理を全ての面について行ってい
る。立体モデルに含まれる面の数をＣとした場合、任意
の２面の組み合せの数Ｃは、 Ｃ＝Ｎ×（Ｎ−１）／２ であり、この回数分の重なり具合の判定が必要とされ
る。すなわち、重なり具合の判定の回数が面の数の二乗
に比例して増加することとなり、例えば図１０に示すよ
うな複雑な形状をした文字列を処理する場合には、多大
な処理時間が必要であった。これに対して、本発明で
は、立体モデルを部品データに分割し、まず部品のまと
まり単位で部品の重なり具合の序列を判定した後に、部
品毎に面の序列を判定して、立体モデルの各構成面の序
列を求めている。この場合の序列の判定処理は、立体モ
デルをＭ個の部品に分割した場合、平均して１／Ｍ²の
処理時間で処理できることになる。

【００７１】以上のことから、本発明によれば、立体モ
デルの各構成面の序列の判定回数を大幅に少なくするこ
とができるので、高速な陰線陰面消去処理が可能になる
という効果がある。さらには、序列の判定回数が少ない
ことから、ワークメモリを大幅に削減でき、リソースの
乏しい小規模なシステム上でも適用できるという効果が
ある。

【図面の簡単な説明】

【図１】本発明の一実施例の立体画像生成装置の概略構
成を示すブロック図である。

【図２】図１に示す立体モデル記憶手段の構成を説明す
るための図で、（ａ）〜（ｆ）は各記憶部の構成を示す
図である。

【図３】図１に示す立体画像生成装置の全体の処理手順
を示すフローチャートである。

【図４】図３の部品ソートの処理を詳細に説明するフロ
ーチャートである。

【図５】図４の処理の一部を詳細に説明するフローチャ
ートである。

【図６】図３の面ソートの処理を詳細に説明するフロー
チャートである。

【図７】図５の処理の一部を詳細に説明するフローチャ
ートである。

【図８】線分の輪郭線で構成された２次元の文字列の一
例を示す図である。

【図９】境界立方体を説明するための図である。

【図１０】立体モデルを説明するための図である。

【図１１】２次元投影画像の一例を示す図である。

【符号の説明】 １０１ レンダリングパラメータ入力手段 １０２ 立体モデル入力手段 １０３ 立体モデル記憶手段 １０４ 陰線陰面消去処理手段 １０５ 部品描画順位決定手段 １０６ 面描画順位決定手段 １０７ 面データ出力手段 ２０１ 立体モデルデータ記憶部 ２０２ 部品データ記憶部 ２０３ 面データ記憶部 ２０４ ３次元頂点データ記憶部 ２０５ ２次元頂点データ記憶部 ２０６ レンダリングパラメータ記憶部

Claims (6)

【特許請求の範囲】
1. 【請求項１】 ３次元物体の２次元投影画像を生成する
   立体画像生成装置において、 少なくとも視点位置と視線の方向とを規定する情報を含
   んだレンダリングパラメータを入力するレンダリングパ
   ラメータ入力手段と、 前記３次元物体を３次元空間内の多角形の集合体として
   定義した立体モデルを入力する立体モデル入力手段と、 前記立体モデルを構成する多角形を前記３次元空間上で
   互いに重なることのない境界立方体に包含されるまとま
   りでグループ分けして複数の部品とし、視点から見た場
   合の各部品の重なり具合の序列、および各部品毎の、視
   点から見た場合の部品内の各面の重なり具合の序列を判
   定する陰線陰面消去処理手段と、 前記立体モデルの各構成面を、前記陰線陰面消去処理手
   段にて判定された序列に従って２次元平面に投影して２
   次元画像として出力する出力手段と、を有することを特
   徴とする立体画像生成装置。
2. 【請求項２】 請求項１に記載の立体画像生成装置にお
   いて、 前記陰線陰面消去処理手段は、 前記複数の部品に関し、視点から見た場合の各部品の陰
   線陰面が消去されるような部品の重ね書きを行うことが
   できる描画順位を決定する部品描画順位決定手段と、 前記複数の部品毎に、視点から見た場合の部品内の各面
   の陰線陰面が消去されるような面の重ね書きを行うこと
   ができる描画順位を決定する面描画順位決定手段と、を
   有し、 前記出力手段が、前記部品描画順位決定手段および面描
   画順位決定手段にて決定された部品および面の描画順位
   に従って、前記立体モデルの各構成面を２次元平面に投
   影することを特徴とする立体画像生成装置。
3. 【請求項３】 請求項１に記載の立体画像生成装置にお
   いて、 前記境界立方体は、前記３次元物体を空間的な位置関係
   により複数にグループ分けしたものであって、グループ
   中の全ての多角形を包含し、かつ、Ｘ−Ｙ平面、Ｙ−Ｚ
   平面、Ｚ−Ｘ平面に平行な面で構成されることを特徴と
   する立体画像生成装置。
4. 【請求項４】 ３次元物体を３次元空間内の多角形の集
   合体として定義した立体モデルを基に、前記３次元物体
   の２次元投影画像を生成する立体画像生成方法におい
   て、 前記立体モデルを構成する多角形を、前記３次元空間上
   で互いに重なることのない境界立方体に包含されるまと
   まりでグループ分けして複数の部品とし、視点から見た
   場合の各部品の重なり具合の序列、および各部品毎の、
   視点から見た場合の部品内の各面の重なり具合の序列を
   判定し、該判定された序列に従って前記立体モデルの各
   構成面を２次元平面に投影することにより前記２次元投
   影画像を得ることを特徴とする立体画像生成方法。
5. 【請求項５】 請求項４に記載の立体画像生成方法にお
   いて、 前記複数の部品について、視点から見た場合の各部品の
   陰線陰面が消去されるような部品の重ね書きを行うこと
   ができる部品描画順位を求めてこれを前記部品の序列と
   し、さらに各部品毎に、視点から見た場合の部品内の各
   面の陰線陰面が消去されるような面の重ね書きを行うこ
   とができる面描画順位を求めてこれを前記部品の各面の
   序列とし、これら部品描画順位および面描画順位に従っ
   て前記立体モデルの各構成面を重ね書きすることにより
   前記２次元投影画像を得ることを特徴とする立体画像生
   成方法。
6. 【請求項６】 請求項４に記載の立体画像生成方法にお
   いて、 前記境界立方体は、前記３次元物体を空間的な位置関係
   によりグループ分けしたものであって、グループ中の全
   ての多角形を包含し、かつ、Ｘ−Ｙ平面、Ｙ−Ｚ平面、
   Ｚ−Ｘ平面に平行な面で構成されており、 前記部品の重なり具合の序列は、任意の２つの境界立方
   体に関して視点から見た場合の重なり具合の序列を、そ
   れぞれの立方体を構成する面の重なり具合を検査するこ
   とにより行われることを特徴とする立体画像生成方法。