Constructing a conforming voronoi mesh for an arbitrarily-shaped enclosed geometric domain

1. A computing system comprising:

a processor; and

memory storing instructions that, when executed by the processor, cause the processor to perform acts comprising:

receiving a computer-implemented definition of an enclosed geometric domain, wherein the enclosed geometric domain is three-dimensional and includes a sharp corner;

determining locations of seeds for the enclosed geometric domain, wherein determining the locations of the seeds comprises:

identifying the sharp corner of the enclosed geometric domain;

centering a first sphere having a first radius over the sharp corner of the enclosed geometric domain, wherein the first radius is selected such that the first sphere intersects only edges that form the sharp corner;

selecting an edge of the enclosed geometric domain, wherein the edge is partially covered by the first sphere;

sampling a point from the edge, wherein the point is uncovered by the first sphere;

placing a second sphere having a second radius centered on the point from the edge, wherein the second radius is selected such that the second sphere intersects no edges of the enclosed geometric domain other than the selected edge, wherein a location of a seed in the seeds is determined based upon the first sphere and the second sphere;

selecting a surface of the enclosed geometric domain, wherein the surface is partially covered by the first sphere and the second sphere;

sampling a second point, the second point sampled from the surface, wherein the point is uncovered by the first sphere or the second sphere;

centering a third sphere having a third radius on the second point, wherein the third radius is selected such that the third sphere does not intersect any edges or sharp corners of the enclosed geometric domain, where the first sphere, the second sphere, and the third sphere intersect at two intersection points; and

labeling the two intersection points as being a subset of the seeds for the enclosed geometric domain

decomposing the enclosed geometric domain into a conforming Voronoi mesh based on the locations of the seeds, wherein the conforming Voronoi mesh comprises Voronoi cells, and further wherein the conforming Voronoi mesh is bounded by the enclosed domain; and

performing a numerical simulation to generate simulation results, wherein the numerical simulation is based on at least one Voronoi cell in the Voronoi cells of the conforming Voronoi mesh.

2. The computing system of claim 1 , wherein determining the locations of the seeds for the enclosed geometric domain further comprises:

repeating the acts of identifying and centering for each sharp corner of the enclosed geometric domain, wherein spheres centered over sharp corners are prohibited from intersecting one another.

3. The computing system of claim 2 , wherein determining the locations of the seeds for the enclosed geometric domain further comprises repeating the acts of selecting, sampling, and placing until all points of all edges of the enclosed geometric domain are covered by at least one sphere.

4. The computing system of claim 1 , wherein determining the locations of the seeds for the enclosed geometric domain further comprises repeating the acts of selecting, sampling, centering, and labeling, until all points of all surfaces of the enclosed geometric domain are covered by at least one sphere.

5. The computing system of claim 4 , wherein determining the locations of the seeds for the enclosed geometric domain further comprises:

sampling a third point from an interior of the enclosed geometric domain;

determining that the third point is at least a threshold distance from every other point labeled as being included in the seeds; and

responsive to determining that the third point is at least the threshold distance from every other point labeled as being included in the seeds, labeling the third point as also being included in the seeds.

6. The computing system of claim 5 , wherein determining the locations of the seeds for the enclosed geometric domain further comprises repeating the acts of sampling, determining, and labeling until each point in the interior of the enclosed domain is within a threshold distance from a point labeled as being included in the seeds.

7. The computing system of claim 4 , wherein determining the locations of the seeds for the enclosed geometric domain further comprises:

determining that the third sphere having the third radius covers a point of intersection of three other spheres;

identifying a third point, the third point being on the surface and covered by the third sphere, wherein a fourth sphere having a fourth radius and that is centered at the identified point does not cover a point of intersection of three other spheres, and wherein the fourth sphere having the fourth radius and that is centered at the identified point covers all points on the surface that are covered solely by the third sphere; and

responsive to identifying the point, replacing the third sphere with the fourth sphere.

8. The computing system of claim 4 , wherein determining the locations of the seeds for the enclosed geometric domain further comprises:

sampling a third point from an interior of the enclosed geometric domain;

determining that the third point satisfies a boundary condition, wherein the boundary condition specifies that a distance between the third point and a first surface of the enclosed geometric domain is greater than a distance between the first surface and at least one seed in the seeds; and

responsive to determining that the third point satisfies the boundary condition, labeling the third point as also being included in the seeds.

9. A method performed by a computing device, the method comprising:

receiving, at the computing device, a computer-implemented definition of an enclosed geometric domain, wherein the enclosed geometric domain is three-dimensional and includes a sharp corner;

determining locations of seeds for the enclosed geometric domain, wherein determining the locations of the seeds comprises:

identifying the sharp corner of the enclosed geometric domain;

centering a first sphere having a first radius over the sharp corner of the enclosed geometric domain, wherein the first radius is selected such that the first sphere intersects only edges that form the sharp corner;

selecting an edge of the enclosed geometric domain, wherein the edge is partially covered by the first sphere;

sampling a point from the edge, wherein the point is uncovered by the first sphere;

placing a second sphere having a second radius centered on the point from the edge, wherein the second radius is selected such that the second sphere intersects no edges of the enclosed geometric domain other than the selected edge, wherein a location of a seed in the seeds is determined based upon the first sphere and the second sphere;

selecting a surface of the enclosed geometric domain, wherein the surface is partially covered by the first sphere and the second sphere;

sampling a second point, the second point sampled from the surface, wherein the point is uncovered by the first sphere or the second sphere;

centering a third sphere having a third radius on the second point, wherein the third radius is selected such that the third sphere does not intersect any edges or sharp corners of the enclosed geometric domain, where the first sphere, the second sphere, and the third sphere intersect at two intersection points; and

labeling the two intersection points as being a subset of the seeds for the enclosed geometric domain;

decomposing the enclosed geometric domain into a conforming Voronoi mesh based on the locations of the seeds, wherein the conforming Voronoi mesh comprises Voronoi cells, and further wherein the conforming Voronoi mesh is bounded by the enclosed geometric domain; and

performing a numerical simulation to generate simulation results, wherein the numerical simulation is based on at least one Voronoi cell in the Voronoi cells of the conforming Voronoi mesh.

10. The method of claim 9 , wherein determining the locations of the seeds for the enclosed geometric domain further comprises:

repeating the acts of identifying and centering for each sharp corner of the enclosed geometric domain, wherein spheres placed over sharp corners are prohibited from intersecting one another.

11. The method of claim 9 , wherein determining the locations of the seeds for the enclosed geometric domain further comprises repeating the acts of selecting, sampling, and placing until all points of all edges of the enclosed domain are covered by at least one sphere.

12. The method of claim 9 , wherein determining the locations of the seeds for the enclosed geometric domain further comprises repeating the acts of selecting, sampling, centering, and labeling until all points of all surfaces of the enclosed domain are covered by at least one sphere.

13. The method of claim 12 , wherein determining the locations of the seeds for the enclosed geometric domain further comprises:

sampling a point from an interior of the enclosed geometric domain;

determining that the point is at least a threshold distance from every other point labeled as being included in the seeds; and

responsive to determining that the point is at least the threshold distance from every other point labeled as being included in the seeds, labeling the point as being included in the seeds.

14. The method of claim 13 , wherein determining the locations of the seeds for the enclosed geometric domain further comprises repeating the acts of sampling, determining, and labeling until each point in the interior of the enclosed geometric domain is within a threshold distance from a point labeled as being included in the seeds.

15. The method of claim 12 , wherein determining the locations of the seeds for the enclosed geometric domain further comprises:

sampling a third point from an interior of the enclosed geometric domain;

determining that the third point satisfies a boundary condition, wherein the boundary condition specifies that a distance between the third point and a first surface of the enclosed geometric domain is greater than a distance between the first surface and at least one seed in the seeds; and

responsive to determining that the third point satisfies the boundary condition, labeling the third point as also being included in the seeds.

16. A computer-readable storage medium comprising instructions that, when executed by a processor, cause the processor to perform acts comprising:

receiving a computer-implemented definition of an enclosed geometric domain, wherein the enclosed geometric domain is three-dimensional and includes a sharp corner;

determining locations of seeds for the enclosed geometric domain, wherein determining the locations of the seeds comprises:

identifying the sharp corner of the enclosed geometric domain;

centering a first sphere having a first radius over the sharp corner of the enclosed geometric domain, wherein the first radius is selected such that the first sphere intersects only edges that form the sharp corner;

selecting an edge of the enclosed geometric domain, wherein the edge is partially covered by the first sphere;

sampling a point from the edge, wherein the point is uncovered by the first sphere;

placing a second sphere having a second radius centered on the point from the edge, wherein the second radius is selected such that the second sphere intersects no edges of the enclosed geometric domain other than the selected edge, wherein a location of a seed in the seeds is determined based upon the first sphere and the second sphere;

selecting a surface of the enclosed geometric domain, wherein the surface is partially covered by the first sphere and the second sphere;

sampling a second point, the second point sampled from the surface, wherein the point is uncovered by the first sphere or the second sphere;

centering a third sphere having a third radius on the second point, wherein the third radius is selected such that the third sphere does not intersect any edges or sharp corners of the enclosed geometric domain, wherein the first sphere, the second sphere, and the third sphere intersect at two intersection points; and

labeling the two intersection points as being a subset of the seeds for the enclosed geometric domain;

decomposing the enclosed geometric domain into a conforming Voronoi mesh based on the locations of the seeds, wherein the conforming Voronoi mesh comprises Voronoi cells, and further wherein the conforming Voronoi mesh is bounded by the enclosed geometric domain; and

performing a numerical simulation to generate simulation results, wherein the numerical simulation is based on at least one Voronoi cell in the Voronoi cells of the conforming Voronoi mesh.

17. The computer-readable storage medium of claim 16 , wherein determining the locations of the seeds for the enclosed geometric domain further comprises:

sampling a third point from an interior of the enclosed geometric domain;

determining that the third point satisfies a boundary condition, wherein the boundary condition specifies that a distance between the third point and a first surface of the enclosed geometric domain is greater than a distance between the first surface and at least one seed in the seeds; and

responsive to determining that the third point satisfies the boundary condition, labeling the third point as also being included in the seeds.