JPH06110655A

JPH06110655A - ソート処理装置

Info

Publication number: JPH06110655A
Application number: JP4285470A
Authority: JP
Inventors: Yasuhiro Izawa; 康浩井澤; Tatsuya Fujii; 達也藤井; Naohito Shiraishi; 尚人白石; Masanobu Fukushima; 正展福島; Tatsuya Nakajima; 達也中島
Original assignee: Ricoh Co Ltd
Current assignee: Ricoh Co Ltd
Priority date: 1992-09-29
Filing date: 1992-09-29
Publication date: 1994-04-22
Also published as: EP0590933A3; US5459822A; DE69320744T2; EP0590933B1; EP0590933A2; DE69320744D1

Abstract

(57)【要約】【目的】この発明は、ソーティング処理が終わるまで
にフレーム遅れが生じず、又、ソーティング装置の前段
の幾何変換後の情報を蓄えるためのＲＡＭが不要になる
ようにしたソート処理装置を設けることを目的とする。【構成】複数のポリゴン中心情報を有するメモリと、
各ポリゴン中心座標をオブジェクト座標から絶対座標に
座標変換するポジションセット部と、ポジションセット
されたオブジェクトを視野変換する視野変換回路とを有
するポリゴン優先順序生成回路１、及び、視野変換した
結果をＺ軸情報に基づいてソーティングするＺソート回
路２を備える構成とする。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ソート処理装置に関す
る。

【０００２】

【従来の技術】例えば、３次元グラフィックス、ゲーム
機器、ワークステーション、ワードプロセッサ、パーソ
ナルコンピュータ等において３次元画像処理を行う場
合、一般に、隠面処理として画面の奥行き方向の軸（Ｚ
軸）を基準軸としてソーティングを行うＺソート法が採
用されている。

【０００３】Ｚソート法を３次元画像処理に適用する場
合には、例えば特開平１−１０３７８５号公報に開示し
ているようにポリゴン情報発生回路と、ソーティング回
路と、ポリゴン表示回路とが用いられ、立体の２次元画
像、すなわち、疑似３次元画像をＣＲＴ上に合成表示す
るように構成される。

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

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

【０００６】そして、これらポリゴンの各端点のＸ，Ｙ
座標、中心位置のＺ座標その他の情報に付いての幾何変
換をポリゴン情報発生回路で行った後、ソーティング装
置においてＺソート法によってソーティングを行ってい
る。

【０００７】

【発明が解決しようとする課題】この従来のＺソート法
においては、ポリゴンの形状が複雑な場合やポリゴンの
数が多い場合には、幾何変換すべきポリゴンの頂点の数
が多くなり、その結果、ソーティングする前にポリゴン
情報発生回路で幾何変換処理すべきポリゴン情報量が膨
大なものとなることがあり、このため、ソート処理回路
の１フレームの情報処理に要する時間（以下、１フレー
ム時間という。）よりもポリゴン情報発生回路での１フ
レーム分の情報の幾何変換処理時間が長くなり、データ
の一部分がソート処理回路の次のフレームの情報処理時
に遅れてソート処理される、いわゆるフレーム遅れが生
じることがある。

【０００８】このようなフレーム遅れを防止するために
は、幾何変換装置とソーティング装置との間に１フレー
ム分の幾何変換結果を所定のタイミングでソーティング
装置に入力するため、バッファＲＡＭが必要になる。

【０００９】本発明は、上記の事情を鑑みてなされたも
のであり、ソーティング処理が終わるまでにフレーム遅
れが生じず、又、ソーティング装置の前段の幾何変換後
の情報を蓄えるためのＲＡＭが不要になるようにしたソ
ート処理装置を設けることを目的とする。

【００１０】

【課題を解決するための手段】本発明は、上記の目的を
達成するため、複数のポリゴン中心情報を有するメモリ
と、各ポリゴン中心情報のオブジェクト座標を絶対座標
に座標変換するポジションセット部と、ポジションセッ
トされたオブジェクトを視野変換する視野変換回路とを
備えるポリゴン優先順序生成回路、及び視野変換した結
果を基準軸情報に基づいてソーティングするソーティン
グ回路を備えることを特徴とするソート処理装置であ
る。

【００１１】

【作用】ポリゴン優先順序生成回路は、ポリゴン中心情
報について幾何変換を行う幾何変換装置であり、ポリゴ
ン中心座標のみをポジションセット部によってオブジェ
クト座標から絶対座標（ワールド座標）に座標変換し、
視野変換部でＸ，Ｙ，Ｚの視野変換を行い、その結果を
ソート回路に転送する。

【００１２】したがって、ポリゴン優先順序生成回路で
幾何変換処理される情報数はポリゴン数と同数であり、
ソーティング回路の前の幾何変換処理に要する時間を１
フレーム時間内に短縮することができる。

【００１３】ソート回路は、ポリゴン優先順序生成回路
で処理された結果を入力し、アルゴリズムとして分布カ
ウント法（応用ビンソート）を用いてソーティングを行
う。すなわち、ポリゴン優先順序生成回路で視野変換さ
れたＺ値に対応したワークメモリの分布カウントメモリ
にポリゴン番号を書き込み、Ｚ値が同じポリゴン番号が
複数個ある場合にはチェーンメモリにチェーンさせて書
き込む。ポリゴン優先順序生成回路の処理及びこの書き
込みが終わった後、分布メモリのアドレスの小さいも
の、すなわち、Ｚ値の小さいものから順に読み出し、ポ
リゴン表示回路へ転送する。また、同じＺ値に複数のポ
リゴン番号がある場合には、チェーンメモリを読み出し
てポリゴン表示回路へ転送する。

【００１４】

【実施例】本発明の一実施例に係るソート処理装置を図
１ないし図５に基づいて具体的に説明すれば、以下の通
りである。

【００１５】図１のブロック図に示すように、このソー
ト処理装置は１つの半導体チップＴ内に集積されたポリ
ゴン優先順序生成回路１と、Ｚソート回路２とを備え、
例えば外部に設けられるポリゴン情報記録媒体から与え
られるポリゴン中心情報をポリゴン優先順序生成回路１
に入力し、ポリゴン中心位置について幾何変換処理を行
い、この幾何変換結果に基づいてＺソート回路２でＺ軸
を基準軸として分布カウント法（応用ビンソート法）に
よってソーティングを行い、ソーティングされたポリゴ
ン中心情報をポリゴン表示回路３に出力するようにして
いる。

【００１６】上記ポリゴン優先順序生成回路１は、図２
の回路ブロック図に示すように、与えられたポリゴン中
心情報を記憶するポリゴン中心メモリ１１、アドレス生
成部１２、メモリインターフェース（Ｉ／Ｆ）１３、ポ
ジションセット部１４、Ｙ回転部１５、Ｘ回転部１６、
Ｚ回転部１７及びこれらの動作を制御するコントローラ
１８を備えている。

【００１７】外部から与えられた単数または複数のポリ
ゴン中心情報は、アドレス生成部１２が生成したアドレ
スを附してポリゴン中心メモリ１１に記憶され、メモリ
インターフェース（Ｉ／Ｆ）１３を介して順次読み出さ
れ、ポリゴン中心座標をポジションセット部１４によっ
てオブジェクト座標から絶対座標（ワールド座標）に座
標変換される。この後、Ｙ回転部１５、Ｘ回転部１６、
Ｚ回転部１７によってＹ，Ｘ，Ｚの各軸の回りに回転す
る所要の幾何変換（視野変換）を行い、Ｚソート回路２
に視野変換されたポリゴン中心情報を出力する。

【００１８】この実施例では、説明を簡単にするため、
視野変換として回転のみを実施しているが、平行移動、
透視投影などの各種変換を施すことは何等妨げない。

【００１９】上記Ｚソート回路２は、図２のブロック図
に示すように、アドレス／データ変換部２１、メモリイ
ンターフェース（Ｉ／Ｆ）２２、ポリゴンＮＯ生成部２
３、ＷＯＲＫメモリ２４及びフラグ処理部２５を備え、
ポリゴン優先順序生成回路１が出力した視野変換された
ポリゴン中心情報をアドレス／データ変換部２１に入力
し、データであるＺ値を例えば０〜Ｚｎのアドレスに変
換した後、ポリゴンＮＯ生成部２３が生成するポリゴン
ＮＯとこのアドレスとをメモリインターフェース（Ｉ／
Ｆ）２２で１対１で対応させてＷＯＲＫメモリ２４に入
力する。

【００２０】ＷＯＲＫメモリ２４は、図４のメモリーパ
ターン図に示すように、分布カウントメモリ２６とチェ
ーンメモリ２７とを備え、分布カウントメモリ２６はス
タートＮＯエリア２６ａと、エンドＮＯエリア２６ｂと
を有する。

【００２１】メモリインターフェースＩ／Ｆ２２から分
布カウントメモリ２６に入力されたデータは付されたア
ドレスに対応するスタートＮＯエリア２６ａ及びエンド
ＮＯエリア２６ｂの領域に逐次格納される。

【００２２】分布カウントメモリ２６のアドレスは各ポ
リゴン中心情報のＺ値であるので、分布カウントメモリ
２６の同じアドレスに複数のデータ（ポリゴンＮＯ）が
入力されることがある。この場合、スタートＮＯエリア
２６ａには最初に書き込まれたデータが保持されるよう
にしてあるが、エンドＮＯエリア２６ｂのデータは新た
に入力されたデータに書き替えられる。

【００２３】チェーンメモリ２７には、各ポリゴンＮＯ
に対応するアドレスが付されたメモリエリアが設けら
れ、エンドＮＯエリア２６ｂのデータが更新される時
に、更新前のエンドＮＯエリア２６ｂのデータをアドレ
スにして、更新後のエンドＮＯエリア２６ｂのデータ、
すなわち、ポリゴンＮＯが書き込まれる。

【００２４】すべてのポリゴンＮＯの分布カウントメモ
リ２６あるいはチェーンメモリ２７への書き込みが終了
すると、分布カウントメモリ２６のスタートＮＯエリア
２６ａのデータとエンドＮＯエリア２６ｂのデータとが
異なるアドレスの次にデータが入力されているアドレス
のスタートＮＯエリア２６ａのデータがエンドＮＯエリ
ア２６ｂのデータをアドレスとしてチェーンメモリ２７
に書き込まれる。

【００２５】このようにして、分布カウントメモリ２６
のスタートＮＯエリア２６ａとチェーンメモリ２７とを
連鎖させてデータ番号を記憶させた後、スタートＮＯエ
リア２６ａのデータ（ポリゴンＮＯ）がメモリインター
フェースＩ／Ｆ２２を介してアドレスの小さい順、すな
わち、Ｚ値の小さい順に読み出され、ポリゴン表示回路
３に出力される。又、同じアドレスに複数のポリゴンＮ
Ｏがある場合には、スタートＮＯエリア２６ａのポリゴ
ンＮＯに続いて、チェーンメモリ２７に書き込まれたポ
リゴンＮＯが書き込まれた順に読み出された後、スター
トＮＯエリア２６ａの次のデータが記入されているアド
レス以降のデータが読み出され、ポリゴン表示回路３に
出力される。

【００２６】なお、フラグ処理部２５はデータの入力さ
れていないアドレスのデータ読取など、Ｚ値を小さいも
のから読み出す場合の無駄な処理を最小限に抑えるため
に設けられている。

【００２７】また、ポリゴン情報のその他のデータにつ
いては、このポリゴン中心位置情報のソート処理に並行
して幾何変換処理することにより、ポリゴン中心情報の
幾何変換処理と同様にソート処理の間に終了することが
でき、幾何変換された他の情報をポリゴン表示回路３に
入力することができ、ポリゴン中心位置情報に対応させ
てポリゴン表示回路３によって表示出力することができ
る。

【００２８】このようにして、ポリゴン中心位置情報に
ついてのみ幾何変換することにより、ソーティング処理
前の幾何変換データ量を少なくすることができ、例えば
図５のタイミングチャートに示すように、幾何変換処理
時間を十分に１フレーム時間内に抑えることが可能にな
り、Ｚソート回路２の前にバッファＲＡＭを設けること
なくフレーム遅れの発生を防止できるようになった。

【００２９】また、ポリゴン優先順序生成回路１と、Ｚ
ソート回路２とを１つの半導体チップＴに集積している
ので、これらを搭載するプリント基板のピン孔、フット
プリント、導体パターン等を削減することができ、プリ
ント基板の製造コストを低減できるとともに、ポリゴン
優先順序生成回路１と、Ｚソート回路２との接続による
ノイズの発生を防止することができ、その分早いクロッ
クを用いて処理速度を一層高速化することが可能にな
る。

【００３０】図６に示す本発明の他の実施例に係るソー
ト処理装置では、２個のポリゴン優先順序生成回路１
Ａ，１Ｂと１個のＺソート回路２とが１つの半導体チッ
プに集積されている。この場合、２個のポリゴン優先順
序生成回路１Ａ，１Ｂを並行して作動させ、それぞれの
ポリゴン優先順序生成回路１Ａ，１Ｂで視野変換された
結果を交互にＺソート回路２に入力してＷＯＲＫメモリ
２４に書き込めるので、ポリゴン優先順序生成回路１
Ａ，１Ｂの処理時間及びこれと等しいＺソート回路２へ
のデータ書き込み処理（前処理）の処理時間を短縮でき
るとともに、例えば１フレーム時間内に１５０００個程
度の多量のポリゴン中心情報のソート処理が可能にな
る。

【００３１】ところで、ポリゴン数が６０００個程度に
なると、Ｚ値の幅が０〜２15程度に拡がり、メモリの領
域がかなり大きくなって、現状の技術レベルでは１つの
ポリゴン優先順序生成回路１と、Ｚソート回路２とを１
チップに集積することが困難になる。

【００３２】この問題を解決するため、本発明の又他の
実施例に係るソート処理装置は、図８に示すように、Ｚ
ソート回路２のＷＯＲＫメモリ２４の分布カウントメモ
リ２６に０〜０ＦＦのアドレスが付されたＨＩＧＨ側領
域２６Ｈと、１００〜１ＦＦのアドレスが付されたＬＯ
Ｗ側領域２６Ｈとを設け、また、チェーンメモリ２７に
００００〜１ＦＦＦのアドレスが付されたＨＩＧＨ側領
域２７Ｈと、２０００〜３ＦＦＦのアドレスが付された
ＬＯＷ側領域２７Ｌとを設け、更に、ＷＯＲＫメモリ２
４には、図９に示すように、ポリゴンＮ０をアドレスと
し、Ｚ値下位８ビットのデータを格納するＺ値ＬＯＷ側
メモリ２８が設けられる。

【００３３】この実施例では、ポリゴン優先順序生成回
路１において演算されたＺ値は上位８ビットと下位８ビ
ットとに分けられ、Ｚ値の上位８ビットがアドレス／デ
ータ変換部２１で０〜１００のアドレスに変換され、メ
モリーＩ／Ｆ２２においてこのアドレスがメモリＩ／Ｆ
２２でポリゴンＮＯ生成部２３が生成するポリゴンＮＯ
に付され、ＨＩＧＨ側領域２６ＨのスタートＮＯ領域２
６Ｈａ及びエンドＮＯ領域２６Ｈｂのアドレスが対応す
る領域にそのポリゴンＮＯが書き込まれる。

【００３４】複数のデータがＨＩＧＨ側領域２６Ｈの同
じアドレスに入力される場合には、スタートＮＯ領域２
６Ｈａのデータは最初に入力されたポリゴンＮＯに保持
され、エンドＮＯ領域２６Ｈｂのデータが後から入力さ
れたポリゴンＮＯに更新される。この場合、更新前のポ
リゴンＮＯをアドレスとして、チェーンメモリ２７のＨ
ＩＧＨ側領域２７Ｈに更新後のポリゴンＮＯが書き込ま
れる。

【００３５】すべてのポリゴンＮＯの分布カウントメモ
リ２６のＨＩＧＨ領域２６Ｈあるいはチェーンメモリ２
７のＨＩＧＨ領域への書き込みが終わると、複数のポリ
ゴンＮＯが入力されている分布カウントメモリ２６のＨ
ＩＧＨ領域２６Ｈの各アドレスについて、そのアドレス
に入力されたポリゴンＮＯがスタートＮＯ領域２６Ｈａ
及びチェーンメモリ２７のＨＩＧＨ領域から読み出さ
れ、それらのポリゴンＮＯをアドレスとしてＺ値の下位
８ビットがＺ値ＬＯＷ側メモリ２８に書き込まれ、この
下位８ビットのＺ値をアドレスとしてポリゴンＮＯが分
布カウントメモリ２６のＬＯＷ領域２６ＬのスタートＮ
Ｏ領域２６Ｌａ及びエンドＮＯ領域２６Ｌｂに書き込ま
れる。ＬＯＷ領域２６Ｌ同じアドレスに複数個のポリゴ
ンＮＯが書き込まれる場合には、スタートＮＯ領域２６
Ｌａのデータは最初に入力されたポリゴンＮＯに保持さ
れ、エンドＮＯ領域２６Ｌｂのデータが後から入力され
たポリゴンＮＯに更新される。この場合、更新前のポリ
ゴンＮＯをアドレスとして、チェーンメモリ２７のＬＯ
Ｗ側領域２７Ｌに更新後のポリゴンＮＯが書き込まれ
る。そして、分布カウントメモリ２６のＬＯＷ側領域２
６Ｌのアドレスが小さい順にポリゴンＮＯを読み出し、
アドレスが最も小さいデータで分布カウントメモリ２６
のＬＯＷ側領域２６ＬのスタートＮＯ領域２６Ｈａのデ
ータを更新するとともに、残りのデータをチェーンメモ
リ２７のＨＩＧＨ側領域２７Ｈに連鎖して記憶させる。
また、分布カウントメモリ２６のＬＯＷ側領域２６Ｌの
複数のデータが入力されたアドレスについてはそのアド
レスのデータに連鎖させてチェーンメモリ２７のＬＯＷ
側領域２７Ｌに入力された順に読み出してチェーンメモ
リ２７のＨＩＧＨ側領域２７Ｈに記憶させる。もっと
も、このＺ値の下位８ビットが関わる処理は、ＨＩＧＨ
側領域２６Ｈに複数のデータが入力されたアドレスがな
い場合には不要である。

【００３６】複数のポリゴンＮＯが入力されている分布
カウントメモリ２６のＨＩＧＨ領域２６Ｈのアドレスの
全てについてこのような処理を終えた後、分布カウント
メモリのＨＩＧＨ側領域２６ＨのスタートＮＯエリア２
６Ｈａのデータがアドレスの小さい順に読み出され、ポ
リゴン表示回路３に転送される。

【００３７】また、分布カウントメモリのＨＩＧＨ側領
域２６ＨのスタートＮＯエリア２６Ｈａの同じアドレス
に複数のデータが入力された場合には、そのアドレスの
スタートＮＯエリア２６Ｈａデータに続いて、チェーン
メモリ２７のＨＩＧＨ側領域２７Ｈに連鎖させて記憶さ
せたデータが順に読み出された後、複数のデータが入力
されたアドレスの次にデータが入力されているアドレス
のデータが読み出されて、ポリゴン表示回路３に転送さ
れる。

【００３８】このソート処理装置において、処理のタイ
ミングを制御するクロックとして１４ＭＨｚ（周期７０
ｎｓ）を用いる場合、ポリゴン優先順位処理回路１の処
理時間は２／３フレーム（１／９０ｓｅｃ）あれば十分
に処理できる。又、ソート回路２の処理は、ポリゴン優
先順位処理回路１の処理に並行して処理でき、フラグ処
理部２５に８ビット×３２ｗｏｒｄのレジスタファイル
を用いると、ＷＯＲＫメモリ２４の初期化時間も含め
て、全ポリゴン数をＮとすれば、（ＡＮ＋８７０９）ク
ロックで処理できる。全ポリゴン数Ｎ＝６０００の場合
には、処理時間は約１／６フレーム時間の（１／３フレ
ーム時間≒５．５ｍｓ）約２．３ｍｓで処理できるよう
になる。

【００３９】

【発明の効果】以上のように、本発明によれば、ポリゴ
ン中心情報に付いてのみＺソートを行うようにしている
ので、ソーティング前のデータ処理量が少なく、その処
理時間を短縮でき、フレーム遅れの発生を確実に防止で
きる。

【００４０】また、本発明において、ポリゴン優先順序
生成回路及びソーティング回路が１チップの半導体チッ
プに集積される場合には、これらの回路を搭載するプリ
ント配線板のピン孔、フットプリント及び導体パターン
の削減でき、コストダウンを図れる上、ポリゴン優先順
序生成回路とソーティング回路との接続によるノイズの
発生を防止でき、高速クロックを用いて処理の高速化を
図ることができる。

【００４１】更に、本発明において、上記ソーティング
回路がポリゴン中心情報のデータをアドレスに変換する
アドレス／データ変換回路と、ポリゴン中心情報の入力
順序を生成するアドレスＮＯ生成部と、ポリゴン中心情
報のデータから変換されたアドレスを付してポリゴン中
心情報の入力順序が書き込まれる分布カウントメモリ
と、ポリゴン中心情報のデータから変換されたアドレス
が同じデータがチェーンさせて書き込まれるチェーンメ
モリとを備え、上記分布カウントメモリが、アドレスの
上位８ビットをアドレスとするＨＩＧＨ側領域と、上位
８ビットが同じアドレスの下位８ビットをアドレスとす
るＬＯＷ側領域とを備え、分布カウントメモリの読み出
し時にＨＩＧＨ側領域のデータをアドレスの小さい順に
読み出し、ＨＩＧＨ側領域の同じアドレスに複数のデー
タが有る場合にのみＬＯＷ側領域のデータをＬＯＷ側領
域のアドレスの小さい順に読み出し、更にＬＯＷ側領域
の同じアドレスに複数のデータがある場合にのみチェー
ンメモリのデータを読み出すように構成される場合に
は、ポリゴン優先順序生成回路及びソーティング回路を
１チップの半導体チップに集積することが容易になると
ともに、処理時間を著しく短縮できる。

【図面の簡単な説明】

【図１】本発明の回路ブロック図である。

【図２】本発明のポリゴン優先順序生成回路のブロック
図である。

【図３】本発明のＺソート回路のブロック図である。

【図４】本発明のＺソート回路のＷＯＲＫメモリのパタ
ーン図である。

【図５】本発明のタイミングチャートである。

【図６】本発明の他の実施例の回路ブロック図である。

【図７】本発明の又他の実施例の分布カウントメモリ及
びチェーンメモリのパターン図である。

【図８】本発明の又他の実施例のＺ値ＬＯＷ側メモリの
パターン図である。

【符号の説明】

１ポリゴン優先順序生成回路１Ａポリゴン優先順序生成回路１Ｂポリゴン優先順序生成回路２Ｚソート回路１１ポリゴン中心メモリ１２アドレス生成部１３メモリインターフェース１４ポジションセット部１５Ｙ回転部１６Ｘ回転部１７Ｚ回転部１８コントローラ２１アドレス／データ変換部２２メモリインターフェース２３ポリゴンＮＯ生成部２４ＷＯＲＫメモリ２５フラグ処理部２６分布カウントメモリ２６ＨＨＩＧＨ側領域２６ＬＬＯＷ側領域２７チェーンメモリ２７ＨＨＩＧＨ側領域２７ＬＬＯＷ側領域２８Ｚ値ＬＯＷ側メモリＴ半導体チップ

───────────────────────────────────────────────────── フロントページの続き (72)発明者福島正展東京都大田区中馬込１丁目３番６号株式会社リコー内 (72)発明者中島達也東京都大田区中馬込１丁目３番６号株式会社リコー内

Claims

【特許請求の範囲】

【請求項１】複数のポリゴン中心情報を有するメモリ
と、各ポリゴン中心座標をオブジェクト座標から絶対座
標に座標変換するポジションセット部と、ポジションセ
ットされたオブジェクトを視野変換する視野変換回路と
を有するポリゴン優先順序生成回路、及び、視野変換し
た結果を基準軸情報に基づいてソーティングするソーテ
ィング回路を備えることを特徴とするソート処理装置。
【請求項２】上記ポリゴン優先順序生成回路及びソー
ティング回路が１チップの半導体チップに集積された請
求項１に記載のソート処理装置。
【請求項３】上記ソーティング回路がポリゴン中心情
報のデータをアドレスに変換するアドレス／データ変換
回路と、ポリゴン中心情報の入力順序を生成するアドレ
スＮＯ生成部と、ポリゴン中心情報のデータから変換さ
れたアドレスを付してポリゴン中心情報の入力順序が書
き込まれる分布カウントメモリと、ポリゴン中心情報の
データから変換されたアドレスが同じデータがチェーン
させて書き込まれるチェーンメモリとを備え、上記分布
カウントメモリが、アドレスの上位８ビットをアドレス
とするＨＩＧＨ側領域と、上位８ビットが同じアドレス
の下位８ビットをアドレスとするＬＯＷ側領域とを備
え、分布カウントメモリの読み出し時にＨＩＧＨ側領域
のデータをアドレスの小さい順に読み出し、ＨＩＧＨ側
領域の同じアドレスに複数のデータが有る場合にのみＬ
ＯＷ側領域のデータをＬＯＷ側領域のアドレスの小さい
順に読み出し、更にＬＯＷ側領域の同じアドレスに複数
のデータがある場合にのみチェーンメモリのデータを読
み出すように構成された請求項１又は２に記載のソート
処理装置。