5

質問が尋ねるのとほぼ同じです。できれば疑似コードで回答し、参照してください。正解は、単純さよりも速度を重視する必要があります。

4

4 に答える 4

4

3D での光線、セグメント、平面、および三角形の交点 を参照してください。ポリゴンを三角測量する方法を見つけることができます。

レイ/ポリゴンの交差が本当に必要な場合は、リアルタイム レンダリングの 16.9 (第 2 版では 13.8) にあります。

最初に、光線と [ポリゴンの平面] の間の交差を計算しますpie_p。これは、光線で置き換えることで簡単に実行できxます。

 n_p DOT (o + td) + d_p = 0 <=> t = (-d_p - n_p DOT o) / (n_p DOT d)

分母|n_p DOT d| < epsilonがepsilon非常に小さい場合、光線はポリゴン プレーンに平行であると見なされ、交差は発生しません。pそれ以外の場合、レイとポリゴン プレーンの交点が計算されますp = o + td。その後、ポリゴンの内側にあるかどうかを判断する問題はp、3 次元から 2 次元に縮小されます...

詳しくは本をご覧ください。

于 2008-11-23T09:24:49.273 に答える
3 
struct point
{
    float x
    float y
    float z
}

struct ray
{
    point R1
    point R2
}

struct polygon
{
    point P[]
    int count
}

float dotProduct(point A, point B)
{
    return A.x*B.x + A.y*B.y + A.z*B.z
}

point crossProduct(point A, point B)
{
    return point(A.y*B.z-A.z*B.y, A.z*B.x-A.x*B.z, A.x*B.y-A.y*B.x)
}

point vectorSub(point A, point B)
{
    return point(A.x-B.x, A.y-B.y, A.z-B.z) 
}

point scalarMult(float a, Point B)
{
    return point(a*B.x, a*B.y, a*B.z)
}

bool findIntersection(ray Ray, polygon Poly, point& Answer)
{
    point plane_normal = crossProduct(vectorSub(Poly.P[1], Poly.P[0]), vectorSub(Poly.P[2], Poly.P[0]))

    float denominator = dotProduct(vectorSub(Ray.R2, Poly.P[0]), plane_normal)

    if (denominator == 0) { return FALSE } // ray is parallel to the polygon

    float ray_scalar = dotProduct(vectorSub(Poly.P[0], Ray.R1), plane_normal)

    Answer = vectorAdd(Ray.R1, scalarMult(ray_scalar, Ray.R2))

    // verify that the point falls inside the polygon

    point test_line = vectorSub(Answer, Poly.P[0])
    point test_axis = crossProduct(plane_normal, test_line)

    bool point_is_inside = FALSE

    point test_point = vectorSub(Poly.P[1], Answer)
    bool prev_point_ahead = (dotProduct(test_line, test_point) > 0)
    bool prev_point_above = (dotProduct(test_axis, test_point) > 0)

    bool this_point_ahead
    bool this_point_above

    int index = 2;
    while (index < Poly.count)
    {
        test_point = vectorSub(Poly.P[index], Answer)
        this_point_ahead = (dotProduct(test_line, test_point) > 0)

        if (prev_point_ahead OR this_point_ahead)
        {
            this_point_above = (dotProduct(test_axis, test_point) > 0)

            if (prev_point_above XOR this_point_above)
            {
                point_is_inside = !point_is_inside
            }
        }

        prev_point_ahead = this_point_ahead
        prev_point_above = this_point_above
        index++
    }

    return point_is_inside
}
于 2008-11-23T12:28:08.577 に答える
1

本書全体の章がこの特定の要件に専念してきました。ここで適切なアルゴリズムを説明するには長すぎます。特に、コンピュータ グラフィックスの参考文献をいくつでも読むことをお勧めします。

  • レイ トレーシング入門編。アンドリュー・S・グラスナー、ISBN 0122861604
于 2008-11-23T09:37:49.437 に答える