Method for improving spatial index efficiency by jittering splitting planes

• US 7,808,500 B2
• Filed: 11/21/2006
• Issued: 10/05/2010
• Est. Priority Date: 11/21/2006
• Status: Active Grant

• Current Assignee: Activision Publishing Incorporated (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Shearer, Robert Allen
• Primary Examiner(s): Chauhan, Ulka
• Assistant Examiner(s): PRENDERGAST, ROBERTA D
• Application Number:
  US11/562,166
• Publication Number:
  US 20080117206A1
• Time in Patent Office: 1,414 Days
• Field of Search: 345/419, 345/420, 345/421, 345/426, 345/544, 345/555
• US Class Current: 345/420
• CPC Class Codes: G06T 15/06 Ray-tracing
• CPC Class Codes: G06T 15/40 Hidden part removal

Abstract

Embodiments of the invention provide methods and apparatus to improve the efficiency of a ray tracing image processing system. According to one embodiment of the invention, when building a spatial index the position of a splitting plane used to create a bounding volume may be jittered or moved along an axis to determine if a more efficient location for the splitting plane exists. After jittering the splitting plane a number of primitives intersected by the splitting plane may be calculated. The number of primitives intersected by the splitting plane for each location may be compared, and the location with the fewest intersected primitives may be chosen for the final position of the splitting plane. By choosing the location with the fewest intersected primitives the number of ray-primitive intersection tests necessary when performing ray tracing may be reduced. Consequently, the efficiency of the image processing system may be improved.

Claims

1. A method, comprising:

creating a spatial index having nodes representing bounding volumes in a three dimensional scene, comprising;

a) drawing an initial splitting plane within a bounding volume at a first point along a reference axis;

b) determining a number of primitives intersected by the initial splitting plane; and

c) jittering the splitting plane along the reference axis and by operation of one or more computer processors to determine a location for the splitting plane where fewer primitives are intersected;

wherein jittering the splitting plane comprises;

selecting a second point a first distance from the first point along the reference axis, wherein the second point is oriented in a first direction along the reference axis with respect to the first point, and wherein selecting the second point comprises;

determining if a group of vertices are close to the first point in the first direction; and

if so, selecting the second point to be a distance from the first point beyond the group of vertices in the first direction;

drawing a second splitting plane within the bounding volume at the second point; and

determining a number of primitives intersected by the second splitting plane.

2. The method of claim 1, wherein drawing an initial splitting plane within the bounding volume at a first point along the reference axis comprises:

projecting vertices of primitives within the bounding volume onto the reference axis; and

determining the first point to be within the middle of the projected vertices.

3. The method of claim 1, wherein creating the spatial index further comprises:

selecting a third point a second distance from the first point along the reference axis, and wherein the third point is oriented in a second direction along the reference axis with respect to the first point;

drawing a third splitting plane within the bounding volume at the third point;

determining a number of primitives intersected by the third splitting plane; and

selecting the splitting plane which intersects the fewest number of primitives.

4. The method of claim 3, wherein the first direction is a positive direction along the reference axis and the second direction is a negative direction along the reference axis.

5. The method of claim 3, wherein the first distance and the second distance are the same distance.

6. A method, comprising:

creating a spatial index having nodes representing bounding volumes in a three dimensional scene, comprising;

a) drawing an initial splitting plane within a bounding volume at a first point along a reference axis;

b) determining a number of primitives intersected by the initial splitting plane;

c) jittering the splitting plane along the reference axis and by operation of one or more computer processors to determine a location for the splitting plane where fewer primitives are intersected;

wherein jittering the splitting plane comprises;

selecting a second point a first distance from the first point along the reference axis, wherein the second point is oriented in a first direction along the reference axis with respect to the first point, and wherein selecting the second point comprises;

(i) determining if a group of vertices are close to the first point in the first direction; and

(ii) if so, selecting the second point to be a distance from the first point beyond the group of vertices in the first direction;

drawing a second splitting plane within the bounding volume at the second point; and

determining a number of primitives intersected by the second splitting plane;

d) selecting a third point a second distance from the first point along the reference axis, wherein the third point is oriented in a second direction along the reference axis with respect to the first point and wherein the first distance and the second distance are the same distance;

e) drawing a third splitting plane within the bounding volume at the third point;

f) determining a number of primitives intersected by the third splitting plane; and

g) selecting the splitting plane which intersects the fewest number of primitives.

7. The method of claim 6, wherein drawing an initial splitting plane within the bounding volume at a first point along the reference axis comprises:

projecting vertices of primitives within the bounding volume onto the reference axis; and

determining the first point to be within the middle of the projected vertices.

8. The method of claim 6, wherein the first direction is a positive direction along the reference axis and the second direction is a negative direction along the reference axis.

9. A method, comprising:

creating a spatial index having nodes representing bounding volumes in a three dimensional scene, comprising;

a) drawing an initial splitting plane within a bounding volume at a first point along a reference axis;

b) determining a number of primitives intersected by the initial splitting plane;

c) jittering the splitting plane along the reference axis and by operation of one or more computer processors to determine a location for the splitting plane where fewer primitives are intersected;

wherein jittering the splitting plane comprises;

selecting a second point a first distance from the first point along the reference axis, wherein the second point is oriented in a first direction along the reference axis with respect to the first point, and wherein selecting the second point comprises;

(i) determining if a first group of vertices are close to the first point in the first direction; and

(ii) if so, selecting the second point to be a distance from the first point beyond the first group of vertices in the first direction;

drawing a second splitting plane within the bounding volume at the second point; and

determining a number of primitives intersected by the second splitting plane;

d) selecting a third point a second distance from the first point along the reference axis, wherein the third point is oriented in a second direction along the reference axis with respect to the first point and wherein selecting the third point comprises;

determining if a second group of vertices are close to the first point in the second direction; and

if so, selecting the third point to be a distance from the first point beyond the second group of vertices in the second direction;

e) drawing a third splitting plane within the bounding volume at the third point;

f) determining a number of primitives intersected by the third splitting plane; and

g) selecting the splitting plane which intersects the fewest number of primitives.

10. The method of claim 9, wherein drawing an initial splitting plane within the bounding volume at a first point along the reference axis comprises:

projecting vertices of primitives within the bounding volume onto the reference axis; and

determining the first point to be relatively within the middle of the projected vertices.

11. The method of claim 9, wherein the first direction is a positive direction along the reference axis and the second direction is a negative direction along the reference axis.

12. The method of claim 9, wherein the first distance and the second distance are the same distance.