Warnock algorithm とは

Warnockアルゴリズムは、コンピュータグラフィックスの分野で一般的に使用されているJohn Warnock氏によって発明された隠れた表面アルゴリズムです。それは、計算するのが簡単な領域が得られるまで、シーンの再帰的な細分化によって複雑な画像をレンダリングする問題を解決する。言い換えれば、シーンが効率的に計算するのに十分シンプルであれば、レンダリングされます。さもなければ、それは単純化のために同様に試験されるより小さな部分に分割される。
これは実行時間が O ( n p ) {\displaystyle O(np)} の分割および征服アルゴリズムであり、nはポリゴンの数であり、pはビューポート内のピクセル数です。
入力は、ポリゴンとビューポートのリストです。最良のケースは、ポリゴンのリストが単純な場合は、ポリゴンをビューポートに描画することです。シンプルは1つのポリゴン(ポリゴンまたはその部分がビューポートの適切な部分に描画されます)または1ピクセルのサイズのビューポート(そのピクセルはオブザーバに最も近いポリゴンの色を取得します)として定義されます。連続的なステップは、ビューポートを4つの等サイズの象限に分割し、各象限のアルゴリズムを再帰的に呼び出すことです。ポリゴンリストは、その象限に表示されるポリゴンのみを含むように変更されます。