Juyang Weng, Narendra Ahuja

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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. It 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 the maintenance of 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. Upper bounds are derived for the numbers of nodes in an octree representing a cubic block of arbitrary orientation and position. These bounds are proportional to the face area of the cube plus the logarithm of the side length of the universe space.

Original languageEnglish (US)
Title of host publicationUnknown Host Publication Title
Number of pages6
ISBN (Print)0818606339
StatePublished - 1985

ASJC Scopus subject areas

  • Engineering(all)

Cite this