Method and apparatus for transforming point cloud data to volumetric data

• US 7,420,555 B1
• Filed: 11/20/2007
• Issued: 09/02/2008
• Est. Priority Date: 12/02/2002
• Status: Expired due to Term

• 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-Anthony
• Application Number:
  US11/943,491
• Time in Patent Office: 287 Days
• Field of Search: None
• US Class Current: 345/424
• 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-implemented method for transforming a point cloud into a voxel set, the voxel set requiring less storage space than the point cloud, the point cloud containing an unorganized plurality of points, each point associated with a set of attributes containing at least one attribute, the method comprising:

mapping each point in to unorganized plurality of points and its associated set of attributes to a voxel in the voxel set; and

if multiple points in the unorganized plurality of points map to the same voxel in the voxel set, combining the sets of attributes associated with the multiple points mapped to said voxel into a single set of attributes for said voxel.

2. The method of claim 1, further comprising:

if only one point in the unorganized plurality of points is mapped to a voxel, setting the set of attributes for said voxel to the set of attributes for said point.

3. The method of claim 1, wherein the point cloud is located in a first coordinate system and the voxel set is located in a second coordinate system, and wherein mapping each point in the unorganized plurality of points to a voxel in the voxel set comprises mapping position coordinates of the point in the first coordinate system to position coordinates of the voxel in the second coordinate system.

4. The method of claim 3, wherein mapping position coordinates for the point in the first coordinate system to position coordinates for the voxel in the second coordinate system comprises scaling the position coordinates of the point in the first coordinate system to the position coordinates of the voxel in the second coordinate system.

5. The method of claim 4, wherein the first coordinate system is a floating point-based coordinate system and the second coordinate system is an integer-based coordinate system.

6. The method of claim 3, wherein at least one attribute in the set of attributes associated each point is scaled when the point is mapped to the voxel.

7. The method of claim 6, wherein the at least one attribute that is scaled is intensity.

8. The method of claim 1, wherein similar attributes within the sets of attributes associated with each of the multiple points mapped to said voxel are combined into a single set of attributes for said voxel based on a predetermined function.

9. The method of claim 8, wherein the predetermined function is an averaging function.

10. The method of claim 8, wherein the predetermined function is an override function.

11. The method of claim 1, further comprising:

if the set of attributes associated with the points of the unorganized plurality of points does not contain a predetermined attribute, generating the predetermined attribute for the set of attributes for each voxel of the voxel set.

12. The method of claim 11, wherein the predetermined attribute is a set of normal values.

13. An apparatus for transforming point cloud data into voxel set data, the apparatus comprising:

a constrained memory for storing the point cloud data and voxel set data, the point cloud data comprising a set of unorganized points, the voxel set data requiring less storage space than the point cloud data; and

a standard processing unit coupled to the constrained memory, the processing unit executing program code for transforming the point cloud data into the voxel set data, the program code executed by the standard processing unit transforming the point cloud data into the voxel set data by mapping each point of point cloud data to a voxel of voxel set data, assigning an attribute associated with each point of point cloud data to the voxel to which the point is mapped, and combining the attributes associated with a plurality of points as a single attribute and assigns the single attribute to the voxel if a plurality of points are mapped to the same voxel.

14. The apparatus of claim 13, wherein the program code executed by the standard processing unit maps each point of point cloud data to a voxel of voxel set data by mapping floating point-based position coordinates for each point to integer-based position coordinates for the voxel.

15. The apparatus of claim 14, wherein the program code executed by the standard processing unit scales the floating point-based position coordinates for each point to the integer-based position coordinates for the voxel when mapping the floating point-based position coordinates for each point to integer-based position coordinates for the voxel.

16. The apparatus of claim 13, wherein the program code executed by the standard processing unit assigns the attribute associated with the point mapped to a voxel, if the point is the only point mapped to the voxel.

17. The apparatus of claim 13, wherein the program code executed by the standard processing unit combines a plurality of attributes associated with each point of point cloud data into a single set of attributes and assigns the singe set of attributes to the voxel, if a plurality of attributes are associated with each point of point cloud data and a plurality of points are mapped to the same voxel.

18. The apparatus of claim 13, wherein the program code executed by the standard processing unit scales the attribute assigned to the voxel from the attribute associated with the point mapped to the voxel.

19. The apparatus of claim 18, wherein the scaled attribute is intensity.

20. The apparatus of claim 13, wherein the program code executed by the standard processing unit generates a predetermined attribute for each voxel if the predetermined attribute is not already associated with the points mapped to each voxel.

21. The apparatus of claim 20, wherein the predetermined attribute is a set of normal values.

22. A method for complexity decimation of point cloud data, the point cloud data containing an unorganized plurality of points, each point associated with a set of attributes containing at least one attribute, the method comprising:

mapping each point in the point cloud and its associated set of attributes to a voxel of volumetric data;

if multiple points in the point cloud map to the same voxel of volumetric data, creating a less complex set of attributes for said voxel from the sets of attributes associated with the multiple points mapped to said voxel, wherein the less complex set of attributes for a voxel is created by combining similar attributes within the sets of attributes associated with each of the multiple points mapped to said voxel based on a predetermined function; and

if only one point in the point cloud is mapped to a voxel, setting the set of attributes for said voxel to the set of attributes for said point.

23. The method of claim 22, wherein the point cloud data is located in a first coordinate system and the volumetric data is located in a second coordinate system, and wherein mapping each point in the point cloud data to a voxel of volumetric data comprises mapping position coordinates of the point in the first coordinate system to position coordinates of the voxel in the second coordinate system.

24. The method of claim 23, wherein mapping position coordinates for the point in the first coordinate system to position coordinates for the voxel in the second coordinate system comprises scaling the position coordinates of the point in the first coordinate system to the position coordinates of the voxel in the second coordinate system.

25. The method of claim 24, wherein the first coordinate system is a floating point-based coordinate system and the second coordinate system is an integer-based coordinate system.

26. The method of claim 24, wherein at least one attribute in the set of attributes associated each point is scaled when the point is mapped to the voxel.

27. The method of claim 26, wherein the at least one attribute that is scaled is intensity.

28. The method of claim 22, wherein the predetermined function is an averaging function.

29. The method of claim 22, wherein the predetermined function is an override function.

30. The method of claim 22, wherein the volumetric data to which the point cloud data is mapped has a maximum dimension that depends on a resolution of a display device upon which the volumetric data will be displayed.

31. 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;

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; and

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,

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, and

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.

32. The computer-readable medium of claim 31, 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 an 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.

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

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

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

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

37. The computer-readable medium of claim 36, 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.

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

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

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

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

42. The computer-readable medium of claim 31, 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.

43. The computer-readable medium of claim 31, 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.