Patent Publication Number: US-10776540-B1

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

Description:
STATEMENT OF GOVERNMENTAL INTEREST 
     This invention was made with Government support under Contract No. DE-NA0003525 awarded by the United States Department of Energy/National Nuclear Security Administration. The U.S. Government has certain rights in the invention. 
    
    
     BACKGROUND 
     Subdividing a geometric domain into polyhedral elements is desirable in numerous technical fields. For example, it is desirable to subdivide a geometric domain into polyhedral elements when performing a three-dimensional numerical simulation using polyhedral discretization. Robustness of conventional processes for performing domain decomposition (e.g., the subdivision of a geometric domain into polyhedral elements) is not trivial. Generally, domain decomposition breaks down a domain into a finite number of cells with certain desired properties, such as positive Jacobian, element convexity, and planar facets. A domain decomposition also defines how a point in the domain is assigned to a cell, and how each cell in the domain decomposition identifies cells in close proximity thereto. 
     Several different approaches have been proposed for performing domain decomposition over geometric domains. These approaches, however, are associated with numerous deficiencies. In particular, conventional Voronoi domain decomposition (VDD) approaches rely on clipping, where facets of one or more Voronoi cells extend beyond a boundary of the geometric domain, and such facets are clipped. This may result in a clipped Voronoi cell having undesirable properties, such as a relatively large aspect ratio. Additionally, clipping may result in creation of cells that are non-convex and/or not star-shaped. Thus, while Voronoi domain decomposition of a geometric domain may produce desirable properties for many applications, there is currently a lack of a robust approach for performing Voronoi domain decomposition that does not rely on clipping. 
     SUMMARY 
     The following is a brief summary of subject matter that is described in greater detail herein. This summary is not intended to be limiting as to the scope of the claims. 
     Described herein are various technologies pertaining to performing Voronoi domain decomposition without relying on clipping. More particularly, a computing system receives a three-dimensional (3D) domain descriptor, such as a Computer-aided Design (CAD) file that defines an enclosed 3D geometric domain. The approach described herein for performing Voronoi domain decomposition is robust, such that the enclosed domain may have an arbitrary shape. The computing system identifies where seeds are to be located with respect to the enclosed domain. As will be described herein, at least some seeds are located exterior to the enclosed domain, resulting in formation of facets that are coincident with a border surface of the enclosed domain. 
     More specifically, the computing system can identify sharp corners of the enclosed domain, wherein sharp corners exist where edges of the enclosed domain intersect and the interior angle of intersection is less than an angle threshold, for example 150°. Thereafter, the computing system centers spheres over these sharp corners, where a radius of each sphere is determined based on a set of rules. For instance, a rule in the set of rules can indicate that the sphere may only intersect the edges that form the sharp corner that is covered by the sphere. In another example, a second rule in the set of rules can indicate that a sphere may not intersect with any other sphere that is centered over a sharp corner of the enclosed domain. Hence, it can be ascertained that at least a portion of each edge and each surface in the enclosed domain remains uncovered. 
     Subsequently, the computing system covers the uncovered portions of the edges with spheres, where the spheres are centered over points on the edges. More specifically, the computing system can uniformly randomly select an edge from amongst all edges of the enclosed domain, and the computing system can randomly select a point on the selected edge. When the selected point is already covered by a sphere, the computing system discards the point and the sampling process is repeated. When the point is uncovered, the computing system centers a sphere over the point. The computing system selects the radius of the sphere based on a second set of rules. For instance, the sphere can only intersect the edge on which the point lies. Further, the sphere is prevented from intersecting another sphere that is not centered on a point on the edge. Additionally, the radius of the circle may be precluded from being over a predefined threshold. Using the above described process, the computing system covers each portion of each edge of the enclosed domain with at least one sphere. 
     The computing system then covers the uncovered portions of the surfaces of the enclosed domain with spheres, where the spheres are centered over points on the surfaces. With more specificity, the computing system can uniformly randomly select a surface from amongst all surfaces of the enclosed domain, and the computing system can randomly select a point on the selected surface. When the selected point is already covered by a sphere, the computing system discards the point and the surface sampling process is repeated. When the point is uncovered, the computing system centers a sphere over the point. The computing system selects the radius of the sphere based on a third set of rules. For instance, the sphere can only intersect the surface on which the selected point lies. Further, the sphere is prevented from intersecting another sphere that is not centered on a point on the surface. Additionally, the radius of the sphere may be precluded from being over a second predefined threshold. 
     In some cases, a sphere placed by the computing system on a surface of the enclosed domain covers the points of intersection of a set of three other spheres. Using such a sphere in connection with identifying intersections of spheres as boundary seeds for a Voronoi mesh can cause the Voronoi mesh not to conform to the boundaries of the enclosed domain. Therefore, in such a case, the sphere that covers the intersection points can be removed, causing a void of uncovered points on the surface. Points in the void are resampled to find a point at which a replacement sphere can be centered to simultaneously 1) cover all points in the void and 2) avoid covering the intersection points of any set of three other spheres. Responsive to identifying such point in the void, the replacement sphere is placed, centered at the identified point. 
     Thereafter, the computing system identifies intersections of spheres, and labels these intersections as being boundary seeds for use when performing Voronoi tessellation. When three spheres intersect, a pair of intersecting points is formed, thereby forming a pair of boundary seeds, where one point in the pair is located inside the enclosed domain, while the other point in the pair is located exterior to the enclosed domain. Thus, each boundary seed inside the enclosed domain is mirrored by another boundary seed outside of the enclosed domain. This mirroring of boundary seeds ensures that a facet of a resultant Voronoi cell is coincident with an edge of the domain —therefore, clipping of Voronoi cells is unnecessary. 
     The computing system can undertake further processing to improve properties of Voronoi cells in the enclosed domain. Specifically, the computing system can add interior seeds to the interior of enclosed domains, where the interior seeds are positioned such that they do not interfere with the facets that are coincident with edges or surfaces of the enclosed domain. More particularly, any seed inserted in the interior of the enclosed domain must be further from any point on any facet that is coincident with an edge or surface than the boundary seed corresponding to the facet. This ensures that the insertion of the seed does not alter a facet formed between a boundary seed pair. The computing system can populate the interior of the enclosed domain with interior seeds by randomly sampling a point from the interior of the domain, checking to ensure that this point does not violate the boundary condition referenced above, and further checking to ensure that the point is at least a threshold distance from any other previously inserted interior seed. When such conditions are met, the computing system places a seed at the sampled point, and the process repeats until the interior of the enclosed domain is populated with a sufficient number of interior seeds. Populating the interior of the enclosed domain with several interior seeds results in formation of Voronoi cells with bounded aspect ratios. Once the computing system has populated the interior of the enclosed domain with interior seeds, the computing system performs a Voronoi tessellation, thereby creating a conforming Voronoi mesh, with unclipped elements, that is bounded by the enclosed domain. 
     The computing system may then perform a numerical simulation based on this Voronoi mesh. There are many different applications for which performing a numerical simulation based on the Voronoi mesh are desired. Examples include numerical simulations of two-dimensional spatio-temporal spaces, reconnection-based arbitrary Lagrangian-Eulerian methods for multi-material high-speed flows from strong shear deformations, polyhedral discretization for cohesive fracture simulations, etc. 
     The above summary presents a simplified summary in order to provide a basic understanding of some aspects of the systems and/or methods discussed herein. This summary is not an extensive overview of the systems and/or methods discussed herein. It is not intended to identify key/critical elements or to delineate the scope of such systems and/or methods. Its sole purpose is to present some concepts in a simplified form as a prelude to the more detailed description that is presented later. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a functional block diagram of an exemplary computing device that is configured to perform numerical simulation based on a conforming Voronoi mesh. 
         FIG. 2  is a flow diagram illustrating an exemplary methodology for performing a numerical simulation based on a conforming Voronoi mesh. 
         FIG. 3  is a flow diagram illustrating an exemplary methodology for determining locations of seeds that are used to construct a conforming Voronoi mesh in an arbitrary three-dimensional (3D) enclosed geometric domain. 
         FIG. 4  is a flow diagram that illustrates an exemplary methodology for determining locations of seeds that are employed to form a conforming Voronoi mesh in an arbitrary 3D enclosed geometric domain. 
         FIG. 5  is a schematic of a portion of an exemplary enclosed geometric domain with spheres positioned over sharp corners of the domain. 
         FIG. 6  is a flow diagram illustrating an exemplary methodology for determining locations of boundary seeds that are used to construct a conforming Voronoi mesh in an arbitrarily-shaped enclosed domain. 
         FIG. 7  is a schematic that illustrates spheres that cover edges of an enclosed domain. 
         FIG. 8  is a flow diagram illustrating an exemplary methodology for determining locations of boundary seeds that are used to construct a conforming Voronoi mesh in an arbitrarily-shaped 3D enclosed geometric domain. 
         FIG. 9  is a schematic that illustrates spheres that cover surfaces of an enclosed domain. 
         FIG. 10  is a flow diagram that illustrates an exemplary methodology for labeling intersection points as being boundary seeds for use in connection with generating a conforming Voronoi mesh in an arbitrarily-shaped enclosed domain. 
         FIG. 11  is a schematic that depicts locations of seeds that are usable when constructing a conforming Voronoi mesh in an arbitrarily-shaped enclosed domain. 
         FIG. 12  depicts an exemplary Voronoi mesh. 
         FIG. 13  is a flow diagram that illustrates an exemplary methodology for determining locations of interior seeds in an enclosed domain, wherein the seeds are employed to bound aspect ratios of at least some cells in a conforming Voronoi mesh. 
         FIG. 14  depicts an exemplary computing system. 
     
    
    
     DETAILED DESCRIPTION 
     Various technologies pertaining to performing numerical simulations based on a conforming Voronoi mesh, and further pertaining to constructing such Voronoi mesh, are now described with reference to the drawings, wherein like reference numerals are used to refer to like elements throughout. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of one or more aspects. It may be evident, however, that such aspect(s) may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to facilitate describing one or more aspects. Further, it is to be understood that functionality that is described as being carried out by certain system components may be performed by multiple components. Similarly, for instance, a component may be configured to perform functionality that is described as being carried out by multiple components. 
     Moreover, the term “or” is intended to mean an inclusive “or” rather than an exclusive “or.” That is, unless specified otherwise, or clear from the context, the phrase “X employs A or B” is intended to mean any of the natural inclusive permutations. That is, the phrase “X employs A or B” is satisfied by any of the following instances: X employs A; X employs B; or X employs both A and B. In addition, the articles “a” and “an” as used in this application and the appended claims should generally be construed to mean “one or more” unless specified otherwise or clear from the context to be directed to a singular form. 
     Further, as used herein, the terms “component”, “system”, and “module” are intended to encompass computer-readable data storage that is configured with computer-executable instructions that cause certain functionality to be performed when executed by a processor. The computer-executable instructions may include a routine, a function, or the like. It is also to be understood that a component or system may be localized on a single device or distributed across several devices. Additionally, as used herein, the term “exemplary” is intended to mean serving as an illustration or example of something, and is not intended to indicate a preference. 
     Described herein are various technologies pertaining to performing a numerical simulation utilizing a computing device, wherein the numerical simulation receives as input information pertaining to a conforming Voronoi mesh that is bounded by a predefined arbitrarily-shaped three-dimensional enclosed geometric domain. The conforming Voronoi mesh is constructed by: 1) determining locations of boundary seeds (where facets of Voronoi cells are coincident with boundaries of the enclosed domain); and 2) optionally, determining locations of interior seeds that result in the Voronoi mesh having Voronoi cells with bounded aspect ratios. 
     With reference now to  FIG. 1 , a functional block diagram of an exemplary computing device  100  is illustrated. The computing device  100  includes a processor  102  and memory  104  that is operably coupled to the processor  102 . The computing device  100  also includes a data store  106  that is operably coupled to the processor  102  and/or the memory  104 . The memory  104  has loaded therein a domain decomposition module  108  that is configured to perform Voronoi domain decomposition (VDD) with respect to an enclosed three-dimensional (3D) geometric domain of arbitrary shape. The domain decomposition module  108  receives a three-dimensional domain descriptor  110 , which defines the above-mentioned enclosed domain. The three-dimensional domain descriptor  110 , For example, may be a Computer-aided Design (CAD) file, which can include an electronic representation of the enclosed domain. More specifically, the 3D domain descriptor  110  comprises lines defined by start and end positions, wherein the lines form edges of the enclosed domain, and surfaces joined at the edges, wherein together the surfaces form the enclosed domain. 
     The domain decomposition module  108  comprises a boundary seed identifier module  112  that is configured to determine locations of boundary seeds with respect to the enclosed domain. More specifically, these boundary seeds are seeds which can be employed by a Voronoi tessellation algorithm to create a Voronoi mesh that comprises Voronoi cells, wherein each cell includes a seed, and further wherein such Voronoi cells each have a facet that is coincident with at least a portion of a surface (boundary) of the enclosed domain. Collectively, the above-mentioned facets are coincident with an entirety of all surfaces of the enclosed domain, such that the resultant Voronoi mesh is conforming, and clipping need not be undertaken. 
     The domain decomposition module  108  further comprises an interior seed identifier module  114  that populates the interior of the enclosed domain with interior seeds (which are in addition to the boundary seeds). The interior seed identifier module  114  positions the interior seeds inside of the enclosed domain such that Voronoi cells that are “grown” using these Voronoi seeds in the resultant conforming Voronoi mesh have a bounded aspect ratio (e.g., an aspect ratio that approaches 1). The domain decomposition module  108  also includes a tessellator module  116  that constructs the conforming Voronoi mesh by performing Voronoi tessellation using the boundary seeds identified by the boundary seeds identifier module  112  and the interior seeds generated by the interior seed identifier module  114 . 
     The memory  104  also includes a numerical simulator module  118  that can perform a numerical simulation based on the conforming Voronoi mesh constructed by the tessellator module  116 . The numerical simulator module  118  can be configured to perform any suitable three-dimensional numerical simulation using polyhedral discretization, wherein applications include, but are not limited to, reconnection-based arbitrary Lagrangian-Eulerian methods for multi-material high-speed flows with strong shear deformations and polygon discretization for three-dimensional cohesive fracture simulations. The numerical simulator module  118  may also be configured to perform particle simulations based on the conforming Voronoi mesh output by the tessellator module  116 . For instance, particle-based flow simulations employ particles to define weighted Voronoi cells for finite element structure analysis. 
     Operation of the computing device  100  is now set forth. The computing device receives the three-dimensional domain descriptor  110 , which, as mentioned above, may be a CAD file. The boundary seed identifier module  112  determines positions of boundary seeds with respect to the enclosed domain defined by the three-dimensional domain descriptor  110 , wherein, as mentioned above, boundary seeds are those whose Voronoi cells, when constructed, each have a facet that is coincident with at least a portion of a surface of the enclosed domain. Boundary seeds identified by the boundary seed identifier module  112  are in pairs: one boundary seed inside the enclosed domain and one boundary seed outside of the enclosed domain, wherein the boundary seeds are equidistant to any point along a surface that separates the boundary seeds in the boundary seed pair. This mirroring of boundary seeds about the surface ensures that a facet, which is between the Voronoi cells for the boundary seeds in the boundary seed pair, is coincident with at least a portion of the surface that separates the boundary seeds in the boundary seed pair. Operation of the computing device  100  generally, and the domain decomposition module  108  specifically, is described in greater detail with respect to  FIGS. 2-9 . 
       FIGS. 2-4, 6, 8, 10 and 13  illustrate exemplary methodologies relating to constructing a conforming Voronoi mesh that is bounded by a predefined, arbitrarily-shaped enclosed domain. While the methodologies are shown and described as being a series of acts that are performed in a sequence, it is to be understood and appreciated that the methodologies are not limited by the order of the sequence. For example, some acts can occur in a different order than what is described herein. In addition, an act can occur concurrently with another act. Further, in some instances, not all acts may be required to implement a methodology described herein. 
     Moreover, the acts described herein may be computer-executable instructions that can be implemented by one or more processors and/or stored on a computer-readable medium or media. The computer-executable instructions can include a routine, a sub-routine, programs, a thread of execution, and/or the like. Still further, results of acts of the methodologies can be stored in a computer-readable medium, displayed on a display device, and/or the like. 
     Referring to  FIG. 2 , an exemplary methodology  200  that is performed by the computing device  100  is illustrated. The methodology  200  starts at  202 , and at  204  a definition of an enclosed 3D geometric domain is received. At  206 , locations of seeds for use when performing Voronoi tessellation are determined such that, 1) a resultant Voronoi mesh constructed based on these seeds is conforming and is bounded by the enclosed domain; and 2) at least some Voronoi cells in the resultant Voronoi mesh have a bounded aspect ratio. 
     At  208 , the Voronoi mesh is generated based on the determined locations of the Voronoi seeds. Hence, a Voronoi domain decomposition is performed, the Voronoi mesh being conforming. At  210 , a numerical simulation is performed based on the Voronoi mesh, and the methodology  200  completes at  212 . 
     Now referring to  FIG. 3 , an exemplary methodology  300  performed by the domain decomposition module  108  in connection with determining locations of boundary seeds and interior seeds is illustrated. The methodology  300  starts at  302 , and at  304 , locations of boundary seeds are determined, wherein Voronoi cells of the boundary seeds in a resultant Voronoi mesh have at least one facet that is coincident with at least a portion of an edge of the enclosed domain, and further wherein these facets, collectively, define the boundary of the enclosed domain. At  306 , locations of interior seeds are determined, such that Voronoi cells of the interior seeds have a bounded aspect ratio. The methodology  300  completes at  308 . 
     Now referring to  FIG. 4 , an exemplary methodology  400  that is performed by the boundary seed identifier module  112  is illustrated. The methodology  400  starts at  402 , and at  404  each sharp corner of the enclosed domain is identified. A sharp corner exists at the intersection of three or more edges (lines) of the enclosed domain. For example, a sharp corner exists when an interior angle at the intersection of two intersecting lines is less than some angle threshold, such as about 150°. In another example, a sharp corner exists at the intersection of any three lines in the enclosed domain, regardless of interior angle. 
     At  406 , for each sharp corner, a radius value is selected, wherein the radius value is selected based on a set of rules. More specifically, spheres are to be centered over each sharp corner of the enclosed domain, wherein the radius of each sphere is determined based on the set of rules mentioned above. Generally, the radius of each sphere must respect the local feature size of the domain defined in the three-dimensional domain descriptor  110 . With particularity, a first rule in the set of rules can require that the radius of a sphere is selected such that the sphere does not intersect any edges other than the edges that form the sharp corner on which the sphere is centered. A second rule in the set of rules can require that the sphere does not intersect or be tangential to any other sphere that is centered on another sharp corner in the three-dimensional domain. Optionally, a third rule in the set of rules can require that the radius be less than a threshold maximum radius value. 
     At  408 , the spheres with the selected radius values are centered over the sharp corners of the enclosed domain. The methodology  400  completes at  410 . 
     Now referring to  FIG. 5 , an exemplary schematic that depicts operation of the methodology  400  with respect to an enclosed domain is illustrated. In the exemplary schematic  500 , a surface of the enclosed domain  502  is a rectangle having four edges  504 - 510  creating four sharp corners  512 - 518 . Responsive to identifying the sharp corners  512 - 518 , the boundary seed identifier module  112  centers respective spheres  520 - 526  (shown in  FIG. 5  as circles), respectively, over the sharp corners  512 - 518  in accordance with the rules set forth above. For example, the boundary seed identifier module  112  can perform the process sequentially, by first identifying a sharp corner (e.g., the sharp corner  512 ), and immediately thereafter placing the sphere  520  over the sharp corner  512  using the rules set forth above. That is, the sphere  520  can initially be set with a smallest possible radius and then expanded until: 1) the sphere  520  intersects an edge other than the edge  504  or  506  or other edges that, with edges  504  and  506  form the sharp corner  512 , b; 2) the sphere  520  intersects a sphere that has previously been centered on a sharp corner; or 3) the radius has reached the predefined maximum. The boundary seed identifier module  112  may then move to a next sharp corner and the process can be repeated until spheres have been centered over all sharp corners of the enclosed domain. As can be ascertained, due to the rules specified above, at least a portion of each of the edges  504 - 510  remains uncovered by any of the spheres  520 - 526  to  520 - 526 . In another approach, the boundary seed identifier module  112  can perform the process of centering spheres over sharp corners in parallel, wherein the boundary seed identifier module  112  identifies all the sharp corners  512 - 516 , centers a sphere over each of the sharp corners, and then (in parallel) expands the radii of the spheres. When a sphere violates one of the rules, the boundary seed identifier module  112  can reduce the radius of the sphere and thereafter keep such radius static while continuing to expand other spheres. Other approaches are also contemplated. 
     Now referring to  FIG. 6 , an exemplary methodology  600  that is performed by the boundary seed identifier module  112  in connection with identifying locations of boundary seeds with respect to the enclosed domain is illustrated. Performance of the methodology  600  subsequent to performance of the methodology  400  results in each point on each edge of the enclosed domain being covered by at least one sphere. The methodology  600  starts at  602 , and at  604  a line segment (which is at least a portion of an edge) of the enclosed domain is selected. For example, the line segment can be uniformly randomly selected, wherein each line segment is assigned a weight that is based on length of the line segment. At  606 , a point is sampled from the selected line segment, wherein the point can be a randomly selected from the line segment. At  608 , a determination is made regarding whether the point is already covered by a sphere. If it is determined at  608  that the point is already covered by a sphere, then the point is discarded and the methodology returns to  604 , where another line segment is uniformly randomly selected. 
     If, however, it is determined at  608  that the sampled point is not covered by a sphere, then at  610  a radius for a sphere is selected based on a second set of rules, wherein the sphere is to be centered at the sampled point. For instance, the second set of rules can indicate that the sphere cannot intersect or be tangential to any sharp corner, and may further not intersect or be tangential to any edge other than the edge that includes the line segment. Further, the second set of rules may indicate that the sphere is not to be within a threshold distance of another edge. Still further, the second set of rules can indicate that the sphere is not to encapsulate any other sphere. Finally, the second set of rules can optionally indicate that the radius is not to exceed a maximum radius. At  612 , responsive to selecting the radius for the sphere, the sphere with the selected radius is positioned on the line segment and centered at the sampled point. At  614 , a determination is made regarding whether each point along the edges of the enclosed domain is covered by a sphere. If each point is not covered, then the methodology returns to  604 . If it is determined at  614  that each point along the edges of the enclosed domain is covered by a sphere, the methodology  600  completes at  616 . 
     Various optimization approaches can be employed by the boundary seed identifier module  112  when covering each point along the edges of the enclosed domain with at least one sphere. For instance, initially, a line segment may be an entirety of an edge of the enclosed domain. After some threshold number of consecutive times that a sampled point on the line segment is identified as being covered by a sphere, the line segment can be partitioned into some smaller line segments. For instance, the line segment may be divided in half, thereby forming two line segments. Subsequently, each of the two line segments can be analyzed to ascertain if each point in the line segment is covered by a sphere. Line segments with each point covered by at least one sphere can be discarded from further consideration, leaving only the line segment that is at least partially uncovered. This process can be repeated on a per-line segment basis (e.g., line segment by line segment) until all points on all edges of the enclosed domain are covered by at least one sphere. In another embodiment, rather than analyzing line segments one by one, when there are some threshold number of consecutive “misses” (where a sampled point is already covered by a sphere), each line segment of the domain can be partitioned into multiple line segments, such that line segments that are entirely covered are identified in batches. Such process can be repeated until all points of the edges of the enclosed domain are covered by spheres. 
     Referring now to  FIG. 7 , an exemplary schematic  700  that depicts the exemplary surface  502  of the enclosed domain with its edges  504 - 510  entirely covered by spheres, is illustrated. The schematic  700  depicts the spheres  520 - 526  centered at the sharp corners  512 - 518 . The schematic  700  additionally illustrates spheres  702 - 712  (again, depicted as circles) placed over portions of the edges  504 - 510 , such that each point in each edge is covered by at least one of the spheres,  520 - 526  or  702 - 712 . The spheres  702 - 712  are positioned on the edges of the enclosed domain  502  by the boundary seed identifier module  112  utilizing the methodology  600  set forth above. 
     Referring now to  FIG. 8 , an exemplary methodology  800  that is performed by the boundary seed identifier module  112  in connection with identifying locations of boundary seeds with respect to the enclosed domain is illustrated. Performance of the methodology  800  subsequent to performance of the methodology  600  results in each point on each surface of the enclosed domain being covered by at least one sphere. The methodology  800  starts at  802 , and at  804  a surface of the enclosed domain is selected. For example, the surface can be uniformly randomly selected, wherein each surface is assigned a weight that is based on surface area of the surface. At  806 , a point is sampled from the selected surface, wherein the point can be randomly selected from the surface. At  808 , a determination is made regarding whether the point is already covered by a sphere. If it is determined at  808  that the point is already covered by a sphere, then the point is discarded and the methodology returns to  804 , where another surface is uniformly randomly selected. 
     If, however, it is determined at  808  that the sampled point is not covered by a sphere, then at  810  a radius for a sphere is selected based on a third set of rules, wherein the sphere is to be centered at the sampled point. For instance, the third set of rules can indicate that the sphere cannot intersect or be tangential to any sharp corner or any edge, and may further not intersect or be tangential to any surface other than the selected surface. Further, the third set of rules may indicate that the sphere is not to be within a threshold distance of another surface. Still further, the third set of rules can indicate that the sphere is not to encapsulate any other sphere. Finally, the second set of rules can optionally indicate that the radius is not to exceed a maximum radius. At  812 , responsive to selecting the radius for the sphere, the sphere with the selected radius is positioned on the line segment and centered at the sampled point. At  814 , a determination is made regarding whether each point along the edges of the enclosed domain is covered by a sphere. If each point is not covered, then the methodology returns to  804 . If it is determined at  814  that each point along the edges of the enclosed domain is covered by a sphere, the methodology  800  completes at  816 . 
     Referring now to  FIG. 9 , an exemplary schematic  900  that depicts the exemplary surface  502  of the enclosed domain is illustrated, wherein the exemplary surface  502  is entirely covered by spheres. The schematic  900  depicts the spheres  520 - 526  centered at the sharp corners  512 - 518  and the spheres  702 - 712  placed over portions of the edges  504 - 510 . The schematic  900  additionally illustrates spheres  902  and  904  (depicted once again as circles), placed over portions of the surface  502  such that each point on the surface  502  is covered by at least one of the spheres  520 - 526 ,  702 - 712 ,  902 , or  904 . The spheres  902  and  904  are positioned on the surface  502  of the enclosed domain by the boundary seed identifier module  112  utilizing the methodology  800  set forth above. 
     Referring now to  FIG. 10 , another exemplary methodology  1000  that is performed by the boundary seed identifier module  112  is illustrated. The methodology  1000  starts at  1002 , and at  1004  points of intersection of the spheres (e.g., the spheres  520 - 526 ,  702 - 712 ,  902 , and  904 ) are identified. As illustrated in  FIG. 9 , each sphere intersects with at least two other spheres, such that each set of three spheres has two intersection points corresponding thereto. The boundary seed identifier module  112  identifies each of these intersection points. 
     One or more of the spheres may cover an intersection point of three other spheres. In other words, for each set of three spheres, there may exist a fourth sphere in the spheres, wherein one or both of the intersection points of the set of three spheres is within the radius of the fourth sphere. If this is the case, a Voronoi mesh generated using the intersection points as boundary seeds may not conform to the enclosed geometric domain. Thus, at  1006 , a determination is made whether any spheres cover intersection points of any sets of three other spheres. For example, a search can be executed over a k-d tree for spheres that overlap intersection points of other groups of spheres. If no spheres cover intersection points of another three spheres, then the methodology  1000  proceeds to  1014 . 
     If one or more spheres do cover one or both of the intersection points of a set of three other spheres, one of the spheres that covers an intersection point is removed at  1008 , causing a void where at least a portion of the surface of the enclosed domain is not covered by a sphere. At  1010 , the void is resampled and a point in the void is identified wherein a sphere centered at the identified point in the void simultaneously covers the entire void and does not cover intersection points of any other three spheres. The point can be identified based on the first, second, and third sets of rules, wherein a sphere centered at the identified point conforms to one of the sets of rules. In response to the point being identified at  1010 , a sphere is centered at the identified point at  1012 , whereupon the methodology  1000  returns to  1004  and new intersection points of the spheres are identified. In rare cases, it may be that it is not possible to identify a point in the void wherein a sphere centered at the identified point simultaneously covers the entire void and does not cover intersection points of any other three spheres. If this is the case, the sphere that was removed at  1008  can be placed back where it was, and an additional sphere placed that covers four intersection pairs formed by the sphere and the set of three spheres that it intersects. For example, if a sphere A was the sphere removed at  1008 , and the sphere A intersected spheres B, C, and D, covering their intersection points, the additional sphere E would be placed such that it covered: 1) the intersection points of spheres A, B, and C; 2) the intersection points of spheres A, C, and D; 3) the intersection points of spheres A, B, and D; and 4) the intersection points of spheres B, C, and D. The spheres A and E would thenceforth no longer be considered in the determination evaluated at  1006 . 
     The methodology repeats the loop comprising steps  1004 - 1012  until it is determined at  1006  that no spheres cover intersection points of any other three spheres, whereupon at  1014 , the intersection points are labeled as being boundary seeds for use by the tessellator module  116  when generating the Voronoi mesh. The methodology  1000  completes at  1016 . 
     It is to be understood that while the methodology  1000  is described herein as being performed by the seed identifier module  112  after spheres are placed according to the methodologies  400 ,  600 , and  800 , in various embodiments some aspects of the methodology  1000  can be performed concurrently with or as part of the methodologies  400 ,  600 , and  800 . With more particularity, when placing a sphere according to the methodologies  400 ,  600 , and  800 , the seed identifier module  112  can perform a check to determine if placing the sphere causes the sphere to cover one or more intersection points of a set of three other already-placed spheres. If placing the sphere does cause the sphere to overlap one or more such intersection points, the seed identifier module  112  can reject the sphere and perform resampling as described above with respect to the methodology  1000 . 
     With reference to  FIG. 11 , an exemplary schematic  1100  that depicts locations of boundary seeds identified by the boundary seed identifier module  112  is illustrated. In the example shown in  FIG. 11 , the boundary seed identifier module  112  identifies boundary seeds  1102 - 1120 . The boundary seeds are in pairs, with each pair including a boundary seed inside the enclosed domain and a boundary seed outside of the enclosed domain, and further wherein boundary seeds in a boundary seed pair are equidistant to any point on an edge or surface that is between boundary seeds in the boundary seed pair. For example, the boundary seed  1102  forms a boundary seed pair with a boundary seed outside of the enclosed domain (not pictured, positioned directly above the surface  502  and aligned with the boundary seed  1102 ), wherein the boundary seed  1102  is inside the enclosed domain and its paired boundary seed is outside of the enclosed domain, and further wherein the boundary seeds  1102  and its paired boundary seed are equidistant to any point on the surface  502  that is between the boundary seed  1102  and its paired boundary seed. In other words, the boundary seeds of a boundary seed pair mirror each other about the surface  502 . 
     Other boundary seeds in boundary seed pairs have the same “mirroring” property. Accordingly, when the tessellator module  116  constructs a Voronoi mesh using the boundary seeds  1102 - 1120 , Voronoi facets shared by boundary seeds in boundary seed pairs are coincident with surfaces of the enclosed domain. In other words, a Voronoi cell of the boundary seed  1102  will have a facet that is coincident with the surface  502  due to the boundary seeds  1102  and its paired boundary seed being equidistant to any point along the surface  502 . Thus, for example, a facet of each Voronoi cell for the boundary seeds  1102 - 1120  will be coincident with a respective portion of the surface  502 , where the facets collectively are coincident with an entirety of the surface  502 . Therefore, it can be ascertained that a Voronoi mesh generated by the tessellator module  116  when utilizing the boundary seeds  1102 - 1120  and their respective paired boundary seeds to construct the Voronoi mesh will be a conforming Voronoi mesh with some of the facets of the Voronoi cells of the seeds  1102 - 1120  being coincident with the surface  502  of the enclosed domain. 
     Referring to  FIG. 12 , a portion of an exemplary conforming Voronoi mesh  1100  is illustrated, where the mesh is bounded by the enclosed domain. 
     In some applications, it may be desirable to cause the resultant conforming Voronoi mesh to have more Voronoi cells than those generated based solely on the boundary seeds. For instance, the numerical simulator module  118  can be configured to solve a partial differential equation (PDE) over the enclosed domain based on a Voronoi mesh, and inclusion of more Voronoi cells in the mesh can result in reduction in error in results of numerical simulation. Hence, the interior seed identifier module  114  can place additional seeds inside the enclosed domain while ensuring that the additional seeds do not compromise the conformity of the resultant Voronoi mesh. In other words, the interior seeds positioned in the enclosed domain by the interior seed identifier module  114  do not alter the facets that are coincident with the surface  502  of the enclosed domain. 
     With reference now to  FIG. 13 , an exemplary methodology  1300  that is performed by the interior seed identifier module  114  when placing interior seeds in an enclosed domain is illustrated. The methodology  1300  starts at  1302 , and at  1304  a point from the interior of the enclosed domain is randomly sampled. At  1306 , a determination is made regarding whether the point violates a boundary condition. In other words, the interior seed identifier module  114  ensures that the distance between the sampled point and any point along any facet that is coincident with the surfaces of the enclosed domain is greater than the distance between any point along the facet and its boundary seed. If it is determined, at  1306 , that a boundary condition has been violated, the methodology returns to  1304 . If the boundary condition is determined not to be violated at  1306 , then the methodology  1300  continues to  1308 , where a determination is made regarding whether the sampled point is covered by a sphere. In other words, at  1308 , determination is made regarding whether the sampled point is within some threshold distance of either a boundary seed or an interior seed. If, at  1308 , it is determined that the sampled point is covered by the sphere, then the methodology  1300  returns to  1304 . 
     If it is determined at  1308  that the sampled point is not already covered by a sphere, then the methodology  1300  continues to  1310 , where the interior seed identifier module  114  labels the sampled point as being an interior seed to be used by the tessellator module  116  when generating the conforming Voronoi mesh. At  1312 , the sphere with a predefined radius is positioned over the interior seed labeled at  1310 , wherein the interior seed is at the center of the sphere (this ensures that the interior seed identifier module  114  does not place another interior seed too close to the interior seed). Thereafter, at  1314 , a determination is made regarding whether there is total coverage in the enclosed domain. In other words, a determination is made as to whether each point in the enclosed domain is covered by a sphere (e.g., whether each point in the enclosed domain is within a threshold distance of another point in the enclosed domain). If there is not total coverage, the methodology returns to  1304 . When there is total coverage, the methodology  1300  completes at  1316 . 
     Similar to the approach described above (with respect to covering the edges of the enclosed domain with spheres), a hierarchical approach can be employed by the interior seed identifier module  114  when populating the interior of the enclosed domain with interior seeds. For example, initially, the interior seed identifier module  114  can sample a point from an entirety of interior of the enclosed domain. After some threshold number of consecutive samplings where the sampled point is covered by a sphere, the interior seed identifier module  114  can partition the interior of the enclosed domain into multiple subspaces. For instance, the interior seed identifier module  114  can place a grid over the interior region of the enclosed domain. The interior seed identifier module  114  may then select a cell of the grid and ascertain whether each point in the cell is covered by a sphere. When each point in the cell is covered by a sphere, the interior seed identifier module  114  can discard the cell from further consideration; this process can be repeated to discard all cells that are entirely covered by one or more spheres. The interior seed identifier module may then randomly select a cell from the remaining cells and sample a point from the cell. Thus, the methodology  1300  can be repeated over continuously decreasing cell sizes until total coverage is obtained. 
     After the interior seed identifier module  114  has placed the interior seeds on the interior of the enclosed domain (without violating the boundary condition), the tessellator module  116  can construct a Voronoi mesh using the boundary seeds and the interior seats as seeds for Voronoi cells in the Voronoi mesh. 
     Hence, returning to  FIG. 1 , the tessellator module  116  generates a decomposed domain  120  and causes the decomposed domain  120  to be retained in the data store  106 . The numerical simulator module  118  can access the decomposed domain  120 , perform numerical simulation based on the decomposed domain  120 , and generate simulation results  122  based on the decomposed domain. In an exemplary embodiment, the domain decomposition module  108  can utilize a k-d tree in the memory  104  when representing seeds and the resultant Voronoi mesh, where hyper-rectangles are defined using the seeds themselves. 
     Referring now to  FIG. 14 , a high-level illustration of an exemplary computing device  1400  that can be used in accordance with the systems and methodologies disclosed herein is illustrated. For instance, the computing device  1400  may be used in a system that is configured to perform numerical simulations. By way of another example, the computing device  1400  can be used in a system that constructs conforming Voronoi meshes. The computing device  1400  includes at least one processor  1402  that executes instructions that are stored in a memory  1404 . The instructions may be, for instance, instructions for implementing functionality described as being carried out by one or more components discussed above or instructions for implementing one or more of the methods described above. The processor  1402  may access the memory  1404  by way of a system bus  1406 . In addition to storing executable instructions, the memory  1404  may also store seeds, Voronoi meshes, definitions of 3D enclosed geometric domains, etc. 
     The computing device  1400  additionally includes a data store  1408  that is accessible by the processor  1402  by way of the system bus  1406 . The data store  1408  may include executable instructions, numerical simulation results, etc. The computing device  1400  also includes an input interface  1410  that allows external devices to communicate with the computing device  1400 . For instance, the input interface  1410  may be used to receive instructions from an external computer device, from a user, etc. The computing device  1400  also includes an output interface  1412  that interfaces the computing device  1400  with one or more external devices. For example, the computing device  1400  may display text, images, etc. by way of the output interface  1412 . 
     It is contemplated that the external devices that communicate with the computing device  1400  via the input interface  1410  and the output interface  1412  can be included in an environment that provides substantially any type of user interface with which a user can interact. Examples of user interface types include graphical user interfaces, natural user interfaces, and so forth. For instance, a graphical user interface may accept input from a user employing input device(s) such as a keyboard, mouse, remote control, or the like and provide output on an output device such as a display. Further, a natural user interface may enable a user to interact with the computing device  1400  in a manner free from constraints imposed by input device such as keyboards, mice, remote controls, and the like. Rather, a natural user interface can rely on speech recognition, touch and stylus recognition, gesture recognition both on screen and adjacent to the screen, air gestures, head and eye tracking, voice and speech, vision, touch, gestures, machine intelligence, and so forth. 
     Additionally, while illustrated as a single system, it is to be understood that the computing device  1400  may be a distributed system. Thus, for instance, several devices may be in communication by way of a network connection and may collectively perform tasks described as being performed by the computing device  1400 . 
     Various functions described herein can be implemented in hardware, software, or any combination thereof. If implemented in software, the functions can be stored on or transmitted over as one or more instructions or code on a computer-readable medium. Computer-readable media includes computer-readable storage media. A computer-readable storage media can be any available storage media that can be accessed by a computer. By way of example, and not limitation, such computer-readable storage media can comprise RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to carry or store desired program code in the form of instructions or data structures and that can be accessed by a computer. Disk and disc, as used herein, include compact disc (CD), laser disc, optical disc, digital versatile disc (DVD), floppy disk, and Blu-ray disc (BD), where disks usually reproduce data magnetically and discs usually reproduce data optically with lasers. Further, a propagated signal is not included within the scope of computer-readable storage media. Computer-readable media also includes communication media including any medium that facilitates transfer of a computer program from one place to another. A connection, for instance, can be a communication medium. For example, if the software is transmitted from a website, server, or other remote source using a coaxial cable, fiber optic cable, twisted pair, digital subscriber line (DSL), or wireless technologies such as infrared, radio, and microwave, then the coaxial cable, fiber optic cable, twisted pair, DSL, or wireless technologies such as infrared, radio and microwave are included in the definition of communication medium. Combinations of the above should also be included within the scope of computer-readable media. 
     Alternatively, or in addition, the functionally described herein can be performed, at least in part, by one or more hardware logic components. For example, and without limitation, illustrative types of hardware logic components that can be used include Field-programmable Gate Arrays (FPGAs), Program-specific Integrated Circuits (ASICs), Program-specific Standard Products (ASSPs), System-on-a-chip systems (SOCs), Complex Programmable Logic Devices (CPLDs), etc. 
     What has been described above includes examples of one or more embodiments. It is, of course, not possible to describe every conceivable modification and alteration of the above devices or methodologies for purposes of describing the aforementioned aspects, but one of ordinary skill in the art can recognize that many further modifications and permutations of various aspects are possible. Accordingly, the described aspects are intended to embrace all such alterations, modifications, and variations that fall within the spirit and scope of the appended claims. Furthermore, to the extent that the term “includes” is used in either the details description or the claims, such term is intended to be inclusive in a manner similar to the term “comprising” as “comprising” is interpreted when employed as a transitional word in a claim.