Mesh hole area detection

Patent metadata

Field	Value
Publication number	US-11763462-B2
Application number	US-202117156202-A
Country	US
Kind code	B2
Filing date	Jan 22, 2021
Priority date	Jan 22, 2021
Publication date	Sep 19, 2023
Grant date	Sep 19, 2023

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

The invention claimed is:

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 by projecting the connected three-dimensional polygons onto a two-dimensional plane and removing self-intersecting polygons; and
classifying a polygon as a hole by:
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.

2. The method of claim 1 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.

3. The method of claim 1 and further comprising determining an area of the hole by:
filling the hole with a hole mesh; and
calculating the area of the hole mesh.

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

5. 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.

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

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

8. 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 by:
dividing the hole into multiple holes;
finding hole filling polygons to fill each of the multiple holes, by recursively finding sets of polygons for each of the multiple holes and determining the sets of polygons having a smallest area for each of the multiple holes; and
adding the area of the hole filling polygons.

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

10. The method of claim 8 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.

11. 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 by projecting the connected three-dimensional polygons onto a two-dimensional plane and removing self-intersecting polygons; and
classifying a polygon as a hole by:
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.

12. The device of claim 11 and further comprising determining an area of the hole by:
filling the hole with a hole mesh; and
calculating the area of the hole mesh.

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

14. The device of claim 13 wherein finding hole filling polygons includes operations comprising:
recursively finding sets of polygons for each of the multiple holes; and
determining the sets of polygons having a smallest area for each of the multiple holes.

15. The device of claim 13 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.

Assignees

• Microsoft Technology Licensing Llc

Inventors

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

Classifications

• G06T7/12 Primary

  Edge-based segmentation · CPC title

• G06T7/13 Primary

  Edge detection · CPC title

• G06T7/62

  of area, perimeter, diameter or volume · CPC title

• G06T15/20

  Perspective computation · CPC title

• G06T17/20

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