US 7,808,500 B2Granted

Method for improving spatial index efficiency by jittering splitting planes

AssigneeInternational Business Machines Corporation

InventorRobert Allen Shearer

Life of this patent

Estimating the term…

Loading patent…

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.

Claims12

Dependent claims

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.

10 more elements

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.

14 more elements

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.

17 more elements

Dependencies are inferred from the claim text.