A level-of-detail (LOD) modeling in computer graphics is to control the number of polygons in mesh at run-time to reduce the rendering cost of small, distant, unimportant geometry. In this paper, we propose the marching cube octree as a scheme for representing and generating the mesh of various level-of-details efficiently.
In the surface reconstruction, modified marching cubes are used for reconstructing the initial mesh. Instead of a midpoint which is used in the original algorithm [57], the ratio of adjacent vertex is used for the triangulation. The results are also feasible when low resolution data is given. These marching cubes are used for the leaf nodes of the marching cube octree.
The marching cube octree is constructed using an octree structure with the marching cubes. To support continuous LOD between levels the priority numbering is proposed. And all nodes are numbered by proposed algorithm. Using adjacent node check and priority queue, node priority numbering can traverse both breadth and depth.
The LOD meshes are generated at run-time using proposed efficient algorithm. It triangulates only needed nodes of the marching cube octree to cover up the whole surface of mesh. Using the priority numbers on nodes and flagging, the LOD mesh can be generated by only referencing without floating point operations which the other LOD models need.
컴퓨터 그래픽스 분야에서의 상세화 모델링(Level-of-detail modeling)이란 실시간에 mesh을 이루는 다각형의 개수를 조절하는 것을 말한다. 상세화 모델링은 작거나 멀거나 중요하지 않은 위치의 rendering 비용을 줄이기 위해서 꼭 필요하다. 이 논문에서는 marching cube 8진트리를 이용한 상세화 모델을 제안하는데 이것은 다양한 상세화 정도의 mesh를 효율적으로 생성하기에 적합한 방법이다.
표면 재구성 단계에서는 기존의 marching cube 알고리즘을 조금 수정하여 초기 mesh를 생성하게 된다. 기존의 marching cube에서 사용하던 중간점 대신 이웃한 꼭지점의 비율을 이용하여 삼각형을 생성한다. 이 방법은 입력 데이터의 해상도가 낮아도 만족스러운 결과를 보여준다. 이 단계에서 사용된 marching cube는 marching cube 8진트리의 말단 노드가 된다.
Marching cube 8진트리는 marching cube를 가지고 8진트리를 구성한 것이다. 모든 노드는 각 단계간에 상세화 정도를 연속적으로 해주기 위해서 우선순위가 매겨진다. 우선순위를 매길 때는 주변 노드 검사와 우선순위 queue를 사용하여 트리의 노드를 방문하게 된다. 이 때 단계가 다른 인접한 두 노드 사이에 생기는 틈새를 메우기 위한 계수도 미리 구해둔다.
구성된 marching cube 8진트리를 바탕으로 논문에서 제안된 효율적인 알고리즘에 의해 실시간으로 상세화 mesh를 생성한다. 이 때 mesh의 표면을 구성하는 노드만 참조해서 삼각형을 만들게 된다. 우선순위와 표시하기(flagging)를 이용하는 이 알고리즘은 다른 방법에서 필요한 부동소수점연산이 필요 없고 단지 참조만으로 구성되기 때문에 효율적이다.
