Recent advance in sample acquisition technology has made 3D samples of large size quite available. However, in many applications, these samples are much denser than necessary. Thus, a decimation step is required. To determine which area is oversampled or undersampled, the shape of the Voronoi diagram of the samples has been used.
However, computing the Voronoi diagram of a large sample takes much time and memory. In this thesis, we propose a sample decimation scheme without the computation of the Voronoi diagram of all the sample points. Instead, we incrementally select necessary samples using only local Voronoi diagram computation. Using our approach, we could decimate much larger samples more efficiently than the previous methods.
최근 들어 레이저 스캐너 등 3차원 물체의 표면에서 샘플을 추출하는 기술의 발달로 인하여, 3차원 상의 점들의 집합을 이용하는 다양한 모델링과 응용방법들이 개발되어 왔다. 그러나 이렇게 얻어진 샘플은 우리가 필요로 하는 것 이상으로 조밀하여 데이터의 크기가 크기 때문에, 이 샘플을 이용하는 여러 알고리즘의 계산시간을 늘리는 문제를 발생시켰다. 실제로 원표면의 기하학적 특징에 따라 그 표면을 나타내기 위한 샘플의 수는 크게 작아질 수 있다. 즉, 복잡한 부분에서는 더 조밀한 샘플들이 필요하고, 반대로 단순한 부분에서는 적은 수의 샘플로도 전체 표면을 나타내기에 충분하다.
표면의 복잡도에 따라 샘플을 단순화 시키기 위하여 기존 연구에서는 보로노이 다이어그램 이라는 특별한 구조를 사용하였다. 하지만 방대한 양의 샘플에 대한 보로노이 다이어그램은 계산시간의 소모가 크고, 많은 메모리가 소요되는 단점이 있다. 큰 사이즈의 샘플에 대한 disk swapping과 관련된 bottleneck 문제는 더욱 심각하다. 본 논문에서는 전체 샘플의 보로노이 다이어그램을 구하지 않으면서, 원표면의 기하학적 특징을 보존하는 효율적인 샘플 단순화 기법을 제시한다.
