옥트리에 잎을 합치는 것

Question

나는 평면 ​​배열을 감지하고 싶습니다 (> 100000 포인트) 매우 큰 포인트 클라우드가 있습니다. 나는 팔레트를 사용하여 포인트를 아주 작은 평면 클러스터로 나누고 이웃을 병합하기로 결정했습니다 동일 평면 인 클러스터. 포함하는 배열 OctreeNode* children[8]와 OctreeNode의가있다 : 나는

내 Octree 구현은 포인터 구조를 사용 ... 빨리 작은 평면 클러스터로 포인트 클라우드를 분할,하지만 어떻게 효과적으로 나를 벗어난입니다 병합 C++ 코드를 작성했습니다 자식 노드에 대한 포인터이거나 리프 노드 인 경우 모두 NULL 포인터입니다.

내 첫 번째 생각은 각 OctreeNode 개체에서 Plane 개체에 대한 포인터를 유지하는 것이 었습니다. 포인트를 처음으로 분할 한 후, 팔레트의 각 리프는 리프에 포함 된 모든 포인트에 맞는 최소 제곱을 나타내는 Plane이됩니다. 그런 다음 트리의 모든 리프 노드를 반복합니다. 각 리프 노드에 대해 이웃 노드의 각 노드를 확인합니다. 인접한 노드의 평면을 현재 리프의 평면과 병합해야한다면 Plane* newPlane = Plane::mergePlanes(this->plane, neighbor->plane);을 호출하여 두 노드의 점을 나타내는 새 평면을 만듭니다.

문제가 생겨서 처음 두 비행기를 모두 새 비행기 (예 : plane = newPlane; neighbor->plane = newPlane;)로 대체하고 완료해야한다고 생각했습니다. (메모리 누수는 제쳐두고 실제 코드로 처리했습니다.) 불행하게도 이것은 실제로 작동하지 않습니다. 여러 비행기를 병합 한 후에는 이 하나만 Plane을 가리킬 수 있으며 단순히 포인터를 this->plane 및 neighbor->plane으로 바꾸어도 이전 비행기를 가리키는 모든 포인터가 대체되지는 않습니다.

솔루션은 처음 출시되었을 때도 hackish처럼 보였으 나 이제는 그 결함이 더욱 분명 해졌습니다. 누구든지 내가 생각해 낸 합병 방법을 고치는 방법을 생각하거나 더 나은 것을 생각할 수 있습니까?

는

Answer 1

표준 수정 프로그램은 노드를 지연 수정하는 것입니다. 당신이 가리키고있는 비행기를 보는 접근 방법을 가지고, 그것이 다른 곳에서 지적되었는지를 확인하십시오. 만약 그렇다면, 당신이 어디 있는지를 찾을 때까지 재귀 적으로 검색하고 모든 객체를 현재의 객체로 다시 채운 다음, 올바른 평면을 돌려 주면됩니다.

이것은 포인터를 따르는 것보다 훨씬 비싸지 만, 실제로는 최종 객체가 보이는 첫 번째 또는 두 번째 장소에있는 대부분의 시간 이후로 생각하면 거의 비싸지 않습니다.

Answer 2

VTK 비슷한 점 핸들 클래스 vtkIncrementalOctreePointLocator을 가지고 감사드립니다. 삽입 지점을 병합하는 것이 이상적이라고 생각합니다.

예컨대 :

double xyz[3]; // location 
id_type point_id; // we get back the point id 

// bool InsertUniquePoint(double xyz[3], id_type &point_id); 
// return value is true, if new point inserted 
bool value = inserter->InsertUniquePoint(xyz, point_id); 

그래서 내 의견 : 너무 큰 클래스, 쉽게 경우 다시 빌드합니다.