Granted Patent B2

US 8,248,416 · App. 12/420,894 · Granted Aug 21, 2012

Assignee: Mental Images GmbH

Abstract

Claims (75)

1. A method executable in a digital processor operable to simulate light transport in a scene by ray tracing, wherein the digital processor is operable to maintain an object list representing a list of objects associated with a boundary of the scene, the method comprising:

executing a ray tracing method that traces r rays through n objects using a memory footprint of only on the order of (n+r) by (1) partitioning the list of objects associated with a boundary of the scene in a recursive manner to generate partitions and (2) culling away the partitions of objects from rays, without using an explicitly stored auxiliary acceleration data structure, and wherein

(a) permutations of rays and objects are storable as index arrays,

(b) a ray permutation is utilized, following the recursive partitioning and culling of partitions of objects, to enumerate ray-object intersections by spatial proximity in a manner adapted for Markov chain simulation, which can comprise executing shading and scattering computations or employing a path tracing technique, and

(c) an order of recursion is determinable by a majority of ray directions of rays associated with the scene.

2. The method of claim 1 further comprising:

accelerating object list partitioning or ray classification by utilizing a construct representing a plurality of objects associated with a boundary of the scene instead of treating objects separately, or by tracing a plurality of rays instead of one.

3. The method of claim I wherein a spatial hierarchy is implicitly determined by recursion, and wherein the spatial hierarchy determined by recursion is explicitly stored for reuse.

4. The method of claim 1 further comprising:

generating geometry or rays on demand based on identification information.

5. The method of claim 1 further comprising:

streaming massive geometry in chunks, and

wherein chunks are processed utilizing any of the recursion and culling of claim 1 .

6. The method of claim 1 further comprising:

partitioning object space or partitioning a ray space to efficiently stream massive geometry.

7. The method of claim 1 further comprising:

checking n objects for intersection by (1) partitioning the object list in a recursive manner to generate partitions and (2) culling away the partitions of objects from other objects, without employing an explicitly stored auxiliary acceleration data structure.

8. The method of claim 7 further comprising:

partitioning object space or partitioning a ray space.

9. The method of claim 2 wherein the accelerating further comprises utilizing a scene graph.

10. The method of claim 2 wherein the accelerating further comprises executing a computation by bucket sorting objects, associated with a boundary of the scene, in object space or rays in ray space.

11. The method of claim 2 wherein the accelerating further comprises recursively clustering m subsequent objects.

12. The method of claim 1 further comprising:

executing a collision detection technique comprising checking n objects for intersection,

wherein the checking of n objects for intersection comprises employing a spatial partition technique that recursively partitions space, without using an explicitly stored auxiliary acceleration data structure.

13. A computer program product operable in a digital computer processor operable to simulate light transport in a scene by ray tracing, wherein the digital processor is operable to maintain an object list representing a list of objects associated with a boundary of the scene, the computer program product comprising computer executable program instructions stored in a non-transitory computer readable medium, the computer executable program instructions stored in the non-transitory computer readable medium comprising:

computer program instructions that when executed by the digital processor cause the digital processor to execute a ray tracing method that traces r rays through n objects using a memory footprint of only on the order of (n+r) by (1) partitioning the list of objects associated with a boundary of the scene in a recursive manner to generate partitions and (2) culling away the partitions of objects from rays, without using an explicitly stored auxiliary acceleration data structure, and wherein

(a) permutations of rays and objects are storable as index arrays,

(b) a ray permutation is utilized, following the recursive partitioning and culling of partitions of objects, to enumerate ray-object intersections by spatial proximity in a manner adapted for Markov chain simulation, which can comprise executing shading and scattering computations or employing a path tracing technique, and

(c) an order of recursion is determinable by a majority of ray directions of rays associated with the scene.

14. The computer program product of claim 13 further comprising:

computer program instructions that when executed by the digital processor cause the digital processor to accelerate object list partitioning or ray classification by utilizing a construct representing a plurality of objects associated with a boundary of the scene instead of treating objects separately, or by tracing a plurality of rays instead of one.

15. The computer program product of claim 13 further comprising:

computer program instructions that when executed by the digital processor cause the digital processor to implicitly determine a spatial hierarchy by recursion, and wherein the spatial hierarchy determined by recursion is explicitly stored for reuse.

16. The computer program product of claim 13 further comprising:

computer program instructions that when executed by the digital processor cause the digital processor to generate geometry or rays on demand based on identification information.

17. The computer program product of claim 13 further comprising:

computer program instructions that when executed by the digital processor cause the digital processor to stream massive geometry in chunks, and wherein chunks are processed utilizing any of recursion and culling.

18. The computer program product of claim 13 further comprising:

computer program instructions that when executed by the digital processor cause the digital processor to partition object space or partition a ray space to efficiently stream massive geometry.

19. The computer program product of claim 13 further comprising:

computer program instructions that when executed by the digital processor cause the digital processor to check n objects for intersection by (1) partitioning the object list in a recursive manner to generate partitions and (2) culling away the partitions of objects from other objects, without employing an explicitly stored auxiliary acceleration data structure.

20. The computer program product of claim 19 further comprising:

computer program instructions that when executed by the digital processor cause the digital processor to partition object space or partition ray space.

21. The computer program product of claim 14 wherein the computer program instructions that when executed by the digital processor cause the digital processor to accelerate object list partitioning or ray classification further comprise computer program instructions that when executed by the digital processor cause the digital processor to utilize a scene graph.

22. The computer program product of claim 14 wherein the computer program instructions that when executed by the digital processor cause the digital processor to accelerate object list partitioning or ray classification further comprise computer program instructions that when executed by the digital processor cause the digital processor to execute a computation by bucket sorting objects, associated with a boundary of the scene, in object space or rays in ray space.

23. The computer program product of claim 14 wherein the computer program instructions that when executed by the digital processor cause the digital processor to accelerate object list partitioning or ray classification further comprise computer program instructions that when executed by the digital processor cause the digital processor to recursively cluster m subsequent objects.

24. The computer program product of claim 13 further comprising:

computer program instructions that when executed by the digital processor cause the digital processor to execute a collision detection technique comprising checking n objects for intersection,

wherein the checking of n objects for intersection comprises employing a spatial partition technique that recursively partitions space, without using an explicitly stored auxiliary acceleration data structure.

25. A subsystem operable in a digital processor operable to simulate light transport in a scene by ray tracing, wherein the digital processor is operable to maintain an object list representing a list of objects associated with a boundary of the scene, the subsystem comprising:

a module operable to execute a ray tracing method that traces r rays through n objects using a memory footprint of only on the order of (n+r) by (1) partitioning the list of objects associated with a boundary of the scene in a recursive manner to generate partitions and (2) culling away the partitions of objects from rays, without using an explicitly stored auxiliary acceleration data structure, wherein

(a) permutations of rays and objects are storable as index arrays,

(b) a ray permutation is utilized, following the recursive partitioning and culling of partitions of objects, to enumerate ray-object intersections by spatial proximity in a manner adapted for Markov chain simulation, which can comprise executing shading and scattering computations or employing a path tracing technique, and

(c) an order of recursion is determinable by a majority of ray directions of rays associated with the scene.

26. The subsystem of claim 25 further comprising:

a module operable to accelerate object list partitioning or ray classification by utilizing a construct representing a plurality of objects associated with a boundary of the scene instead of treating objects separately, or by tracing a plurality of rays instead of one.

27. The subsystem of claim 25 wherein a spatial hierarchy is implicitly determined by recursion, and wherein the spatial hierarchy determined by recursion is explicitly stored for reuse.

28. The subsystem of claim 25 further comprising:

a module operable to generate geometry or rays on demand based on identification information.

29. The subsystem of claim 25 further comprising:

a module operable to stream massive geometry in chunks, and

wherein chunks are processed utilizing any of recursion or culling.

30. The subsystem of claim 25 further comprising:

a module operable to partition object space or ray space to efficiently stream massive geometry.

31. The subsystem of claim 25 further comprising:

a module operable to check n objects for intersection by (1) partitioning the object list in a recursive manner to generate partitions and (2) culling away the partitions of objects from other objects, without employing an explicitly stored auxiliary acceleration data structure.

32. The subsystem of claim 31 further comprising:

a module operable to partition object space or ray space.

33. The subsystem of claim 26 wherein the module operable to accelerate further comprises a module operable to utilize a scene graph.

34. The subsystem of claim 26 wherein the module operable to accelerate further comprises a module operable to execute a computation by bucket sorting objects, associated with a boundary of the scene, in object space or rays in ray space.

35. The subsystem of claim 26 wherein the module operable to accelerate further comprises a module operable to recursively cluster m subsequent objects.

36. The subsystem of claim 25 further comprising:

a module operable to execute a collision detection technique comprising checking n objects for intersection,

wherein the checking of n objects for intersection comprises employing a spatial partition technique that recursively partitions space, without using an explicitly stored auxiliary acceleration data structure.

Assignments (1)

Continuity (10)