Part design system using a context-free grammar

[0001] This application claims priority to European patent application no. 03291846.8 filed Jul. 25, 2003.

[0002] The invention relates to the field of computers programs and system, and more specifically to part design programs and systems.

[0003] A number of systems and programs are offered on the market for the design of parts or assemblies of parts, such as the one provided by the applicant under the trademark CATIA. These so-called computer-aided design (CAD) systems allow a user to construct and manipulate complex three-dimensional (3D) models of parts or assembly of parts.

[0004] A number of different modeling techniques can be used to create a model of an assembly. These techniques include solid modeling, wire-frame modeling, and surface modeling. Solid modelling techniques provide for topological 3D models, where the 3D model is a collection of interconnected edges and faces, for example. Geometrically, a 3D solid model is a collection of trimmed surfaces that defines a closed skin. The trimmed surfaces correspond to the topological faces bounded by the edges. The closed skin defines a bounded region of 3D space filled with the part's material. Wire-frame modeling techniques, on the other band, can be used to represent a model as a collection of simple 3D lines, whereas surface modeling can be used to represent a model as a collection of exterior surfaces. CAD systems may combine these, and other, modeling techniques, such as parametric modeling techniques.

[0005] Parametric modeling techniques can be used to define various parameters for different features and components of a model, and to define relationships between those features and components based on relationships between the various parameters. Solid modeling and parametric modeling can be combined in CAD systems supporting parametric solid modeling.

[0006] A design engineer is a typical user of a 3D CAD system. The design engineer designs functional, physical and aesthetic aspects of 3D models, and is skilled in 3D modeling techniques. The design engineer creates parts and may assemble the parts into one or more subassemblies. In addition to parts, a subassembly may also consist of other subassemblies. Using parts and subassemblies, the design engineer designs an assembly. Hereinafter, parts and subassemblies are collectively referred to as “components”.

[0007] A part or component is constructed using various geometric building blocks, using tools generally provided in CAD systems. The order in which a design engineer creates features while constructing a part affects the physical structure of that part in a feature-based CAD. These systems are therefore history-based. For example, a part constructed first by cutting a block with a cylinder and then adding a boss that extends inside the void left by the cut cylinder will result in a hole with material from the boss inside the hole. If the order of the operations were reversed such that the boss was added before the cylindrical cut, then the cut would not only cut the material of the original block, but also that of the subsequent boss, resulting in a hole with no material inside of it. This is exemplified in FIGS. 1 to 3, which show a window displayed on the screen of a prior art CAD system. FIG. 1 shows a window 2 that contains three views of a part under construction. The top view 4, front view 6, and rotated view 8 reveal that the part is partially defined by two block features (i.e., upper block 12 and lower block 14). Additionally, the top view 4 and the front view 6 plainly show an extruded profile 10 of a circle. The purpose of the extruded profile 10 is to create a cylindrical cut feature in the part. FIG. 2 shows the window 2 after the extruded profile 10 was used to construct a cut feature. The cut 16 was created by subtracting material that was located within the extruded profile 10 from the upper block 12 and the lower block 14. The cut 16 would appear as illustrated in FIG. 2 in a history-based CAD system if the upper block 12 and the lower block 14 were included in the part definition (i.e., existed) prior to the inclusion of cut feature 16. FIG. 3 shows the window 2 containing a part in which a cut feature 18 did not subtract material from the upper block 12. The cut 18 may appear as illustrated in FIG. 3 in a history-based CAD system if the lower block 4 was included in the part definition first, the cut feature 18 was included in the part definition second, and the upper block was included in the part definition third. The example of FIG. 1-3 shows that the order in which features are entered for defining a component influences the output shape of the component. This discussion in reference to mechanical parts applies to other types of parts or components in a design system, e. g. moulded parts, electrical features in a circuit, or more generally any type of features the assembly of which forms parts or components.

[0008] EP-A-1 302 904 offers a solution to the problem of features order in such history-based CAD systems. It is based on the principle of separating feature creation order and feature regeneration order. Feature creation refers to the order in which a user adds features to a component; feature regeneration order refers to the order in which the geometric feature operations are applied to the underlying geometric model. This is achieved by associating to a given feature a feature scope, representative of the other features on which the given feature will have effects. The feature scope may be explicit—in which case the CAD system user would explicitly build a list of the other features on which a given feature will act. The feature scope may be implicit; it is then automatically defined by the system, based on a system of rules, e.g. relying on the order in which the features are introduced, on a proximity calculation or on attributes of the features. Explicit definition of feature scope creates an additional burden on the user. Implicit definition of feature scope is limited to a given number of pre-programmed rules. This document further discusses dynamically grouping and ordering features, according to the feature scopes, to build feature chains. A feature chain maintains three volumes; the first volume is a positive volume that combines all features that add material; the second volume is a negative volume that combines all features that remove material. The third volume combines the positive and negative volume. Features chains are created and represented by features trees; these trees are created taking into account the feature scopes. The system is thus dependent on feature scopes for building feature trees. More generally, the solution proposed in this patent to tantamount to changing a temporal complexity—the order in which features are defined—into scopes. However, defining scopes may be as complicated as defining a proper order for features.

[0009] US-A-2002/0133803 discusses a horizontally-structured CAD-CAM modelling system. This document suggests defining datum plane and linking new features to the datum planes. Thus, features are supposed to be amendable independently of each other. This solution makes it necessary for the user to define datum planes and to decide, for each new feature, to which datum plane the feature should be attached. This solution makes it possible to amend some features independently of other features. However, it does not address the problem of temporal order of features, as discussed above. Referring again to the example of FIGS. 1-3, the fact that the upper block, the lower block and the extruded profile are “attached” to the same datum plane does not change the fact that the order in which these features are defined may change the resulting part or component.

[0010] Other systems are proposed, which are not history dependent. These include systems relying on boundary representation modelling. The system only stores the boundary representation and not the sequence of actions of the user for defining the representation. A problem with these systems is that they hardly allow the user to modify or amend already designed structures. More specifically, these systems may provide tools for helping the user in generating new structures; these tools extrapolate the existing boundaries and only operate for limited changes to the boundaries. They also rely on a limited series of pre-programmed changes. FIG. 4 is an example of a cross-section of a part in a boundary representation modelling. The part is a volume 20 in which a hole 22 is drilled; the hole has a shape defined by the revolution of a curve 24 around an axis 26 and by a bottom 28. A displacement of the bottom 28 of the hole toward the position 30 represented in dotted lines may be allowed by the system—if the bottom is identified as a line by the system. If this is not the case, moving the bottom may involve fully re-designing the bottom. In addition, if the bottom is moved, the lower part of wall 24 needs to be extended. This may involve re-designing the lower part of the wall. On the contrary, in a history-based system, the lower part of wall 24 could be defined as a relimitation of a conical surface and would be easily extended, simply by “replaying” the design scenario—“replaying” the relimitation step. This example demonstrates some of the advantages of history-based systems: they capture the design intention of the end-user; in other words, they reflect successive design steps. History based systems also allow easy a posteriori changes.

[0011] Thus, there exists a need for a CAD system, which would be simpler to use and still provide the advantages of history-dependent systems. The system should preferably be easy to adapt to the needs of the user and to the field of the art where it is used.

[0012] According to the invention, there is provided a system for designing parts or assemblies of parts, with

• [0013] (a) a history-based design system having a storage format with primitives and operations, a part or assembly of parts being defined in the history based design system by an ordered sequence of operations and primitives;
• [0014] (b) at least two functional features, each of which is adapted to be instantiated by a end user by providing a set of specifications, an instantiated functional feature providing at least a contribution, a contribution being an ordered sequence of operations and primitives of the history-based design system;
• [0015] (c) a seed structure defined using a context-free grammar, the seed structure being adapted to receive contributions from instantiated functional features, to order operations and primitives of received contributions and to provide an ordered sequence of operations and primitives to the history based system;
• [0016] (d) an editor for editing the seed structure in said grammar.

[0017] The operations may comprise commutative operations and non-commutative operations; the seed structure would then have inputs adapted to receive contributions. The seed structure would be adapted to apply commutative operations to the contributions received on each input and to apply commutative or non-commutative operations to the results of the commutative operations applied to said contributions.

[0018] The seed structure is preferably represented in the context-free grammar as an acyclic oriented graph. It may be a binary tree, or a non-binary tree.

[0019] A terminal alphabet of the context free grammar preferably comprises at least a solid, union, intersection and subtraction. One may add juxtaposition to the terminal alphabet.

[0020] In one embodiment, the terminal alphabet of the context free grammar comprises curves, surfaces and relimitation.

[0021] The invention also provides a process for providing a history-free system for the design of parts or assemblies of parts, the process comprising the steps of

• [0022] (a) providing a history-based design system having a storage format with primitives and operations, a part or assembly of parts being defined in the history based design system by an ordered sequence of operations and primitives;
• [0023] (b) providing at least two functional features, each of which is adapted to be instantiated by a end user by providing a set of specifications, an instantiated functional feature providing at least a contribution, a contribution being an ordered sequence of operations and primitives of the history-based design system;
• [0024] (c) using a context-free grammar to define a seed structure, the seed structure being adapted to receive contributions from instantiated functional features, to order operations and primitives of received contributions and to provide an ordered sequence of operations and primitives to the history based system.

[0025] In one embodiment, the operations comprise commutative operations and non-commutative operations; the step of using comprises providing a seed structure having inputs adapted to receive contributions and the seed structure adapted to apply commutative operations to the contributions received on each input and to apply commutative or non-commutative operations to the results of the commutative operations applied to said contributions.

[0026] The step of using preferably comprises defining the seed structure as an acyclic oriented graph; the seed structure may then be defined as a binary or non-binary tree.

[0058] In the rest of this specification, the words “part” or “assembly of parts” is used to designate an object modeled or designed in a computer-aided design system.

[0059] In reference to FIG. 5, the general structure of a system according to the invention is discussed.

[0060] Explanations are provided in reference to FIGS. 6 and 7, as regards context free grammars.

[0061] A first embodiment of the invention is discussed in reference to FIGS. 8-18; the invention is applied to the modeling of thin solids.

[0062] A second embodiment of the invention is discussed in reference to FIGS. 19-20. The invention is applied to the concurrent modeling of thin solids with the corresponding moulds.

[0063] A third embodiment of the invention is discussed in reference to FIG. 21-30 and 35. A generic context-free grammar is disclosed, which makes it possible to represent seed structures in non-binary trees.

[0064] Last, a fourth embodiment of the invention is discussed in reference to FIGS. 31-34. This embodiment allows a fast evaluation of the modeled object in a B-rep evaluator.

[0065] The invention makes it possible for the user of the CAD system to design parts or assemblies of parts without worrying about feature order. In essence, the system provided by the invention is a history-free design system. However, it includes a history based design system and therefore provides the advantages of such systems, as discussed above. It thus captures the design-intention of the user and permits a posteriori changes.

[0066] This is achieved by providing in the system

• • [0067] a history-based or history dependent computer-aided design system;
  • [0068] a set of functional features, that are accessed and instantiated by the end-user and
  • [0069] a seed structure.

[0070] In the history-based design system, modeled objects are defined by an ordered sequence of operations and primitives. The system is adapted to receive data in the form of such ordered sequences. Examples of primitives—blocks—are given in reference to FIG. 1-3 in a design system adapted for the modeling of solid objects. Examples of operations include assembling, e.g. as applied to the two blocks of FIG. 1, or cutting, e.g. as applied in FIGS. 2 and 3 at various stages. The importance of the order in the sequence is exemplified in reference to FIGS. 1-3. Such history-based design systems are well known to the person skilled in the art and include the CATIA system referred to above. Primitives and operations available in such systems are also known to the person skilled in the art.

[0071] The history based system is represented at 40 in FIG. 5 and is not further detailed. It is sufficient to say that this system 40, also referred to as the “core system” in the rest of the specification is adapted to receive an ordered sequence of primitives and operations. It may then evaluate the received sequence to compute a modeled object, display the modeled object to the user, store the sequence or provide any additional handling of the received ordered sequence. One may use in this system a B-rep type evaluator. A B-rep type evaluator is a geometrical and topological algorithm that computes the boundary description of the resulting solid from the boundary descriptions of the input solids.

[0072] The system of the invention 42 is history-free and declarative. It comprises a end-user interface 44; this interface provides the end-user with the ability of selecting functional features out of the set of functional features and instantiating the selected functional feature with parameters. This is schematically represented in FIG. 5 by parameters 46 and selected functional features 48, which are input to end-user interface 42. Functional features represent design functions that are relevant for the field of the art at stake. For instance, if the design system is applied to the design of solids, functional features could comprise housings, through holes, blind holes. Other examples of functional features are discussed below. A given functional feature may be instantiated by providing parameters or values relevant for the selected functional feature. For instance, a housing could be instantiated by providing the following parameters: a profile, a height and a thickness. A through hole could be instantiated by providing a positioning point, an axis and a diameter. A blind hole could be instantiated by providing a positioning point, an axis, a diameter as well as a depth. A discussed below, the set of functional features may be adapted by an expert user.

[0073] User interface 44 outputs contributions 50, which are applied to the seed structure 52. Contributions are discussed in detail below. In essence, an instantiated functional feature input to the end-user interface 44 provides at least one contribution output by interface 44. A contribution is an ordered sequence of primitives and operations of the core system; a contribution is applied on a given input of the seed structure, as discussed below.

[0074] Contributions are applied to the seed structure 52. The seed structure receives contributions and based on the received contributions, provides to the core system 40 a data flow 54 which is an ordered sequence of primitives and operations, adapted to be handled by the core system. More specifically, the seed structure receives contributions and handles these contributions, by applying operations on the contributions or adding additional primitives. The seed structure does not separate or break a given contribution; in other words, a given contribution inputted to the seed structure is found in the resulting sequence provided by the seed structure.

[0075] The seed structure is built so that the order in which contributions are received does not change the result output by the seed structure, or more specifically, the evaluation of this result by the core system. This property of the seed structure is ensured since

• • [0076] rules used for applying contributions to the seed structure are commutative;
  • [0077] each contribution is kept intact by the seed structure.

[0078] In essence, the end-user is provided with tools—the functional features—which appear to be commutative. The functional features may thus be instantiated by the end-user in any order. Non-commutative operations are either contained within contributions or are carried out by the seed structure. Since contributions are not split or broken in the seed structure, the order of primitives and operations in the contributions is not amended by the design system. Since the ordering in the seed structure is not user-dependent, non-commutative operations in the seed structure provide a result which is not user dependent.

[0079] In addition, the system is provided with an editor for editing the seed structure, which is represented schematically at 56 in FIG. 5. This editor makes it possible for an expert user to amend the seed structure and adapt it to the specific requirements of a given field of the art in which the design system is used. The seed structure is defined in a context-free grammar and may be edited in this grammar. Respecting syntactic rules in this grammar ensures that the seed structure will always keep the property of ordering the various contributions to provide the same evaluation of the output data flow in the core system 40, irrespective of the order in which the functional features are instantiated by the end-user.

[0080] In a preferred use of the invention, the expert user is a high skilled designer. He knows very well the technical field (sheet metal aerospace, machined parts for aerospace, automotive power train, ect.) as well as the CAD system behavior and limitations (manifold or non manifold solids, linear Constructive Solid Geometry structure, balanced Constructive Solid Geometry structures etc.). The end user is the mechanical designer and is provided with the various functional features. The way rights may be granted to users in a computer system is known to the person skilled in the art and is not detailed further.

[0081] As shown by arrow 58 in FIG. 5, the editor may also allow an expert user to change the set of functional features, e.g. for adding new functional features.

[0082] System 42, from the perspective of the end-user, has the advantages of allowing easy modeling of objects. First, there are provided functional features, adapted to the field of the art, which facilitate object modeling. Second, the order in which the functional features are instantiated is not relevant to the resulting modeled object.

[0083] System 42 has the further advantage of being easily adapted to the field of the art, by editing the seed structure. This makes it possible to use the same design system for various fields of the art, while allowing an expert-user to customize the system. Several examples of seed structures are defined below. In the example of FIGS. 8-15, the seed structure is adapted to the design of thin plastic parts. In the example of FIGS. 16-17, the seed structure makes it possible to design at the same an upper and a lower mold. The description further gives the example in reference to FIGS. 27-30 of a seed structure adapted to optimize evaluation of modeled objects, in the case where interim results are stored. According to the capabilities of the core system, the seed structure may thus be adapted.

[0084] The editor makes it possible to adapt an existing seed structure to make it more efficient, according to the capabilities of the core system, without changing its function. The editor also makes it possible to increase the functional capabilities of a seed structure in a given application. For instance, the editor makes it possible, for solids, to design concurrently a solid component and its mould, as exemplified below. It makes it possible to design at the same corresponding elements of an assembly, e.g. the two parts forming a housing with their linkage. The editor also makes it possible for the expert user to create a seed structure adapted to a given application. For instance, in naval construction, walls, openings, strengthening members are combined with specific relimitations. A seed structure may be designed in the editor for capturing the design methodology used in this field. More generally, any design process used in a CAD system may be captured in a seed structure and its associated functional features.

[0085] In addition, as discussed below, the editor may allow the expert user to amend existing functional features or create new functional features.

[0086] The system of the invention further allows concurrent engineering. Concurrent engineering is the art to coordinate several designers working at the same time on a shared part or assembly. Each designer is supposed to modify the (shared) part and is also supposed to receive modifications from other designers. The key point is to reconcile the modifications. In prior art systems, this is an issue, inasmuch the order in which modifications from each designer is carried out may impact the resulting modelled object. The order independency between design changes in the invention allows straightforward merges of modifications or additions carried out by each designer.

[0087] Context-free grammars are now discussed briefly, before exemplifying the invention. Details on context-free grammars may be found in Introduction to Automata Theory, Language and Computation, J. E. Hopcroft and J. D. Ullmann, Addison-Wesley, 1979. Although this reference discusses context-free grammars, it does not provide any suggestion to use such grammars in computer aided design systems.

[0088] A context-free grammar G is defined by G=(X, V, P) where X is a set of terminal symbols, V is a set of non-terminal symbols and P is a set of rules. A rule is a couple (S, m) where the first object is a non-terminal symbol and the second object is a string made of terminal and non-terminal symbols; more precisely, P is a subset of V×(X∪V)*. A rule is also written as S m; in other words, a rule changes a non-terminal symbol into a string made of terminal and non-terminal symbols. Using a context-free grammar makes it possible to recursively produce words in a well-defined syntax as well as algorithms to scan these words, check the syntax and launch computations. In this respect, the function of a non-terminal symbol is to be replaced by a string made of terminal and non-terminal symbols—thanks to a function. A sequence of symbols in the grammar is now called a word.

[0089] The seed structure 52 is defined and edited in a context-free grammar. As such, it is merely a word in the context free grammar. The grammar first provides a formal and rigorous environment for defining seed structures; checking syntax of a seed structure edited in editor 56 makes it possible to avoid that the end-user violates syntactic rules. This is fully independent of the field of the art in which the system 42 is used.

[0090] The use of a context free grammar makes it easy to input contributions to the seed structure, by using recursive functions. Specifically, the seed structure is a word comprising a number of terminal and non-terminal symbols, which are used for applying contributions to the seed structure; the non-terminal symbols could be understood as “inputs” to the seed structure, the terminal symbols are used to specify the operations that combine the objects (solid objects in the examples). In this respect, applying a contribution to the seed structure can be carried out merely by replacing a non-terminal symbol of the seed structure by a contribution; assuming a contribution is a word, this is simply a given rule of the grammar. For ensuring recursivity—the ability to apply any number of contributions to the seed structure—it is sufficient to apply a contribution to the seed structure by replacing a non-terminal symbol of the seed structure by a sequence comprising not only the contribution but also the replaced non-terminal symbol. In the rest of this specification, a rule in which the replaced non-terminal symbol appears in the replacing string is called a substitution. Using this definition of a substitution, a contribution is applied to the seed structure by using a substitution for changing a non-terminal symbol of the seed structure into a word comprising the non-terminal symbol and the contribution. This ensures that the resulting word still comprises the non-terminal symbol, to which an additional contribution may again be applied. This further ensures that the structure of the seed structure is preserved throughout the inputting of contributions.

[0091] Using a context-free grammar further makes it easy for the expert-user to ensure that the system 42 remains declarative: it is sufficient to check that substitution rules, which allow contributions to be applied to the seed structure, remain commutative.

[0092] The simplest context-free grammar used in this invention is now discussed in reference to FIGS. 6 and 7. This grammar is defined as follows:
X={a,φ}
V={S}
P={SSSφ,Sa}
Symbol a is the first terminal symbol and it represents any solid—defined in the embodiment by a contribution or by an ordered sequence of primitives and operations of the core system. Symbol φ is the second terminal symbol and represents any operation, such as the operation of union (+), subtraction (−) and intersection (·). Non-terminal symbol S may be replaced by a sequence of non-terminal symbols and terminal symbols, using the rules contained in the set P of rules. Specifically, the first rule SSSφ replaces a non-terminal symbol S by the result of the operation φ between two non-terminal symbol. This result is noted SSφ, which is simply a more compact way of saying SφS. In terms of trees, the first operation replaces a leaf S of a tree by a node having two branches. The node is the result of the operation φ on two non-terminal symbols located at the end of the branches. The second operation S a replaces a non-terminal symbol by a terminal symbol and is typically used when a given value—a terminal symbol—is to be applied to a leaf of the tree.

[0093] The syntax of a word produced with this grammar may be checked by the pushdown automaton represented in FIG. 6. In this figure, state 1 is the initial status; state 2 is the final status. The syntax is correct if the automaton reaches the final status after reading the last symbol, otherwise, it is not. The person skilled in the art of formal languages understands that the syntax of any word in the grammar may be checked easily.

[0094] FIG. 7 is an example of a binary tree coded in this grammar. This tree is coded by the word abc+d−− which is a compact way of saying a−((b+c)−d). This tree is produced through the following sequence of grammar rules:
SSS−aS−aSS−−aSd−−aSS+d−−abS+d−−abc+d−−
In other words, one starts from a non-terminal symbol S; the first operation is applied for replacing the non-terminal symbol by a tree having two branches 60 and 62 with a − operation at the root. The second operation is applied to replace the non-terminal symbol S in the leaf of first branch 60 of the tree by a terminal symbol a. The first operation is then applied to the remaining non-terminal symbol in the leaf of branch 62, which is replaced by a tree having two branches 64, 66 with a − operation at the root. The second operation is applied to replace the non-terminal symbol S in the leaf of branch 66 of the tree by a terminal symbol d. The first operation is then applied to the non-terminal symbol in the leaf of branch 64, which is replaced by a tree having two branches 68, 70 with a + operation at the root. The second operation is applied twice to replace the non-terminal symbols S in the leaf of branches 68, 70 by terminal symbols b and c. In the example of FIG. 7, non-terminal symbol S does not appear any more, since all instances of S were replaced by a tree or a terminal symbol. In the description of FIG. 7, symbol a is used for describing the terminal symbol; it is also used as one of the possible solids a, b, c and d.

[0095] FIGS. 8-18 exemplify a design system in a first embodiment of the invention; the seed structure in this first embodiment is represented as a binary tree. For the sake of explanation, the design system is applied to the design of thin solids, such as injection-moulded plastic parts. Two functional features are provided; the first functional feature is a thin bloc and the second functional feature is a fixture.

[0096] FIG. 8 is a schematic view of a seed structure in this example. The seed structure of FIG. 8 derives from the consideration that a thin solid is structured by the subtraction of two solids; the first one is the external shape of the thin solid and the second one is the internal shape of the thin solid. A mechanical function on a thin solid can be decomposed in the following five basic operations:

• • [0097] add material to the external shape,
  • [0098] remove material from the external shape,
  • [0099] add material to the internal shape,
  • [0100] remove material from the internal shape and
  • [0101] remove material from the overall shape so that it can never be filled again.
    The seed structure represents the fact that the basic operations are carried out in the following order:
  • [0102] define the external shape by adding material to the external shape and removing material from the external shape,
  • [0103] define the internal shape by adding-material to the internal shape and removing material from the internal shape,
  • [0104] remove the internal shape from the external shape and
  • [0105] remove material from the overall shape so that it can never be filled again.
    Using this order of operations will always leads to the same resulting solid.

[0106] The seed structure may be defined in the following context-free grammar G₀=(X, V, P) where
X={a,+,−,·}
V={S,e⁻,e⁻,i⁺,i⁻,u}
P={Se⁺e⁻−i⁺i⁻−−u−}∪{zza+,zε{e⁺,e⁻,i⁺,i⁻,u}}
This context-free grammar is an elaborated version of the grammar disclosed in reference to FIGS. 6 and 7. As above, the first terminal symbol a represents any solid. The second, third and fourth terminal symbols +,−,· respectively stand for union, subtraction and intersection. The first non-terminal symbol S is generic; non-terminal symbols e⁺,e⁻,i⁺,i⁻ and u are used for the sake of convenience, for representing the input of contributions in the five operations listed above; they could be qualified as “handles”. Specifically, non-terminal symbol e⁺ is used for adding material to the external shape, etc. The geometrical evaluation of non-terminal symbols e⁺,e⁻,i⁺,i⁻ and u is the empty set so the geometrical shape of the seed structure is the empty set.
This allows the cohabitation with actual solids in the binary tree; in other words, non-terminal symbols e⁺,e⁻,i⁺,i⁻ and u may remain in the ordered sequence provided at the output of the seed structure, without this having any consequence on the solid obtained.

[0107] The first operation in the formal grammar consists in providing the seed structure. The generic symbol S is replaced by the seed structure of FIG. 8, which is written as e⁺e⁻−i⁺i⁻−−u−. The leaves of the tree forming the seed structure are the symbols “e⁺”, “e⁻”, “i⁺”, “i⁻” and “u”. These leaves correspond to the five operations discussed above, in the order given above. In the seed structure, symbol “−” stands for subtraction. The tree structure may be described as follows. In node 80 of the tree, material removed from the external shape (leaf e⁻) is subtracted from material added to the external shape (leaf e⁺). The result is noted e⁺e⁻−in a compact representation. In node 82 of the graph, material removed from the internal shape (leaf i⁻) is subtracted from material added to the internal shape (leaf i⁺). The result may again be noted i⁺i⁻−. In node 84 of the graph, the result i⁺i⁻−of node 82 is subtracted from result e⁺e⁻−of node 80, thus leading to the result noted e⁺e⁻−i⁺i⁻−−in a compact representation. Practically speaking, this is tantamount to subtracting from the external shape the internal shape of the thin solid. In node 86 of the graph—which is the tree root—the material to be removed from the overall shape is subtracted from the result of node 84. This is noted e⁺e⁻i⁺i⁻−−u−

[0108] The second set of operations comprises the substitution operations, each of which consists in replacing one of the non-terminal symbols by a sequence containing a contribution and the replaced non-terminal symbol. Applying at least one substitution to the “handles” provides a modelled object.

[0109] As discussed above, the substitutions have the first property of preserving the seed structure, in that the replaced non-terminal symbol is still available after the substitution is applied, so as to allow further contributions to be applied. In addition, the substitutions have the second property that they do not change the resulting modelled object, whatever the order in which the contributions are applied. For instance,
e⁺b+c+e⁻−i⁺i⁻−−u−
is obtained by adding materials b and c in this order to the external shape. The modelled object is the same as
e⁺c+b+e⁻−i⁺i⁻−−u−
which is obtained by adding materials c and b, in this order, to the external shape. Thus, thanks to the fact that the second set of operations—substitutions—are commutative, functional features may be instantiated in any order. The resulting solid is independent from the order in which the functional features are instantiated.

[0110] As discussed above, the exemplary seed structure of FIG. 8 may be amended by an expert user. Examples of amended seed structures are provided below. For amending the seed structure, one may use the following grammar G₁:
X={a,+,−,·}
V={S,e⁺,e⁻,i⁺,i⁻u}
P={zzzφ,zε{S,e⁺,e⁻,i⁺,i⁻,u},φε{+,−,·}}∪{za}
This grammar actually “includes” grammar G₀, as defined above, and represents a “meta-granmmar”. This meta-grammar makes it possible to define any seed structure. Contrary to grammar G₀, it does not guaranty that the system remains declarative. Indeed, grammar G₁ makes it possible to define non-commutative substitutions. Grammar G₁ may be used for checking the syntax of a seed structure amended or created by the expert user: this makes it possible to change the seed structure discussed above (e⁺e⁻−i⁺i⁻−−u−) to another seed structure. Grammar G₀—or the amended version thereof—uses commutative substitutions and ensures that the overall system is declarative and history-free.

[0111] FIG. 9-18 show examples of a modelled object obtained using the seed structure of FIG. 8 and various functional features. The first functional feature used in the example is a basic thin bloc. It is defined by a planar profile and an extrusion length. The thickness is a predefined value attached to the mechanical part under design. Each functional feature does not redefine it. This convention is advantageous for the design of thin plastic parts, but could be done without. Assuming the thickness is defined for a given object, the functional feature may be implemented by the end-user, by providing a profile and an extrusion length.

[0112] By convention, in this example, the bottom face is the default open face. Consequently, the thin bloc is defined by two extruded solids A and B easily created from the input data: profile, height and thickness. Extruded solid A represents the material added to the external shape, that is the contribution applied to leaf e⁺; extruded solid B represents the material added to the internal shape—and removed from the internal shape in the seed structure, that is the contribution applied to leaf i⁺. Contributions A and B are defined by the end-user interface 42, based on the information provided by the user.

[0113] FIG. 9 shows contributions A and B; contribution A is a solid having an outside shape corresponding to the planar profile and a length L corresponding to the extrusion length; contribution B is a solid having an outside shape corresponding to the planar profile—minus the predefined thickness and the same length L. As discussed, contribution A is applied to leaf e⁺ using operation e⁺e⁺A+, while contribution B is applied to leaf i⁺, using operation i⁺i⁺B+. Thus, starting from the seed structure and creating a thin bloc yields the word e⁺A+e⁻−i⁺B+i⁻−−u− that is equivalent to the tree of FIG. 10. This tree yields, through a standard evaluator in the history based system, the modelled object of FIG. 11. Notice that during this evaluation, A+e⁺=A and B+i⁺=B in the evaluator.

[0114] This first example of functional feature makes it clear that the contributions applied to entries of the seed structure are defined based on the various inputs of the user. The end-user does not have to care about the various contributions. The only input of the end-user relates to the functional features and the parameters of these functional features.

[0115] The second functional feature used in this example is a fixture feature, represented in FIG. 12. It is defined by a point in space, by a direction and a hole type; these various parameters are entered by the end-user, when embodying the functional feature. It is again assumed that the thickness is fixed for the given modelled object, otherwise this could be one additional parameter. One may use for defining the point in space and the direction the methods discussed in the prior art, e.g. datum plane and the like, as discussed in US-A-2002/0133803.

[0116] This fixture functional feature adds a drilled circular bloc and an appropriate space reservation to the part so that the assembly is easy. The fixture results in a number of contributions, referenced C, D, E, F and G in FIG. 12. The contributions are defined according to the parameters of the functional feature entered by the end-user.

[0117] The first contribution removes material from the external shape; this material is noted C on FIG. 12 and the contribution is applied to leaf e⁻ of the seed structure, using function e⁻e⁻C+; contribution C actually removes from the external shape a conical section, extending from the top of FIG. 12 to the upper disk of contribution F. The second and third contributions D and E remove material from the internal shape; they are applied to the leaf i⁻ of the seed structure, using the functions i⁻i⁻D+ and i⁻i⁻E+). One should note at this stage that the order in which the second and third contributions are applied is of no importance to the resulting modelled object. The fourth contribution F adds material to the external shape, on leaf e⁺, using function e⁺e⁺F+. The fifth contribution G permanently removes a drilled area, using function uuG+. By definition, a drilled area cannot be filled by material in any case. The role of the u symbol is to capture this property.

[0118] A fixture created on the current part leads to the updated word e⁺F+A+e⁻C+−i⁺B+i⁻E+D+−−uG+−. This word is equivalent to the binary CSG tree represented in FIG. 13. The corresponding modelled object appears in FIG. 14. Note again that the order in which the various contributions are applied to the leaves of the seed structure is of no relevance to the evaluated modelled object. In other words, the following word e⁺A+F+e⁻C+−i⁺B+i⁻D+E+−−uG+− provides the same modelled object when evaluated in the history-based design system.

[0119] An additional data structure may be used for maintaining the link between the mechanical functions and the related basic solids. In the example, there may be a link between the thin solid feature and contributions A and B. There is a link as well between the fixture feature and contributions C, D, E, F and G. This makes it possible to maintain, for the end-user, the fact that several contributions—e.g. contributions A and B—actually stems from the instantiation of a given functional feature. Amendments to the functional feature would then change the various affected contributions.

[0120] It should also be noticed that there is no dependency between the various instantiated functional features—in the example the thin solid of FIG. 11 and the fixture of FIG. 12. From the system point of view, the fixture can exist without the thin solid. The thin solid can be deleted; the part is still valid from the syntactical and topological points of view. This is exemplified in FIGS. 15 to 17. In FIGS. 15 and 16, the fixture is instantiated in the middle of the solid. The perspective view of FIG. 15 shows the inside of the resulting thin solid with the fixture; it shows the contribution F added to the outside shape and the contribution D removed from the internal shape; the line on FIG. 15 between contributions D and F is only represented for the sake of clarity, but does not exist in the modelled object produced by the evaluator. FIG. 16 shows the upper side of the resulting thin solid with the fixture. It shows the contribution C removed from the external shape. In FIG. 17, the fixture is instantiated outside of the thin solid. Thus, contributions C, D and E do not remove any material, since they are applied in a location where there is no material to remove. Contribution F adds material to the external shape, in the form of a disk separate from thin solid A of FIG. 6. Contribution G removes material from the disk added in contribution F, so that the resulting fixture is solely a separate drilled disk. From a technical standpoint, the addition of material outside of the thin solid may appear nonsensical. From a syntactical or topological standpoint, the resulting modelled object is correct. The examples of these figures show that the fixture may be instantiated in any position, without syntactical errors. The resulting object may always be evaluated by the core system.

[0121] Furthermore, rounds, fillets and drafts can be added to basic solids. This does not change the syntax since a rounded (or drafted or filleted) basic solid behaves like a basic solid. The parameters of these additional features can be included in the functional feature definition. For example, a rounded and drafted thin solid yields the part represented in FIG. 18.

[0122] The role of the expert user and end user is illustrated through the previous example. The expert user who knows very well the thin plastic part industry designs:

• • [0123] the seed structure;
  • [0124] the functional features.
    All the functional features may be available for the end-user in a dedicated “Thin Plastic Part” workbench. The end-user opens this workbench and designs thin parts using exclusively predefined declarative functional features.

[0125] The embodiment of FIGS. 8-18 only provides two functional features. More functional features could be defined by an expert user. For instance, in the example of thin plastic solids, one could provide other types of fixtures. A functional feature comprises on one hand the parameter(s) provided to the end-user for instantiating the functional feature. On the other hand, the functional feature comprises the various contributions to be applied to the seed structure. Each contribution is defined according to the parameters inputted by the end-user. An expert-user may define any number of functional features.

[0126] The operation of the system is explained in reference to FIGS. 8-18. The expert user first defines the seed structure and the functional features. The end-user instantiates one or more of the functional features. This results in contributions being applied to the seed structure, see FIGS. 8, 10 and 13; due to recursivity of the substitution, new contributions may always be added. At any time, the corresponding word (or the corresponding tree structure) may be evaluated in the history-based design system. For the end-user, the system appears to be history-based. However, as discussed above, any of the functional features may be amended, independently of the order in which the features are instantiated; as discussed above, this is due to the fact that the seed structure and the contributions are built so that the order in which the contributions are applied to the seed structure is irrelevant to the modelled object.

[0127] A second embodiment is disclosed in reference to FIG. 19 and 20. This embodiment makes it possible to design at the same time a part and the mould for this part. The seed structure and the contributions of FIGS. 8-18 may be used for the part. In addition, additional seed structures are provided for the upper and lower matrices of the mould.

[0128] The context free grammar in this embodiment is similar to the one discussed in reference to FIGS. 8-18. There are provided additional terminal symbols and functions:
X={a,+,−,·}
V={S,U,L,e⁺,e⁻,i⁺,i⁻,u}
P=P₀∪P₁∪P₂
P₀={Se⁺e⁻−i⁺i⁻−u−}∪{zza+,z ε{e⁻,e⁻,i⁺,i⁻,u}}
P₁={SUe⁺−e⁻+}
P₂={SLi+i⁻−}

[0129] The starting shapes for the upper and lower matrices are defined as U and L; these are non terminal symbol in the exemplified context free grammar; they could of course be defined by a specific functional feature. These shapes are examples of the simplest mould, with an upper matrix U and a lower matrix L. The shape of these matrices is the end user's responsibility, especially the join surface definition.

[0130] The additional functions in P₁ and P₂ provide the seed structures for the upper and lower matrices. These seed structures are shown in FIGS. 19 and 20. The seed structure for the upper matrix in FIG. 19 is defined by the word U e⁺−e⁻+; U is the starting shape for the upper matrix. “Handles” e⁺, e⁻ have the same meaning as in the embodiment of FIGS. 8-18. The seed structure for the lower matrix in FIG. 20 is defined by the word L i⁺+i⁻−; L is the starting shape for the upper matrix; “handles” i⁺ and i⁻ are the same as in the previous embodiment. Contributions from an instantiated functional feature are applied, at the same time, to the three trees.

[0131] Specifically, assume a thin solid is defined, as discussed above in reference to FIGS. 9-11. Contribution A to the external shape is applied as discussed above in reference to FIG. 10. It is also applied to the tree of FIG. 19, leading to the word U A e⁺+−e⁻+. In other words, the external shape of the thin part is removed from the upper mould U. Contribution B to the internal shape is applied, as discussed above in reference to FIG. 10. In addition, this contribution is applied to the tree of FIG. 20, leading to the word L B i⁺++i⁻−; this means that the internal shape of the thin solid is added to the lower mould L. One understands at this stage that the upper and lower moulds are defined at the same time as the parts themselves, simply by providing addition words or seed structures for the upper and lower moulds. One understand that contributions are the same as those defined above; however the seed structure comprise three separate words for the modelled object, the upper mould and the lower mould.

[0132] Assume now the second functional feature is instantiated for adding a fixture. The tree of FIG. 19 would become U A Fe⁺++−C e⁻++, while the tree of FIG. 20 would become L B i⁺++D i⁻+E+−. This example shows that the seed structure may comprise several words, for designing concurrently the part as well as the upper and lower moulds.

[0133] Thus, instantiating a new functional feature in the part automatically updates the shape of the upper and lower matrices. Notice that the u non-terminal symbol does not appear in the mould structures since the machining features do not appear on the part right out of the mould.

[0134] The example of FIGS. 19-20 shows that letting the expert-user amend the seed structure makes it possible for this expert-user to adapt the design systems to his needs.

[0135] FIGS. 21-29 exemplify a design system in another embodiment of the invention; the system in this embodiment uses a non-binary tree. The non-binary tree makes it possible to provide a simpler and shorter seed structure. The generic non-binary context-free grammar is disclosed in reference to FIGS. 21-24. A first example of a tree structure using a specific non-binary context free grammar is disclosed in reference to FIGS. 24-26. A second example of use of a non-binary tree is disclosed in reference to FIGS. 27-28. The description in reference to FIG. 29 disclose the same seed structure as in FIGS. 8-18, using non-binary trees.

[0136] The following context free grammar is used in this embodiment. The grammar is G_T=(X, V, P) where
X={a,δ}
V={S,T}
P={SSTδS,TSTδ,Sa,T1}

[0137] Terminal symbol a represents any node of the tree. Terminal symbol δ is a syntactical feature that counts the number of children nodes under a parent node; it is used for building the tree. At this level of abstraction, there is no distinction between operand symbols and operation symbols. This specialization is done by the application that uses the grammar. This explains that the set of terminal symbols, contrary to the example provided above, does not contain any “operation”.

[0138] Non-terminal symbol S may be replaced by a sequence of non-terminal symbols and terminal symbols, using the rules contained in the set P of rules. Non-terminal symbol T is used for the sake of adding branches to the tree and with terminal symbol δ, for counting branches in a tree. In other words, non-terminal symbol T makes it possible to allow a substitution at any place in a tree.

[0139] First rule SSTδS replaces non-terminal symbol S by a tree with one branch. Second rule SSTδ adds one branch to node S of the tree. Third rule Sa replaces a non-terminal symbol by a terminal symbol and is typically used when a given value—a terminal symbol—is to be applied to a node of the tree. Fourth rule T1 replaces non-terminal symbol by a 1, thus deleting non-terminal symbol T from the seed structure. This fourth rule is used when there is no need to add more branches to a given node, notably when the tree is completed.

[0140] Clearly, any binary tree is compliant with this language provided it is rewritten substituting φ by δ²φ. This grammar therefore covers the grammars discussed above.

[0141] FIG. 21 exemplifies the use of this grammar, on a tree coded by the word ahbcdδ³eδgδ³i. This tree is produced by the following sequence of grammar rules:
SSTδSSTδiaTδiaSTδ²iahTδ²iahSTδ³iahSTδSTδ³i ahSTδgTδ³iahSTδSTδgTδ³iahSTδeTδgTδ³iahSSTδ²eTδgTδ³i ahSSSTδ³eTδgTδ³iahbSSTδ³eTδgTδ³iahbcSTδ³eTδgTδ³i ahbcdTδ³eTδgTδ³iahbcdδ³eδgδ³i

[0142] FIG. 22 shows an automaton which is able to check the syntax of a word produced with this grammar. State 0 is the initial state, state 1 is the final state.

[0143] The equivalence between the tree and the word can be demonstrated by associating actions with the automaton transitions. Two heaps are useful: H₁ and H₂. Standard operations on heaps are available: pop up (put an object on top of the heap) and push down (get an object from the top of the heap). The actions associated with the transition (p,a,q) are

• • [0144] While H₂ is not empty do begin
    • [0145] Get y from top of H₂.
    • [0146] Add the arc (y,a) to the tree.
  • [0147] End
  • [0148] Put a on top of H₁.
    The actions associated to the transition (q,δ,p) are
  • [0149] Get y from top of H₁.
  • [0150] Put y on top of H₂.
    After the whole word is scanned, heap H₁ should contain only one object, which is the root node and heap H₂ should be empty. Otherwise, the syntax is not correct. The automaton of FIG. 22 thus makes it possible the check the syntax of any tree in the grammar. The use of such automaton thus makes it possible, in the editor, to check the syntax of seed structure inputted by the expert user.

[0151] The previous grammar defines a meta-language thanks to the following reason. Any (context free) grammar can be described by a graph, which captures the non-terminal symbols, the terminal symbols and the rules in a so-called derivation tree. Since the previous grammar is designed to describe any tree, it can describe itself. The derivation tree of the tree grammar is represented in FIG. 23. Thus, any tree may be described in this context-free grammar. The editor may use this meta-language, or a more restricted version of the language, with some terminal symbol specifically designed. Using a generic meta-language increased the field of possible adaptations of the design system, but increases the work to be carried out by the skilled user. On the other hand, defining more specifically the symbol or operations of the language helps the skilled user in writing or amending the seed structure.

[0152] The grammar discussed in reference to FIGS. 21-23 further makes it possible to cover any directed acyclic graph, provided the graph does not contain any loop or cycle. This extension allows the language to handle shared data, shared inputs or results in the data flow of the part structure. Data may thus be shared in the design system.

[0153] FIG. 24 is a directed acyclic graph, which could represent a product or the structure of a modelled object. This graph may be changed into a tree by duplicating the shared nodes as many times as necessary; the resulting tree is represented in FIG. 25.

[0154] The sharing is captured through symbol repetition. Since the initial graph features two root nodes, i and j, duplicating shared nodes yields two trees, respectively coded by the words aebcδ²ecdδ²fδ²hgδ⁴i and gfdδ³j. The decomposition of an acyclic graph into a set of trees is not unique. For example, the previous graph could lead to the tree of FIG. 26 and to the following words.
abceδ²efhδ²gδ⁴i
gcdδ²fdδ³j

[0155] This non-uniqueness of tree decomposition is not a trouble because the same level of information is captured. Criteria for a better or for the best possible decomposition are the application's responsibility.

[0156] One also understands from the example of FIGS. 24-26 that the seed structure and the resulting words need not be unique, as already exemplified in reference to FIGS. 19 and 20.

[0157] FIGS. 27 and 28 disclose a tree structure using a non-binary tree defined in a grammar derived from the one of FIGS. 21-23. The tree is used for designing a complex assembly of parts and captures the top down recursive decomposition of the main product into its components. The “ . . . includes . . . ” semantic link is captured by the system. The product structure grammar allows the expert user to design a predefined skeleton structure in such a way that any device added to the main product automatically updates the relevant sub products. It should be noticed that there is no order dependency in the product structure context. The added value is the structure definition and the ease of adding a new device.

[0158] The word S₁T₁δaS₂T₂δbfT₃δcδ³d captures a simple tree structure represented in FIG. 27; the structure is equipped with non-terminal symbols of type S and T. These are provided with indices for the sake of understanding only. In this tree, d is an assembly of parts or sub-products a,b and c.f is a component of sub-product c. The non-binary grammar makes it possible to add components e in sub-product a and components g and h in sub-product c, thanks to the following operations:
T₁eT₁δ
T₃gT₃δ
T₃hT₃δ
Note that type T symbols allow TxTδ substitutions, where x is a terminal symbol. This yields the following word S₁eT₁δ²aS₂T₂δbfgT₃δ³cδ³d and the tree of FIG. 28. As previously, non-terminal symbols S₁ and S₂ remain available for further substitutions.

[0159] The use of a non-binary tree thus makes it easier to add components or contributions at a given level, without any limitation on the number of components added.

[0160] A non-binary tree may be used for a seed structure directed to thin solids, as in FIGS. 8-18. The formal grammar is the following:
X={a,+,−,δ}
V={S,e⁺,e⁻i⁺,i⁻,u}
P={Se⁺δ+e⁻δ+δ²−i⁺δ+i⁻δ+δ²−δ²−uδ+δ²−}∪{zazδ,z ε{e⁺,e⁻,i⁺,i⁻,u}}^As
compared to the grammar discussed in reference to FIGS. 8-18, this grammar contains additional terminal symbol δ; as discussed above, this is used for the sake of counting the number of branches issued from a given node. One has not used in this discussion the non-terminal symbol T, simply for the sake of clarity of the discussion.

[0161] The first operation in the set P of operations provides the seed structure. The word is e⁺δ+e⁻δ+δ²−i⁺δ+i⁻δ+δ²−δ²−uδ+δ²− and the corresponding tree is FIG. 8, and is represented in FIG. 29. Once more, this seed structure is built using the meta-grammar. However, there is provided the ability to add branches to the tree, thanks to substitutions. The substitutions are operations of the type zAzδ where z stands for any of the non-terminal symbols e⁺, e⁻, i⁺, i⁻ and u. A substitution thus adds a new operand to the list that contains z. In other words, a substitution adds a brother to z. This simplifies the tree, in that the depth of the tree is limited, compared to the embodiment of FIGS. 8-18.

[0162] Contributions may be defined as discussed above. Instantiating the contributions of a thin solid and fixtures, as above, provides the tree of FIG. 30, or the following word
AFe⁺δ³+Ce⁻δ²+δ²−Bi⁺δ²+DEi⁻δ³+δ²−δ²−Guδ²+δ²−

[0163] It is fully clear that the evaluation of this word in the history based design system provides the modelled object of FIG. 14. However, the tree of FIG. 30 has a depth of 4 while the tree of FIG. 13 has a depth of 5. Additional contributions in the seed structure of FIG. 8 would cause the depth of the tree to feather increase, while additional contributions to the seed structure of this embodiment would not cause any increase in the depth of the tree of FIG. 30.

[0164] Thus, the use of a non-binary context-free grammar for defining the seed structure expands the possibilities availed to the expert user.

[0165] A third embodiment of the invention is now discussed in reference to FIGS. 31-34. The third embodiment makes it possible to speed up the evaluation of a modelled object after changes to components of this modelled object. For this purpose, the intermediate solids are kept, inasmuch as possible, to avoid re-evaluation in cases of changes.

[0166] The problem of changes to components is exemplified in reference to FIG. 31. This shows a tree structure similar to the one of FIG. 13—but without the “handles”. Assume leaf L in this tree is modified. If the intermediate solids are kept, the replayed operations are those on the path from the root solid to the modified leaf solid; in the example of FIG. 31, the only replayed are those on the path from leaf L to the root of the tree, that is the four operations indicated in FIG. 31. To get the new shape of the solid, only four operations need to be recomputed.

[0167] To preserve this benefit, substitutions should increment the structure in such a way that existing intermediate solids remain unchanged as much as possible. This is not the case with the binary tree grammar and the seed structure of FIG. 8, because the new solids appear on top of existing solids. This may cause useless B-rep operations.

[0168] The goal of the grammar and seed structure in this third embodiment is to place the new solids at the best possible place in the structure. The grammar is the following:
X={a,+,−,x}
V={S,e⁺,e⁻,i⁺,i⁻,u}
P={Sxe⁺+xe⁻+−xi⁺+xi⁺−−xu+−}∪{za+z,z ε{e⁺,e⁻,i⁺,i⁻,u}}
In this grammar, the symbol x stands for a dummy solid that evaluates as the empty set. The seed structure is provided by the first operation, while the substitutions are provided in the other operations. The substitutions are clearly commutative, for the reasons discussed above.

[0169] The seed structure is the word
xe⁺+xe⁻+−xi⁺+xi⁻+−−xu+−
and it is represented as a tree in FIG. 32. From a qualitative point of view, each of the “handles” in FIG. 8 is replaced by a two-leaves tree formed of a terminal symbol x and of the corresponding handle.

[0170] A substitution rule is defined, as expressed in the grammar, by za+z, where z again stands for any of the non-terminal symbols e⁺, e⁻, i⁺, i⁻ and u and where a stands for any basic solid.

[0171] The operation of this seed structure is again exemplified with the same thin solid and fixture of FIGS. 11 and 12. The thin solid functional feature is captured by the following substitutions:
e⁺A+e⁺
i⁺B+i⁺
which leads to the tree represented in FIG. 33 or to the following word:
xA+e⁺+xe⁻+−xB+i⁺+xi⁻+−−xu+−
The fixture functional feature is capture by the following substitutions
e⁺F+e⁺
e⁻C+e⁻
i⁻D+i⁻
i⁻E+i⁻
uG+u
These substitutions provide the tree represented in FIG. 34 and the following word:
xA+F+e⁺+xC+e⁻+−xB+i⁺+xD+E+i⁻+−−xG+u+−

[0172] As expected due to the grammar, new basic solids appear in the tree after existing solids. Thus, intermediate results may be kept and re-used even after new solids are added. For instance, F is after A, E is after D.

[0173] In this embodiment, one uses a binary tree and a grammar derived from the one disclosed above in reference to FIGS. 8-18. It is noteworthy that the advantages discussed in this third embodiment also apply to a non-binary tree. One could also apply the same solution to other seed structures, for modelled objects other than thin solids.

[0174] The invention is not limited to the examples provided in the detailed description. One may notably use history-based design systems different from the one discussed in the examples. The various solutions discussed in reference to each embodiment may be applied to the other embodiments. This applies notably to the discussion of the functions of the expert user and to the discussion of the operation of the system given in reference to the first embodiment of FIGS. 8-18. These also apply to the other embodiments.

[0175] The examples given above refer to moulded thin solids. Additional or alternative operations and contributions could be used for other types of modelled objects. For instance, for assemblies of parts, one could additionally allow parts to be juxtaposed. This would simply represent an additional non-terminal symbol. For designing modelled objects out of a surface—e.g. stamped metal car parts—one could use a terminal symbols curves and surfaces. The operations could then comprise relimitation for stamping part of an existing modelled object or cut, for cutting a curve or surface.

[0176] In the examples provided above, the non-terminal symbols are all used in the initial seed structure. A sequence of substitution rules may introduce a new non-terminal symbol that was not in the initial seed structure. This capability allows a seed structure to become more complex. Dynamic non-terminal symbols can be reused in further substitution rules. For example, after a few design steps, the need is to add material to the solid part after the first subtraction. The tree structure of FIG. 30 cannot support this operation and could be changed into the structure of FIG. 35 for allowing the addition of material. The tree of FIG. 35 features the new non terminal symbol f that is ready to capture solid contributions. The sequence of substitution rules starts with the expression
AFe⁺δ³+Ce⁻δ²+δ²−Bi⁺δ²+DEi⁻δ³+δ²−δ²−GUδ²+δ²−
which represents the tree of FIG. 30. In this expression, the first subtraction symbol is replaced by the non terminal symbol S, which saves the syntax and prepares the node insertion. This provides the following expression:
AFe⁺δ³+Ce⁻δ²+δ² SBi⁺δ²+DEi⁻δ³+δ²−δ²−Guδ²+δ²−
As expected, the seed structure edition involves the meta-grammar.
Then, the following substitutions are executed.
S STδ S SSTδ² S− STδ² S− STδ²+− Sδ²+− STδ Sδ²+−fTδ Sδ²+−fTδ+δ²+−fδ+δ²+
and the resulting expression corresponds to the expected tree of FIG. 35.
AFe⁺δ³+Ce^−δ2+δ²−fδ+δ²+Bi⁺δ²+DEi⁻δ³+δ²−δ²−Guδ²+δ²−
This example shows that it is possible, using the same meta-grammar, to amend the seed structure for producing a more complex seed structure.

[0177] It is also possible to execute or not a substitution rule, attached to a functional feature, according to the value of a logical variable. This variable, commonly called the “activity”, may be embedded in the functional feature definition and the end-user defines its value (“true” or “false”) through any rule or program. This makes it possible to maintain a functional feature in the modelled object, without it being considered by the evaluator in the core system. The functional feature is inactivated and may be activated if and when needed. Using a logical variable also makes it possible to provide additional view of the modelled object. For instance, one may wish to provide a view of the modelled object, before any machining step. One would then inactivate the contributions applied to handle u before evaluating the modelled object. This example shows that it is possible to inactivate not only a full functional feature, but also a contribution of a functional feature.

[0178] Last, a substitution rule need not be executed if the replaced non-terminal symbol is not in the target structure. This is a standard behaviour of substitution rules and will not lead to an error message. For instance, in the example of upper and lower moulds, the seed structures of FIGS. 19 and 20 do not comprise the handle u. This does not prevent the system from applying the fixture functional feature to the upper and lower moulds, without the contribution G being considered.

[0179] The implementation of the invention in a computer system was not discussed in full detail above. The implementation of a history-based design system 40 is well known to the person skilled in the art. The additional features of FIG. 5 may be implemented in the same or another computer system, by using tools such as existing programmation languages (C++, Java, Fortran, etc.), as well as library of programs usually available in any CAD system. The programs in such libraries make it possible to

• • [0180] create objects;
  • [0181] write objects;
  • [0182] read modelled objects, etc.
    One may thus implement the invention, as represented in FIG. 5, on any existing CAD system, which is then used as the core system 40 of FIG. 5.

[0183] This is also made easier, since most existing CAD systems provide a programmation platform in which the additional elements of the invention may be programmed.

[0184] The invention was described in the reference to the preferred embodiment of CAD systems but can be applied to computer-aided manufacturing (CAM) systems and to computer-aided engineering (CAE) systems. One may use similar grammars and meta-grammars for other systems, such as product data management (PDM) systems, virtual product modelling (VPM) or product lifecycle management (PLM) systems, but also for enterprise resource planning (ERP) systems. Such systems organize tasks to be carried out on products (in a generic meaning). In such a system which usually relies on a process modeller, queries and tasks are order-sensitive.

The following table shows an example of a possiblecorrespondence between the elements of the described CAD system and a PDM system:

[0185]

	history-based design system	order based query system;
	functional feature	parametric task;
	feature parameters	task parameters;
	part	task;
	primitive	elementary action;
	operation	operation.

[0186] A task in a PDM system is an ordered sequence of elementary actions and operations and corresponds to a part in a CAD system. The table shows that the solutions discussed above in reference to CAD systems also apply to PDM systems and provide similar advantages.