SGI algorithm とは

SGIアルゴリズムは、三角形のセットから三角形ストリップを作成します。 K. Akeley、P. Haeberli、D. BurnsによってSilicon GraphicsのIRIS GL APIで使用するための "tomesh.c"というCプログラムとして発行されました。
このアルゴリズムは、三角形ストリップにまだ追加されていない三角形のセットに対して作用し、入力三角形の全体の集合から始まる。三角形は、ストリップに追加することができる三角形がなくなるまで貪欲に追加されます。この場合、新しいストリップが開始されます。三角形ストリップを開始または継続するための三角形を選択する場合、選択は三角形の次数(すなわちそれに隣接する三角形の数)に基づいており、より小さい度合いが好ましい。
新しいストリップを開始できる三角形を迅速に識別するために優先順位キューを使用して実装された場合、アルゴリズムは線形時間で実行されます。