JPH1040412A - 三次元図形描画方法及びその装置 - Google Patents

Abstract

(57)【要約】 【課題】 画素の書き込みの有無を調べる時に書き込み
の有無を示すフラグと同時に色データを読みだしてお
り、またメモリの読みだし動作と書き込み動作の切り換
え回数が多く、アクセス効率が低かった。 【解決手段】 フレームバッファに画素が配置され、異
なる領域に書き込みチェックフラグを複数個ずつ格納す
るメモリが配置され、メモリから複数個の書き込みチェ
ックフラグをまとめて読み出して（１０１）そのうちの
１つを取り出し（１０２）、書き込みチェックフラグを
調べて（１０３）対応する画素に書き込みがなされてい
ない場合は新しいデータを書き込み（１０４）、この画
素に対応する書き込みチェックフラグを書き込み済みに
変更し（１０６）、調べ終わった複数個の書き込みチェ
ックフラグをまとめてメモリに格納する（１０７）ステ
ップを備える。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、三次元図形描画方
法及びその装置に関する。

【０００２】

【従来の技術】三次元図形をコンピュータ等を用いて描
画する場合、物体を描画するときの順序として視点に近
い図形から遠い図形に向かって描画する、front to ba
ckと称される手法がある。

【０００３】このfront to back 法を用いることによ
る利点は、以下のようなものである。即ち、アニメーシ
ョンのように描画時間が予め決まっている場合には、時
間切れで全ての物体を描画しきれないことがあり得る。
このような場合にも、frontto back 法によれば、描画
しきれなかった物体は視点から遠い位置にあるため、描
画されていない図形があることが目立たない。

【０００４】逆に、このfront to back 法における不
利な点は、既に描いた手前側の図面よりも背後にある図
面はその部分を消去しなければならないという隠面消去
が必要であるという点である。

【０００５】図５に、従来の描画装置におけるフレーム
バッファ１０１の概略構成を示す。フレームバッファ１
０１の内部に、画面表示に用いるデータを格納する画素
が配列された画面表示用のメモリ領域１０２と、画面表
示に用いられないメモリ領域１０５とが存在する。ここ
で、フレームバッファ１０１の寸法は、カラム方向×ロ
ウ方向＝ＸMAX ×ＹMAX に対応するものとし、また１対
のカラムアドレスとロウアドレスとで指定される一つの
画素１０３に対応したメモリ領域の深さ、即ち容量の大
きさは、Ｄビットであるとする。

【０００６】画面に表示すべき複数の物体が、視点から
みて手前側から順に奥へとソーティングされている場
合、front to back 方式では次に描く物体は既に描か
れた物体より遠方に位置する。よって、物体を描画する
際には、フレームバッファ１０１上のこれから描画しよ
うとする画素１０３を、既に描画されたか否かを調べ
る。そして、まだ描画されていない画素１０３にのみ描
画処理をするようにすることで、隠面消去が達成され
る。

【０００７】ここで、画素１０３がそれぞれ既に描画済
みであるか否かを調べるためには、それぞれの画素１０
３毎に、一般にvalid bitと証される書き込みチェック
フラグを設ける必要がある。従来は、図６に示されるよ
うに、各画素１０３には１ビットの書き込みチェックフ
ラグ１１１と、この画素１０３に描くべき色データ１１
２とを格納していた。

【０００８】図７に、従来の描画装置における描画処理
の手順をフローチャートとして示す。先ず、ステップ５
０１としてフレームバッファ１０１上のアドレス（Ｘ，
Ｙ）で示される描画対象となっている画素１０３を読み
出す。ステップ５０２として、この画素１０３から書き
込みチェックフラグ１１１を取り出し、ステップ５０３
として当該画素１０３は書き込み済みか否かを調べる。
書き込み済みである場合はステップ５０７へ移行し、全
ての描画処理が終了したか否かを判断し、終了していた
ら描画処理を終了し、終了していない場合はステップ５
０８として次の画素へ移行する。

【０００９】ステップ５０３において、書き込み済みで
ないと判断したときは、新しい色データをこの画素に書
き込み、ステップ５０４として書き込みチェックフラグ
を描画済みに変更し、ステップ５０５としてこのフラグ
１１１と色データ１１２とを加える。この一纏めにした
フラグ１１１及び色データ１１２とを、ステップ５０６
としてアドレスＸ，Ｙにおける当該画素１０３に書き込
む。ステップ５０７として、全ての描画処理が終了した
か否かを判断し、終了していたら描画処理を終了し、終
了していない場合はステップ５０８として次の画素へ移
行する。

【００１０】このような、描画対象となっている各画素
１０３毎に、画素１０３に書かれているフラグ及び色デ
ータの読み出し、書き込みチェックフラグのチェック、
書き込み済みでない場合はフラグを書き込み済みに変更
してこのフラグと色データとを書き込むという処理を、
表示すべき物体の全てについて行うまで、あるいは制限
時間が来るまで繰り返す事で、１フレーム分の描画処理
が終了する。

【００１１】

【発明が解決しようとする課題】しかし、上述した従来
の描画装置には次のような問題があった。当該画素が既
に書き込み済みか否かを調べるためには、書き込みチェ
ックフラグを読み出すための読み出し動作を行う際に、
余分な色データまで読み出さなければならない。この結
果、読み出すときのデータのビット幅に比較して、読み
出すことができる書き込みチェックフラグのビット数が
大幅に少ないことになる。

【００１２】さらには、書き込みチェックフラグを読み
出すための読み出し動作を、１画素描画する毎に必ず１
回行わなければならない。よって、書き込みチェックフ
ラグを読みだす動作と書き込む動作とを切り換える必要
が頻繁に生じる。この切り換えには無駄な時間が含まれ
るので、メモリアクセス速度の低下を招いていた。

【００１３】本発明は上記事情に鑑みてなされたもの
で、front to back 法を用いた描画処理において、メ
モリアクセス速度を向上させることが可能な三次元図形
描画方法及びその装置を提供することを目的とする。

【００１４】

【課題を解決するための手段】本発明の三次元図形描画
方法は、三次元図形を視点に近い側から遠い方へ順に描
画していく描画方法であって、フレームバッファの所定
領域に画面表示用のデータを格納する画素が配置され、
前記所定領域とは異なる領域に、それぞれの前記画素に
書き込みがなされたか否かを示す書き込みチェックフラ
グを複数個ずつ格納するメモリが配置されており、前記
メモリから複数個の前記書き込みチェックフラグをまと
めて読み出すステップと、読み出した前記書き込みチェ
ックフラグを順に調べて、それぞれ対応する前記画素に
書き込みがなされている場合はこの画素に格納済みのデ
ータを保持され、対応する前記画素に書き込みがなされ
ていない場合はこの画素に新しいデータを書き込み、こ
の画素に対応する書き込みチェックフラグを書き込み済
みに変更するステップと、調べ終わった複数個の前記書
き込みチェックフラグをまとめて前記メモリに格納する
ステップとを備えることを特徴とする。

【００１５】ここで、前記画面表示用の画素と、それぞ
れの画素に対応する前記書き込みチェックフラグを格納
するメモリとは、前記フレームバッファにおける同一ロ
ウに配置されており、読み出した前記書き込みチェック
フラグを調べるステップでは、この書き込みチェックフ
ラグが格納されていたメモリのロウアドレスと、対応す
る画素のロウアドレスとが同一であってもよい。

【００１６】本発明による三次元図形描画装置は、画面
表示用のデータを格納する画素が所定領域に配置され、
前記所定領域とは異なる領域に、それぞれの前記画素に
書き込みがなされたか否かを示す書き込みチェックフラ
グを複数個ずつ格納するメモリが配置されたフレームバ
ッファと、前記フレームバッファにおける前記画素又は
前記メモリに対してアクセスするアクセス手段と、前記
アクセス手段が前記メモリから読みだした複数個の前記
書き込みチェックフラグを順に調べるフラグチェック手
段と、前記フラグチェック手段が調べた結果、それぞれ
対応する前記画素に書き込みがなされていない場合は、
前記アクセス手段にこの画素に新しいデータを書き込ま
せ、この画素に対応する書き込みチェックフラグを書き
込み済みに変更し、前記アクセス手段に調べ終わった複
数個の前記書き込みチェックフラグをまとめて前記メモ
リに格納させる制御手段とを備えることを特徴とする。

【００１７】ここで、前記フレームバッファは、前記画
面表示用の画素と、それぞれの画素に対応する前記書き
込みチェックフラグを格納するメモリとを、同一ロウに
配置していてもよい。

【００１８】

【発明の実施の形態】以下、本発明の一実施の形態につ
いて図面を参照して説明する。

【００１９】本実施の形態による三次元図形描画装置
は、フレームバッファのうち画面表示に用いられていな
いメモリ領域に、書き込みチェックフラグをまとめて格
納するメモリ配置を有する点に特徴がある。

【００２０】図２に、第１の実施の形態による描画装置
のフレームバッファ１の構成を示す。フレームバッファ
１には、画面表示に用いられるデータを格納する各々の
画素３を含むメモリ領域２と、画面表示には用いられな
いメモリセル５、９を含むメモリ領域４、８とが存在す
る。本実施の形態では、画面表示に用いられないメモリ
領域８に書き込みチェックフラグを格納する。

【００２１】図３に、画面表示に用いられないメモリ領
域８における一つのメモリ９の構成を示す。図６に示さ
れた従来の装置では、画面表示に用いられるメモリ領域
１０２の各画素１０３は、当該画素に関する書き込みチ
ェックフラグと色データとを一組にして格納していた
が、本実施の形態によるメモリ９は１ビットの書き込み
チェックフラグ１０のみを格納している。

【００２２】図１に、この描画装置において描画を行う
ときの処理の手順を示す。ステップ１０１として、書き
込みチェックフラグを書き込んだメモリ９の一つを読み
出す。このメモリ９は、図２に示されたようにＤビット
の深さを持っているので、１ビットの書き込みチェック
フラグをＤ個格納している。また、このメモリ９のアド
レスを、（Ｘ，Ｙ）とする。従来は、書き込みチェック
を行う場合にも、色データを同時に読み出さざるを得な
かったが、本実施の形態では書き込みチェックフラグの
みをまとめて読み出すことができる。

【００２３】ステップ１０２として、読み出したＤ個の
書き込みチェックフラグのうち、現時点で描画の対象と
なっている１画素に対応する書き込みチェックフラグ１
個を取り出して、書き込み済みか否かを調べる。書き込
み済みであれば当該画素に対しては現在格納している色
データを保持させ、ステップ１０５に移行して読み出し
たＤ個の書き込みチェックフラグの全てのチェックを終
了したか否かを判断する。終了していないときはステッ
プ１０２へ戻り、読み出したＤ個のフラグのうちの次の
フラグをステップ１０３において調べる。当該フラグが
示す画素３の書き込みがなされていないときは、ステッ
プ１０４へ移行し、新しい物体の色データを当該画素３
に書き込む。このようにして読みだしたＤ個の書き込み
チェックフラグの全てのチェックが終了したときは、ス
テップ１０５からステップ１０６へ移行し、読み出した
Ｄ個のフラグを全て書き込み済みに変更する。ステップ
１０７として、このＤ個の書き込みチェックフラグをま
とめてアドレス（Ｘ，Ｙ）の一つのメモリ９に書き込
む。

【００２４】以上のようなＤ個の書き込みフラグチェッ
クをまとめて読み出してそれぞれ対応する画素が書き込
み済みであるか否かを調べる処理のサイクルを繰り返
し、ステップ１０８において全ての描画が終了したと判
断すると描画処理を終了する。

【００２５】上述した第１の実施の形態による描画装置
及びこの装置を用いた描画方法によれば、書き込み済み
であるか否かを調べる場合、フレームバッファのメモリ
領域から書き込みチェックフラグを読み出すときにフラ
グ以外の色データといった余分なデータを合わせて読み
出す必要がない。よって、一つのメモリ領域５がＤビッ
トの容量を持つ場合は、Ｄ個のフラグを一度に読み出す
ことが可能であり、書き込みチェックフラグの読み出し
時間を短縮することができる。以下に、１画素に対する
描画処理を行うときに要するアクセス時間を、従来の描
画装置と上記本実施の形態とを比較する。

【００２６】従来の装置では、１画素に描画するために
メモリにアクセスするときに要する時間Ｔ１は、書き込
みが既になされている画素に対しては、 Ｔ１＝１画素リード時間 … （１） であり、書き込みがまだなされていない画素に対して
は、 Ｔ１＝１画素リード時間＋１画素ライト時間 … （２） である。よって、Ｄ個の画素のうち、書き込みがなされ
たものがｎ個あるとすると、１画素の描画を行うために
メモリをアクセスする時間Ｔ１は、 Ｔ１＝１画素リード時間＋１画素ライト時間×ｎ／Ｄ … （３） である。

【００２７】これに対し、本実施の形態によれば、１画
素の描画を行うためにメモリをアクセスする時間Ｔ２
は、Ｄ個のフラグを格納した１つのメモリ領域を読み出
して、書き込まれていないｎ個の画素に書き込みを行
い、さらにフラグを格納した１つのメモリ領域へのフラ
グを書き込む時間を合計した値となるため、 Ｔ２＝（１画素リード時間＋１画素ライト時間×ｎ＋１画素ライト時間） ／１Ｄ … （４） となる。

【００２８】上記Ｔ１とＴ２とを比較し、本実施の形態
によれば従来よりも、以下の時間Ｔ３だけアクセス時間
を短縮することができる。 Ｔ３＝Ｔ１−Ｔ２ ＝（１画素リード時間×（Ｄ−１）−１画素ライト時間）／Ｄ … （５） 即ち、一つのメモリ領域５の深さ方向の容量Ｄが大きい
ほど本実施の形態によりアクセス時間を短縮する効果が
大きい。

【００２９】さらに、本実施の形態によればメモリ領域
を読み出す動作と書き込む動作とを切り換える時に要す
る時間を短縮することができる。従来は、１画素毎にフ
ラグと色データとを読み出して当該画素へフラグ及び色
データを一纏めにしたものを書き込む必要があり、１画
素毎に読みだしと書き込みとを切り換える必要があっ
た。

【００３０】これに対し本実施の形態では、図１のフロ
ーチャートを用いて説明したように、Ｄ個の画素への描
画を行う処理を１単位として、フラグを格納した１つの
メモリ領域を１回読みだした後、描画済みでない画素へ
の色データの書き込みとＤ個の画素への描画処理が済ん
だ後のフラグを格納したメモリ領域への１回のフラグの
書き込みという書き込み動作が次々と行われる。このた
め、読みだしと書き込み動作とを切り換える回数が従来
よりも減少し、切り換え時間を短縮することができる。

【００３１】従来の装置において、Ｄ個の画素のうち、
描画済みでないものがｎ個ある場合、読み出しから書き
込みに切り換えるために要する時間Ｔ１１は、 Ｔ１１＝ｎ／Ｄ×（１回の読み出しから書き込みへの切り換え時間） …（６） である。本実施の形態によれば、切り換わる回数は上述
したように１回であるので、切り換えに要する時間Ｔ１
２は、 Ｔ１２＝１／Ｄ×（１回の読み出しから書き込みへの切り換え時間） …（７） となる。ところで、描画処理を行った後の次の描画サイ
クルは、フラグを書き込んだ１つのメモリの読み出しか
ら開始される。このため、前のサイクルにおける書き込
みから次のサイクルにおける読み出しへの切り換えも必
要となる。

【００３２】そこで、本実施の形態によれば、 Ｔ１２−Ｔ１１＝ （ｎ−１）／Ｄ×（１回の読み出しから書き込みへの切り換え時間 ＋１回の書き込みから読み出しへの切り換え時間） … （８） だけ時間短縮される。

【００３３】次に、本発明の第２の実施の形態による描
画装置について、そのフレームバッファの構成を示した
図４を用いて説明する。

【００３４】本実施の形態では、フレームバッファ２１
をＤＲＡＭ型のメモリで構成しており、画面表示用のメ
モリ領域２２と、書き込みチェックフラグを格納するメ
モリ領域２８と、いずれにも使用しないメモリ領域２４
とが存在する。そして、本実施の形態における特徴は、
画面表示用のメモリ領域２２の画素２３と、この画素２
３に対応する書き込みチェックフラグを書き込むメモリ
領域２８のメモリ２９とが同一のロウアドレスに配置さ
れている点にある。メモリ領域２２の画素２３とメモリ
領域２８のそれぞれのメモリ２９は、上記第１の実施の
形態と同様に、深さ方向にＤビットの容量を持ってい
る。よって、メモリ領域２８の各メモリ２９は、同一ロ
ウアドレスのＤ個の画素２３分の書き込みチェックフラ
グを格納している。

【００３５】また、第２の実施の形態では画素２２と同
一ロウアドレスに書き込みチェックフラグを格納するメ
モリ２９を設ける必要上、画面表示用のメモリ領域２２
の大きさには制約が存在する。このメモリ領域２２のカ
ラム方向の画素２３の数Ｗは、同一ロウアドレスに格納
可能な書き込みチェックフラグの数と同一またはそれよ
りも小さくなければならない。よって、 Ｗ≦（ＸMAX −Ｗ）×Ｄ という関係式が成立し、 Ｗ≦ＸMAX ×Ｄ／（Ｄ＋１） … （９） となる。この（９）式が成立する範囲内で画素２３をカ
ラム方向に設けることができる。

【００３６】本実施の形態によれば、上記第１の実施の
形態と同様に、書き込みチェックフラグを読み出すとき
に余分な色データを読み出すことがなく、さらにメモリ
の読みだし動作と書き込み動作との切り換え回数が少な
いため、アクセス速度が向上する。さらに、一般のＤＲ
ＡＭで用いられているようにファーストページモードを
適用して、第１の実施の形態よりもさらにアクセス速度
の高速化を図ることが可能である。即ち、第２の実施の
形態では画面表示用の画素２３とこの画素２３に対応し
た書き込みチェックフラグを格納するメモリ２８とが同
一ロウアドレスに配置されているため、ロウアドレスを
固定した状態でカラムアドレスのみを変えて描画動作を
行うことができる。

【００３７】上述した実施の形態はいずれも一例であっ
て、本発明を限定するものではない。例えば、第１、第
２の実施の形態では図２、図４にそれぞれ示されたよう
にフレームバッファの左上部に画面表示用の画素を配置
しているが、この配置には限定されず他の領域に配置し
てもよい。また、第２の実施の形態では図４に示される
ようにフレームバッファの左上部に画面表示用の画素を
配置し、右上部に書き込みチェックフラグを格納するメ
モリを配置している。しかし、画素に対応する書き込み
チェックフラグを格納するメモリを同一ロウアドレスに
配置するのであれば、フレームバッファ上の他の領域に
画素及びメモリを配置していもよい。

【００３８】

【発明の効果】以上説明したように、本発明の三次元図
形描画方向及びその装置は、画素の書き込み済みの有無
を示す書き込みチェックフラグを画素とは異なる領域の
メモリにまとめて格納するため、一つのメモリが有する
全容量分だけフラグを格納することができ、一度の読み
出し動作でまとめてフラグのみを読み出すことができ、
メモリをアクセスする効率が向上する。さらに、メモリ
の読み出し動作と書き込み動作とを切り換える回数が減
少し、アクセスの高速化が達成される。

【図面の簡単な説明】

【図１】本発明の第１の実施の形態による三次元図形描
画方法における図形描画処理の手順を示すフローチャー
ト。

【図２】同第１の実施の形態による三次元図形描画装置
のフレームバッファの構成を示す説明図。

【図３】同フレームバッファにおける書き込みチェック
フラグを格納する各メモリの構成を示す説明図。

【図４】本発明の第２の実施の形態による三次元図形描
画装置のフレームバッファの構成を示す説明図。

【図５】従来の三次元図形描画装置のフレームバッファ
の構成を示す説明図。

【図６】同フレームバッファにおける各画素の構成を示
す説明図。

【図７】従来の三次元図形描画方法における図形描画処
理の手順を示すフローチャート。

【符号の説明】

１、２１ フレームバッファ ２、２２ 画面表示用のメモリ領域 ３、２３ 画素 ４、２８ 書き込みチェックフラグ格納用のメモリ領域 ５、９、２９ メモリ ８、２４ 画面表示に用いないメモリ領域 １０ 書き込みチェックフラグ

Claims (4)

【特許請求の範囲】
1. 【請求項１】三次元図形を視点に近い側から遠い方へ順
   に描画していく三次元図形描画方法において、 フレームバッファの所定領域に画面表示用のデータを格
   納する画素が配置され、前記所定領域とは異なる領域
   に、それぞれの前記画素に書き込みがなされたか否かを
   示す書き込みチェックフラグを複数個ずつ格納するメモ
   リが配置されており、 前記メモリから複数個の前記書き込みチェックフラグを
   まとめて読み出すステップと、 読み出した前記書き込みチェックフラグを順に調べて、
   それぞれ対応する前記画素に書き込みがなされている場
   合はこの画素に格納済みのデータを保持され、対応する
   前記画素に書き込みがなされていない場合はこの画素に
   新しいデータを書き込み、この画素に対応する書き込み
   チェックフラグを書き込み済みに変更するステップと、 調べ終わった複数個の前記書き込みチェックフラグをま
   とめて前記メモリに格納するステップと、 を備えることを特徴とする三次元図形描画方法。
2. 【請求項２】前記画面表示用の画素と、それぞれの画素
   に対応する前記書き込みチェックフラグを格納するメモ
   リとは、前記フレームバッファにおける同一ロウに配置
   されており、読み出した前記書き込みチェックフラグを
   調べるステップでは、この書き込みチェックフラグが格
   納されていたメモリのロウアドレスと、対応する画素の
   ロウアドレスとが同一であることを特徴とする請求項１
   記載の三次元図形描画方法。
3. 【請求項３】三次元図形を視点に近い側から遠い方へ順
   に描画していく三次元図形描画装置において、 画面表示用のデータを格納する画素が所定領域に配置さ
   れ、前記所定領域とは異なる領域に、それぞれの前記画
   素に書き込みがなされたか否かを示す書き込みチェック
   フラグを複数個ずつ格納するメモリが配置されたフレー
   ムバッファと、 前記フレームバッファにおける前記画素又は前記メモリ
   に対してアクセスするアクセス手段と、 前記アクセス手段が前記メモリから読みだした複数個の
   前記書き込みチェックフラグを順に調べるフラグチェッ
   ク手段と、 前記フラグチェック手段が調べた結果、それぞれ対応す
   る前記画素に書き込みがなされていない場合は、前記ア
   クセス手段にこの画素に新しいデータを書き込ませ、こ
   の画素に対応する書き込みチェックフラグを書き込み済
   みに変更し、前記アクセス手段に調べ終わった複数個の
   前記書き込みチェックフラグをまとめて前記メモリに格
   納させる制御手段と、 を備えることを特徴とする三次元図形描画装置。
4. 【請求項４】前記フレームバッファは、前記画面表示用
   の画素と、それぞれの画素に対応する前記書き込みチェ
   ックフラグを格納するメモリとを、同一ロウに配置して
   いることを特徴とする請求項３記載の三次元図形描画装
   置。