Method and apparatus for transforming polygon data to voxel data for general purpose applications

• US 6,867,774 B1
• Filed: 12/02/2002
• Issued: 03/15/2005
• Est. Priority Date: 12/02/2002
• Status: Active Grant

• Current Assignee: Mcloud Technologies (USA) Inc.
• Original Assignee: Ngrain (Canada) Corporation
• Inventors: Halmshaw, Paul A., Woo, Andrew C.-H., Young, Jonathan M.
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US10/309,412
• Time in Patent Office: 834 Days
• Field of Search: 345/419, 345/424, 345/428, 345/581, 345/6, 382/154
• US Class Current: 345/424
• CPC Class Codes: G06T 15/08 Volume rendering

Abstract

A method and apparatus are provided for transforming 3D geometric data, such as polygon data (16) formed of polygons (18), into volumetric data (14) formed of voxels (12). According to the method, 3D geometric data to be converted to voxel data are acquired, and the resolution of a final voxel grid to be produced is obtained (e.g., user-defined). Then, each geometric unit (e.g., a polygon) in the 3D geometric data is mapped (or scan converted) to an imaginary voxel grid having a higher resolution than the resolution of the final voxel grid. Next, with respect to the geometric units that are mapped to the imaginary voxels in the imaginary voxel grid dividing one final (actual) voxel into smaller sub-volumes, a weighted average of the attribute values (color, normal, intensity, etc.) is obtained. The weighted average is stored as the attribute value of the final voxel.

Claims

1. An efficient method of transforming scan-convertible 3D geometric data to voxel data, comprising the steps of:

acquiring 3D geometric data;

obtaining the resolution of a final voxel grid to be produced;

mapping each geometric unit in the 3D geometric data to an imaginary voxel grid having a higher resolution than the resolution of the final voxel grid;

with respect to the geometric units that are mapped to the imaginary voxels in the imaginary voxel grid corresponding to a final voxel in the final voxel grid, obtaining a weighted average of the attribute values of those geometric units with respect to the imaginary voxels; and

storing the weighted average as the attribute value of the final voxel.

2. The method of claim 1, wherein the attribute value is selected from the group consisting of color, intensity, and normal values.

3. The method of claim 1, wherein the attribute value is selected from the group consisting of temperature, density, mass, tensile strength, and flammability values.

4. The method of claim 1, wherein plural types of attribute values are calculated for each final voxel, and each type of attribute values is stored separately.

5. The method of claim 1, wherein the 3D geometric data comprise polygonal data, and the geometric unit comprises a polygon.

6. The method of claim 1, wherein the 3D geometric data comprise b-spline surface data, constructive solid geometry (CSG) data, or subdivision surfaces data.

7. The method of claim 1, wherein the attribute value is a normal value, and a weighted average of the normal values of the geometric units mapped to the imaginary voxels is obtained by adding each normal value to a total normal value so that each addition will cause the magnitude of the total normal value to grow.

8. The method of claim 7, wherein the addition of a normal value to the total normal value will cause the magnitude of the total normal value to grow by changing the direction of the normal value by 180 degrees.

9. A computer-readable medium or signal having computer-executable instructions for performing the method in any one of claims 1-8.

10. An apparatus for transforming 3D geometric data to voxel data, comprising an input/output interface, display, memory, and processor with hardware and software components for performing the method in any one of claims 1-8.

11. A method of transforming surface-based 3D data to voxel data, comprising the steps of:

(a) acquiring surface-based 3D data;

(b) acquiring a texture map associated with the surface-based 3D data;

(c) mapping each surface unit in the surface-based 3D data to a voxel grid;

(d) for each voxel in the voxel grid mapped from the surface unit, obtaining a color value by interpolating the surface unit'"'"'s texture coordinates and then performing a lookup of the interpolated coordinate in the texture map; and

(e) storing the obtained color value for each voxel, wherein the color value represents and replaces the texture map.

12. The method of claim 11, wherein the step (c) of mapping each surface unit in the surface-based 3D data to a voxel grid comprises:

(i) obtaining the resolution of a final voxel grid to be produced; and

(ii) mapping each surface unit in the surface-based 3D data to an imaginary voxel grid having a higher resolution than the resolution of the final voxel grid; and

wherein the step (d) of obtaining a color value for each voxel in the voxel grid comprises;

(iii) with respect to the surface units that are mapped to the imaginary voxels in the imaginary voxel grid corresponding to the final voxel in the final voxel grid, obtaining a color value for each imaginary voxel by interpolating the surface unit'"'"'s texture coordinates and then performing a lookup of the interpolated coordinate in the texture map; and

(iv) obtaining a weighted average of the color values of those surface units with respect to the imaginary voxels.

13. The method of claim 11, wherein the surface-based 3D data comprise polygonal data, and the surface unit comprises a polygon.

14. The method of claim 11, wherein the surface-based 3D data comprise b-spline surface data or subdivision surfaces data.

15. A computer-readable medium or signal having computer-executable instructions for performing the method in any one of claims 11-14.

16. An apparatus for transforming surface-based 3D data to voxel data, comprising an input/output interface, display, memory, and processor with hardware and software components for performing the method in any one of claims 11-14.

17. A method of transforming surface-based 3D data to voxel data, comprising the steps of:

(a) acquiring surface-based 3D data;

(b) acquiring an attribute map associated with the surface-based 3D data;

(c) mapping each surface unit in the surface-based 3D data to a voxel grid;

(d) for each voxel in the voxel grid mapped from the surface unit, obtaining an attribute value by interpolating the surface unit'"'"'s attribute coordinates and then performing a lookup of the interpolated attribute coordinate in the attribute map; and

(e) storing the obtained attribute value for each voxel, wherein the attribute value represents and replaces the attribute map.

18. The method of claim 17, wherein the attribute map is selected from the group consisting of a bump map, radiosity map, transparency map, and reflection map.

19. The method of claim 17, wherein the step (c) of mapping each surface unit in the surface-based 3D data to a voxel grid comprises:

(i) obtaining the resolution of a final voxel grid to be produced; and

(ii) mapping each surface unit in the surface-based 3D data to an imaginary voxel grid having a higher resolution than the resolution of the final voxel grid; and

wherein the step (d) of, obtaining an attribute value for each voxel in the voxel grid comprises;

(iii) with respect to the surface units that are mapped to the imaginary voxels in the imaginary voxel grid corresponding to the final voxel in the final voxel grid, obtaining an attribute value for each imaginary voxel by interpolating the surface unit'"'"'s attribute coordinates and performing a lookup of the interpolated attribute coordinate in the attribute map; and

(iv) obtaining a weighted average of the attribute values of those surface units with respect to the imaginary voxels.

20. The method of claim 17, wherein the surface-based 3D data comprise polygonal data, and the surface unit comprises a polygon.

21. The method of claim 17, wherein the surface-based 3D data comprise b-spline surface data or subdivision surfaces data.

22. A computer-readable medium or signal having computer-executable instructions for performing the method in any one of claims 17-21.

23. An apparatus for transforming surface-based 3D data to voxel data, comprising an input/output interface, display, memory, and processor with hardware and software components for performing the method in any one of claims 17-21.

24. A method of transforming surface-based 3D data to voxel data for the purpose of complexity decimation, comprising the steps of:

acquiring surface-based 3D data;

obtaining the resolution of an intended display; and

mapping each surface unit in the surface-based 3D data to a voxel grid having a resolution corresponding to the resolution of the intended display.

25. The method of claim 24, wherein the voxel grid resolution is set at 0.5 to 2 of the resolution of the intended display.

26. The method of claim 24, wherein the surface-based 3D data comprise polygonal data, and the surface unit comprises a polygon.

27. The method of claim 24, wherein the surface-based 3D data comprise b-spline surface data or subdivision surfaces data.

28. A computer-readable medium or signal having computer-executable instructions for performing the method in any one of claims 24-27.

29. An apparatus for transforming surface-based 3D data to voxel data, comprising an input/output interface, display, memory, and processor with hardware and software components for performing the method in any one of claims 24-27.

30. A method of generating a normal for a voxel in voxel graphics, comprising:

(a) projecting a scan plane intersecting the voxel, wherein the scan plane is perpendicular to a first axis;

(b) using the scan plane, scanning for voxels in the direction perpendicular to the scan plane;

(c) recording the traversed distance before a voxel was found for each voxel space in the scan plane; and

(d) obtaining a normal (N₁, N₂, N₃), wherein N₁is the first component of the normal along the first axis, N₂ is the second component of the normal along the second axis perpendicular to the first axis, and N₃ is the third component of the normal perpendicular to both the first and second axes, by;

(i) setting N₁ as 1;

(ii) obtaining N₂ by adding incremental changes between the traversed distances recorded in each adjacent voxel spaces along the second axis and dividing the total incremental changes by the number of voxel spaces; and

(iii) obtaining N₃ by adding incremental changes between the traversed distances recorded in each adjacent voxel spaces along the third axis and dividing the total incremental changes by the number of voxel spaces.

31. The method of claim 30, wherein plural scan planes are projected, and each scan plane is used to obtain a normal separately.

32. The method of claim 30, wherein the scan plane is scanned in both positive and negative directions along the first axis, and each of the positive and negative scanning is used to obtain a normal separately.

33. The method of claim 30, wherein x, y, and z scan planes are projected, and each scan plane is scanned in both positive and negative directions perpendicular to the scan plane, to obtain six suggested normals for the voxel.

34. The method of claim 33, further comprising the steps of:

counting the number of discontinuities for each data set associated with each of the six normals, wherein a discontinuity is defined as a change between the traversed distances recorded in adjacent voxel spaces that is greater in magnitude than a predefined constant value; and

selecting one normal associated with the smallest number of discontinuities.

35. The method of claim 34, wherein the predefined constant value is a gradient radius of influence.

36. The method of claim 33, further comprising the step of:

averaging a set of available normals while ignoring the calculated contributions of a normal direction component from a scan plane where the component'"'"'s vector lies along the scan plane, to obtain one normal for the voxel.

37. A computer-readable medium or signal having computer-executable instructions for performing the method in any one of claims 30-36.

38. An apparatus comprising an input/output interface, display, memory, and processor with hardware and software components for performing the method in any one of claims 30-36.