A new linear octree construction by filling algorithms

A novel linear octree construction based on filling the closed voxel-based border is proposed. The algorithm is based on a sweeping strategy. First it is proved that if an octant contains no border voxel then its attribute can be determined by examining the attributes of all its processed neighbors. Then a data structure called active front is used to keep track of the attributes of the corresponding neighbors as the sweeping process is carried out octant by octant. Compared with the existing algorithm, the main advantage of this approach is that it does not require prior blocking information of the boundary voxels. The time complexity of the algorithm is proportional to the ratio of boundary voxels. It is optimal in the sense that all boundary voxels are traversed only once and all octants of the octree are also examined once