Adjacency algorithms for linear octree nodes

摘要

A formula for deriving the rectangular coordinates X, Y and Z from the octal locational code of a linear octree node is introduced. This formula is simpler than those that have previously been proposed1. Algorithms for determining the octal locational code of a face, edge and corner adjacent block to a given linear octree node are proposed. The edge and the corner adjacency algorithms are presented as direction extensions of the eastern, western, front, back, southern and northern neighbour finding procedures. Necessary and sufficient conditions for two octree nodes to be face adjacent in any of the above named directions are formulated in a form of digit tests on their respective locational codes. The face adjacency conditions derived in this paper were later used to select the octal value of the rightmost digit that must be appended or deleted from the locational code of the same size neighbour to identify smaller or larger size neighbours of a selected node in the specified direction. All the adjacency algorithms presented have a computational complexity of O(n), where n is the number of digits that form the locational code of the octree node for which a neighbour is sought.