발산 정리로 3D 메시 부피 계산을 엄청나게 빠르게
Hilariously Fast Volume Computation with the Divergence Theorem
이 글은 닫힌 삼각형 메시의 부피를 계산하는 빠른 알고리즘을 소개합니다. 발산 정리를 이용해 부피 적분을 표면 적분으로 변환하고, 각 삼각형에 대해 간단한 산술 연산만으로 부피를 구합니다. 이 알고리즘은 삼각형 수에 선형인 O(n) 복잡도를 가지며, 삼각형당 7번의 덧셈과 3번의 곱셈만 필요합니다. CPU만 사용하는 Raspberry Pi에서도 초당 30 million 개의 삼각형을 처리할 수 있을 만큼 빠릅니다. 저자는 이 알고리즘이 독창적이지 않을 수 있다고 인정하며, 유사한 알고리즘이 기존 논문에 있음을 발견했습니다.
이 알고리즘은 수치 적분이나 미분을 전혀 포함하지 않으며, 삼각형 수에 선형인 O(n) 복잡도를 가집니다.
HN 토론
51- physicsguy
이건 배경 지식에 따라 "와, 이거 대단한데!" 또는 "어, 이 트릭은 꽤 잘 알려져 있다고 생각했는데!"라고 하게 되는 그런 것 중 하나입니다 ;)
여기 1980년에 Fortran으로 작성된 유사한 구현이 있는데, 무게 중심 같은 다른 속성도 계산합니다:
Algorithm 550: Solid Polyhedron Measures
A. M. Messner and G. Q. Taylor
ACM Trans. Math. Softw., 6(1), Mar 1980, pp.121--130
키워드: polyhedron, graphics, numerical integration
언어: Fortran 66/77; Shar Index: Z; Gams: P
파일 크기: 19.1 KB;
하지만 Messner가 먼저 발표한 것은:
A. M. Messner, "A surface Integral method for computer
calculation of mass properties", Paper No. 852, 29TH ANNUAL
CONF. OF THE SOCIETY OF AERONAUTICAL WEIGHT ENGINEERS,
Washington, D.C., May 1970.
제 생각에는 그렇습니다.
- eterevsky
메시의 모든 삼각형을 가져와서 그것과 한 평면에 대한 투영 사이의 프리즘 같은 다면체의 부피를 계산하고, 투영의 방향에 따라 + 또는 - 부호를 붙이는 것과 같은 것 아닌가요? 이런 종류의 공식은 기본 기하학을 기반으로 작동합니다.
- srean
반면에, 격자점에 꼭짓점이 있는 다각형의 면적을 계산하려면 내부 점의 수 I와 경계 점의 수 B를 세면 됩니다. 그러면 면적 A는
A = I + B/2 - 1
입니다.
이것은 Pick의 정리입니다
https://en.wikipedia.org/wiki/Pick's_theorem
제가 가장 좋아하는 결과 중 하나입니다. 불행히도 고차원으로는 그렇게 잘 일반화되지 않습니다.
게시물처럼 다면체의 부피를 원한다면 신발끈 공식의 3차원 유사체(본질적으로 동일)를 사용할 수 있습니다.
Va, Vb, Vc를 표면의 삼각분할에서 삼각형 ∆의 꼭짓점이라고 합시다. 원점에 대해 일관된 순서/방향으로 꼭짓점을 지정해야 합니다.
그러면 부피 V는 모든 그러한 삼각형에 대한 부호 있는 부피의 합입니다:
V_∆ = 1/6 Va ^ Vb ^ Vc.
이것이 부호 있는 면적과 부피, 행렬식, 외대수의 아름다움입니다.
이것이 왜 그런지 이해하려면 이 짧고 아름다운 비디오가 있습니다
- elikoga
제 직감으로는 순진한 공식이 삼각형 피라미드 부피를 원점에 대해 방향에 따라 부호를 붙여 합산하는 것이라고 생각합니다. 그들이 유도한 것도 그런 것 같습니다. 이것은 각 모서리에 대해 삼각형 면적을 합산하여 2D 다각형 면적을 계산하는 일반화이며, 저는 GIS 데이터에서 지도 다각형 면적을 계산하는 수학 캠프에서 이것을 배웠습니다. AI 시대 이전에는 수학 지식을 얻기가 어려웠다고 기억하지만, 이렇게 어려웠던 것은 기억나지 않습니다.
저자는 "렌더링한 메시를 샘플링하는 것과 동일하다"가 무슨 뜻인지 모르겠습니다.
- ahaferburg
여기서 강조점은 메시가 단순하고 닫혀 있어야 한다는 것입니다. 출력에 의존하기 전에 이러한 전제 조건을 검증하십시오.
강체의 관성 행렬을 계산하기 위한 모멘트에 대한 유사한 공식도 있습니다.