サイラス・ベック・アルゴリズム

提供: MonoBook
ナビゲーションに移動 検索に移動

サイラス・ベック・アルゴリズム英語: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;
}

関連項目