TY - GEN

T1 - An iterative, octree-based algorithm for distance computation between polyhedra with complex surfaces

AU - Borrmann, André

AU - Schraufstetter, Stefanie

AU - Van Treeck, Christoph

AU - Rank, Ernst

PY - 2007

Y1 - 2007

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84891340002&partnerID=8YFLogxK

U2 - 10.1061/40937(261)13

DO - 10.1061/40937(261)13

M3 - Conference contribution

AN - SCOPUS:84891340002

SN - 0784409374

SN - 9780784409374

T3 - Congress on Computing in Civil Engineering, Proceedings

SP - 103

EP - 110

BT - Computing in Civil Engineering - Proceedings of the 2007 ASCE International Workshop on Computing in Civil Engineering

T2 - 2007 ASCE International Workshop on Computing in Civil Engineering

Y2 - 24 July 2007 through 27 July 2007

ER -