JPH05224885A - ソーティング装置 - Google Patents

Abstract

(57)【要約】 【目的】 この発明は、ワーキングメモリを使用せずに
高速なソート処理が行えるソーティング装置を提供する
ことをその目的とする。 【構成】 この発明のソーティング装置は、処理する数
のソートデータを格納し、そのデータを一括してパラレ
ルに出力する記憶手段２１と、この出力されたデータと
所定データとを比較する比較器を処理する数だけ備えた
比較手段２３と、処理する数のソートデータから比較す
る所定のデータを１つ選択する選択手段２２と、比較手
段２２の各比較器の比較結果と夫々カウントする加算手
段２４と、加算手段２４からのデータに基づきその比較
するデータの順番を求める手段２６と、を備えてなり、
複数個のデータから順次比較するデータを選択し、それ
以外のデータとパラレルに比較することにより、順次デ
ータの順番を求める。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、ソーティング装置に
かかり、特に複数の基準値データに基づきデータをソー
ティングする装置に関する。

【０００２】

【従来の技術】画像処理装置は、外部から供給される画
像情報に基づき、ＣＲＴ表示用の各種画像信号を合成画
像を出力するものであり、単に２次元的な平面画像ばか
りでなく、立体的な合成出力することから、例えば３次
元画像用ビデオゲーム、コンピュータグラフィックス、
ＣＡＤ装置のディスプレイ及びその他の用途に幅広く用
いられている。

【０００３】ところで、画像処理装置を用いて奥行きを
持った３次元画像リアルタイムで合成する場合には、各
ポリゴンの３次元データを画像奥行き方向の座標値、即
ちＺ値データに基づき、１／６０秒間に処理対象のポリ
ゴンに対して高速でソーティングする必要がある。

【０００４】このため、複数の３次元データを所定のＺ
軸データに基づき、高速ソーティングできる装置の開発
が望まれている。しかし、従来はワーキングメモリにポ
リゴンのＺ値に対応する番地にそのＺ値のポリゴンの数
をカウントしていき、全てのポリゴンの処理を終了した
ときにワーキングメモリの小さい方からその値を調べ、
０でなければそのアドレス（Ｚ値）とそのデータ（その
Ｚ値の数）よりデータを加算していくことにより、夫々
のＺ値の順番を取っていた。

【０００５】

【発明が解決しようとする課題】しかしながら、前述の
ソーティング装置では、Ｚ値のデータが大きくなった時
にそれに対応する大きなワーキングメモリを必要とする
ため、ソーティング装置の個数が大きくなるという問題
があった。

【０００６】この発明は、従来のこのような問題点に鑑
みなされたものにして、ワーキングメモリを使用せずに
高速なソート処理が行えるソーティング装置を提供する
ことをその目的とする。

【０００７】

【課題を解決するための手段】この発明のソーティング
装置は、処理する数のソートデータを格納し、そのデー
タを一括してパラレルに出力する記憶手段と、この出力
されたデータと所定データとを比較する比較器を処理す
る数だけ備えた比較手段と、処理する数のソートデータ
から比較する所定のデータを１つ選択する選択手段と、
上記比較手段の各比較器の比較結果と夫々カウントする
加算手段と、上記加算手段からのデータに基づきその比
較結果を同時にカウントすることにより、その比較する
データの順番を求める手段と、を含み複数個のデータか
ら順次比較するデータを選択し、それ以外のデータとパ
ラレルに比較することにより、順次データの順番を求め
ることを特徴とする。

【０００８】更に、この発明は、初期値としてアドレス
と同じデータを持ち、得られらたデータの順番をアドレ
スとして出力されたデータをインクリメントし、同じア
ドレスに書き込みをする手段とを備え、同じソートデー
タ値にも処理された順に全てのデータ数からなる一連の
順番を付けるとよい。

【０００９】

【作用】この発明は、記憶手段にソートを必要とする全
てのデータを読み込み、その中から１つずつ選択してい
き、その選択されたデータを選択されていない全てのデ
ータに同時に比較し、選択されたデータのほうが大きい
時または小さい時に比較手段よりキャリーが出力され、
その全てのデータのキャリーをカウントすることにより
その選択されたデータの順番が求まり、その結果をその
アドレスに対応する番地にデータの順番を書き込む。そ
して全てのデータを選択し終わった時にソート処理が終
了となる。

【００１０】従って選択されたデータとそれ以外のデー
タとの比較は大／小関係のみでよいためデータの大きさ
によるハードウエアの大きさはあまり差はなくなる。従
って、処理は高速で且つ同じ装置でのデータの大きさに
よるスピードとはない。

【００１１】また、順序をカウントするメモリを使用す
ることにより、同じ数値データに対しても入力された時
による順番を付けることができる。

【００１２】

【実施例】以下、この発明の実施例を図面に基づいて説
明する。

【００１３】図１はこの発明のソーティング装置の全体
構成を示すブロック図、図２はソーティング装置の要部
の構成を示すブロック図である。１はＺ値を格納するＺ
値メモリ（ＲＡＭ）であり、ソートされるデータを格納
する。そして格納されたデータは一括してパラレルにソ
ーティング装置２に出力される。ソーティング装置２
は、記憶手段、比較手段及び加算手段とを備える。記憶
手段がソートを必要とする全てのデータを格納する。そ
して、比較手段は記憶手段からパラレルに出力されたデ
ータと所定されたデータとを比較する比較器をそのデー
タの数だけ有しする。各比較器はデータの大又は小の関
係によりキャリーを出力し、そのキャリーを加算手段で
カウントする。そしてその加算した値に基づきそのデー
タを順序リストメモリ３へ書き込む。この順序リストメ
モリ（ＲＡＭ）はアドレスに対応するデータの順番を格
納するものである。

【００１４】Ｚ値ＲＡＭ１の構成及び順序リストＲＡＭ
３の構成を図３に示す。図３に示すように夫々のメモリ
のデータ構造は夫々対応するアドレスがポリゴンの番号
と等しく、Ｚ値ＲＡＭ１ではＺ値そのものの値を持ち、
順序リストＲＡＭ３ではポリゴンのＺ値に対応する順番
を格納するものである。

【００１５】図２に従ってこの発明の構成をさらに説明
すると、Ｚ値ＲＡＭ１よりパラレルに出力されたデータ
は記憶手段２１に格納される。この記憶手段２１は、ソ
ートされるデータ数だけのレジスタを有するレジスタ群
で構成され、そのレジスタ群よりデータがパラレルに同
時にマルチプレクサ２２へ送られ、マルチプレクサ２２
を介して比較手段２３の比較器の一方の入力に夫々与え
られる。比較器の他方入力には処理する数のソートデー
タから選択された比較する所定データがマルチプレクサ
２２を介して与えられる。即ちカウンタ２５の示す記憶
手段２１のレジスタの値を全ての比較器の一方の入力へ
入力し、カウンタ２５の示していない全てのレジスタの
値を比較器の他方の入力へ入力する。

【００１６】そして、各比較器より出力されるキャリー
の値が加算手段２４へ与えられ加算手段器２４はそのキ
ャリーを全て加算し、そのデータを順序カウント用処理
装置２６へ送る。順序カウント用処理装置２６の内部に
は順序カウント用ＲＡＭが備えられ、このＲＡＭがその
キャリー値を加算した値によりアクセスされ、そのデー
タをカウンタの示す順序リストＲＡＭ３へ書き込む。こ
の動作を繰り返すことにより、Ｚ値のデータの昇順若し
くは降順に従ったデータが順序リストＲＡＭの値として
書き込まれることになる。

【００１７】図４は、１６個のデータに対するこの発明
による処理を行った結果を示す。Ｚ値ＲＡＭに書き込ま
れた夫々のＺ値データに基づき順序リストＲＡＭに示す
ようにその順序値が書き込まれている。

【００１８】図５ないし図８を参照してこの発明を更に
説明する。図５は、この発明のソーティング装置の具体
的な実施例を示すブロック図である。図６は、この図５
に示した具体例に基づき昇順にデータをソートする場合
の動作を説明するフローチャートである。図７は降順に
データをソートする場合の動作を示すフローチャートで
ある。

【００１９】図５に示すように、記憶手段２１はレジス
タ２１−１からレジスタ２１−ｎのを備える。このレジ
スタは、ソートを必要とする全てのデータの数に対応す
る個数を持つ。即ち、この実施例では、レジスタにｎ個
即ちデータ数ｎ個のソーティングを行う装置である。そ
して、レジスタ２１−１にはＺ値ＲＡＭの０番地の値が
格納され、以下レジスタ２１−２から２１−ｎまでに同
様にＺ値ＲＡＭ１のデータが格納される。即ちカウンタ
２５の示すＺ値ＲＡＭ１のデータを読み出し、そのカウ
ンタ２５が示すレジスタ２１−１〜２１−ｎへデータを
夫々格納していくわけである。即ち、カウンタ２５が指
示する値をデコーダ２７よりデコーダし、夫々対応する
レジスタ２１−１〜２１−ｎにデータが書き込まれる。
そして、各レジスタに書き込まれたデータは、このレジ
スタ２１−１〜２１−ｎからマルチプレクサ２８又は２
９を介して夫々対応する比較器２２にデータが与えられ
る。マルチプレクサ２８又は２９はデータを昇順又は降
順にソーティングする場合に夫々コントローラ３０によ
り制御されるものである。即ち、データを昇順にソーテ
ィングする場合には、ソーティング対象となるデータを
比較器２２のＡ入力へ入力するためマルチプレクサ２８
によりそのデータが選択されそしてそれ以外の全てのデ
ータはマルチプレクサ２９を介して比較器２２のＢ入力
へ与えられるものである。

【００２０】逆に、データを降順にソーティングする場
合には、ソーティング対象となるデータを比較器のＢ入
力するために、マルチプレクス２９を介してそのデータ
が選択されて書き込まれ、そして、それ以外の全てのデ
ータはマルチプレクサ２８を介して比較器のＡ入力に与
えられる。

【００２１】各比較器２２からは、昇順の場合にはその
データが小さい場合にキャリーが発生し、降順の場合に
は大きい場合にキャリーが発生する。そして、各比較器
２２からの出力は、加算器２３の夫々のＢ入力に与えら
れそして加算器のＡ入力には夫々前段の加算器２３の出
力が与えられる。即ち、比較器２２−１のキャリーは加
算器２３−１のＢ入力に与えられ、そして比較器２２−
２の出力は加算器２３のＢ入力へ、そして加算器２３−
２のＡ入力には加算器２３−１の出力が与えられる。全
ての加算器２３−１〜２３−ｎのデータは加算され、そ
の出力がマルチプレクサ２６ａを介して、順序カウント
ＲＡＭ２６ｄへ与えられる。

【００２２】そして、出力されるキャーリは、加算手段
２３にて全て加算され、その値により順序カウントＲＡ
Ｍ２６ｄがアクセスされ、そのデータをカウンタ２５の
示す順序リストＲＡＭ３へ書き込む。順序カウントＲＡ
Ｍ２６ｄの出力データがインクリメンタ２６ｃにて一つ
インクリメントされ、同じアドレスの順序カウントＲＡ
Ｍ２６ｄへ書き込まれる。この動作を全てのデータに行
って、データが昇順又は降順にソーティングされた結果
が順序リストＲＡＭ３へ書き込まれることになる。

【００２３】この動作を更に図６のフローチャートに従
って説明する。ステップＳ１において、カウンタ２５の
カウンタをリセットし、ステップＳ２に進む。ステップ
Ｓ２においては、カウンタ２５に示すＺ値ＲＡＭ１のデ
ータを読み出してカウンタ２５の示すレジスタ２１−１
〜２１−ｎへそのデータをセットする。そして、ステッ
プＳ３においては、カウンタ２５の示す順序カウントＲ
ＡＭ２６ｄへのカウンタの値を設定する。

【００２４】ステップＳ４においては、カウンタ値が１
２８を示したか否か、即ちこの実施例では１２８個のデ
ータをソートする場合を仮定しているので、その全ての
データが書き込まれたか否かを判断し、カウンタが１２
８に達していない場合には、ステップＳ５でカウンタ２
５の値を１つカウントアップし、ステップＳ２に戻り前
述の動作を繰り返す。そして、カウンタの値が１２８に
達すると、ステップＳ６へ進みステップＳ６でカウント
２５の値をリセットする。

【００２５】続いて、ステップＳ７にて、カウンタ２５
のレジスタの値を全ての比較器２１のＡ入力へ入力し、
ステップＳ７へ進む。

【００２６】ステップＳ８においては、カウンタ２５で
示していない全てのレジスタの値を比較器のＢ入力へ入
力する。そして、ステップＳ９で全ての比較器より出力
されるキャリー値を全て加算し、その値により、順序カ
ウントＲＡＭ２６ｄをアクセスし、そのデータをカウン
タの示す順序リストＲＡＭ２６ｄへ書き込む。

【００２７】然る後、ステップＳ１０へ進み、ステップ
Ｓ１０において、順序カウントＲＡＭ２６ｄのデータを
加算器２６ｃにて１つインクリメントして同じアドレス
の順序カウントＲＡＭ２６ｄへ書き込む。そして、カウ
ンタ２５の値が１２８に達したか否か、ステップＳ１１
で判断され、１２８に達しいてない即ち、全てのデータ
が終わっていない場合にはステップＳ１２に進み１つカ
ウントアップして、ステップＳ７へ戻り、前述の動作を
繰り返す。カウント値１２８になると全てのデータのソ
ーティングが終了して全ての動作を終了する。

【００２８】この図６はデータを昇順にソーティングす
る場合を示しているが、図７はデータを降順にソーティ
ングする場合を示す。図６と図７の相違はステップＳ
７’、ステップＳ８’が相違する。即ち、比較器への入
力が相違するのみで、その他は全て同一である即ち降順
にデータをソーティングする場合にはステップＳ７’で
カウンタ２５の示すレジスタの値をこの場合にはＢ入力
へ入力する。そしてステップＳ８’で示すようにカウン
タの示していない全てのレジスタの値を比較器のＡ入力
へ入力されるのである。そのほかの動作は全て昇順及び
降順いついては全く同一である。

【００２９】以上の動作をさらに図８に従って説明す
る。図８は５つのデータを昇順にソーティングする場合
を示している。

【００３０】まず、図８のＮｏ．１で示すように、順序
カウントＲＡＭ２６ｄが初期値に設定される。即ち、ア
ドレス０、１、２、３、４に対してデータが０、１、
２、３、４となるように初期化される。そしてＺ値デー
タには、この図８で示すようにアドレス０にデータ１０
０が、アドレス１にデータ５０が、アドレス２にデータ
１００が、アドレス３にデータ１００が、アドレス４に
データ２００が書き込まれているものとする。そして、
アドレス０を示すカウンタ値が設定され、アドレス０の
Ｚ値データが全ての比較器のＡ入力に比較器のＢ入力に
は他のデータが全て入力される。その結果、加算器より
１つキャリーがでるので、順序リストＲＡＭ３にアドレ
ス０の部分にデータ１を書き込む。

【００３１】続いて、そして順序カウントＲＡＭ２６ｄ
のデータ１を１つインクリメントし、それと同じアドレ
スの順序カウントＲＡＭ２６ｄへインクリメントした値
を書く。即ち、Ｎｏ．２に示すように順序カウントＲＡ
Ｍはアドレス０に対して０、アドレス１に対して１つイ
ンクリメントされた２、アドレス２は２、アドレス３は
３、アドレス４は４と書き込まれている。

【００３２】続いて、Ｚ値データのアドエス１のデータ
を比較器Ａの入力にする。そして、この場合、比較器の
Ｂ入力には他のデータが全て入力される。キャリーはで
ないので加算値は０である。そのデータが順序リストＲ
ＡＭ３のアドレス１に０として書き込まれる。そして、
アドレスの０の値を１つインクリメントされ、順序カウ
ントＲＡＭ２３ｄがＮｏ．３に示すようにアドレス０の
ところにデータ１が書き込まれる。

【００３３】次いで、Ｚ値データのアドレス２の出力が
呼び出され、そのデータを読みだすとそのキャリーが１
出力されるので、そのアドレス順序カウントＲＡＭ２６
ｄに書き込まれているデータが順序リストＲＡＭ３のア
ドレスのところに書き込まれる。そしてこのデータ２を
１つインクリメントした結果が順序カウントＲＡＭ２６
ｄのアドレス１の部分に書き込まれる。即ちＮｏ．４に
示すようにアドレス１のところにデータ３が書き込まれ
る。

【００３４】続いて、Ｚ値ＲＡＭ１のアドレス３に相当
するデータが呼び出され、その結果又キャリーが１出る
ので、その順序カウントＲＡＭ２６のアドレス１に書き
込まれているデータ３が順序リストＲＡＭのアドレス３
に書き込まれる。そしてそのデータを１つカウントアッ
プし、そのデータをアドレス１に書き込む。即ちＮｏ．
５に示すように、アドレス１にはデータ４が書き込まれ
るそしてＺ値データのアドレス４の示すデータ２００が
読み出され、この場合キャリーが４つ出て、アドレスが
４であるので、そのままその順序リストＲＡＭに４が書
き込まれる。そして順序リストＲＡＭ２６ｄのアドレス
毎にアドレス０、１から順次読み出すとそのデータが昇
順にソーティングされた結果が読み出されることにな
る。

【００３５】

【発明の効果】以上説明したように、この発明によれば
選択されたデータとそれ以外のデータとの比較は大／小
関係でよいためデータの大きさによるハードウエアの大
きさはあまり差はなく、処理は高速で且つ同じ装置での
データの大きさにスピード差はなく極めて良好なソーテ
ィング装置を提供することができる。また、順序カウン
トＲＡＭを使用することにより同じ数値データにも入力
される順序により順番をつけることができる。

【図面の簡単な説明】

【図１】この発明のソーティング装置の全体構成を示す
ブロック図である。

【図２】ソーティング装置の要部の構成を示すブロック
図である。

【図３】Ｚ値ＲＡＭ１の構成及び順序リストＲＡＭ３の
構成を示す模式図である。

【図４】１６個のデータに対するこの発明による処理を
行った結果を示す模式図である。

【図５】この発明のソーティング装置の具体的な実施例
を示すブロック図である。

【図６】図５に示した具体例に基づき昇順にデータをソ
ートする場合の動作を説明するフローチャートである。

【図７】図５に示した具体例に基づき降順にデータをソ
ートする場合の動作を示すフローチャートである。

【図８】５つのデータを昇順にソーティングする場合を
示す模式図である。

【符号の説明】

２１ 記憶手段 ２２ マルチプレクサ ２３ 比較手段 ２４ 加算手段

Claims (2)

【特許請求の範囲】
1. 【請求項１】 処理する数のソートデータを格納し、そ
   のデータを一括してパラレルに出力する記憶手段と、こ
   の出力されたデータと所定データとを比較する比較器を
   処理する数だけ備えた比較手段と、処理する数のソート
   データから比較する所定のデータを１つ選択する選択手
   段と、上記比較手段の各比較器の比較結果を夫々カウン
   トする加算手段と、上記加算手段からのデータに基づき
   その比較結果を同時にカウントすることにより、その比
   較するデータの順番を求める手段と、を含み、複数個の
   データから順次比較するデータを選択し、それ以外のデ
   ータとパラレルに比較することにより、順次データの順
   番を求めることを特徴とするソーティング装置。
2. 【請求項２】 初期値としてアドレスと同じデータを持
   ち、得られらたデータの順番をアドレスとして出力され
   たデータをインクリメントし、同じメモリのアドレスに
   書き込みをする手段とを備え、同じソートデータ値にも
   処理された順に全てのデータ数からなる一連の順番を付
   けるをことを特徴とする請求項１に記載のソーティング
   装置。