「サイラス・ベック・アルゴリズム」を編集中

'''サイラス・ベック・アルゴリズム'''（[[英語]]：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

コーエン・サザーランド・アルゴリズムより効率的になるよう設計されている。
またコーエン・サザーランド・アルゴリズムは長方形のみなのに対して、サイラス・ベック・アルゴリズムは多角形にも適用できる。

米空軍が考案しただけあって[[ベクターグラフィックス]]で表現された[[シューティングゲーム]]の[[実装]]が捗る。

== 詳細 ==
直線のパラメトリック方程式
:<math>
\begin{align}
\mathbf p(t) &= t \mathbf p_1 + (1 - t) \mathbf p_0\\
\end{align}
</math>
:<math> 0 \leq t \leq 1 </math>.

クリッピング領域との交点を見つけるために、領域の辺の[[法線]]（多角形を構成する直線の法線）と直線の[[内積]]を計算する。'''p'''<sub>''E''</sub> は多角形の[[頂点]]。 '''n'''は[[法線]]。
:<math>\mathbf n \cdot (\mathbf p(t) - \mathbf p_E)</math>

この値が、
* if < 0, 直線は内側になる。
* if = 0, 直線は平行である。
* if > 0, 直線は内側にない。

== 2Dでの実装例 ==
verticesからなる多角形と、point0とpoint1からなる直線に対して、
サイラスベックアルゴリズムを適用し、直線が多角形外であればnullを、多角形内であれば接点となる2点を返す。

<source lang="csharp">
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;
}
</source>

== 関連項目 ==
* [[Cohen–Sutherland algorithm]]
* [[Liang–Barsky algorithm]]
* [[Cyrus Beck algorithm]]
* [[Nicholl–Lee–Nicholl algorithm]]
* [[Fast clipping]]

[[category: 2DCG]]
[[category: 3DCG]]
[[category: コンピューター・グラフィックス]]