Method for computer-aided identification of the child octants of a parent octant, which are intersected by a beam, in an octree data structure by means of look-up tables

1. A method performed by a processor of a computer for identification of child octants of a parent octant, which are intersected by a beam, in an octree data structure, comprising the steps of:

establishing a number, a, of the child octants of the parent octant which are intersected by the beam; and

identifying, when a=3 and a=4, the child octants which are intersected by the beam using at least one pre-calculated and previously stored look-up table (LUT),

wherein when a=3, a first LUT and when a=4 a further, second LUT is used for identification of the child octants which are intersected by the beam.

2. The method according to claim 1 , wherein a one-dimensional LUT is used as the first LUT, and a two-dimensional LUT is used as the second LUT.

3. The method according to claim 1 , further comprising: establishing an entry octant (Index ID in ) and an exit octant (Index ID out ) of the beam; and, on the basis of this determination, the number, a, is established and the intersected child octants of the parent octant are identified.

4. The method according to claim 3 , wherein:

a) with a=1 the entry octant,

b) with a=2 the entry and the exit octant,

c) with a=3 the entry, the exit octant and precisely one further child octant (Index ID Mid ) of the parent octant,

d) with a=4 the entry, the exit octant and precisely two further child octants (Indices ID Mid1 and ID Mid2 ) of the parent octant,

are identified as child octants of the parent octant which are intersected by the beam.

5. The method according to claim 3 , wherein:

the entry octant is indexed by means of a three-place bitmask ID in ;

the exit octant is indexed by means of a three-place bitmask ID out ; and in that the number a is established via a bitwise XOR cross-linkage of these bitmasks.

6. The method according to claim 5 , wherein:

the coordinates of the entry point of the beam into the entry octant (entry coordinates) and the coordinates of the exit point of the beam from the exit octant (exit coordinates) are calculated,

the bitmask ID in is calculated by means of a size comparison of the entry coordinate with the coordinates of dividing planes of the parent octant (division coordinates) and the bitmask ID out , is calculated by means of a size comparison of the exit coordinates with the coordinates of the dividing planes of the parent octant and

when a=3 or a=4, the LUT is indexed by means of a value calculated from the entry coordinates and/or exit coordinates and/or the index ID in and/or the index ID out , and the division coordinates for identification of the further intersected child octant or octants ID Mid or ID Mid1 and ID Mid2 .

7. The method according to claim 1 , wherein the child octants of the parent octant are indexed by an ordered sequential subdivision of the space according to (x, y, z) coordinates of a left-handed Cartesian coordinate system.

8. The method according to claim 1 , wherein the dividing planes of the parent octant are disposed isotropically or anisotropically.

9. The method according to claim 1 , wherein the method is a component of a method for graphic display of surface views of objects by means of the computer, of a method for indexing three-dimensional spatial regions in information systems, in particular in geographical information systems, of a method for removing concealed surface components (hidden surface removal) in the case of computer-aided display of geographical data, in particular terrain data, of a simulation method for describing the physical behaviour of particle systems, in particular molecule systems, or of solid bodies, of a method for recognising object collisions in computer simulations, in particular in computer games, or of a method for computer-aided sorting of data and/or identification of partial quantities of data within a total quantity of data (sorting and/or search algorithm).

10. A computer system, comprising:

a memory; and

a calculation unit,

wherein the memory unit and the calculation unit are operable for computer-aided identification of child octants of a parent octant, which are intersected by a beam, in an octree data structure, comprising:

establishing a number, a, of the child octants of the parent octant which are intersected by the beam; and

identifying, when a=3 and a=4, the child octants which are intersected by the beam using at least one pre-calculated and previously stored look-up table (LUT),

wherein when a=3, a first LUT and when a=4 a further, second LUT is used for identification of the child octants which are intersected by the beam.

11. The computer system of claim 10 , wherein the memory unit and a calculation unit are operable for graphic display of surface views of objects, for indexing three-dimensional spatial regions in information systems, in particular in geographical information systems, for removing concealed surface components in the computer-aided display of geographical data, in particular terrain data, for simulation of the physical behaviour of particle systems, in particular molecule systems, or of solid bodies, for recognition of object collisions in computer simulations, in particular in computer games or for sorting data and/or identifying partial quantities of data within a total quantity of data.