Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15]


Journal of Information Science and Engineering, Vol. 22 No. 3, pp. 641-657 (May 2006)

Fast Octree Construction Endowed with an Error Bound Controlled Subdivision Scheme

Hong-Long Chou and Zen Chen
Department of Computer Science and Information Engineering
National Chiao Tung Unviersity
Hsinchu, 300 Taiwan
E-mail: {hlchou; zchen}

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.

Keywords: octree construction, subdivision strategy, octant projection, cross ratio, distance map, construction quality, memory space, computation time

Full Text () Retrieve PDF document (200605_11.pdf)

Received March 19, 2004; revised April 20, 2004; accepted May 18, 2004.
Communicated by H. Y. Mark Liao.