Premium
An efficient distance algorithm for interval‐based octree‐encoded CSG objects with time‐space coherence utilization
Author(s) -
Dyllong Eva,
Grimm Cornelius
Publication year - 2007
Publication title -
pamm
Language(s) - English
Resource type - Journals
ISSN - 1617-7061
DOI - 10.1002/pamm.200700567
Subject(s) - octree , interval (graph theory) , algorithm , computer science , rounding , range (aeronautics) , coherence (philosophical gambling strategy) , realization (probability) , interval arithmetic , theoretical computer science , mathematics , engineering , mathematical analysis , statistics , combinatorics , bounded function , operating system , aerospace engineering
In this paper, a new distance algorithm for octree‐encoded CSG objects is presented. Interval vectors are used to describe the nodes of the octree for a reliable and efficient realization of the hierarchical data structure. The algorithm yields the lower bounds of the distance between the objects and is based on accurate algorithms that have been shown in [1], but involves interval arithmetic for reliable handling of rounding errors. Furthermore, time‐space coherence is utilized to increase the efficiency of sequential distance calculations. Experiments validate the approach and show its range of applicability. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)