Patent ID: 6429864
Filing Date: 2002-08-06
Classification: G06T

Abstract:
Method for traversing a space partition, particularly a quadtree- or octree-partition, in the direction of a semi-infinite straight-line,whereby the parameter â€œmaximum depthâ€  defines the depth of the space partition, whereby 2maximum depth is the edge length of the entire partitioned region, whereby the semi-infinite straight-line is given by a starting point as well as a directional vector, whereby the directional vector possesses a main component as well as secondary components, and whereby the amount of every secondary component is less or equal to the amount of the main component, characterized by the following steps: (d) determining the distances of the semi-infinite straight-line's entry point into the terminal cell in the direction of the main component as well as in the directions of the secondary components from the walls of the encompassing terminal cell; (f) decrementing of said collective specified distances in the direction of the main component by 2n and in the direction of a secondary component by 2nÃ—(rise m of the respective secondary component), whereby n is a natural number, whereby 2n assumes in a descending sequence the values â€œedge length of the encompassing terminal cellâ€ , . . . 2, 1, whereby the spacings in the direction of the main component and in the direction of the secondary components are reduced by the successively following decrement only when the whole-numbered components of the resulting decremented distances are collectively non-negative, and whereby the decrements are processed in a descending sequence until the following terminating condition is fulfilled: the decremented spacing in the direction of the main component and/or the whole numbered portion of the decremented spacing in the direction of at least one secondary component is zero; (g) determining, from the decremented distances in the direction of the main component and in the directions of the secondary components present upon the termination, the contiguous unit cell at the exit point of the semi-infinite straight-line from the terminal cell; (h) determining that terminal cell of the space partition which encompasses the unit cell determined in step (g).