3D 점-삼각형 충돌 감지

StackOverflow https://stackoverflow.com/questions/99542

  •  01-07-2019
  •  | 
  •  

문제

다음 물리적 시뮬레이션에서 부동 소수점 오류를 어떻게 수정합니까?

  • 원점(x, y, z),
  • 힘이 적용된 후 원하는 지점(x', y', z')입니다.
  • 모서리 BC를 공유하는 두 개의 삼각형(A, B, C) 및 (B, C, D)

충돌 감지를 위해 이 방법을 사용하고 있습니다.

For each Triangle
    If the original point is in front of the current triangle, and the desired point is behind the desired triangle:
        Calculate the intersection point of the ray (original-desired) and the plane (triangle's normal).
        If the intersection point is inside the triangle edges (!)
            Respond to the collision.
        End If
    End If
Next Triangle

내가 겪고 있는 문제는 때때로 점이 BC 선에 너무 가까워서 기술적으로 항상 하나 또는 다른 삼각형과 충돌해야 함에도 불구하고 두 삼각형 중 하나와 충돌하지 못하는 부동 소수점 수학의 회색 영역에 속한다는 것입니다. 그들은 우위를 공유합니다.이런 일이 발생하면 점이 두 모서리 공유 삼각형 사이를 바로 통과합니다.나는 코드의 한 줄을 다음과 같이 표시했습니다. (!) 왜냐하면 그곳이 내가 변화해야 할 곳이라고 믿기 때문입니다.

매우 제한된 상황에서 작동하는 한 가지 아이디어는 에지 테스트를 건너뛰는 것입니다.효과적으로 삼각형을 평면으로 변환합니다.이것은 내 메시가 볼록 ​​껍질인 경우에만 작동하지만 볼록 모양을 만들 계획입니다.

저는 특히 모든 앞뒤 테스트에 내적과 삼각형 법선을 사용하고 있습니다.

도움이 되었습니까?

해결책

이는 가장자리와 정점이 있는 일부 형상에 대해 단일 광선을 촬영할 때 피할 수 없는 문제입니다.물리적 시뮬레이션이 가장 작은 수치적 부정확성을 찾아내는 모습은 정말 놀랍습니다!

다른 응답자들이 제안한 설명과 해결책 중 일부는 효과가 없을 것입니다.특히:

  • 수치적 부정확성으로 인해 광선이 "간극을 통과"할 수 있습니다.문제는 선 BC에 대해 테스트하기 전에 광선을 ABC 평면과 교차한다는 것입니다(예를 들어 점 P를 얻음).그런 다음 선 BC에 대해 테스트하기 전에 평면 BCD(점 Q를 얻음)와 광선을 교차합니다.P와 Q는 모두 가장 가까운 부동 소수점 근사값으로 표현됩니다.이것들이 정확히 놓여 있어야 하는 평면 위에 놓여 있다고 기대할 이유가 없습니다. 따라서 BC의 왼쪽에 P와 BC의 오른쪽에 Q를 모두 가질 수 있는 모든 가능성이 있습니다.

  • 작거나 같은 테스트를 사용하는 것은 도움이 되지 않습니다.문제는 광선과 평면의 교차점의 부정확성입니다.

  • 제곱근은 문제가 되지 않습니다.내적과 부동 소수점 나누기를 사용하여 필요한 모든 계산을 수행할 수 있습니다.

다음은 몇 가지 진정한 솔루션입니다.

  • 볼록 메시의 경우 말한 대로 모든 평면에 대해 테스트하고 가장자리와 꼭지점을 무시할 수 있습니다(따라서 문제를 완전히 피할 수 있음).

  • 각 삼각형과 광선을 차례로 교차하지 마십시오.대신 스칼라 삼중곱.(이 방법은 각 삼각형을 고려할 때 광선과 모서리 BC에 대해 정확히 동일한 계산 순서를 만들어 두 삼각형 사이의 수치적 부정확성이 최소한 일관되게 유지되도록 합니다.)

  • 볼록하지 않은 메시의 경우 가장자리와 정점에 약간의 너비를 지정합니다.즉, 메시의 각 꼭지점에 작은 구를 배치하고 메시의 각 가장자리를 따라 얇은 원통을 배치합니다.이러한 구, 원통 및 삼각형과 광선을 교차시킵니다.이러한 추가 기하학적 수치는 메쉬의 가장자리와 꼭지점을 통과하는 광선을 중지합니다.

책을 강력 추천해드려요 실시간 충돌 감지 크리스터 에릭슨.446~448페이지에는 이 정확한 문제에 대한 논의가 있고, 184~188페이지에는 광선과 삼각형을 교차시키는 스칼라 삼중 곱 접근 방식에 대한 설명이 있습니다.

다른 팁

가장자리에 있는지 테스트를 포함하지 않는 것 같습니다("내부 삼각형 가장자리"라고 쓰고 있음).코드를 "작거나 같음"(내부 또는 중복)으로 변경해 보세요.

부동 소수점 정밀도가 적용되는 방식으로 광선이 삼각형 사이에 정확하게 떨어질 가능성은 다소 낮습니다.이것이 실제로 문제라고 절대적으로 확신하십니까?

어쨌든 가능한 해결책은 단 하나의 광선을 쏘는 대신 서로 매우 가까운 세 개의 광선을 쏘는 것입니다.하나가 정확히 그 사이에 있으면 나머지 둘 중 적어도 하나는 삼각형에 빠지는 것이 보장됩니다.

이를 통해 문제가 실제로 부동 소수점 오류인지 아니면 그보다 더 가능성이 높은 오류인지 테스트할 수 있습니다.

@성명:실제로 내 코드에서는 이미 "크거나 같음" 비교를 사용하고 있습니다. 제안해 주셔서 감사합니다.+1

내 현재 솔루션은 가장자리 테스트에 약간의 넛지 양을 추가하는 것입니다.기본적으로 각 삼각형을 테스트할 때 부동 소수점의 오류에 대응하기 위해 가장자리가 아주 작은 양만큼 밀려납니다.0과 같은지 테스트하는 대신 부동 소수점 계산 결과가 0.01보다 작은지 테스트하는 것과 비슷합니다.

이것이 합리적인 해결책입니까?

거리를 측정하는 경우 제곱근에 주의하세요.쟤네는 버리는 고약한 버릇이 있어 반 당신의 정확성.이러한 계산 중 몇 가지를 쌓아두면 빠르게 큰 문제가 발생할 수 있습니다.다음은 내가 사용한 거리 함수입니다.

double Distance(double x0, double y0, double x1, double y1)
{
  double a, b, dx, dy;

  dx = abs(x1 - x0);
  dy = abs(y1 - y0);

  a = max(dx, dy));
  if (a == 0)
    return 0;
  b = min(dx, dy);

  return a * sqrt( 1 + (b*b) / (a*a) );
}

마지막 연산은 제곱근이 아니므로 더 이상 정밀도를 잃지 않습니다.

나는 내가 진행하고 있던 프로젝트에서 이것을 발견했습니다.그것을 연구하고 그것이 무엇인지 알아낸 후에 나는 그를 축하할 책임이 있다고 생각되는 프로그래머를 추적했지만 그는 내가 무슨 말을 하는지 전혀 몰랐습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top