asaのブログ

数学・プログラミング(C++、WebGL)をまとめています

線分の交差判定について

線分Aと線分Bがあったとき、AとBが交差しているか求める。

1. ベクトルを使う

線分は始点と終点を持ったベクトルで表すことができる。
LineSegmentというクラスをおいて、メンバに始点ベクトルと終点ベクトルを持たせる。

2. 外積を使って交差判定する
あるベクトルに対して別のベクトルが右にあるか、左にあるかは外積を使って求めることができる。

外積は簡単に求めることができて、次の計算で求める。

    // 外積を求める
    float cross(const Vector& vec) const {
        return x * vec.y - y * vec.x;
    }

線分Aが線分Bと交差しているかを判定するには、線分Aから見て線分Bの端の点が自分の右と左にあるかを調べる。また線分Bから見て、線分Aの端の点が右と左にそれぞれあるかを見る。

平行の時は、線分Aと線分Bが重なっているかを見て、交差を判定する。

    // 指定の線分と交差しているか
    // @return 0(交差していない), 1(交差している)
    int isCross(const LineSegment& l) {
        Vector l1 = end - start;
        float c1 = l1.cross(l.getStart() - start);
        float c2 = l1.cross(l.getEnd() - start);
        
        Vector l2 = l.getEnd() - l.getStart();
        float c3 = l2.cross(start - l.getStart());
        float c4 = l2.cross(end - l.getStart());
        
        if (c1 * c2 == 0.0 && c3 * c4 == 0.0) { // 平行のとき
            LineSegment ls;
            ls.setStartEnd(start.x, start.y, end.x, end.y);
            if (isInLine(l) || l.isInLine(ls)) {
                return 1;
            }
            return 0;
        } else if ((c1 * c2 < 0.0 && c3 * c4 <= 0.0)
                   || (c1 * c2 <= 0.0 && c3 * c4 < 0.0)
                   || (c1 * c2 < 0.0 && c3 * c4 < 0.0)) { // 交差するとき
            return 1;
        } else { // 交差しないとき
            return 0;
        }
    }

平行のとき、線分がある線分の中に含まれるかどうかは、それぞれの端の点が線分の中に含まれるかを見る。

線分の中に点が含まれるときは、線分ベクトルの単位ベクトルと始点から点までのベクトルの単位ベクトルを求めて一致しているか、そして線分ベクトルの長さの中に始点から点までのベクトルの長さがおさまっていることを確認する。

    // 指定の線分を含むか
    // このメソッドは線分同士が平行の時しか使用しない
    bool isInLine(const LineSegment& l) const {
        bool b1 = isPointInLine(l.getStart());
        bool b2 = isPointInLine(l.getEnd());
        if (b1 || b2) {
            return true;
        } else {
            return false;
        }
    }
    
    // 指定の点を線分の中に含むか
    // このメソッドは平行の時しか使用しない
    bool isPointInLine(const Vector& p) const {
        if (start == p) {
            return true;
        }
        
        Vector l1 = end - start;
        Vector l2 = p - start;
        Vector u1 = l1.getUnit();
        Vector u2 = l2.getUnit();

        if (u1 == u2 && l2.norm() <= l1.norm()) {
            return true;
        } else {
            return false;
        }
    }

線対称なベクトルを求める

正射影が求まると線対称なベクトルも簡単に求まる。
求めた正射影ベクトルへの垂線となるベクトルの根元を正射影ベクトルまで持って来れば良い。


gist8d799076706d3bf23c97480a4aa0a9b6

正射影ベクトルを計算する

▪️正射影を求める
たまに思い出すとこうしてあれしてと手順が浮かんでも、うっかり間違う可能性があるのでメモ。

VectorAとVectorBがあったとき、VectorAをVectorBに正射影する。
VectorBの単位ベクトルを e とおいて、2つのベクトルの余弦を cos 、VectorAの長さを norm とすると
norm *e * cos
で求まる。VectorAを最後に足してやるのをたまに忘れるので注意。

▪️コード


gist7044b79909905c22a2ca8ba2fb255347

【WebGL】鮮鋭化

■鮮鋭化後 
f:id:asa_r:20180225123530p:plain

■元画像
f:id:asa_r:20180225123628j:plain

カーネルの変更
 鮮鋭化はカーネルの変更だけでいけます。

gist031eaed25b867f5739548db196c41feb


 なお、一緒に載っていたエンボスのカーネルは下の通り。

gist07f80c810336822ea865f397c7eed5da

 使って見るとこんな感じ。
f:id:asa_r:20180225124857p:plain

■参考
8.2. Convolution Matrix

【WebGL】エッジ抽出

 f:id:asa_r:20180225121129p:plain

■概要
 畳み込み行列を使ってエッジ抽出。

■フラグメントシェーダー
 自身と周囲8ピクセルの行列適用後の画素の和を手に入れた後、それを重さで割って描画する画素を手に入れます。透明度も行列で変換されているので、元々のテクスチャのアルファ値を適用してやります。


gistceca2de638c8f11423d6d26f210ac7a3

■CPU側の計算
 これまで書いてきたものと変わりないですが、カーネルカーネルの重さの分の記述が追加されています。reduceは初めて使いました。エッジ抽出は別のカーネルを適用してもいけるようです(GIMPの解説とかを見ると)。


gistf4692584f7738b4b4d7ec296935be34b

■参考
webglfundamentals.org

【WebGL】グレースケール化

 f:id:asa_r:20180225075948p:plain

 画像をグレースケールに直す。コードは前回のものと変わらず。
 フラグメントシェーダーを書き換えただけのコード。
 グレースケールの式はwikiより(グレースケール - Wikipedia)。



gist9e08e34ee379022c03abdf17fe6e7fb3

 グレースケールを応用するとセピア変換ができます。グレースケール画像の赤成分を強く、他の成分を弱くすると綺麗なセピアになる。画像とシェーダーは下の通り。

f:id:asa_r:20180225130742p:plain


gist72cbc499d6b98da4655654c5ab11fb6b


■参考画像
pixabay.com

【WebGL】テクスチャのロード

 テクスチャの読み込みをやってみた。基本の流れは結局変わらないのが分かった。画像のサイズが2のべき乗になっていないときは注意。画像のサイズが取れていて真っ黒な画面が表示されるときはテクスチャのカラーとして(0, 0, 0, 1)が返っている可能性あり。
 

gistd759fc9b4a4da0075563d148c26df83e


gistc99c4d432d36686111cca816e7723b79

■ まとめ
(1) バッファを作成する
(2) glコンテキストと結びつける
(3) 頂点情報を成立させる
(4) 変数用の番号を取得する
(5) 番号とデータを結びつける
(6) データを登録(データをシェーダーに送る)
で多分良し。

■ gl.createBuffer()
 頂点情報等を保存するバッファを作成。

■ gl.bindBuffer()
 このメソッドによってバッファがglコンテキストに結びつけられる

■ gl.bufferData()
 頂点配列を作成して、ここで引数にWebGL浮動小数点配列として渡せばようやくオブジェクトの頂点情報が成立する

■ gl.getAttribLocation()
 レジスタに割り当てられるレジスタ番号を取得する。この番号が分からないとどこにその変数があるのか分からなくなる。

■ gl.enableVertexAttribArray()
 さっき割り当てられた番号がこのメソッドで有効になる。番号というかgetAttribLocation(program, "アトリビュート変数")で指定したアトリビュート変数が有効になる。
 ようやく変数に値を送ることができる。バッファをバインドしておかないと意味ないけれど。バインド終わったよということを明示するのにgl.bindBuffer(gl.ARRAY_BUFFER, null)としても良いのかもしれない。

■ gl.vertexAttribPointer()
 これでシェーダーにデータが登録される。無事に。