System and method for adaptive span computation during ray casting

• US 20070057968A1
• Filed: 09/15/2005
• Published: 03/15/2007
• Est. Priority Date: 09/15/2005
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Fossum, Gordon, Minor, Barry
• Granted Patent: US 7,362,330 B2
• Time in Patent Office: Days
• US Class Current: 345/623
• CPC Class Codes: G06T 15/20 Perspective computation

Abstract

A system and method for adaptive span computation when ray casting is presented. A processor uses start point fractional values during view screen segment computations that start a view screen segment'"'"'s computations a particular distance away from a down point. This prevents an excessive sampling density during image generation without wasting processor resources. The processor identifies a start point fractional value for each view screen segment based upon each view screen segment'"'"'s identifier, and computes a view screen segment start point for each view screen segment using the start point fractional value. View screen segment start points are “tiered” and are a particular distance away from the down point. This stops the view screen segments from converging to a point of severe over sampling while, at the same time, providing a pseudo-uniform sampling density.

Claims

1. A computer-implemented method comprising:

identifying a down point location;

determining one or more start point fractional values based upon the down point location;

selecting one of the start point fractional values for a view screen segment;

computing a view screen segment start point using the selected start point fractional value;

generating image values corresponding to the view screen segment starting at the view screen segment start point; and

displaying the image values on a view screen.

2. The method of claim 1 wherein the computing further comprises:

identifying the distance between the down point location and a view screen edge that corresponds to the view screen segment;

multiplying the selected start point fractional value with the identified distance, resulting in a start point fractional distance; and

adding the start point fractional distance to the down point location, resulting in the view screen segment start point.

3. The method of claim 1 wherein the selecting further comprises:

identifying a view screen segment identifier that corresponds to the view screen segment;

determining a last bit value of the view screen segment identifier;

selecting a fifty percent start point fractional value in response to determining that the last bit value is one;

in response to determining that the last bit value is zero, determining a second to last bit value of the view screen segment identifier;

selecting a twenty five percent start point fractional value in response to determining that the second to last bit value is one;

in response to determining that the second to last bit value is zero, determining a third to last bit value of the view screen segment identifier; and

selecting a twelve and one-half percent start point fractional value in response to determining that the third to last bit value is one.

4. The method of claim 1 wherein the determining further comprises:

identifying the start point fractional values that are located within the view screen.

5. The method of claim 1 further comprising:

selecting a view screen intersection point based upon the view screen segment start point;

calculating a height map intersection point based upon the selected view screen intersection point;

retrieving height map data corresponding to the calculated height map intersection point; and

wherein the generating includes the retrieved height map data.

6. The method of claim 1 further comprising:

identifying a pixel resolution corresponding to a plurality of pixels included in the view screen;

determining a view screen segment density for a plurality of view screen segments based upon the pixel resolution, the view screen segment included in the plurality of view screen segments; and

wherein the view screen segment density ensures that one or more of the plurality of view screen segments corresponds to generating image values for each of the plurality of pixels.

7. The method of claim 1 further comprising:

wherein the method is performed using a broadband processor architecture, the broadband processor architecture including a plurality of heterogeneous processors, a common memory, and a common bus; and

wherein the plurality of heterogeneous processors use different instruction sets and share the common memory and the common bus.

8. A computer program product comprising:

a computer operable medium having computer readable code, the computer readable code being effective to;

identify a down point location;

determine one or more start point fractional values based upon the down point location;

select one of the start point fractional values for a view screen segment;

compute a view screen segment start point using the selected start point fractional value;

generate image values corresponding to the view screen segment starting at the view screen segment start point; and

display the image values on a view screen.

9. The computer program product of claim 8 wherein the computer readable code is further effective to:

identify the distance between the down point location and a view screen edge that corresponds to the view screen segment;

multiply the selected start point fractional value with the identified distance, resulting in a start point fractional distance; and

add the start point fractional distance to the down point location, resulting in the view screen segment start point.

10. The computer program product of claim 8 wherein the computer readable code is further effective to:

identify a view screen segment identifier that corresponds to the view screen segment;

determine a last bit value of the view screen segment identifier;

select a fifty percent start point fractional value in response to determining that the last bit value is one;

in response to determining that the last bit value is zero, determine a second to last bit value of the view screen segment identifier;

select a twenty five percent start point fractional value in response to determining that the second to last bit value is one;

in response to determining that the second to last bit value is zero, determine a third to last bit value of the view screen segment identifier; and

select a twelve and one-half percent start point fractional value in response to determining that the third to last bit value is one.

11. The computer program product of claim 8 wherein the computer readable code is further effective to:

identify the start point fractional values that are located within the view screen.

12. The computer program product of claim 8 wherein the computer readable code is further effective to:

select a view screen intersection point based upon the view screen segment start point;

calculate a height map intersection point based upon the selected view screen intersection point;

retrieve height map data corresponding to the calculated height map intersection point; and

wherein the generating includes the retrieved height map data.

13. The computer program product of claim 8 wherein the computer readable code is further effective to:

identify a pixel resolution corresponding to a plurality of pixels included in the view screen;

determine a view screen segment density for a plurality of view screen segments based upon the pixel resolution, the view screen segment included in the plurality of view screen segments; and

wherein the view screen segment density ensures that one or more of the plurality of view screen segments corresponds to generating image values for each of the plurality of pixels.

14. The computer program product of claim 8 wherein the computer program product is performed using a broadband processor architecture, the broadband processor architecture including a plurality of heterogeneous processors, a common memory, and a common bus;

and

wherein the plurality of heterogeneous processors use different instruction sets and share the common memory and the common bus.

15. An information handling system comprising:

one or more processors;

a memory accessible by the processors;

one or more nonvolatile storage devices accessible by the processors; and

a view screen segment start point computation tool for computing view screen segment start points, the view screen segment start point computation tool being effective to;

identify a down point location;

determine one or more start point fractional values based upon the down point location;

select one of the start point fractional values for a view screen segment;

compute a view screen segment start point using the selected start point fractional value;

generate image values corresponding to the view screen segment starting at the view screen segment start point; and

display the image values on a view screen.

16. The information handling system of claim 15 wherein the view screen segment start point computation tool is further effective to:

identify the distance between the down point location and a view screen edge that corresponds to the view screen segment;

multiply the selected start point fractional value with the identified distance, resulting in a start point fractional distance; and

add the start point fractional distance to the down point location, resulting in the view screen segment start point.

17. The information handling system of claim 15 wherein the view screen segment start point computation tool is further effective to:

identify a view screen segment identifier that corresponds to the view screen segment;

determine a last bit value of the view screen segment identifier;

select a fifty percent start point fractional value in response to determining that the last bit value is one;

in response to determining that the last bit value is zero, determine a second to last bit value of the view screen segment identifier;

select a twenty five percent start point fractional value in response to determining that the second to last bit value is one;

in response to determining that the second to last bit value is zero, determine a third to last bit value of the view screen segment identifier; and

select a twelve and one-half percent start point fractional value in response to determining that the third to last bit value is one.

18. The information handling system of claim 15 wherein the view screen segment start point computation tool is further effective to:

identify the start point fractional values that are located within the view screen.

19. The information handling system of claim 15 wherein the view screen segment start point computation tool is further effective to:

identify a pixel resolution corresponding to a plurality of pixels included in the view screen;

determine a view screen segment density for a plurality of view screen segments based upon the pixel resolution, the view screen segment included in the plurality of view screen segments; and

wherein the view screen segment density ensures that one or more of the plurality of view screen segments corresponds to generating image values for each of the plurality of pixels.

20. The information handling system of claim 15 wherein the information handling system is a broadband processor architecture that includes a plurality of heterogeneous processors that share the memory, the plurality of heterogeneous processors using different instruction sets.