Generating 3d structures using genetic programming to satisfy functional and geometric constraints

Patent metadata

Field	Value
Publication number	US-2019164342-A1
Application number	US-201715825959-A
Country	US
Kind code	A1
Filing date	Nov 29, 2017
Priority date	Nov 29, 2017
Publication date	May 30, 2019
Grant date	—

Abstract

Techniques are disclosed for generation of 3D structures. A methodology implementing the techniques according to an embodiment includes initializing systems configured to provide rules that specify edge connections between vertices and parametric properties of the vertices. The rules are applied to an initial set of vertices to generate 3D graphs for each of these vertex-rule-graph (VRG) systems. The initial set of vertices is associated with provided interaction surfaces of a 3D model. Skeleton geometries are generated for the 3D graphs, and an associated objective function is calculated. The objective function is configured to evaluate the fitness of the skeleton geometries based on given geometric and functional constraints. A 3D structure is generated through an iterative application of genetic programming techniques applied to the VRG systems to minimize the objective function. Receiving updated constraints and interaction surfaces, for incorporation in the iterative process.

First claim

What is claimed is:

1 . A method to generate a 3-dimensional (3D) structure, the method comprising:
receiving, by a processor-based system, one or more constraints relevant to a 3D structure to be generated, at least one of the one or more constraints derived from a designated interaction surface of a given 3D model; and generating, by the processor-based system, the 3D structure using the one or more constraints, including the designated interaction surface of the given 3D model, through iterative application of genetic programming to a plurality of vertex-rule-graph (VRG) systems to evolve the VRG systems based on the constraints.

2 . The method of claim 1 , wherein the generating further comprises:
initializing, by the processor-based system, the plurality of VRG systems, the VRG systems configured to provide rules that specify edge connections between vertices and property parameters of the vertices; applying, by the processor-based system, the rules of the VRG systems to an initial set of vertices to generate a plurality of 3D graphs, each of the 3D graphs associated with one of the VRG systems, wherein the initial set of vertices is associated with the designated interaction surface of the given 3D model; generating, by the processor-based system, a plurality of skeleton geometries, each of the skeleton geometries associated with one of the 3D graphs; calculating, by the processor-based system, an objective function for each of the skeleton geometries, the objective function configured to evaluate fitness of the skeleton geometries based on given constraints, the given constraints including the interaction surface of the given 3D model; and generating, by the processor-based system, the 3D structure through iterative application of genetic programming to a selected subset of the plurality of VRG systems, the genetic programming iterations to minimize the objective function.

3 . The method of claim 2 , wherein the genetic programming further comprises performing graph crossovers of the VRG systems and applying mutations to the rules and vertices of the VRG systems.

4 . The method of claim 2 , wherein the initializing further comprises initializing the rules of the plurality of VRG systems with randomized connections between the vertices and with randomized property parameters of the vertices, the initializing performed prior to a first iteration of the method.

5 . The method of claim 2 , wherein the VRG system rules specifying edge connections between vertices comprise at least one of a direction parameter, a distance parameter, a recursion limit parameter, and a symmetry flag.

6 . The method of claim 2 , wherein the VRG system rules specifying property parameters of the vertices comprise at least one of an active/inactive state flag of the vertex, orthonormal vectors defining a coordinate system of the vertex, and recursion counters for each of the rules to be applied to the vertex.

7 . The method of claim 2 , wherein the generating of the skeleton geometries further comprises replacing the edge connections of the 3D graphs with cylinders and replacing the vertices of the 3D graphs with spheres.

8 . The method of claim 1 , wherein the constraints further comprise at least one of a fitting volume, an avoidance volume, a symmetry requirement, a maximum total length of the edge connections, and a maximum mass of the 3D structure.

9 . The method of claim 1 , further comprising:
presenting the generated 3D structure for display; receiving one or more updated constraints, including one or more updated interaction surfaces; receiving weighting factors associated with the constraints including the one or more updated constraints; and iterating the method using the weighting factors and the one or more updated constraints.

10 . A system to generate a 3-dimensional (3D) structure, the system comprising:
one or more processors; a procedure generation module at least one of controllable and executable by the one or more processors, and configured to initialize a plurality of vertex-rule-graph (VRG) systems, the VRG systems configured to provide rules that specify edge connections between vertices and property parameters of the vertices; a procedure application module at least one of controllable and executable by the one or more processors, and configured to apply the rules of the VRG systems to an initial set of vertices to generate a plurality of 3D graphs, each of the 3D graphs associated with one of the VRG systems, wherein the initial set of vertices is associated with a designated interaction surface of a 3D model; a skeleton geometry generation module at least one of controllable and executable by the one or more processors, and configured to generate a plurality of skeleton geometries, each of the skeleton geometries associated with one of the 3D graphs; an optimization module at least one of controllable and executable by the one or more processors, and configured to calculate an objective function for each of the skeleton geometries, the objective function configured to evaluate fitness of the skeleton geometries based on given constraints, wherein the given constraints comprise at least one of a fitting volume, an avoidance volume, a symmetry requirement, the interaction surfaces, a maximum total length of the edge connections, and a maximum mass of the 3D structure; and a genetic programming module at least one of controllable and executable by the one or more processors, and configured to generate the 3D structure through iterative application of genetic programming to a selected subset of the plurality of VRG systems, the genetic programming iterations to minimize the objective function, wherein the genetic programming module is further configured to perform graph crossovers of the VRG systems and to apply mutations to the rules and vertices of the VRG systems.

11 . The system of claim 10 , wherein the procedure generation module is further configured to initialize the rules of the plurality of VRG systems with randomized connections between the vertices and with randomized property parameters of the vertices, the initializing performed prior to a first iteration of the genetic programming.

12 . The system of claim 10 , wherein the VRG system rules specifying edge connections between vertices comprise at least one of a direction parameter, a distance parameter, a recursion limit parameter, and a symmetry flag; and the VRG system rules specifying property parameters of the vertices comprise at least one of an active/inactive state flag of the vertex, orthonormal vectors defining a coordinate system of the vertex, and recursion counters for each of the rules to be applied to the vertex.

13 . A non-transitory computer program product having instructions encoded thereon that when executed by one or more computer processors cause the one or more computer processors to perform a process comprising:
receiving one or more constraints relevant to a 3D structure to be generated, at least one of the one or more constraints derived from a designated interaction surface of a given 3D model; and generating the 3D structure using the one or more constraints, including the designated interaction surface of the given 3D model, through iterative application of genetic programming to a plurality of vertex-rule-graph (VRG) systems to evolve the VRG systems based on the constraints.

14 . The non-transitory computer program product of claim 13 , wherein the generating further comprises:
initializing the plurality of VRG systems, the VRG systems configured to provide rules that specify edge connections between ve

Assignees

• Adobe Inc

Inventors

• Krs Vojtech
• Mech Radomir
• Carr Nathan A

Classifications

• G06T15/00

  Three-dimensional [3D] image rendering · CPC title

• G06T17/20 Primary

  Finite element generation, e.g. wire-frame surface description, {tesselation} · CPC title

• G06T17/10 Primary

  Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes · CPC title

• G06F30/00

  Computer-aided design [CAD] · CPC title

• G06T17/005 Primary

  Tree description, e.g. octree, quadtree · CPC title