Multi-stage block mesh simplification

Patent metadata

Field	Value
Publication number	US-10937246-B2
Application number	US-201816229532-A
Country	US
Kind code	B2
Filing date	Dec 21, 2018
Priority date	Dec 22, 2017
Publication date	Mar 2, 2021
Grant date	Mar 2, 2021

Abstract

A method of operating a computing system to generate a model of an environment represented by a mesh is provided. The method allows to update 3D meshes to client applications in real time with low latency to support on the fly environment changes. The method provides 3D meshes adaptive to different levels of simplification requested by various client applications. The method provides local update, for example, updating the mesh parts that are changed since last update. The method also provides 3D meshes with planarized surfaces to support robust physics simulations. The method includes segmenting a 3D mesh into mesh blocks. The method also includes performing a multi-stage simplification on selected mesh blocks. The multi-stage simplification includes a pre-simplification operation, a planarization operation, and a post-simplification operation.

First claim

What is claimed is:

1. A method of operating a computing system comprising one or more processors to generate a model of an environment represented by a mesh, the method comprising:
segmenting, with a processor of the one or more processors, the mesh into a plurality of first mesh blocks;
performing, with a processor of the one or more processors, a first simplification operation on each of a plurality of selected first mesh blocks to generate a plurality of second mesh blocks;
performing, with a processor of the one or more processors, a region-based operation on each of the second mesh blocks to generate a plurality of third mesh blocks, wherein the region-based operation comprises a planarization operation; and
performing, with a processor of the one or more processors, a second simplification operation on each of the third mesh blocks to generate fourth mesh blocks.

2. The method of claim 1 , wherein the first mesh blocks comprise a portion of a representation of the environment with a first value of a metric of complexity and the fourth mesh blocks comprise the portion of the representation of the environment with a fourth value of the metric of complexity, the fourth value being less than the first value.

3. The method of claim 2 , wherein the metric of complexity indicates a number of triangles in a respective mesh block.

4. The method of claim 2 , wherein:
the second mesh blocks comprise the portion of the representation of the environment with a second value of the metric of complexity;
the third mesh blocks comprise the portion of the representation of the environment with a third value of the metric of complexity; and
a percentage reduction between the third value and the fourth value is greater than a percentage reduction between the first value and the second value.

5. The method of claim 4 , wherein:
the percentage reduction between the third value and the fourth value is at least two times greater than the percentage reduction between the first value and the second value.

6. The method of claim 4 , wherein:
the fourth mesh blocks are generated by a meshing service with a cross reality platform; and
the method further comprises:
receiving, as an input to the meshing service, a value representing a mesh complexity; and
controlling, based on the value representing mesh complexity, the percentage reduction between the third value and the fourth value and the percentage reduction between the first value and the second value.

7. The method of claim 6 , wherein the value is provided by an application requesting meshes from the meshing service.

8. The method of claim 1 , wherein the first simplification operation and the second simplification operation are performed using the same simplification algorithm.

9. The method of claim 1 , wherein the first simplification operation and the second simplification operation are performed using a triangle reduction algorithm.

10. A method of operating a computing system comprising one or more processors to generate a model of an environment represented by a mesh, the method comprising:
segmenting, with a processor of the one or more processors, the mesh into a plurality of first mesh blocks;
performing, with a processor of the one or more processors, a first simplification operation on each of a plurality of selected first mesh blocks to generate a plurality of second mesh blocks;
performing, with a processor of the one or more processors, a region-based operation on each of the second mesh blocks to generate a plurality of third mesh blocks; and
performing, with a processor of the one or more processors, a second simplification operation on each of the third mesh blocks to generate fourth mesh blocks, wherein performing the first simplification operation on the plurality of selected first mesh blocks comprises processing the selected first mesh blocks in parallel.

11. The method of claim 1 comprising combining:
the plurality of fourth mesh blocks with a plurality of unselected second mesh blocks into a new mesh of the environment.

12. The method of claim 1 , wherein performing the region-based operation comprises:
detecting planar areas in the selected plurality of second mesh blocks by a region growing algorithm; and
simplifying the detected planar areas of the selected plurality of second mesh blocks.

13. The method of claim 12 , wherein simplifying the detected planar areas of the selected plurality of second mesh blocks is based on a target triangle count.

14. The method of claim 12 , wherein the region-based operation further comprises planarizing the selected plurality of second mesh blocks by projecting triangles of the detected planar areas of the selected plurality of second mesh blocks to corresponding planes.

15. The method of claim 14 , further comprising:
adjusting plane normals of the detected planar areas of the selected plurality of second mesh blocks to substantially vertical and parallel to the corresponding planes before simplifying the detected planar areas of the selected plurality of second mesh blocks.

16. A method of operating a computing system comprising one or more processors to generate a model of an environment represented by a mesh, the method comprising:
segmenting, with a processor of the one or more processors, the mesh into a plurality of first mesh blocks;
performing, with a processor of the one or more processors, a first simplification operation on each of a plurality of selected first mesh blocks to generate a plurality of second mesh blocks;
performing, with a processor of the one or more processors, a region-based operation on each of the second mesh blocks to generate a plurality of third mesh blocks; and
performing, with a processor of the one or more processors, a second simplification operation on each of the third mesh blocks to generate fourth mesh blocks, wherein the model of the environment is three dimensional (3D), and each first mesh block corresponds to a cube in the 3D model of the environment.

17. The method of claim 1 , wherein the first simplification operation on each of the plurality of selected first mesh blocks is performed in parallel.

18. The method of claim 1 , wherein the region-based operation on each of the second mesh blocks is performed in parallel.

19. The method of claim 1 , wherein the second simplification on each of the third mesh blocks is performed in parallel.

Assignees

• Magic Leap Inc

Inventors

• Molyneaux David Geoffrey
• Steinbrücker Frank Thomas
• 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