Surface simplification based on offset tiles

• US 8,884,955 B1
• Filed: 05/04/2012
• Issued: 11/11/2014
• Est. Priority Date: 05/04/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Hsu, Stephen Charles
• Primary Examiner(s): Tung, Kee M
• Assistant Examiner(s): Chin, Michelle
• Application Number:
  US13/464,612
• Time in Patent Office: 921 Days
• US Class Current: 345/421
• CPC Class Codes: G06T 17/205 Re-meshing

Abstract

An exemplary method for simplifying the geometry of a three-dimensional mesh includes dividing a first three-dimensional mesh into a first plurality of tiles along initial boundary lines. The method also includes for at least one tile of the first plurality of tiles, reducing the vertices toward a center of the tile while maintaining vertices along a perimeter of the tile, and assembling the first plurality of tiles to determine a second three-dimensional mesh. The method also includes dividing the second three-dimensional mesh into a second plurality of tiles along boundary lines offset from the initial boundary lines. The method further includes for at least one tile of the second plurality of tiles, reducing the vertices toward a center of the tile while maintaining vertices along a perimeter of the tile, and assembling the second plurality of tiles to determine a simplified three-dimensional mesh.

Claims

1. A method for simplifying the geometry of a three-dimensional mesh, comprising:

(a) dividing a first three-dimensional mesh into a first plurality of tiles along initial boundary lines, each tile comprising a region of the first three-dimensional mesh;

(b) for at least one tile of the first plurality of tiles, reducing a number of vertices included within an interior of the entire tile to simplify the mesh included in the tile while maintaining vertices along a perimeter of the tile;

(c) after the reducing (b), assembling the first plurality of tiles to determine a second three-dimensional mesh;

(d) dividing the second three-dimensional mesh into a second plurality of tiles along boundary lines offset from the initial boundary lines, each tile comprising a region of the first three-dimensional mesh;

(e) for at least one tile of the second plurality of tiles, reducing a number of vertices included within an interior of the entire tile while maintaining vertices along a perimeter of the tile; and

(f) after the reducing (e), assembling the second plurality of tiles to determine a simplified three-dimensional mesh,

wherein the initial boundary lines of the first plurality of tiles are diagonally offset by a fraction of a tile from the boundary lines of the second plurality tiles.

2. The method of claim 1, whereby the two step reducing of (b) and (e) causes the simplified three-dimensional mesh to be simplified continuously.

3. The method of claim 1, wherein the reducing (b) comprises using a quadric-based simplification algorithm.

4. The method of claim 1, wherein the reducing (e) comprises using a quadric-based simplification algorithm.

5. The method of claim 1, further comprising

(g) before the reducing (b), determining the boundary lines offset from the initial boundary lines,

wherein the reducing (b) is constrained to not form faces straddling the boundary lines offset from the initial boundary lines.

6. The method of claim 5, wherein the tiles in the first and second plurality of tiles are rectangular tiles of a same size.

7. The method of claim 1, wherein the tiles are quadrilateral tiles.

8. The method of claim 1, wherein the dividing (a) comprises dividing the first three-dimensional mesh into the first plurality of tiles along straight lines.

9. The method of claim 1, wherein the dividing (a) comprises dividing the first three-dimensional mesh into the first plurality of tiles along crooked lines.

10. The method of claim 1, wherein the reducing (b) comprises reducing the vertices of a first tile and reducing the vertices of a second tile in parallel, the first and second tiles being in the first plurality of tiles.

11. A system for simplifying the geometry of a three-dimensional mesh, comprising:

a tile grouper configured to;

(i) divide a first three-dimensional mesh into a first plurality of tiles along initial boundary lines, each tile comprising a region of the first three-dimensional mesh; and

(ii) divide a second three-dimensional mesh into a second plurality of tiles along boundary lines offset from the initial boundary lines, each tile comprising a region of the first three-dimensional mesh;

a vertex reducer configured to;

(i) for at least one tile of the first plurality of tiles, reduce a number of vertices included within an interior of the entire the to simplify the mesh included in the tile while maintaining vertices along a perimeter of the tile; and

(ii) for at least one the of the second plurality of tiles, reduce a number of vertices included within an interior of the entire tile while maintaining vertices along a perimeter of the tile; and

an assembler configured to;

(i) assemble the first plurality of tiles to determine the second three-dimensional mesh; and

(ii) assemble the second plurality of tiles to determine a simplified three-dimensional mesh,

wherein the initial boundary lines of the first plurality of tiles are diagonally offset by a fraction of a tile from the boundary lines of the second plurality tiles.

12. The system of claim 11, wherein when the vertex reducer reduces the vertices the vertex reducer is configured to use a quadric-based simplification algorithm.

13. The system of claim 11, wherein before the vertex reducer reduces the tiles in the first plurality of tiles, the vertex reducer is configured to determine the boundary lines offset from the initial boundary lines and the vertex reducer is further configured to not form aces straddling the boundary lines offset from the initial boundary lines.

14. The system of claim 13, wherein the tiles in the first and second plurality of tiles are rectangular tiles of a same size.

15. The system of claim 11, wherein the tiles are quadrilateral tiles.

16. The system of claim 11, wherein the initial boundary lines are straight lines.

17. The system of claim 11, wherein the initial boundary lines are crooked lines.

18. The system of claim 11, wherein the vertex reducer is configured to reduce the vertices of a first tile and reduce the vertices of a second tile in parallel, the first and second tiles being in the first plurality of tiles.

19. An apparatus comprising at least one non-transitory computer readable storage medium encoding instructions thereon that, in response to execution by a computing device, cause the computing device to perform operations comprising:

(a) dividing a first three-dimensional mesh into a first plurality of tiles along initial boundary lines, each tile comprising a region of the first three-dimensional mesh;

(b) for at least one tile of the first plurality of tiles, reducing a number of vertices included within an interior of the entire tile to simplify the mesh included in the tile while maintaining vertices along a perimeter of the tile;

(c) after the reducing (b), assembling the first plurality of tiles to determine a second three-dimensional mesh;

(d) dividing the second three-dimensional mesh into a second plurality of tiles along boundary lines offset from the initial boundary lines, each tile comprising a region of the first three-dimensional mesh;

(e) for at least one tile of the second plurality of tiles, reducing a number of vertices included within an interior of the entire tile to simplify the mesh included in the tile while maintaining vertices along a perimeter of the tile; and

(f) after the reducing (e), assembling the second plurality of tiles to determine a simplified three-dimensional mesh,

wherein the initial boundary lines of the first plurality of tiles are diagonally offset by a fraction of a tile from the boundary lines of the second plurality tiles.