Systems and methods for three dimensional computation and visualization using a parallel processing architecture

Abstract

Systems and methods are provided for system for generating a physical model for engineering design or visualization. A system includes a processor-readable memory that further includes one or more data structures containing physical data associated with points in a three dimensional volume. A system also includes a plurality of data processors that operate in parallel to perform calculations using the physical data to generate a physical model for providing real-time visualization and calculation associated with the three dimensional volume.

It is claimed: 
     
       1. A system for generating a physical model for engineering design or visualization, comprising:
 a processor-readable memory, wherein the processor-readable memory includes:
 one or more data structures containing physical data associated with points in a three dimensional volume, the one of more data structures including:
 a density data structure for storing density data corresponding to the points for identifying whether each of the points is within or outside the three dimensional volume,
 wherein the density data takes a plurality of discretized values with a pre-determined maximum value and a pre-determined minimum value, 
 wherein the pre-determined maximum value is larger than the pre-determined minimum value, 
 the plurality of discretized values between the pre-determined maximum value and the pre-determined minimum value, 
 wherein when the point is within the three dimensional volume, the value of the density data corresponding to the point is equal to the pre-determined maximum value, 
 wherein when the point is outside the three dimensional volume, the value of the density data corresponding to the point is equal to the pre-determined minimum value, 
 wherein when the point is on the boundary of the three dimensional volume, the value of the density data corresponding to the point is equal to one of the plurality of pre-determined discretized values between the pre-determined maximum value and the pre-determined minimum value; and 
 
 a results data structure for storing results data, wherein the results data identifies physical values at the points in the three dimensional volume, wherein the results data is distinct from the density data; and 
 
 
 a plurality of data processors that operate in parallel to perform calculations using the physical data to generate a physical model for providing real-time visualization and calculation associated with the three dimensional volume, wherein providing the visualization includes:
 for a particular pixel, identifying a first point in the three dimensional volume along a ray originating from a vantage point having a corresponding density data structure density that meets a visualization criterion; and 
 determining a pixel value for the particular pixel based on a results data structure value that corresponds with the first identified point in the three dimensional volume. 
 
 
     
     
       2. The system of  claim 1 , where in the results data is indicative of temperature, pressure, force, or velocity at points of the three dimensional volume. 
     
     
       3. The system of  claim 1 , wherein the visualization of the physical model includes a two dimensional visualization of the points in the three dimensional volume or a calculated value based on the densities and the physical values. 
     
     
       4. The system of  claim 1 , wherein the system is configured to generate a two dimensional visualization of the three dimensional volume for display on a display device. 
     
     
       5. The system of  claim 4 , wherein the two dimensional visualization is updated in real-time based on user input. 
     
     
       6. The system of  claim 5 , wherein the two dimensional visualization is updated within 30 milliseconds of receipt of the user input. 
     
     
       7. The system of  claim 6 , wherein the user input is a mouse input, a keyboard input, a touch screen input, or a stylus input. 
     
     
       8. The system of  claim 1 , wherein the density data includes a density value in a range of 0 and a display density threshold for each point of the three dimensional volume, wherein the visualization criterion includes the display density threshold, and wherein the visualization criterion commands visualization of the first identified point along the ray having a density value greater than or equal to the display density threshold. 
     
     
       9. The system of  claim 8 , wherein the data processors are configured to regenerate the two dimensional visualization based on a received change to the vantage point. 
     
     
       10. The system of  claim 1 , wherein determining the pixel value for the particular pixel further includes:
 identifying points in the three dimensional volume along a line between the first identified point and a light source; 
 determining whether any points along the line have a corresponding density data value that meets a shading threshold; and 
 determining the pixel value for the particular pixel based on whether any points along the line have a density data value that meets the shading threshold. 
 
     
     
       11. The system of  claim 10 , wherein when one or more points along the line have a density data value that meets the shading threshold, the pixel value is determined to be a darker pixel value based on the first identified point being shaded from the light source. 
     
     
       12. The system of  claim 1 , wherein in a second visualization, the visualization criterion commands visualization of a first identified point along the ray that intersects a geometric boundary within the three dimensional volume;
 where in the pixel value for the particular pixel is determined based on whether the first identified point along the ray that intersects the geometric boundary has a density data value that meets a display density threshold. 
 
     
     
       13. The system of  claim 12 , wherein the geometric boundary is a plane that intersects the three dimensional volume. 
     
     
       14. The system of  claim 12 , wherein the geometric boundary is a sphere that is at least partially within the three dimensional volume. 
     
     
       15. The system of  claim 12 , wherein the visualization criterion commands visualization of a first identified point along the ray that intersects one of a plurality of geometric boundaries. 
     
     
       16. The system of  claim 15 , where in the plurality of geometric boundaries include a plane, a sphere, or a surface. 
     
     
       17. The system of  claim 12 , wherein when no points along the ray intersect the geometric boundary, the pixel value for the particular pixel is determined based on a first point identified along the ray that has a density data value that meets the display density threshold. 
     
     
       18. The system of  claim 12 , wherein the plurality of data processors are configured to calculate a value based on the first identified point along each of a plurality of rays that intersect the geometric boundary. 
     
     
       19. The system of  claim 18 , wherein the calculated value is an area or a temperature associated with all of the first identified points. 
     
     
       20. The system of  claim 1 , wherein the pixel value for the particular pixel is colored based on results data from the results data structure associated with the first point identified along the ray that has a density data value that meets the display density threshold. 
     
     
       21. The system of  claim 1 , further comprises determining every physical value for each point along a ray that passes through the three dimensional volume, wherein in a second visualization, the visualization criterion commands visualization of a point identified along the ray that is identified as having a minimum or maximum associated physical value of every physical value;
 wherein the point identified along the ray as having the minimum or maximum associated results value is colored based upon the minimum or maximum associated results value. 
 
     
     
       22. The system of  claim 1 , wherein in a second visualization, the visualization criterion commands visualization of all points identified along the ray that are identified as having associated physical values within a range;
 wherein the points identified along the ray as having associated physical values within the range are colored based upon the associated physical values. 
 
     
     
       23. The system of  claim 1 , wherein the processor-readable memory further includes a motion indicator data structure, wherein the motion indicator data structure is configured to store a current position of a motion indicator within the three dimensional volume. 
     
     
       24. The system of  claim 23 , wherein the motion indicator includes a particle, wherein the particle is displayed in the two dimensional visualization based on the current position of the motion indicator. 
     
     
       25. The system of  claim 24 , wherein the processor-readable memory includes multiple motion indicator data structures, and wherein the two dimensional visualization depicts multiple particles simultaneously. 
     
     
       26. The system of  claim 23 , wherein the motion indicator includes a stream line, wherein the streamline is displayed in the two dimensional visualization based on the current position of the motion indicator and a previous position of the motion indicator. 
     
     
       27. The system of  claim 23 , wherein the processor cores are configured to update the current position of a particular motion indicator based on results data associated with the current position. 
     
     
       28. The system of  claim 27 , wherein the processor cores are configured to update the current position of the particular motion indicator by performing a mathematical calculation based on the current position of the particular motion indicator and the results data association with the current position. 
     
     
       29. The system of  claim 28 , wherein the results data is indicative of a velocity and a direction at points in the three dimensional volume, wherein the processor cores are configured to update the current position of the particular motion indicator based on a velocity and direction associated with the current position in the results data structure and the current position of the particular motion indicator and a velocity and direction associated with the particular motion indicator. 
     
     
       30. The system of  claim 1 , wherein the processor-readable memory and the plurality of data processors are components of a graphics processing unit. 
     
     
       31. The system of  claim 1 , wherein the density data structure is generated based on a source data structure stored on a second processor-readable memory that is external to the graphics processing unit. 
     
     
       32. The system of  claim 31 , wherein source data structure density values are sampled based on a determination of whether a point associated within source data structure density value is in the three dimensional volume. 
     
     
       33. The system of  claim 31 , wherein the system is configured to generate the density data structure based on a source data structure of arbitrary size. 
     
     
       34. The system of  claim 31 , wherein the density data structure is generated based on a subset of the source data structure, wherein upon a zoom in or zoom out command, wherein the system is configured to regenerate the density data structure based on a different subset of the source data structure. 
     
     
       35. The system of  claim 31 , wherein the results data structure is populated from a second source data structure stored on the second processor-readable memory that is external to the graphics processing unit. 
     
     
       36. The system of  claim 1 , wherein the two dimensional visualization includes an animation based on the density data and the results data. 
     
     
       37. The system of  claim 36 , wherein the animation is based on force physical values in the results data structure, wherein the plurality of data processors are configured to determine deformations in the three dimensional volume based on the force physical values. 
     
     
       38. The system for generating a physical model for engineering design or visualization of  claim 1 , wherein providing the visualization further includes:
 populating the density data structure with density data obtained from a source density data structure stored on first processor-readable memory that is external to the graphics processing unit; and 
 populating the results data structure with results data received as a stream of data from a software computation model. 
 
     
     
       39. The system for generating a physical model for engineering design or visualization of  claim 1 , wherein densities are a measure of a degree of inclusion within a three dimensional object. 
     
     
       40. The system of  claim 1 , wherein the value of the density data corresponding to the point on the boundary of the three dimensional volume is selected from the plurality of the pre-determined discretized values based on a degree of inclusion of the point within the three-dimensional volume. 
     
     
       41. The system of  claim 40 , wherein providing the visualization further comprises:
 assigning a background pixel value to the particular pixel if the ray does not intersect any point in the three dimensional volume; and 
 assigning a pixel value different from the background pixel value if the ray intersects any point in the three dimensional volume. 
 
     
     
       42. The system of  claim 41 , wherein all pixels along the ray that intersects any point in the three dimensional volume are assigned a common pixel value. 
     
     
       43. The system of  claim 41 , wherein pixels along the ray that intersects any point in the three dimensional volume are assigned different pixel values. 
     
     
       44. The system of  claim 43 , wherein the different pixel values assigned to pixels along the ray that intersects any point in the three dimensional volume are determined based at least on a shading criteria, the shading criteria comprising:
 a light pixel value assigned to pixels along the ray that intersects any point in the three dimensional volume if the density data for that pixel does not meet a shading threshold; and 
 a dark pixel value assigned to pixels along the ray that intersects any point in the three dimensional volume if the density data for that pixel meets the shading threshold. 
 
     
     
       45. A method of generating a physical model for engineering design or visualization, comprising:
 generating a density structure for storing density data at points in a three dimensional volume in a processor-readable memory, wherein the density data corresponds to the points for identifying whether each of the points is within or outside the three dimensional volume; 
 wherein the density data takes a plurality of discretized values with a pre-determined maximum value and the pre-determined minimum value, 
 wherein the pre-determined maximum value is larger than the pre-determined minimum value, 
 a plurality of discretized values between the pre-determined maximum value and the pre-determined minimum value, the points including a first point, a second point and a third point, 
 wherein the first point is within the three dimensional volume, a value of the density data corresponding to the first point is equal to the pre-determined maximum value, 
 wherein the second point is outside the three dimensional volume, a value of the density data corresponding to the second point is equal to the pre-determined minimum value, 
 wherein the third point is on the boundary of the three dimensional volume, a value of the density data corresponding to the third point is equal to one of the plurality of pre-determined discretized values between the pre-determined maximum value and the pre-determined minimum value, 
 generating a results data structure for storing results data in the processor-readable memory, the results data identifying physical values at the points in the three dimensional volume, wherein the results data is distinct from the density data; and 
 performing calculations using the density data and the results data to generate a physical model for providing a visualization utilizing a plurality of data processors operating in parallel, wherein providing the visualization includes:
 for a particular pixel, identifying a first point in the three dimensional volume along a ray originating from a vantage point having a corresponding density data structure density that meets a visualization criterion; and 
 determining a pixel value for the particular pixel based on a results data structure value that corresponds with the first identified point in the three dimensional volume. 
 
 
     
     
       46. A system for generating a physics simulation model for engineering design or visualization, comprising:
 a processor-readable memory, wherein the processor-readable memory includes:
 a density data structure containing density data corresponding to the points for identifying whether each of the points is within or outside the three dimensional volume, 
 wherein the density data takes a plurality of discretized values with a pre-determined maximum value and the pre-determined minimum value, 
 wherein the pre-determined maximum value is larger than the pre-determined minimum value, 
 a plurality of discretized values between the pre-determined maximum value and the pre-determined minimum value, 
 wherein when the point is within the three dimensional volume, the value of the density data corresponding to the point is equal to the pre-determined maximum value, 
 wherein when the point is outside the three dimensional volume, the value of the density data corresponding to the point is equal to the pre-determined minimum value, 
 wherein when the point is on the boundary of the three dimensional volume, the value of the density data corresponding to the point is equal to one of the plurality of pre-determined discretized values between the pre-determined maximum value and the pre-determined minimum value, 
 a results data structure containing results data, wherein the results data is distinct from the density data; 
 a volumetric data structure for storing volumetric data, wherein the volumetric data is based on at least the density data and the results data; and 
 
 a plurality of data processors that operate in parallel to perform calculations using the volumetric data to generate a discretized physics model based on visualization algorithms and physics computational algorithms, wherein the visualization algorithm includes:
 for a particular pixel, identifying a first point in the three dimensional volume along a ray originating from a vantage point having a corresponding density data structure density that meets a visualization criterion; and 
 determining a pixel value for the particular pixel based on a results data structure value that corresponds with the first identified point in the three dimensional volume.