サイラス・ベック・アルゴリズム
サイラス・ベック・アルゴリズム(英語:Cyrus Beck algorithm)とは、コンピューターグラフィックスにおけるラインクリッピングのアルゴリズム(直線が多角形の内側にあるかを判断するアルゴリズム)である。
概要 編集
1978年に米国空軍研究所のMike CyrusとJay Beckが発表したアルゴリズムである。
Generalized two- and three-dimensional clipping (Computers & Graphics, 1978: 23–28.) https://www.sciencedirect.com/science/article/pii/0097849378900213
コーエン・サザーランド・アルゴリズムより効率的になるよう設計されている。 またコーエン・サザーランド・アルゴリズムは長方形のみなのに対して、サイラス・ベック・アルゴリズムは多角形にも適用できる。
米空軍が考案しただけあってベクターグラフィックスで表現されたシューティングゲームの実装が捗る。
詳細 編集
直線のパラメトリック方程式
- .
クリッピング領域との交点を見つけるために、領域の辺の法線(多角形を構成する直線の法線)と直線の内積を計算する。pE は多角形の頂点。 nは法線。
この値が、
- if < 0, 直線は内側になる。
- if = 0, 直線は平行である。
- if > 0, 直線は内側にない。
2Dでの実装例 編集
verticesからなる多角形と、point0とpoint1からなる直線に対して、 サイラスベックアルゴリズムを適用し、直線が多角形外であればnullを、多角形内であれば接点となる2点を返す。
public static Vector2[] CyrusBeck(Vector2[] vertices, Vector2 point0, Vector2 point1)
{
// 引数チェック
if (vertices == null || vertices.Length < 3)
{
throw new ArgumentException(nameof(vertices));
}
// 頂点数
var vcount = vertices.Length;
// 法線を計算
var normal = new Vector2[vcount];
for (int i = 0; i < vcount; i++)
{
normal[i].X = vertices[i].Y - vertices[(i + 1) % vcount].Y;
normal[i].Y = vertices[(i + 1) % vcount].X - vertices[i].X;
}
// P1-P0を計算
var p1p0 = point1 - point0;
// P0-PEiを計算
var p0pei = new Vector2[vcount];
for (int i = 0; i < vcount; i++)
{
p0pei[i] = vertices[i] - point0;
}
// 分子と分母を計算
var numerator = new float[vcount];
var denominator = new float[vcount];
for (int i = 0; i < vcount; i++)
{
numerator[i] = Vector2.Dot(normal[i], p0pei[i]);
denominator[i] = Vector2.Dot(normal[i], p1p0);
}
// enterとleavingを計算
var t = new float[vcount];
var tE = new List<float>();
var tL = new List<float>();
for (int i = 0; i < vcount; i++)
{
t[i] = numerator[i] / denominator[i];
if (0 < denominator[i])
tE.Add(t[i]);
else
tL.Add(t[i]);
}
tE.Add(0);
tL.Add(1);
var temp = new float[2];
temp[0] = tE.Max();
temp[1] = tL.Min();
// 範囲外(外側)にあると思われる
if (temp[1] < temp[0])
{
return null;
}
// 結果
var result = new Vector2[2];
result[0].X = point0.X + p1p0.X * temp[0];
result[0].Y = point0.Y + p1p0.Y * temp[0];
result[1].X = point0.X + p1p0.X * temp[1];
result[1].Y = point0.Y + p1p0.Y * temp[1];
return result;
}