Fast octree construction endowed with an error bound controlled subdivision scheme

Abstract

In the conventional octree construction method any grey octant is subdivided recursively until all its descendant octants are no longer grey. The subdivision process is executed no matter how small the white portion in the grey octant is. When there are many grey octants, each containing a fairly small white portion, then the huge increase in the resulting descendant nodes due to the subdivisions may cause the construction process to terminate due to an insufficient amount of memory. In such a case the subdivisions made are not worthwhile. In this paper, we shall make effective use of octant subdivision to improve the overall system performance. A new octree construction method is proposed with a novel subdivision strategy such that only those octants with a projection error exceeding a pre-specified error bound will be subdivided. Furthermore, we also present a fast way to compute the 2D projection of octant vertices and a new intersection test to reduce overall processing time. Computer simulations are conducted which show that the new method performs better than the conventional method in terms of memory space and computation time. Moreover, a theoretical analysis of the performance of the new method is included.