Newell’s algorithm とは

Newell's Algorithmは、隠れた表面の除去に必要な深度ソートのポリゴンサイクルを排除するための3Dコンピュータグラフィックス手順です。これは、1972年に、Martin NewellとDick Newell、Tom Sanchaの兄弟によって提案されました.3人ともCADCentreで働いていました。
隠面消去の深度ソートフェーズでは、2つのポリゴンがx、y、z方向に重複範囲または極小値および極大値を持たない場合は、それらを簡単にソートすることができます。 2つのポリゴンQとPのZ方向のエクステントが重複している場合、切断が必要な場合があります。
その場合、Newellのアルゴリズムは次のことをテストします:
 Z重なりのテスト。ソートリストから顔Qを選択する際に暗示される2つの面のXの極限座標値が重複しない(Xのミニマックステスト)2つの面のYの極限座標値が重複しない(Yのミニマックステスト) Pのすべての頂点はQの平面よりも深いQのすべての頂点は、Pの平面よりも視点に近い。PとQのラスタライズは重ならない
テストは、計算の難易度が高い順に行われることに注意してください。
ポリゴンは平面でなければならないことにも注意してください。
テストがすべて偽である場合は、並べ替えでPとQの順序を入れ替え、それを記録してからもう一度やり直してください。ポリゴンの順序を2回目に切り替えようとすると、視程サイクルがあり、ポリゴンを分割する必要があります。分割は、1つのポリゴンを選択し、他のポリゴンとの交線に沿って切断することによって行われます。上記のテストが再び実行され、アルゴリズムはすべてのポリゴンが上記のテストに合格するまで続きます。