コンテンツにスキップ

Cohen-Sutherlandのアルゴリズム

線分クリッピングのアルゴリズム、Wiki1が詳しいと思います.
確かCG-Artsの本にも載ってたはず2,現時点で手元にないので調べられないけども...(どこにやったっけ...)

線分のクリッピングでやりたいことっていうのは非常に簡単.
まず以下の図のような場合を考える.

cohen_suther_01

矩形があってそれに飛び出してる線がある.
線は矩形の中に納まってほしいわけである.

cohen_suther_02

矩形内に収まると嬉しいことは何かというと、矩形外の処理を省略できる点である.

そしたら実際に見ていく.
まず先ほどの矩形の周りに8個の矩形を用意する.
用意した後に4bitで番号を振り分ける.

cohen_suther_03

まず,0000がクリッピングしたい矩形となる.
この四角形の外にある場合は基本的にはクリッピングするものと考えて良い.
そして各ビットの意味も特に難しくはない.

  • 0001: 1ビット目が立っている→対象矩形より左にある矩形
  • 0010: 2ビット目が立っている→対象矩形より右にある矩形
  • 0100: 3ビット目が立っている→対象矩形より上にある矩形
  • 1000: 4ビット目が立っている→対象矩形より下にある矩形

こんな感じ.4ビットを使って上下左右を上手く表してるわけ.
なので例として0101なら、左上と分かる訳だね.

まずはこれを表すわけだけど、プログラムで書くのは簡単.

constexpr int INSIDE    = 0;    // Windowの内側:0000

auto ComputeRegion = [&](Vec2 p)
    {
        int region = INSIDE;

        if (p.x < WINDOW_X_MIN)
        {
            region |= 1;        // Windowの左側:0001
        }
        else if (WINDOW_X_MAX < p.x)
        {
            region |= 1 << 1;   // Windowの右側:0010
        }

        if (p.y < WINDOW_Y_MIN)
        {
            region |= 1 << 2;   // WINDOWの上側:0100
        }
        else if (WINDOW_Y_MAX < p.y)
        {
            region |= 1 << 3;   // WINDOWの下側:1000
        }

        return region;
    };
0を用意してあげる.これは内側.
pと対象となる矩形、今回はWindowで見てるのでそれと比較を行う.
左に出ていれば1ビット目を立てたいので、0回左シフト.
右に出ていれば2ビット目を立てたいので、1回左シフト.
という風に左シフトを駆使して上手くビットを立ててあげるだけで良い.
XとYの判定があるので、そこだけ注意してあげれば特に問題はない.

そしたらこれを使って実際にクリッピングしていく処理を見ていく.
今回は2点をp1とp2で取って、resultに結果として受け取ることになる.
返り値にboolで返すため、そもそもクリッピングがいらない場合はそっちで判断可能!!

auto ComputeCohenSutherland = [&](Vec2 p1, Vec2 p2, std::pair<Vec2, Vec2>& result)
{
    // ...
}

まずp1とp2に対して先ほどの処理を適用して、4ビットの値に変えてあげる.
その後は条件を満たすまで、以下の処理を行う.

    int regionP1 = ComputeRegion(p1);
    int regionP2 = ComputeRegion(p2);

    while (true)
    {
        // ...
    }

まずは単純なパターンから.
regionP1とregionP2の両方とも0のパターン.

        if (regionP1 == 0 && regionP2 == 0)
        {
            // 両方ともWindow内
            result.first = p1; result.second = p2;
            return true;
        }
0というのは0000と同じこと、つまり両方の点が内側にあるということである.

cohen_suther_04

この場合は単純に点はそのままでOKなので、resultにp1とp2を格納するだけでOK.
勿論返り値はtrueで返してあげればよい.

次のパターン.

        else if (regionP1 & regionP2)
        {
            // 両方ともWindow外の同じ位置
            return false;
        }
&演算子を行うことで、同じビットが立っているときは外側と判定して返り値としてfalseで返す.
これは単純で例えば、一番上のところに線がある場合を考えると分かりやすい.

cohen_suther_05

左上の点は0101,右上の点は0110となる.
これに&演算子を適用すると0100となり値を持つ.
つまり、外側で同じ範囲を持っている場合は、確実に弾くことができるということだ.

因みに、外側の同じ範囲の場合もちゃんと弾くことができる.
0100に両方ともある場合は0100 & 0100 = 0100みたいな感じになるので、絶対立つからだ.

更に言うと、中央が絡む範囲はダメである.
0001と0010の二点の場合は0001 & 0010= 0000なので、確かに成り立ってない.
あくまで外側のみが限定である.

ここまでできれば、クリッピングを実際に行っていく必要がある.
クリッピングの計算に関してはちょっと細かく見ていこう.
今回は左側のクリッピングを見ていく.
他もやること自体は同じなので、1つだけ見ればよい.

cohen_suther_06

クリッピングする必要があるのが見つかったということは

  • 片方の点が外側に出てる
  • 両方の点が外側に出ている

のどちらかとなる.上の図だと前者である.
そのため、まずは外側になっている点を見つけ出す.
もし2つある場合も今回はwhileを使ってるので、2回目のループで勝手にクリッピングされる寸法.

        else
        {
            // 両方が全く違う位置の場合
            // 少なくともどっちかは外なので、それをpickする
            int outRegion = regionP1 != INSIDE ? regionP1 : regionP2;

            // ...
        }

このとき、次のような三角形を考える.

cohen_suther_07

まずx軸の縮め方は簡単、すでに矩形の最小値はわかるはずなのでそこに合わせればよい.
この最小値をxminx_{min}とするならば、x=xminx=x_{min}である.

問題はy軸の縮め方、ここがちょっと面倒.
面倒だけど、三角形の合同を考えればそこまで難しくない.
求めたい値はyとしておく.
三角形の合同より次が言える.

(xmin−x1):(x2−x1)=(y−y1):(y2−y1) \begin{equation} \begin{split} (x_{min}-x_{1}) : (x_{2}-x_{1}) = (y - y_{1}) : (y_{2} - y_{1}) \end{split} \end{equation}

後はこれを使って変換するだけ.

y−y1y2−y1=xmin−x1x2−x1y=y1+(y2−y1)xmin−x1x2−x1 \begin{equation} \begin{split} & \frac{y-y_{1}}{y_{2}-y_{1}} = \frac{x_{min} - x_{1}}{x_{2}-x_{1}} \\ & y = y_{1} + (y_{2}-y_{1}) \frac{x_{min} - x_{1}}{x_{2}-x_{1}} \end{split} \end{equation}

これで式は求まったので、後は実際に計算をしてあげるだけ.
やることは単純で、どこのビットが立ってるのかを見て,各方向に適用してあげるだけ.
上記の式はLEFTの部分に相当するが、それ以外も大体同じような処理になってるのでまとめて書いてある.

            Point p;
            if (outRegion & 1)
            {
                // LEFT
                p.y = p1.y + (p2.y - p1.y) * (WINDOW_X_MIN - p1.x) / (p2.x - p1.x);
                p.x = WINDOW_X_MIN;
            }
            else if (outRegion & (1 << 1))
            {
                // RIGHT
                p.y = p1.y + (p2.y - p1.y) * (WINDOW_X_MAX - p1.x) / (p2.x - p1.x);
                p.x = WINDOW_X_MAX;
            }
            else if (outRegion & (1 << 2))
            {
                // TOP
                p.x = p1.x + (p2.x - p1.x) * (WINDOW_Y_MIN - p1.y) / (p2.y - p1.y);
                p.y = WINDOW_Y_MIN;
            }
            else if (outRegion & (1 << 3))
            {
                // BOTTOM
                p.x = p1.x + (p2.x - p1.x) * (WINDOW_Y_MAX - p1.y) / (p2.y - p1.y);
                p.y = WINDOW_Y_MAX;
            }

最後にどの点をクリッピングしたかを判定し、クリッピングした方の点を縮めてあげればOK.
次のwhileによる更新に備えてregionも更新しておく.

            // 新しい範囲を指定
            bool isRegionP1 = outRegion == regionP1;
            Vec2& newP = isRegionP1 ? p1 : p2;
            int& newRegion = isRegionP1 ? regionP1 : regionP2;
            newP = p;
            newRegion = ComputeRegion(newP);

今回はWikiに揃えてコードを書いたが、while省略して両方の点を一気に調べてしまうのも手かとは思う.
というかそっちの方が綺麗に書けそうな気はした、まあ今回はこれでOKということで...
ということで結果を見てみる.

cohen_suther_08

今回は青い枠に収まるようにするプログラムを書いた.
黄色が外側と判定されたもの.
赤がクリッピングされたもの,結構上手くいってるんじゃない？

線分クリッピングはまだ他にもあるので、やるかもしれないしやらないかもしれない.
少なくともCyrus–Beckはやろうかな...動画でも扱いましたからね.

  1. Cohen–Sutherland algorithm ↩

  2. コンピュータグラフィックス [改訂新版] ↩