JPH01103785A - ソーティング回路 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明はソーティング回路、特に複数の基準軸情報に基
づきデータをソーティングする回路に関する。

［従来の技術］ 画像合成回路は、外部から供給される画像情報に基づき
、ＣＲＴ表示用の各種画像信号を合成出力するものであ
り、単に二次元的な平面画像ばがってなく、立体的な三
次元画像をも合成出力することができることから、例え
ば三次元画像用のビデオゲーム、飛行機及び各種乗物の
操縦シュミレータ、コンピュータグラフィックス、ＣＡ
Ｄ装置のデイスプレィおよびその他の用途に幅広く用い
られている。

ところで、画像合成回路を用いて奥行きを持った三次元
画像をリアルタイムで合成する場合には、各標体の三次
元情報を画面奥行き方向の座標値、すなわち２軸情報に
基づき各フレーム毎に高速でソーティングしてやること
が必要となる。

このために、複数の三次元データを所定の基準軸、すな
わち２軸情報に基づき高速ソーティングできるソーティ
ング回路の開発が望まれていた。

［発明が解決しようとする問題点１ しかし、従来このようなソーティングは、各データのＺ
軸情報そのものを逐次比較し並べ換えるという作業を、
全２軸情報に対して行っていたため、高速ソーティング
を行う場合には、比較的大型のコンピュータを用いなけ
ればならず、装置全体が複雑かつ高価なものとなってし
まうという問題があった。

［発明の目的］ 本発明は、このような従来の課題に鑑みなされたもので
あり、その目的は、複数のデータのソーティング処理を
簡単な構成で高速に行うことが可能なソーティング回路
を提供することにある。

［問題点を解決するための手段］ 前記目的を達成するため、本発明は、複数のデータを所
定の基準軸情報に基づきソーティングする回路であって
、 基準軸情報書込み用の少なくとも２個のメモリエリアを
有するソーティングメモリと、一方のメモリエリアに格
納された一組の基準軸情報の所定のサーチ桁の値をサー
チし、サーチした値に基づきこの一組の基準軸情報を分
類しながら昇順または降順に他方のメモリエリアに写し
換えるという転送処理を、基準軸情報の最下位の桁から
最上位の桁に向けサーチ桁を１桁ずつシフトしながら両
メモリエリアの間で繰り返し行うソーターと、 を含み、基準軸情報に基づきデータをソーティングする
ことを特徴とする。

また、本発明は、基準軸情報とその組合せ情報から成る
複数のデータを所定の基準軸情報に基づきソーティング
する回路であって、 各データの組合せ情報が書込まれる情報メモリと、 各データの基準軸情報と、組合せ情報書込アドレスとが
対を成して書込まれる少なくとも２個のメモリエリアを
有するソーティングメモリと、一方のメモリエリアに格
納された一組の基準軸情報の所定のサーチ桁の値をサー
チし、この一組の基準軸情報およびこれと対を成す組合
せ情報書込アドレスをサーチした値に基づき分類しなが
ら昇順または降順に他方のメモリエリアに写し換えると
いう転送処理を、基準軸情報の最下位の桁から最上位の
桁に向けサーチ桁を１桁ずつシフトしながら両メモリエ
リアの間で繰り返し行うソーターと、 を含み、ソーティングメモリから基準軸情報を読み出す
際、これと対をなす組合せ情報書込アドレスに基づき情
報メモリから組み合わせ情報を読み出すことにより、デ
ータを基準軸情報に基づきソーティングすることを特徴
とする。

［作用］ このように本発明によれば、転送処理を、基準軸情報の
下位桁から上位桁に向けサーチ桁を１桁ずつシフトしな
がら両メモリエリアの間で繰り返し行うことにより、最
上位桁の転送処理を終了した時点で、データは基準軸情
報に基づき昇順または降順にソーティングされた状態と
なる。

従って、本発明によれば、単に一方のメモリエリアに格
納された一組の基準軸情報の所定のサーチ桁の値をサー
チし、サーチした値に基づきこの一組の基準軸情報を昇
順または降順に分類しながら他方のメモリエリアに写し
換えるという転送処理を繰り返すという単純な処理を行
うのみで、複数のデータを所定の基準軸情報に基づき高
速ソーティングすることができ、前述した画像合成回路
のソーティング回路としてばかりでなく、これ以外の用
途にも幅広く用いることが可能となる。

［実施例］ 次に本発明の好適な実施例を図面に基づき説明する。

第１１１例 第１図には本発明に係るソーティング回路の好適な実施
例が示されている。

本発明のソーティング回路１０は、少なくとも２組のメ
モリエリア１２−１および１２−２を有するソーティン
グメモリ１２と、前記メモリエリア１２−１および１２
−２を用いて基準軸情報をソーティングするソーター１
４と、を含み、ソーティングメモリ１２にランダムに入
力される１組の基準軸情報に基づきデータを昇順または
降順にソーティング処理し出力することを特徴とするも
のである。

ここにおいて、前記各メモリエリア１２−１および１２
−２は、入力される１組の基準軸情報を格納するのに充
分なメモリ容量を有するよう形成する必要がある。そし
て、ソーティングメモリ１２に入力される１組の基準軸
情報は、１２−１または１２−２のいずれか一方のメモ
リエリアに格納される。実施例においてはメモリエリア
１２−１に格納されるよう形成されている。

また前記ソーター１４は、メモリエリア１２−１内に格
納された１組の基準軸情報を、メモリエリア１２−１お
よび１２−２間で交互に転送しながらソーティング処理
し、その値が小さい順または大きい順に並び替える。

実施例において、このソーター１４には、読出しポイン
タ１４−１および書込みポインタ１４−２の２つのアド
レスポインタが用いられている。

そして、読出しポインタ１４−１は、データ読出しを行
うメモリエリアのアドレスを指定し、データの読出しは
常に、このポインタ１４−１の指すアドレスに対して行
われ、読出しが行われる毎にポインタの指すアドレスは
１つインクリメントされる。

また、書込みポインタ１４−２は、データ書込みするメ
モリエリアのアドレスを指定し、読み出されたデータの
書込みは常にこのポインタ１４−２の指すアドレスに対
して行われる。そして、書込みが行われる毎にその値が
１つインクリメントされる。

第２図および第３図には、データ数がＮ個、各データが
Ｍビットの２進数で表されている１組の基準軸情報を、
メモリエリアのアドレスの小さい方から昇順にソーティ
ング処理する場合の一例が示されている。

本発明の特徴的事項は、一方のメモリエリアに格納され
た一組の基準軸情報の所定のサーチ桁の値をサーチし、
サーチした値に基づきこの一組の基準軸情報を分類しな
がら昇順または降順に他方のメモリエリアに写し換える
という転送処理を行うことにある。

このような転送処理を、基準軸情報の最下位の桁から最
上位の桁に向けサーチ桁を１桁ずつシフトしながら両メ
モリエリアの間で繰り返し行うことにより、最上位桁の
転送処理が終了した時点で、一方のメモリエリアに基準
軸情報を昇順または降順にソーティングして格納するこ
とができる。

ここにおいて、１組の基準軸情報を昇順にソーティング
しようとする場合には、サーチされた各サーチ桁の値に
基づき基準軸情報を分類しながら昇順に転送処理すれば
よく、また１組の基準軸情報を降ｊ１＠にソーティング
しようとする場合には、前とは逆にサーチされた各サー
チ桁の値に基づき基準軸情報を分類しなから降順に転送
処理すればよい。

第４図〜第７図には、前記第２図および第３図に示すフ
ローチャートに従って行われるソーティング処理の一例
が示されている。同図においてソーティング処理の対象
となる１組の基準軸情報は、４ビツト（Ｍ＝４　）の２
進数で表された「１」〜「８」の合計８個の基準軸情報
から構成されている。

まず、ソーティングメモリ１２にランダムに入力された
１組の基準軸情報が一方のソーティングエリア１２−１
に第４図に示すように格納された場合を想定する。

このようにして格納された１組の基準軸情報に対し、第
２図に示すソーティングが開始されると、まず最初にサ
ーチ桁を表す変数ｍがＯにリセットされ、次に第３図に
示す転送処理が開始される。

そして、転送処理が開始されると、ソーター１４内の各
ポインタ１４−１．および１４−２は共に０にリセット
され、データの読出しが行われるメモリエリアおよびデ
ータの書込みが行われるメモリエリアの先頭アドレスを
指定する。

そして、第３図のフローＡに従い、ｍ＝０のサーチ桁の
値が「０」の基準軸情報を一方のメモリエリア１２−１
からアドレスの若い順に順次読み出し、他方のメモリエ
リア１２−２に順次書込む転送処理を行う。

そして、ｍ＝０のサーチ桁の値がｒ□、の基準軸情報を
全て転送処理すると、次に読出しポインタ１４−１のみ
をリセットし、同様にしてｍ＝０のサーチ桁の値が「１
」の基準軸情報をアドレスの若い順から順次読み出し、
他方のメモリエリア１２−２へ転送処理する。

このようにして本実施例のソーティング回路１０は、１
回の転送処理で、転送元となるメモリエリア１２−１か
らの読出しをフローＡおよびフローＢで示すように二進
行い、メモリエリア１２−２に対する転送情報の書込み
を一巡行う。

従って、Ｎ個の基準軸情報に対する読出し作業と書込み
作業が同時に行われず、しかも各メモリエリアに対する
読出および書込アクセス時間が等しい場合には、１回の
転送処理に ＮＸ　（２＋１　＞　＝３Ｎ・・・（１）で表されるよ
うに合計３Ｎアクセスサイクルの転送時間が必要となる
。

なお、このような転送処理を行う場合に、サーチ桁ｍの
データが「０」の基準軸情報同士、および「１」の基準
軸情報同士は、互いにその順序関係が入れ代らないよう
にする必要がある。

このようにして、ｍ＝ｏの転送処理が終了すると、ソー
ティング回路１０は第２図に示すようにサーチ桁ｍを１
つインクリメントしｍ＝１とする。

そして、第５図に示すように、一方のメモリエリア１２
−２に格納された基準軸情報に対し第３図に示す転送処
理を同様にして行う。

この結果、このメモリエリア１２−２に書き込まれた基
準軸情報は第５図に示すように他方のメモリエリア１２
−１に転送処理されることになるそして、ｍ＝１の転送
処理が終了すると、同様にしてサーチ桁ｍをインクリメ
ントしながら、第６図および第７図に示すようにｍ＝２
およびｍ−３のサーチ桁に対する転送処理を行う。

このようにして、基準軸情報の最上位桁ｍ＝３をサーチ
桁とした転送処理が終了すると、メモリエリア１２−１
内に転送処理された基準軸情報は第７図に示すように「
１」〜「８」の昇順にソーティングされることになる。

このようにして、本実施例のソーティング回路１０では
、各基準軸情報に対してＭ回（Ｍは基準軸情報のビット
数）の転送処理を行うことにより１組の基準軸情報を昇
順または降順にソーティングすることができる。従って
、第４図〜第７図に示すように基準軸情報がＭ＝４ビッ
トであるなら−１５＝ ば、各基準軸情報に対しそれぞれ４回の転送処理をする
ことによりソーティング処理が完了する。

また、実施例のソーティング回路１０によれば、基準軸
情報のビット数Ｍが偶数ならば、最初に基準軸情報が格
納されたメモリエリア１２−１に、またＭが奇数ならば
他方のメモリエリア１２−２内にソーティングが完了し
た１組の基準軸情報が格納されることになる。

また、第４図〜第７図に示す実施例では、１組の基準軸
情報を昇順にソーティングする場合を例に取り説明した
が、本発明はこれに限らず、例えば第３図に示すフロー
チャートにおいて、まずＢで示すフローを実行し、その
次にＡで示すフローを実行するよう転送処理を行えば、
前記実施例とは逆に１組の基準軸情報を降順にソーティ
ングすることができる。

また、前記実施例においては２進数で表された１組の基
準軸情報をソーティングする場合を例に取り説明したが
、本発明はこれに限らず、３進数、４進数・・・に対し
ても同様にしてソーティングを行うことかできる。

例えば、３進数で表された１組の基準軸情報を昇順にソ
ーティングする場合には、第８図に示すように、まずｍ
＝ｏの最下位の桁をサーチ桁とする。そして、最初に当
該サーチ桁が「０」の値となる基準軸情報を転送処理し
、次に「１」の値となる基準軸情報を転送処理し、次に
「２」の値となる基準軸情報を転送処理する。

このような転送処理が終了した時点で、次に第９図およ
び第１０図に示すように、サーチ桁ｍを１つずつインク
リメントしながら同様な転送処理を繰り返し行えばよい
。

このようにすることにより、第１０図に示すように最上
位桁の転送処理が終了した時点で、３進数で表された１
組の基準軸情報が昇順にソーティングされることが理解
されよう。

また、前記実施例においては、整数で表された１組の基
準軸情報をソーティングする場合を例に取り説明したが
、本発明はこれに限らず、浮動小数点データに対しても
ソーティング処理を同様にして行うことができる。

この場合には、ソーティングメモリ１２に、例えば基準
軸情報が１０進数の場合には、次式で示すように正規化
された浮動小数点データが入力され、 ｍＸ１０　　（１０−１≦ｍ＜１００）また、基準軸情
報が２進数の場合には、次式で表される浮動小数点デー
タが入力される。

ｍＸ２　　（２６ｍく　２　〉 なお、前記各式において、ｍは正規化された仮数部を表
し、ｅは指数部（ｅ≧０の整数）を表している。

本発明において、このような浮動小数点データをソーテ
ィングする場合は、桁数に注意し、各データを指数部、
仮数部の順にあらかじめ並べ変えてやる必要がある。

従って、浮動小数点データをソーティングする場合には
、ソーティングメモリ１２の前段に正規化データ処理回
路３０を設け、この正規化データ処理回路３０を用いて
、入力される浮動小数点データを指数部、仮数部の順に
並べ変えたデータに変換しソーティングメモリ１２へ入
力する必要がある。

このような正規化データ処理回路３０を用いることによ
り、例えば指数部が２桁、仮数部が３桁からなる１０進
数の浮動小数点データ、例えば０、１２３Ｘ　１０７の
浮動小数点データの値は０７１２３に変換され、また、 ０．３Ｘ　１０”の浮動小数点データの値は１４３００
の値に変換されソーティングメモリ１２へ入力される。

また、指数部が２桁、仮数部が３桁の２進数からなる浮
動小数点データ、例えば０．１０１×２１の浮動小数点
データは０１１０１のデータに変換され、また ０、１１０Ｘ２１０の浮動小数点データは１０１１０の
値に変換されソーティングメモリ１２へ入力される。

このようにして、本発明によれば、浮動小数点データが
基準軸情報として入力された場合でも、正規化データ処
理回路３０を用いてこれを指数部、仮数部の順に並べ変
えてソーティングメモリ１２へ入力することにより、入
力された基準軸情報を前記実施例の場合と同様にして昇
順または降順にソーティングすることができる。

例えば、第２９図に示すように、仮数部３桁、指数部１
桁の１０進数からなる１組の基準軸情報が入力された場
合を想定すると、該基準軸情報を構成する各浮動小数点
データは指数部、仮数部の順に並ぶようデータ処理され
、ソーティングメモリ１２へ入力される。

従って、このようにしてソーティングメモリ１２に入力
される１組の基準軸情報は、前記実施例の場合と同様に
して昇順または降順にソーティングされることが理解さ
れよう。

また、第３０図に示すように、仮数部２桁、指数部２桁
の２進数からなる１組の基準軸情報が入力された場合を
想定すると、該基準軸情報の各浮動小数点データは指数
部、仮数部の順に並び変えられソーティングメモリ１２
へ入力される。

＝　２０− 従って、このようにしてソーティングメモリ１２へ入力
された１一組の基準軸情報は、前記実施例の場合と同様
にして昇順または降順にソーティング処理される。

また、前記実施例においては、正の基準軸情報をソーテ
ィングする場合を例に取り説明したが、本発明はこれに
限らず、１組の負の基準軸情報に対しても、負の数に補
数を用いることによりそのソーティングを同様にして行
うことができる。

また、本発明によれば、正および負の数が混在した１組
の基準軸情報に対しても、これを正のグループと負のグ
ループとに分けてそれぞれソーティングすることにより
、１組の基準軸情報を全体として昇順または降順にソー
ティングすることができる。

なお、通常負の数に補数を用いる２進数データは、正負
の符号として、正の場合には０、負の場合には１の値が
最上位ビットに与えられる。従って、正および負のデー
タが混在する基準軸情報を正および負にグループ分けす
る場合には５、最上位ビットの値が０のグループと１の
グループとに分ければ良い。

また、ここで負の場合に最上位ビットを０、正の場合に
最上位ビットを１と設定するようにすれば、基準軸情報
を正および負にグループ分けしなくても、基準軸情報全
体を昇順または降順にソーティングすることもできる。

また、前記実施例においては、ソーティングメモリ１２
のメモリエリア１２−１に１組の基準軸情報のみを書き
込み、当該基準軸情報をソーティングする場合を例に取
り説明したが、本発明はこれに限らず、基準軸情報およ
びその組合せ情報（基準軸情報とペアを成す情報）から
成るソーティングデータに対しても同様にしてソーティ
ングを行うことができる。

この場合には、入力される１組のソーティングデータを
一方のメモリエリア１２−１に順次書き込み、その基準
軸情報に着目し前記実施例の場合と同様にしてソーティ
ングを行えばよい。

なお、このようにすると、ソーティングデータ１個当り
のデータ量が多くなるため、データの読出しおよび書込
みのための時間が長くなる。このため、ソーティング処
理に要する時間もそのデータ量に比例して長くなること
は避けられない。

第２実施例 このような問題を解決するために、組合せ情報を含むソ
ーティングデータをその基準軸情報に基づきソーティン
グする場合には、第１１図に示すソーティング回路１０
を用いることが好ましい。

このソーティング回路１０は、１組のソーティングデー
タが入力されると、該ソーティングデータの基準軸情報
のみをソーティングメモリ１２内に前記実施例と同様に
して格納し、各基準軸情報と対をなす組合せ情報は情報
メモリ１６内に格納するよう形成されている。

この時、情報メモリ１６に格納された組合せ情報と、ソ
ーティングメモリ１２内に格納された基準軸情報との対
応関係を何らかの形で与えておく必要がある。

このような対応関係を与える手段としてはいくつかの方
法が考えられるが、本実施例においては情報メモリ１６
に書き込まれた各組合せ情報の書込みアドレスをインデ
ックスとして定義し、このインデックスをソーティング
メモリ１２内に、各基準軸情報と対応づけて格納してい
る。

すなわち、本実施例のソーティングメモリ１２内には、
各基準軸情報とインデックスの各ペアが隣接するアドレ
スに書き込まれている（例えば、基準軸情報は偶数アド
レス、インデックスは奇数アドレスに書き込まれている
）。そして、ソーター１４による転送処理は、基準軸情
報とそのインデックスとを１単位として行われる。

従って、実施例のソーティング回路１０では、データの
転送に、前記実施例に示すソーティング回路に比べて約
２倍のデータの読出し書込みを行う必要があり、従って
、−回の転送処理に要する時間も前記第１式で示す時間
に比べて約２倍となる。

そして、このソーティングメモリ１２内に書き込まれた
基準軸情報の転送処理を、前記第１実施例と同様にして
、サーチ桁ｍを最下位桁から最上位桁まで順次インクリ
メントしながら繰り返して行うことにより、ソーティン
グメモリ１２内に格納された１組の基準軸情報を昇順ま
たは降順にソーティングすることができる。

そして、ソーティング回路１０からのソーティングデー
タの出力は、ソーティングメモリ１２からソーティング
の終了した基準軸情報を読み出す際、各基準軸情報と対
をなすインデックスに基づき情報メモリ１６から対応す
る組合せ情報を読み出すようにして行われる。

このようにすることにより、実施例のソーティング回路
１０からは、所定の基準軸情報に基づきソーティングさ
れたソーティングデータが出力されることになる。

以上説明したように、本実施例によれば、ソーティング
データの情報量の多少に関わらず、ソーティングメモリ
１２を用いた基準軸情報ソーティング処理が短時間です
む。このため、ソーティングデータ１単位当たりの情報
量が多い場合でも、そのソーティング処理を短時間で効
率よく行うことが可能となる。

ここにおいて、本実施例のソーティング回路１０のソー
ティング時間を第１図に示すソーティング回路１０と比
較してみる。

前記実施例では基準軸情報のみを転送すればよいのに比
べて、本実施例では基準軸情報およびインデックスの２
つの情報を転送処理しなければならないため、その転送
処理に約２倍の時間がかかる。

従って、本実施例の転送処理は、 ２　（ＮＸ　（２＋１＞）　＝６Ｎ・・・（２）で示す
ように、６Ｎアクセスサイクル時間が必要となる。

また、このようなソーティング回路１０ではこれ以外に
、第２図に示すソーティング動作の開始および終了時に
イニシャライズ用の１アクセスサイクル、終了検出用の
１アクセスサイクルの合計２アクセスサイクルの余裕分
をみる必要があり、さらに転送処理１回毎に約２アクセ
スサイクルの余裕分をみる必要がある。

従って、実施例のソーティング回路１０は、ソーティン
グ処理を行うために、次式で示すアクセスサイクル時間
が必要となる。

（（６Ｎ＋２＞Ｍ＋２）・・・（３） また、本実施例のソーティング回路１０を、後述する三
次元画像合成装置に適用した場合には、一画面分のソー
ティング処理を１フイ一ルド時間（約１／６０秒＝　１
６．５ｍ５ｅｃ　）以内で行わなければならないが、こ
のような場合でも実施例のソーティング回路１０は、充
分余裕をもってソーティング処理を行うことができる。

すなわち、画像を合成するのに充分な条件、例えば、１
組の情報数がＮ＝１０２３個、個々の情報のビット数が
Ｍ−１５の基準軸情報をソーティングする場合を想定す
ると、そのソーティング時間は、前記第３式から９２１
０２アクセスサイクル時間となる。

ここにおいて、ソーティング回路１０のＲＡＭアクセス
が６．１４４　ＭＨｚクロックに同期して行われている
と仮定すれば、そのソーティング時間は次式で示すよう
になる。

９２１０２／　＜　６．１４４ｘｌＯ６）　＝１５．０
ｍ５ｅｃ−（４）このように、実施例の回路では、その
ソーティング処理時間が、前述したＣＲＴの１フイ一ル
ド時間（１６，５ｍ５ｅｃ　）以内となるため、１フイ
一ルド時間内にそのソーティング処理を余裕をもって実
行可能であることが理解されよう。

また、本実施例において、その転送処理を次のようにす
ることにより、そのソーティング時間をさらに短縮する
ことができる。

例えば、所定のサーチ桁ｍにおいて「０」のデータをサ
ーチしている時に、「１」のデータがサーチされた場合
には、そのインデックスまで読み出す必要はない。

逆に、「１」をサーチしている時に、「０」のデータが
サーチされた場合には、同様にそのインデックスを読み
出す必要はない。

従って、転送処理を行う場合に、このような不要インデ
ックスの読出しを行わないようにすれば、１回の転送処
理でＮアクセスサイクル分、転送処理時間を短縮するこ
とができ、この結果ソーティング全体の処理サイクルを
、 （５Ｎ＋２　’）　Ｍ＋２＝　７６７５７アクセスサイ
クルまで短縮することができる。例えば、このソーティ
ング回路１０を前述しなと同じ条件で三次元画像に適用
した場合を想定すると、その処理時間は ７６７５７／　（６，１４４ｘｌＯ６）　−１２，５ｍ
５ｅｃとなる。

第旦実旅倒 第１２図には本発明に係るソーティング回路１０の好適
な第３実施例が示されており、本実施例の特徴的事項は
、ソーター１４に、２組の書込みポインタ１４−２およ
び１４−３を設け、さらに予備ポインタ１４−４を設け
たことにある。

ここにおいて、前記一方の書込みポインタ１４−２は、
サーチ桁ｍのデータが「０」である基準軸情報の書込み
アドレスを指定するために用いられ、他方の書込みポイ
ンタ１４−３はサーチ桁のデータが１１」の値を示す基
準軸情報の書込みアドレスを指定するために用いられる
。

また、予備ポインタ１４−４は、サーチ桁ｍより１桁上
の桁、すなわち＜ｍ＋１）の桁におけるデータが「０」
の値を示す基準軸情報の個数をカウントするために用い
られる。

本実施例の特徴的事項は、このような１組のポインタ１
４−２および１４−３と、予備ポインタ１４−４を用い
、各サーチ桁ｍに対し１回のサーチを行うのみで、当該
桁のデータがｒ□、の基準軸情報のみならず、「１」の
基準軸情報も転送処理可能としたことにある。

第１３図には、本実施例のソーティング回路１０を用い
て行われるソーティング動作の一例が示されており、例
えば第４図に示すように一方のメモリエリア１２−１に
ランダムに格納された１組の基準軸情報に対するソーテ
ィング動作が開始されると、まず初期カウント動作が行
わる。この初期カウントにより最下位の桁ｍ＝ｏの値が
「ｏ」の値となる基準軸情報の個数にのカウントを行う
。

第１４図にはこの初期カウント動作の一例が示されてお
り、初期カウントが開始されるとまずカウントｋが０に
リセットされ、次にｍ＝ｏの桁にある各基準軸情報の値
をアドレスの若い順にサーチしていく。

そして、その値が「０」となる基準軸情報がサーチされ
る毎に、そのカウント値ｋを１つずつインクリメントし
ていく。

そして、このような初期カウントが終了すると、次に第
１５図に示す転送処理が開始される。

この転送処理が開始されると、まず読出しポインタ１４
−１および書込みポインタ１４−２がリセットされ、こ
れら各ポインタ１４−１および１４−２はメモリエリア
１２−１および１２−２の先頭の読出しアドレスおよび
書込みアドレスを指定することになる。

これと同時に、書込みポインタ１４−３には、前記予備
カウント動作により予備ポインタ１４−４を用いてカウ
ントされたカウント値ｋが初期値として設定される。

従って、書込みポインタ１４−３により最初に指定され
る書込みアドレスは、サーチ桁ｍの値が「１」を示す基
準軸情報の先頭書込みアドレスを指定することとなる。

このような初期設定が終了すると、第１５図に示すよう
に、予備カウンター１４−４の値は０にリセットされ、
フローＥおよびＦからなる一連の転送処理動作が行われ
る。

すなわち、フローＥでは、読出しポインタ１４−１によ
り指定される転送元の読出しエリアから基準軸情報を読
み出し、当該読出しポインタ１４−１の値を１つインク
リメントする。

そして、この時読み出された基準軸情報のサーチ桁ｍ（
第４図に示す場合においてはｍ＝０）の値が［０」であ
る場合には、当該基準軸情報を書込みポインタ１４−２
により指定されるメモリエリア１２−２のアドレスに転
送し、当該書込みポインタ１４−２の値を１つインクリ
メントする。

また、読み出された基準軸情報のサーチ桁ｍの値が「１
」の場合には、書込みポインタ１４−３によって指定さ
れるメモリエリア１２−２のアドレスに当該基準軸情報
を転送し、その後この書込みポインタ１４−３の値を１
つインクリメントする。

最初の基準軸情報の転送が終了すると、次にフローＦに
示すように、読み出された基準軸情報に対し、そのサー
チ桁ｍより１つ上の桁、すなわち＜ｍ＋１）の桁の値が
０か否かを判定し、その値が「Ｏ」であるならば予備カ
ウンタ１４−４のカウント値ｋを１つインクリメントす
る。

このようにして、実施例のソーティング回路１０は、基
準軸情報を１回読み出す毎にサーチ桁の値に応じた転送
処理を行うとともに、そのサーチ桁より１つ上の桁の値
が０か否かを検出し、０ならば予備カウンタ１４−４の
値をその都度インクリメントするという動作を繰り返し
て行う。

この結果、実施例のソーティング回路１０を用いて所定
のサーチ桁ｍ、例えばｍ＝ｏのサーチ桁に対するサーチ
を１回行えば、当該サーチ桁における転送処理は全て終
了し、しかも当該サーチ桁より１桁上（ｍ＝、１の桁）
の値が「０」となる基準軸情報が何個あるかを予備ポイ
ンタ１４−４を用いて検出することができる。

従って、実施例のソーティング回路１０によれば、各サ
ーチ桁ｍのサーチが終了する毎に、第１３図に示すよう
にサーチ桁ｍを１つにクリメントし第１５図に示す転送
処理を繰り返して行うことにより、例えば第４図〜第７
図に示すように、１組の基準軸情報のソーティングを前
記第１実施例と同様に行うことが可能となる。

この時、本実施例のソーティング回路１０は、第１図に
示すソーティング回路に比べ、１回の転送処理に要する
アクセスサイクル時間を大幅に短くし、ソーティングに
要する時間を短縮することが可能となる。

すなわち、本実施例のソーティング回路１０によれば、
１回の転送処理に、転送元のメモリエリアからのデータ
の読出しを一巡、転送先メモリエリアに対するデータの
書込みを一巡行えばよい。

このため、Ｎ個の基準軸情報を転送する場合には、その
転送処理を Ｎ（１＋１）＝２Ｎ　　　　　　　　　・・・（５）の
アクセスサイクル時間で済ますことができる。

また、本実施例のソーティング回路１０を、例えば第１
１図に示すようなタイプのソーティング回路１０に適用
すれば、転送処理の対象となるデータが２倍（基準軸情
報とそのインデックス情報）となる。このため、１回の
転送処理に用する時間は第５式に示す値の２倍、すなわ
ち ２Ｘ２Ｎ＝４Ｎ　　　　　　　　　　　・・・（６）の
アクセスサイクル時間となる。

また、本実施例のソーティング回路１０を第１１図に示
す回路に適用した場合には、ソーティング処理のイニシ
ャライズおよび終了検出にそれぞれ１アクセスサイクル
の計２アクセスサイクルの余裕分をみる必要がある。ま
た、これ以外に第１５図に示すフローＥの転送処理に２
アクセスサイクル余裕分をみる必要がありしかも、第１
４図に示す初期カウントに（Ｎ＋２）アクセスサイクル
を必要とする。このため、ソーティング全体では、 ＜４Ｎ＋２）Ｍ＋　（Ｎ＋２）＋２ ＝（４Ｎ＋２）Ｍ＋Ｎ＋４　　　・・・（７）のアクセ
スサイクル時間が必要となる。

この第７式で示されるアクセスサイクル時間を、Ｍ＝１
５、Ｎ＝１０２３からなる１組の基準軸情報をソーティ
ングする場合を想定して演算すると、そのソーティング
には６２４３７アクセスサイクル時間が必要となる。

従って、このソーティングを、例えば６．１４４ＭＨｚ
のクロックに同期して行う場合に、そのソーティング時
間は、 ６２４３７／　（６，１４４ｘ１０６）　＝１０．２ｍ
５ｅｃとなり、前記第１実施例のソーティング回路を第
１１図に示す回路に適用した場合に比べそのソーティン
グ時間を大幅に短縮可能であることが理解されよう。

なお、本実施例においては、２進数からなる基準軸情報
に基づきデータをソーティングする場合を例にとり説明
したが、これ以外に、３進数、４進数、・・・からなる
基準軸情報に基づきデータをソーティングする場合にも
用いることができる。

例えば基準軸情報が３進数の場合には、「０」「１」「
２」用の合計３個の書込ポインタと、ｒＱＪ　ｒｌＪ用
め合計２個の予備ポインタを設ける。そして、「２］用
の書込ポインタには、その初期値としてｒＱＪ　　ｒｌ
Ｊ用の各予備ポインタの加算値をセットしてやればよい
。このようにすることにより、３進数からなる基準軸情
報に基づきデータを良好にソーティングすることができ
る。

以上説明したように、本発明によれば２組のメモリエリ
アを有するソーティングメモリを用い、その値がランダ
ムに入力される１組の基準軸情報のソーティングを高速
で行うことができる。

特に、本発明によれば、所定のルールに従って、２つの
メモリエリアの間を、データを転送処理するという単純
な作業でそのソーティングを行うことができるため、回
路全体を極めて簡単なものとすることが可能となる。

さらに、本発明によれば、基準軸情報が各種の情報と組
み合され、データ量が大きなソーティングデータとなっ
た場合でも、前記第１１図に示す回路構成を採用するこ
とにより、このようなデータ量の多い各ソーティングデ
ータをその基準軸情報に従い高速でソーティング処理す
ることが可能となる。

用途 以上説明したように、本発明に係るソーティング回路１
０は各種のデータをその基準軸情報に基づき高速ソーテ
ィングすることができる。このため、大量のデータをソ
ーティングする場合、例えば、データベースの情報を日
付などの基準軸情報に基づきソーティングする場合や、
その他の用途に広範囲に用いることができる。

以下に本発明のソーティング回路１０を三次元の画像合
成装置に適用した場合の好適な一例を説明する。

具体例 第１６図には、本発明を用いた三次元画像合成装置の好
適な一例が示されており、実施例の装置は、ポリゴン情
報発生回路２０、本発明に係るソーティング回路１０お
よびポリゴン表示回路２２から構成され、立体の二次元
画像、すなわち擬似三次元画像をＣＲＴ上に合成表示す
るよう形成されている。

前記ポリゴン情報発生回路２０は、三次元の立体情報を
扱い、これに回転、平行移動、透視投影などの各種変換
を施して、表示すべき三次元情報を二次元多角形の組合
せ情報に変換し、各多角形の頂点の（Ｘ、Ｙ）座標をポ
リゴン情報として演算している。

また、このポリゴン情報発生回路２０は、各多角形の奥
行き方向の表示地点、すなわち各多角形中心の２軸座標
をもポリゴン情報として演算し、さらに、必要に応じて
多角形の色情報、輝度情報などを付随データとして演算
する。

なお、本実施例においては説明を簡単にするために、付
随データとして色情報が演算されるものとして以後の説
明を行う。

このようにして、ポリゴン情報発生回路２０から各多角
形のポリゴン情報（多角形の各頂点位置におけるＸＹ座
標、中心点におけるＺ軸座標および色情報）が演算出力
されると、ソーティング回路１０は、出力される複数の
ポリゴン情報を所定の基準軸情報、この場合にはＺ軸情
報に基づきソーティングしポリゴン情報表示回路２２へ
向け出力する。

すなわち、実施例のソーティング回路１０は、ＣＲＴの
１画面毎に演算される複数のポリゴン情報を、そのＺ軸
座標値が小さいものから順にポリゴン表示回路２２に向
けソーティング出力する。

従って、第１７図に示すように、ＣＲＴの画面上を基準
点とし、その奥行き方向に向けＺ軸が大きくなるように
ＸＹＺの三次元座標を設定すると、ソーティング回路１
０からは、画面の手前に表示される多角形、すなわち優
先度の高い多角形のポリボン情報から順にソーティング
出力されることとなる。

そして、ポリゴン表示回路２２は、このようにして出力
される各多角形のポリゴン情報を、その優先度を基にし
て画像合成し、例えば複数の多角形が重ね合せ表示され
るような場合は、その優先度の高い多角形が優先的に表
示されるよう三次元画像の合成を行う。

なお、本実施例においてはソーティング回路１０として
多角形のポリゴン情報をその２軸座標値に基づき昇順に
ソーティング出力するものを例に取り説明したが、本発
明はこれに限らず必要に応じて所定の基準軸情報、実施
例の場合にはＺ軸情報に基づきポリゴン情報を降順にソ
ーティング出力することも可能である。

ポリゴン　　　生口 第１８図には、飛行機用操縦シュミレータ装置に適用さ
れたポリゴン情報発生回路２０の具体的な構成が示され
ており、実施例のポリゴン情報発生回路２０は、飛行中
における各種フライト条件のシュミレーション画像を演
算し、このシュミレーション画像を複数多角形の組合せ
情報としてソーティング回路１０へ向け出力している。

実施例において、このポリゴン情報発生回路２０は、操
作部２０−１、メインＣＰＵ回路２０−２、三次元情報
メモリ２０−３、三次元演算回路２０−４を含む。そし
て、前記操作部２０−１は、実際の飛行機の操縦席と全
く同じに形成され、その操作情報は、スイッチや可変抵
抗器を介して電気信号に変換され、メインＣＰＵ回路２
０−２へ向け出力される。

メインＣＰＵ回路２０−２は、シュミレータとして動作
の中枢部を成すものであり、操作部２〇−１から出力さ
れる信号に基づき、飛行機の飛行位置を表すデータを演
算し三次元演算回路２０−４へ向け出力する。

また、このメインＣＰＵ回路２０−２は、三次元演算回
路２０−４から出力される各種の状況信号、例えば「飛
行機が他の物体に衝突した」、「飛行機が乱気流に入っ
た」、「、飛行機が目的地に到達した」などの情報を受
は取り、これに応じた状況データを演算し、三次元演算
回路２０−４へ向け出力している。

また、前記三次元情報メモリ２０−３には、あらゆる物
体が多面体として表現され、この多面体の各頂点を表す
三次元座標データと、多面体の各表面を各頂点のつなが
りとして表す多角形データとが書き込み記憶されている
。ここにおいて、前記各多面体データは、固定座標系を
用いて表されている。

また、前記三次元演算回路２０−４は、メインＣＰＵの
演算する飛行機の現在位置に基づき、三次元情報メモリ
２０−３に格納された各種多面体データを参照しながら
、その飛行機から見える光景を演算する。そして、その
光景を図形情報の組合せとしてソーティング回路１０へ
向け出力している。

本実施例におけるポリゴン情報発生回路２０は以上の構
成から成り、次にその作用を説明する。

　４３　一 実施例の三次元演算回路２０−４は、飛行機を原点とし
た移動座標系を想定し、第１７図に示すごとく、図中右
方向をＸ座標、下方向をＹ座標、前方向をＺ座標に設定
する。

そして、メインＣＰＵ回路２０−２から、飛行機の現在
位置を表す移動座標が出力されると、この三次元演算回
路２０−４は三次元情報メモリ２０−３から所定の多面
体データの読出しを行う。

実施例において、三次元情報メモリ２０−３に書き込ま
れた情報は、固定座標系を用いて表されているため、三
次元演算回路２０−４は、三次元情報メモリ２０−３か
ら読み出した情報を移動座標系の座標データに変換する
必要がある。

この変換には、座標の回転と平行移動という２つの演算
要素の組合せで実現することができ、こ　　　゛の演算
の過程において、パイロットの視野に入らないことが判
明した情報＜２＜ａなど）が除去される。変換により求
められた状況データは、メインＣＰＵ回路２０−２へ向
け出力される。そして、座標変換された各多面体情報は
、次に表示画面がＺ＝０の平面上にあるとして、ｚく０
の視点に向って透視投影変換される。

このような透視投影変換により、前記各多面体データは
、多面体の各頂点座標をＸ、Ｙの二次元に変換した点情
報の集りとして表される。

また、このような透視投影変換を行うにあたり、視点と
多面体の各頂点座標との距離を求めておく。

そして、前記透視投影変換により求められた二次元の点
座標（多面体の頂点座標）を、多面体表面を表す各多角
形毎に分類し、分類した多角形がパイロットの視野すな
わち画面の視野に入るや否かをチエツクし、視野に全く
入らない多角形は除去する。

その後、この三次元演算回路２０−４は、受付は座標範
囲に入る多角形に対し、当該多角形の中心点におけるＺ
軸座標の値を代表値として決定する。

これと同時に、三次元演算回路２０−４は、受付は座標
範囲に入る各多角形の付随データ、実施例においては色
情報を演算する。

そして、三次元演算回路２０−４は、このようにして求
めた各多角形の頂点のＸＹ座標、その中心位置の２軸座
標および色情報をポリゴン情報として各多角形毎に出力
する。

実施例のポリゴン情報発生回路２０から出力される各多
角形のポリゴン情報は１７ワードで構成され、その中の
１ワードが中心点の２座標、残りの１６ワードが多角形
の頂点のＸＹ座標、色情報などを表すために用いられて
いる。

また、前記１ワードは１７ビツトで構成されている。

このようにして、実施例のポリゴン情報発生回路２０は
、パイロットの視野に入る状況を複数の多角形の組合せ
情報に変換し、各多角形のポリゴン情報をソーティング
回路１０へ向け順次出力することになる。

ここにおいて、各多角形はそのポリゴン情報に含まれる
２軸座標値が小さいほど画面の手前に表示されるため、
ポリゴン情報に含まれるＺ軸座標値の値が小さいほど当
該多角形の優先度が高いことになる。従って、このよう
にランダムに出力される各多角形のポリゴン情報をその
Ｚ軸座標値の小さい順にソーティングしてやれば、ポリ
ゴン表示回路２２による三次元画像の合成を簡単かつ迅
速に行うことが可能となる。

（以下余白） 又二ｊシ宸Ｃ乙可賂 本発明のソーティング回路１０は、所定の基準軸情報を
含む複数のデータを、前記基準軸情報に基づき昇順また
は降順にソーティングすることを特徴とするものである
。

第１９図には、本実施例に係るソーティング回路１０の
具体的な構成が示されている。

実施例のソーティング回路１０は、第１１図に示すタイ
プの回路として形成されており、ソーティングメモリと
してソーティングＲＡＭ１２が用いられ、情報メモリと
してＸＶＲＡＭ１６が用いられている。

前記ソーティングＲＡＭ１２およびＸＶＲＡＭ１６は、
前段のポリゴン情報発生回路２０によるデータの書込み
と、後段のポリゴン表示回路２２によるデータの読出し
とが独立で行われる、いわゆるマルチボートＲＡＭとし
て形成されている。

そして、ポリゴン情報発生回路２０から出力される一画
面分の多角形のポリゴン情報の内、その基準軸情報、実
施例においてはＺ軸情報はソーテインクＲＡＭ１２に書
き込まれ、残りの情報がＸＶＲＡＭ１６に書き込まれる
。

そして、ソーター１４はソーティングＲＡＭ　１２内に
書き込まれたＺ軸情報をソーティングするとともに、こ
れらＲＡＭ１２および１６の制御を行っている。

本実施例において、ソーティングＲＡＭ１２がソーティ
ングするのはソーティングＲＡＭ１２に書き込まれたＺ
軸情報のみであり、ＸＶＲＡＭ１６に書き込まれたポリ
ゴン情報は入力側から出力側へそのまま伝達される。

そこで、ソーティング処理が終了した後、ソーティング
ＲＡＭ１２内でソーティングされたＺ軸情報とＸＶＲＡ
Ｍ１６内に書き込まれたポリゴン情報との関連を示すた
めに「インデックス」が必要となる。

このため、ポリゴン情報発生回路２０からＸＶＲＡＭ１
６およびソーティングＲＡＭ１２に各多角形のポリゴン
情報が書き込まれる際に、ＸＶＲＡＭ１６に書き込まれ
る各多角形情報の先頭アドレスが「インデックス」とし
てソーティングＲＡＭ１２に書き込まれる。

このとき、ソーティングＲＡＭ１２に書き込まれるイン
デックスは各多角形毎に１ワードの値として与えられ、
対応する多角形のＺ軸座標とペアでソーティングＲＡＭ
１２に書き込まれている。

（ａ）サイクルスチール ところで、前記ＸＹＲＡＭ１６は、ポリゴン情報発生回
路２０とポリゴン表示回路２２の両者からアクセスされ
るデュアルポートＲＡＭとして形成されている。また、
ソーティングＲＡＭ１２は、先の２つの回路に、さらに
ソーター１４が加わった王者からアクセスされるトリプ
ルポー）ＲＡＭとして形成されている。

通常のＲＡＭをこのようにマルチボート化するために、
一般にサイクルスチールという手法が用いられる。

本実施例においては第２０図に示すように、　　。

３．０７２　ＭＨｚのタロツクＣＰＩに同期してＸＹＲ
，ＡＭ１６をマルチボート化し、さらにこのクロックＣ
ＰＩを２分割したクロックＣＰ２を用いてソーティング
ＲＡＭ１２をマルチポート化している。

同図において、■はポリゴン情報発生回路２０による書
込み区間を表し、■はポリゴン表示回路２２による読出
し区間を表し、■はソーター１４による書込みまたは読
出し区間を表している。

（ｂ）エリアの切替え また、本実施例においてソーティングＲＡＭ１２および
ＸＹＲＡＭ１６は、それぞれ複数のメモリエリアを有し
、個々のエリアが一画面分（１フイ一ルド分）の容量を
持つよう形成されている。

そして、これらのＲＡＭ１２および１６は、１つのフィ
ールド期間内で、各種変換回路により別々のメモリエリ
アがアクセスされ、またフィールドの切替わる時点で、
周辺回路のアクセスするエリアが切り替わるよう形成さ
れている。

これによって、ポリゴン情報発生回路２０→ソーター１
４→ポリゴン表示回路２２という経路の＝　５１　− パイプライン処理が実現される。

（ｂの１）ソーティングＲＡＭ１２のエリア切替え 本発明のソーティングＲＡＭ１２は、少なくとも２つの
メモリエリアを有するよう形成されれば充分であるが、
本実施例においてはソーティング処理の高速化を図るた
めに、４つのメモリエリアを有するよう形成されている
。

第２１図には、ソーティングＲＡＭ１２の各メモリエリ
ア１２−１．１２−２、・・・１２−４のエリア切替え
動作の一例が示されており、同図には、ソーティングＲ
ＡＭ１２内の４つのメモリエリア１２−１．１２−２、
・・・１２−４のメモリエリアの切替えが時間の経過と
ともにどのようにして行われるかが概略的に表されてい
る。

同図においては、説明を簡単にするために、１００の領
域に位置するメモリエリアはポリゴン情報発生回路２０
によりアクセスされ、１０２および１０４の領域に位置
するメモリエリアはソータ−１４によりアクセスされ、
１０６の領域に位置するメモリエリアはポリゴン表示回
路２２によりアクセスされるものとする。

ここにおいて、Ａ（図示せず）、Ｂ（図示せず）、Ｃは
ソーティング前における各フィールド毎の２軸情報、ａ
、ｂ、ｃはソーティング中における各フィールド毎のＺ
軸情報、Ａ−、Ｂ−１Ｃ−はソーティング後における各
フィールド毎のＺ軸情報をそれぞれ表している。

ここにおいて、Ｃ，ｃ、Ｃ−の２軸情報に着目してみる
と、まずフィールド１において、メモリエリア１２−１
にＣの２軸情報がポリゴン情報発生回路２０によって書
き込まれる。

そして、フィールド１からフィールド２へ切り替わると
同時に、ポリゴン情報発生回路２０のアクセスしている
エリア１２−１と、ソーター１４のアクセスしているエ
リア１２−２とのエリア切替えが行われ、またこれと同
時にソーター１４のアクセスしているエリア１２−３と
ポリゴン表示回路２２のアクセスしているエリア１２−
４の間でエリア切替えが行われる。

このような各メモリエリアの切替えは、フィールドが切
り替わる毎に瞬時に行なわれ、その後各メモリエリアは
ポリゴン情報発生回路２０、ポリゴン表示回路２２およ
びソーター１４により、第２０図に示すタイミングチャ
ートに従ってアクセスされる。

この時、ソーター１４は、前述したように、−方のメモ
リエリアに格納された一組の基準軸情報の所定のサーチ
桁の値をサーチし、サーチした値に基づきこの一組の基
準軸情報を分類しながら昇順または降順に他方のメモリ
エリアに写し換えるという転送処理を繰り返しソーティ
ングを行う。

このようなソーティングが完了した時点で、メモリエリ
ア１２−１または１２−４にはＣのＺ軸情報が昇順また
は降順にソーティングされた状態で書き込まれることに
なる。

このとき、基準軸情報のビット数Ｍが奇数の場合には、
メモリエリア１２−４に最終的な基準軸情報が書き込ま
れる。しかし、ビット数Ｍが偶数の場合にはメモリエリ
ア１２−１に基準軸情報が書き込まれるため、この場合
には、その値を他方のメモリエリア１２−４に転送して
やる必要がある。　その後、フィールド２からフィール
ド３へ切り替えると同時に、該メモリエリア１２−４は
ポリゴン表示回路２２によりアクセスされることとなる
。

また、ビット数Ｍが偶数の場合には、前述のようにメモ
リエリア１２−１に書き込まれた最終的な基準軸情報を
メモリエリア１２−４へ転送することなく、たとえば、
フィールド３からフィールド４への切換えと同時にメモ
リエリア１２−１からソーティングされた最終的な基準
軸情報をポリゴン表示回路２２が直接読出すよう形成し
てもよい。このとき、メモリエリア１２−４に、ポリゴ
ン情報発生回路２０からランダムに出力される基準軸情
報が書込まれるよう、エリア切換えを行なう必要がある
。

このようにして、本実施例においては、フィールド１に
おいて、ポリゴン情報発生回路２ｏがらメモリエリア１
２−１にランダムに書き込まれたＣの２軸情報が、フィ
ールド２において、ソーティング回路１０により昇順ま
たは降順にソーティング処理され、フィールド３でメモ
リエリア１２−３からポリゴン表示回路２２により読み
出されることとなる。

ところで、第２１図からも明らがなように、実施例のポ
リゴン表示回路２０は２フイールド過去のＺ軸情報Ｃを
読み出している。

従って、ＸＹＲＡＭ１６からも、ソーティングＲＡＭ１
２と同期して２フイールド前のデータを読み出すことが
必要となる。

（ｂの２）ＸＹＲＡＭのエリア切替え 本実施例のＸＹＲＡＭ１６は、第２２図に示すように３
個のメモリエリア１６−１．１６−２．１６−３を有す
る。

そして、このＸＹＲＡＭ１６は、第２０図に示すタイミ
ングチャートに従い、１１０の領域にあるメモリエリア
がポリゴン情報発生回路２０によりアクセスされ、１１
４の領域にあるメモリエリアがポリゴン表示回路２２に
よりアクセスされ、また１１２の領域にあるメモリエリ
アがどこからもアクセスされず情報保持するだけの状態
に制御される。

そして、実施例のＸＹＲＡＭ１６は、各メモリエリア１
６−１．１６−２．１６−３が各フィールド切替えに同
期して、１個ずつローティジョンしながら切替制御され
るよう形成されている。

従って、例えばフィールド１において、ポリゴン表示回
路２０からメモリエリア１６−１に書き込まれたＣのポ
リゴン情報は、フィールド２でそのまま保持され、フィ
ールド３でポリゴン表示回路２２により読み出さる。こ
の結果、ポリゴン表示回路２２は、２フイールド過去の
ポリゴン情報Ｃ−を読み出すこととなる。

このとき、ＸＹＲＡＭ１６の読出しアドレスは、ソーテ
ィングＲＡＭ１２から読み出される各多角形の２軸座標
と対をなす「インデックス」により指定され、各ポリゴ
ン情報は２軸座標のソーティング順に順次読み出される
ことになる。

このようにして、本実施例のソーティング回路１０は、
１フイールド毎にポリゴン情報発生回路２０から演算出
力される複数の多角形のポリゴン情報を、１フイ一ルド
時間内にそのＺ軸座標に基づき昇順にソーティング処理
しポリゴン表示回路２２へ向け出力することができる。

（ｂの３）画面情報の書込み遅れが発生した場合のメモ
リエリアの切替え ところで、ポリゴン情報発生回路２０は、一画面分の情
報の書込みを１フイールド内で完了するのが原則である
が、その処理内容によっては、１フイールド内で書込み
が完了せず、次のフィールドにまたがることもある。

このような書込み遅れが発生すると、ソーティング回路
１０は、フィールド更新時であっても入力メモリエリア
の切替えができず、その切替えを次のフィールド更新時
まで待たなくてはならない。

この場合に、全メモリエリアの切替えを停止すると、パ
イプライン遅延が増大するため、何らかの対策が必要と
なる。

例えば、フィールド１からフィールド２への更新時に、
前記書込み遅れが発生し、情報「Ｃ」の書込みが両フィ
ールドにまたがってしまった場合を想定する。

この場合、書込み遅れが発生しなければ、「Ｃ」の１つ
前の情報である「Ｂ」がフィールド２で出力される。

しかし、エリア切替えを全て同時に停止してしまうと、
「Ａ」が２フイールドにまたがって出力され、ｒ１３Ｊ
の出力が１フイールド遅れてしまう。

このようなパイプライン遅延を少しでも少なくするため
、本実施例のソーティング回路１０は、書込み遅れが発
生した場合には以下に述べるような変則的なエリア切替
えを行う。

■：ソーティングＲＡＭのエリア切替え第２３図には、
フィールド１からフィールド２への更新時に一画面分の
情報「Ｃ」の書込み遅れが発生した場合におけるソーテ
ィングＲＡＭ１２のエリア切替え動作の一例が示されて
おり、この場合には、フィールド１からフィールド２へ
の切替え時にメモリエリア１２−１および１２−２のエ
リア切替えを停止し、さらにフィールド２がらフィール
ド３への切替え時にメモリエリア１２−４および１２−
３のエリア切替えを停止する。

なお、この時フィールド２において行われるメモリエリ
ア１２−２および１２−４の間のソーティングは無効と
される。

■：　ＸＹＲＡＭのエリア切替え また、第２４図には、フィールド１からフィールド２へ
の更新時にメモリエリア１６−１への情報「Ｃ」の書込
み遅れが発生した場合におけるＸＹＲＡＭ１６のエリア
切替え動作の一例が示されており、この場合には、フィ
ールド１からフィールド２への更新時にメモリエリア１
６−１の切替えを停止し、さらにフィールド２からフィ
ールド３への更新時にメモリエリア１６−３の切替えを
−６０＝ 停止する。

このようにして、実施例のソーティング回路１０では、
メモリエリアへの一画面分の情報の書込み遅れが発生し
た場合に、第２３図および第２４図に示すようにメモリ
エリアの切替えを変則的に行い、パイプライン処理によ
る遅延を最小限に抑制している。

なお、本実施例においては、ＸＹＲＡＭ１６、ソーティ
ングＲＡＭ１２のエリア切り替えを、１フイールド毎に
行う場合を例にとり説明したが、本発明はこれに限らず
、画面が更新される毎にエリア切り替えを行うよう形成
すれば充分である。

例えば、画面が１フレーム毎、数フレーム毎、または数
フイールド毎に更新される場合には、これに合わせて１
フレーム毎、数フレーム毎、または数フイールド毎にエ
リア切り替えを行えばよい。

（ｃ）メモリマツプ 第２５図には、本実施例に用いられるソーティングＲＡ
Ｍ１２およびＸＹＲＡＭ１６のメモリマツプの一例が示
されており、実施例においては、ＸＹＲＡＭ１６の１つ
のメモリエリアとソーティングＲＡＭ１２の１つのメモ
リエリアとが一体となり、入出力がそれぞれ単一のアド
レスバスと単一のデータバスでアクセスされるよう回路
構成されている。

同図において、（１）は入力側のメモリマツプ、（２）
は出力側のメモリマツプをそれぞれ表している。

なお、以下の説明では、ポリゴン情報発生回路２０から
ランダムに出力される各多角形のポリゴン情報にＮＯ，
０１ＮＯ１１、−ｔ４０．　　＜ｎ−１＞の番号を与え
る。また、このようにして出力される多角形のポリゴン
情報に対し優先度の高い順にＰｒ。

０、Ｐｒ、　１、・−・Ｐｒ、　　（ｎ−１＞の番号を
与える。

ここで、ｎは一画面中に表示される多角形のポリゴン情
報の番号を表し、実施例においては０≦ｎ≦１０２３の
範囲に設定される。

（Ｃの１）ＸＹＲＡＭ　（入出力共通）のメモリマツプ 第２６図にはＸＹＲＡＭ１６の１つのメモリエリアのメ
モリマツプが示されており、このメモリエリアは、入力
側および出力側から見て、その物理アドレスは共に００
００１１〜３　Ｆ　Ｆ　Ｆ　Ｈの範囲にある。

そして、このメモリエリアには、各多角形毎に１６ワー
ドずつのデータ書込みエリアが設けられている。

第２６図（２）には、１つの多角形に対して与えられた
メモリエリアの詳細なメモリマツプが示されており、同
図において、このエリアには四角形のポリゴン情報に含
まれる色情報と４つの頂点のＸＹ座標とが９ワード分書
き込まれ、残り７ワ一ド分が空領域となっている。

（Ｃの２）ソーティングＲＡＭの入力側メモリエリアの
メモリマツプ 第２７図には、ソーティングＲＡＭ１２の入力側メモリ
エリアにおけるメモリマツプの一例が示されており、各
多角形の中心位置における２軸座標は前述したように１
５ビツトのデータにより与えられている。このため、こ
れら各Ｚ軸座標は同図に示すメモリエリアの偶数ワード
の所定エリア（偶数ワードのビットＯ〜ビット１４の領
域）に書き込まれている。また、これら各偶数ワードの
最上位ビット（偶数ワードのビット１５の領域）には「
終了フラグ」が書込み可能に形成されている。

なお、第２７図に示すメモリマツプを第２６図に示すＸ
ＹＲＡＭのメモリマツプと比較すると、入力側のソーテ
ィングＲＡＭとＸＹＲＡＭとでは、多角形０．１．２、
・・・ｎ−１のＪｌＭにその情報が同じ並びになってい
ることが理解される。

このデータの並びを利用して、前述したように、ＸＹＲ
ＡＭ１６に書き込まれた各多角形のポリゴン情報書込み
エリアの先頭アドレスが、インデックスとして定義され
ている。

そして、第２７図に示すように、ソーティングＲＡＭ１
２の入力側メモリエリアの偶数ワードに各多角形の２軸
座標値が書き込まれる毎に、当該メモリエリアの奇数ワ
ードに当該多角形のインデックスが順次設定される。

第２６図に示すように、本実施例のＸＹＲＡＭのメモリ
エリアには、１つの多角形のポリゴン情報を書き込むな
めに１６ワードが割り当てられている。このため、例え
ば、ｋ番目の多角形のポリゴン情報書込みエリアの先頭
アドレスは１６にで与えられる。

従って、ソーティングＲＡＭ１６のメモリエリアに書き
込まれたに番目の多角形のインデックスは、１６にのア
ドレス情報となる。

（Ｃの３）ソーティングＲＡＭの出力側エリアのメモリ
マツプ 第２８図には、ソーティングＲＡＭ１２の出力側メモリ
エリアのメモリマツプの一例が示されており、同図に示
すようにこのメモリエリアには各多角形のＺ軸座標がそ
の値の小さいＪｌ［に、すなわち優先度の高い順にソー
ティングされた状態で書き込まれている。

ここにおいて、このメモリエリアの偶数アドレスにはソ
ーティングされた各多角形のＺ軸座標値、奇数アドレス
にはそのインデックスが書き込まれている。ここにおい
てＰｒ、　ｋの多角形が、ソーティング前はＮＯ，ｋ−
であると仮定すると、Ｐｒ、　ｋの多角形のインデック
スは１６に゛で与えられる。

なお、実施例では、ｋもに−も１０ビツトで与えられて
いるため、前記インデックス情報１６に−は１４ビツト
で与えられることとなる。また、第２６図（２）に示す
よう、ＸＹＲＡＭ１６は、１６ワ一ド単位で各ポリゴン
情報を書き込むため、インデックスの下位４ビツトは常
に０となる。

このように、本実施例ではソーティングＲＡＭメモリエ
リアの偶数アドレスにＺ座標、奇数アドレスにインデッ
クス情報が書き込まれ、しかも、最後のＺ座標またはイ
ンデックスが書き込まれたアドレスには、その終了エリ
ア（１５ビツト）に「終了フラグ」が書き込まれる。

そして、ポリゴン表示回路２２は、偶数アドレスまたは
奇数アドレスのいずれかに書き込まれた「終了フラグ」
を検出することにより、当該メモリエリアに書き込まれ
た最終のＺ軸情報を判別し次の動作に移ることができる
。こようにすることにより、当該メモリエリアの空領域
のデータを読み出すことにより発生する処理時間の無駄
を低減し、そのソーティング処理をより高速に行うこと
を可能としている。

また、ポリゴン表示回路２２は、通常ソーティングＲＡ
Ｍ１６のメモリエリアから、各多角形のポリゴン情報を
ｐｒ、　ｏ、Ｐｒ、　１、−Ｐｒ、　　（ｎ−１＞の順
で呼び出すが、これ以外にも、この逆の順序でポリゴン
情報の読出しを行う可能性もある。この点を考慮し実施
例のメモリエリアは「総ポリゴン数」を最終アドレスに
書き込むよう形成されている。

従って、ｎ＝１０２３の場合には、第２８図の右側の点
線で引き出した位置に示すように、総ポリゴン数と終了
フラグが同じワード内に同居して書き込まれることとな
る。

［発明の効果］ 以上説明したように、本発明によれば、多数のデータを
その基準軸情報に基づき高速でソーティングすることが
できる簡単かつ安価なソーティング回路を提供できると
いう効果があり、ソーティング処理を必要とする各種用
途に幅広く用いることが可能となる。

【図面の簡単な説明】

第１図は本発明に係るソーティング回路の好適な第１実
施例を示すブロック図、 第２図および第３図は第１図に示す回路を用いて行われ
るソーティング処理のフローチャート図、第４図〜第７
図は４桁の２進数からなる一組の基準軸情報をソーティ
ングする場合の一例を示す説明図、 第８図〜第１０図は３桁の３進数からなる一組の基準軸
情報をソーティングする場合の説明図、第１１図は本発
明の好適な第２実施例を示すブロック図、 第１２図は本発明の好適な第３実施例を示すブロック図
、 第１３図〜第１５図は前記第１２図に示す実施例の動作
を示すフローチャート図、 第１６図は本発明に係るソーティング回路を三次元情報
演算回路に適用した場合の実施例を示すブロック図、 第１７図は第１６図に示す回路を用いて表示される画像
の三次元概念図、 第１８図は第１６図に示すポリゴン情報発生回路の具体
的な構成を示すブロック図、 第１９図は第１６図に示すソーティング回路１０の回路
構成を示すブロック図、 第２０図は第１９図に示すソーティング回路をマルチボ
ート化するためのサイクルスチールを表すタイミングチ
ャート図、 第２１図および第２２図はソーティングＲＡＭおよびＸ
ＹＲＡＭのエリア切替え動作を示す説明図、 第２３図および第２４図はポリゴン情報発生回路にデー
タ書込み遅れが発生した場合におけるソーティングＲＡ
ＭおよびＸＹＲＡＭのエリア切替え動作の説明図、 第２５図は実施例に用いられるＸＹＲＡＭおよびソーテ
ィングＲＡＭのメモリマツプ概念図、第２６図は実施例
に用いられるＸＹＲＡＭのメモリマツプの詳細な説明図
、 第２７図および第２８図は実施例に用いられるソーティ
ングＲＡＭのメモリマツプの詳細な説明図、 第２９図および第３０図は第１図に示す装置を用いて浮
動少数点データをソーティングする場合の説明図である
。 １０　　　・・・　ソーティング回路 １２　　　・・・　ソーティングメモリ１２−１．１２
−２．１２−３．１２−４・・・　メモリエリア １４　　　・・・　ソータ− １６　　　・・・　情報メモリ ２０　　　・・・　ポリゴン情報発生回路２２　　　・
・・　ポリゴン表示回路 代理人　弁理士　　布　施　行　夫 （外１名） 第２図 第３図 第４図 ｍｍ３　ｍｍ２　ｍｍｌ　ｍ＝０ 常　　ｒ　　Ｒｋ 第６図 ｍｍ３　ｍ−２ｍ−１ｍ冒Ｏ ｏ　　　　　　　　　　　　　　　　　　　Ｏ第７図 オフ　　〜Ｉ　　國 ｍ＝３　ｍ＝２　ｍｍｌ　　ｍ＝０ ｍ−３ｍ−２ｍ−１ｍ−０ ｏ　　　　　　　　　　　　　　　　　　Ｏｌと−Ｉ　
　　　　　　　　　　　　　　Ｉに−と第２２図 第２３図 第２４図 第２５図 第２８図 第２９図 第３０図

Claims (4)

【特許請求の範囲】
1. （１）複数のデータを所定の基準軸情報に基づきソーテ
   ィングする回路であって、 基準軸情報書込み用の少なくとも２個のメモリエリアを
   有するソーティングメモリと、 一方のメモリエリアに格納された一組の基準軸情報の所
   定のサーチ桁の値をサーチし、サーチした値に基づきこ
   の一組の基準軸情報を分類しながら昇順または降順に他
   方のメモリエリアに写し換えるという転送処理を、基準
   軸情報の最下位の桁から最上位の桁に向けサーチ桁を１
   桁ずつシフトしながら両メモリエリアの間で繰り返し行
   うソーターと、 を含み、基準軸情報に基づきデータをソーティングする
   ことを特徴とするソーティング回路。
2. （２）基準軸情報とその組合せ情報から成る複数のデー
   タを所定の基準軸情報に基づきソーティングする回路で
   あって、 各データの組合せ情報が書込まれる情報メモリと、 各データの基準軸情報と、組合せ情報書込アドレスとが
   対を成して書込まれる少なくとも２個のメモリエリアを
   有するソーティングメモリと、一方のメモリエリアに格
   納された一組の基準軸情報の所定のサーチ桁の値をサー
   チし、この一組の基準軸情報およびこれと対を成す組合
   せ情報書込アドレスをサーチした値に基づき分類しなが
   ら昇順または降順に他方のメモリエリアに写し換えると
   いう転送処理を、基準軸情報の最下位の桁から最上位の
   桁に向けサーチ桁を１桁ずつシフトしながら両メモリエ
   リアの間で繰り返し行うソーターと、 を含み、ソーティングメモリから基準軸情報を読み出す
   際、これと対をなす組合せ情報書込アドレスに基づき情
   報メモリから組み合わせ情報を読み出すことにより、デ
   ータを基準軸情報に基づきソーティングすることを特徴
   とするソーティング回路。
3. （３）画像合成装置に適用される特許請求の範囲（２）
   記載の回路において、 前記情報メモリは、データ書込用、データ保持用、デー
   タ出力用として、画面を更新する毎に切り替え使用され
   る少なくとも３個のメモリエリアを有し、 前記ソーティングメモリは、データ書込用、データソー
   ティング用、データ出力用として用いられる少なくとも
   ４個のメモリエリアを有し、その少なくとも２個のメモ
   リエリアはデータ書込用、データソーティング用として
   画面を更新する毎に切り替え使用され、残りの少なくと
   も２個のメモリエリアはデータソーティング用、データ
   出力用として画面を更新する毎に切り替え使用され、演
   算される画像情報をソーティング出力することを特徴と
   するソーティング回路。
4. （４）特許請求の範囲（２）、（３）のいずれかに記載
   の回路において、 前記基準軸情報は２進数データから構成されて成ること
   を特徴とするソーティング回路。