3D computer modelling apparatus

• US 20020186216A1
• Filed: 06/10/2002
• Published: 12/12/2002
• Est. Priority Date: 06/11/2001
• Status: Active Grant

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Lyons, Alexander Ralph, Baumberg, Adam Michael, Kotcheff, Aaron William Christopher
• Granted Patent: US 6,952,204 B2
• Time in Patent Office: Days
• US Class Current: 345/422
• CPC Class Codes: G06T 17/10 Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation
• CPC Class Codes: G06T 17/205 Re-meshing

Abstract

In a computer processing apparatus 3002, a number of depth maps 3200-3270 of a subject object 3300 are processed to generate a 3D computer model of the subject object. The points in each depth map are connected to give a 2D mesh, and each 2D mesh is then projected into 3D space in dependence upon the depths of the points in the mesh, thereby giving a 3D mesh 3610. Side faces for each edge of the 3D mesh are added extending away from the depth map, thereby generating a respective polyhedron 3600 for each depth map. The 3D computer model of the subject object is generated by calculating the intersections of the polyhedra.

Claims

1. A method of processing data defining a plurality of depth maps of a subject object, to generate a 3D computer model of the subject object comprising points in a three-dimensional space representing points on the surface of the subject object, the method comprising:

processing each depth map to connect points therein to generate a respective two-dimensional mesh of connected points in each depth map;

projecting each two-dimensional mesh into three-dimensional space in dependence upon the position and orientation in the three-dimensional space of the depth map containing the mesh and the respective depths of the points in the mesh defined by the depth map, to generate a respective polyhedron from each depth map, each polyhedron comprising a three-dimensional mesh of connected vertices defining planar faces corresponding to the two-dimensional mesh, together with planar side faces for each edge of the three-dimensional mesh;

calculating points in the three-dimensional space representing points on the surface of the subject object by calculating the respective points at which a predetermined number of the planar surfaces from the generated polyhedra intersect.

2. A method according to claim 1, wherein each depth map comprises an array of pixels, and wherein, in the processing of a depth map to connect points therein, pixels are divided into sub-pixels and sub-pixels are connected to generate the two-dimensional mesh.

3. A method according to claim 1, further comprising processing each generated polyhedron prior to the intersection calculations, to replace each vertex in the polyhedron at which more than three planar faces meet with a plurality of vertices at each of which no more than three planar faces meet.

4. A method according to claim 3, wherein each replacement vertex is defined to have the same position in the three-dimensional space as the vertex which it replaces.

5. A method according to claim 1, wherein the calculation of points in the three-dimensional space representing points on the surface of the subject object comprises:

defining a volume of the three-dimensional space in which all points on the subject object must lie;

subdividing the volume into a plurality of volume parts;

testing the volume parts against the polyhedra generated from the depth maps, and;

discarding a volume part if it is wholly outside at least one of the polyhedra;

if a volume part is at least partially within all of the polyhedra, processing the data defining the planar surfaces which intersect the volume part and, in dependence upon the number of planar surfaces which intersect the volume part;

subdividing the volume part into a plurality of smaller volume parts for further testing;

calculating the 3D points in the volume part at which a predetermined number of the planar surfaces meet;

or

discarding the volume part.

6. A method according to claim 5, wherein a volume part is subdivided if the volume part is at least partially within all of the polyhedra and the number of planar surfaces which intersect the volume part is more than a predetermined number.

7. A method according to claim 5, wherein a volume part is discarded if the volume part is at least partially within all of the polyhedra and the number of planar surfaces which intersect the volume part is less than a predetermined number.

8. A method according to claim 5, wherein, when a volume part is tested, data is stored defining the planar surfaces which intersect the volume part, and when a smaller volume part is tested which was generated by subdivision of a parent volume part, only the planar surfaces which intersect the parent volume part are tested to determine whether they intersect the smaller volume part.

9. A method according to claim 5, wherein, when a volume part is tested, data is stored defining each polyhedron which the volume part is determined to lie wholly inside, and, when a smaller volume part is tested which was generated by subdivision of a parent volume part, tests are carried out to determine whether the smaller volume part lies inside each of the polyhedra not defined in the stored data, but no tests are carried out to determine whether the smaller volume part lies inside any of the polyhedra defined in the stored data.

10. A method according to claim 1, further comprising connecting the calculated points in the three-dimensional space representing points on the surface of the subject object to generate a 3D computer model comprising a polygon mesh representing the surface of the subject object.

11. A method according to claim 1, further comprising generating a signal conveying the 3D computer model.

12. A method according to claim 11, further comprising making a recording of the signal either directly or indirectly.

14. Apparatus according to claim 13, wherein each depth map comprises an array of pixels, and wherein the depth map point connector is arranged to divide pixels into sub-pixels and to connect sub-pixels to generate the two-dimensional mesh.

15. Apparatus according to claim 13, further comprising a vertex replacer operable to process each generated polyhedron prior to processing by the 3D point calculator, to replace each vertex in the polyhedron at which more than three planar faces meet with a plurality of vertices at each of which no more than three planar faces meet.

16. Apparatus according to claim 15, wherein the vertex replacer is arranged to define each replacement vertex to have the same position in the three-dimensional space as the vertex which it replaces.

17. Apparatus according to claim 13, wherein the 3D point calculator comprises:

a volume definer operable to define a volume of the three-dimensional space in which all points on the subject object must lie;

a volume divider operable to subdivide the volume into a plurality of volume parts; and

a volume tester operable to test the volume parts against the polyhedra generated by the projection means, the volume tester being arrange to;

discard a volume part if it is wholly outside at least one of the polyhedra;

if a volume part is at least partially within all of the polyhedra, process the data defining the planar surfaces which intersect the volume part and, in dependence upon the number of planar surfaces which intersect the volume part;

subdivide the volume part into a plurality of smaller volume parts for further testing;

calculate the 3D points in the volume part at which a predetermined number of the planar surfaces meet;

or

discard the volume part.

18. Apparatus according to claim 17, wherein the volume tester is arranged to subdivide a volume part if the volume part is at least partially within all of the polyhedra and the number of planar surfaces which intersect the volume part is more than a predetermined number.

19. Apparatus according to claim 17, wherein the volume tester is arranged to discard a volume part if the volume part is at least partially within all of the polyhedra and the number of planar surfaces which intersect the volume part is less than a predetermined number.

20. Apparatus according to claim 17, wherein the volume tester is arranged to store data when a volume part is tested defining the planar surfaces which intersect the volume part, and is arranged to operate so that, when a smaller volume part is tested which was generated by subdivision of a parent volume part, only the planar surfaces which intersect the parent volume part are tested to determine whether they intersect the smaller volume part.

21. Apparatus according to claim 17, wherein the volume tester is arranged to store data when a volume part is tested defining each polyhedron which the volume part is determined to lie wholly inside, and is arranged to operate so that, when a smaller volume part is tested which was generated by subdivision of a parent volume part, tests are carried out to determine whether the smaller volume part lies inside each of the polyhedra not defined in the stored data, but no tests are carried out to determine whether the smaller volume part lies inside any of the polyhedra defined in the stored data.

22. Apparatus according to claim 13, further comprising a point connector operable to connect the calculated points in the three-dimensional space representing points on the surface of the subject object to generate a 3D computer model comprising a polygon mesh representing the surface of the subject object.

23. A storage device storing instructions for causing a programmable processing apparatus to become operable to perform a method as set out in claim 1.

24. A signal conveying instructions for causing a programmable processing apparatus to become operable to perform a method as set out in claim 1.

13. Apparatus for processing data defining a plurality of depth maps of a subject object, to generate a 3D computer model of the subject object comprising points in a three-dimensional space representing points on the surface of the subject object, the apparatus comprising:

a depth map point connector operable to process each depth map to connect points therein to generate a respective two-dimensional mesh of connected points in each depth map;

a mesh projector operable to project each two-dimensional mesh generated by the connection means into three-dimensional space in dependence upon the position and orientation in the three-dimensional space of the depth map containing the mesh and the respective depths of the points in the mesh defined by the depth map, to generate a respective polyhedron from each depth map, each polyhedron comprising a three-dimensional mesh of connected vertices defining planar faces corresponding to the two-dimensional mesh, together with planar side faces for each edge of the three-dimensional mesh; and

a 3D point calculator operable to calculate points in the three-dimensional space representing points on the surface of the subject object by calculating the respective points at which a predetermined number of the planar surfaces from the polyhedra generated by the projection means intersect.

25. Apparatus for processing data defining a plurality of depth maps of a subject object, to generate a 3D computer model of the subject object comprising points in a three-dimensional space representing points on the surface of the subject object, the apparatus comprising:

connection means for processing each depth map to connect points therein to generate a respective two-dimensional mesh of connected points in each depth map;

projection means for projecting each two-dimensional mesh generated by the connection means into three-dimensional space in dependence upon the position and orientation in the three-dimensional space of the depth map containing the mesh and the respective depths of the points in the mesh defined by the depth map, to generate a respective polyhedron from each depth map, each polyhedron comprising a three-dimensional mesh of connected vertices defining planar faces corresponding to the two-dimensional mesh, together with planar side faces for each edge of the three-dimensional mesh; and

3D point calculation means for calculating points in the three-dimensional space representing points on the surface of the subject object by calculating the respective points at which a predetermined number of the planar surfaces from the polyhedra generated by the projection means intersect.