Method and apparatus for transforming point cloud data to volumetric data

• US 7,317,456 B1
• Filed: 12/02/2002
• Issued: 01/08/2008
• Est. Priority Date: 12/02/2002
• Status: Active Grant

• Current Assignee: Mcloud Technologies (USA) Inc.
• Original Assignee: Ngrain (Canada) Corporation
• Inventors: Lee, Michael J.
• Primary Examiner(s): Chauhan; Ulka
• Assistant Examiner(s): PAPPAS, PETER
• Application Number:
  US10/309,411
• Time in Patent Office: 1,863 Days
• Field of Search: None
• US Class Current: 345/427
• CPC Class Codes: G06T 15/08 Volume rendering
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects

Abstract

A method and apparatus are provided for transforming an irregular, unorganized cloud of data points (100) into a volumetric data or “voxel” set (120). Point cloud (100) is represented in a 3D cartesian coordinate system having an x-axis, a y-axis and a z-axis. Voxel set (120) is represented in an alternate 3D cartesian coordinate system having an x′-axis, a y′-axis, and a z′-axis. Each point P(x, y, z) in the point cloud (100) and its associated set of attributes, such as intensity or color, normals, density and/or layer data, are mapped to a voxel V(x′, y′, z′) in the voxel set (120). Given that the point cloud has a high magnitude of points, multiple points from the point cloud may be mapped to a single voxel. When two or more points are mapped to the same voxel, the disparate attribute sets of the mapped points are combined so that each voxel in the voxel set is associated with only one set of attributes.

Claims

1. A computer-readable medium storing computer-executable components for transforming point cloud data into voxel set data, the computer-executable components comprising:

a scaling component for generating a position scaling factor and a base offset for the point cloud data, the point cloud data comprising a set of unorganized points, wherein the scaling component generates the position scaling factor for the point cloud data by;

determining a maximum dimension of the voxel set data;

determining a maximum range of coordinates for the point cloud data; and

calculating the position scaling factor as a function of the maximum dimension and the maximum range; and

a mapping component for mapping each point of the point cloud data to a voxel of the voxel set data using the base offset and position scaling factor for the point cloud data, wherein each point of the point cloud data is mapped to an alternate coordinate system.

2. The computer-readable medium of claim 1, wherein for each point of point cloud data, the mapping component maps the point of the point cloud data to a voxel of the voxel set data by determining a position of the voxel in the alternate coordinate system as a function of a position of the point in a first coordinate system, the base offset for the point cloud data and the position scaling factor.

3. The computer-readable medium of claim 2, wherein for each point of point cloud data, the mapping component further transfers at least one attribute associated with the point to the voxel to which the point is mapped if said voxel has not yet been transferred any attributes.

4. The computer-readable medium of claim 3, wherein for each point of point cloud data, the mapping component combines the at least one attribute associated with the point with any similar attributes of prior points mapped to the same voxel and transfers the combined attributes to said voxel, if said voxel has already been transferred attributes.

5. The computer-readable medium of claim 4, wherein the mapping component combines the attributes based on a predetermined function.

6. The computer-readable medium of claim 5, wherein the predetermined function is an averaging function.

7. The computer-readable medium of claim 5, wherein the predetermined function is an override function.

8. The computer-readable medium of claim 3, wherein the at least one attribute is intensity.

9. The computer-readable medium of claim 8, wherein the scaling component further generates an intensity scaling factor that is applied to the intensity attribute when the intensity attribute is transferred from the point to the voxel.

10. The computer-readable medium of claim 3, wherein the at least one attribute is color.

11. The computer-readable medium of claim 3, wherein the at least one attribute is a set of normal values.

12. The computer-readable medium of claim 3, wherein the at least one attribute is density.

13. The computer-readable medium of claim 3, wherein the at least one attribute is layer data.

14. The computer-readable medium of claim 1, further comprising a normals generating component for generating normals associated with each voxel of the voxel set data if the point cloud data does not already contain normals.

15. The computer-readable medium of claim 1, further comprising a layer data generating component for generating layer data associated with each voxel of the voxel set data if the point cloud data does not already contain layer data.

16. The computer-readable medium of claim 1, wherein the maximum dimension of the voxel set data is based on a resolution of a display device upon which the volumetric data will be rendered.