(57)【要約】【課題】少ないメモリで、描画順序の影響を受けず、描画速度の低下を招くことなく、正確なアンチエイリアス処理を実現できる画像処理装置およびその方法を提供する。【解決手段】エッジ情報を描画後の画像からエッジ情報を得、アンチエイリアスのために必要な処理内容を決定し、決定した処理を行うアンチエイリアス処理系２００を有する。描画時に得られたｚバッファの情報と各ピクセルにおける法線ベクトルの情報のどちらか、あるいはその両方の情報をスキャンし、あるいはｚバッファの情報から復元された法線ベクトルの情報を使い、状態を保持するステートマシーンとエッジの連続を測るカウンタを規定し、各エッジ上のピクセルに対して、それぞれ、どの方向のとなりのピクセルのピクセル値と、どれくらいの割合でブレンドすべきかを決定し、決定された値を使ってブレンド処理を行い、ピクセル値が更新されるところまで、スキャンの間に逐次行う。【選択図】      図１２
2005100177.tif 000002
【特許請求の範囲】
【請求項１】
スクリーン座標系の描画対象領域内に、ピクセルデータを発生してメモリに対してレンダリング処理を行い、上記メモリに描画された画像を生成する場合に、エッジ情報を生成してアンチエイリアス処理を行う画像処理装置であって、
上記メモリに描画される所定のピクセルデータに基づいて上記エッジ情報を抽出するエッジ情報抽出手段と、
上記エッジ情報抽出手段で得られたエッジ情報に基づいてアンチエイリアスのために必要な処理内容を決定し、決定した処理を行うアンチエイリアス処理手段と
を有する画像処理装置。
【請求項２】
上記アンチエイリアス処理手段は、各エッジ上のピクセルに対してブレンドのための隣接するピクセルと、ブレンドする割合とを決定し、上記決定したピクセルおよび値に基づいてブレンド処理を行う
請求項１記載の画像処理装置。
【請求項３】
上記アンチエイリアス処理手段は、上記エッジ情報から処理中のピクセルがどのような形のパターンのどの位置にいるのかを示す第１の手段と、エイリアスパターンの開始点からエッジが逆転する変節点までの長さ、上記変節点からエイリアスパターンが終了するまでの長さをそれぞれ測定する第２の手段とを含み、上記第１の手段と第２の手段の情報に基づいてブレンド対象のピクセルの位置と当該ブレンドの係数を計算する
請求項２記載の画像処理装置。
【請求項４】
上記メモリに描画されるピクセルデータには奥行き情報を含み、
上記エッジ情報抽出手段は、上記奥行き情報が格納された上記メモリの奥行き情報バッファをスキャンした結果得られた奥行き情報の２階微分値を求め、当該２階微分値に基づいてエッジ情報を抽出する
請求項３記載の画像処理装置。
【請求項５】
上記メモリへの描画時に生成されるデータにピクセル毎の法線ベクトルを含み、上記メモリには法線ベクトルが格納される法線ベクトルバッファが形成され、
上記エッジ情報抽出手段は、上記法線ベクトルバッファに格納された上記ピクセル毎の法線ベクトルをスキャンした結果得られた法線ベクトルに基づいてエッジ情報を抽出する
請求項３記載の画像処理装置。
【請求項６】
上記メモリに描画されるピクセルデータには奥行き情報を含み、
上記エッジ情報抽出手段は、上記奥行き情報が格納された上記メモリの奥行き情報バッファをスキャンした結果得られた奥行き情報とスクリーン座標からピクセル毎の法線ベクトルを復元し、復元した法線ベクトルに基づいてエッジ情報を抽出する
請求項３記載の画像処理装置。
【請求項７】
上記エッジ情報抽出手段は、注目するライン近傍の複数のラインのエッジ情報を抽出する
請求項４記載の画像処理装置。
【請求項８】
上記エッジ情報抽出手段は、注目するライン近傍の複数のラインのエッジ情報を抽出する
請求項５記載の画像処理装置。
【請求項９】
上記エッジ情報抽出手段は、注目するライン近傍の複数のラインのエッジ情報を抽出する
請求項６記載の画像処理装置。
【請求項１０】
スクリーン座標系の描画対象領域内に、ピクセルデータを発生してメモリに対してレンダリング処理を行い、上記メモリに描画された画像を生成する場合に、エッジ情報を生成してアンチエイリアス処理を行う画像処理方法であって、
上記メモリに描画される所定のピクセルデータに基づいて上記エッジ情報を抽出する第１ステップと、
上記第１ステップで得られたエッジ情報に基づいてアンチエイリアスのために必要な処理内容を決定し、決定した処理を行う第２ステップと
を有する画像処理方法。
【請求項１１】
上記第２ステップでは、各エッジ上のピクセルに対してブレンドのための隣接するピクセルと、ブレンドする割合とを決定し、上記決定したピクセルおよび値に基づいてブレンド処理を行う
請求項１０記載の画像処理方法。
【請求項１２】
上記第２のステップは、
上記エッジ情報から処理中のピクセルがどのような形のパターンのどの位置にいるのかを示す第３にステップと、
エイリアスパターンの開始点からエッジが逆転する変節点までの長さ、変節点からエイリアスパターンが終了するまでの長さをそれぞれ測定する第４ステップとを含み、
上記第３ステップと第４ステップ情報に基づいてブレンド対象のピクセルの位置と当該ブレンドの係数を計算する
請求項１１記載の画像処理方法。
【請求項１３】
上記メモリに描画されるピクセルデータには奥行き情報を含み、
上記第１ステップでは、上記奥行き情報が格納された上記メモリの奥行き情報バッファをスキャンし、得られた奥行き情報の２階微分値を求め、当該２階微分値に基づいてエッジ情報を抽出する
請求項１２記載の画像処理方法。
【請求項１４】
上記メモリへの描画時に生成されるデータにピクセル毎の法線ベクトルを含み、上記メモリには法線ベクトルが格納される法線ベクトルバッファを形成し、
上記第１ステップでは、上記法線ベクトルバッファに格納された上記ピクセル毎の法線ベクトルをスキャンし、得られた法線ベクトルに基づいてエッジ情報を抽出する
請求項１２記載の画像処理方法。
【請求項１５】
上記メモリに描画されるピクセルデータには奥行き情報を含み、
上記第１ステップでは、上記奥行き情報が格納された上記メモリの奥行き情報バッファをスキャンした結果得られた奥行き情報とスクリーン座標からピクセル毎の法線ベクトルを復元し、復元した法線ベクトルに基づいてエッジ情報を抽出する
請求項１２記載の画像処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、モデルを単位図形の組み合わせによって表現し、スクリーン座標系の描画対象領域内に、ピクセルデータを発生してメモリに対してレンダリング処理を行い、画像を生成する場合に、エッジ情報を生成してアンチエイリアス処理を行う画像処理装置およびその方法に関するものである。
【背景技術】
【０００２】
昨今のコンピュータシステムにおける演算速度の向上や描画機能の強化とも相俟って、コンピュータ資源を用いて図形や画像の作成や処理を行う「コンピュータ・グラフィックス（ＣＧ）」技術が盛んに研究・開発され、さらに実用化されている。
【０００３】
たとえば、３次元グラフィックスは、３次元オブジェクトが所定の光源によって照らされたときの光学現象を数学モデルで表現して、このモデルに基づいてオブジェクト表面に陰影や濃淡を付けたり、さらには模様を貼り付けたりして、よりリアルで３次元的な２次元高精細画像を生成するものである。
このようなコンピュータ・グラフィックスは、科学、工学、製造などの開発分野でのＣＡＤ／ＣＡＭ、その他の各種応用分野においてますます盛んに利用されるようになってきている。
【０００４】
３次元グラフィックスは、一般には、フロントエンドとして位置づけられる「ジオメトリ・サブシステム」と、バックエンドとして位置づけられる「ラスタ・サブシステム」とにより構成される。
【０００５】
ジオメトリ・サブシステムとは、ディスプレイ・スクリーン上に表示する３次元オブジェクトの位置や姿勢などの幾何学的な演算処理を行う過程のことである。
ジオメトリ・サブシステムでは、一般にオブジェクトは多数のポリゴンの集合体として扱われ、ポリゴン単位で、「座標変換」、「クリッピング」、「光源計算」などの幾何学的な演算処理が行われる。
【０００６】
一方、ラスタ・サブシステムは、オブジェクトを構成する各ピクセル（ｐｉｘｅｌ）を塗りつぶす過程のことである。
ラスタライズ処理は、たとえばポリゴンの頂点毎に求められた画像パラメータを基にして、ポリゴン内部に含まれるすべてのピクセルの画像パラメータを補間することによって実現される。
ここで言う画像パラメータには、いわゆるＲＧＢ形式などで表される色（描画色）データ、奥行き方向の距離を表すｚ値などがある。
また、最近の高精細な３次元グラフィックス処理では、遠近感を醸し出すためのｆ（ｆｏｇ：霧）や、物体表面の素材感や模様を表現してリアリティを与えるテクスチャｔ（ｔｅｘｔｕｒｅ）なども、画像パラメータの１つとして含まれている。
【０００７】
ここで、ポリゴンの頂点情報からポリゴン内部のピクセルを発生する処理では、よくＤＤＡ（Ｄｉｇｉｔａｌ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ａｎａｌｙｚｅｒ）と呼ばれる線形補間手法を用いて実行される。
ＤＤＡプロセスでは、頂点情報からポリゴンの辺方向へのデータの傾きを求め、この傾きを用いて辺上のデータを算出した後、続いてラスタ走査方向（Ｘ方向）の傾きを算出し、この傾きから求めたパラメータの変化分を走査の開始点のパラメータ値に加えていくことで、内部のピクセルを発生していく。
【０００８】
そして、３次元コンピュータグラフィックスでは、各ピクセルに対応する色を決定するときに、各ピクセルの色の計算をし、この計算した色の値を、当該ピクセルに対応するディスプレイバッファ（フレームバッファ）のアドレスに書き込むレンダリング（Ｒｅｎｄｅｒｉｎｇ）処理を行う。
【０００９】
このようなコンピュータグラフィクス処理により生成した画像は、直線、多角形エッジ、色の境界等が不連続であるエイリシアング効果が発生することから、視覚的な解像度を高めるためにアンチエイリアスなどの画像処理を行う。アンチエイリアス処理を行うには、エッジ情報の抽出が必要となる。
【００１０】
従来、エッジの抽出方法としては、生成した映像からフィルタリングだけでエッジを抽出する方法や、ポリゴンをアウトラインで書いてエッジを出す方法等がある。
また、アンチエイリアスの手法としては、スーパーサンプリング（Ｓｕｐｅｒ  Ｓａｍｐｌｉｎｇ）法や、ピクセル毎にカバレージ（ｃｏｖｅｒａｇｅ）を出す方法等がある。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
ところが、フィルタリングだけでエッジを抽出する方法は、３次元コンピュータグラフィックスの画像であるという利点、すなわち画像生成時に有用なデータが発生する等を利用していないために、ある程度のエッジ情報は得られるが、アンチエイリアス処理に利用できるほど正確なエッジ情報を取り出すことができない。
【００１２】
ポリゴンをアウトラインで書いてエッジを出す方法では、ポリゴン単位で、その周辺のエッジをすべて書き出すので、本来必要な描画ピクセルの他に、その周りのピクセルのレ
ンダリングが必要である。その部分で、描画速度の低下を招く。また、せっかくレンダリングされたポリゴンのエッジの大半は描画オブジェクトのエッジではなく、また、他のポリゴンで上書きされるなどして、無駄になっている。
【００１３】
また、アンチエイリアシングの手法としてのスーパーサンプリングの方法は、大量の点に描画して、後でローパスフィルタ（ＬＰＦ）をかけるという方法であり、この方法では、サンプル数を増やせばそれだけクオリティは向上するが、その分莫大なメモリが必要となる。また、サンプル数を増やすと、その数だけレンダリングする必要があり、描画速度にも重大な低下を引き起こす。
【００１４】
また、ピクセル毎にカバレージを出す方法は、スーパーサンプリングの手法に比べて必要となるメモリは少ないが、描画順序の影響が大きく、ポリゴンの描画順序が悪いと正確なアンチエイリアス処理ができないため、Ｚソートの手法が必要となる。また、Ｚソート
を行ったとしても、いつまでも背景が残るなどの問題がある。たとえばトライアングルファン（Ｔｒｉａｎｇｌｅ  Ｆａｎ）の中心では、そのような問題が発生する。
【００１５】
本発明の第１の目的は、本来必要な描画ピクセルの他に回りのピクセルのレンダリングが不要で、描画速度の低下を招くことなく、アンチエイリアス処理に利用できるほど正確なエッジ情報を取り出すことができる画像処理装置およびその方法を提供することにある。
【００１６】
本発明の第２の目的は、少ないメモリで、描画順序の影響を受けず、描画速度の低下を招くことなく、正確なアンチエイリアス処理を実現できる画像処理装置およびその方法を提供することにある。
【課題を解決するための手段】
【００１７】
上記目的を達成するため、本発明の第１の観点は、スクリーン座標系の描画対象領域内に、ピクセルデータを発生してメモリに対してレンダリング処理を行い、上記メモリに描画された画像を生成する場合に、エッジ情報を生成してアンチエイリアス処理を行う画像処理装置であって、上記メモリに描画される所定のピクセルデータに基づいて上記エッジ情報を抽出するエッジ情報抽出手段と、上記エッジ情報抽出手段で得られたエッジ情報に基づいてアンチエイリアスのために必要な処理内容を決定し、決定した処理を行うアンチエイリアス処理手段とを有する。
【００１８】
好適には、上記アンチエイリアス処理手段は、各エッジ上のピクセルに対してブレンドのための隣接するピクセルと、ブレンドする割合とを決定し、上記決定したピクセルおよび値に基づいてブレンド処理を行う。
【００１９】
好適には、上記アンチエイリアス処理手段は、上記エッジ情報から処理中のピクセルがどのような形のパターンのどの位置にいるのかを示す第１の手段と、エイリアスパターンの開始点からエッジが逆転する変節点までの長さ、上記変節点からエイリアスパターンが終了するまでの長さをそれぞれ測定する第２の手段とを含み、上記第１の手段と第２の手段の情報に基づいてブレンド対象のピクセルの位置と当該ブレンドの係数を計算する。
【００２０】
好適には、上記メモリに描画されるピクセルデータには奥行き情報を含み、上記エッジ情報抽出手段は、上記奥行き情報が格納された上記メモリの奥行き情報バッファをスキャンした結果得られた奥行き情報の２階微分値を求め、当該２階微分値に基づいてエッジ情報を抽出する。
【００２１】
好適には、上記メモリへの描画時に生成されるデータにピクセル毎の法線ベクトルを含み、上記メモリには法線ベクトルが格納される法線ベクトルバッファが形成され、上記エッジ情報抽出手段は、上記法線ベクトルバッファに格納された上記ピクセル毎の法線ベクトルをスキャンした結果得られた法線ベクトルに基づいてエッジ情報を抽出する。
【００２２】
好適には、上記メモリに描画されるピクセルデータには奥行き情報を含み、上記エッジ情報抽出手段は、上記奥行き情報が格納された上記メモリの奥行き情報バッファをスキャンした結果得られた奥行き情報とスクリーン座標からピクセル毎の法線ベクトルを復元し、復元した法線ベクトルに基づいてエッジ情報を抽出する。
【００２３】
好適には、上記エッジ情報抽出手段は、注目するライン近傍の複数のラインのエッジ情報を抽出する。
【００２４】
本発明の第２の観点は、スクリーン座標系の描画対象領域内に、ピクセルデータを発生してメモリに対してレンダリング処理を行い、上記メモリに描画された画像を生成する場合に、エッジ情報を生成してアンチエイリアス処理を行う画像処理方法であって、
上記メモリに描画される所定のピクセルデータに基づいて上記エッジ情報を抽出する第１ステップと、上記第１ステップで得られたエッジ情報に基づいてアンチエイリアスのために必要な処理内容を決定し、決定した処理を行う第２ステップとを有する。
【００２５】
本発明によれば、たとえばエッジ情報抽出手段により奥行き情報のメモリに対する描画終了後に、奥行き情報バッファがスキャンされ、スキャンして得られた奥行き情報の２階微分値を求められる。
そして、設定されたしきい値と求めた２階微分値との比較によりエッジであるか否かの評価が行われる。
すなわち、本発明によれば、通常の３次元コンピュータグラフィックス描画時に本来必要であり、描画されたときには情報として残っているにもかかわらず従来はその後使われなかった情報、たとえば奥行き（ｚ）バッファの情報を利用してたとえば描画後にエッジ情報を抽出する。
また、本発明によれば、通常の３次元コンピュータグラフィックス描画では残らない情報、たとえば、ピクセルごとの法線ベクトルの情報等を取っておいて、後段で使う、または、後段のエッジ抽出のために必要な情報を描画時に作り出して残しておく。
そして、アンチエイリアス処理手段において、各エッジ上のピクセルに対してそれぞれ、どの方向の隣接するピクセルのピクセル値と、ブレンドする割合が決定され、決定した値に基づくブレンド処理が行われる。
【発明の効果】
【００２６】
本発明によれば、本来必要な描画ピクセルの他に回りのピクセルのレンダリングが不要で、描画速度の低下を招くことなく、アンチエイリアス処理に利用できるほど正確なエッジ情報を取り出すことができる。
また、少ないメモリで、描画順序の影響を受けず、描画速度の低下を招くことなく、正確なアンチエイリアス処理を実現できる利点がある。
【発明を実施するための最良の形態】
【００２７】
以下、本実施形態においては、パーソナルコンピュータなどに適用される、任意の３次元物体モデルに対する所望の３次元画像をＣＲＴ(Cathode Ray Tube)などのディスプレイ上に高速に表示する３次元コンピュータグラフィックスシステムについて説明する。
【００２８】
図１は、本発明に係る画像処理装置としての３次元コンピュータグラフィックスシステム１０のシステム構成図である。
【００２９】
３次元コンピュータグラフィックスシステム１０は、立体モデルを単位図形である三角形（ポリゴン）の組み合わせとして表現し、このポリゴンを描画することで表示画面の各画素の色を決定し、ディスプレイに表示するポリゴンレンダリング処理を行うシステムである。
また、３次元コンピュータグラフィックスシステム１０では、平面上の位置を表現する（ｘ，ｙ）座標の他に、奥行きを表すｚ座標を用いて３次元物体を表し、この（ｘ，ｙ，ｚ）の３つの座標で３次元空間の任意の一点を特定する。
【００３０】
また、３次元コンピュータグラフィックスシステム１０は、コンピュータグラフィクスで生成した画像に対してアンチエイリアスなどの画像処理を行う。この場合において、通常の画像を処理する場合には利用できない、有用な情報がコンピュータグラフィクス（ＣＧ）画像の生成過程において多数発生する。本実施形態においては、それら有用な情報を再利用あるいは加工して、画像内のオブジェクトの境界や方向が急峻に変化する表面を示すエッジ情報を正確に取り出す方法を示す。
本実施形態においては、２種類の方法を示す。詳細については後述する。
第１番目の方法は、通常の３次元コンピュータグラフィックス描画時に本来必要であり、描画されたときには情報として残っているにもかかわらず従来はその後使われなかった情報、たとえばｚバッファの情報を利用して描画後にエッジ情報を抽出する方法である。ｚバッファの情報は色情報とともに３次元コンピュータグラフィックスでは描画されるものであるが、従来は色情報は後段に流されて使われるがｚ情報（ｚ値）は、その後使われることなく捨てられていた。本実施形態においては、そのｚバッファの情報を後段において再利用する。
第２番目の方法は、通常の３次元コンピュータグラフィックス描画では残らない情報、たとえば、ピクセルごとの法線ベクトルの情報や、ポリゴンの傾きの情報を取っておいて、後段で使う方法、または、後段のエッジ抽出のために必要な情報を描画時に作り出して残しておくという方法である。この方法は後段の処理に対して、やるべきことを示す、という意味で、「命令」または「operation code」「オペコード」をレンダリングしておく、と解釈することもできる。これらの情報は３次元コンピュータグラフィックス独特の情報である。描画時に持っている情報を、後段の画像処理で使えるようにうまく加工して後段へ流す手法であるとも言える。
【００３１】
ｚバッファを使う方法では、ピクセル単位で、その２階微分を計算してエッジ抽出に使う。
法線ベクトルを使う方法では、ピクセル単位に、隣り合うピクセル同士の法線ベクトルの内積を計算して、その大きさからエッジであるかどうかを判断する。
さらに、ｚバッファの情報だけから、ピクセルのスクリーン座標を使って法線ベクトルの情報を各ピクセルで復元して使う方法も採用可能である。
さらに、この手法で見つけたエッジ部分だけにスーパーサンプリングなどの手法を用いる方法も採用可能である。
【００３２】
また、３次元コンピュータグラフィックスシステム１０は、アンチエイリアス処理を行
う場合、一般に用いられている手法とは異なり、描画時に各ピクセルのカバレージを計算、格納することは行わない。マルチサンプリング、スーパーサンプリングのような手法も使わない。
すなわち、３次元コンピュータグラフィックスシステム１０は、コンピュータグラフィックス画像の生成終了後の後処理としてアンチエイリアス処理を行う。
コンピュータグラフィックス画像生成の終了後に後処理としてエッジを抽出し、そのエッジ情報を利用してアンチエイリアス処理を行う。
エッジ情報からエッジのパターンを割り出し、そのパターンに合わせてピクセルに対して処理を行う。本実施形態においては、書き込まれた（打ち込まれた）ピクセルの周りのピクセルに対してブレンド処理を行うだけでなく、オブジェクトと背景の両方に対して対称的にブレンド処理を行う。カバレージで言うと１００％として書き込まれた（打ち込まれた）ピクセルもブレンド処理を受けることがある。
パターン抽出時には、ステートマシーン（StateMachine）とカウンタを用いて、直線的に長いエッジに対応できる。
エッジのパターンとしては、アンチエイリアス処理が必要なパターンだけを扱う。エッジが重なったパターンも扱う。
本実施形態では、ｚバッファなどの情報をピクセル単位でスキャンしながら、同時にアンチエイリアス処理も進行させていく、という実装方法も示す。
【００３３】
必要な処理は以下のとおりである。
１）スクリーン座標でのｘ方向、ｙ方向それぞれに関するエッジ情報を描画後の画像から復元する。
２）得られたエッジ情報から、アンチエイリアス（anti-aliasing）のために必要な処
理内容を決定する。
３）決定された処理を行う。
【００３４】
本実施形態では、描画時に得られたｚバッファの情報と各ピクセルにおける法線ベクトルの情報のどちらか、あるいはその両方の情報をスキャンすることにより、あるいはｚバッファの情報から復元された法線ベクトルの情報を使ってアンチエイリアス処理を各ピクセルに施して行くという手法を採用する。
各スキャンにおいて、状態を保持する第１の手段としてのステートマシーンとエッジの連続を測る第２の手段としてのカウンタを規定する。その２つの素子により各エッジ上のピクセルに対して、それぞれ、どの方向のとなりのピクセルのピクセル値と、どれくらいの割合でブレンドすべきかを決定する。そして、決定された値を使ってブレンド処理が行われ、ピクセル値が更新されるところまでが、上記スキャンの間に逐次行われる。
この方法によれば、アンチエイリアス処理の目的で増加すべきメモリ量は少なくてすみ、描画時にパフォーマンスを下げるような処理は追加されない。
【００３５】
以下、上記のように構成される３次元コンピュータグラフィックスシステム１０の各部の具体的な構成および機能について順を追って説明する。
【００３６】
図１に示すように、３次元コンピュータグラフィックスシステム１０は、メインプロセッサ１１、メインメモリ１２、Ｉ／Ｏインタフェース回路１３、およびレンダリング回路１４が、メインバス１５を介して接続され、レンダリング回路１４とＣＲＴコントロール回路１６とが接続されている。なお、図１においては、レンダリング回路１４の外部にＣＲＴコントロール回路１６を設けているが、レンダリング回路１４内に設ける構成等も採用可能である。
これらの構成要素のうち、レンダリング回路１４または／およびＣＲＴコントロール回路１６が本発明のエッジ情報抽出手段、およびアンチエイリアス処理手段を構成する。
以下、各構成要素の機能について説明する。
【００３７】
メインプロセッサ１１は、たとえば、アプリケーションの進行状況などに応じて、メインメモリ１２から必要なグラフィックデータを読み出し、このグラフィックデータに対して、座標変換、クリッピング(Clipping)処理、ライティング(Lighting)処理などのジオメトリ(Geometry)処理などを行い、ポリゴンレンダリングデータを生成する。
メインプロセッサ１１は、ポリゴンレンダリングデータＳ１１を、メインバス１５を介してレンダリング回路１４に出力する。
【００３８】
Ｉ／Ｏインタフェース回路１３は、必要に応じて、外部から動きの制御情報またはポリゴンレンダリングデータなどを入力し、これをメインバス１５を介してレンダリング回路１４に出力する。
【００３９】
レンダリング回路１４に入力されるポリゴンレンダリングデータは、ポリゴンの各３頂点の（ｘ，ｙ，ｚ，Ｒ，Ｇ，Ｂ，α，ｓ，ｔ，ｑ）のデータを含んでいる。
ここで、（ｘ，ｙ，ｚ）データは、ポリゴンの頂点の３次元座標を示し、（Ｒ，Ｇ，Ｂ）データは、それぞれ当該３次元座標における赤、緑、青の輝度値を示している。
また、αはブレンド値（係数）を示している。
（ｓ，ｔ，ｑ）データのうち、（ｓ，ｔ）は、対応するテクスチャの同次座標を示しており、ｑは同次項を示している。ここで、「ｓ／ｑ」および「ｔ／ｑ」に、それぞれテクスチャサイズＵＳＩＺＥおよびＶＳＩＺＥを乗じて、実際のテクスチャ座標データ（ｕ，ｖ）が得られる。
レンダリング回路１４のグラフィックスメモリ（具体的には後記するテクスチャバッファ）に記憶されたテクスチャデータへのアクセスは、テクスチャ座標データ（ｕ，ｖ）を用いて行われる。
すなわち、ポリゴンレンダリングデータは、三角形の各頂点の物理座標値と、それぞれの頂点の色とテクスチャデータである。
【００４０】
レンダリング回路１４は、図１に示すように、線形補間演算のための初期設定演算ブロックとしてのＤＤＡ(Digital Differential Analyzer) セットアップ回路１４１、線形補間処理ブロックとしてのトライアングルＤＤＡ回路１４２、テクスチャエンジン回路１４３、メモリインタフェース（Ｉ／Ｆ）回路１４４、およびたとえばＤＲＡＭからなるグラフィックスメモリ１４５を有している。そして、テクスチャエンジン回路１４３、およびメモリインタフェース（Ｉ／Ｆ）回路１４４により処理回路が構成される。
【００４１】
ＤＤＡセットアップ回路１４１は、後段のトライアングルＤＤＡ回路１４２において物理座標系上の三角形の各頂点の値を線形補間して、三角形の内部の各画素の色と深さ情報を求めるに先立ち、ポリゴンレンダリングデータＳ１１が示す（ｚ，Ｒ，Ｇ，Ｂ，α，ｓ，ｔ，ｑ）データについて、三角形の辺と水平方向の差分などを求めるセットアップ演算を行う。
このセットアップ演算は、具体的には、開始点の値と終点の値と、開始点と終点との距離を用いて、単位長さ移動した場合における、求めようとしている値の変分を算出する。
ＤＤＡセットアップ回路１４１は、算出した変分データを含むプリミティブに関する情報としてのセットアップデータＳ１４１をトライアングルＤＤＡ回路１４２に出力する。
三角形の各頂点データは、たとえばｘ，ｙ座標が１６ビット、ｚ座標が２４ビット、ＲＧＢカラー値が各１２ビット（＝８＋４）、ｓ，ｔ，ｑテクスチャ座標は各３２ビット浮動少数値（ＩＥＥＥフォーマット）等で構成される。
【００４２】
トライアングルＤＤＡ回路１４２は、ＤＤＡセットアップ回路１４１から入力した変分データを含むプリミティブに関する情報としてのセットアップデータＳ１４１を基に、三角形内部の各画素における線形補間された（ｚ，Ｒ，Ｇ，Ｂ，α，ｓ，ｔ，ｑ）データを算出する。
トライアングルＤＤＡ回路１４２は、各画素の（ｘ，ｙ）データと、当該（ｘ，ｙ）座標における（ｚ，Ｒ，Ｇ，Ｂ，α，ｓ，ｔ，ｑ）データとを、ＤＤＡデータ（補間データ）Ｓ１４２としてテクスチャエンジン回路１４３に出力する。
【００４３】
すなわち、トライアングルＤＤＡ回路１４２は、ポリゴンの頂点毎に求められた画像パラメータに基づいてポリゴン内部に含まれるすべてのピクセルの画像パラメータを補間するラスタライズ処理（ラスタライゼーション：Ｒａｓｔｅｒｉｚａｔｉｏｎ）を行う。
具体的には、トライアングルＤＤＡ回路１４２は、各種データ（ｚ，テクスチャ座標、カラーなど）をラスタライズする。
【００４４】
テクスチャエンジン回路１４３は、「ｓ／ｑ」および「ｔ／ｑ」の算出処理、テクスチャ座標データ（ｕ，ｖ）の算出処理、グラフィックスメモリ１４５からの（Ｒ，Ｇ，Ｂ）データの読み出し処理等をパイプライン方式で行う。
なお、テクスチャエンジン回路１４３は、たとえば所定の矩形内に位置する複数（たとえば４あるいは８）画素についての処理を同時に並行して行う。
【００４５】
テクスチャエンジン回路１４３は、ＤＤＡデータＳ１４２が示す（ｓ，ｔ，ｑ）データについて、ｓデータをｑデータで除算する演算と、ｔデータをｑデータで除算する演算とを行う。
テクスチャエンジン回路１４３には、たとえば図示しない除算回路が並列処理する画素数分だけ（たとえば８個）設けられており、８画素についての除算「ｓ／ｑ」および「ｔ／ｑ」が同時に行われる。また、８画素のうち代表点からの補間演算処理を行うように実装することも可能である。
【００４６】
また、テクスチャエンジン回路１４３は、除算結果である「ｓ／ｑ」および「ｔ／ｑ」に、それぞれテクスチャサイズＵＳＩＺＥおよびＶＳＩＺＥを乗じて、テクスチャ座標データ（ｕ，ｖ）を生成する。
また、テクスチャエンジン回路１４３は、メモリＩ／Ｆ回路１４４を介して、グラフィックスメモリ１４５に、生成したテクスチャ座標データ（ｕ，ｖ）を含む読み出し要求を出力し、メモリＩ／Ｆ回路１４４を介して、グラフィックスメモリ１４５に含まれるテクスチャバッファに記憶されているテクスチャデータを読み出すことで、（ｓ，ｔ）データに対応したテクスチャアドレスに記憶された（Ｒ，Ｇ，Ｂ）データを得る。
テクスチャエンジン回路１４３は、読み出した（Ｒ，Ｇ，Ｂ）データの（Ｒ，Ｇ，Ｂ）データと、前段のトライアングルＤＤＡ回路１４２からのＤＤＡデータＳ１４２に含まれる（Ｒ，Ｇ，Ｂ）データとを、それぞれ掛け合わせるなどして、画素データを生成する。
テクスチャエンジン回路１４３は、この画素データを最終的に画素のカラー値としてメモリＩ／Ｆ回路１４４に出力する。
【００４７】
なお、グラフィックスメモリ１４５に含まれるテクスチャバッファには、ＭＩＰＭＡＰ（複数解像度テクスチャ）などの複数の縮小率に対応したテクスチャデータが記憶されている。ここで、何れの縮小率のテクスチャデータを用いるかは、所定のアルゴリズムを用いて、前記三角形単位で決定される。
【００４８】
テクスチャエンジン回路１４３は、フルカラー方式の場合には、テクスチャバッファから読み出した（Ｒ，Ｇ，Ｂ）データを直接用いる。
一方、テクスチャエンジン回路１４３は、インデックスカラー方式の場合には、あらかじめ作成しておいたカラーインデックステーブルのデータを、テクスチャカラールックアップテーブル（ＣＬＵＴ）バッファより内蔵するＳＲＡＭ等で構成した一時保管バッファに転送しておいて、このカラールックアップテーブルを用いて、テクスチャバッファから読み出したカラーインデックスに対応する（Ｒ，Ｇ，Ｂ）データを得る。
たとえばカラールックアップテーブルがＳＲＡＭで構成された場合、カラーインデックスをＳＲＡＭのアドレスに入力すると、その出力には実際の（Ｒ，Ｇ，Ｂ）データが出てくるといった使い方となる。
【００４９】
また、テクスチャエンジン回路１４３は、前述したエッジ情報抽出の第２の方法を実現スルために、通常の３次元コンピュータグラフィックス描画では残らない情報、たとえば、ピクセルごとの法線ベクトルの情報や、ポリゴンの傾きの情報をグラフィックスメモリ１４５に格納するように構成することも可能である。
【００５０】
メモリＩ／Ｆ回路１４４は、テクスチャエンジン回路１４３から入力した画素データＳ１４５に対応するｚデータと、グラフィックスメモリ１４５に含まれるｚバッファに記憶されているｚデータとの比較を行い、入力した画素データによって描画される画像が、前回、グラフィックスメモリ１４５（ディスプレイバッファ）に書き込まれた画像より、手前（視点側）に位置するか否かを判断し、手前に位置する場合には、画像データに対応するｚデータでｚバッファに記憶されたｚデータを更新する。
また、メモリＩ／Ｆ回路１４４は、（Ｒ，Ｇ，Ｂ）データをグラフィックスメモリ１４５（ディスプレイバッファ）に書き込む。
【００５１】
さらに、メモリＩ／Ｆ回路１４４は、今から描画しようとしている画素におけるテクスチャアドレスに対応したテクスチャデータを格納しているグラフィックメモリ１４５のメモリブロックをそのテクスチャアドレスより算出し、そのメモリブロックにのみ読み出し要求を出すことにより、テクスチャデータを読み出す。
この場合、該当するテクスチャデータを保持していないメモリブロックにおいては、テクスチャデータの読み出しのためのアクセスが行われないため、描画により多くのアクセス時間を提供することが可能となっている。
【００５２】
メモリＩ／Ｆ回路１４４は、描画においても同様に、今から描画しようとしている画素アドレスに対応する画素データを格納しているグラフィックスメモリ１４５のメモリブロックに対して、該当アドレスから画素データをモディファイ書き込みをするために読み出し、モディファイ後同じアドレスへ書き戻す。
隠れ面処理を行なう場合には、やはり同じように今から描画しようとしている画素アドレスに対応する奥行きデータを格納しているメモリブロックに対して、該当アドレスから奥行きデータをモディファイ書き込みするため読み出し、必要ならばモディファイ後同じアドレスへ書き戻す。
【００５３】
また、メモリＩ／Ｆ回路１４４は、テクスチャエンジン回路１４３からグラフィックスメモリ１４５に対する、生成されたテクスチャ座標データ（ｕ，ｖ）を含む読み出し要求を受けた場合には、グラフィックスメモリ１４５に記憶された（Ｒ，Ｇ，Ｂ）データを読み出す。
また、メモリＩ／Ｆ回路１４４は、ＣＲＴコントロール回路１６から表示データを読み出す要求を受けた場合には、この要求に応じて、グラフィックメモリ１４５（ディスプレイバッファ）から一定の固まり、たとえば８画素あるいは１６画素単位で表示データを読み出す。
メモリＩ／Ｆ回路１４４は、ＣＲＴコントロール回路１６から、たとえばｚ値を使ったエッジ情報復元のためにｚ値の読み出し要求を受けた場合には、この要求に応じて、グラフィックメモリ１４５（ｚバッファ）をｘ方向（横方向），ｙ方向（縦方向）にスキャンしてｚ値を読み出す。
また、メモリＩ／Ｆ回路１４４は、ＣＲＴコントロール回路１６から、たとえば法線ベクトルを使ったエッジ情報復元のために法線ベクトルの読み出し要求を受けた場合には、この要求に応じて、グラフィックメモリ１４５をスキャンして法線ベクトル情報を読み出す。
【００５４】
メモリＩ／Ｆ回路１４４は、グラフィックスメモリ１４５へのアクセス（書き込みまたは読み出し）を行うが、書き込み経路と読み出し経路とが別経路として構成されている。
すなわち、書き込みの場合には書き込みアドレスと書き込みデータが書き込み系回路で処理されてグラフィックスメモリ１４５に書き込み、読み出しの場合には読み出し系回路で処理されてグラフィックスメモリ１４５から読み出す。
そして、メモリＩ／Ｆ回路１４４は、所定のインターリーブ方式のアドレッシングに基づいてグラフィックスメモリ１４５へのアクセスを、たとえば１６画素単位で行う。
【００５５】
このようなメモリとのデータのやりとりにおいては、それまでの処理を複数並行処理することで、描画性能を向上させることができる。
特に、トライアングルＤＤＡ部分とテクスチャエンジン部分を並列実効形式で、同じ回路を設ける（空間並列）か、または、パイプラインを細かく挿入する（時間並列）ことで、複数画素の同時算出を行っている。
グラフィックスメモリ１４５のメモリブロックは表示領域において隣接した部分は、後述するように異なるメモリブロックとなるように配置してあるので、三角形のような平面を描画する場合には面で同時に処理できることになるため、それぞれのメモリブロックの動作確率は非常に高くなっている。
【００５６】
グラフィックスメモリ１４５は、基本的には、テクスチャバッファ、ディスプレイバッファ、ｚバッファおよびテクスチャＣＬＵＴ(Color Look Up Table) バッファとして機能する。
また、グラフィックスメモリ１４５は、ＣＲＴコントロール回路１６が、法線ベクトルを使ったエッジ情報復元を行うように構成されている場合には、テクスチャバッファ、ディスプレイバッファ、ｚバッファおよびテクスチャＣＬＵＴ(Color Look Up Table) バッファとして機能に加えて、法線ベクトルを格納する法線バッファとしても機能する。
また、グラフィックスメモリ１４５は、同一機能を有する複数、たとえば４個のモジュールに分割されている。
【００５７】
また、グラフィックスメモリ１４５には、より多くのテクスチャデータを格納するために、インデックスカラーにおけるインデックスと、そのためのカラールックアップテーブル値が、テクスチャＣＬＵＴバッファに格納されている。
インデックスおよびカラールックアップテーブル値は、上述したように、テクスチャ処理に使われる。
すなわち、通常はＲ，Ｇ，Ｂそれぞれ８ビットの合計２４ビットでテクスチャ要素を表現するが、それではデータ量が膨らむため、あらかじめ選んでおいたたとえば２５６色等の中から一つの色を選んで、そのデータをテクスチャ処理に使う。このことで２５６色であればそれぞれのテクスチャ要素は８ビットで表現できることになる。インデックスから実際のカラーへの変換テーブルは必要になるが、テクスチャの解像度が高くなるほど、よりコンパクトなテクスチャデータとすることが可能となる。
これにより、テクスチャデータの圧縮が可能となり、内蔵メモリの効率良い利用が可能となる。
【００５８】
さらに、グラフィックスメモリ１４５には、描画と同時並行的に隠れ面処理を行うため、描画しようとしている物体の奥行き情報が格納されている。
なお、表示データと奥行きデータおよびテクスチャデータの格納方法としては、たとえばメモリブロックの所定の位置、たとえば先頭から連続して表示データが格納され、次に奥行きデータが格納され、残りの空いた領域に、テクスチャの種類毎に連続したアドレス空間でテクスチャデータが格納される。
【００５９】
以上のように、ＤＤＡセットアップ回路１４１、トライアングルＤＤＡ回路１４２、テクスチャエンジン回路１４３、メモリＩ／Ｆ回路１４４等における所定処理を経て、最終的なメモリアクセスがピクセル(Pixel；Picture Cell Element) という描画画素単位になる。
【００６０】
ＣＲＴコントロール回路１６は、与えられた水平および垂直同期信号に同期して、図示しないＣＲＴに表示する表示アドレスを発生し、グラフィックスメモリ１４５に含まれるディスプレイバッファから表示データを読み出す要求をメモリＩ／Ｆ回路１４４に出力する。
この要求に応じて、メモリＩ／Ｆ回路１４４は、グラフィックスメモリ１４５（ディスプレイバッファ）から一定の固まりで表示データを読み出す。
ＣＲＴコントロール回路１６は、グラフィックスメモリ１４５から読み出した表示データを記憶するたとえばＦＩＦＯ回路を内蔵し、一定の時間間隔で、ＲＧＢのインデックス値を発生する。
ＣＲＴコントロール回路１６は、各インデックス値に対応するＲ，Ｇ，Ｂデータを記憶しており、発生したＲＧＢのインデックス値に対応するデジタル形式のＲ，Ｇ，Ｂデータを、図示しないＤ／Ａコンバータ(Digital/Analog Converter)に転送し、アナログ形式のＲ，Ｇ，Ｂデータを生成する。
ＣＲＴコントロール回路１６は、この生成されたＲ，Ｇ，Ｂデータを図示しないＣＲＴに出力する。
ＣＲＴコントロール回路１６は、以上のようにコンピュータグラフィックス処理により生成した画像に対してアンチエイリアスなどの画像処理を行う。
【００６１】
以下、本実施形態におけるアンチエイリアス処理を行うためのエッジ情報生成処理、および生成したエッジ情報に基づく具体的なアンチエイリアス処理について、図面に関連付けて説明する。
【００６２】
まず、エッジ抽出のための情報生成処理について説明する。
本実施形態において、エッジ抽出のための情報生成方法としては、前述したように、ｚバッファの情報であるｚ値を再利用する第１の方法と、ピクセルごとの法線ベクトルの情報を用いる第２の方法を採用される。
【００６３】
ｚバッファの情報を利用するエッジ抽出方法
３次元コンピュータグラフィックスの描画時にｚ値は本来計算されてグラフィックスメモリ１４５に書き込まれる。ここでは、ｚ値そのものを使うのではなく、ｚ値の２階微分が必要となる。
図２（Ａ）および（Ｂ）に示すように、ｚ値の２階微分値は非常に有益な情報であり、その値が、適当なしきい値からはずれる点がエッジであるとみなすことができる。２次元画像から画像認識により算出するｚ値ではなく、３次元コンピュータグラフィックス描画時には正確なｚの値がわかっているので、ｚの２階微分値から検出するエッジ情報の精度は極めて高いものとなる。ここで得られたエッジは多くの場合、描画されたオブジェクトと背景との境界である。
【００６４】
図２（Ａ）において、エッジを挟んだ２点では、図中矢印＜２＞で示す２階微分の結果（方向）が同一オブジェクト内あるいは背景における図中矢印＜１＞，＜３＞で示す結果（方向）と大きく違っている。同様に、図２（Ｂ）において、エッジを挟んだ２点では、図中矢印＜３＞で示す２階微分の結果（方向）が同一オブジェクト内あるいは背景における図中矢印＜１＞，＜２＞，＜４＞，＜５＞で示す結果（方向）と大きく違っている。
【００６５】
ｚの２階微分値を得る方法としては、描画終了後にｚバッファをスキャンして計算する方法と、描画時に、ピクセル値の書き込み（打ち込み）と同じタイミングでｚの２階微分値を更新していく方法を採用することができる。
メモリを節約する必要があるときは、好適には、前者の方法を使って、ＣＲＴコントロール回路１６の要求に従ってｚのスキャンと同時に必要な処理を終わらせる方法をとることが望ましい。
後段の処理を軽くする必要があれば、後者の方法により、ｚの２階微分値の計算を描画とともに終わらせておくことができる。
【００６６】
ここで、描画とともにｚの２階微分値の計算を終わらせる方法を説明する。この場合、ＣＲＴコントロール回路１６ではなく、メモリＩ／Ｆ回路１４４あるいはテクスチャエンジン回路１４３により、描画とともにｚの２階微分値の計算を行うことになる。ＣＲＴコントロール回路１６は、メモリＩ／Ｆ回路１４４を通して生成画像に関する２階微分値を読み出し、アンチエイリアス処理を行う。
本来あるｚバッファの他にｚの２階微分値のバッファを用意して０に初期化しておく。描画時に、あるピクセルのｚ値が更新される度に、そのピクセルのｚ値が２階微分に影響する周囲のピクセルにおける２階微分値を更新する。
そのプロセスにより、描画終了時にはｚの２階微分値のバッファもできあがる。
【００６７】
スクリーン座標をｘ，ｙとし、各ピクセルにおけるｚ値をｚ（ｘ，ｙ）とすると、２階微分値の分布としては、次の２つの分布を各ピクセルについて必要になる。
【００６８】
（数１）
d2z/dx2( x, y ) = z( x+1, y ) + z( x-1, y ) − 2 * z( x, y )
d2z/dy2( x, y ) = z( x, y+1 ) + z( x, y-1 ) − 2 * z( x, y )
…（１）
【００６９】
描画時、あるｘ，ｙのアドレスのｚ値が更新されるとしたら、( x-1, y ), (x+1, y),
(x, y-1), (x, y+1), (x, y)のアドレスのｚの２階微分値が更新される。
【００７０】
たとえば、更新前の２階微分値を下記のようであると仮定する。
【００７１】
（数２）
d2z/dx20＿ 0( x, y ) = z0( x+1, y ) + z0( x-1, y )− 2 * z0( x, y )
…（２）
【００７２】
ここで、たとえば( x-1, y )のｚ値がｚ１に更新されるとすると、更新後の２階微分値は次のようになる。
【００７３】
（数３）
d2z/dx21＿ 1( x, y ) = z0( x+1, y ) + z1( x+1, y )− 2 * z0( x, y )
…（３）
【００７４】
このとき、２階微分値を更新するには、次式のような計算を行えばよい。
【００７５】
（数４）
d2z/dx2 ＿ 1− d2z/dx2＿0 = z1( x-1, y )− z0( x-1, y )
…（４）
【００７６】
d2z/dx20＿の値を読み出して、上記差分を加算して書き戻すというリードモディファイライト（read＿modify＿write）の手続きで更新していくことができる。
なお、ｚの２階微分値をアンチエイリアス（anatialiasing）などの処理に使うときは
、ｘ，ｙそれぞれの方向の値のどちらかを使用する方法でも両方の情報を独立に使用する方法も採用可能である。
【００７７】
次に、ｚの２階微分値を得る方法として、描画終了後にｚバッファをスキャンして計算し、エッジ情報を生成していく方法について説明する。
【００７８】
図３（Ａ）〜（Ｃ）は、ｚの２階微分値を得る方法として、描画終了後にｚバッファをスキャンして計算し、エッジ情報を生成していく方法について説明するための図である。
図３（Ａ）〜（Ｃ）に示すように  ｚバッファをスキャンする場合、横方向（ｘ方向）のスキャンと縦方向（ｙ方向）のスキャンのどちらもエッジ情報を復元するには有効であるが、アンチエイリアス処理においては縦、横の両方向のスキャンを併用することも有効である。
スキャン時、各ピクセルにおいて行うことは下記に示すようなフィルタリングである。  
【００７９】
（数５）
d2z = 4*z( x, y ) − z( x, y-1 )− z( x, y+1 )− z( x-1, y )−z( x+1, y ) 
d2zdx = 2*z( x, y ) − z( x-1, y )− z( x+1, y )
d2zdy = 2*z( x, y ) − z( x, y-1 )− z( x, y+1 )
…（５）
【００８０】
式５に示した係数で上下左右と中心ピクセルを加算して値を求める方法があるが、その他に、上下と中心ピクセルで縦方向の値、左右と中心ピクセルで横方向の値の２つの値を分けて求めることも可能である。この方法は後のアンチエイリアス処理において有効な方法である。
【００８１】
横方向（ｘ方向）と縦方向（ｙ方向）のフィルタリング値（ｚの２階微分値）を別々に計算する方法では、２つの値〔d2dx ( x, y ) 〕および〔dz2dy ( x, y )〕がスキャン時に各ピクセルについて求められる。それぞれの値に対してしきい値Ｚｔｈを用いた次の評価、すなわち、絶対値がしきい値Ｚｔｈより大きいかが評価される。
【００８２】
（数６）
abs ( dz2dx(x,y) ) > zth
abs ( dz2dy(x,y) ) > zth
…（６）
なお、Ｚｔｈは調整可能なしきい値である。
【００８３】
上記評価式（６）が真ならば、その方向でのエッジであり、そうでなければその方向ではエッジではないということになる。
たとえばｚの２階微分（スクリーン座標ピクセル間１としたときのｘ，ｙにおける値）を、式７のようであるとする。
【００８４】
（数７）
ｘ方向d2zdx = z(x+1,y) + z(x-1,y) - 2*z(x,y)
ｙ方向d2zdy = z(x,y+1) + z(x,y-1) - 2*z(x,y)
しきい値Ｚｔｈ                                                  …（７）
【００８５】
この場合、d2zdx > zth のときｘ方向に不連続であり、ｙ方向に伸びるエッジであると評価する。
d2zdy > zth のときｙ方向に不連続であり、ｘ方向に伸びるエッジであると評価する。
上記のことが、ｚバッファに対する１回のスキャンで各ピクセルについて処理できる。
また、あるピクセルに対してｘ方向とｙ方向、独立に、それぞれエッジであるかどうかを判定するのは、アンチエイリアスにとって有効な手段である。
【００８６】
次に、エッジ抽出に法線ベクトルを使う方法について説明する。
【００８７】
ピクセルごとの法線ベクトルの情報を利用するエッジ抽出方法
法線ベクトルは描画時に生成されるが、これは通常グラフィックスメモリ１４５に格納されないで、使われたあとは捨てられる。これを、各ピクセルごとにグラフィックスメモリ１４５に蓄積しておけば、後段でエッジ抽出のために使うことができる。抽出方法は後述する。
【００８８】
一方、法線ベクトルを蓄積しておくためにはメモリが必要なので、その分のメモリを節約するために法線ベクトルをメモリに格納せずに、描画後に、スクリーン座標とｚバッファのｚ値から法線ベクトルを復元する方法を使うことができる。
具体的な手法としては、図４および下記式８に示すように、各ピクセルにおいて、スクリーン座標のｘ，Ｙ座標値とｚバッファのｚ値で３次元座標を作り、当該ピクセルの上または下のピクセルと右または左のピクセルと、当該ピクセルの３点の３元座標を使ってベクトルの外積を計算すれば、それは法線ベクトルとなる。
【００８９】
（数８）
(nx0, ny0,nz0) = ( (x2,y2,z2)− (x0,y0,z0) × ( (x1,y1,z1) − (x0,y0,z0) ) 
nx0 = (y2-y0)*(z1-z0) − (z2-z0)*(y1-y0)
ny0 = (z2-z0)*(x1-x0) − (x2-x0)*(z1-z0)
nz0 = (x2-x0)*(y1-y0) − (y2-y0)*(x1-x0)
…（８）
【００９０】
すなわち、ｚバッファの値から法線を復元する方法においては、ｚバッファの値ｚと、ｚバッファのアドレス(x,y)の３つのパラメータが形成する３次元空間における、ある１
点から他の２点へのベクトルの外積を正規化したものを法線ベクトルとする。
一例を示すと、ｚバッファのアドレスをｘ，ｙの２次元に展開したとき、ピクセル間のｘ，ｙそれぞれの方向の距離を１とすると次のようになる。
【００９１】
（数９）
nx = z(x+1, y) - z(x,y)
ny = z(x, y+1) - z(x,y)
nz = -1
…（９）
【００９２】
このように、法線ベクトルを使ったエッジ情報復元のためには、描画時に各ピクセルの法線ベクトルの成分をバッファに格納しておくか、または、ｚバッファの情報とスクリーン座標から法線ベクトルを復元する必要がある。
法線ベクトルを格納しておくとしたら、フォンシェーディングのために線形補間された法線ベクトルの値を格納しておけば精度は上がるが、法線ベクトルを補間しない描画のときにはポリゴンの平均値を各ピクセルにおける値として格納しておいてもよい。
また、３成分全てを格納する必要はなく、ベクトルの大きさが１であることを法線ベクトルの条件とすれば、２成分と残り１成分の符号だけを格納しておけば後で演算により３成分を取り出すこともできる。
【００９３】
図５（Ａ）〜（Ｄ）に、法線ベクトルの情報からエッジ情報を取り出す方法を示す。
図に示すように、横方向（ｘ方向）、縦方向（ｙ方向）のどちらか、またはその両方のスキャンにより情報を取り出す。法線ベクトルバッファがあるときは、この法線ベクトルバッファをスキャンする。
法線ベクトルを復元するときは、ｚバッファをスキャンして、法線ベクトルを復元しながらエッジ判定を行う。スキャン中に各ピクセルにおいて行うことは、図および下記式９に示したとおり、中心ピクセルの法線ベクトルと上下左右の各ピクセルの法線ベクトルとの内積を取ることである。
【００９４】
（数１０）
Px0 = N(x,y)・ N(x-1,y)
Px1 = N(x,y)・ N(x+1,y)
Py0 = N(x,y)・ N(x,y-1)
Py1 = N(x,y)・ N(x,y+1)
…（１０）
【００９５】
上記内積に対して、それぞれ以下の評価を行う。
【００９６】
（数１１）
11-1.  Abs( px0 ) < ( 1.0＿ nth )
11-2.  Abs( px1 ) < ( 1.0＿ nth )
11-3.  Abs( py0 ) < ( 1.0＿ nth )
11-4.  Abs( py1 ) < ( 1.0＿ nth )
【００９７】
ここでnthは、調整可能なしきい値である。上記式１１−１または１１−２が真であっ
たならば、当該ピクセルはｘ方向に関してエッジであると結論される。上記式１１−３または１１−４が真であったならば、当該ピクセルはｙ方向に関してエッジであると結論される。
すなわち、ｘ，ｙ両方向にそれぞれ隣り合うピクセル同士の法線ベクトルの内積を計算し、その内積の値が１．０からしきい値の範囲内であれば、エッジでないと判定され、しきい値の範囲を逸脱したらエッジであると判定される。
【００９８】
たとえば、ｘ方向において次の条件を満足するとき、当該ピクセルの左(xが小さくなる方向）に、ｙ方向へ伸びるエッジが存在する、と判定される。
【００９９】
（数１２）
nx(x-1,y)*nx(x,y) + ny(x-1,y)*ny(x,y) + nz(x-1,y)*nz(x,y) < nth
…（１２）
【０１００】
次の条件を満足するとき、当該ピクセルの右(xが大きくなる方向）に、y方向へ伸びる
エッジが存在する、と判定される。
【０１０１】
（数１３）
nx(x+1,y)*nx(x,y) + ny(x+1,y)*ny(x,y) + nz(x+1,y)*nz(x,y) < nth
…（１３）
【０１０２】
次の条件を満足するとき、当該ピクセルの上(yが小さくなる方向）に、ｘ方向へ伸びるエッジが存在する、と判定される。
【０１０３】
（数１４）
nx(x,y-1)*nx(x,y) + ny(x,y-1)*ny(x,y) + nz(x,y-1)*nz(x,y) < nth
…（１４）
【０１０４】
次の条件を満足するとき、当該ピクセルの下(yが大きくなる方向）に、ｘ方向へ伸びるエッジが存在する、と判定される。
【０１０５】
（数１５）
nx(x,y+1)*nx(x,y) + ny(x,y+1)*ny(x,y) + nz(x,y+1)*nz(x,y) < nth
…（１５）
【０１０６】
上記評価まで、１回のスキャンで各ピクセルに対して処理することができる。ｘ，ｙ方向それぞれに対して独立にエッジの有無を調べることも、縦方向、横方向のスキャンを両方行うことも、この後の処理としてアンチエイリアス処理を行うときに、有用な情報となる。
【０１０７】
上記したように得られたエッジかどうかという情報に、当該ピクセルの、左右どちらか、あるいは上下どちらにエッジがあるか、という情報を付け加える。したがって、情報としては、エッジの有る無しを示す１ビット情報に加えて、どちら側にエッジがあるかということを示す１ビット情報が必要であり、最低２ビットの情報を生成する。
【０１０８】
本実施形態では、上記したようにスクリーン座標でのｘ方向、ｙ方向それぞれに関するエッジ情報を描画後の画像から所定の情報を復元し、得られたエッジ情報から、アンチエイリアス（anti-aliasing）のために必要な処理内容を決定し、決定した処理を行う。
【０１０９】
本実施形態では、描画時に得られたｚバッファの情報と各ピクセルにおける法線ベクトルの情報のどちらか、あるいはその両方の情報をスキャンすることにより、あるいはｚバッファの情報から復元された法線ベクトルの情報を使ってアンチエイリアス処理を各ピクセルに施して行く。
たとえば各スキャンにおいて、状態を保持するステートマシーンとエッジの連続を測るカウンタを規定する。その２つの素子により各エッジ上のピクセルに対して、それぞれ、どの方向のとなりのピクセルのピクセル値と、どれくらいの割合でブレンドすべきか、決定する。そして、決定された値を使ってブレンド処理が行われ、ピクセル値が更新されるところまでが、上記スキャンの間に逐次行われる。
この方法によれば、アンチエイリアス処理の目的で増加すべきメモリ量は少なくてすみ、描画時にパフォーマンスを下げるような処理は追加されない。
【０１１０】
以下、この処理のアルゴリズムと実装形態について説明する。
【０１１１】
アルゴリズム
エイリアスとなるエッジの最も一般的な形は、図６（Ａ），（Ｃ）に示すようなパターンである。このようなパターンのエッジに対して、図６（Ｂ），（Ｄ）に示すようにブレンド処理を行う。
具体的には、図７に示すように、エッジを挟むピクセル同士が互いにブレンドされる。この場合、１ピクセルの辺の長さを１．０としたときの図中、台形の面積がブレンド係数となる。
【０１１２】
図７の場合を例として、ピクセル値をそれぞれ、Ａ０，Ａ１，Ａ２，Ｂ０，Ｂ１，Ｂ２としたとき、それぞれのピクセル値がどのように変わるかを下記に示す。ここでは、ピクセルに対応するブレンド係数はａ０，ａ１，ａ２，ｂ０，ｂ１，ｂ２とする。
【０１１３】
（数１６）
A0  ->  A0 * ( 1− a0 ) + B0 * a0
B0  ->  B0 * ( 1− b0 ) + A0 * b0
a0 = 3.0 * 0.5 * 0.5 * ( 1− 2*2/(3*3) )
b0 = 3.0 * 0.5 * 0.5 * ( 1*1/(3*3) )
A1  ->  A1 * ( 1− a1 ) + B1 * a1
B1  ->  B1 * ( 1− b1 ) + A1 * b1
a1 = 3.0 * 0.5 * 0.5 * 2*2/(3*3) * ( 1− 1*1/(2*2) )
b1 = 3.0 * 0.5 * 0.5 * 2*2/(3*3) * ( 1− 1*1/(2*2) )
A2  ->  A2 * ( 1− a2 ) + B2 * a2
B2  ->  B2 * ( 1− b2 ) + A2 * b2
a2 = 3.0 * 0.5 * 0.5 * ( 1*1/(3*3) )
b2 = 3.0 * 0.5 * 0.5 * ( 1− 2*2/(3*3) )
…（１６）
【０１１４】
上記係数を使うと水平または垂直に近いエッジにおいてもエイリアスの形が完全に取り払われる。
【０１１５】
上記処理を行うためにはエッジのパターン（エイリアスパターン）を見つけだす必要がある。基本的には、図８に示すようなエッジのパターンを縦方向、横方向、それぞれ独立に見つけだす処理となる。
この目的のためにはマスクを定義してパターンマッチングを行ってもよいが、以下に示す方法を採用することができる。以下に示す方法とパターンマッチングを組み合わせてもよい。
【０１１６】
ある１ラインに注目すると、そのラインをどちらかの端点からスキャンしていくことになる。スキャンの途中で、ラインと垂直な方向でエッジとなるピクセルが見つかることがある。
たとえば、ｘ方向にスキャンしている場合ではｙ方向にエッジとなるピクセルである。ｙ方向スキャンのときはｘ方向にエッジとなるピクセルのことである。ｘ（ｙ）方向にエッジというのは、その方向で、ｚの２階微分値や法線ベクトルの方向などが急峻に変化するということである。
そのようなピクセルが見つかったときには、当該ラインの上のラインまたは下のラインのピクセルにもライン方向と垂直方向にエッジとなるピクセルが見つかる確率が極めて高い。
さらに、スキャンを進めると、当該ラインで垂直方向にエッジであるピクセルが何個か続き、上下どちらかのピクセルでも垂直方向にエッジであるピクセルが続く。ある時点で、当該ラインのピクセルは垂直方向にエッジであることは続いている状態で、上下のラインで、垂直方向にエッジであるラインが上下逆転する。そして、また何個かそのような状態が続いた後、当該ラインにおいて、垂直方向のエッジのピクセルがなくなる。これが１つのエイリアスパターンの見つけ方である。
当該ラインで垂直方向にエッジであるピクセルは、上下どちらか、垂直方向にエッジとなっているピクセルとブレンドされて書き戻されることになる。
【０１１７】
本実施形態においては、このようなパターンを見つけだすときには、各ラインのスキャンにおいて、たとえばステートマシンとカウンタを使う。
ステートマシンは、処理中のピクセルが、どのような形のパターンのどの位置にいるのかを示し、カウンタはエイリアスパターンの開始点から変節点（上下のエッジが逆転するところ）までの長さ、変節点からエイリアスパターンが終了するまでの長さを、それぞれ測定する。
これにより、各ピクセルに対して、どれだけの長さのエイリアスパターンのどの位置にあるのか示すことができ、ブレンドする相手のピクセルの位置と、ブレンドの係数を計算することができる。
【０１１８】
本方法では、どれだけの種類のパターンを認識できるかが処理のクオリティに効いてくる。特に、２つ以上のエッジが重なったり近接したりするときに適切な処理を見いだす必要がある。
そのため、本実施形態では、ラインスキャンのときに当該ラインの他に上下に複数のラインのエッジ情報も取得する。たとえば図９に示すような重なったエッジや図１０および図１１に示すような近接したエッジのパターンを見つけて適切に処理するには、上下少なくとも２ラインずつの合計５ラインの情報を同時に見る必要がある。
【０１１９】
図１２は、以上説明したエッジ情報生成とアンチエイリアスを実現する具体的な実装形態を概念的に示す図である。
【０１２０】
このアンチエイリアス処理系２００は、図１２に示すように、ｚバッファ２０１、法線ベクトルバッファ２０２、ｚバッファ２０１を横（ｘ方向）スキャンしたｚ値を２階微分する第１の２階微分回路２０３、横（ｘ方向）スキャンした法線ベクトルの内積をとる第１の内積計算回路２０４、２階微分回路２０３と内積計算回路２０４の結果に基づいてエッジ判定を行う第１のエッジ判定回路２０５、第１のエッジ判定回路２０５の判定結果に基づき処理中のピクセルがどのような形のパターンのどの位置にいるのかを示す第１のステートマシン２０６、エイリアスパターンの開始点から変節点（上下のエッジが逆転するところ）までの長さ、変節点からエイリアスパターンが終了するまでの長さをそれぞれ測定する第１のカウンタ２０７、ｚバッファ２０１を縦（ｙ方向）スキャンしたｚ値を２階微分する第２の２階微分回路２０８、縦（ｙ方向）スキャンした法線ベクトルの内積をとる第２の内積計算回路２０９、２階微分回路２０８と内積計算回路２０９の結果に基づいてエッジ判定を行う第２のエッジ判定回路２１０、第２のエッジ判定回路２１０の判定結果に基づき処理中のピクセルがどのような形のパターンのどの位置にいるのかを示す第２のステートマシン２１１、エイリアスパターンの開始点から変節点（上下のエッジが逆転するところ）までの長さ、変節点からエイリアスパターンが終了するまでの長さをそれぞれ測定する第２のカウンタ２１２、完成したコンピュータグラフィックス（ＣＧ）画像を格納するディスプレイバッファ２１３、アンチエイリアス処理後の画像を格納するディスプレイバッファ２１４、およびフラグレジスタ２１５を含む。
【０１２１】
図１２のアンチエイリアス処理系２００は、前提として、以下のものが存在する状態から処理を始めることを仮定する。
1.描画が完成した３次元コンピュータグラフィックス画像、
2.描画とともに完成したｚバッファ２０１、
3.描画とともに完成した法線ベクトルバッファ２０２。
【０１２２】
上記バッファというのは、各ピクセルごとに持つデータのメモリのことである。ｚバッファ２０１は、前述したように、描画の副生成物でり、本来ならば、描画終了とともに捨てられる情報である。本実施形態では、それを再利用する。
法線ベクトルバッファ２０２に関しては、ｚッファ２０１とスクリーン座標から計算して法線ベクトルを復元することができるので、その処理を入れる場合は、法線ベクトルバッファは必要ではない。
【０１２３】
図１２のアンチエイリアス処理系２００においては、縦スキャンと横スキャンを、同時並列的に行う。それぞれのスキャンとともに処理も進行させる。
それぞれのスキャンで、ｚ値の２階微分を第１および第２の２階微分回路２０３，２０８で求め、隣あうピクセル同士の法線ベクトルの内積を第１および第２の内積計算回路２０４，２０９で計算する。
そして、第１および第２のエッジ判定回路２０５，２１０において、第１および第２の２階微分回路２０３，２０８、並びに第１および第２の内積計算回路２０４，２０９の結果に基づいてｘ方向とｙ方向それぞれについて当該ピクセルがエッジであるかどうかを判定し、判定結果をステートマシーン２０６，２１１に送る。
ステートマシーン２０６，２１１は、処理中のピクセルが、どのようなパターンのエッジの、どの部分なのかを判断し、そのエッジの情報を保持する。そして、カウンタ２０７，２１２において、エッジの長さを測る。
１つのエッジのパターンが、そのライン内で終了すると、ステートマシーン２０６，２１１、カウンタ２０７，２１２はクリアされ、そのラインの後ろのピクセルに遡ってブレンド係数の計算、ブレンドする相手のピクセルの決定などを行い、それぞれのピクセルに対してブレンド処理を行い、処理後の画像を格納するメモリであるディスプレイバッファ２１４に書き込む。
そのとき、横スキャンの処理と縦スキャンの処理が並行して行われているため、それぞれ他のスキャンが既に当該ピクセルに対して処理を行ったかどうかの１ビットのフラッグ情報を各ピクセルに対して保持する必要がある。
フラグレジスタ２１５にフラグが立っていなければバッファ２１３の「完成したCG画像」のピクセル値に対してブレンド処理を行い、立っていれば、バッファ２１４の「アンチエイリアス（Anti-Alias）処理後の画像」からピクセル値を読み出し、それに対してブレンド処理を行って書き戻す。
なお、法線バッファなし、法線復元もなしで、ｚバッファの情報のみを使うこともある。
【０１２４】
また、スキャンの幅は、通常のエッジパターンを検出するには３ラインで十分だが、重なったエッジなどを分離するには少なくとも５ライン同時にスキャンする必要がある。本発明では、複数のラインとして何ライン同時にスキャンするかどのような可能性も否定しない。
【０１２５】
以下に、ステートマシーンの一例について説明する。
【０１２６】
ここで説明するステートマシーンにおいては、「state」、「count」、「parity」と
いう３つの変数を使う。
また、next#stateは、次にstateがとる値を示す。
スキャン方向に１ピクセルづつ進んでいく。ｘ方向、ｙ方向に、それぞれｚバッファまたは、法線バッファまたは、エッジ情報バッファ（ｚバッファなどのスキャンにより得られたエッジ情報が入っているメモリのこと）をスキャンして、読み込みデータによって変数「state」を変化させる。変数「state」に応じてカウンタのクリア、カウントアップ
、値の保持が決まる。
【０１２７】
ｘ方向スキャンの場合
state==0のとき
if( y方向にedgeであるピクセルだった)
next#state = 1
count = 1;
if( x方向にもedgeであった)
parity = 1;
else
parity = 0;
else
next#state = 0;
count = 0;
state==1のとき
if( y方向にedgeであるピクセルだった）
next#state = 1;
count = count + 1;
else
next#state = 0;
if(parity==1&&x方向にedgeであるピクセルだった）
mode=2でcount数のピクセル分、遡ってblend処理
if(parity==1&&x方向にedgeではなかった）
mode=1でcount数のピクセル分、遡ってblend処理
if(parity==0&&x方向にedgeであるピクセルだった）
mode=0でcount数のピクセル分、遡ってblend処理
if(parity==0&&x方向にedgeではなかった）
なにもしない
【０１２８】
以上のステートマシーンの動きとブレンド処理を図で書くと図１３（Ａ）〜（Ｄ）に示すようになる。
図の例は、ｘ方向のスキャンで、上と横のエッジを見る場合の例である。
変数stateが１から０に変わるところで、遡ったブレンド処理を行う。
【０１２９】
ブレンド（blend）係数の求め方
mode==0のとき、count値の大きいピクセルのブレンド係数の値が０．５付近の値で、
count値が若い（小さい）ピクセルのブレンド値は０付近の値に近付く。この計算の方法
は種々選択可能である。
上記例では、たとえばcount値Ｃのピクセルのブレンド係数をＣ／５＊０．５とするの
が最も簡単な方法である。他にも、たとえば図７に示すように台形の面積面積をブレンド係数とすることも可能である。
このときは、式としては、次のようになる。
【０１３０】
（数１７）
blend係数= 0.5*0.5/ Len *( Len-C+1)2  - (Len-C)2 
…（１７）
Lenは本例では５である。
【０１３１】
mode==1のときは、count値Ｃとブレンド係数の大きさの関係がmode==0のときの逆に
なる。
mode==2のときは、０から０．５の間の適当な値で一様にしても、真ん中（この例だと
C==3付近）のブレンド係数が若干大きくなるように値を設定してやると、見た目、自然な仕上がりになる。
【０１３２】
なお、ここで説明したステートマシーン（state machine）は、ほんの１例である。
基本的には、ｘ方向とｙ方向、それぞれの処理であり、各スキャンにおいて、エッジの形を感知するステートマシーンを置いて、ピクセル数を数える仕組みであり、ステートマシーンが動作した結果、通ってきたピクセルに対して遡って処理を施す、という処理となる。
【０１３３】
ｘ方向ブレンドとｙ方向ブレンドを選択または混ぜる方法としては、以下のような方法を採用することが可能である。
・ブレンドする前に、ブレンド係数を比して大きい方だけの処理を行う方法。
・ブレンドする前に、ブレンド係数を比して小さい方だけの処理を行う方法。
・両方の処理を対当に混ぜ合わせる方法。
・ｘ方向処理とｙ方向処理の間に時間的に前後する場合、先に処理した方を優先する方法。このとき、処理されたことを示す1bitをピクセルごとに記憶させるメモリが必要になる。
・ｘ方向処理とｙ方向処理の間に時間的に前後する場合、ブレンド係数の大小で、どちらの処理を優先するか決める方法。この場合、ブレンド係数をピクセルごとに記憶させるメモリが必要になる。
・ｘ方向処理とｙ方向処理の間に時間的に前後する場合、対当に混ぜる方法。この場合、ブレンド係数をピクセルごとに格納するメモリが必要になる。
【０１３４】
図１４および図１５にｚバッファのみを使用して、描画後の完全に後処理として行う場合の概念図を示す。この場合、図１のＣＲＴコントロール回路１６がメモリＩ／Ｆ回路１４４を通してグラフィックスメモリ１４５へのアクセスをしてｚバッファをスキャンして、ｚ値情報を使ってアンチエイリアス処理を各ピクセルに施して行く。
【０１３５】
図１４は、レンダリングされた結果のＲＧＢ画像に対して、ＣＲＴコントロール回路１６によりメモリ上で画像を変化させ、その終了後、ディスプレイに転送する場合を示している。
図１５は、レンダリングされた結果のＲＧＢ画像をディスプレイのためにラスタスキャンするのと並行して、それに同期してｚバッファもスキャンして、ディスプレイへの転送時に、ＣＲＴコントロール回路１６によりメモリ上で画像を変化させ、その終了後、ディスプレイに転送する場合を示している。
【０１３６】
図１４および図１５の両例共に、ｚバッファのみを使い、レンダリングに追加の処理はない。完全に後処理として行う。
エッジ情報抽出に際しては、具体的には、以下の２種のエッジを区別して、異なる処理を行う。
第１の処理は、図１６に示すように、隣り合う平面の境界の場合の処理である。
第２の処理は、図１７に示すようなオブジェクトと背景の境界の場合の処理である。
第１の処理と第２の処理とでは、ｚの２階微分のしきい値が異なる。
【０１３７】
第１の処理
第１の処理では、ブレンド係数が正確に求まる。
図１６に示すように、当該ピクセルを中心とする、1x5 + 5x1 の十字形のｚ値を読み出す。
そして、当該ピクセルと接するピクセルの間に隣り合う平面の境界のエッジが存在するかどうか判定する。この判定と同時にブレンド係数も算出する。
判定にはｚの２階微分を使う。２階微分はｘ方向、ｙ方向、独立に計算して使用する。  この場合、２種類のしきい値を使用する。
この第１の処理と同時に第２の処理のための情報を生成しておく。
図１６の例では、ブレンド係数として用いられるｓは次のようになる。
【０１３８】
（数１８）
s = (sz3+sz1-2*sz2)/(sd4-sz3-sz2+sz1)
…（１８）
【０１３９】
第２の処理
当該ピクセルを中心とする、1xn + nx1 の十字形の情報を読み出す。ただし、nはマス
クである。ここでいう情報というのは、上記第１の処理で生成されたものである。
当該ピクセルと接するピクセルの間にオブジェクトと背景の境界のエッジが存在するとき、上記マスク内の、エッジを構成するピクセルの数を数える。
その数からブレンド係数を算出する。
【０１４０】
処理の流れ
下記の２つのループを順に行う。
第１ループ
第１のループでは、下記の処理を、全ピクセルに対して、順に行う。
エッジ抽出と第１の処理に係るエッジのブレンド処理を行う。これは、1x5 + 5x1 のマスクで全ピクセルについて、行う処理である。
・当該ピクセル上のｚの２階微分をｘ，ｙ方向について求める。
・当該ピクセルの上下左右４つのピクセルについて、それらのピクセル上のｚの２階微分をｘ，ｙ方向について求める。
・第１の処理に係るエッジを検出する（しきい値はzdev, zdev0を使う）x, y方向。
・第２の処理に係るエッジを検出する（しきい値はzdev1を使う）x, y方向。
・第１の処理に係るエッジの検出結果を使って、ブレンド処理を行い、ＲＧＢバッファを更新する。
・第２の処理に係るエッジ検出の結果と第１の処理のブレンド処理が行われたかどうかを示す１ビットを、メモリに残す（全ピクセルに対して）。
【０１４１】
第２ループ
第２のループでは、下記の処理を、全ピクセルに対して、順に行う。
第２の処理に係るエッジのブレンド処理を行う。これは、1xn + nx1 のマスクで全ピクセルについて、行う処理である。...nはマスク長である。
・ｘ方向、ｙ方向、それぞれマスクだけ、変数stateを見ながらカウントする。
・カウントする値は、４種である。
・上記４種のカウント値からブレンド係数を求めてブレンド処理を行い、ＲＧＢバッファを更新する。
このとき、第１の処理のブレンドが行われたフラグが立っていたら、ブレンド係数は０にする。
第１のループおよび第２のループは、それぞれ独立したループである。
【０１４２】
次に、第２ループのカウント処理について、図１７に関連付けて説明する。
ここでは、マスクｎは７である。
図で、「Len = min ( (maskLen-1)/2, L1 )」とあるのは、マスクの中を数えるときに
、L1の端に到達するのが先か、マスクの端に到達するのが先かで、最小値（min値）を知
ることができる。
maskLenというのは図１７では７であり、ここではｎである。
図中、で示されるピクセルの数をもとに、次式で求められる値をブレンド係数とする。  
【０１４３】
（数１９）
α = (黒いpixelの数- Len ) / (4*(Len+1) )
…（１９）
【０１４４】
なお、係数の求め方は、上記は一例である。
基本は、与えられたマスクのマスク内のピクセルに対して、ブレンド係数ができるだけ多くの階調を持つように、ピクセルを分類して、それぞれ数えて、それらを使って係数
を求める、ということである。
【０１４５】
次に、上記構成による動作を説明する。ここでは、ｚバッファのみを使い、レンダリングに追加の処理はない。完全に後処理として行う場合を例に説明する。
【０１４６】
３次元コンピュータグラフィックスシステム１０においては、グラフィックス描画等のデータは、メインプロセッサ１１のメインメモリ１２、あるいは外部からのグラフィックスデータを受けるＩ／Ｏインタフェース回路１３からメインバス１５を介してレンダリング回路１４に与えられる。
なお、必要に応じて、グラフィックス描画等のデータは、メインプロセッサ１１等において、座標変換、クリップ処理、ライティング処理等のジオメトリ処理が行われる。
ジオメトリ処理が終わったグラフィックスデータは、三角形の各３頂点の頂点座標ｘ，ｙ，ｚ、輝度値Ｒ，Ｇ，Ｂ、描画しようとしている画素と対応するテクスチャ座標ｓ，ｔ，ｑとからなるポリゴンレンダリングデータＳ１１となる。
このポリゴンレンダリングデータＳ１１は、レンダリング回路１４のＤＤＡセットアップ回路１４１に順々に転送される。
【０１４７】
ＤＤＡセットアップ回路１４１においては、ポリゴンレンダリングデータＳ１１に基づいて、三角形の辺と水平方向の差分などを示す変分データが生成される。
具体的には、開始点の値と終点の値、並びに、その間の距離を用いて、単位長さ移動した場合における、求めようとしている値の変化分である変分が算出され、変分データを含むセットアップデータＳ１４１としてトライアングルＤＤＡ回路１４２に出力される。
【０１４８】
トライアングルＤＤＡ回路１４２においては、変分データを含むセットアップデータＳ１４１を用いて、三角形内部の各画素における線形補間された（ｚ，Ｒ，Ｇ，Ｂ，α，ｓ，ｔ，ｑ）データが算出される。
そして、この算出された（ｚ，Ｒ，Ｇ，Ｂ，α，ｓ，ｔ，ｑ）データと、三角形の各頂点の（ｘ，ｙ）データとが、ＤＤＡデータＳ１４２として、トライアングルＤＤＡ回路１４２からテクスチャエンジン回路１４３に出力される。
すなわち、トライアングルＤＤＡ回路１４２においては、ポリゴンの頂点毎に求められた画像パラメータに基づいてポリゴン内部に含まれるすべてのピクセルの画像パラメータ（ｚ，テクスチャ座標、カラーなど）を補間するラスタライズ処理が行われる。
【０１４９】
テクスチャエンジン回路１４３においては、ＤＤＡデータＳ１４２が示す（ｓ，ｔ，ｑ）データについて、ｓデータをｑデータで除算する演算と、ｔデータをｑデータで除算する演算とが行われる。そして、除算結果「ｓ／ｑ」および「ｔ／ｑ」に、それぞれテクスチャサイズＵＳＩＺＥおよびＶＳＩＺＥが乗算され、テクスチャ座標データ（ｕ，ｖ）が生成される。
【０１５０】
次に、テクスチャエンジン回路１４３からメモリＩ／Ｆ回路１４４に対して生成されたテクスチャ座標データ（ｕ，ｖ）を含む読み出し要求が出力され、メモリＩ／Ｆ回路１４４を介して、グラフィックスメモリ１４５に記憶された（Ｒ，Ｇ，Ｂ）データが読み出される。
次に、テクスチャエンジン回路１４３において、読み出した（Ｒ，Ｇ，Ｂ）データの（Ｒ，Ｇ，Ｂ）データと、前段のトライアングルＤＤＡ回路１４２からのＤＤＡデータＳ１４２に含まれる（Ｒ，Ｇ，Ｂ）データとが掛け合わされ、画素データとして生成される。
この画素データは、テクスチャエンジン回路１４３からメモリＩ／Ｆ回路１４４に出力される。
【０１５１】
そして、メモリＩ／Ｆ回路１４４において、テクスチャエンジン回路１４３から入力した画素データに対応するｚデータと、ｚバッファに記憶されているｚデータとの比較が行われ、入力した画素データＳ１４５によって描画される画像が、前回、ディスプレイバッファに書き込まれた画像より、手前（視点側）に位置するか否かが判断される。
判断の結果、手前に位置する場合には、画像データに対応するｚデータでｚバッファに記憶されたｚデータが更新される。
【０１５２】
次に、メモリＩ／Ｆ回路１４４において、（Ｒ，Ｇ，Ｂ）データがグラフィックスメモリ１４５のディスプレイバッファに書き込まれる。
これら書き込む（更新も含む）べきデータは、書き込み系回路を介し所定のメモリに対して並列的に書き込まれる。
【０１５３】
メモリＩ／Ｆ回路１４４においては、今から描画しようとしている画素におけるテクスチャアドレスに対応したテクスチャを格納しているグラフィックスメモリ１４５のメモリブロックがそのテクスチャアドレスにより算出され、そのメモリブロックにのみ読みだし要求が出され、テクスチャデータが読み出される。
【０１５４】
描画においても同様に、今から描画しようとしている画素アドレスに対応する画素データを格納しているメモリブロックに対して、該当アドレスから画素データがモディファイ書き込み(Modify Write)を行うために読み出され、モディファイ後、同じアドレスへ書き戻される。
【０１５５】
隠れ面処理を行う場合には、やはり同じように今から描画しようとしている画素アドレスに対応する奥行きデータを格納しているメモリブロックに対して、該当アドレスから奥行きデータがモディファイ書き込み(Modify Write)を行うために読み出され、必要ならばモディファイ後、同じアドレスへ書き戻される。
【０１５６】
そして、図示しないＣＲＴに画像を表示する場合には、ＣＲＴコントロール回路１６において、与えられた水平垂直同期周波数に同期して、表示アドレスが発生され、メモリＩ／Ｆ回路１４４へ表示データ転送の要求が出される。
メモリＩ／Ｆ回路１４４では、その要求に従い、一定のまとまった固まりで、表示データがＣＲＴコントロール回路１６に転送される。
ＣＲＴコントロール回路１６では、図示しないディスプレイ用ＦＩＦＯ等にその表示データが貯えられ、一定の間隔でＲＧＢのインデックス値が生成される。
ＣＲＴコントロール回路１６においては、内部にＲＧＢのインデックスに対するＲＧＢ値が記憶されていて、インデックス値に対するＲＧＢ値が図示しないＤ／Ａコンバータへ転送される。
そして、Ｄ／Ａコンバータでアナログ信号に変換されたＲＧＢ信号がＣＲＴへ転送される。
【０１５７】
この場合、レンダリングされた結果のＲＧＢ画像に対して、ＣＲＴコントロール回路１６によりメモリ上で画像を変化させ、その終了後、ディスプレイに転送される。あるいは、レンダリングされた結果のＲＧＢ画像をディスプレイのためにラスタスキャンするのと並行して、それに同期してｚバッファもスキャンして、ディスプレイへの転送時に、ＣＲＴコントロール回路１６によりメモリ上で画像を変化させ、その終了後、ディスプレイに転送される。
そして、ｚバッファをスキャンしながら、法線ベクトルを復元するときは、ｚバッファをスキャンして、法線ベクトルを復元しながらエッジ判定が行われる。
【０１５８】
この場合、たとえばｚバッファに対して縦スキャンと横スキャンが、同時並列的に行われる。それぞれのスキャンとともに処理も進行させる。
たとえばＣＲＴコントロール回路１６において、それぞれのスキャンにおいて、ｚ値の２階微分が求められ、隣あうピクセル同士の法線ベクトルの内積が計算される。
そして、２階微分の結果および内積計算に結果に基づいてｘ方向とｙ方向それぞれについて当該ピクセルがエッジであるかどうかが判定される。この判定結果は、たとえばステートマシーンに送られる。
ステートマシーンにおいては、処理中のピクセルが、どのようなパターンのエッジの、どの部分なのかが判断され、そのエッジの情報が保持される。そして、カウンタにおいて、エッジの長さを測定される。
１つのエッジのパターンが、そのライン内で終了すると、ステートマシーン、カウンタはクリアされ、そのラインの後ろのピクセルに遡ってブレンド係数の計算、ブレンドする相手のピクセルの決定などが行われる。
そして、それぞれのピクセルに対してブレンド処理が行われる。
【０１５９】
ブレンド処理後の画像は、格納するメモリであるディスプレイバッファに書き込まれる。
そのとき、横スキャンの処理と縦スキャンの処理が並行して行われているため、それぞれ他のスキャンが既に当該ピクセルに対して処理を行ったかどうかの１ビットのフラッグ情報が各ピクセルに対して保持される。
たとえば、フラグレジスタにフラグが立っていなければバッファ「完成したCG画像」のピクセル値に対してブレンド処理が行われる。
これに対してフラグが立っていれば、「アンチエイリアス（Anti-Alias）処理後の画像」からピクセル値が読み出され、それに対してブレンド処理が行われた後、書き戻される。
【０１６０】
以上説明したように、本実施形態によれば、３次元コンピュータグラフィックスであることを生かして、描画時に持っている情報を有効に使用するので、極めて正確なエッジ情報を得ることができる。
また、描画の後処理であるので、描画処理そのものに対して要求される付加的な処理は最小である。付加的な処理が要求される場合もあるが、その場合でも、ピクセルの打ち込み数が増えたりするような処理ではないため、描画速度を遅くすることは全くない。
３次元コンピュータグラフィックスを描画するときに必ず生成するｚバッファの情報だけで処理することができるため、必要なメモリの量が増大することがない。
アンチエイリアス処理に使うことを考えると、従来のものと比較して、全ての処理を後処理として行うことができるため、描画速度に対する影響が少ない。また、正確なエッジ情報を使ってエッジのパターンを抽出できるので、スーパーサンプリングなどの手法で問題になるマスクサイズによる制約などは全く無く、水平または垂直に近い直線的なエッジのエイリアスを実に美しく取り除くことができる。
【０１６１】
なお、図１に示す３次元コンピュータグラフィックスシステム１０では、ポリゴンレンダリングデータを生成するジオメトリ処理を、メインプロセッサ１１で行う場合を例示したが、レンダリング回路１４で行う構成にしてもよい。
【図面の簡単な説明】
【０１６２】
【図１】本発明に係る画像処理装置としての３次元コンピュータグラフィックスシステムのシステム構成図である。
【図２】本実施形態に係るｚ値の２階微分について説明するための図である。
【図３】本実施形態に係るｚバッファのスキャン動作について説明するための図である。
【図４】本実施形態に係るｚ値を用いて法線ベクトルを復元する方法を説明するための図である。
【図５】本実施形態に係る法線ベクトルの使用方法を説明するための図である。
【図６】アンチエイリアスが必要なエッジの最も一般的なパターンを示す図である。
【図７】本実施形態に係るアンチエイリアス処理におけるブレンド動作を説明するための図である。
【図８】本実施形態に係るエイリアスパターンの探索方法について説明するための図である。
【図９】本実施形態に係るラインスキャンのときに当該ラインの他に上下に複数のラインのエッジ情報も取得する場合に、重なったエッジパターンを見つけて適切に処理する方法を説明するための図である。
【図１０】本実施形態に係るラインスキャンのときに当該ラインの他に上下に複数のラインのエッジ情報も取得する場合に、近接したエッジのパターンを見つけて適切に処理する方法を説明するための図である。
【図１１】本実施形態に係るラインスキャンのときに当該ラインの他に上下に複数のラインのエッジ情報も取得する場合に、近接したエッジのパターンを見つけて適切に処理する方法を説明するための図である。
【図１２】本実施形態に係るアンチエイリアス処理系の構成例を概念的に示す図である。
【図１３】本実施形態に係るステートマシーンの動きとブレンド処理を模式的に示す図である。
【図１４】レンダリングされた結果のＲＧＢ画像に対して、メモリ上で画像を変化させ、その終了後、ディスプレイに転送する場合を示す図である。
【図１５】レンダリングされた結果のＲＧＢ画像をディスプレイのためにラスタスキャンするのと並行して、それに同期してｚバッファもスキャンして、ディスプレイへの転送時に、メモリ上で画像を変化させ、その終了後、ディスプレイに転送する場合を示す図である。
【図１６】隣り合う平面の境界の場合のエッジ抽出処理を説明するための図である。
【図１７】オブジェクトと背景の境界の場合のエッジ抽出処理を説明するための図である。
【符号の説明】
【０１６３】
１０…３次元コンピュータグラフィックスシステム（画像処理装置）、１１…メインプロセッサ、１２…メインメモリ、１３…Ｉ／Ｏインタフェース回路、１４…レンダリング回路、１４１…ＤＤＡセットアップ回路、１４２…トライアングルＤＤＡ回路、１４３…テクスチャエンジン回路、１４４…メモリインタフェース（Ｉ／Ｆ）回路、１４５…グラフィックスメモリ、１６…ＣＲＴコントロール回路、２００…アンチエイリアス処理系、２０１…ｚバッファ、２０２…法線ベクトルバッファ、２０３…第１の２階微分回路、２０４…第１の内積計算回路、２０５…第１のエッジ判定回路、２０６…第１のステートマシン、２０７…第１のカウンタ、２０８…第２の２階微分回路、２０９…第２の内積計算回路、２１０…第２のエッジ判定回路、２１１…第２のステートマシン、２１２…第２のカウンタ、２１３…完成したコンピュータグラフィックス（ＣＧ）画像を格納するディスプレイバッファ、２１４…アンチエイリアス処理後の画像を格納するディスプレイバッファ、２１５…フラグレジスタ。
【図１】
2005100177.tif 000003
【図２】
2005100177.tif 000004
【図３】
2005100177.tif 000005
【図４】
2005100177.tif 000006
【図５】
2005100177.tif 000007
【図６】
2005100177.tif 000008
【図７】
2005100177.tif 000009
【図８】
2005100177.tif 000010
【図９】
2005100177.tif 000011
【図１０】
2005100177.tif 000012
【図１１】
2005100177.tif 000013
【図１２】
2005100177.tif 000014
【図１３】
2005100177.tif 000015
【図１４】
2005100177.tif 000016
【図１５】
2005100177.tif 000017
【図１６】
2005100177.tif 000018
【図１７】
2005100177.tif 000019
【手続補正書】
【提出日】平成16年12月3日(2004.12.3)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
スクリーン座標系の描画対象領域内に、ピクセルデータを発生してメモリに対してレンダリング処理を行い、上記メモリに描画された画像を生成する場合に、エッジ情報を生成してアンチエイリアス処理を行う画像処理装置であって、
上記メモリに描画される所定のピクセルデータに基づいて上記エッジ情報を抽出するエッジ情報抽出手段と、
上記エッジ情報抽出手段で得られたエッジ情報に基づいてアンチエイリアスのために必要な処理内容を決定し、決定した処理を行うアンチエイリアス処理手段と
を有する画像処理装置。
【請求項２】
上記アンチエイリアス処理手段は、各エッジ上のピクセルに対してブレンドのための隣接するピクセルと、ブレンドする割合とを決定し、上記決定したピクセルおよび割合に基づいてブレンド処理を行う
請求項１記載の画像処理装置。
【請求項３】
上記アンチエイリアス処理手段は、上記エッジ情報から処理中のピクセルがどのような形のエイリアスパターンのどの位置にいるのかを検出する第１の手段と、検出されたエイリアスパターンの開始点からエッジが逆転する変節点までの長さ、上記変節点からエイリアスパターンが終了するまでの長さをそれぞれ測定する第２の手段とを含み、上記第１の手段と第２の手段から得られた情報に基づいてブレンド対象のピクセルの位置と当該ブレンドの係数を計算する
請求項２記載の画像処理装置。
【請求項４】
上記メモリに描画されるピクセルデータには奥行き情報を含み、
上記エッジ情報抽出手段は、上記奥行き情報が格納された上記メモリの奥行き情報バッファをスキャンした結果得られた奥行き情報の２階微分値を求め、当該２階微分値に基づいてエッジ情報を抽出する
請求項３記載の画像処理装置。
【請求項５】
上記メモリへの描画時に生成されるデータにピクセル毎の法線ベクトルを含み、上記メモリには法線ベクトルが格納される法線ベクトルバッファが形成され、
上記エッジ情報抽出手段は、上記法線ベクトルバッファに格納された上記ピクセル毎の法線ベクトルをスキャンした結果得られた法線ベクトルに基づいてエッジ情報を抽出する
請求項３記載の画像処理装置。
【請求項６】
上記メモリに描画されるピクセルデータには奥行き情報を含み、
上記エッジ情報抽出手段は、上記奥行き情報が格納された上記メモリの奥行き情報バッファをスキャンした結果得られた奥行き情報とスクリーン座標からピクセル毎の法線ベクトルを復元し、復元した法線ベクトルに基づいてエッジ情報を抽出する
請求項３記載の画像処理装置。
【請求項７】
上記エッジ情報抽出手段は、注目するライン近傍の複数のラインのエッジ情報を抽出する
請求項４記載の画像処理装置。
【請求項８】
上記エッジ情報抽出手段は、注目するライン近傍の複数のラインのエッジ情報を抽出する
請求項５記載の画像処理装置。
【請求項９】
上記エッジ情報抽出手段は、注目するライン近傍の複数のラインのエッジ情報を抽出する
請求項６記載の画像処理装置。
【請求項１０】
スクリーン座標系の描画対象領域内に、ピクセルデータを発生してメモリに対してレンダリング処理を行い、上記メモリに描画された画像を生成する場合に、エッジ情報を生成してアンチエイリアス処理を行う画像処理方法であって、
上記メモリに描画される所定のピクセルデータに基づいて上記エッジ情報を抽出する第１ステップと、
上記第１ステップで得られたエッジ情報に基づいてアンチエイリアスのために必要な処理内容を決定し、決定した処理を行う第２ステップと
を有する画像処理方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
好適には、上記アンチエイリアス処理手段は、各エッジ上のピクセルに対してブレンドのための隣接するピクセルと、ブレンドする割合とを決定し、上記決定したピクセルおよび割合に基づいてブレンド処理を行う。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
好適には、上記アンチエイリアス処理手段は、上記エッジ情報から処理中のピクセルがどのような形のエイリアスパターンのどの位置にいるのかを検出する第１の手段と、検出されたエイリアスパターンの開始点からエッジが逆転する変節点までの長さ、上記変節点からエイリアスパターンが終了するまでの長さをそれぞれ測定する第２の手段とを含み、上記第１の手段と第２の手段から得られた情報に基づいてブレンド対象のピクセルの位置と当該ブレンドの係数を計算する。