1【特許請求の範囲】【請求項１】表示対象となる図形を構成する全ての小図
形データを登録する領域と、各小図形データ毎の描画プ
ライオリティ番号を格納する領域とを有するセグメント
メモリと、小図形を構成する全ての画素データを生成するぬりつぶ
し手段と、描画プライオリティ番号が付与されていない全ての小図
形データをセグメントメモリから読み出してぬりつぶし
手段に供給して、描画プライオリティ番号が付与されて 10
いない全ての小図形のそれぞれを構成する全ての画素データを生成させた後に、再び描画プライオリティ番号が付与されていない全ての小図形データをセグメントメモ
リから読み出してぬりつぶし手段に供給して、描画プラ
イオリティ番号が付与されていない全ての小図形のそれ

2
ぞれを構成する全ての画素データを生成させるぬりつぶし制御手段と、１度目に生成された各小図形を構成する画素データに隠面処理を施す隠面処理手段と、隠面処理手段から出力される画素データを格納するメモ
リと、２度目に生成された各小図形を構成する画素データがメモリに格納されている画素データと一致しているか否かを判別する一致判別手段と、一致していることを示す一致判別手段からの判別結果に応答して、隠面処理手段から出力される全ての画素デー
タのメモリに対する格納処理を行なった回数に対応する
描画プライオリティ番号を生成してセグメントメモリの該当する領域に格納するプライオリティ番号生成手段とを有することを特徴とするＺソーティング装置。

(2)3【発明の詳細な説明】〈産業上の利用分野〉
この発明はＺソーティング装置に関し、さらに詳細にいえば、３次元グラフィックディスプレイ装置において透明面処理を行なう場合に特に好適なＺソーティング装置に関する。
〈従来の技術〉
従来から３次元グラフィックディスプレイ装置においては、ディスプレイ図形の立体的表現を行なうために、シェーディング機能を具備している。上記シェーディング
機能としては、直線補間を行なう場合に、輝度値をも補間することが原始的な方法として採用されていたが、描
画図形の境界においてスジが発生し、不自然な立体的表現となってしまうので、最近では、描画図形の法線ベク
トルを基にして輝度演算を行なうフォンシェーディング（Phong Shading）機能が採用されるようになっている。
このフォンシェーディング処理は、複数の透明面が存在する場合に、各透明面に対応する図形データを、不透明面を描画した後、順次奥行き順に描画してゆくことにより、最終的に自然な立体的表現を行なうことができるのである。
〈発明が解決しようとする問題点〉
上記フォンシェーディング機能においては、セグメント毎に予め設定された順序で描画するのであるから、上記
順序が不透明面から最も手前の透明面に向かうように設定されていれば、各セグメントを順次描画するのみで正確な輝度値を算出することができる。
しかし、インテリジェントな３次元グラフィックディス
プレイ装置においては、予め各セグメントの描画，順序を設定しておいても、視点を基準として向こう側から手前側に向かって順次各セグメントを描画してゆくと仮定
した場合の描画順序と同じ順序になるという保証が全くないという問題がある。
さらに詳細に説明すると、透明面が重なり合っていて、しかも当初の描画順序が、第６図に示すように不透明面（41）から透明面（42）、透明面（43）に向かって、即
ち手前側に向かって順次描画するように設定されていたとしても、図形を回転させた場合等においては、図形の描画順序は必ずしも奥行き順とは一致しなくなるのである。上記不透明面（41）の輝度値をI1、透明面（42）（43）の輝度値をI2,I3、透明面（42）（43）の透過率
をe2,e3、目に見える正しい輝度値をＩとすれば、第６図の場合には、
Ｉ＝I3＋e3（I2＋e2 I1）となる。
奥行き順に描画されている場合には、不透明面（41）、透明面（42）（43）の順に描画されるのであるから、各面を描画する毎に既に演算されメモリに格納されている輝度値と、描画しようとする面の輝度値とから新たな輝度値を求め、メモリに格納するだけでよい。

10

20

30

40

50

特公平７−５８５１１4
メモリに格納されている輝度値をIM,不透明面（41）の透過率をe1＝０とすれば、IM＝I1＋e1 IM
IM＝I2＋e2 IM
IM＝I3＋e3 IMのように同じ処理（IM＝Ii＋ei IM）を繰返すことによって最終的にIMは正しい輝度値Ｉと等しい値になる。
しかし、描画順序が奥行き順でない場合には、例えば、不透明面（41）、透明面（43）（42）の順に描画することがあり、正しい輝度値ＩがＩ＝I3＋e3（I2＋e2 I1）によって得られることを考えてみれば、奥行き順に描画されている場合と違って、同じ処理の繰返しによっては正しい輝度値を得ることができない。即ち、IM＝I1＋e1 IM
IM＝I3＋e3 IM
IM＝I2＋e2 IMの順に処理を繰返した場合には、最終的に得られる輝度
値IMは、
Im＝I2＋e2（I3＋e3 I1）となり、
Ｉ＝I3＋e3（I2＋e2 I1）
により得られる輝度値とは一致しないことになる。
したがって、描画順序と奥行き順序とが一致するという保証がない場合には、透明面同士の重なりの数だけｚバ
ッファを用意しておき、全ての面に属する全ての画素に対するｚ値を格納した後、画素毎に格納したｚ値を基に輝度値の演算順序を定めなくてはならない。
この結果、各面の輝度値や透過率を保持しておくための大容量の専用メモリが必要であり、しかもメモリ数が、面と面の重なりの数だけ必要になり、構成が複雑化するとともにコストアップの原因になるという問題がある。
そして、以上のようにして透明面の数だけ専用メモリを準備していても座標変換が施された状態によっては、第４図に見られるような透明面の場合には、同一面であっても重なりを生じる場合と生じない場合とがあり、重なりを生じる場合には、その透明面を重なりがなくなるよ
うに分割しなければならない。即ち、上記専用メモリにはかなりの冗長性が必要であり、かつ、分割のために複雑な処理が必要になるという問題がある。
さらには、メモリの数により定まる枚数以内の透明面が重なり合った状態での処理を行なうことができるのみであり、拡張性が乏しいのみならず、メモリの利用効率が低くなるという問題がある。したがって、上記の問題を解決するために、全ての透明面を奥行き方向に並べかえ
るＺソーティング処理をソフトウェアにより行なうことが考えられているが、Ｚソーティング処理を行なうための所要時間が長くなり、全体としてフォンシェーディン
グ所要時間が長くなってしまうという問題がある。
〈発明の目的〉(3)5
この発明は上記の問題点に鑑みてなされたものであり、全ての透明面を奥行き方向に並べかえるための所要時間を短縮することができるＺソーティング装置を提供することを目的としている。
〈問題点を解決するための手段〉
上記の目的を達成するための、この発明のＺソーティン
グ装置は表示対象となる図形を構成する全ての小図形データを登録する領域と、各小図形データ毎の描画プライ
オリティ番号を格納する領域とを有するセグメントメモ
リと、小図形を構成する全ての画素データを生成するぬりつぶ
し手段と、描画プライオリティ番号が付与されていない全ての小図
形データをセグメントメモリから読み出してぬりつぶし
手段に供給して、描画プライオリティ番号が付与されていない全ての小図形のそれぞれを構成する全ての画素データを生成させた後に、再び描画プライオリティ番号が付与されていない全ての小図形データをセグメントメモ
リから読み出してぬりつぶし手段に供給して、描画プラ
イオリティ番号が付与されていない全ての小図形のそれ
ぞれを構成する全ての画素データを生成させるぬりつぶし制御手段と、１度目に生成された各小図形を構成する画素データに隠面処理を施す隠面処理手段と、隠面処理手段から出力される画素データを格納するメモ
リと、２度目に生成された各小図形を構成する画素データがメモリに格納されている画素データと一致しているか否かを判別する一致判別手段と、一致していることを示す一致判別手段からの判別結果に応答して、隠面処理手段から出力される全ての画素デー
タのメモリに対する格納処理を行なった回数に対応する
描画プライオリティ番号を生成してセグメントメモリの該当する領域に格納するプライオリティ番号生成手段とを有することを特徴とするものである。
〈作用〉以上の構成のＺソーティング装置であれば、表示図形を構成する全ての小図形データをセグメントメモリに登録しておき、全ての小図形データに基いて、ぬりつぶし制
御手段により制御されるぬりつぶし手段により小図形を構成する全ての画素データを生成し、隠面処理手段により隠面処理を施すことにより、実際の図形データをメモリに格納する。
その後、ぬりつぶし制御手段によりぬりつぶし手段を制御して、小図形を構成する全ての画素データを生成する。
そして、隠面処理を施してメモリに格納された図形デー
タと、その後に生成された各小図形を構成する全ての画
素データとが全て一致しているか否かを一致判別手段により判別し、全て一致していることを示す一致判別手段

10

20

30

40

50

特公平７−５８５１１6からの判別信号に基いてプライオリティ番号生成手段により、最も手前側であることを示すプライオリティ番号を生成し、セグメントメモリの該当する領域に格納する。
次に、プライオリティ番号が格納された小図形を除く全ての小図形を構成する全ての画素データを生成し、隠面処理を施すことにより、実際に目に見える図形データをメモリに格納する。そして、ぬりつぶし手段により再び小図形を構成する全ての画素データを生成し、隠面処理を施してメモリに格納された図形データと、その後に生成された各小図形を構成する全ての画素データとが全て一致しているか否かを一致判別手段により判別する。その後、一致判別手段からの判別信号に基いて、２番目に手前側であることを示すプライオリティ番号を生成し、セグメントメモリの該当する領域に格納する。
以下、順次、上記処理を行なうことにより全ての小図形
データに対してそれぞれプライオリティ番号を生成し、セグメントメモリの該当する領域に格納することができる。
〈実施例〉
以下、実施例を示す添付図面によって詳細に説明する。
第５図は３次元グラフィックディスプレイ装置の原理を示すブロック図であり、セグメントメモリを有するセグ
メント管理プロセッサ（１）から出力される描画図形の頂点座標（x,y,z）、および色，輝度を示すインデック
ス値Ｉを入力とする座標変換部（２）と、座標変換部（２）からの出力データを入力とするクリップ部（３）と、クリップ部（３）からの出力データを入力とするぬりつぶし部（４）と、ぬりつぶし部（４）からの出力データを入力とする直線補間部（５）と、直線補間部（５）からの出力データを格納する表示用メモリ（６）とから構成されている。上記セグメントメモリは、表示対象となる図形を構成する全ての描画図形（小図形）データを登録しておく小図形データ登録領域と、各小図形のそれぞれに対応して、該当する小図形のプライオリテ
ィ番号を格納するプライオリティ番号格納領域とを有している。
また、上記セグメント管理プロセッサ（１）は、後述する全可視図形検出データを入力として、セグメントメモ
リの全可視図形に対応するプライオリティ番号格納領域にプライオリティ番号を格納するプライオリティ番号生
成格納機能と、プライオリティ番号がセグメントメモリのプライオリティ番号格納領域に格納されていない全ての小図形データをセグメントメモリの小図形データ登録
領域から読み出してクリップ部（３）を通してぬりつぶし部（４）に供給するぬりつぶし制御機能とを有している。さらに、図示しない上位プロセッサは、図形データ
をセグメント管理プロセッサ（１）に供給する機能を有しているとともに、動作指令をセグメント管理プロセッ
サ（１）に供給する機能を有している。具体的には、プ(4)7ライオリティ番号が付与されていない全ての小図形デー
タをセグメントメモリから読み出してぬりつぶし部（４）に供給した後、再度同じ小図形データをセグメン
トメモリから読み出してぬりつぶし部（４）に供給すべ
きことを指示する動作指令をセグメント管理プロセッサ（１）に供給する。
したがって、上記セグメント管理プロセッサ（１）がプライオリティ番号生成手段に相当し、上記セグメント管理プロセッサ（１）および図示しない上位プロセッサがぬりつぶし制御手段に相当する。
上記座標変換部（２）は、セグメント管理プロセッサ（１）から供給されたデータに対して平行移動，拡大，縮小，回転移動等の処理を施すものである。上記クリップ部（３）は予め設定されている枠からはみ出た部分を切断するものであり、予め設定されている枠から完全にはみ出た図形（以下、プルーニング図形と略称する）の検出を行なうこともできる。
上記ぬりつぶし部（４）は、頂点情報に基いて輪郭線を直線補間することによってスキャンラインに沿った線分に分解するものであり、全可視図形データ（描画図形を構成する全ての画素データが表示用メモリ（６）に書込まれている画素データと一致する図形データ）の検出を行なうこともできる。
上記直線補間部（５）は、上記分解された線分の始点と終点との間の画素データを生成するものである。
上記表示用メモリ（６）は上記画素データを格納するものであり、さらにセットされたＺ値データと既に書込まれているＺ値データとの比較を行なって、大きい方、または小さい方のＺ値データを保持する隠面処理機能およびセットされたＺ値データと既に書込まれているＺ値データとの一致検出を行なう機能を有している。
そして、上記クリップ部（３）、およびぬりつぶし部（４）からの出力データ（プルーニング図形検出信号、および全可視ポリゴン検出信号）をセグメント管理プロ
セッサ（１）に供給している。
上記の構成の３次元グラフィックディスプレイ装置の動作は次のとおりである。
図示しない上位プロセッサから図形データがセグメント
管理プロセッサ（１）に供給されることにより、セグメ
ントメモリに各描画図形の頂点座標、およびインデック
ス値を格納するとともに、座標変換部（２）に供給する。そして、平行移動，拡大，縮小，回転移動等に対応
する座標変換処理が施されたデータをクリップ部（３）に供給することにより、クリッピング処理を施した後、ぬりつぶし部（４）において多角形の辺を直線補間する
ことにより、スキャンラインに沿った線分に分解し、直線補間部（５）において、上記分解された線分の始点と終点との間の各点のデータを生成し、表示用メモリ（６）に格納する。したがって、表示用メモリ（６）の内容に基いて図示しないCRTディスプレイ画面上に所望

10

20

30

40

50

特公平７−５８５１１8の図形を表示させることができる。
また、全描画図形データのＺソートを行なう場合には、クリップ部（３）においてプルーニング図形の検出を行なってプルーニング図形検出結果をセグメント管理プロ
セッサ（１）に供給し、セグメントメモリに格納されている描画図形データに対応する領域に、最下位優先度（例えば65535）のプライオリティでプルーニング図形
検出データを格納する。
その後、ぬりつぶし部（４）においてスキャンラインに沿う線分に分解して直線補間部（５）に供給し、全可視図形を検出して全可視図形検出データをセグメント管理
プロセッサ（１）に供給する。そして、セグメント管理
プロセッサ（１）により、セグメントメモリに格納されている全可視図形データに対応する領域にプライオリテ
ィ番号を格納する。
以上のようにしてプライオリティ番号を格納した後は、プライオリティ番号が付与された描画図形データを除いて再び表示用メモリ（６）にデータを書込み、次いで直線補間部（５）において全可視図形を検出し、次の順位のプライオリティ番号を格納し、これら動作を順次反復することにより、表示すべき全描画図形のそれぞれに対してプライオリティ番号を付与することができる。
第４図は上記Ｚソート動作を説明する図であり、２枚の透明面が存在する状態を示している。
即ち、プライオリティ番号が何れの描画図形データにも付与されていない状態において、第４図Ａに示すように、隠面処理を施した図形データをメモリに書込んでおき、次いで描画図形を構成する全ての画素データがメモ
リの図形データと一致している描画図形を検出してプライオリティ番号 1"を付与する。
次いで、プライオリティ番号 1"が付与された描画図形
データを除いて、隠面処理が施された図形データをメモリに書込んでおき（第４図Ｂ参照）、描画図形を構成す
る全ての画素データがメモリの図形データと一致している描画図形を検出してプライオリティ番号 2"を付与する。
以下、同様にしてプライオリティ番号 3" 4"…を付与する（第４図Ｃ参照）。
以上のようにしてプライオリティ番号の付与が完了した
後は、プライオリティ番号に基いて各描画図形を順次表示させることができる。
但し、最下位優先度が付与されたプルーニング図形デー
タについては、処理を行なわないことにより表示の高速化を図ることもできる。
第１図は隠面処理、および全可視ポリゴン検出動作を行なう部分の構成を詳細に説明するブロック図であり、第５図のブロック図における直線補間部（５）に含まれる部分と表示用メモリ（６）とを示している。この部分
は、フレームメモリ（11）からの読出したＺ座標データ
が一時的に格納されるレジスタ（12）と、描画すべき線

(5)9分を構成するデータが一時的に格納されるレジスタ（13）と、両レジスタ（12）（13）の内容を入力とする演
算器（14）と、演算器（14）の動作を制御する制御回路（15）と、演算器（14）から出力される判定信号を入力とする一致判別回路（18）を有している。
上記レジスタ（13）はレジスタ（12）へのデータ格納と同期してデータが格納されるものであり、共に、同一のx,y座標に対応するｚ座標値が格納される。
上記演算器（14）は、両レジスタ（12）（13）の内容の差を算出する機能と、何れかのレジスタの内容をそのま
まフレームメモリ（11）に供給する機能とを有し、制御回路（15）から出力されるモード設定信号に基いて何れかの機能が選択される。
そして、上記演算器（14）からは、例えばレジスタ（12）の内容が大きいことを示す判定信号、および両レジ
スタの内容が等しいことを示す判定信号は、制御回路（15）に供給し、制御回路（15）は、上記判定信号に基いて何れのレジスタの内容をそのまま出力すべきであるかを示す信号を演算器（14）に供給している。
上記一致判別回路（18）は、描画図形を構成する全ての画素に対して上記演算器（14）から出力される判定信号
が両レジスタの内容が等しいことを示す判定信号である
場合にのみ全可視図形であることを示す判別信号を出力し、セグメント管理プロセッサ（１）に供給するものである。
次いで隠面処理動作を説明する。
先ず、制御回路（15）から差算出機能を選択すべきことを示すモード設定信号が演算器（14）に供給され、この間に、それぞれレジスタ（12）（13）に格納されているフレームメモリ（11）からの読出しデータ、および描画すべき線分を構成する画素データを演算器（14）に供給することにより両データの差を算出して、演算結果の正負を示す符号データを制御回路（15）に供給する。
次いで、符号データに基いて制御回路（15）から何れかのレジスタの内容をそのまま出力すべきことを示すモード設定信号を演算器（14）に供給することにより、選択されたレジスタの内容をそのままフレームメモリ（11）に格納し、隠面処理を行なわせることができる。
さらに、全可視図形検出動作を説明する。
演算器（14）により両レジスタ（12）（13）の内容の差を算出し、差か零であるか否かを示す判定信号を出力する。そして、一致判別回路（18）において、零であることを示す判定信号が、その描画図形を構成する全ての画素に対して出力されたか否かを判別することにより、全可視図形であるか否かを判別することができる。
第２図は上記判定信号に基いて自動的に全可視図形であるか否かを判別するための構成を示す電気回路図であり、上記判定信号をANDゲート（16）を通してラッチ回路（17）のＤ入力端子に供給しているとともに、画素単
位判定ストローブ信号をラッチ回路（17）のクロック入

10

20

30

40

50

特公平７−５８５１１
10力端子に供給している。そして、ラッチ回路（17）のＱ
出力信号を上記ANDゲート（16）に供給している。
尚、描画前に出力される初期化信号をラッチ回路（17）のプリセット入力端子に供給している。
したがって、描画前に出力される初期化信号をラッチ回路（17）のプリセット入力端子に供給することにより、
Ｑ出力信号をハイレベルにプリセットし、ANDゲート（16）を開く。
その後、画素を描画する毎に画素単位判定ストローブ信号をクロック入力端子に供給して、ANDゲート（16）からの出力信号をラッチする。上記ANDゲート（16）は当初開かれた状態であるから、上記判定信号がそのままラッチされ、判定信号に応じてＱ出力信号を出力する。即ち、上記判定信号が全てハイレベルであれば、次の初期化信号が供給されるまでの間、Ｑ出力信号はハイレベルのままであるが、判定信号が１度でもローレベルになれ
ば、Ｑ出力信号がローレベルになり、ANDゲート（16）を閉じるので、次の初期化信号が供給されるまでの間、
Ｑ出力信号はローレベルのままになる。
したがって、初期化信号が供給される直前のＱ出力信号がハイレベルであれば、全可視線分（極限状態としての点も含む）、または全可視図形であると判別することができ、Ｑ出力信号がローレベルであれば、全可視線分、または全可視図形でないと判別することができる。
第３図は他の実施例を示すブロック図であり、第２図の具体例を第１図に組み込んでなる実施例と異なる点は、
上記レジスタ（12）（13）および演算器（14）からなる処理部（20）を複数個並列状に設けた点、上記処理部（20）から出力される一致判定用の判定信号、およびデータレジスタファイル（21）から出力される制御信号を入力とする複数個のORゲート（22）、およびORゲート（22）からの出力信号を入力とするANDゲート（23）を設けた点、画素単位に判定せず、フレームメモリをアクセスする毎に判定ストローブを出力するようにした点のみである。尚、上記データレジスタファイル（21）は、描画対象の画素に対応してローレベル信号を出力するとともに、他の画素に対応してハイレベル信号を出力するものである。
したがって、この実施例の場合には、描画対象の画素に対応する処理部（20）から判定信号が出力され、ORゲー
ト（22）に供給される。そして描画対象の画素に対応するORゲート（22）には、データレジスタファイル（21）からのローレベル信号が供給され、他のORゲート（22）にはハイレベル信号が供給されているのであるから、上記判定信号がハイレベルであれば、全てのORゲート（22）がハイレベル信号を出力し、ANDゲート（23）からハ
イレベル信号を出力することになる。他方、判定信号がローレベルであれば、ANDゲート（23）からローレベル信号を出力することになる。
この結果、ANDゲート（23）からの出力信号レベルに基(6)特公平７−５８５１１

11
12
いて全可視線分、または全可視図形であるか否かを判別＊ 〈発明の効果〉することができる。具体的に説明すれば、書込まれたピ
以上のようにこの発明は、プライオリティ番号が付与さクセルがZ1,Z2,Z3,Z4であり、リードサイクルに読込ん
れていない図形データに基いて、一旦隠面処理を施しただピクセルがZa,Zb,…Zhである状態（ピクセルZ1,Z2,Z
状態で画素データをメモリに書込み、次いで同じ図形デ3,Z4が８ピクセルZa,Zb,…Zhのうち４ピクセルZd,Ze,Z
ータを構成する全ての画素データが上記メモリの画素デ
f,Zgに対応している状態）を考えてみれば、Z1＝Zd,Z2ータと一致していることを条件としてプライオリティ判＝Ze,Z3＝Zf,Z4＝Zgの条件が全て満足された場合に、全号を付与するので、特別なソート用のメモリを使用する
可視線分、または全可視図形であることを示す判定信号
ことなく、確実なＺソートを行なうことができるというを出力し、上記条件が１つでも満足されない場合に、全特有の効果を奏する。
可視線分、または全可視図形でないことを示す判定信号 10 【図面の簡単な説明】を出力する。
第１図はこの発明のＺソーティング装置の要部を示すブ
尚、この発明は上記の実施例に限定されるものではな
ロック図、
く、例えば、始点側から順次プライオリティ番号を付与
第２図は一致判別回路の具体例を示す電気回路図、する代わりに反対側から順次プライオリティ番号を付与
第３図は他の実施例を示すブロック図、することが可能である他、交差した描画図形が存在する
第４図はＺソート動作を説明する図、場合（プライオリティが付与されていない描画図形に対
第５図は３次元グラフィックディスプレイ装置の要部をして、２度にわたってぬりつぶしを行なう前述の処理を示すブロック図、
施した場合に、プライオリティが付与される描画図形が第６図は従来例を概略的に説明する図。
１つもなかった場合）に、各描画図形をさらに細分化し（１）…セグメント管理プロセッサ、（４）…ぬりつぶてＺソート処理を行なわせることが可能である他、交差 20 し部、（５）…直線補間部、（６）…表示用メモリ、した描画図形が存在することをホストコンピュータに通（11）…フレームメモリ、（12）（13）…レジスタ、
知して、この処理を中断、終了することが可能であり、（14）…演算器、（15）…制御回路、（16）…ANDゲー
その他、この発明の要旨を変更しない範囲内において種ト、（17）…ラッチ回路々の設計変更を施すことが可能である。
＊
【第１図】

(7)

【第２図】

【第３図】

特公平７−５８５１１

(8)

【第４図】

【第６図】

特公平７−５８５１１

(9)

【第５図】

特公平７−５８５１１