Volume Representation: Linear Octtrees From Three-Dimensional Arrays
Tianwen Zhang, Zhongrong Li · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1990
Many of the programming techniques used in solving two-dimensional problems can be extended to three-dimensions. Here a method is proposed for converting the three-dimensional array representation of an object into its linear octtree description. The method contains two algorithms: (1) conversion of three-dimensional array into set of 0-octants and (2) translation--merging of 0-octants encoded an object. For the three--dimensional array A = { a(i, j, k) I 0<i,j,k<2n-1} ,algorithm(1) requires 0(2 3n) time and algorithm (2) can be executed in linear time with respect to the total number of 0-octants.