octree subdivision에 대한 큐브와 CSG 객체 간의 교차점 찾기

Question

CSG (Constructive Solid Geometry) 트리에서 원래 설명하는 볼륨을 나타내는 octree를 만들려고합니다.

내 원래 계획은 전체 개체를 포함하는 큰 큐브로 시작한 다음 8 개의 하위 큐비의 각각에 대해 완전히 바깥에 있고 완전히 개체 내부에 있고 내부에있는 큰 큐브로 시작하는 것이 었습니다 및 외부. 이 "중간"큐비는 재귀 적으로 세분화됩니다.

내 문제는 어리석은 일이지만, 위와 같이 큐브를 분류 할 수 있도록 큐브와 CSG 객체의 교차점을 찾는 방법을 고안 할 수는 없습니다.

내 CSG 구조는 합집합, 교차 및 차감의 부울 연산과 함께 큐브, 구 및 원통형 (이후에는 아마도 토러스)과 같은 프리미티브로 작성됩니다. CSG의 명시 적 트리 구조 옆에

는 그 표현에서 나는 또한 포인트 (x,y,z) 외부 (> 0) 또는 내부 (< 0) 객체 인 경우 말해 것이다 거리 함수 d(x,y,z)의 종류가.

큐브가 CSG 구조에 의해 설명 된 객체와 교차하는지 어떻게 알 수 있습니까?

Answer 1

희소 한 복셀 octree를 다시 발명하려고하는 것처럼 들립니다.

제 생각에는 고려해야 할 최상의 큐브 해상도로 샘플을 가져 오는 것입니다 (어쨌든 해상도를 줄여야 함).

거리 함수가 Z-Order 곡선 (모턴 (Morton) 순서라고도 함)에있는 점에 대해 샘플링하고 거리 함수가 부호를 변경할 때마다 좌표를 기록하십시오. Z 차수 곡선의 특성에 따라 필요한 저장 공간은 부피가 아닌 표면적과 관련하여 점근 적으로 조정해야합니다.

이 구조는 모톤 (Morton) 순서가 8 진수의 깊이 우선 탐색과 동일하기 때문에 이산 octree와 기능적으로 동일합니다 (따라서 그대로 사용 가능).

그러나 요점은,이 구조를 사용하면 큐브 모서리의 모턴 화 된 좌표의 이진 검색을 사용하여 효율적으로 팔진 트리 큐브 교차를 테스트 할 수 있다는 것입니다. 이 작업을 수행 할 때 octree aligned cube는 2 개의 좌표를 사용하여 설명 할 수 있습니다. 우리는 Morton-order와 관련하여 "lower"와 "upper"큐브 코너를 가질 것이고, 사인 변경이있을 때만 (큐브가 완전히 비어 있지 않거나 가득 차 있지는 않음) 큐브가 "흥미로운"것입니다 간격은 (lower,upper]입니다. 개별 샘플 CSG 프리미티브가 가장 작은 눈금 선 안에 완전히 들어 가지 않도록 원본 샘플링 해상도를 선택하면 아무 기능도 놓치지 않습니다.

명시 적으로 큐브 경계와 교차점을 찾는 것이 약간 복잡하지만 공정하게 수행 할 수 있습니다. 내 기억에 입방체 경계에서 발생하는 부호 변화를 고려해야하고 표면 경계가 큐브 경계와 일치한다는 특수한 경우를 고려해야합니다 (완전한 전체 큐브에서도 발생할 수 있음). 내가 수학을 계산하지 않았기 때문에 나는 독자의 연습 문제로 남겨 둘 것입니다. 나는 앞으로 더 당신을 도우려고 노력하고 싶었습니다.