１．はじめに
サポート，ラフト，スカート／ブリムモデル等を生成する場面で、閉領域（スライス面）からポリゴン化する必要がありました。
閉領域は、頂点座標の配列で、順番に稜線を示し、最後に最初の頂点にたどり着く構成です。
閉領域は、多角形形状であるため、このままでは面（三角ポリゴン）としては扱えない（多のアルゴリズム的に）ので、三角ポリゴン化します。
２．アルゴリズム（考え方）
スライスした閉領域の特性上法線は上向きとなっているため、生成平面がモデル下面とする場合は、面登録時に頂点の順番を入替えます。
-
３点の場合
この場合、何もする必要はなく、そのまま三角ポリゴンとして登録する。 -
４点の場合
この場合、P1-P3を結ぶ稜線を追加する。
これにより、三角ポリゴン２面（P1-P2-P3/P3-P4-P1)として、ポリゴン登録する。 -
５点の場合
この場合、P1-P3/P1-P4を結ぶ稜線を追加する。
これにより、三角ポリゴン３面（P1-P2-P3/P3-P4-P1/P4-P5-P1)として、ポリゴン登録する。
上記法則から基本アルゴリズムを考える。
- 閉領域の始点(P1)から+2した点(P3)との間に稜線を追加する。
- P1-P2-P3の三角面を登録し、閉領域からP2を取り除く。
- 新たな閉領域が頂点３点になるまで、前記を繰り返す。
ここで注意するのは、下図の様な場合、三角ポリゴンとしては生成できません。
生成不可能となるのは、「追加する稜線が、他の稜線とクロスする。」／「生成面の法線が反転する。」場合が考えられます。
生成不可能となる場合、当該稜線は追加できないので、始点となる点を次へ移します（例：P1→P2)
※この場合、P1/P2がダメでP3から開始。P3-P8が引けなくなり、次はP7が始点となり終了する。
３．２つの閉領域から生成するには
下図のような外側と内側の２つの閉領域があり、この間を埋めたポリゴンとする場合、
下図のように、生成できるポリゴンを見つけ切り離す感じにします。すると残りの部分が閉領域１つとなるので、前記アルゴリズムでポリゴン化していきます。
４．おわりに
本アルゴリズムで生成されるポリゴンは分割がきれいではないです。
ですがスライスには影響しないため採用しています。
時間があれば改良したいと考えています。