プログラミング

UnityのCompute Shaderに線分と三角形の衝突判定をさせる

投稿日:2019年5月11日 更新日:

はじめてCompute Shader使ってみた。でもあまり性能は出ないのでただの失敗の記録です。

まず元のアルゴリズムはコレ。
線分と三角形の当たり判定 – 富士見研究所

で、これをまず三角形の表裏問わず判定するように改造して、
さらにGPUにやらせるにあたって、きっとif文とかが苦手だと思うのでif文を取っ払ってこう書く。 resultが正の値ならHitしてます。

#pragma kernel LineTriangleHit

struct LTHit
{
    float3 lineStart;
    float3 lineEnd;
    float3 triP;
    float3 triQ;
    float3 triR;
    int    result;
};

RWStructuredBuffer<LTHit> LTHits;

[numthreads(8,1,1)]
void LineTriangleHit (uint3 id : SV_DispatchThreadID)
{
    float3 s = LTHits[id.x].lineStart;
    float3 e = LTHits[id.x].lineEnd;
    float3 p = LTHits[id.x].triP;
    float3 q = LTHits[id.x].triQ;
    float3 r = LTHits[id.x].triR;
    float3 l = e - s;
    float3 n = cross(q - p, r - p);
    float  dists = dot(s - p, n);
    float  diste = dot(e - p, n);
    
    float3 crossPoint = dists / (dists - diste) * l + s;
    
    int r0 = -sign(dists * diste);
    int r1 = sign(dot(n, cross(q - p, p - crossPoint)));
    int r2 = sign(dot(n, cross(r - q, q - crossPoint)));
    int r3 = sign(dot(n, cross(p - r, r - crossPoint)));
    
    LTHits[id.x].result = r0 | ((r1 | r2 | r3) ^ (r1 & r2 & r3));
}

一番のポイントは最後のビット演算なんですが、
r1~r3がそれぞれ線分と三角形の交点から各頂点へのベクトルと各辺ベクトルの外積になっていて(正確にはその符号部分)、
交点が三角形の内側にある場合、この外積はすべて同じ方向を向く。
ベクトルが同じ方向を向いてる=符号が同じ、ということなので、3つの変数の符号が一致しているか見るんですよ。

で、変数の符号の一致を確認する。
たとえば2変数なら “if (x*y>0)”みたいにする。
if文が嫌いなのでビット演算にやらせると、 “result = x XOR y”みたいになる。resultが正なら符号が一致している。
これを3変数に拡張すると、”(x OR y OR z) XOR (x AND y AND z)”で取れるのでそのように書く、というわけです。

とりあえずアイデアとしてはそんな感じで、この処理の速さはともかく、データを流し込む処理に時間食ってぜんぜん性能出ないので封印しようかな。って。

-プログラミング

執筆者:


  1. […] 別の記事で書いたときからちょっと進化していて、GPUのスレッドの使い方を工夫してあります。 […]

comment

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください

関連記事

no image

Unityでメッシュをさわるノウハウ

ヒマなので覚書。ウラを取っていない経験則なので話半分で読んでください。 あと、3Dの基本概念とUnity固有の話の区別が付いていないのでごめんなさい。 もくじ1 Meshクラスの基本2 ポリゴンの読み …

SHOWROOMのガチイベをGoogleスプレッドシートでグラフにしよう

まえがき SHOWROOMのガチイベ、と言えば配信者が獲得ポイント数でランキングされ、最終的にファンの札束で殴り合って勝者を競う札束タワーバトルなわけです。 数日~数週間にわたって配信者同士でランキン …

no image

[python]Windows環境でsubprocessするときは文字コードに気をつけて

pythonは内部の文字コードと実行環境の文字コードが色々絡み合っていて、いろんなところで悪さをする。 特にWindows環境だと、内部はUTF-8で動いているのに実行環境はShift-JIS(正確に …

no image

例え話をしないC言語のポインタの説明

もくじ1 まえおき2 Hello, Worldより簡単に2.1 サンプルコード2.2 変数の置き場所2.3 変数が入っているところを見てみる3 C言語とメモリ3.1 変数cの「まわり」を見てみる3.2 …

no image

[C言語]スペースを大量に入れるとバグが直るコードを書いてみた

↓こういうツイートがバズっていたので、実際に組んでみた。 修士の頃、授業の課題でC言語書いてる時にどうしても謎のエラーが出て困っていた。それを見たSE経験(金融系)がある社会人大学院生の同期の女性が「 …