Method and apparatus for performing ray-node intersection test

Patent metadata

Field	Value
Publication number	US-9830733-B2
Application number	US-201514690708-A
Country	US
Kind code	B2
Filing date	Apr 20, 2015
Priority date	Sep 18, 2014
Publication date	Nov 28, 2017
Grant date	Nov 28, 2017

Abstract

A method and apparatus to perform a ray-node intersection test are provided. The method includes receiving an input representing coordinates of a bounding box and an origin coordinate of a ray as fixed-point numbers, obtaining difference values between the input coordinates of the bounding box and the origin coordinate, and obtaining multiplication values between the obtained difference values and a reciprocal number of a direction vector of the ray, where the reciprocal number is a floating-point number.

First claim

What is claimed:

1. A method of performing a ray-node intersection test, the method comprising:
generating a ray in a rendering scene;
tracing a path of the ray in an acceleration structure comprising nodes; and
performing the ray-node intersection test to locate a node that intersects the ray,
wherein the ray-node intersection test comprises:
receiving an input comprising fixed-point numbers representing coordinates of a bounding box and an origin coordinate of the ray;
obtaining difference values between the input coordinates of the bounding box and the input origin coordinate; and
obtaining multiplication values between the obtained difference values and a reciprocal number of a direction vector of the ray,

wherein the reciprocal number is a floating-point number, and
wherein the obtaining of the multiplication values comprises:
obtaining an added value by adding a predetermined value to a mantissa of the reciprocal number;
determining a sign of the added value; and obtaining multiplication values between the added value to which the determined sign is applied and the differences values.

2. The method of claim 1 , wherein the receiving of the input comprises receiving an input comprising a fixed-point number representing a maximum value among the coordinates of the bounding box,
wherein the obtaining of the difference values comprises obtaining a difference value between the maximum value and the origin coordinate, and
wherein the obtaining of the multiplication values comprises obtaining a multiplication value between the obtained difference value between the maximum value and the origin coordinate and the reciprocal number of a direction vector of the ray.

3. The method of claim 1 , wherein the receiving of the input comprises receiving input comprising a fixed-point number representing a minimum value among the coordinates of the bounding box,
wherein the obtaining of the difference values comprises obtaining a difference value between the minimum value and the input origin coordinate, and
wherein the obtaining of the multiplication values comprises obtaining a multiplication value between the obtained difference value between the minimum value and the origin coordinate and the reciprocal number of a direction vector of the ray.

4. The method of claim 1 , further comprising shifting the multiplication values by a predetermined number of positions.

5. The method of claim 4 , wherein the shifting is performed by using an exponent of the reciprocal number, exponents of the difference values, exponents of the multiplication values, and a bit number of the mantissa of the reciprocal number.

6. The method of claim 4 , wherein the shifted multiplication values are fixed-point numbers.

7. The method of claim 1 , wherein the predetermined value is set by using a bit number of the mantissa of the reciprocal number that is a floating-point number.

8. The method of claim 1 , wherein the obtaining of the multiplication values comprises determining the sign by using a sign bit of the reciprocal number.

9. An apparatus for performing a ray-node intersection test, the apparatus comprising:
a ray generator configured to generate a ray in a rendering scene; and
an acceleration structure traverser configured to trace a path of the ray in an acceleration structure comprising nodes, and to perform the ray-node intersection test to locate a node that intersects the ray,
wherein the acceleration structure traverser further comprises
an input unit configured to receive an input comprising fixed-point numbers representing coordinates of a bounding box and an origin coordinate of the ray;
a difference value obtaining unit configured to obtain difference values between the input coordinates of the bounding box and the input origin coordinate; and
a multiplication value obtaining unit configured to obtain multiplication values between the obtained difference values and a reciprocal number of a direction vector of the ray,

wherein the reciprocal number is a floating-point number, and
wherein the obtaining of the multiplication values comprises:
obtaining an added value by adding a predetermined value to a mantissa of the reciprocal number;
determining a sign of the added value; and obtaining multiplication values between the added value to which the determined sign is applied and the differences values.

10. The apparatus of claim 9 , wherein the input unit receives an input comprising a fixed-point number representing a maximum value among the coordinates of the bounding box,
wherein the difference value obtaining unit obtains a difference value between the maximum value and the input origin coordinate, and
wherein the multiplication value obtaining unit obtains a multiplication value between the obtained difference value between the maximum value and the origin coordinate and the reciprocal number of a direction vector of the ray.

11. The apparatus of claim 9 , wherein the input unit receives an input comprising a fixed-point number representing a minimum value among the coordinates of the bounding box,
wherein the difference value obtaining unit obtains a difference value between the minimum value and the input origin coordinate, and
wherein the multiplication value obtaining unit obtains a multiplication value between the obtained difference value between the minimum value and the origin coordinate and the reciprocal number of a direction vector of the ray.

12. The apparatus of claim 9 , further comprising a shifting unit that shifts the multiplication values by a predetermined number of positions.

13. The apparatus of claim 12 , wherein the shifting unit performs shifting by using an exponent of the reciprocal number, exponents of the difference values, exponents of the multiplication values, and a bit number of the mantissa of the reciprocal number.

14. The apparatus of claim 12 , wherein the shifted multiplication values are fixed-point numbers.

15. The apparatus of claim 9 , wherein the predetermined value is set by using a bit number of the mantissa of the reciprocal number that is a floating-point number.

16. The apparatus of claim 9 , wherein the multiplication value obtaining unit determines the sign by using a sign bit of the reciprocal number.

17. A non-transitory computer readable medium comprising instructions that, when executed by a computer, cause a processor to perform a method of a ray-node intersection test, the method comprising:
generating a ray in a rendering scene;
tracing a path of the ray in an acceleration structure comprising nodes; and
performing the ray-node intersection test to locate a node that intersects the ray,
wherein the ray-node intersection test comprises
receiving an input comprising coordinates of a bounding box and an origin coordinate of the ray;
obtaining difference values between the input coordinates of a bounding box and the input origin coordinate of the ray, wherein the coordinates are fixed-point numbers, and
obtaining multiplication values between the obtained difference values and a reciprocal number of a direction vector of the ray,

wherein the reciprocal number is a floating-point number,
wherein the obtaining of the multiplication values comprises:
obtaining an added value by adding a predetermined value to a mantissa of the reciprocal number;
determining a sign of the added value; and
obtaining multiplication values between the added value to which the determined sign is applied and the difference values.

Assignees

• Samsung Electronics Co Ltd

Inventors

• Hwang Seokjoong
• Shin Youngsam
• Lee Wonjong
• Lee Jaedon

Classifications

• G06T15/06 Primary

  Ray-tracing · CPC title