# US 12,008,715 B2 · Determining drainage constraints and geometries in a triangular mesh > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,008,715 B2 - Document ID: US12008715B2 - Status: Granted - Kind: B2 - Application number: 17/682,891 - Filed: 2022-02-28 - Published: 2023-08-31 - Granted: 2024-06-11 - Earliest claimed: 2022-02-28 - Assignees: Autodesk, Inc. - Applicants: Autodesk, Inc. - Inventors: Valentin R. Koch; Weiwei Hu - Web page: https://patentgrep.com/patent/US12008715B2 ## CPC - G06T 17/20: Finite element generation, e.g. wire-frame surface description, {tesselation} - G06F 30/13: Architectural design, e.g. computer-aided architectural design [CAAD] related to design of buildings, bridges, landscapes, production plants or roads - G06F 30/23: using finite element methods [FEM] or finite difference methods [FDM] - G06T 17/05: Geographic models - G06T 17/205: {Re-meshing} - G06T 19/20: Editing of three-dimensional [3D] images, e.g. changing shapes or colours, aligning objects or positioning parts - G06F 2111/04: Constraint-based CAD - G06T 2219/2021: Shape modification - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method and system provide the ability to design a terrain surface. A triangular surface mesh representative of an existing surface is obtained and consists of triangles that are connected by vertices and edges. A drain intention is specified for the terrain surface through a geometry that is a point or line. The drain intention defines a drainage flow that influences a shape of the terrain surface. The mesh is modified using a Voronoi diagram that prevents a drain conflict between mesh triangles. A drain direction is autonomously determined a for each of the mesh triangles based on the drain intention. The determination generates a drain pattern that is used to shape the terrain surface. ## Claims ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 1) 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. ### Claim 8 (depends on 1) 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. ### Claim 9 (depends on 1) 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. ### Claim 10 (depends on 1) The computer-implemented method of claim 1, further comprising: building the terrain surface based on the drain pattern. ### Claim 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. ### Claim 12 (depends on 11) 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. ### Claim 13 (depends on 11) 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. ### Claim 14 (depends on 11) 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. ### Claim 15 (depends on 11) 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. ### Claim 16 (depends on 11) 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. ### Claim 17 (depends on 11) 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. ### Claim 18 (depends on 11) 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. ### Claim 19 (depends on 11) 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. ### Claim 20 (depends on 11) The computer-implemented system of claim 11, further comprising: building the terrain surface based on the drain pattern.