Systems and methods for generating a large scale polygonal mesh

• US 9,390,556 B2
• Filed: 03/14/2014
• Issued: 07/12/2016
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Teledyne Digital Imaging, Inc. (Teledyne Technologies Incorporated)
• Original Assignee: Teledyne CARIS, Inc. (Teledyne Technologies Incorporated)
• Inventors: Masry, Mark
• Primary Examiner(s): McDowell, Jr., Maurice L
• Application Number:
  US14/212,580
• Publication Number:
  US 20140267262A1
• Time in Patent Office: 851 Days
• US Class Current: 1/1
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A polygonal mesh is generated from a collection of points that are organized for a mesh partition in accordance with a tile that includes one or more bins used to process the points that define the mesh. The resolution of the tile is related to the number of bins for the tile. The organization of the tiles in a partition of the mesh permits the mesh to be constructed with partitions that are independent of each other and that can be joined to form a continuous mesh. The resolution of the mesh can be dynamic with respect to the partitions due to the variable resolution assigned to each tile. Portions of the mesh for which points are not provided can be assigned finalization points to permit a continuous mesh to be constructed.

Claims

1. A computer implemented method for generating a polygonal mesh based on a collection of points, comprising:

generating, by a processor, a resolution map that includes a set of tiles, each tile having an associated resolution value representative of a density of the points located in the tile;

defining a binning grid for each tile based on the associated resolution value of the tile;

selecting one or more tiles for inclusion in a mesh partition for mesh generation;

assigning each point associated with each selected tile to a bin in the binning grid of a respective tile;

assigning a finalization point to each empty bin in the binning grid;

generating, by the processor, the mesh partition using points assigned to the bins in the selected tiles;

removing polygons from the mesh partition that include a finalization point at a vertex; and

outputting the mesh partition.

2. The method according to claim 1, further comprising receiving a mesh area input for generating the polygonal mesh.

3. The method according to claim 2, further comprising selecting all tiles that are at least partially within the mesh area input.

4. The method according to claim 3, further comprising generating each mesh partition that is at least partially within the mesh area input.

5. The method according to claim 4, further comprising generating each mesh partition using points located outside each respective mesh partition.

6. The method according to claim 5, wherein the points located outside each respective mesh partition are determined by the resolution value.

7. The method according to claim 1, wherein the resolution map is generated in accordance with one or more of a quadtree or an octree structure.

8. The method according to claim 1, wherein the mesh partition is one or more of a 2D or 3D mesh.

9. The method according to claim 1, further comprising generating the resolution map based on one or more of a characteristic of the collection of points or an attribute of the points.

10. The method according to claim 1, further comprising organizing and storing the collection of points in accordance with an associated spatial position of each point in the collection of points.

11. The method according to claim 1, further comprising:

loading the resolution map into memory; and

loading a subset of points from the collection of points into the memory, where the subset of points includes each point in the selected one or more tiles.

12. The method according to claim 1, wherein the resolution map is a hierarchical resolution map.

13. The method according to claim 1, further comprising combining the mesh partition with at least one additional independently triangulated mesh partition to generate a single, contiguous, non-self-intersecting mesh that covers an area represented by the collection of points.

14. A system for generating a polygonal mesh from a collection of points, comprising:

a processor communicatively coupled to a memory and operative to execute instructions retrieved from the memory to;

generate a resolution map that includes a set of tiles, each tile having an associated resolution value representative of a density of the points located in the tile;

define a binning grid for each tile based on the associated resolution value of the tile;

select one or more tiles for inclusion in a mesh partition for mesh generation;

assign each point associated with each selected tile to a bin in the binning grid of a respective tile;

assign a finalization point to each empty bin in the binning grid;

generate the mesh partition using points assigned to the bins in the selected tiles; and

removing polygons from the mesh partition that include a finalization point at a vertex.

15. The system according to claim 14, wherein the processor is further operative to receive a mesh area input for generating a mesh.

16. The system according to claim 15, wherein the processor is further operative to select all tiles that are at least partially within the mesh area input.

17. The system according to claim 16, wherein the processor is further operative to generate each mesh partition that is at least partially within the mesh area input.

18. The system according to claim 17, wherein the processor is further operative to generate each mesh partition using points located outside each respective mesh partition.

19. The system according to claim 14, wherein the processor is further operative to organize and store the collection of points in accordance with an associated spatial position of each point in the collection of points.

20. A computer implemented method for generating a mesh, comprising:

determining, by a processor, a mesh partition to be generated;

assigning a binning grid to at least one tile in the mesh partition;

assigning each point associated with the at least one tile to a bin in the binning grid;

assigning a finalization point to each empty bin in the binning grid;

generating, by the processor, the mesh using the points assigned to the bins in the binning grid; and

removing polygons from the mesh partition that include a finalization point at a vertex.

21. The method according to claim 20, further comprising receiving a mesh area input for generating the polygonal mesh,

wherein determining the mesh partition to be generated is based at least in part on the mesh area input.