Fast Octree Construction Endowed with an Error Bound Controlled Subdivision Scheme

周宏隆(Hong-Long Chou) ； 陳稔(Zen Chen)

《Journal of Information Science and Engineering》 22卷3期 (2006/05) Pp. 641-657

https://doi.org/10.6688/JISE.2006.22.3.11

並列摘要

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.

並列關鍵字

octree construction ； subdivision strategy ； octant projection ； cross ratio ； distance map ； construction quality ； memory space ； computation time