라인 세그먼트가 구체를 교차하는지 여부를 테스트합니다

Question

나는 라인 세그먼트 (즉, 두 점 사이)가 구를 교차하는지 여부를 결정하려고 노력하고있다. 나는 세그먼트가 구 표면과 교차하는지 여부에 관계없이 교차로의 위치에 관심이 없다. 누구든지 가장 효율적인 알고리즘이 무엇인지에 대한 제안이 있습니까? (교차로 위치에 관심이 없기 때문에 일반적인 Ray-Sphere 교차로 알고리즘보다 간단한 알고리즘이 있는지 궁금합니다).

Answer 1

나는 표준 방식이 무엇인지 모르겠지만, 그것이 교차하는지 알고 싶다면 여기에 내가 할 일이 있습니다.

일반적인 규칙 ... sqrt () 또는 기타 값 비싼 작업을 피하십시오. 가능하면 반경의 제곱을 처리하십시오.

1. 시작점이 구의 반경 내부에 있는지 확인하십시오. 이것이 사실이 아니라는 것을 알고 있다면이 단계를 건너 뛰십시오. 당신이 내부에 있다면, 당신의 광선은 구를 교차시킬 것입니다.

여기에서 시작점은 구의 외부에 있습니다.

2. 이제 구체에 맞는 작은 상자를 상상해보십시오. 해당 상자 밖에있는 경우 광선의 X 방향, y 방향 및 z 방향을 확인하여 광선에서 시작하는 상자의 측면이 교차하는지 확인하십시오. 이것은 간단한 부호 점검 또는 0과 비교해야합니다. 당신이 바깥에 있고 그것에서 멀어지면 결코 교차하지 않을 것입니다.

여기에서 당신은 더 복잡한 단계에 있습니다. 출발점은 가상 상자와 구 사이입니다. 미적분학과 지오메트리를 사용하여 단순화 된 표현식을 얻을 수 있습니다.

당신이하고 싶은 일의 요지는 광선과 구 사이의 가장 짧은 거리가 구의 반경보다 적은지 결정하는 것입니다.

당신의 광선이 (x0 + it, y0 + jT, Z0 + Kt), 그리고 당신의 구의 중심은 (xs, ys, zs)에 있습니다. 그래서 우리는 그것이 가장 짧은 (xs -x0 -i를 줄 수 있도록 t를 찾고 싶습니다.t, ys -y0 -jt, zs -z0 -k티).

x = xs -x0, y = yx -y0, z = zs -z0, d = 벡터 제곱 크기

d = x^2 -2*x나t + (i*t)^2 + y^2-2*y제이t + (j*t)^2 + z^2-2*z케이t + (k*t)^2

d = (i^2 + j^2 + k^2)t^2- (xI + yJ + Zk)*2*t + (x^2 + y^2 + z^2)

dd/dt = 0 = 0 = 2*t*(i^2 + j^2 + k^2) -2*(xI + yj + z*k)

t = (xI + yj + z*k) / (i^2 + j^2 + k^2)

d = .... 결과가 구의 반경 제곱보다 작거나 같으면 교차점이 있습니다. 그것이 더 크면 교차로가 없습니다.

Answer 2

교차 여부를 아는 경우에만 관심이있는 경우 기본 알고리즘이 다음과 같이 보일 것입니다 ...

레이 라인의 벡터 인 A-> B가 있다고 생각합니다.

이 벡터와 구의 중심 사이의 가장 짧은 거리는 광선 벡터의 교차점과 구의 중심을 통과하는 90 도인 벡터에서 발생한다는 것을 알고 있습니다.

따라서 두 개의 벡터가 있으며, 그 방정식은 완전히 완전히 정의되었습니다. 선형 대수학을 사용하여 벡터의 교차점을 해결하고 라인의 길이 (또는 라인 길이의 제곱)를 더 효율적으로 반경 (또는 반지름 제곱보다 적은 경우 테스트 할 수 있습니다. ) 당신의 구체.

Answer 3

이 페이지 이 문제에 대한 정확한 솔루션이 있습니다. 본질적으로, 당신은 선의 방정식을 구의 방정식으로 대체 한 다음 결과 2 차의 판별제를 계산합니다. 판별 값은 교차점을 나타냅니다.

Answer 4

당신은 정확도를 원한다면 어쨌든 그 위치를 작동시켜야합니다. 속도 알고리즘을 향상시키는 유일한 방법은 Ray-Sphere 교차로에서 Ray-Bounding-Box 교차로로 전환하는 것입니다.

또는 더 깊이 가서 SQRT 및 기타 내부 기능 호출을 개선 할 수 있습니다.

http://wiki.cgsociety.org/index.php/ray_sphere_intersection