JPH0223479A - 画像表示方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、空間中の複数の多面体を２次元画像として表
示するための画像表示方法に関する。

（従来の技術） コンピュータ・グラフィックス等で行われるように、複
数の多面体をスキャンライン毎に隠れ面消去して陰影づ
けられた２次元画像として画面上に表示する場合、まず
各多面体を構成する各多角形の頂点を画面における座標
系に変換する。そして、各頂点の画面上における列番地
Ｘと行番地ｙおよび奥行きの値２と輝度ｉとを求める。

通常、その座標変換は視点に基づく透視変換である。次
に、スキャンライン毎に多角形を構成する稜線との交わ
りを求め、セグメントを作成する。そして、スキャンラ
インアルゴリズムと呼ばれる方法により各セグメント間
で前後判定をして、各セグメントの画面に表示する区間
の輝度を求める。このスキャンラインアルゴリズムの詳
細は文献１：［コンピュータデイスプレィによる図形処
理工学」、山口富士夫著、日刊工業新聞社、第５章隠れ
面消去問題、に記載されている。

（発明が解決しようとする問題点） 従来の画像表示におけるスキャンライン単位の隠れ面消
去では、全てのセグメントの間で重なりを調べ、重なり
があるセグメント同士で前後判定を行う。したがって、
重なりを判定する回数はセグメントの数の２乗のオーダ
ーで増加してしまい、複雑な図形になるとセグメント同
士の前後判定の回数が膨大となり、処理時間が増大する
という問題点がある。

こうした問題点を解決するためにセグメントをソーティ
ングする方法が知られている。この詳細は、例えば文献
１に記載されている。セグメントをソーティングするこ
とによりセグメントの重なりを判定する回数を減少でき
る。さらにスキャンライン間の類似性を利用することが
でき、セグメント同士の前後判定の回数を減らすことが
できる。

したがって処理時間を減少することができる。しかしな
がら、このソーティングを用いた方法を用いると処理自
体が非常に複雑となってしまい、実現する場合ハード規
模が膨大になるという問題がある。

本発明は、接続しているいくつかのセグメントをまとめ
てマクロセグメントとすることにより、セグメント間の
前後判定の回数を単純な処理により減少させることので
きる画像表示方法を提供することを目的とする。

（問題点を解決するための手段） 本発明の画像表示方法は、３次元空間中の複数の多面体
を画面上に表示するために、上記の多面体を構成する各
多角形を上記画面上に射影した時の上記画面上の各スキ
ャンラインにおける両端点に対応する上記多角形上の点
を結んだ線として定義されるセグメントを示す情報とし
て上記セグメントの両端点の座標値と輝度とを求め、上
記の各スキャンライン内で同一の多面体に含まれかつ接
続しているセグメントから構成されるマクロセグメント
を示す情報として上記マクロセグメントを構成するセグ
メントの接続情報を求め、上記マクロセグメントに含ま
れる複数のセグメントの両端点の座標値に基づき同一の
スキャンライン内に含まれるマクロセグメント同士の前
後判定を行い、この判定結果と上記セグメントの両端点
の輝度とに基づき画面上の各画素の輝度を求めることを
特徴とする。

（作用） 本発明の、多面体を表示するための画像表示方法につい
て説明する。スキャンライン毎の隠れ面消去による画像
表示において、まず多面体を構成する複数の多角形の形
状情報と接続情報により多面体を表現する。次に多角形
の形状情報からセグメント情報を求める。セグメントと
は、各多角形を画面上に射影した時の各スキャンライン
における両端点に対応する多角形上の点を結んだ線分で
ある。セグメント情報とはセグメントの両端点の座標値
とその両端点に対応する画面上の輝度とである。

次に、多角形の接続情報に基づいてマクロセグメント情
報を求める。マクロセグメントは、各スキャンライン内
で同一の多面体に含まれかつ接続しているセグメントか
ら構成される折れ線によって定義される。マクロセグメ
ント情報はマクロセグメントを構成するセグメントの接
続情報である。

次に、同一スキャンライン内に含まれる全てのマクロセ
グメント間で前後判定をする。前後判定とは、画面に対
して各マクロセグメントの前後を判定する処理で、これ
によりマクロセグメントのうちで画面に表示するための
見える範囲を求めることができる。処理にあたり、まず
重なりのあるマクロセグメントを選び出す。そして、各
マクロセグメントを構成するセグメントの内で重なりの
ある一組のセグメントを選び出す。そして選び出された
セグメント間で、各セグメントの両端点の座標値に基づ
いて前後判定を行うことにより、マクロセグメント間の
前後関係を求め、見える範囲を求める。

そして、この判定結果とセグメントの両端点の輝度とに
基づいて、画面上の各画素の輝度を求める。このような
方法により、セグメント間の前後判定の回数を減らすこ
とができる。

（実施例） 以下、図面により本発明の一実施例を説明する。

第１図は本発明の処理の流れを示す流れ図である。入力
は多面体を構成する各多角形の形状情報と接続情報とす
る。多角形の形状情報とは多角形を構成する頂点の座標
値と輝度と各頂点の並びとである。ただしこれらの座標
値は、視点に基づく透視変換により画面に基づく座標系
に変換されているものとする。また、透視変換の代わり
に平行投影などにより座標変換されていてもよい。第２
図（ａＸｂ）は多角形の形状情報の一例を示す説明図で
ある。第２図（ａ）に示すように頂点の座標値は頂点番
号１（ｉ＝１．２．・・・）とそれに対応する座標値（
ｘｉ、　ｙｉ、　ｚｉ　）とによって示される。第２図
（ｂ）に示すように各多角形は、多角形番号ｊ（ｊ＝１
．２．・・・）と頂点番号の並びＰｊｋ（ｋ＝１．２．
・・・）と各多角形ｊにおける各頂点ｋに対応する輝度
Ｉｊｋとによって示される。なお第２図（ｂ）の頂点番
号は、それらを時計回りに結ぶことによって多角形が構
成されるように左から順に並べる。

また各多角形の頂点番号と輝度は、三角形なら３つ四角
形なら４つと言う具合に多角形を構成する頂点の数だけ
記す。これらの形状情報により、多角形の形状を示すこ
とができる。多角形の接続情報は、ある多角形を構成し
ている稜線が別のどの多角形と接続しているかを示す情
報である。第３図（ａＸｂ）は多角形の接続情報の一例
を示す説明図である。第３図（ａ）に示すように各多角
形は、多角形番号１（ｉ＝１．２．・・・）と多角形の
左側を構成する稜線の番号並びＬＥｉｊ　（ｊ　＝　１
．２．・・・）と多角形の右側を構成する稜線の番号並
びＲＥｉｊとである。ここで多角形の左側とは、その多
角形を構成する頂点の内でｙ座標の値が最も小さい頂点
と大きい頂点とを結んだ線より左側にあるという意味で
あり、多角形の右側についても同様である。稜線の端点
の内でｙ座標の小さいものを始点、大きいものを終点と
するとき、第３図（ａ）の稜線の番号は始点のｙ座標の
小さい順に左から並べる。なお各多角形における上段と
下段には、それぞれの多角形の左側および右側にある稜
線の数だけ記す。第３図（ｂ）に示すように各稜線は、
稜線番号ｉとその稜線の始点ＦＰｉと終点ＥＰｉと左側
に接続する多角形ＬＰＯＬｉと右側に接続する多角形Ｒ
ＰＯＬｉとによって示される。これらの接続情報によっ
て多角形間のつながりを示すことができる。

まず第１図のセグメント情報作成１で多角形の形状情報
からセグメント情報を求める。第４図はセグメントを示
す説明図である。第４図に示すように２１．２２．２３
は多角形であり、１１はあるスキャンラインを含みＸＺ
平面に平行なスキャンライン平面である。セグメントは
スキャンライン平面１１と多角形２１．２２．２３との
交線で３１．３２．３３である。セグメント情報をセグ
メントに対応する多角形を示す情報とセグメントの端点
の座標値とその端点の画面上に対応する点での輝度とす
る。第５図はセグメント情報の一例を示す説明図である
。第５図に示すように各セグメントは、セグメント番号
１（ｉ＝１゜２２．・、）とそのセグメントに対応する
多角形番号Ｔｉとそのセグメントの左端のＸ座標値ＬＸ
ｉと２座標値ＬＺｉと輝度ＬＩｉおよび右端Ｘ座標値Ｒ
Ｘｉと２座標値ＲＺｉと輝度ＲＩｉとによって示される
。セグメント情報は、多角形を構成する稜線とスキャン
ライン平面との交点における座標値と輝度とを求めるこ
とにより作成できる。この詳細は、例えば文献１に記載
されている。

次に第１図のマクロセグメント情報作成２で、多角形の
接続情報とセグメント情報からマクロセグメント情報を
求める。結合しているセグメントで構成される折れ線に
よってマクロセグメントを定義する。例えば第４図では
、セグメント３１．３２．３３を結んだ折れ線である。

マクロセグメント情報を、マクロセグメントを構成する
セグメントの並びとする。第６図はマクロセグメント情
報の一例を示す説明図である。第６図に示すように各マ
クロセグメントは、マクロセグメント番号ｉ（ｉ　＝１
．２．・・・）とそのマクロセグメントの左端と右端の
Ｘ座標値ＬＸｉ、　ＲＸｉおよびそのマクロセグメント
を構成する各セグメント５ＥＧｉｊθ＝１．２．・・・
）を、左端のＸ座標値の小さい順い並べることによって
示される。マクロセグメント情報は、１つのセグメント
に対応する多角形からその両端の稜線を求め、その稜線
に接続する多角形に対応するセグメントを求めるという
具合に、次々と隣合うセグメントを求めることによって
構成できる。なおマクロセグメント情報は、あるスキャ
ンラインと次のスキャンラインとで類似していることか
ら、この類似性を利用して高速に求めることもできる。

次に第１図のマクロセグメント間の前後判定３で、同一
のスキャンラインに含まれる全てのマクロセグメント間
で前後判定をする。前後判定により、マクロセグメント
のうちで画面に表示するための見える範囲を求める。こ
のため、まずマクロセグメント間に重なりがあるかをマ
クロセグメントの両端点のＸ座標値により判定する。そ
して重なりがあるとき次のようにして前後判定をする。

ただしここではマクロセグメント間に交差がないものと
する。

１）２つのマクロセグメントＭＳＬ　ＭＳ２で重なりの
ある区間からスキャンライン上での１点ａを選ぶ２）　
ＭＳＩ、ＭＳ２のそれぞれからａを含むセグメントＳ１
、Ｓ２を選ぶ ３）Ｓｌ、Ｓ２の間で前後判定をして、前にあるセグメ
ントをＳとする ４）　Ｓを含むマクロセグメントが前にあると判定され
る なお、３）の２つのセグメント間の前後判定はセグメン
ト情報から種々の方法でできる。例えば、前記のａにお
けるＳｌ、Ｓ２の奥行きの値ｚ１、ｚ２をＳｌ、Ｓ２の
端点のＸ座標値と２座標値とからそれぞれ求めて、Ｚｌ
、ｚ２の大小から８１、Ｓ２の前後を判定する等があげ
られる。

そして、各マクロセグメントの内で画面に表示する区間
を求める。

次に第１図の各画素の輝度計算４で、各マクロセグメン
トの画面に表示する区間に含まれる画素の輝度を求める
。第７図はその表示の仕方を示す説明図である。第７図
に示すように、まずマクロセグメント４２の画面に表示
する区間４１における両端点４３．４７の輝度を求める
。その方法は、両端点４３．４７を含むセグメントＳ１
、Ｓ２を選び出し、Ｓｌ、Ｓ２の両端点のＸ座標値と輝
度とから線形補間などをすることにより求める。そして
、両端点４３．４７と画面に表示する区間４１に含まれ
るセグメントの端点４４．４５．４６とにおけるＸ座標
値と輝度とに基づいて、画面に表示する区間４１に含ま
れる各画素の輝度を線形補間して求める。

このように全てのマクロセグメントについて、画面に表
示する区間に含まれる各画素の輝度を求めることにより
、３次元空間中の複数の多面体を隠れ面消去して画面上
に表示できる。

（発明の効果） 以上述べたように、本発明の画像表示方法を用いること
によって、空間中の多面体を表示する際のセグメント間
の前後判定の回数を減らすことができるので、従来の画
像表示方法に比べて簡単な方法で高速に画像を表示する
ことができる。

【図面の簡単な説明】

第１図は本発明の実施例を示す流れ図、第２図（ａＸｂ
）は多角形の形状情報の一例を示す説明図、第３図（ａ
Ｘｂ）は多角形の接続情報の一例を示す説明図、第４図
はセグメントを示す説明図、第５図はセグメント情報の
一例を示す説明図、第６図はマクロセグメント情報の一
例を示す説明図、第７図はマクロセグメントの表示法を
示す説明図である。 図において、 １・・・セグメント情報作成、２・・・マクロセグメン
ト情報作成、３・・・マクロセグメント間の前後判定、
４・・・各画素の輝度計算、１１・・・スキャンライン
平面、２１．２２．２３・・・多角形、３１．３２．３
３・・・セグメント、４１・・・区間、４３，４７・・
・端点、４４．４５．４６・・・セグメントの端点。

Claims (1)

【特許請求の範囲】
1. ３次元空間中の複数の多面体を画面上表示するために、
   上記の多面体を構成する各多角形を上記画面上に射影し
   た時の上記画面上の各スキャンラインにおける両端点に
   対応する上記多角形上の点を結んだ線分として定義され
   るセグメントを示す情報として上記セグメントの両端点
   の座標値と輝度とを求め、上記の各スキャンライン内で
   同一の多面体に含まれかつ接続しているセグメントから
   構成されるマクロセグメントを示す情報として上記マク
   ロセグメントを構成するセグメントの接続情報を求め、
   上記マクロセグメントに含まれる複数のセグメントの両
   端点の座標値に基づき同一のスキャンライン内に含まれ
   るマクロセグメント同士の前後判定を行い、この判定結
   果と上記セグメントの両端点の輝度とに基づき画面上の
   各画素の輝度を求めることを特徴とする画像表示方法。