Surface mesh self-intersection detection

1 . A method comprising:

obtaining, by a three-dimensional modeling program, (i) a surface mesh comprising vertices and edges that define triangles that approximate a surface of a three-dimensional model of a three-dimensional object, and (ii) a Delaunay diagram of the vertices of the surface mesh, wherein the Delaunay diagram comprises a volumetric mesh comprising tetrahedrons having vertices at the vertices of the surface mesh;

determining, by the three-dimensional modeling program and using the Delaunay diagram, data indicating at least one intersection among the triangles of the surface mesh;

causing a refinement of the surface mesh based on the data indicating the at least one intersection, wherein the refinement removes the at least one intersection among the triangles of the surface mesh; and

rendering, on a display device, an updated surface mesh generated by the refinement;

wherein determining, using the Delaunay diagram, the data indicating the at least one intersection among the triangles of the surface mesh comprises:

for each edge of the edges of the surface mesh, determining whether the edge is not an edge of any of the tetrahedrons in the Delaunay diagram; and

in response to determining that the edge is not in the Delaunay diagram, determining at least one triangle among the triangles of the surface mesh that intersects with the edge.

2 . The method of claim 1 , wherein the obtaining comprises generating the surface mesh from the three-dimensional model of the three-dimensional object.

3 . The method of claim 1 , wherein the obtaining comprises generating the Delaunay diagram from the vertices of the surface mesh using Delaunay tetrahedrization algorithm.

4 . The method of claim 1 , wherein the surface of the three-dimensional model comprises faces, wherein the data indicating the at least one intersection among the triangles of the surface mesh comprises data identifying at least one face of the surface of the three-dimensional model that corresponds to the at least one triangle that intersects with the edge.

5 . The method of claim 1 , wherein determining the at least one triangle among the triangles of the surface mesh that intersects with the edge comprises:

determining a triangular surface of a tetrahedron in the volumetric mesh of the Delaunay diagram that intersects with the edge;

determining, from the triangles of the surface mesh, a set of candidate triangles, wherein each candidate triangle shares at least one vertex with the triangular surface; and

determining, from the set of candidate triangles, the at least one triangle that intersects with the edge.

6 . The method of claim 1 , wherein the causing comprises:

removing the at least one intersection among the triangles of the surface mesh by generating the updated surface mesh, comprising:

generating, a respective updated portion of the updated surface mesh for each face of the surface of the three-dimensional model where the at least one intersection among the triangles of the surface mesh is located, wherein an average mesh size for each updated portion of the updated surface mesh is smaller than an average mesh size for the portion of the surface mesh before the update.

7 . The method of claim 6 , further comprising:

generating an updated volumetric mesh of the three-dimensional model of the three-dimensional object using the updated surface mesh.

8 . The method of claim 7 , further comprising:

providing the updated volumetric mesh of the three-dimensional model for numerical simulation of the three-dimensional object.

9 . The method of claim 7 , wherein generating the updated volumetric mesh comprises generating an updated Delaunay diagram from vertices of the updated surface mesh using Delaunay tetrahedrization algorithm, wherein the updated Delaunay diagram comprises the updated volumetric mesh.

10 . The method of claim 6 , further comprising:

rendering the updated surface mesh and/or an updated volumetric mesh of the three-dimensional model of the three-dimensional object generated using the updated surface mesh to an animation document for a digital projector.

11 . The method of claim 1 , comprising iteratively generating the refinement of the surface mesh, wherein the iteratively generating comprises, for each iteration:

obtaining an initial surface mesh at a current iteration, wherein the initial surface mesh at the current iteration is an updated surface mesh generated in a previous iteration;

generating a Delaunay diagram at the current iteration from vertices of the initial surface mesh using Delaunay tetrahedrization algorithm;

for each edge of the edges of the initial surface mesh, determining whether the edge is not an edge of any of the tetrahedrons in the Delaunay diagram at the current iteration;

in response to determining that the edge is not in the Delaunay diagram at the current iteration, generating data identifying at least one face of the surface of the three-dimensional model that needs the refinement, wherein the generating comprises:

determining a triangular surface of a tetrahedron in the volumetric mesh of Delaunay diagram at the current iteration that intersects with the edge;

determining, from the triangles of the initial surface mesh, a set of candidate triangles, wherein each candidate triangle shares at least one vertex with the triangular surface;

identifying, from the set of candidate triangles, one or more candidate triangles that intersect with the edge;

identifying the at least one face of the surface of the three-dimensional model that corresponds to the one or more candidate triangles that intersect with the edge; and

adding data identifying the at least one face to a refinement set of faces comprising one or more faces that need the refinement; and

generating an updated surface mesh for the iteration for each face in the refinement set of faces, wherein an average mesh size for the updated surface mesh is smaller than an average mesh size for the surface mesh before update.

12 . The method of claim 11 , wherein the iteratively generating comprises, for a last iteration:

for each edge of edges of a second initial surface mesh at a current iteration, determining whether the edge is not an edge of any of the tetrahedrons in a Delaunay diagram at the current iteration; and

in response to determining that each edge of the second initial surface mesh is an edge of a tetrahedron in the Delaunay diagram at the current iteration, determining that the second initial surface mesh is a final updated surface mesh.

13 . The method of claim 11 , wherein generating the updated surface mesh for the iteration for each face in the refinement set of faces comprises:

computing an average mesh size for each of two or more faces in the refinement set of faces;

computing, using the average mesh sizes, a minimum average mesh size among the two or more faces in the refinement set of faces;

determining, using the minimum average mesh size, a new average mesh size for the two or more faces in the refinement set of faces; and

generating, for each face in the two or more faces in the refinement set of faces, the updated surface mesh for the iteration, wherein the average mesh size for the updated surface mesh equals to the new average mesh size.

14 . A system comprising:

a non-transitory storage medium having instructions of a three-dimensional modeling program stored thereon; and

one or more data processors configured to run the instructions of the three-dimensional modeling program to perform operations specified by the instructions of the three-dimensional modeling program;

wherein the operations comprise:

obtaining (i) a surface mesh comprising vertices and edges that define triangles that approximate a surface of a three-dimensional model of a three-dimensional object, and (ii) a Delaunay diagram of the vertices of the surface mesh, wherein the Delaunay diagram comprises a volumetric mesh comprising tetrahedrons having vertices at the vertices of the surface mesh;

determining, using the Delaunay diagram, data indicating at least one intersection among the triangles of the surface mesh;

causing a refinement of the surface mesh based on the data indicating the at least one intersection, wherein the refinement removes the at least one intersection among the triangles of the surface mesh; and

rendering, on a display device, an updated surface mesh generated by the refinement;

wherein determining, using the Delaunay diagram, the data indicating the at least one intersection among the triangles of the surface mesh comprises:

for each edge of the edges of the surface mesh, determining whether the edge is not an edge of any of the tetrahedrons in the Delaunay diagram; and

in response to determining that the edge is not in the Delaunay diagram, determining at least one triangle among the triangles of the surface mesh that intersects with the edge.

15 . The system of claim 14 , wherein the obtaining comprises generating the surface mesh from the three-dimensional model of the three-dimensional object.

16 . The system of claim 14 , wherein the obtaining comprises generating the Delaunay diagram from the vertices of the surface mesh using Delaunay tetrahedrization algorithm.

17 . The system of claim 14 , wherein the surface of the three-dimensional model comprises faces, wherein the data indicating the at least one intersection among the triangles of the surface mesh comprises data identifying at least one face of the surface of the three-dimensional model that corresponds to the at least one triangle that intersects with the edge.

18 . The system of claim 14 , wherein determining the at least one triangle among the triangles of the surface mesh that intersects with the edge comprises:

determining a triangular surface of a tetrahedron in the volumetric mesh of the Delaunay diagram that intersects with the edge;

determining, from the triangles of the surface mesh, a set of candidate triangles, wherein each candidate triangle shares at least one vertex with the triangular surface; and

determining, from the set of candidate triangles, the at least one triangle that intersects with the edge.

19 . The system of claim 14 , wherein the causing comprises:

removing the at least one intersection among the triangles of the surface mesh by generating the updated surface mesh, comprising:

generating, a respective updated portion of the updated surface mesh for each face of the surface of the three-dimensional model where the at least one intersection among the triangles of the surface mesh is located, wherein an average mesh size for each updated portion of the updated surface mesh is smaller than an average mesh size for the portion of the surface mesh before the update.

20 . A non-transitory computer-readable medium encoding instructions operable to cause data processing apparatus to perform operations comprising:

obtaining (i) a surface mesh comprising vertices and edges that define triangles that approximate a surface of a three-dimensional model of a three-dimensional object, and (ii) a Delaunay diagram of the vertices of the surface mesh, wherein the Delaunay diagram comprises a volumetric mesh comprising tetrahedrons having vertices at the vertices of the surface mesh;

determining, using the Delaunay diagram, data indicating at least one intersection among the triangles of the surface mesh;

causing a refinement of the surface mesh based on the data indicating the at least one intersection, wherein the refinement removes the at least one intersection among the triangles of the surface mesh; and

rendering, on a display device, an updated surface mesh generated by the refinement;

wherein determining, using the Delaunay diagram, the data indicating the at least one intersection among the triangles of the surface mesh comprises:

for each edge of the edges of the surface mesh, determining whether the edge is not an edge of any of the tetrahedrons in the Delaunay diagram; and

in response to determining that the edge is not in the Delaunay diagram, determining at least one triangle among the triangles of the surface mesh that intersects with the edge.