Viewpoint dependent brick selection for fast volumetric reconstruction

Patent metadata

Field	Value
Publication number	US-11024095-B2
Application number	US-202016809376-A
Country	US
Kind code	B2
Filing date	Mar 4, 2020
Priority date	Dec 22, 2017
Publication date	Jun 1, 2021
Grant date	Jun 1, 2021

Abstract

A method to culling parts of a 3D reconstruction volume is provided. The method makes available to a wide variety of mobile XR applications fresh, accurate and comprehensive 3D reconstruction data with low usage of computational resources and storage spaces. The method includes culling parts of the 3D reconstruction volume against a depth image. The depth image has a plurality of pixels, each of which represents a distance to a surface in a scene. In some embodiments, the method includes culling parts of the 3D reconstruction volume against a frustum. The frustum is derived from a field of view of an image sensor, from which image data to create the 3D reconstruction is obtained.

First claim

What is claimed is:

1. A method of operating a computing system to generate a three-dimensional (3D) reconstruction of a surface in a scene, the method comprising:
accessing information that describes a plurality of bricks for the scene, each brick comprising a plurality of voxels;
accessing a depth image comprising a plurality of pixels;
conducting a first acceptance test for each of the plurality of bricks, wherein the first acceptance test comprises accepting said brick for further processing based at least in part on determining a pixel of the plurality of pixels intersects said brick; and
generating the 3D reconstruction based on the accepted bricks.

2. The method of claim 1 , further comprising:
conducting a second acceptance test comprising accepting bricks that have a position in front of a background as indicated by pixels in the depth image, wherein each pixel of the depth image indicates a distance to a region adjacent the surface in the scene.

3. The method of claim 2 , wherein:
the second acceptance test comprises accepting bricks that have a position in front of a solid or holey background as indicated by pixels in the depth image.

4. The method of claim 3 , wherein:
generating the 3D reconstruction comprises selecting processing for accepted pixels based on whether the pixel was accepted in the first acceptance test or second acceptance test.

5. The method of claim 2 , wherein:
the first and second acceptance tests are performed in sequence such that the second acceptance test is performed on bricks neither accepted nor rejected in the first acceptance test.

6. The method of claim 1 , wherein:
determining a pixel of the plurality of pixels intersects said brick comprises:
computing a minimum and maximum distance, in coordinates of the depth image, to a bounding box around a projection of the brick into the depth image; and
accepting the brick when, for at least one pixel, the distance value of the pixel is between the minimum and maximum dimensions.

7. The method of claim 1 , wherein:
each pixel of the depth image indicates a distance to a region adjacent the surface in the scene;
the method further comprises conducting a second acceptance test on at least a portion of the bricks not accepted in the first acceptance test, the second acceptance test comprising for each such brick:
accepting the brick if the maximum dimension is less than the distance value for any pixel in the depth image.

8. The method of claim 7 , further comprising:
for each brick accepted in the second acceptance test, selecting processing for the accepted pixel based on whether the minimum dimension is greater than the distance value for any pixel in the depth image.

9. The method of claim 1 , further comprising:
rejecting said brick for further processing when bricks determined to be behind a surface represented in the depth image.

10. The method of claim 1 , wherein the further processing comprises:
updating the plurality of voxels of an accepted brick based on image data of the scene.

11. The method of claim 1 , wherein determining a pixel intersects said brick comprises projecting a brick silhouette of said brick into the depth image, the brick silhouette being a minimum bounding box for said brick projected on the depth image.

12. The method of claim 1 , wherein determining whether each of the portion of the plurality of pixels intersects said brick comprises:
computing minimum and maximum padded values for said brick;
for each of the portion of the plurality of pixels, comparing a distance indicated by said pixel against the minimum and maximum padded values of said brick; and
determining said pixel intersects said brick when the distance indicated by said pixel is between the maximum and the minimum padded values.

13. The method of claim 1 , wherein:
the depth image corresponds to a camera frustum, the camera frustum being in the shape of a 3D trapezoidal prism;
the method comprises culling a portion of the plurality of bricks against the camera frustum so as to produce a reduced set of bricks before conducting the first acceptance test; and
the first acceptance test is conducted against the reduced set of bricks.

14. The method of claim 13 , wherein culling a portion of the plurality of bricks against the camera frustum comprises:
finding a cubic axis-aligned bounding box (AABB) to contain the trapezoidal prism;
conducting a third acceptance test, wherein the third acceptance test comprises:
dividing the AABB into a plurality of sub-AABBs,
determining each of the plurality of sub-AABBs intersects with the trapezoidal prism, and
rejecting bricks corresponding to a sub-AABB as outside the camera frustum when the sub-AABB is determined as not intersecting the camera frustum; and
repeating the third acceptance test until a sub-AABB corresponds to only one brick.

15. The method of claim 14 , wherein determining each of the plurality of sub-AABBs intersects with the trapezoidal prism comprises:
determining at least one corner point of the sub-AABB lies inside each of planes delimiting the camera frustum; and
determining every corner point of the camera frustum lies inside the sub-AABB.

16. A computing device configured to generate a three-dimensional (3D) reconstruction of a portion of a scene, the computing device comprising:
a central processing unit (CPU) coupled to access a depth image and a visual image; and
at least one non-transitory computer-readable medium comprising computer-executable instructions configured for execution on the CPU that, when executed by the CPU, perform a method comprising:
selecting bricks representing portions of the scene based at least in part on an intersection between the bricks and the depth image; and
computing a 3D representation based on portions of the visual image corresponding the selected bricks.

17. The computing device of claim 16 , comprising:
a depth sensor, wherein the CPU is coupled to receive the depth image from the depth sensor.

18. The computing device of claim 16 , comprising:
a support member comprising a portion of a head-mounted device.

19. The computing device of claim 18 , wherein the head-mounted device further comprises a display.

20. The computing device of claim 16 , comprising:
an image sensor having a field of view defining a frustum within the scene, wherein the visual image is from the image sensor; and
the portion of the scene is defined by the frustum.

Assignees

• Magic Leap Inc

Inventors

• Steinbrücker Frank Thomas
• Molyneaux David Geoffrey
• Wu Zhongle
• Wei Xiaolin
• Min Jianyuan
• Zhang Yifu

Classifications

• G06T19/00 Primary

  Manipulating three-dimensional [3D] models or images for computer graphics · CPC title

• G06F3/01

  Input arrangements or combined input and output arrangements for interaction between user and computer (G06F3/16 takes precedence) · CPC title

• G02B27/01

  Head-up displays · CPC title

• H04N7/18

  Closed-circuit television [CCTV] systems, i.e. systems in which the video signal is not broadcast · CPC title

• G06T17/20

  Finite element generation, e.g. wire-frame surface description, {tesselation} · CPC title