Determining drainage constraints and geometries in a triangular mesh

1. A computer-implemented method for designing a terrain surface, comprising:

(a) obtaining, in a computer, a triangular surface mesh representative of an existing surface, wherein the triangular surface mesh comprises two or more triangles that are connected by vertices and edges;

(b) specifying a drain intention for the terrain surface through one or more geometries, wherein:

(i) each of the one or more geometries comprises a point or a line; and

(ii) the drain intention defines a drainage flow that influences a shape of the terrain surface;

(c) modifying the triangular surface mesh using a Voronoi diagram resulting in a modified triangular surface mesh, wherein:

(i) the Voronoi diagram is based on the one or more geometries; and

(ii) the modifying prevents a drain conflict between the two or more triangles;

(d) autonomously determining a drain direction of each of the two or more triangles in the modified triangular surface mesh based on the drain intention, wherein the autonomously determining generates a drain pattern that is used to shape the terrain surface.

2. The computer-implemented method of claim 1 , wherein specifying the drain intention comprises:

specifying a drain element type for one of the one or more geometries, wherein the drain element type comprises a low point.

3. The computer-implemented method of claim 1 , wherein specifying the drain intention comprises:

specifying a drain element type for one of the one or more geometries, wherein the drain element type comprises a drain line.

4. The computer-implemented method of claim 1 , wherein specifying the drain intention comprises:

specifying a drain element type for one of the one or more geometries, wherein the drain element type comprises a ridge line.

5. The computer-implemented method of claim 1 , wherein autonomously determining the drain direction of each triangle comprises:

determining a geometry direction to a nearest geometry of the one or more geometries;

determining the drain direction based on the geometry direction and a drain intention type of the nearest geometry.

6. The computer-implemented method of claim 1 , wherein autonomously determining the drain direction of each triangle comprises:

identifying one or more zones, wherein each of the one or more zones include a subset of the one or more geometries;

selecting one of the one or more zones;

determining a geometry direction to a nearest geometry, of the one or more geometries within the selected zone; and

determining the drain direction based on the geometry direction and a drain intention type of the nearest geometry.

7. The computer-implemented method of claim 1 , further comprising:

identifying one or more zones of the triangular surface mesh;

selecting one of the one or more zones;

determining a geometry direction of the selected zone; and

determining the drain direction based on the geometry direction, wherein the drain direction complies with a minimum slope constraint.

8. The computer-implemented method of claim 1 , further comprising resolving the drain conflict between the triangles by:

creating the Voronoi diagram of the terrain surface using the one or more geometries, wherein:

the Voronoi diagram comprises an advanced Voronoi diagram;

the advanced Voronoi diagram is based on lines or curves;

the Voronoi diagram comprises one or more Voronoi cells;

placing a surface mesh break line along borders of the one or more Voronoi cells in the Voronoi diagram; and

retriangulating the triangular surface mesh along the placed break lines to result in the modified triangular surface mesh.

9. The computer-implemented method of claim 1 , further comprising:

identifying a first zone and a second zone of the triangular surface mesh, wherein the first zone overlaps with the second zone;

defining a hierarchy for the first zone and the second zone, wherein:

the first zone is higher priority than the second zone;

settings of the first zone override settings of the second zone;

determining a first geometry direction of the first zone and a second geometry direction of the second zone based on the hierarchy; and

determining the drain direction of each of the two or more triangles based on the first geometry direction and the second geometry direction.

10. The computer-implemented method of claim 1 , further comprising:

building the terrain surface based on the drain pattern.

11. A computer-implemented system for designing a terrain surface, comprising:

(a) a computer having a memory;

(b) a processor executing on the computer;

(c) the memory storing a set of instructions, wherein the set of instructions, when executed by the processor cause the processor to perform operations comprising:

(i) obtaining a triangular surface mesh representative of an existing surface, wherein the triangular surface mesh comprises two or more triangles that are connected by vertices and edges;

(ii) specifying a drain intention for the terrain surface through one or more geometries, wherein:

(1) each of the one or more geometries comprises a point or a line; and

(2) the drain intention defines a drainage flow that influences a shape of the terrain surface;

(iii) modifying the triangular surface mesh using a Voronoi diagram resulting in a modified triangular surface mesh, wherein:

(1) the Voronoi diagram is based on the one or more geometries; and

(2) the modifying prevents a drain conflict between the two or more triangles;

(iv) autonomously determining a drain direction of each of the two or more triangles in the modified triangular surface mesh based on the drain intention, wherein the autonomously determining generates a drain pattern that is used to shape the terrain surface.

12. The computer-implemented system of claim 11 , wherein the operations specifying the drain intention comprises:

specifying a drain element type for one of the one or more geometries, wherein the drain element type comprises a low point.

13. The computer-implemented system of claim 11 , wherein the operations specifying the drain intention comprises:

specifying a drain element type for one of the one or more geometries, wherein the drain element type comprises a drain line.

14. The computer-implemented system of claim 11 , wherein the operations specifying the drain intention comprises:

specifying a drain element type for one of the one or more geometries, wherein the drain element type comprises a ridge line.

15. The computer-implemented system of claim 11 , wherein the operations autonomously determining the drain direction of each triangle comprises:

determining a geometry direction to a nearest geometry of the one or more geometries;

determining the drain direction based on the geometry direction and a drain intention type of the nearest geometry.

16. The computer-implemented system of claim 11 , wherein the operations autonomously determining the drain direction of each triangle comprises:

identifying one or more zones, wherein each of the one or more zones include a subset of the one or more geometries;

selecting one of the one or more zones;

determining a geometry direction to a nearest geometry, of the one or more geometries within the selected zone; and

determining the drain direction based on the geometry direction and a drain intention type of the nearest geometry.

17. The computer-implemented system of claim 11 , wherein the operations further comprise:

identifying one or more zones of the triangular surface mesh;

selecting one of the one or more zones;

determining a geometry direction of the selected zone; and

determining the drain direction based on the geometry direction, wherein the drain direction complies with a minimum slope constraint.

18. The computer-implemented system of claim 11 , wherein the operations further comprise resolving the drain conflict between the triangles by:

creating the Voronoi diagram of the terrain surface using the one or more geometries, wherein:

the Voronoi diagram comprises an advanced Voronoi diagram;

the advanced Voronoi diagram is based on lines or curves;

the Voronoi diagram comprises one or more Voronoi cells;

placing a surface mesh break line along borders of the one or more Voronoi cells in the Voronoi diagram; and

retriangulating the triangular surface mesh along the placed break lines to result in the modified triangular surface mesh.

19. The computer-implemented system of claim 11 , wherein the operations further comprise:

identifying a first zone and a second zone of the triangular surface mesh, wherein the first zone overlaps with the second zone;

defining a hierarchy for the first zone and the second zone, wherein:

the first zone is higher priority than the second zone;

settings of the first zone override settings of the second zone;

determining a first geometry direction of the first zone and a second geometry direction of the second zone based on the hierarchy; and

determining the drain direction of each of the two or more triangles based on the first geometry direction and the second geometry direction.

20. The computer-implemented system of claim 11 , further comprising:

building the terrain surface based on the drain pattern.