2

レイトレーシングの方法で、3Dでピッキングするという正確でわかりやすい表現が見つかりませんでした。このアルゴリズムを任意の言語で実装した人はいますか? 疑似コードはコンパイルできないため、一般的に不足している部分が書かれているため、直接動作するコードを共有します。

4

2 に答える 2

10

あなたが持っているのは、画面上の2Dの位置です。最初に行うことは、そのポイントをピクセルから正規化されたデバイス座標(-1 から 1) に変換することです。次に、ポイントが表す 3D 空間内の線を見つける必要があります。このためには、3D アプリがプロジェクションとカメラを作成するために使用する変換マトリックス/CES が必要です。

通常、射影、ビュー、モデルの 3 つのマトリックスがあります。オブジェクトの頂点を指定すると、それらは「オブジェクト空間」にあります。モデル行列を掛けると、「ワールド空間」の頂点が得られます。ビュー行列を再度掛けると、「目/カメラ空間」が得られます。投影を再度掛けると、「クリップ スペース」が得られます。クリップ スペースには非線形の深さがあります。マウス座標に Z コンポーネントを追加すると、それらがクリップ スペースに配置されます。線/オブジェクトの交差テストは任意の線形空間で実行できるため、少なくともマウス座標を目の空間に移動する必要がありますが、交差テストをワールド空間 (またはシーン グラフによってはオブジェクト空間) で実行する方が便利です。

マウス座標をクリップ空間からワールド空間に移動するには、Z コンポーネントを追加し、逆投影行列を掛けてから逆カメラ/ビュー行列を掛けます。線を作成するには、Z に沿った 2 つの点が計算されます —fromとto.

ここに画像の説明を入力

次の例では、オブジェクトのリストがあり、それぞれに位置と境界半径があります。もちろん、交差点が完全に一致することはありませんが、今のところ十分に機能します。これは疑似コードではありませんが、独自のベクトル/マトリックス ライブラリを使用しています。場所によっては自分のものに置き換える必要があります。

vec2f mouse = (vec2f(mousePosition) / vec2f(windowSize)) * 2.0f - 1.0f;
mouse.y = -mouse.y; //origin is top-left and +y mouse is down

mat44 toWorld = (camera.projection * camera.transform).inverse();
//equivalent to camera.transform.inverse() * camera.projection.inverse() but faster

vec4f from = toWorld * vec4f(mouse, -1.0f, 1.0f);
vec4f to = toWorld * vec4f(mouse, 1.0f, 1.0f);

from /= from.w; //perspective divide ("normalize" homogeneous coordinates)
to /= to.w;

int clickedObject = -1;
float minDist = 99999.0f;

for (size_t i = 0; i < objects.size(); ++i)
{
    float t1, t2;
    vec3f direction = to.xyz() - from.xyz();
    if (intersectSphere(from.xyz(), direction, objects[i].position, objects[i].radius, t1, t2))
    {
        //object i has been clicked. probably best to find the minimum t1 (front-most object)
        if (t1 < minDist)
        {
            minDist = t1;
            clickedObject = (int)i;
        }
    }
}

//clicked object is objects[clickedObject]

の代わりにintersectSphere、バウンディング ボックスまたはその他の暗黙的なジオメトリを使用するか、メッシュの三角形を交差させることができます (これには、パフォーマンス上の理由から kd ツリーの構築が必要になる場合があります)。

[編集]
これは、線/球の交差の実装です（上記のリンクに基づいています）。球が原点にあると仮定するため、from.xyz()asを渡す代わりに をp与えfrom.xyz() - objects[i].positionます。

//ray at position p with direction d intersects sphere at (0,0,0) with radius r. returns intersection times along ray t1 and t2
bool intersectSphere(const vec3f& p, const vec3f& d, float r, float& t1, float& t2)
{
    //http://wiki.cgsociety.org/index.php/Ray_Sphere_Intersection
    float A = d.dot(d);
    float B = 2.0f * d.dot(p);
    float C = p.dot(p) - r * r;

    float dis = B * B - 4.0f * A * C;

    if (dis < 0.0f)
        return false;

    float S = sqrt(dis);    

    t1 = (-B - S) / (2.0f * A);
    t2 = (-B + S) / (2.0f * A);
    return true;
}
于 2013-11-22T11:35:42.880 に答える