(57)【要約】回転画面を備えた立体表示装置において所望の線を高速で描画するための方法は、回転画面を一連の角度位置で段階的に通過させる段階と、それぞれの角度位置において、上記回転画面上に、上記所望の線と上記回転画面との交点を含む線分を近似的にラスタ化する段階とを含む。
2004508640.tif 000002
【特許請求の範囲】
【請求項１】
複数のボクセルを備えた立体表示装置に、所望の線を近似するラスタ化した線を描画する方法であって、
画面を、その画面が入口平面と同一平面に位置する第１角度位置に、配置する段階と、
前記所望の線と前記入口平面との交点に対応する第１ボクセルを選択する段階と、
前記入口平面に交差する出口平面と前記所望の線との交点の、前記入口平面への射影に対応する第２ボクセルを選択する段階と、
前記第１ボクセルと前記第２ボクセルとを連結する連結線分を画定する段階と、
前記連結線分をラスタ化するため、選択したボクセルを前記画面上に描画する段階とを包含した、方法。
【請求項２】
前記選択したボクセルを描画する前記段階が、前記選択したボクセルを均一に照光する段階を包含した、請求項１に記載の方法。
【請求項３】
前記選択したボクセルを描画する前記段階が、前記選択したボクセルを選択した照光パターンに従って描画する段階を包含した、請求項１に記載の方法。
【請求項４】
前記選択したボクセルの少なくとも１つの照光レベルが、実質的にゼロに指定されるように、前記照光パターンを選択する段階を更に包含した、請求項３に記載の方法。
【請求項５】
前記選択したボクセルの前記少なくとも１つを、前記第１ボクセル及び前記第２ボクセルからなるグループから選択する段階を更に包含した、請求項４に記載の方法。
【請求項６】
前記画面が前記入口平面と同一平面に位置する第１角度位置から、前記画面が前記出口平面と同一平面に位置する第２角度位置まで、前記画面を回転させつつ、前記選択したボクセルの描画を継続する段階を更に包含した、請求項１に記載の方法。
【請求項７】
前記第１ボクセルを選択する前記段階が、
前記線をデカルト座標で定義する定数を求める段階と、
前記入口平面の前記角度位置を表す角度を求める段階と、
前記定数及び前記角度に基づいて、三角法変換を行って、前記所望の線と前記入口平面との前記交点の円柱座標を特定する段階とを包含した、請求項１に記載の方法。
【請求項８】
前記三角法変換を行う前記段階が、ルックアップテーブルから、引数の三角関数の値を得る段階を包含した、請求項７に記載の方法。
【請求項９】
前記第１ボクセルに対応した回転座標であって、選択した角度の回転に対応する回転座標を生成する段階を更に包含した、請求項７に記載の方法。
【請求項１０】
台形像効果を補正するため、前記回転座標を射影する段階を更に包含した、請求項９に記載の方法。
【請求項１１】
前記第１ボクセルに対応した射影座標であって、台形歪みの補正により得られる射影座標を生成する段階を更に包含した、請求項７に記載の方法。
【請求項１２】
前記ルックアップテーブルが、前記画像を配置可能な角度位置の数の少なくとも２倍の項目数を備えた、請求項８に記載の方法。
【請求項１３】
前記選択したボクセルを前記画面上に描画する前記段階が、ブレセンハムのアルゴリズムを適用して、前記所望の線と前記入口平面との前記交点と、前記所望の線と出口平面との交点の前記入口平面への前記射影とに基づいて、前記選択したボクセルを求める段階を更に包含した、請求項１に記載の方法。
【請求項１４】
前記方法が更に、
前記画面上での選択したボクセルの前記描画を実行して、前記連結線分をラスタ化するための専用の第１プロセッサを提供する段階と、
前記第１プロセッサと通信して、前記第１プロセッサに前記所望の線を示す情報を与える第２プロセッサを提供する段階とを更に包含した、請求項１に記載の方法。
【請求項１５】
回転画面を備えた立体表示装置において所望の線を描画する方法であって、
前記回転画面を一連の角度位置で段階的に通過させる段階と、
それぞれの角度位置において、前記画面上に、前記所望の線と前記回転画面との交点を含む線分のラスタ化した近似を描画する段階とを包含した、方法。
【請求項１６】
複数のボクセルを備えた立体表示装置に、所望の線を近似するラスタ化した線を描画するためのソフトウェアをその上に符号化したコンピュータ読取り可能媒体であって、前記ソフトウェアが、
画面を、その画面が入口平面と同一平面に位置する第１角度位置に配置し、
前記所望の線と前記入口平面との交点に対応する第１ボクセルを選択し、
前記入口平面に交差する出口平面と前記所望の線との交点の、前記入口平面への射影に対応する第２ボクセルを選択し、
前記第１ボクセルと前記第２ボクセルとを連結する連結線分を画定し、
前記連結線分をラスタ化するため、選択したボクセルを前記画面上に描画するための命令を包含した、コンピュータ読取り可能媒体。
【請求項１７】
前記選択したボクセルを描画するための前記命令が、前記選択したボクセルを均一に照光するための命令を包含した、請求項１６に記載のコンピュータ読取り可能媒体。
【請求項１８】
前記選択したボクセルを描画するための前記命令が、選択した照光パターンに従って前記選択したボクセルを描画するための命令を包含した、請求項１６に記載のコンピュータ読取り可能媒体。
【請求項１９】
前記照光パターンを選択するための前記命令が、前記選択したボクセルの少なくとも１つの照光レベルを実質的にゼロに指定するための命令を包含した、請求項１８に記載のコンピュータ読取り可能媒体。
【請求項２０】
前記照光パターンを選択するための前記命令が、前記選択したボクセルの前記少なくとも１つを、前記第１ボクセル及び前記第２ボクセルからなるグループから選択するための命令を包含した、請求項１９に記載のコンピュータ読取り可能媒体。
【請求項２１】
前記ソフトウェアが、前記画面が前記入口平面と同一平面に位置する第１角度位置から、前記画面が前記出口平面と同一平面に位置する第２角度位置まで、前記画面を回転させつつ、前記選択したボクセルを描画するための命令を更に包含した、請求項１６に記載のコンピュータ読取り可能媒体。
【請求項２２】
前記第１ボクセルを選択するための前記命令が、
前記線をデカルト座標で定義する定数を求め、
前記入口平面の前記角度位置を表す角度を求め、
前記定数及び前記角度に基づいて、三角法変換を行って、前記所望の線と前記入口平面との前記交点の円柱座標を特定するための命令を包含した、請求項１６に記載のコンピュータ読取り可能媒体。
【請求項２３】
前記三角法変換を行うための前記命令が、ルックアップテーブルから、引数の三角関数の値を得るための命令を包含した、請求項２２に記載のコンピュータ読取り可能媒体。
【請求項２４】
前記ソフトウェアが、前記第１ボクセルに対応した回転座標であって、選択した角度の回転に対応する回転座標を生成するための命令を更に包含した、請求項２２に記載のコンピュータ読取り可能媒体。
【請求項２５】
前記ソフトウェアが、台形像効果を補正するため、前記回転座標を射影するための命令を更に包含した、請求項２４に記載のコンピュータ読取り可能媒体。
【請求項２６】
前記ソフトウェアが、前記第１ボクセルに対応した射影座標であって、台形歪みの補正により得られる射影座標を生成するための命令を更に包含した、請求項２２に記載のコンピュータ読取り可能媒体。
【請求項２８】
前記選択したボクセルを前記画面上に描画するための前記命令が、ブレセンハムのアルゴリズムを適用して、前記所望の線と前記入口平面との前記交点と、前記所望の線と出口平面との交点の前記入口平面への前記射影とに基づいて、前記選択したボクセルを求めるための命令を更に包含した、請求項１６に記載のコンピュータ読取り可能媒体。
【請求項２９】
前記ソフトウェアが、
前記画面上での選択したボクセルの前記描画を実行して、前記連結線分をラスタ化するための専用の第１プロセッサを提供し、
前記第１プロセッサと通信して、前記第１プロセッサに前記所望の線を示す情報を与える第２プロセッサを提供するための命令を更に包含した、請求項１６に記載のコンピュータ読取り可能媒体。
【請求項３０】
回転画面を備えた立体表示装置に、所望の線を描画するためのソフトウェアをその上に符号化したコンピュータ読取り可能媒体であって、前記ソフトウェアが、
前記回転画面を一連の角度位置で段階的に通過させ、
それぞれの角度位置において、前記画面上に、前記所望の線と前記回転画面との交点を含む線分のラスタ化した近似を描画するための命令を包含した、コンピュータ読取り可能媒体。
【発明の詳細な説明】
【０００１】
本発明は、コンピュータグラフィックスに関し、特に、ボクセルが円柱座標格子上に配列されている立体表示装置における直線の描画に関する。
【０００２】
優先権主張
３５合衆国法典§１１９（ｅ）（１）に従い、本願は、２０００年９月７日付けの米国仮特許出願第６０／２３０，９７２号の優先日の利益を主張し、その内容はここに引用して本開示の一部とする。
【０００３】
発明の背景
多くのコンピュータが実現する表示装置は、個別の画素すなわちピクセルの２次元アレーからなっている。画像を形成するには、ラスタライザがこれらのピクセルを選択的に照光（原語：ｉｌｌｕｍｉｎａｔｅ）する。個々のピクセルは非常に小さいので、表示は人間の目には画像が連続的に描かれているように映る。この錯覚は、写真のような色調が連続する複雑な画像にはとりわけ効果的である。
【０００４】
しかし、単純な幾何学的形状に関しては、表示がピクセル化されているという性質が見ている人間に分かってしまうことがある。例えば、ラスタライザが直線を引くという命令を受けた場合、この所望の線上の点が、この線を描画（原語：ｒｅｎｄｅｒ）するのに使用可能なピクセルと一致するという保証はどこにもない。その結果、所望の線は、しばしば、所望の線に近いが必ずしも一致するとは限らない、ピクセルからなるラスタ化された線として描かれる。この結果、ラスタ化した線は、ギザギザまたは梯状に見えてしまう。
【０００５】
画像を描く過程で、多数の直線や線分がしばしば描かれる。その結果、所望の線に関して、ラスタライザは、結果として得られるラスタ化した線のギザギザ形状を最小限に抑制するようにピクセルを頻繁に選択しなければならない。単純明快な数学的アプローチは、所望の線の式と利用可能なピクセルの座標を用いて、この線のすべての点において最小２乗誤差を極小化するというものである。こうしたアプローチには、ラスタ化した線上でのピクセル選択を全般的に最適化するという利点がある一方、必要な浮動小数点演算が多数に上るので、極端に時間を要するものとなる。
【０００６】
速度上の制約条件を満たすため、通常、ラスタライザは、時間がかかる浮動小数点演算を避けるラスタ化方法を実行する。上述の制約条件を満たす方法の１つとしては、ブレセンハム，Ｊ．Ｅ．（Ｂｒｅｓｅｎｈａｍ， Ｊ．Ｅ．）、デジタルプロッタをコンピュータ制御するためのアルゴリズム（Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｃｏｍｐｕｔｅｒ Ｃｏｎｔｒｏｌ ｏｆ ａ Ｄｉｇｉｔａｌ Ｐｌｏｔｔｅｒ）、ＩＢＭ Ｓｙｓｔｅｍ Ｊｏｕｒｎａｌ， Ｖｏｌ． ４， ｐｐ．２５−３０， １９６５があり、その内容はここに引用して本開示の一部とする。整数演算のみを用いることで、ブレセンハムのアルゴリズムは、ピクセルの選択を判別式の符号を調べることに簡略化している。
【０００７】
ラスタ化する線上で、１点でなく複数点を単一の判断の結果に基づいて選択する、より高速なラスタ化方法も存在する。また、ピクセル化した表示装置に円錐領域と２次領域を描画することを目的とした様々なラスタ化方法も存在する。
【０００８】
しかし、上述のラスタ化方法はすべて、ピクセルアレーが、デカルト座標系で容易にモデル化できる一様な直交格子上に配列されているという前提の上に成り立っている。こうしたアルゴリズムが開発された時点におけるコンピュータのモニターやプリンタなどの２次元表示装置の普及状況を考慮すれば、これは無理のない前提であった。
【０００９】
しかし、それ以降、立体すなわち３次元表示装置が開発されている。こうした表示装置は、一組の局所的及び特定領域からの可視光を一定の体積内で生成、吸収、又は拡散できるものである。こうしたシステムの例が、Ｈｉｒｓｃｈの米国特許第２，９６７，９０５号、Ｋｅｔｃｈｐｅｌの米国特許第３，１４０，４１５号、Ｔｓａｏの米国特許第５，７５４，１４７号、及び１９６０年１０月３１日付けのＡｖｉａｔｉｏｎ Ｗｅｅｋの６６乃至６７ページに記載されている。
【００１０】
発明の概要
本発明の方法は、回転画面を備えた立体表示装置において所望の線の高速描画を可能とする。この方法は、回転画面を角度位置の連続体に通過させる段階を含む。それぞれの角度位置において、上記画面上に、上記所望の線と上記回転画面との交点を含む線分が、近似的にラスタ化して描かれる。
【００１１】
本発明の一態様によれば、上記画面は、画面が入口平面と同一平面に位置する第１角度位置に配置される。次に、第１及び第２ボクセルが、所望の線と入口平面との間の幾何学的関係に基づいて選択される。具体的には、第１ボクセルは、所望の線と入口平面との交点に対応し、第２ボクセルは、所望の線と出口平面との交点の入口平面への射影に対応する。次に、第１ボクセルと第２ボクセルとを連結する連結線分が、この２次元画面上の選択したボクセルを描画することでラスタ化される。
【００１２】
連結線分のラスタ化は、ブレセンハムのアルゴリズムのようなアルゴリズムによって実行できる。しかし、任意の２次元ラスタ化アルゴリズムを用いて、この連結線分をラスタ化してよい。
【００１３】
本発明の一態様では、第１ボクセルは、デカルト座標において上記所望の線を定義する定数を求め、且つ、上記入口平面の角度位置を表す角度を求めることにより選択される。これら定数及び角度に基づいて、三角法変換により、所望の線と入口平面との交点の円柱座標を特定する。
【００１４】
場合によっては、立体表示装置の光学配置が、付加的且つ随意に選択可能な本発明のステップで補正される歪みを発生させることがある。例えば、結像画面の回転が引き起こす歪みは、第１ボクセルに対応した回転座標を生成することで補正可能だが、この場合、回転座標は選択した角度の回転に対応する。同様に、台形像効果が原因となる歪みは、第１ボクセルに対応した射影座標を生成することで補正可能だが、この場合、射影座標は台形歪みの補正により求められる。
【００１５】
本発明の上記及びその他の特徴及び利点は、次の詳細な説明及び図面から明らかとなるはずである。
【００１６】
詳細な説明
図１に示した本発明を実施するための立体表示装置１０は、台座部分１１及び回転部分１２を含む。モータ制御装置１３の動作により、モータ（図示しない）は、台座部分１１に結合された回転部分１２を軸１６を中心として高速で回転させる。
【００１７】
台座部分１１内では、光源１８が、ラスタライザ２０の制御下で、結像画面１４上の選択したピクセル２２を照光するための空間的に変化する光のパターンを、連続的な瞬間において生成する。一般的な光源１８としては、その配向がラスタライザ２０に制御される、個々にアドレス可能なミラーからなる微小機械的アレーがある。この光は、回転部分１２に結合し且つ軸１６に同軸である回転光学サブシステム１７に光学的に連通した静止光学サブシステム１５を介して回転部分１２の内部に導かれる。
【００１８】
回転光学サブシステム１７からの光は、回転光学サブシステム１７の上方に配置され且つ台座部分１１の周縁部に配置された第１リレーミラー２１に光を向けるように角度を付けた中央ミラー１９に投射される。第１リレーミラー２１は、光を、台座部分１１の周縁部にある第２リレーミラー２３に向けて反射するように角度を付けられている。第２リレーミラー２３は、第１リレーミラー２１からの光を、結像画面１４に向けるように角度を付けられている。
【００１９】
結像画面１４上で照光するピクセル及びそれらを照光する瞬間は、結像画面１４の角度位置を示すデータ（モータ制御装置１３により与えられる）と、３次元画像を表すデータ（データソース２５に格納されている）に基づいて、ラスタライザ２０により決定される。
【００２０】
回転部分１２が軸１６を中心に回転すると、結像画面１４が、回転部分１２内の表示立体領域（ｄｉｓｐｌａｙ ｖｏｌｕｍｅ）２７を掃引する。回転部分１２の回転速度が十分速ければ、また、連続した瞬間における照光が十分短い時間間隔で隔てられていれば、連続した曲線が、表示立体領域２７内の空中に浮かんでいるように見えるはずである。
【００２１】
図２は、ラスタライザ２０により近似される所望の線２４の、軸１６に直交する面への射影を示す。図２では、結像画面１４を、紙面に対して直交した軸１６周りを回転する際の連続した６つの瞬間において示した。これら６つの瞬間のそれぞれにおいて、光源１８は、ラスタライザ２０に制御されながら、結像画面１４上のピクセル２２を照光する。図２に示したように、光源１８の照準を正しいピクセルに定め、正しい時刻に発光させることで、所望の線２４に近似するラスタ化した線を掃引できる。この所望線２４を掃引するために光源１８の照準を正しく定め且つ発光させるのは、ラスタライザ２０の機能である。
【００２２】
光源の照準を定めるため、ラスタライザ２０は、空間内の点を識別する方法を必要とする。これは言い換えれば、ラスタライザ２０は座標系を必要とするということである。利用可能な座標系としてはデカルト座標系がある。
【００２３】
デカルト座標系を用いる場合は、ラスタライザ２０は、例えば、時刻ｔ１において、光源１８が北３０単位に照準を定め、時刻ｔ２において、光源１８が北に２９単位、東に１単位、高さ１単位に照準を定め、時刻ｔ３において、光源５が北に２８単位、東に２単位、高さ２単位に照準を定めるなどと指定することにより、図２の所望の線を引くことができる。結像画面１４が適切に位置決めされることを保証するため、ラスタライザ２０は、結像画面１４の回転速度に基づいて時刻ｔ１、ｔ２、及びｔ３の値を指定する必要もある。結像画面１４の回転は、南北成分と東西成分とに分解できるが、これは円柱座標系を用いれば容易に避けることができる負担が大きな計算操作である。
【００２４】
その代替策として、ラスタライザ２０は、例えば、時刻ｔ１において、光源１８が、軸１６から３０単位離れた地点に９０度の角度で照準を定め、時刻ｔ２において、光源１８が、軸１６から２９．０２単位離れた地点に、８８．０３度の角度で、高さ１単位に照準を定め、時刻ｔ３において、光源１８が、軸１６から２８．０７単位離れた地点に、８５．９１度の角度で、高さ２単位に照準を定めるなどと指定することにより、円柱座標に図２の所望の線を引くことができる。もちろん、これによって引かれる線は、デカルト座標を用いて引いた線と同一になる。光源１８を発光させる時刻を指定する段階になれば、円柱座標を用いる利点は明らかとなる。結像画面１４は回転しているので、この画面の運動を南北成分及び東西成分に分解するよりは、毎秒の角度で表す方が遙かに自然である。この理由から、立体表示装置１０内での結像画面１４の運動に関する計算は、円柱座標系に基づいて行うのがもっとも好ましい。
【００２５】
円柱座標系で線を描画する過程は、デカルト座標系で線を描画する過程とは根本的に異なる。デカルト座標系では、直線の傾きは一定である。一方向における単位変化は、その変化の位置にかかわらず、残りの２方向にも同じ変化を及ぼす。このことは円柱座標系には当てはまらない。
【００２６】
円柱座標系では、直線の傾きは、その直線に沿った位置により大きく変化することがある。直線上のすべての点においてその傾きが一定であるデカルト座標系とは対照的に、円柱座標系における直線の傾きは、直線に沿って大きく変化することがある。これは、円柱座標系における座標格子が、デカルト座標系の座標格子のようには空間的に一様な格子ではないからである。
【００２７】
円柱座標系の軸に最も近い直線部分に関しては、原点からの直線の距離が変化しても角度変化の割合は小さい。円柱座標系の軸から遠く離れた直線部分に関しては、角度がわずかに変化しても、軸からの半径方向距離は大きく変化する。
【００２８】
図１の立体表示装置１０において、ラスタライザ２０は、一連の画像を結像画面１４に射影させる。結像画面１４にどのような画像が表示されるかは、結像画面１４が軸１６を中心にして回転するさいの画面１４の角度位置により決まる。しかし、画像は、画面１４の角度位置と共にとぎれなく変化するわけではない。そうする代わりに、表示画像は特定の角度位置範囲では一定状態を保ち、画面１４の角度位置が複数の閾値角度のいずれかを横切るときにのみ変化する。これら閾値角度は、通常は均等に離間され互いに非常に隣接している。図示した実施形態では、閾値角度間の分離角は、３０分の弧と１度の弧との間である。
【００２９】
従って、立体表示装置１０の表示立体領域は、交差平面からなる円柱領域（ｃｙｌｉｎｄｒｉｃａｌ ｖｏｌｕｍｅ）と見ることができ、これら交差平面は、結像画面１４の回転中心となる軸１６において交差する。図２の断面図では、一対の交差面それぞれが、くさび形のスライス２８を画定している。任意スライスの境界を定める２つの平面を、「入口平面３０」及び「出口平面３２」と称する。画面１４が軸１６を中心に回転するときは、画面は、一瞬の間、特定のスライス２８の入口平面３０と同一平面に位置し、次に、画面はそのスライス２８を横断し、更に、そのスライス２８の出口平面３２と同一平面に位置する。図２から明らかなように、スライス２８の出口平面３２は、次のスライス３３の入口平面と同一平面に位置している。
【００３０】
結像画面１４が任意の入口平面３０と同一平面に位置するときは、画面１４上に表示された画像の変更が可能となる。結像画面１４がスライス２８を横断している間は、画面１４上の表示画像は変化せず一定である。所望の線２４を引くためにラスタライザ２０が一般的に利用可能なデータには、少なくとも２点（ｘ０，ｙ０，ｚ０）及び（ｘ１，ｙ１，ｚ１）のデカルト座標を得るもととなるデータが含まれる。これらの２点から、所望の線２４を表す次の定数が計算される。
【数１】
2004508640.tif 000003
【数２】
2004508640.tif 000004
【数３】
2004508640.tif 000005
【数４】
2004508640.tif 000006
【００３１】
これらの定数は、所望の線２４それぞれに一度だけ計算すればよい。図示した実施形態では、ｄは１６ビットの符号付き固定小数点数で、ｈｔは４０ビットの固定小数点数で、γは１６ビットの符号付き固定小数点数である。
【００３２】
性能を向上させるには、θｔの値をルックアップテーブルから取得するようにする。ルックアップテーブルは、ラスタ化の正確度をあまり低下させない程度の粗さのθｔの解像度を選択することで可能な限り小さくする。具体的には、θｔの解像度が、表示空間のθ解像度より粗くなる場合は、異なる平面に対応するθの値が同一のｒ及びｈ値にマッピングされることがある。これは、θ方向の解像度の好ましくない低下の原因となる。
【００３３】
図示した実施形態では、ルックアップテーブル内の項目数は、表示空間のθ解像度の２倍である。この比率により、ほとんどの視覚的アーチファクトを除去し、表示装置１０の最小解像度の低下を防止するに十分な正確度が得られる。
【００３４】
これらの定数が与えられれば、ラスタライザ２０は、図２に示したような所望の線２４と各交差平面との交点の円柱座標を算出する。これら交点は次の式で与えられる。
【数５】
2004508640.tif 000007
【数６】
2004508640.tif 000008
上記式において、θは特定の交差平面に関連付けられた角度である。
【００３５】
所望の線２４を描画する図３に示した１つのアプローチは、所望の線２４と入口平面３０との交点に最も近接した、その平面上のボクセル２６を選択することである。その後、ラスタライザ２０は、画面１４が入口平面３０と同一平面に位置する瞬間から始まり、そのスライス２８の出口平面３２に回転しつつ到着する直前で終わるまでの間隔は、その選択したボクセル２６を照光し続ける。連続したスライスに関してこの処理を繰り返して、所望の線２４を近似するラスタ化した線が作成される。
【００３６】
上述の方法の難点は、θ解像度が極端に高くなければ、結果として生じるラスタ化した線は、図４に示したように、一連の不連続的な円弧として現れることである。各弧３４は、画面１４が特定のスライス２８を横断する際に、その画面が掃引する角度に比例した長さとなる。
【００３７】
これを解決するため、ラスタライザ２０は、上述のように所望の線２４と入口平面３０及び出口平面３２との交点（以降、それぞれ「入口点３６」及び「出口点３８」と称する）を特定する。画面１４が入口平面３０と同一平面に位置するときは、ラスタライザ２０は、入口点３６に対応するボクセルを描画する。更に、図５に示したように、ラスタライザ２０は、出口点３８の入口平面３０への射影（以降、「射影した出口点４０」と称する）を特定する。これによって、入口点３６と射影した出口点４０とを結ぶ連結線分４２が、画面１４上に画定される。その後、ラスタライザ２０は、この連結線分４２をラスタ化するボクセルを画面１４上で描画する。このラスタ化は、ブレセンハムのアルゴリズムのような従来の２次元ラスタ化アルゴリズムを用いて実行できる。
【００３８】
従って、本発明のラスタ化方法は、結像画面１４が３次元表示領域内で円柱を掃引する際に、この結像画面１４上で一連の２次元ラスタ化を行うことで、円柱座標系内において３次元ラスタ化を実現する。
【００３９】
画面１４がスライス２８を横断するときは、図６に示したように、その画面１４上に描画された連結線分４２が、連結線分４２の幅および配向に対応した幅および配向を備えた平面ストリップ４４を掃引する。閾値角度は互いに接近しているので、入口点３６と射影した出口点４０とは平面上で少数のピクセルによってしか離間していない。従って、連結線分４２は短い線分である。結果的に、画面１４が掃引する平面ストリップ４４は、数ボクセル分の幅しかない。
【００４０】
画面１４が出口平面３２に接近するにつれ、連結線分４２上の射影した出口点４０は出口点３８に接近する。この出口点３８は、次のスライス３３の入口点でもある。従って、複数の連結線分により掃引される複数の平面ストリップは、互いに滑らかに結合するように見え、結果として滑らかな線が３次元で表示される。
【００４１】
このラスタ化方法は円柱座標系に関連して説明したが、回転及び射影によって円柱座標系から得られる複数の座標系にも適用可能である。図１に示したような特定の立体表示装置は、補正を必要とするある種の画像歪みを引き起こす。
【００４２】
第１の種類の画像歪みは、光源１８が、静止画像を回転する結像画面１４上に射影するとき視覚的に明らかとなる。これが起こると、静止画像が、結像画面１４の中心の周りを回転しているように見える。この種の歪みは、「回転歪み」と呼ばれる。
【００４３】
第２の種類の歪みは、光源１８が、長方形の画像を結像画面１４上に射影するとき視覚的に明らかとなる。これが起こると、長方形は台形に歪んだように見える。「台形歪み」と呼ばれるこの種の歪みが発生する理由は、画面１４上の画像の底部から光源１８の焦点への光学通路が、画面の上部から焦点への光学通路より短いことによる。結果的に、光源１８により射影される画像の上部分は、画像の底部分よりも大きく拡大されてしまう。
【００４４】
台形及び回転歪みを補正する必要がある表示装置に関しては、入口点３６及び射影した出口点４０の円柱座標の計算と、連結線分４２のラスタ化との間に、付加的ステップを実行するのが好ましい。入口点３６及び射影した出口点４０の円柱座標を計算すると、それぞれ角度、半径、及び高さ（θ１，ｒ１，ｈ１）及び（θ２，ｒ２，ｈ２）となる。台形歪みは、ベクトル（ｒ１，ｈ１）及び（ｒ２，ｈ２）に射影演算を行うことにより補正して、ベクトル（ｒ’１，ｈ’１）及び（ｒ’２，ｈ’２）を得る。画面１４上での光源１８の画像の回転は、画面１４中心の周りに反対方向に回転させることで補正する。ベクトル（ｒ’１，ｈ’１）は角度−θ１で回転させ、ベクトル（ｘ１，ｙ１）を得る。ベクトル（ｒ’２，ｈ’２）は角度−θ２で回転させ、ベクトル（ｘ２，ｙ２）を得る。ベクトル（ｘ１，ｙ１）は、回転部分１２が角度θ１まで回転した瞬間に、入口点３６を結像画面１４上に描画するのに必ず照光しなければならない、光源１８上の１点を指定する。ベクトル（ｘ２，ｙ２）は、同様に、回転部分１２が角度θ２まで回転した瞬間に、射影した出口点４０を結像画面１４上に描画するのに必ず照光しなければならない、光源１８上の１点を指定する。連結線分４２は、座標（ｘ１，ｙ１）及び（ｘ２，ｙ２）をエンドポイントとして用いて光源１８上に引く。図１に示したものとは異なる光学通路となるように設計した表示装置では、上述した歪み補正の一方又は他方を必要とすることもあるし、何の補正も必要としないこともある。
【００４５】
添付した付録のソースコードは、上述したラスタ化方法のあるインプリメンテーションを教示したものである。このソースコードでは、変数「ｘ」はベクトルで、「ｑ」で始まる変数は角度である。関数「ｂｒｅｓ２ｄ（ｘ，ｘ＿，ｑ）」は、スライスｑに関連付けられた平面内でｘからｘ＿に延伸する線をラスタ化するための従来のブレセンハムのアルゴリズムをインプリメントし、関数「ａｎｇ＿ａｄｄ（ｑ，ｑ＿）」は、角度ｑにｑ＿を加え、演算「ｘ−＞（ｒ，ｈ）」は、ｒ−ｈ平面内のベクトルをそのｒ成分とｈ成分とに分解し、更に、演算「ｘ＝（ｒ，ｈ）」は、ｒ成分とｈ成分とを備えたベクトルをｒ−ｈ平面内に形成する。
【００４６】
次のソースコードは、射影した座標系を参照する。この射影した座標系は、動軸回転表示及び台形像効果の演算に関して上述した円柱座標系に関連したものである。これら演算は、次のソースコードにおいてイタリック体で示してある。
【００４７】
本発明とその好適な実施形態を説明したが、新規なものと主張し特許証により確保されるものは以下の通りである。
付録
ｌｉｎｅ＿ｐｏｌａｒ＿ｐｏｓ（ｑ， ｄ，ｇａｍｍａ，ｐｈｉ，ｇｓ，ｈ＿ｔ ）
｛
ｔｈ ＝ ａｎｇ＿ａｄｄ（ｑ，−ｐｈｉ）；
ｉｆ（ ｔｈ ＞＝ ＴＲＩＧ＿ＰＩ ）
ｔｈ −＝ ＴＲＩＧ＿ＰＩ；
ｉｆ（ ｔｈ＜ＴＲＩＧ＿ＰＩ＿２ ）
ｓｅｃ＿ｔａｎ ＝ ｓｅｃ＿ｔａｎ＿ｔａｂｌｅ［ｔｈ］；
ｅｌｓｅ
ｓｅｃ＿ｔａｎ ＝ ｓｅｃ＿ｔａｎ＿ｔａｂｌｅ［ＴＲＩＧ＿ＰＩ−１−ｔｈ］；
ｓｅｃ＿ｔａｎ −＞ （ｓｅｃ，ｔａｎ）；
／＊ ｔｍｐ ＝ ｇａｍｍａ＊ｔａｎ（ｔｈｅｔａ） ＊／
ｔｍｐ ＝ ｇａｍｍａ＊ｔａｎ；
ｉｆ（ ｔｈ＞＝ＴＲＩＧ＿ＰＩ＿２ ）
ｔｍｐ＝−ｔｍｐ；
／＊ ｒ ＝ ａｂｓ（ｄ＊ｓｅｃ（ｔｈｅｔａ）） ＊／
／＊ ｈ ＝ （（ｇａｍｍａ＊ｔａｎ（ｔｈｅｔａ））＞＞ｇｓ） ＋ ｈ＿ｔ ＊／
ｒ ＝ （ｄ＊ｓｅｃ）＞＞（１＋＿ｈｅ＿ｔａｎ＿ｓｈｉｆｔ）；
ｈ ＝ （（（ｇａｍｍａ＊ｔａｎ）＞＞ｇｓ） ＋ ｈ＿ｔ）＜＜１６；
ｒｅｔｕｒｎ （ｒ，ｈ）；
｝
／＊射影した座標空間内の線上の位置を計算する＊／
ｌｉｎｅ＿ｐｏｓ（ ｑ， ｄ，ｇａｍｍａ，ｐｈｉ，ｇｓ，ｈ＿ｔ）
｛
ｘ ＝ ｌｉｎｅ＿ｐｏｌａｒ＿ｐｏｓ（ｑ，ｄ，ｇａｍｍａ，ｐｈｉ，ｇｓ，ｈ＿ｔ）；
ｃｙｌｎ２ｐｒｏｊｅｃｔｅｄ（ｑ，ｘ）；
ｒｅｔｕｒｎ （ｘ）；
｝
／＊スライスを進め、状態を維持する＊／
ｎｅｘｔ＿ｓｌｉｃｅ（ ＊ｑ， ＊ｘ， ｘ＿ ）
｛
／＊スライス番号をインクリメントする＊／
＊ｑ ＝ ａｎｇ＿ｓｌｉｃｅ＿ｉｎｃ（＊ｑ）；
／＊次のスライスのリーディングエッジが、このスライスのトレーリングエッジである＊／
ｉｆ（ ｓｌｉｃｅ＿ｎｕｍｂｅｒ（＊ｑ） ＝＝ ０ ）
＊ｘ ＝ （ｘ＿＾０ｘｆｆｆｆ００００）＋０ｘ０００１００００； ／＊ｈを否定してＰｉジャンプを補正する＊／
ｅｌｓｅ
＊ｘ ＝ ｘ＿；
｝
ｌｉｎｅ＿ｓｕｂ（ ｑ， ｑ＿ｅｎｄ， ｘ０， ｘ１， ｄ，ｇａｍｍａ，ｐｈｉ，ｇｓ，ｈ＿ｔ ）
｛
ｘ０ ＝ ｃｙｌｎ２ｐｒｏｊｅｃｔｅｄ（ｑ， ｘ０）；
ｘ１ ＝ ｃｙｌｎ２ｐｒｏｊｅｃｔｅｄ（ｑ＿ｅｎｄ，ｘ１）；
／＊線の第１頂点＊／
ｉｆ（ ｑ！＝ｑ＿ｅｎｄ ）
ｌｉｎｅ＿ｎｅｘｔ＿ｓｌｉｃｅ（＆ｑ，＆ｘ，ｘ０）；
ｅｌｓｅ
ｘ ＝ ｘ０；
／＊線の中間スライスを描く＊／
ｗｈｉｌｅ（ｑ！＝ｑ＿ｅｎｄ） ｛
ｘ＿ ＝ ｒｅ＿ｌｉｎｅ＿ｐｏｓ（ｑ， ｄ，ｇａｍｍａ，ｐｈｉ，ｇｓ，ｈ＿ｔ）；
ｂｒｅｓ２ｄ（ｑ，ｘ，ｘ＿）；
ｌｉｎｅ＿ｎｅｘｔ＿ｓｌｉｃｅ（＆ｑ，＆ｘ，ｘ＿）；
｝
／＊線の最終スライスを描く＊／
ｘ＿ ＝ ｘ１；
ｂｒｅｓ２ｄ （ｑ，ｘ，ｘ＿）；
｝
／＊円柱線座標定数ｄ、γ、φ、ｇｓ、ｈ＿ｔを用いて、円柱（射影）座標において（ｑ０，ｘ０）から（ｑ１，ｘ１）へ線を引く＊／
ｌｉｎｅ（ｑ０，ｘ０， ｑ１，ｘ１， ｄ，ｇａｍｍａ，ｐｈｉ，ｇｓ，ｈ＿ｔ）
｛
／＊フロントスキャン＊／
ｑ ＝ ｑ０；
ｑ＿ｅｎｄ ＝ ｑ１；
ｌｉｎｅ＿ｓｕｂ（ｑ，ｑ＿ｅｎｄ，ｘ０，ｘ１， ｄ，ｇａｍｍａ，ｐｈｉ，ｇｓ，ｈ＿ｔ）；
／＊バックスキャン＊／
ｑ ＝ ａｎｇ＿ｆｉｘｕｐ（ｑ ＋ＴＲＩＧ＿ＰＩ）；
ｑ＿ｅｎｄ ＝ ａｎｇ＿ｆｉｘｕｐ（ｑ＿ｅｎｄ＋ＴＲＩＧ＿ＰＩ）；
ｌｉｎｅ＿ｓｕｂ（ｑ，ｑ＿ｅｎｄ，ｘ０，ｘ１， ｄ，ｇａｍｍａ，ｐｈｉ，ｇｓ，ｈ＿ｔ）；
｝
「射影した」座標系と共に使用する追加サブルーチン
ｌｉｎｅ＿ｄｅｋｅｙｓｔｏｎｅ（ｘ）
｛
ｘ −＞ （＿ｘｘ，＿ｙｙ）； ／＊ｘベクトルを（ｘ，ｙ）成分に解読する＊／
ｉｎｔ ｉ ＝ （（＿ｙｙ ＋ （ＦＢ＿ＹＬＩＮＥＳ＜＜５）） ＞＞ ６） ＜＜ １； ／＊ キーテーブル中の索引 ＊／
／＊ｉをテーブルサイズまで切り取る＊／
ｉｆ（ｉ＞１５３４）
ｉ＝１５３４；
ｅｌｓｅ ｉｆ（ｉ＜０）
ｉ＝０；
ｘｘ ＝ （（＿ｘｘ＊ｋｅｙ＿ｔａｂｌｅ［ｉ］） ＞＞ ｋｅｙ＿ｓｈｉｆｔ） ＋ ｃｘ＿ｉｋｅｙ；
ｙｙ ＝ （（＿ｙｙ＊ｋｅｙ＿ｔａｂｌｅ［ｉ＋１］） ＞＞ ｋｅｙ＿ｓｈｉｆｔ） ＋ ｃｙ＿ｉｋｅｙ；
ｒｅｔｕｒｎ （ｘｘ，ｙｙ）；
｝
ｌｉｎｅ＿ｄｅｔｕｍｂｌｅ（ｑ， ｘ）
｛
ｘ −＞ （ｒ，ｈ）； ／＊ ｘベクトルのｒとｈ部分を抽出する ＊／
／＊２ｄ回転：　　　　　　　　　　　 ＊／
／＊ ｘ ＝ ｒ＊ｃｏｓ（ｔｈ） ＋ ｈ＊ｓｉｎ（ｔｈ） ＊／
／＊ ｙ ＝ ｈ＊ｃｏｓ（ｔｈ） − ｒ＊ｓｉｎ（ｔｈ） ＊／
ｉｆ（ｑ＞＝ＴＲＩＧ＿ＰＩ） ｛
ｒ＝ −ｒ； ／＊ Ｐｉ．．２Ｐｉは、ｒが否定された状態で０．．Ｐｉにマッピングされる＊／
ｑ −＝ ＴＲＩＧ＿ＰＩ；
｝
／＊−ｑで回転させる＊／
ｘ１ ＝ ｒ＊ｃｏｓ（ｑ）；
ｘ２ ＝ −ｈ＊ｓｉｎ（ｑ）；
ｙ１ ＝ ｈ＊ｃｏｓ（ｑ）；
ｙ２ ＝ ｒ＊ｓｉｎ（ｑ）；
ｘｘ ＝ （ｘ１＋ｘ２）＞＞１５； ／＊ ｓｉｎ／ｃｏｓテーブルは、１５の少数ビットを備える＊／
ｙｙ ＝ （ｙ１＋ｙ２）＞＞１５；
ｒｅｔｕｒｎ （ｘｘ，ｙｙ）；
｝
ｃｙｌｎ２ｐｒｏｊｅｃｔｅｄ（ｑ，ｘ）
｛
ｘ＿ ＝ｌｉｎｅ＿ｄｅｋｅｙｓｔｏｎｅ（ｘ）；
ｘ＿＿＝ｌｉｎｅ＿ｄｅｔｕｍｂｌｅ（ｑ，ｘ＿）；
ｒｅｔｕｒｎ ｘ＿＿；
｝
【図面の簡単な説明】
【図１】
立体表示装置である。
【図２】
表示立体領域の平面図である。
【図３】
３次元空間において線をラスタ化する一方法を示す。
【図４】
３次元空間において線をラスタ化する一方法を示す。
【図５】
３次元空間において線をラスタ化する第２の方法を示す。
【図６】
３次元空間において線をラスタ化する第２の方法を示す。
【図１】
2004508640.tif 000009
【国際公開パンフレット】
2004508640.tif 000010
2004508640.tif 000011
2004508640.tif 000012
2004508640.tif 000013
2004508640.tif 000014
2004508640.tif 000015
2004508640.tif 000016
2004508640.tif 000017
2004508640.tif 000018
2004508640.tif 000019
2004508640.tif 000020
2004508640.tif 000021
2004508640.tif 000022
2004508640.tif 000023
2004508640.tif 000024
2004508640.tif 000025
2004508640.tif 000026
2004508640.tif 000027
2004508640.tif 000028
2004508640.tif 000029
2004508640.tif 000030
2004508640.tif 000031
2004508640.tif 000032
2004508640.tif 000033
【国際公開パンフレット（コレクトバージョン）】
2004508640.tif 000034
【国際公開パンフレット（コレクトバージョン）】
2004508640.tif 000035
2004508640.tif 000036
2004508640.tif 000037
2004508640.tif 000038
2004508640.tif 000039
2004508640.tif 000040
2004508640.tif 000041
2004508640.tif 000042
2004508640.tif 000043
2004508640.tif 000044
2004508640.tif 000045
2004508640.tif 000046
2004508640.tif 000047
2004508640.tif 000048
2004508640.tif 000049
2004508640.tif 000050
2004508640.tif 000051
2004508640.tif 000052
2004508640.tif 000053
2004508640.tif 000054
2004508640.tif 000055
2004508640.tif 000056
2004508640.tif 000057
2004508640.tif 000058
2004508640.tif 000059
【国際調査報告】
2004508640.tif 000060
2004508640.tif 000061
2004508640.tif 000062