Inferring quality in point cloud-based three-dimensional objects using topographical data analysis

1. A system, comprising:

a computing device comprising a processor and a memory; and

machine-readable instructions stored in the memory that, when executed by the processor, cause the computing device to at least:

generate a first graph representing a three-dimensional model, each vertex in the first graph representing a respective connected component within a layer of the three-dimensional model and each edge in the first graph representing a connection between two respective connected components within two respective layers of the three-dimensional model;

generate a second graph representing negative space associated with the three-dimensional model, each vertex in the second graph representing a connected component of a negative space region within the layer of the three-dimensional model and each edge in the second graph representing a connection between two respective connected components with two respective layers of the three-dimensional model;

apply a persistent homology analysis to the first graph to determine whether a hole or tunnel exists in each vertex of the first graph; and

identify an error with the three-dimensional model based at least in part on the first graph, the second graph, and the persistent homology analysis.

2. The system of claim 1 , wherein the machine-readable instructions further cause the computing device to repair the error.

3. The system of claim 2 , wherein the machine-readable instructions that cause the computing device to repair the error further cause the computing device to at least:

identify a two-dimensional, non-convex polygon that represents the hole or tunnel;

triangulate an interior of the non-convex polygon; and

add additional data points within the interior of the non-convex polygon based at least in part on triangulating the interior of the non-convex polygon.

4. The system of claim 1 , wherein the machine-readable instructions that cause the computing device to generate the first graph further cause the computing device to at least:

insert a plurality of points into the negative space region of the three-dimensional model;

separate the three-dimensional model into a series of layers, each layer in the series of layers having a predefined width;

identify a set of connected components in each layer in the series of layers, each connected component in the set of connected components representing at least a portion of the plurality of points in the negative space region of the three-dimensional model; and

for each connected component in the set of components in a respective layer, identify a collection of connected components that touch the connected component.

5. The system of claim 1 , wherein the machine-readable instructions that cause the computing device to generate the first graph further cause the computing device to at least:

separate the three-dimensional model into a series of layers, each layer in the series of layers having a predefined width;

identify a set of connected components in each layer in the series of layers; and

for each connected component in the set of components in a respective layer, identify a collection of connected components that touch the connected component.

6. The system of claim 5 , wherein machine readable instructions further cause the computing device to at least:

receive an input from a user interface specifying the predefined width, the predefined width being substantially equal to a z-axis resolution of a three-dimensional printer; and

set the predefined width equal to the input specifying the predefined width.

7. A method, comprising:

generating a first graph representing a three-dimensional model, each vertex in the first graph representing a respective connected component within a layer of the three-dimensional model and each edge in the first graph representing a connection between two respective connected components within two respective layers of the three-dimensional model;

generating a second graph representing negative space associated with the three-dimensional model, each vertex in the second graph representing a connected component of a negative space region within the layer of the three-dimensional model and each edge in the second graph representing a connection between two respective connected components with two respective layers of the three-dimensional model;

applying a persistent homology analysis to the first graph to determine whether a hole or tunnel exists in each vertex of the first graph; and

identifying an error with the three-dimensional model based at least in part on the first graph, the second graph, and the persistent homology analysis.

8. The method of claim 7 , further comprising repairing the error in the three-dimensional model.

9. The method of claim 8 , wherein repairing the error in the three-dimensional model further comprises:

identifying a two-dimensional, non-convex polygon that represents the hole or tunnel;

triangulating an interior of the non-convex polygon; and

adding additional data points within the interior of the non-convex polygon based at least in part on triangulating the interior of the non-convex polygon.

10. The method of claim 7 , wherein generating the second graph further comprises:

inserting a plurality of points into the negative space region of the three-dimensional model;

separating the three-dimensional model into a series of layers, each layer in the series of layers having a predefined width;

identifying a set of connected components in each layer in the series of layers, each connected component in the set of connected components representing at least a portion of the plurality of points in the negative space region of the three-dimensional model; and

for each connected component in the set of components in a respective layer, identifying a collection of connected components that touch the connected component.

11. The method of claim 7 , wherein generating the first graph further comprises:

separating the three-dimensional model into a series of layers, each layer in the series of layers having a predefined width;

identifying a set of connected components in each layer in the series of layers; and

for each connected component in the set of components in a respective layer, identifying a collection of connected components that touch the connected component.

12. The method of claim 11 , further comprising:

receiving an input from a user interface specifying the predefined width, the predefined width being substantially equal to a z-axis resolution of a three-dimensional printer; and

setting the predefined width equal to the input specifying the predefined width.

13. A non-transitory computer-readable medium comprising machine-readable instructions that, when executed by the processor, cause the computing device to at least:

generate a first graph representing a three-dimensional model, each vertex in the first graph representing a respective connected component within a layer of the three-dimensional model and each edge in the first graph representing a connection between two respective connected components within two respective layers of the three-dimensional model;

generate a second graph representing negative space associated with the three-dimensional model, each vertex in the second graph representing a connected component of a negative space region within the layer of the three-dimensional model and each edge in the second graph representing a connection between two respective connected components with two respective layers of the three-dimensional model;

apply a persistent homology analysis to the first graph to determine whether a hole or tunnel exists in each vertex of the first graph; and

identify an error with the three-dimensional model based at least in part on the first graph, the second graph, and the persistent homology analysis.

14. The non-transitory computer-readable medium of claim 13 , wherein the machine-readable instructions further cause the computing device to repair the error.

15. The non-transitory computer-readable medium of claim 14

wherein the machine-readable instructions that cause the computing device to repair the error further cause the computing device to at least:

identify a two-dimensional, non-convex polygon that represents the hole or tunnel;

triangulate an interior of the non-convex polygon; and

add additional data points within the interior of the non-convex polygon based at least in part on triangulating the interior of the non-convex polygon.

16. The non-transitory computer-readable medium of claim 13 , wherein the machine-readable instructions that cause the computing device to generate the first graph further cause the computing device to at least:

insert a plurality of points into the negative space region of the three-dimensional model;

separate the three-dimensional model into a series of layers, each layer in the series of layers having a predefined width;

identify a set of connected components in each layer in the series of layers, each connected component in the set of connected components representing at least a portion of the plurality of points in the negative space region of the three-dimensional model; and

for each connected component in the set of components in a respective layer, identify a collection of connected components that touch the connected component.

17. The non-transitory computer-readable medium of claim 13 , wherein the machine-readable instructions that cause the computing device to generate the first graph further cause the computing device to at least:

separate the three-dimensional model into a series of layers, each layer in the series of layers having a predefined width;

identify a set of connected components in each layer in the series of layers; and

for each connected component in the set of components in a respective layer, identify a collection of connected components that touch the connected component.

18. The non-transitory computer-readable medium of claim 17 , wherein the machine-readable instructions further cause the computing device to at least:

receive an input from a user interface specifying the predefined width, the predefined width being substantially equal to a z-axis resolution of a three-dimensional printer; and

set the predefined width equal to the input specifying the predefined width.