Patent ID: 8358303
Filing Date: 2013-01-22
Classification: G06F

Abstract:
1. A method of searching an address value of a neighboring cell that is in contact with a randomly selected octree cell in an octree structure cell, the method comprising steps to be executed by a processor configured to process data, wherein the steps comprise: performing address encoding of octree cells by giving an inherent address value that is increased according to a depth level of octree to each cell in the octree structure such that address difference values of neighboring cells in the octree structure have a sequential rule, wherein an address is given by assigning positive integers of 1 through 8 from an upper left rear corner of an octree cell and repeatedly increasing the number of digits according to the depth level of octree and adding a new digit at the end of an old address, and wherein the sequential rule includes selecting the address difference values of neighboring cells from a predetermined set of numbers, the size of the predetermined set being based on the depth level of the neighboring cells; and searching an address value of a neighboring cell that is in contact by a surface with the selected octree cell by using the sequential rule based on the address difference values, wherein, in the searching of the address value of a neighboring cell, a searching of address values of neighboring cells that are in contact by surfaces of 6 directions of an octree coordinate system is performed by steps that comprise: normalizing a difference value with respect to each axis of the octree coordinate system between address values of the selected octree cell and a cell that is opposite, with respect to a selected axis of the octree coordinate system, to the selected octree cell as a coordinate value of the selected octree cell from a center of the octree coordinate system, wherein an address value of the cell that is opposite to the selected octree cell, with respect to the selected axis, is determined by finding a corresponding digit for each digit of the address value of the selected octree cell based on a lookup table, and wherein the normalizing comprises (a) determining a further difference value between the difference value with respect to each axis and a maximum address difference value between the selected cell and its neighboring cells, (b) acquiring in binary representation a normalized address coordinate with respect to the selected axis by dividing the further difference value by a base number that is associated with the selected axis, and (c) acquiring a decimal coordinate of the selected cell with respect to the selected axis by converting the binary representation of the normalized address coordinate with respect to the selected axis from a binary representation to a decimal representation; determining an identity value based on the decimal coordinate of the selected cell with respect to the selected axis; and determining address values of neighboring cells of the selected cell with respect to the selected axis based on the identity value.