주어진 3D 그리드, 3 차원 구면 중심 및 반경, 구형에 포함되거나 교차 된 모든 셀을 신속하게 계산하고 싶습니다.빠른 구형 교차점
현재 저는 구의 (gridaligned) boundingbox를 가져 와서이 boundingbox의 최소 anx 최대 점에 대한 두 개의 셀을 계산합니다. 그 두 셀 사이의 각 셀에 대해, 박스 - 스페어 교차 테스트를합니다.
더 좋은 것이 있다면 큰 것이 될 것입니다.
감사합니다!
원을 그리는 데 사용할 수있는 Bresenham 알고리즘 버전이 있습니다. z = 0에서 2 차원 공간을 고려해보십시오 (구가 0,0,0 인 것으로 가정). 격자 점의 x-y 평면 만 봅니다. x = R, y = 0에서 시작하여 Bresenham 알고리즘을 따라 그리기 대신 y = y_R, x = 0까지 따르십시오. x 좌표가 낮은 모든 격자 점이 원 안에 있음을 알 수 있습니다. ~ x = x_center. 그것들을 목록에 넣거나, 세거나 다른 방법으로 기록하십시오. 2 차원 문제로 끝나면, z 대신 R까지 축소 된 반경 R (z) = sqrt (R^2-z^2)를 사용하여 z를 반복하면서 반복하십시오.
구체 중심이 실제로 격자 점에있는 경우 구의 오른쪽 반쪽 안쪽이나 바깥쪽에있는 모든 격자 점은 왼쪽에 미러 파트너가 있고 위/아래에도 마찬가지로 있으므로 차원 당 계산/목록의 절반. Bresenham을 45도 선까지만 실행하는 시간을 절약 할 수 있습니다. 센터에 상대적인 x, y 점에는 상대 y가 있기 때문입니다. 구가 어디에도있을 수 있으면 각 8 진수에 대한 결과를 계산해야합니다.
구의 내부 또는 외부에있는 개별 셀을 얼마나 효율적으로 계산하더라도 아무리 많은 셀을 표시해야하기 때문에 알고리즘은 항상 O (반지름^3)가됩니다. DarenW의 midpoint (일명 Bresenham) circle 알고리즘은 sqrt() 호출을 피하기 위해 제곱 된 반지름을 사용하여 교차점을 테스트하기 만하면 일정한 요소 속도 향상을 제공 할 수 있습니다.
O (r^3)보다 나은 성능을 원할 경우 플랫 그리드 대신 octree을 사용할 수 있습니다. 트리의 각 노드는 완전히 안쪽, 완전히 바깥 쪽 또는 부분적으로 안쪽으로 표시 될 수 있습니다. 부분적으로 내부 노드의 경우 트리를 재귀 적으로 처리하여 가장 정밀한 셀을 얻을 수 있습니다. 이것은 여전히 경계에 O (r^2 log r) 개의 마디 (O^(r^2)) 마킹을 필요로 할 것이고, O (log r)는 그 각각을 얻기 위해 트리를 밟을 것이다. 응용 프로그램의 문제.
교차점의 반경은 구의 중심으로부터 평면 제곱의 가장 가까운 점까지 거리 1을 뺀 값을 구의 반경과 같습니다. – amphetamachine
미안 - 뭐라구? 어떤 교차점의 반지름? 구가 교차하는 세포의 지표를 찾고 있습니다. – Mat