Shape Preserving Mesh Simplification
AssigneeGoogle Inc.
InventorXiaolin Wei
Life of this patent
Estimating the term…
Abstract
Systems and methods for simplifying a three-dimensional mesh providing a three-dimensional model, such as a three-dimensional model of a cityscape, are provided. In particular, mesh simplification techniques can preserve important structural shapes in the original three-dimensional mesh. Important features in a representation of a city scene or other scene can be represented by structural edges (e.g. building outlines, bridges, curved structures such as curved highway overpasses, etc.). These structural edges can be detected and a representation of the structural edges can be constructed in the mesh. The mesh can then be simplified using the structural edges as high-level simplification criterion such that the structural edges are preserved during simplification.
Claims20
A computer-implemented method for mesh simplification of a three-dimensional polygon mesh, the method comprising:
- identifying, with a computing device, a structural edge in the three-dimensional polygon mesh using plane detection;
- constructing, with the computing device, a sharp edge in the three-dimensional polygon mesh at the structural edge, the sharp edge comprising a straight chain of connected vertices in the three-dimensional polygon mesh;
- identifying, with the computing device, a candidate edge for edge collapse, the candidate edge being associated with a first vertex and a second vertex;
- determining, with the computing device, an error for collapsing the candidate edge to a new vertex, the error determined based at least in part on the location of the first vertex and the second vertex relative to the sharp edge;
- and
- collapsing, with the computing device, one or more edges in the three-dimensional polygon mesh based at least in part on the error.
A computing system comprising one or more processors and one or more tangible computer-readable media, the system further comprising:
- a sharp edge construction module implemented by the one or more processors, the sharp edge construction module configured to identify a structural edge in a three-dimensional polygon mesh providing a representation of a geographic area using plane detection, the sharp edge construction module further configured to construct a sharp edge in the three-dimensional polygon mesh at a detected plane intersection associated with the structural edge, the sharp edge comprising a straight chain of connected vertices in the three-dimensional polygon mesh;
- a filtering module implemented by the one or more processors, the filtering module configured to filter the sharp edge based on one or more of length of the sharp edge, height of the sharp edge, or areas of planes corresponding to the sharp edge;
- and
- a mesh simplification module implemented by the one or more processors, the mesh simplification module configured to identify a candidate edge for edge collapse, the candidate edge being associated with a first vertex and a second vertex, the mesh simplification module further configured to determine an error for collapsing the candidate edge to a new vertex, the error determined based at least in part on the location of the first vertex and the second vertex relative to the sharp edge, the mesh simplification module further configured to collapse one or more edges in the three-dimensional polygon mesh based at least in part on the error.
A computer program product comprising a tangible non-transitory computer-readable medium storing computer-readable instructions for execution by one or more processors, causing the one or more processors to perform operations, the operations comprising:
- identifying a structural edge in the three-dimensional polygon mesh representative of a geographic area using plane detection;
- constructing a sharp edge in the three-dimensional polygon mesh at a detected plane intersection associated with the structural edge, the sharp edge comprising a straight chain of connected vertices in the three-dimensional polygon mesh;
- identifying a candidate edge for edge collapse, the candidate edge being associated with a first vertex and a second vertex;
- determining an error for collapsing the candidate edge to a new vertex, the error based at least in part on the location of the first vertex and the second vertex relative to the sharp edge;
- and
- collapsing one or more edges in the three-dimensional polygon mesh based at least in part on the error.
Dependencies are inferred from the claim text.