Mesh hole area detection

Patent metadata

Field	Value
Publication number	US-2022237803-A1
Application number	US-202117156202-A
Country	US
Kind code	A1
Filing date	Jan 22, 2021
Priority date	Jan 22, 2021
Publication date	Jul 28, 2022
Grant date	—

Abstract

A computer implemented method includes obtaining a mesh representative of a scanned environment. Boundary edges of the mesh are identified. The boundary edges are grouped into ordered, connected three-dimensional closed non-intersecting polygons. A polygon is classified as a hole, and the area of the hole is determined.

First claim

1 . A computer implemented method comprising:
obtaining a mesh representative of a scanned environment; identifying boundary edges in the mesh; grouping the boundary edges into ordered, connected three-dimensional closed non-intersecting polygons; classifying a polygon as a hole; and determining an area of the hole.

2 . The method of claim 1 wherein grouping the boundary edges comprises:
projecting the connected three-dimensional polygons onto a two-dimensional plane; and
removing self-intersecting polygons.

3 . The method of claim 2 wherein the connected three-dimensional polygons are iteratively projected onto a two-dimensional plane from multiple different perspectives until a projection is found where edges of the projection do not self-intersect.

4 . The method of claim 2 wherein classifying a polygon as a hole comprises:
examining each projected edge of the polygon to determine whether the projected edge lies towards or away from an inside of the projected boundary;
determining a ratio of projected edges facing away versus facing towards an inside of the projected boundary;
comparing the determined ratio to a threshold; and
classifying the polygon as a hole in response to the threshold being met or exceeded.

5 . The method of claim 2 wherein determining an area of the hole comprises:
filling the hole with a hole mesh; and
calculating the area of the hole mesh.

6 . The method of claim 5 wherein filling the hole with a hole mesh utilizes only vertices of the hole boundary edges.

7 . The method of claim 1 and further comprising:
determining respective areas of multiple holes in the mesh; and
calculating a percentage of hole area to mesh area.

8 . The method of claim 1 wherein identifying boundary edges in the mesh comprises determining edges that have only one adjacent mesh face.

9 . The method of claim 1 wherein obtaining a mesh comprises:
scanning the environment; and
providing feedback regarding the hole.

10 . The method of claim 1 wherein determining an area of the hole comprises:
dividing the hole into multiple holes;
finding hole filling polygons to fill each hole; and
adding the area of the hole filling polygons.

11 . The method of claim 10 wherein finding hole filling polygons comprises:
recursively finding sets of polygons for each hole; and
determining the set of polygons having a smallest area for each hole.

12 . The method of claim 11 wherein filling the hole with a hole mesh utilizes only vertices of the hole polygon edges.

13 . The method of claim 10 wherein dividing the holes into multiple holes comprises:
identifying vertices of the hole;
identifying a minimal distance between two opposing vertices of the hole; and
dividing the hole based on the two opposing vertices having the minimal distance.

14 . A machine-readable storage device having instructions for execution by a processor of a machine to cause the processor to perform operations to perform a method, the operations comprising:
obtaining a mesh representative of a scanned environment; identifying boundary edges in the mesh; grouping the boundary edges into ordered, connected three-dimensional closed non-intersecting polygons; classifying a polygon as a hole; and determining an area of the hole.

15 . The device of claim 14 wherein grouping the boundary edges includes operations comprising:
projecting the connected three-dimensional polygons onto a two-dimensional plane; and
removing self-intersecting polygons.

16 . The device of claim 15 wherein determining an area of the hole comprises:
filling the hole with a hole mesh; and
calculating the area of the hole mesh.

17 . The device of claim 14 wherein determining an area of the hole includes operations comprising:
dividing the hole into multiple holes;
finding hole filling polygons to fill each hole; and
adding the area of the hole filling polygons.

18 . The device of claim 17 wherein finding hole filling polygons includes operations comprising:
recursively finding sets of polygons for each hole; and
determining the set of polygons having a smallest area for each hole.

19 . The device of claim 17 wherein dividing the holes into multiple holes includes operations comprising:
identifying vertices of the hole;
identifying a minimal distance between two opposing vertices of the hole; and
dividing the hole based on the two opposing vertices having the minimal distance.

20 . A device comprising:
a processor; and a memory device coupled to the processor and having a program stored thereon for execution by the processor to perform operations comprising:
obtaining a mesh representative of a scanned environment;
identifying boundary edges in the mesh;
grouping the boundary edges into ordered, connected three-dimensional closed non-intersecting polygons;
classifying a polygon as a hole; and
determining an area of the hole.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Pekelny Yuri
• Joss Matthew Alexander
• Burca Vlad Stefan
• Elenzil Orion Wilson

Classifications

• G06T2207/20021

  Dividing image into blocks, subimages or windows · CPC title

• G06T17/20

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

• G06T7/13 Primary

  Edge detection · CPC title

• G06T7/12 Primary

  Edge-based segmentation · CPC title

• G06T2207/10028

  Range image; Depth image; 3D point clouds · CPC title