광선과 다각형 사이의 교차점을 찾는 가장 빠른 방법은 무엇입니까?
-
10-07-2019 - |
문제
질문이 묻는대로. 가급적 의사 코드로 답변하고 참조됩니다. 정답은 단순성보다 속도를 평가해야합니다.
해결책
보다 3D의 광선, 세그먼트, 비행기 및 삼각형 교차점. 다각형을 삼각 할 수있는 방법을 찾을 수 있습니다.
Ray/Polygon 교차로가 정말로 필요한 경우 16.9입니다. 실시간 렌더링 (13.8).
우리는 먼저 광선과 [Ploygon의 평면] 사이의 교차점을 계산합니다.
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 개의 디피 온으로 줄어 듭니다 ...
자세한 내용은 책을 참조하십시오.
다른 팁
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
}
전체 도서 장은이 특정 요구 사항에 전념했습니다. 여기에서 적절한 알고리즘을 설명하기에는 너무 길다. 특히 컴퓨터 그래픽에서 몇 가지 참조 작품을 읽는 것이 좋습니다.
- Ray Tracing 소개, ed. Andrew S. Glassner, ISBN 0122861604
function Collision(PlaneOrigin,PlaneDirection,RayOrigin,RayDirection)
return RayOrigin-RayDirection*Dot(PlaneDirection,RayOrigin-PlaneOrigin)/Dot(PlaneDirection,RayDirection)
end
(PlanEdirection은 평면에 수직 인 단위 벡터입니다)
제휴하지 않습니다 StackOverflow