An Iterative, Octree-Based Algorithm for Distance Computation Between Polyhedra with Complex Surfaces
An Iterative, Octree-Based Algorithm for Distance Computation Between Polyhedra with Complex Surfaces
复制标题
一种基于八叉树的迭代复杂曲面多面体距离计算算法
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
E. Rank
中科院分区：
文献类型：
--
作者：
A. Borrmann;Stefanie Schraufstetter;C. Treeck;E. Rank
In a current research project, our group is developing a 3D Spatial Query Language for Building Information Models. Among other features, the spatial language includes metric operators, i.e. operators that depend on the distance between 3D spatial objects. To implement these operators, a fast and well-scaling algorithm based on the octree-encoded discretized geometry for computing the distance between two polyhedra was developed. The proposed algorithm implements a divide-and-conquer strategy: It uses comparably cheap polygon-octant intersection tests to build up the octree, and subsequently performs very simple distance calculations between two octants, that can be realized as fast integer operations. The paper describes the algorithm in detail, discusses its scaling behavior and the advantages of using an octree encoding.
