Patent ID: 7289118
Filing Date: 2007-10-30
Classification: G06T

Abstract:
1. Method for determining a two-dimensional representation of a three-dimensional world, whereby the two-dimensional representation is specified at least by a geometric description, a tree structure for spatial division of the three-dimensional world, and the material properties of all the objects of this world, wherein a ray tracing method is used, whereby several rays are brought together into a packet of discrete rays, whereby an association of a data structure with each packet of discrete rays is carried out, whereby a status-related assignment of the data structure to each ray is stored in memory, whereby all of the following are applied to the packet(s) of the several discrete rays, in that in a work step that performs an operation on a packet, this operation is performed on every ray of the packet, if the status-related assignment is stored in the data structure assigned to the packet, that the ray in question participates in this operation, whereby the ray tracing method is broken down into the following work steps, which are worked off one after the other, for the individual packets of rays: A Camera ray generation: A packet of rays is generated, which are supposed to be intersected with the geometry of the three-dimensional world, proceeding from the virtual camera, B Tree traversal: In accordance with the spatial orientation of the rays, the tree data structure for the geometry of the three-dimensional world is run through, until a tree leaf or a placeholder is reached, whereby in this manner, tree nodes and placeholders are read out of a memory, and calculations are carried out, whereby when a placeholder is reached, the corresponding sequence of instructions of the substitute object is carried out, in that the placeholder is replaced with an object that can also be a complex one, whereby if a placeholder is present, two alternatives are available: C Read-in of the tree leaf: All the references of the objects and placeholders that are located in this tree leaf are read in from a memory, and carried out, if applicable, D Intersecting of all objects: All the objects that were specified in work step C are read in, and intersected with the packet of rays, whereby if a transformation was specified for an object, this is applied before the intersection with the object is calculated, whereby if a geometry-changing sequence of instructions was specified for an object, this is carried out before the intersection with the object is calculated, whereby if an object to be intersected is a complex object having its own tree structure, which must be traversed, this object is intersected in that the work steps B-F, adapted to the complex object, are carried out, E Intersection evaluation: It is checked whether valid intersection points exist for the packet of rays, hereby possible ray intersections are determined for elements of the tree for which a ray intersection is possible, but which have not yet been examined, if valid intersection points were not yet determined in a sufficient amount, in that the method starts again at step B, including the previous results, whereby in the case of a sufficient amount of determined ray intersections, the method continues with step F, F Determining the object properties: With evaluation of the results of the preceding work steps, data of objects with which valid intersection points were calculated, if there are any, are read out of the memory, whereby the results of the calculations flow into step G, whereby if the results are appropriate, values in a memory are recalculated, whereby in the case that a material-changing sequence of instructions was specified for one or more of the objects that were intersected by a ray, in such a manner that the material properties of this object are of significance for the work step F or G, this sequence of instructions is carried out ahead of the calculations of the work step F, G Subsequent ray generation: If it was calculated in step F that one or more additional rays are supposed to be intersected with the geometry of the three-dimensional world, then corresponding packets of rays are calculated in this step, and the sequence of the method starts again at work step B for these rays, whereby otherwise, it starts again at step A, if additional camera rays still have to be generated for forming the two-dimensional representation.