Ray tracing method and apparatus

Patent metadata

Field	Value
Publication number	US-9996966-B2
Application number	US-201414276280-A
Country	US
Kind code	B2
Filing date	May 13, 2014
Priority date	Nov 4, 2013
Publication date	Jun 12, 2018
Grant date	Jun 12, 2018

Abstract

A ray tracing method includes determining whether acceleration structure traversal data of a previous ray similar to a received ray is stored in a traversal cache, and reading the stored acceleration structure traversal data, and performing image rendering based on the read acceleration structure traversal data, based on a result of the determining.

First claim

What is claimed is:

1. A ray tracing method comprising:
extracting feature information of a received ray comprising an origin and a direction of the received ray;
determining a key of the received ray among a plurality of keys for a current frame based on the extracted feature information, wherein each of the plurality of keys is associated with at least one ray for the current frame, respectively;
determining whether acceleration structure traversal data of a previous ray of a previous frame, that is similar to the received ray of the current frame, is stored in a traversal cache based on the key; and
reading the stored acceleration structure traversal data, and performing image rendering based on the read acceleration structure traversal data, based on a result of the determining involving the acceleration structure traversal data, which comprises determining whether a cache hit or a cache miss occurs based on whether tag data indicating an origin and a direction of the received ray matches tag data indicating an origin and a direction of the previous ray.

2. The ray tracing method of claim 1 , wherein the plurality of keys are keys of a hash table database, and the ray tracing method further comprising:
determining that the previous ray is similar to the received ray based on the key.

3. The ray tracing method of claim 1 , wherein the determining of the key comprises:
determining a group to which the received ray belongs by searching, based on the extracted feature information, a database in which information of groups set based on feature information of rays, and keys of the groups, are stored, and
determining a key of the determined group as the key of the received ray.

4. The ray tracing method of claim 3 , wherein:
the information of the groups comprises an origin and a direction of each of the rays; and
the determining of the key comprises determining the group to which the received ray belongs by comparing the origin and the direction of the received ray with the origin and the direction of each of the rays.

5. The ray tracing method of claim 1 , wherein:
the determining of whether the acceleration structure traversal data is stored comprises comparing the key of the received ray with the tag data stored in the traversal cache and indicating a key of a ray; and
the reading comprises, in response to the tag data matching the key of the received ray, reading the acceleration structure traversal data corresponding to the matching tag data.

6. The ray tracing method of claim 1 , wherein the acceleration structure traversal data comprises at least one of data of a node cluster where a previous ray intersects, data of a leaf node where the previous ray intersects, and data of a primitive where the previous ray intersects.

7. The ray tracing method of claim 6 , wherein, in response to the acceleration structure traversal data comprising the data of the node cluster, the image rendering comprises detecting a leaf node where the received ray intersects by traversing nodes included in the node cluster.

8. The ray tracing method of claim 6 , wherein, in response to the acceleration structure traversal data comprising the data of the leaf node, the rendering comprises testing whether the received ray intersects the leaf node.

9. The ray tracing method of claim 6 , further comprising, in response to the acceleration structure traversal data comprising the data of the primitive, transmitting the data of the primitive to an intersection test unit.

10. The ray tracing method of claim 6 , wherein, in response to the acceleration structure traversal data comprising the data of the primitive, the rendering comprises testing whether the received ray intersects the primitive.

11. A ray tracing apparatus comprising:
one or more processors configured to extract feature information of a received y comprising an origin and a direction of the received ray;
determine a key of the received ray among a plurality of keys for a current frame, based on the extracted feature information, wherein each of the plurality of keys is associated with at least one ray for the current frame, respectively;
determine whether acceleration structure traversal data of a previous ray of a previous frame, that is similar to the received ray of the current frame, is stored in a traversal cache based on the key; and
read the stored acceleration structure traversal data, and perform acceleration structure traversal with the received ray based on the read acceleration structure traversal data, based on a result of the determination involving the acceleration structure traversal data, which comprises determining whether a cache hit or a cache miss occurs based on whether tag data indicating an origin and a direction of the received ray matches tag data indicating an origin and a direction of the previous ray.

12. The ray tracing apparatus of claim 11 , wherein the plurality of keys are keys of a hash table database, and the one or more processors is further configured to:
determine that the previous ray is similar to the received ray based n the key.

13. The ray tracing apparatus of claim 11 , further comprising:
a database in which information of groups set based on feature information of rays, and keys of the groups, are stored; and
wherein the one or more processors is configured to
determine a group to which the received ray belongs by searching the database based on the extracted feature information, and
determine a key of the determined group as the key of the received ray.

14. The ray tracing apparatus of claim 13 , wherein:
the information of the groups comprises an origin and a direction of each of the rays; and
the one or more processors is configured to determine the group to which the received ray belongs by comparing the origin and the direction of the received ray with the origin and the direction of each of the rays.

15. The ray tracing apparatus of claim 11 , wherein:
the one or more processors is configured to
store the tag data indicating a key of a ray, and acceleration structure traversal data corresponding to the tag data,
compare the key of the received ray with the stored tag data; and

the one or more processors is configured to read the acceleration structure traversal data corresponding to the matching tag data in response to the tag data matching the key of the received ray.

16. The ray tracing apparatus of claim 11 , wherein the acceleration structure traversal data comprises at least one of data of a node cluster where the previous ray intersects, data of a leaf node where the previous ray intersects, and data of a primitive where the previous ray intersects.

17. The ray tracing apparatus of claim 16 , wherein, in response to the acceleration structure traversal data comprising the data of the node cluster, the one or more processors is configured to traverse nodes included in the node cluster to detect a leaf node where the received ray intersects.

18. The ray tracing apparatus of claim 16 , wherein, in response to the acceleration structure traversal data comprising the data of the leaf node, the one or more processors is configured to test whether the received ray intersects the leaf node.

19. The ray tracing apparatus of claim 16 , wherein the one or more processors is further configured to test whether the received ray intersects the primitive in response to the acceleration structure traversal data comprising the data of the primitive.

20. The ray tracing method of claim 1 , further comprisin

Assignees

• Samsung Electronics Co Ltd

Inventors

• Lee Won-Jong
• Shin Young-Sam
• Lee Jae-Don

Classifications

• G06T2200/04

  involving 3D image data · CPC title

• G06T15/06 Primary

  Ray-tracing · CPC title