| [ QuizWit ] in KIDS 글 쓴 이(By): staire (강 민 형) 날 짜 (Date): 2000년 6월 29일 목요일 오후 12시 49분 31초 제 목(Title): Re: 퀵 소트보다 빠른 알고리듬이 있나요 사실은 옥트리에 대한 글인데 제목이 이상하게 붙은 건 제 탓이 아니라 환상님 책임입니다. ^^ voxel은 아시죠? 2차원에서의 pixel을 3차원으로 확장한 최소단위 정육면체 정도로 생각하시면 될겁니다. 그런데 3차원 물체를 voxel로 모델링하면서 해상도를 올리려면 무식하게 큰 메모리가 필요할 뿐 아니라 모델링 이후의 처리에 걸리는 시간도 만만치 않습니다. 그런데 모델링할 대상의 형상이 얼마나 복잡한가에 관계되는 문제지만 대개 꽉 찬 voxel과 빈 voxel(빈 공간)은 몰려다닙니다. 그것을 이용해서 다음과 같은 방법의 모델링이 가능합니다. 1. 다음과 같은 structure와 정수 root를 정의합니다. struct Octree { Octree child[8] } 2. 모델링할 대상을 완전히 담을 수 있는 정육면체를 정의합니다. 3. root에 다음과 같은 값을 부여합니다. - 정육면체 속이 꽉 찼으면 1 - 정육면체 속이 완전히 비었으면 0 - 일부 차 있고 일부 비었다면 새로운 Octree를 하나 생성한 후 그 Octree의 포인터를 root에 넣은 후 정육면체를 각 면에 평행한 평면으로 절반으로 쪼개어 (8조각이 나겠죠?) 0에서 7까지 번호를 붙입니다. 4. 옥트리의 8개의 child는 8개의 조각에 대응합니다. 각각의 child 값은 3에서와 마찬가지로 속이 찼으면 1, 비었으면 0, 이도저도 아니라면 다시 새로운 옥트리 하나를 생성시켜서 그 포인터를 줍니다. 5. 4번을 해상도 한계에 도달하거나 모든 값이 0또는 1이 될 때까지 반복합니다. 이런 식으로 모델링하면 각각의 정육면체를 voxel로 잘게 썰지 않고서도 3차원 형상을 표현할 수 있습니다. 형상이 단순한 부분은 큰 정육면체로, 복잡하거나 섬세한 부분은 작은 정육면체로 '필요한 만큼 작은' voxel로 표현하기 때문이죠. ----------- Prometheus, the daring and enduring... |