標題: Fast octree construction endowed with an error bound controlled subdivision scheme
作者: Chou, HL
Chen, Z
資訊工程學系
Department of Computer Science
關鍵字: octree construction;subdivision strategy;octant projection;cross ratio;distance map;construction quality;memory space;computation time
公開日期: 1-May-2006
摘要: 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.
URI: http://hdl.handle.net/11536/12347
ISSN: 1016-2364
期刊: JOURNAL OF INFORMATION SCIENCE AND ENGINEERING
Volume: 22
Issue: 3
起始頁: 641
結束頁: 657
Appears in Collections:Articles


Files in This Item:

  1. 000237907900012.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.