| Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] | [ 12] | [ 13] | [ 14] | [ 15] |
¡@
Hong-Long Chou and Zen Chen
Department of Computer Science and Information Engineering
National Chiao Tung Unviersity
Hsinchu, 300 Taiwan
E-mail: {hlchou; zchen}@csie.nctu.edu.tw
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.
Received March 19, 2004; revised April 20, 2004; accepted May 18, 2004.
Communicated by H. Y. Mark Liao.