Efficient methods and apparatus for resampling three dimensional datasets

• US 6,687,393 B1
• Filed: 07/16/1999
• Issued: 02/03/2004
• Est. Priority Date: 07/16/1999
• Status: Expired due to Term

• Current Assignee: General Electric Company
• Original Assignee: General Electric Company
• Inventors: Skinner, Jr., John V.
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US09/354,822
• Time in Patent Office: 1,663 Days
• Field of Search: 382/131-132, 382/154, 382/285, 345/419-424, 345/426, 378/4, 378/11, 378/15, 378/197, 378/205, 378/405, 600/400, 600/425, 600/437, 600/443
• US Class Current: 382/131
• CPC Class Codes: G06T 15/08 Volume rendering
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• CPC Class Codes: Y10S 378/901 Computer tomography program or processor

Abstract

In one form, the present invention is a method for rapidly resampling a three-dimensional volume of data to permit efficient interactive viewing and visualization of the data is provided in which a set of parallel line segments defining a surface having a constant slope in at least one direction and intersecting the three-dimensional volume are selected and the data is processed at points on the parallel line segments to generate a reformatted image of the data. A corresponding apparatus embodiment is provided. Processing of data can proceed quickly because it is not necessary to check the parallel line segments during processing of the points on the segments to determine whether the points are within a given data volume.

Claims

1. A method for rapidly resampling a three-dimensional volume of data to permit efficient interactive viewing and visualization of the data, the method comprising:

selecting a set of parallel line segments defining a surface having a constant slope in at least one direction and intersecting the three-dimensional volume, wherein selecting a set of parallel line segments comprises the step of clipping ends of the line segments so that the clipped line segments lie wholly within the three-dimensional volume; and

processing the data by resampling the three-dimensional volume of data at points on the parallel line segments to generate a reformatted image of the data, wherein the processing comprises;

selecting a sampling function; and

computing the selected sampling of the data at points along the clipped line segments.

2. A method in accordance with claim 1 wherein the processing step comprises processing the data along at points on the clipped line segments.

3. A method in accordance with claim 2 selecting a sampling function comprises the step of selecting a specialized sampling function corresponding to a slope of the parallel line segments.

4. A method in accordance with claim 3 wherein selecting a specialized sampling function corresponding to a slope of the parallel line segments comprises the step of selecting one of a plurality of specialized sampling functions in accordance with a slope of the parallel line segments.

5. A method in accordance with claim 4 wherein selecting one of a plurality of specialized sampling functions comprises the step of selecting a specialized sampling function having a selected interpolation method from among several specialized sampling functions corresponding to a slope of the parallel line segments and that provide different interpolation methods.

6. A method in accordance with claim 4 wherein selecting one of a plurality of specialized sampling functions comprises the step of selecting a specialized sampling function having a selected voxel addressing scheme from among several specialized sampling functions corresponding to a slope of the parallel line segments and that provide different voxel addressing schemes.

7. A method in accordance with claim 4 and further comprising the step of generating the sampling functions from a template.

8. A method in accordance with claim 7 wherein generating the sampling functions comprises the step of generating the sampling functions using class-structured sets of macros.

9. A method in accordance with claim 7 wherein selecting a specialized sampling function having a selected interpolation method comprises the step of selecting a trilinear interpolation, nearest neighbor, or process sampling function.

10. A method in accordance with claim 3 wherein computing the selected specialized sampling of the data at points along the clipped line segments comprises the step of applying a step-and-interpolate iteration to the sample data.

11. A method in accordance with claim 10 wherein the applied step-and-interpolate iteration is free of bounds checking.

12. A method in accordance with of claim 1 wherein selecting a set of parallel line segments comprises the step of selecting a set of non-colinear coplanar parallel line segments that extend in three dimensions.

13. A method in accordance with claim 1 wherein selecting a set of parallel line segments comprises the step of selecting a set of parallel line segments in a surface having a pair of orthogonal axes, the surface having curvature along exactly one of the pair of orthogonal axes.

14. A method in accordance with claim 1 wherein clipping ends of the line segments comprises the steps of:

determining a first set of faces of the volume for clipping a first endpoint of each of the line segments and a second set of faces of the volume for clipping a second, opposite endpoint of each of the line segments; and

for each line segment, analyzing the first endpoint of the line segment and the first set of faces to clip at a first clipping point, and analyzing the second endpoint of the line segment and the second set of faces to clip at a second clipping point.

15. A method in accordance with claim 14 wherein determining a first set of faces and a second set of faces comprises the step of determining a first set of three faces and a second set of three faces.

16. A method in accordance with claim 1 and further comprising the step of selecting a baseline segment forming one edge of a sampling region.

17. A system for rapidly resampling a three-dimensional volume of data for efficient interactive viewing and visualization of the data, said system configured to:

select a set of parallel line segments defining a surface having a constant slope in at least one direction and intersecting the three-dimensional volume;

clip ends of the parallel line segments so that the clipped line segments lie wholly within the three-dimensional volume;

process the data by resampling the three-dimensional volume of data at points on the parallel line segments to generate a reformatted image of the data;

select a sampling function; and

compute the selected sampling of the data at points along the clipped line segments.

18. A system in accordance with claim 17 wherein said system is further configured to process the data at points on the clipped line segments.

19. A system in accordance with claim 18 wherein said system is further configured to select a set of parallel line segments in a surface having a pair of orthogonal axes, the surface having curvature along exactly one of the pair of orthogonal axes.

20. A system in accordance with claim 18 wherein said system is further configured to select a specialized sampling function corresponding to a slope of the parallel line segments.

21. A system in accordance with claim 18 wherein said system is further configured to determine a first set of faces of the volume for clipping a first endpoint of each of the line segments and a second set of faces of the volume for clipping a second, opposite endpoint of the line segments, to analyze, for each line segment, the first endpoint of the line segment and the first set of faces to clip at a first clipping point, and to analyze the second endpoint of the line segment and the second set of faces to clip at a second clipping point.

22. A system in accordance with claim 21 wherein said system is further configured to determine a first set of three faces as the first set of faces of the volume, and to determine a second set of three faces as the second set of faces of the volume.

23. A system in accordance with claim 21 wherein said system is further configured to apply a step-and-interpolate iteration to the sample data as part of the computation of the selected specialized sampling of the data at points along the clipped line segments.

24. A system in accordance with claim 18 wherein said system is further configured to select a set of non-colinear coplanar parallel line segments that extend in tree dimensions.

25. A system in accordance with of claim 24 wherein said system is further configured to select one of plurality of specialized sampling functions in accordance with a slope of the parallel line segments.

26. A system in accordance with claim 25 wherein said system is further configured to select a specialized sampling function having a selected interpolation method from among several specialized sampling functions corresponding to a slope of the parallel line segments and that provide different interpolation methods.

27. A system in accordance with claim 25 wherein said system is further configured to select one of a plurality of specialized sampling functions having a selected voxel addressing scheme from among several specialized sampling functions corresponding to a slope of the parallel line segments and that provide different voxel addressing schemes.

28. A system in accordance with claim 25 wherein said system is further configured to generate sampling functions from a sampling function template.

29. A system in accordance with claim 28 wherein said system is further configured to generate sampling functions using class-strucured sets of macros.

30. A system in accordance with claim 25 wherein said system is further configured to select a specialized sampling function having a selected interpolation method from a group of sampling methods including trilinear interpolation, nearest neighbor, and process sampling functions.

31. A system in accordance with claim 30 wherein said system is further configured so that the step-and-interpolate iteration is free of bounds checking.

32. A system in accordance with claim 17 wherein said system is further configured to select a baseline segment forming one edge of a sampling region.