TY - JOUR

T1 - OCTREES OF OBJECTS IN ARBITRARY MOTION

T2 - REPRESENTATION AND EFFICIENCY.

AU - Weng, Juyang

AU - Ahuja, Narendra

N1 - Funding Information:
This research was supported in part by the National Bureau of Standards under Grant COMM 60NANB4D0004 and the National Science Foundation under Grant ECS 83-52408.

PY - 1987

Y1 - 1987

N2 - An algorithm is presented that updates the octree of a three-dimensional object after the object has undergone arbitrary rotation and translation. The algorithm moves each of the black leaves and then adds the subtree corresponding to the displaced black leaf. The algorithm uses a computationally efficient method to detect the intersections of moved blocks with octree tessellation. On the average, the space and time complexities of the algorithm are both bounded by O(Kn), where K is the number of nodes in the source tree and n is the logarithm of the side-length of the universe space. The quantization errors are prevented from accumulating by maintaining a compact source octree. Each incremental displacement is performed with respect to the source tree. Implementation results are given for the motion of synthetic three-dimensional objects.

AB - An algorithm is presented that updates the octree of a three-dimensional object after the object has undergone arbitrary rotation and translation. The algorithm moves each of the black leaves and then adds the subtree corresponding to the displaced black leaf. The algorithm uses a computationally efficient method to detect the intersections of moved blocks with octree tessellation. On the average, the space and time complexities of the algorithm are both bounded by O(Kn), where K is the number of nodes in the source tree and n is the logarithm of the side-length of the universe space. The quantization errors are prevented from accumulating by maintaining a compact source octree. Each incremental displacement is performed with respect to the source tree. Implementation results are given for the motion of synthetic three-dimensional objects.

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

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

U2 - 10.1016/S0734-189X(87)80164-0

DO - 10.1016/S0734-189X(87)80164-0

M3 - Article

AN - SCOPUS:0023398950

VL - 39

SP - 167

EP - 185

JO - Computer Vision, Graphics, and Image Processing

JF - Computer Vision, Graphics, and Image Processing

SN - 0734-189X

IS - 2

ER -