New efficient octree construction from multiple object silhouettes with construction quality control

Abstract

In this paper, we propose an octree construction method with a new subdivision strategy which is governed by the degree of overlapping between each generated octant and the object. The specification of a maximum level of subdivision required in the conventional method is not needed. We introduce "grey-grey" and "grey-black" nodes based on a construction quality measure. The construction quality is measured by the maximum 2D projection error of the projected octant image with respective to the object silhouette in all views. Only those octants which are "grey-grey" nodes will be subdivided. Furthermore, we present a fast computation of the 2D projection and a new intersection test to reduce the computer processing time. Computer simulations are conducted to show that the new method outperforms the conventional method in terms of memory space and computation time subject to the same level of construction quality.