HK1138092B - Automatic generation of building instructions for building element models - Google Patents
Automatic generation of building instructions for building element models Download PDFInfo
- Publication number
- HK1138092B HK1138092B HK10103885.0A HK10103885A HK1138092B HK 1138092 B HK1138092 B HK 1138092B HK 10103885 A HK10103885 A HK 10103885A HK 1138092 B HK1138092 B HK 1138092B
- Authority
- HK
- Hong Kong
- Prior art keywords
- building
- building element
- model
- sub
- assembly
- Prior art date
Links
Description
Technical Field
The invention relates to generation of building instructions for building element models.
Disclosure of Invention
There are various known types of modeling concepts for sets of mechanical construction toys. In particular, modular or semi-modular concepts are very popular because they provide an interesting and challenging play experience. Generally, these concepts provide a set of prefabricated building elements that can be interconnected to each other in some predetermined manner by means of connecting elements of the prefabricated elements. The prefabricated building elements resemble known objects adapted to perform a specific modelling task. Thus, for example, in building a model of a house, the building elements may resemble wall tiles, roof tiles, doors, and windows. The purpose of selecting building elements in this way is to significantly reduce the amount of work involved in building a model of a house compared to the situation where all details of the house are defined each time a new model is to be made. However, there is a mutual opposition between the complete freedom to build a house or another object and the simplicity of building a model.
For example, the toy building sets in the name LEGO include a number of different types of interconnectable building elements, with protrusions and corresponding recesses as connecting elements. The connecting elements are placed according to a regular grid pattern, whereby various interconnections between building elements may be created.
Typically, such a toy building set assembly comprises a set of building elements, e.g. animals, robots, or another creature, automobiles, airplanes, space vehicles, buildings, etc., adapted to create one or more building element models. Typically, a building kit further comprises printed building instructions or building instructions describing how to build a model from building elements. Needless to say, an interesting feature of such building sets is that they motivate children to make their own models.
Typically, the building contained in a toy construction set includes a step-by-step illustration of how and in what order building elements are added to the model. Such building instructions have the advantage of being easy to handle, even for children, without having a rich experience of playing blocks, and/or without having to read skills.
In general, building instructions for a model may be viewed as a sequence of steps and sub-steps in building a building element. The sequence starts with one or more initial building elements and progresses through a series of steps to the structure of the fully assembled model. In each step, a single building element or a sub-assembly of building elements is added. For purposes of the present description, the term "subassembly" refers to a subset of interconnected building elements of a building element model. Thus, adding a sub-assembly rather than a single building element may involve adding a sub-assembly description of the sub-assembly to a main assembly description. For the purposes of the present description, such a secondary assembly specification is also called a "substep". As such, the sequence of steps can be generally represented as a tree of branches of steps, each branch containing an accompanying building instruction.
Previously, such assembly instructions were generated manually, e.g. by manually determining reasonable assembly steps, drawing the corresponding instructions in a CAD system, and finally printing the instructions thus generated. Although such assembly specifications are of high quality, i.e. easy to handle, the above manufacturing process also has drawbacks: they require a high degree of skill and require a high degree of manual labor. As a result, building instructions typically exist only for building element models designed by the manufacturer of the building elements. In particular, the above prior art methods for generating assembly instructions are not suitable for children who wish to generate assembly instructions for their own models, with which children share their models with their friends.
Recently, assembly instructions have been generated electronically, rather than in printed form. In particular, animated assembly instructions are provided, with more complex assembly steps being animated. However, the creation of such building instructions still involves the design and drawing of the building steps/animating thereof by a skilled designer.
In complex systems such as the LEGO system, the number of possible building instructions for a model grows exponentially with the number of building elements in the model. Therefore, determining a high quality specification set from an almost infinite number of possible assembly specifications for a given model is a problem for an automated assembly specification process. Thus, there is a need to provide an automated process that generates practical, easy-to-use instructions, even for complex models. It is further desirable to provide a process for assembling a presentation on reasonable computing hardware in a reasonable time.
There is a further need to provide a method for generating building instructions suitable for children who wish to generate building instructions for their own models, which may enable the children to share their models with their friends and further improve the playing experience. In particular, there is a need to provide methods that are easily available to users with little user interaction and input.
Certain research topics have also discussed the design of efficient, easy to understand, step-by-step assembly instructions. The Internet publication "design effective step-by-step-assembly instructions" by M.Agrawala et al, retrieved from http:// graphics.stanford.ediu/papers/assemblies/assembly, describes the design principles of efficient assembly instructions based on cognitive psychology. The article further describes a computerized system for generating assembly instructions based on information about each object to be assembled, the orientation of the assembly and the camera angle for graphical presentation, grouping information, information about fasteners, and meaning, symmetry of parts, and constraints on the order of the assembly. Based on this input, the system calculates a sequence of assembly steps based on a number of search algorithms, and taking into account given constraints. The problem with the above prior art systems is that they are computationally expensive and require complex input data, thus requiring a high degree of abstract thinking from the user.
Published international patent application WO2005/124696 describes an automated process for generating building instructions for a virtual model, wherein the building instructions utilize a sequence of steps determined by a sequence of building steps used by a user in assembling the virtual model in a virtual assembly environment. Although this prior art approach provides an easy-to-use automated process, it remains a problem to improve the quality of the automatically generated assembly instructions.
There is described a computer-implemented method of generating building instructions for a building element model, the model comprising a plurality of building elements, the building instructions representing a sequence of building steps for building the building element model, each building step comprising adding at least one building element to the building element model; the method comprises the following steps:
-determining from the digital representation of the building element model at least one sequence of decomposition steps for at least partially decomposing the building element model into a number of building elements, each decomposition step comprising removing at least one building element from the building element model;
-determining at least one assembly step of the sequence of assembly steps based on at least one of the plurality of decomposition steps.
Thus, it is recognized that by determining one or more sequences of disassembly steps, a sequence of assembly steps can be efficiently determined.
The decomposition of the model may be viewed as a sequence/iterative process of steps and sub-steps to decompose building elements. The sequence starts with the complete model and proceeds in a series of steps. In a complete decomposition the process continues until all building elements are separated from the model, whereas in a partial decomposition the process ends when only a predetermined residual part of the model remains. In each step, a single building element or a sub-assembly of building elements is separated. As such, separating a sub-assembly, rather than a single building element, may involve a sub-disassembly of that sub-assembly associated with a primary disassembly. Such an ancillary decomposition is also called a "sub-step". Thus, similar to assembly, the sequence of steps of the decomposition process is generally a tree of branches of steps, each branch containing an attached decomposition.
When it is known how to decompose, this information can be used in the process of generating the assembly sequence. Thus, the assembling step may be determined in response to the step of determining the decomposition sequence. Furthermore, it is possible to search for decomposition sequences that meet certain selection criteria using reasonable computational resources and can produce high quality assembly specifications.
It is further known that the assembly instructions generated by this computationally simple method are easy to understand for the user, in particular a child.
Furthermore, because the only input to the building instructions is a digital representation of the building element model, e.g., as recorded during the virtual model generation process, the building instructions are easy for the user to generate without requiring the user to possess design skills or abstract knowledge about geometry, constraints, etc. Moreover, the generation of the assembly instructions is also independent of the order in which the user actually assembles the virtual model. This may be beneficial because the virtual assembly environment may allow the assembly steps to be performed in an order that may be difficult or even impossible to perform for a physical, real-world model.
In certain embodiments, the method comprises:
-determining from the digital representation of the building element model a sequence of decomposition steps for decomposing the building element model into a number of building elements, each decomposition step comprising removing at least one building element from the building element model;
-reversing the determined order of the disassembling steps to obtain the order of the assembling steps.
If it is known how to decompose, it can be reversed, resulting in building instructions, just as a model can be decomposed by performing the building instructions in the reverse direction. Thus, by determining one or more sequences of disassembly steps and then reversing the order of the disassembly steps to obtain a sequence of assembly steps, the sequence of assembly steps can be efficiently determined. Advantageously, this process requires only the generation of a single decomposed sequence.
In an alternative embodiment, the method comprises performing an iterative process, wherein an iteration of the iterative process comprises:
-obtaining a sequence of assembly steps resulting from a previous iteration, the sequence of assembly steps resulting in a first partial model;
-determining a subsequent building step representing a connection of at least one subsequent building element to the first part model, resulting in a second part model.
-determining whether the building element model can be decomposed by a sequence of decomposition steps for decomposing the building element model resulting in the second partial model;
-if it is determined that the building element model can be decomposed by a sequence of decomposition steps for decomposing the building element model resulting in a second partial model, appending the determined subsequent building step to the obtained sequence of building steps.
Thus, in this embodiment, each assembly step is determined so that a partial model can be obtained by partial decomposition of the complete model. Thus, by the assembly process, an efficient process for generating assembly specifications can be provided, simulating decomposition from the complete model up to the current assembly stage in each assembly step.
This embodiment is assembled (starting with the brick and ending with the complete model) and not based entirely on decomposition. Because this is a relatively intuitive way for a user to consider the building instructions, it is relatively easy to use, is powerful, and allows the user to interact with the process of generating the building instructions. One example of user interaction may be to objectify any suggested brick and obtain an alternative suggestion. In fact, this simple interaction may enable the user to generate particularly high quality assembly instructions in a very short time, requiring very little user interaction. Furthermore, the generator can ensure that hard constraints are never violated, so no matter what the user object, only reasonable suggestions are made.
Accordingly, in one embodiment, the step of determining the subsequent assembly step may include receiving user input, for example, in the form of at least one of a suggestion, an approval, and a rejection of the assembly step.
The step of determining whether a building element model is resolvable through a sequence of decomposition steps for decomposing the building element model resulting in the second partial model may comprise the step of determining whether the building element model is resolvable through a sequence of decomposition steps, wherein each decomposition step is selected by one or more predetermined sets of selection criteria. Thus, an efficient method is provided that may provide high quality assembly instructions.
In some embodiments, the process of determining the order of the decomposition steps comprises performing an iterative process, wherein an iteration of the iterative process comprises:
-obtaining a previous part model resulting from a previous iteration;
-determining at least one building element to be separated from a previous part model resulting in a new part model.
Thus, starting from a complete model, a sequence of partial models is generated by removing one or more building elements in each iteration. Whereas searching for high quality building instructions generally requires back-tracking, it is computationally very costly, and even prohibitively expensive for larger models, the building decomposition can be achieved with one pass of the algorithm (with much lower requirements on computing hardware).
In general, in complex building systems, such as the toy building systems sold under the name LEGO, it may not be possible for some models to be disassembled from building element to building element, because some building elements may lock with each other and may not separate into individual building elements. In general, however, all models may be separated by removing a single building element or a sub-assembly of building elements in each step.
Accordingly, in some embodiments, the process of determining at least one building element includes:
-determining a set of candidate sub-assemblies of the previous part model, each candidate sub-assembly comprising a respective interconnected building element of the previous part model;
-selecting one of the determined set of candidate sub-assemblies or individual building elements to be separated from the previous part-model resulting in the generation of a new part-model, according to a first set of predetermined selection criteria.
Thus, in certain embodiments, for a decomposed sequence, the sub-assembly is treated as a pseudo-log component. However, the number of possible sub-assemblies of a building element model generally grows exponentially with the number of building elements in the model. Thus, even for medium-sized models, the top-down approach of searching all possible sub-assemblies and selecting one sub-assembly to separate, given certain conditions, is computationally very costly, although such an approach may be feasible when considering the removal of only a single building element.
In some embodiments, the methods described herein combine the top-down approach above with a bottom-up approach for generating candidate sub-components to be subjected to a top-down search. The generation of candidate sub-components may be performed according to a set of one or more generator sub-processes or a second set of selection criteria, thus producing a subset of candidate sub-components of the set of all possible sub-components of the model. Thus, the search space is pruned using a bottom-up approach before performing a top-down approach, which is computationally expensive.
The above partitioning of the top-down search and bottom-up generation results in a computationally less expensive, easier to program, and easier to expand, e.g., by adding an additional generator sub-process for generating candidate sub-components.
Furthermore, the control power of the above method is also improved as it provides a mechanism for controlling the number of candidate sub-components to be generated, thus providing a mechanism for coordinating the computational cost with the quality of the resulting assembly specification and adjusting the size of the pool of candidate sub-components for any given hardware and time requirements.
In certain embodiments, at least one of the second set of selection criteria comprises determining a connection strength of one or more candidate sub-components to the previous portion of the model. Accordingly, the sub-components are generated/selected according to the strength of the connection with the rest of the previous part model. As a result, this selection/generation strategy of the subassemblies results in a particularly high quality assembly specification.
Additional or alternative selection rules for efficiently selecting candidate sub-assemblies include determining a change in assembly orientation and/or sub-assemblies movably connected to a previous portion of the model (e.g., via hinges or joints, sliders, etc.).
In some embodiments, a method includes representing a previous portion of a model by a data structure representing a graph (e.g., an undirected graph), including nodes representing respective building elements of the previous portion of the model, and edges connecting the respective nodes representing connections between corresponding building elements. By representing the former portion model as a graph, graph partitioning techniques and other techniques known from graph theory (see, e.g., "graph theorgannds and italics," Chapman & Hall/CRC, second edition, 2006, by jonathanl, gross and jayylelen) may be used to efficiently identify appropriate candidate sub-components, e.g., by identifying joint nodes or pairs of joints in the graph, in order to identify sub-components that are connected to the rest of the former portion model by a single joint building element or by a pair of building elements. Thus, the model of interconnected building elements corresponds to a connected graph, and the sub-assemblies correspond to connected sub-graphs.
Nodes and/or edges of a graph may have one or more respective attributes associated with them, corresponding to attributes of corresponding building elements and connections, respectively. For example, a node of a graph may have one or more of the following attributes: building element type, building element volume, building element shape/geometry, building element volume mass, building element bounding box, building element position in a coordinate system, main assembly orientation associated with a building element, location, type and/or orientation of a connecting element of a building element, etc. Similarly, edges of a graph may have one or more of the following properties associated with them: type of connection, strength of connection, direction of connection, etc. When edges of a graph have respective weights/values associated with them (representing respective connection strengths of the connections), a particularly efficient graph partitioning method, such as one for finding the fewest cuts, can be used to obtain high quality assembly specifications.
In some embodiments, each building element includes one or more coupling elements for engaging with one or more corresponding coupling elements of another building element to provide a coupling between the building element and the other building element. Such coupling elements may impose further restrictions on the possible placement of building elements, since the coupling may only be performed between compatible coupling elements, e.g. protrusions that fit into corresponding recesses when placed in the correct position relative to each other. Each connecting element may have a connecting element class associated with it, each connecting element class having a connection strength associated with it. In some embodiments, the method comprises determining said associated connection strength value corresponding to an edge of a connection between two building elements, based on the number and respective class of connecting elements contributing to the corresponding connection. Thus, an efficient and accurate method for calculating/estimating connection strengths in a building element model is provided.
In some embodiments, the process of determining said associated connection strength values comprises determining the connection strength values on the basis of the number and respective class of connection elements contributing to the corresponding connection, and on the basis of the volume of two building elements, so that not only the connection strength but also the size of the building element is taken into account, and thus whether the building element is easy to fix and manipulate during construction.
In some embodiments, determining at least one building element to be separated from a previous part model that results in a new part model comprises calculating one or more weighting functions for at least one of a subset of building elements and a set of candidate sub-assemblies of building elements; and selecting one of the individual building elements and sub-assemblies based on a comparison of the calculated weighting functions. Thus, an extensible and flexible framework of the selection process is provided, which can be modified or extended by alternative or additional weighting functions, which can weight different selection criteria relative to each other according to their importance/priority. The weighting function may comprise any suitable function of one or more attributes of one or more building elements.
In some embodiments, at least one of the one or more weighting functions has a range of possible outcomes, including a first sub-range representing a degree of separation appropriateness and a second sub-range representing a degree of separation inadequacy, thereby allowing both to assign positive and negative weights to building elements and/or sub-assemblies.
Accordingly, in some embodiments, selecting individual building elements or sub-assemblies based on a comparison of the calculated weighting functions includes calculating a total weight based on one or more of the calculated weighting functions; wherein the process of calculating the overall weights comprises assigning values in a second range to the overall weights if at least one of the calculated weighting functions has a result in the second range, thereby providing an overrule strategy preventing building elements and/or sub-components not fulfilling certain conditions from being separated, although they may get high weights from other weighting functions.
Examples of weighting functions that are found to produce high quality building instructions include weighting functions that determine whether building elements or sub-assemblies are physically separable or whether the direction of separation of the building elements or sub-assemblies is, for example, blocked by other parts of the model. Such a weighting function can be efficiently calculated, for example, by calculating the extended geometry of the building elements or sub-assemblies.
Another example of such a weighting function comprises a weighting function that gives lower weights to the articulated building elements and/or building elements comprised in the pairs of joints of a building element or sub-assembly, in order to avoid separating the model into separate partial models. When the weighting function is included with other building elements or sub-assemblies connected (directly or through other building elements), it is ensured that small disjoint parts are quickly removed from the model (if they occur).
When one of the weighting functions is a function of the strength of the connection of the connections between the building elements of the sub-assembly, building elements and sub-assemblies can be obtained that are easily separable from the remaining models. In particular, it has been found that weighting functions give higher weight to building elements and sub-assemblies with stronger internal connectivity and weaker external connectivity, resulting in high quality building instructions. Furthermore, in such a weighting function, the connectivity strength may be calculated as a strength with respect to the volume of the interconnected building elements or sub-assemblies.
Further examples of suitable weighting functions include such weighting functions as: at least the properties of a building element or sub-assembly and the properties of a building element or sub-assembly that was separated in a previous iteration of the iterative process, may thus be advantageous to eliminate symmetrically placed building elements or sub-assemblies, building elements or sub-assemblies that are located at a close distance from another building element or sub-assembly, etc. Examples of such attributes include the position of the building element relative to a coordinate system, building element type, and so forth. In some embodiments, the weighting function may further be a function of the attributes of more than one building element removed in the previous iteration. For example, when comparing partial models, one or more previous iterations may be given different weights; for example, the latest iteration may be given a higher weight than the previous iteration.
Embodiments of the methods described herein receive a digital representation of a building element model. Such a digital representation may be provided by any suitable process, for example, a computer-implemented assembly environment, and/or a process for generating a digital representation of a building element model from one or more images (e.g., an image of a physical model or another object). One such process is described in us 7,092,899. In this process, a digital representation of a building element model of an object is created from a CAD model or a set of two-dimensional images of a three-dimensional object. Some embodiments of the digital representation may include information in any suitable data format that indicates the type, location, and/or interconnection of building elements, etc. Embodiments of the numerical representation may further include information regarding overall model attributes, attributes of individual building elements (e.g., building element type, color, size, bounding box, etc.).
A computer-implemented assembly environment for interactively assembling virtual building element models may include a computer program that, when executed on a computer, provides a graphical user interface for a user to manipulate virtual building element models, including such operations as selecting building elements, adding building elements to models, removing building elements from models, changing orientations of building elements, changing properties of building elements, e.g., color, type, size, etc., viewing a model, saving a digital representation of a model, loading a previously saved digital representation of a model, and so forth. The virtual building elements may be virtual counterparts of the corresponding physical building elements, i.e. having a corresponding relative size, shape, color, etc.
The computer-implemented assembly environment may be configured to implement a predetermined set of constraints imposed on the relative positions of building elements with respect to each other, such as conflict detection between building elements. For example, the constraints correspond to corresponding constraints that apply to the corresponding physical building elements, thereby ensuring that the virtual building element model can also be assembled from the corresponding physical building elements. Thus, it is an advantage that the method ensures that the generated assembly specifications are practically realizable, i.e. produce the desired result.
In some embodiments, the assembly specification is generated as a sequence of graphical representations, such as images. Each graphical representation may comprise a graphical representation of a partial building element model (also referred to as a partial model), each graphical representation corresponding to a step in a building process of adding a predetermined number of building elements to the model, thereby providing an operationally simple building instruction. In this manner, all or only a subset of the partial models that make up the determined assembly sequence may be included in the final assembly specification, as one or more steps of the assembly sequence may be incorporated into the entire assembly specification. The user can easily determine which building elements to add in each step and how to add them by comparing two consecutive graphical representations.
When the method further comprises providing a user interface for viewing the graphical representation, wherein the user interface preferably facilitates the handling of user controls of the generated graphical representation, the digital representation of the building element model may conveniently be viewed on the computer. In particular, since the digital representation of the model includes all of the information necessary to generate the building instructions, the building instructions may be conveniently transferred from one computer to another, e.g., stored on a storage medium, sent over a communications network, e.g., as an email link, uploaded on a Web server, etc. In this manner, a recipient of the digital representation may view the graphical representation, manipulate it, e.g., change a perspective, zoom, change viewing options, and/or the like. Thus, the user can easily transmit their building instructions to friends. Yet another advantage is that the digital representation need not include a graphical representation of each step of the building instruction, and thus the file size of the digital representation can be made smaller. Furthermore, because the digital representation may include all relevant model information, the recipient of the model may modify the model even before generating the building instructions.
In some embodiments, the assembly instructions may be generated in a predetermined file format, such that printed and/or electronic assembly instructions may be generated. Examples of suitable file formats include HTML, XML, BMP, TIFF, and the like.
In some embodiments, the predetermined number of additional building elements added in one step of the specification in steps is user selectable, thereby enabling a user to select between a very detailed one-step specification (where, for example, each step corresponds to the placement of a single new building element) and a very concise specification (where each step corresponds to a larger number of newly placed building elements). In some embodiments, the number of building elements added in each step is the same in all steps. In other embodiments, the number of additional building elements added may be different for different steps of the building instructions. For example, the size of the steps may be controlled by the user for each step, so that a finer specification may be generated for more complex parts of the assembly.
The invention can be implemented in different ways including the method described above and in the following, a data processing system, and further product means, each yielding advantages and advantages associated with the first-mentioned method, each having one or more preferred embodiments corresponding to the preferred embodiments associated with the first-mentioned method and being set forth in the associated dependent claims.
In particular, the features of the methods described above and below may be implemented in software and implemented on a data processing system or other processing device caused by the execution of computer-executable instructions. The instructions may be program code means loaded in a memory, such as a RAM, from a storage medium or from another computer via a computer network. Alternatively, the described features may be implemented in hardwired circuitry in place of or in combination with software.
Accordingly, the present invention further relates to a data processing system for performing the method described above and below. The invention further relates to a computer program comprising program code means for performing all the steps of the method described above and in the following when said program is run on a computer. The invention further relates to a computer program product comprising program code means for performing the method as described above and in the following when said computer program product is run on a computer. The program code means may be stored on a computer readable medium and/or embodied as a propagated data signal.
In some embodiments, the computer program comprises a first software component for generating a digital representation of a building element model; and a second software component for generating building instructions from the generated digital representation, thereby providing a separate software component for reading the digital representation of the model and presenting the corresponding building instructions. Thus, when the assembly instruction is delivered, the user can deliver the digital representation together with the second software component, thereby providing a simple, stand-alone representation of the assembly instruction that can be viewed by the recipient without the need for additional software. However, it should be appreciated that the two processes, i.e., generating the digital representation of the model and generating the assembly specification, may be integrated into a single software component.
Drawings
The present invention will now be described more fully hereinafter with reference to the accompanying drawings, in which:
FIGS. 1a-b show a data processing system that generates building instructions for building element models;
FIG. 2 shows a flow diagram of an embodiment of the generation of a general assembly specification;
FIG. 3 shows a flow diagram of an embodiment of a process for generating a sequence of decomposition steps;
FIG. 4 shows an example of a building element and its connecting elements;
FIG. 5 shows an embodiment of a data structure that numerically represents a building element model;
FIG. 6 shows an embodiment of a graphical user interface for assembling an illustration application;
FIG. 7 shows a representation of a building element model as an undirected graph;
8-13 show embodiments of selection criteria;
FIG. 14 shows a flow diagram of another embodiment of the generation of a general assembly specification;
FIG. 15 shows a flow diagram of an embodiment of a process for generating a sequence of partially decomposed decomposition steps;
FIG. 16 shows a flow diagram of another embodiment of the general building instruction generation.
Detailed Description
FIGS. 1a-b illustrate a data processing system for generating and manipulating computer-readable models of geometric objects.
FIG. 1a shows a schematic diagram of an example of a computer system. The computer system comprises a suitably programmed computer 101, e.g. a personal computer, comprising a display 120, a keyboard 121, a computer mouse 122 and/or another pointing device, such as a touch pad, a trackball, a light pen, a touch screen, etc.
The computer system denoted 101 may generate building instructions from a digital representation of a building element model. Computer system 101 may further facilitate designing, storing, manipulating, and sharing virtual building element models and generating building instructions as described herein. Computer system 101 may be used as a stand-alone system or as a client in a client/server system. In certain embodiments, the computer system further includes one or more interfaces for connecting the computer to a computer network (e.g., the Internet).
FIG. 1b shows a block diagram of a data processing system for generating building instructions for a building element model. The computer 101 includes a memory 102, and the memory 102 may be implemented partly as volatile and partly as non-volatile memory means, such as Random Access Memory (RAM) and a hard disk. The memory has stored thereon a model code interpreter 107, a model code generator 108, a UI event handler 109, a modeling application 110, and an assembly specification generator 113, each executable by the central processing unit 103. Further, model data 111, i.e. a set of data structures representing a digital representation of the building element model, is stored on the memory.
Code interpreter 107 may read and interpret digital representations that define a model, e.g., codes that represent data structures of building elements of a model. In a preferred embodiment, the code interpreter may read a digital representation of the model and convert such model into a known graphical format for presentation on a computer display, preferably a 3D presentation of the model. The UI event handler 109 may translate the user's interaction with the user interface into appropriate user commands that may be recognized by the code generator 108. A set of possible and recognizable commands may include: retrieving a building element from a library of elements, connecting a building element to another building element, disconnecting a building element, discarding a building element, manipulating a building element, a set of building elements, etc., e.g., by activating a rotation, etc. Along with each command, a corresponding set of parameters may be associated, e.g. cursor coordinates relative to a display coordinate system, type of building element, etc.
Code generator 108 may further modify the data structure of the model in response to a user command. As a simultaneous or subsequent task, the code interpreter may be executed in order to present the results of the code generator.
Modeling application 110 may control memory, files, user interfaces, and the like.
An embodiment of virtual reality modeling is described in US6,389,375. Furthermore, interactively placing new virtual building elements into a scene comprising a 3D structure is described in the already published international application WO 04104811. The contents of both documents are incorporated herein by reference in their entirety.
Build instructions application 113 can read the digital representation of the model and generate build instructions from the read model data as described herein. The assembly instruction application 113 may further provide a user interface for displaying the partial models, or any other suitable output format of the generated assembly instructions, according to the stored sequence of assembly steps as described herein. The assembly instruction application 113 may use the functionality provided by the code interpreter 107 and the UI event handler 109 to perform model reading and graphical rendering, respectively, and to receive user input. In an alternative embodiment, the assembly specification application is stand-alone, i.e., does not rely on external software components. In some embodiments, the assembly instruction application generates the assembly instructions in a suitable file format, for example, in a form that can be printed.
User 105 is able to interact with computer system 101 through user interface 106, which preferably includes a graphical user interface displayed on a computer screen and one or more input devices such as a keyboard and/or pointing device. To load, save, or transfer models, geometry descriptions, or other data, the computer system includes an input/output unit (I/O) 104. The input/output unit may serve as an interface to different types of storage media and different types of computer networks (e.g., the internet). Further, input/output units (I/O)104 may be used, for example, to interactively exchange models with other users. Data exchange between the memory 102, the Central Processing Unit (CPU)103, the User Interface (UI)106, and the input/output unit 104 is performed through a data bus 112.
Notably, the data processing system of FIG. 1 can be configured to execute both a modeling application and an assembly specification application. However, in other embodiments, the data processing system may be configured to execute the build instruction application based only on model data received from another computer (the computer on which the modeling application or another application for generating the digital model representation is running). Also, the modeling application may be installed on the other computer alone or in combination with the building instructions application.
FIG. 2 shows a flow diagram of an embodiment of the generation of an assembly specification. In step S1, a digital representation of a building element model is received, e.g., created by a model generation module (e.g., modeling application 110 of FIG. 1 b) or by any other suitable process.
The digital representation may be retrieved from the storage medium 203, for example, a local hard disk, a CDROM, a diskette, etc. of a computer running the assembly description application. Alternatively, or in addition, the digital representation of the model may be stored remotely, e.g., received from another computer of a computer network in which it is stored. For example, the digital representation may be downloaded from a Web server, where it may be available to one or more users. An example of a data structure of the numerical representation will be described below.
In subsequent steps S2-S4, the building instruction application generates the building instructions 205 from the loaded digital representation. In one embodiment, the building instruction application generates a sequence of 3D views of the part models, wherein each part model differs from the immediately preceding part model in that a predetermined number of additional building elements are added to the model according to the sequence of building steps determined by the building instruction process as described herein. The assembly instructions 205 may be presented electronically, printed, or presented in another suitable manner. In some embodiments, the generation of the assembly instructions may be controlled by user 204. For example, the user may select the number of additional building elements to be added in each step. In addition, the user may also manipulate the generated 3D view, including changing the orientation of the camera, and so forth, as described below. User 204 may be the same user as user 202 or a different user.
In particular, in step S2, a decomposition sequence is generated from the received digital representation of the model, e.g., in the form of a continuous list of building elements and/or sub-components of the model. A subordinate decomposition sequence of subcomponents of the contiguous list is further generated. In one embodiment, the process represents the decomposition sequence as a tree of branches of steps, where each branch may contain a dependent decomposition. An example of a process for generating a decomposed sequence will be described in more detail below.
In step S3, the generated decomposed sequence is inverted to obtain an assembled sequence.
In step S4, building instructions are generated from the generated sequence of builds, e.g., as a sequence of images or other representation of part models, in each of which one or more building elements and sub-components from the generated list are added as compared to the previous part model. The generated descriptions may be stored and/or output in any suitable form as described herein.
Fig. 3 shows a flow chart of an example of the decomposition process of the model M. The decomposition process decomposes the model M, including all building elements in the model, according to the complete digital representation of the model M (step 301). The inputs to the model M comprise information about the individual building elements, such as size/dimensions, number of knobs, characteristics such as hinges, pins, shafts, etc. of the building elements. The numerical representation also includes information about where to place each building element in the model, e.g. by specifying the respective (x, y, z) position of the building element relative to an appropriate coordinate system.
In step 302, the decomposition process tests whether a building element to be separated is left in the model M (or a portion of the model generated in a previous iteration). If there are still building elements in the model, step 303 is performed, selecting/generating one or more candidate sub-components for removal from the model M. The candidate sub-assemblies include interconnected building elements. In a following step 304, the building element to be separated or one of the generated candidate sub-assemblies (E) is selected according to a first set of predetermined selection criteria. This first set of predetermined selection criteria assigns weights to each building element and generated sub-assembly according to a predetermined weighting function, examples of which are described in more detail below. Thus, building elements or sub-assemblies are determined from a pool of candidate items, the pool comprising all individual building elements and generated candidate sub-assemblies. Thus, for the selection process, the sub-assembly may be considered as a pseudo-building element in addition to the actual building element. For purposes of the present description, building elements and members of a candidate sub-assembly are also referred to as candidates to be removed.
In step 303, candidate sub-components are found/selected by a second set of selection criteria (determining how to separate/cut off the model). Examples of such selection criteria are described in more detail below.
In step 305, the building element or sub-component E selected in step 304 is separated from the model, i.e. a new partial model M' ═ M \ E is generated, wherein selected building elements of all building elements of the selected candidate sub-component are removed. A data structure representing the decomposed sequence is maintained and updated with information about the separated sub-components/building elements. The sequence is stored so that it can then be reversed to obtain the assembly instructions.
If a sub-component to be split is selected, the selected sub-component may be split by performing the splitting process in step 307 recursively (i.e., with the selected sub-component E acting as the input model M), and then returning to step 302, continuing the iterative splitting process, looking for the next building element to be split from the remaining partial model (i.e., model M' ═ M \ E.).
When there are no more building elements in the model, the model is completely decomposed, and the decomposition process stops in step 308.
Thus, the embodiment of the decomposition process described above may be expressed by the following pseudo code:
DeconstructmodelM:
LetCandidatesbethesetofallbricksinM
LetResultbeanemptysequenceofbricks
While(Candidatesisnotempty)
LetDbethesubsetofCandidatesthatare
detachable
Letbbethe″bestdetachable″brickfromD
AddbtoResult
RemovebfromCandidates
ReturnResult
in the pseudo code above, the selection of the "best separable" brick corresponds to the selection performed in step 304 above, i.e. the selection based on a set of predetermined selection criteria, e.g. one or more of the selection criteria described below.
Preferably, candidate sub-components that can be separated from the model are first selected and then each candidate is assigned a weight according to the degree of priority of separation, it being possible from a computational point of view to handle this selection when dividing into multiple steps, since assigning weights to sub-components is only pre-formed for a subset of all possible sub-components of the model.
An example of a decomposition process is described by one of the inventors in the paper "Computer-aided division of building in structures for LEGOmodels", written by JacobAllerelli of department of MathesicisandComputerScience, university of southern Denmark, department of Mathesicismatic, and ComputerScience, 2006, which is incorporated herein by reference. Examples of selection rules for determining the second set of selection criteria for candidate sub-components in step 303 will be described in more detail below. These selection criteria will also be referred to as "heuristic cuts".
Minimum cut/graph partitioning:
it has been recognized that by using a graph partitioning technique that partitions a graph into sub-graphs, appropriate candidate sub-components can be efficiently determined. To this end, the model is represented in a data structure representing an undirected graph (comprising nodes and edges connecting the nodes), wherein the nodes represent building elements and the edges represent connections between the building elements. Such a pattern is also called a connectivity pattern. Fig. 7 shows an example of a connectivity graph. Fig. 7a shows an example of a building element model comprising building elements a, b, c, d, and e. Fig. 7b shows the corresponding connectivity graph with nodes a, b, c, d, e.
The edge data items of the graphical data structure may comprise attributes representing the (physical) connection strengths of corresponding connections between the building elements connected by the connections represented by the edges. In this manner, the graph partitioning process for identifying the smallest weight cut of the graph produces sub-components such that the physical strength/strength required to separate the sub-components is at least approximately minimized. In this way, the most loosely connected subassembly is selected. An example of determining the strength of the connection between building elements will be described in more detail below.
The assembly direction is changed:
preferably, the mold with the assembly direction changed is cut. When building elements are interconnected in at least two building directions, a change of building direction may occur. The location of the change in the assembly direction can be found by performing a local graph search in the connectivity graph. The building direction may be defined by associating an orientation attribute with each building element. Alternatively or additionally, the building direction may be defined by assigning a direction attribute to the connections between the building elements. To this end, the nodes and/or edges of the connectivity graph may have attributes associated therewith that represent the assembly direction of the corresponding connection.
Single building block component joint cuts off:
building elements that interconnect two or more subassemblies/building elements are called "articulated building elements" and may be good cut points/nodes of a split model. Once identified, the articular building elements may be included in the separate subassembly, i.e., removed, or may be excluded from the separate subassembly, i.e., not removed. In the figures, the articular building elements may, for example, be marked-for example, by so-called graphic coloring-so that they can be easily positioned. Joint nodes of a connectivity graph can be found by any suitable algorithm for finding joint nodes of a graph, for example, based on a depth-first search (see, e.g., "graph theoryanditsappplications", jonathanl.
The joint pair of the building block component is cut off:
the term "joint pair" refers to two building elements interconnecting two or more non-intersecting subassemblies together, i.e., a pair of building elements whose removal results in the model being decomposed into two or more non-intersecting subassemblies. Subassemblies connected to the rest of the model by articulated building elements or articulated pairs may be useful candidates for generating building instructions.
The joint pairs may be looked up through a process in which a list a of all joint nodes in the connectivity graph G is maintained. Then, a graph G' is generated in which the non-joint nodes n in G are removed. A list B of all joint nodes in G' is kept. For each node m in B \ A, the following joint pairs are found: (n, m), this process is repeated for all the non-articulated nodes n in graph G.
Hinge or joint connection:
the hinge connection is a hinge between one or more building elements around the hinge direction. The building elements may comprise internal hinges or hinge connection elements for providing a hinged connection between two or more building elements. Subassemblies that are connected to the rest of the model by a hinged connection may be useful candidates for generating assembly instructions. Such components may be identified in a connectivity graph when the edges of the graph have associated attributes that indicate the presence of a hinge structure. For example, a sub-graph of the connectivity graph that is connected to the rest of the connectivity graph only by one or more hinge connections may be searched. Fig. 12b shows a toy building element with a connecting element 1201 for providing a hinged connection. It should be understood that other types of removable connections may be used to identify candidate sub-assemblies, such as bonded connections, and the like.
Special cases are as follows:
some building elements are only specific in certain points in the way they can be connected to other building elements. Examples of these building elements are a figure with a single connecting element under the base of the figure, glass in the window, tires on the wheels, and railroad cars on the rails. Thus, these particular building elements are candidates for being cut out of the model in their external connections (i.e. in the locations where they are connected to any building element other than their corresponding building element).
Thus, in the foregoing, a number of heuristic cuts for identifying candidate sub-components are described. In this manner, during the decomposition process, one heuristic cut or a combination of more heuristic cuts, as described above, may be used to efficiently find candidate sub-components among all possible sub-components of the model.
As described above, in one embodiment, each removal candidate-i.e., each building element of the model and each candidate sub-component selected by the above or alternative heuristic cut-off (cut-recurrics) process, is weighted by one or more weighting functions to find the removal candidate with the highest weight, i.e., the removal candidate E that is best suited for removal from the model (step 304), and this selected removal candidate is then isolated (step 305).
In one embodiment, the weighting functions are selected such that each weighting function either enhances the likelihood of a building element/sub-assembly being selected, or it will reject a building element/sub-assembly being selected, depending on the conditions in which it is implemented. The results of all weighting functions for each building element/sub-assembly are combined to obtain the total weight of the building elements/sub-assemblies. The building element/sub-assembly with the highest weight may then be selected. When the individual weighting functions are selected according to a uniform weighting pattern, the set of weighting functions can be easily changed.
For example, in one embodiment, each weighting function results in a weight. The weights are either real numbers in the range [ 0.. multidot., 1], or negative integers (-1., -2., -3.). If it is advantageous to separate building elements/sub-assemblies, when the weight assigned to a building element/sub-assembly lies in the range [01], 0 is assigned when separating building elements/sub-assemblies is neither objected nor advocated, and 1 is assigned when separating is most appropriate. A real number between these two extreme values indicates that the separation between the two is advantageous. If the separation is unfavorable, the weighting function assigns negative weights in the range (-1, -2, -3.) -to the building elements/sub-assemblies, wherein different negative values indicate the degree of the unfavorable separation. It should be appreciated that other sets of weighting functions having different ranges may be defined.
The veto scheme may be implemented using a weighting function having two separate ranges, for example, as described below:
for each building element/sub-assembly x, each weighting function of a set of weighting functions is evaluated, the respective individual weights being combined as follows: if there are no negative weights between the assigned weights of x (so-called "negation"), then all weights are summed to obtain a total weight. On the other hand, if there are one or more "overrules" between the assigned weights, all non-overrules weights are discarded, i.e., set to 0. According to this, a good building element/sub-assembly to be separated is the one without "overruling" and with a high cumulative weight. On the other hand, once a building element/sub-assembly is given a "overrule", it cannot leave the "overrule" state until the next iteration in the decomposition process. If all building elements/sub-assemblies get a negative weight, the building element with the total negative weight with the smallest absolute value may be selected. Alternatively, one or more iterations may be traced back, attempting to select a different building element/sub-assembly, requesting user interaction, or proceeding in another suitable manner.
As a result, the above weighting results in a high quality building instruction when a disassembly process is found (at least one building element/sub-assembly without a "negative" in each step).
Many examples of weighting functions are now described in more detail:
separation strategy:
an example of a weighting function determines whether a building element/sub-assembly to be separated is physically accessible and separable from the rest of the model. To this end, the weighting function verifies whether one or more of the following two requirements are fulfilled:
1) all directions along which building elements/sub-assemblies are detachable/connectable are parallel. In this way, this weighting function may determine the direction of assembly and/or the direction of all connections of a building element, e.g. based on properties associated with corresponding nodes and/or edges in the connectivity graph. If all directions are parallel, the building elements may be separated by a translational movement. For example, building element 803 of FIG. 8a has two non-parallel connection directions: which are connected to the shaft 802 and the toy building elements 804. The connection to the shaft 802 has an associated direction parallel to the shaft 802 because removal of a building element 803 from the shaft 802 requires movement of the building element 803 in a direction along the shaft 802. On the other hand, the connection to the building element 804 has a direction perpendicular to the axis, i.e. in the direction in which the knob protrudes from the top surface of the building element 804. Thus, removal of building element 803 may result in the model being taut, which may be difficult for, for example, a child to perform without simultaneously disengaging other connections of the model. Figure 12 shows an example of a building element with corresponding directions for indicating separability by means of arrows.
2) Moving the building element/sub-assembly in the direction of the connection does not result in interference with other building elements of the model. For example, the weighting function may determine a bounding box of a building element/sub-assembly, determining whether translating the bounding box in the direction of the connection by a predetermined distance results in a conflict/intersection with another building element. Fig. 13 shows a model in which building element 1301 is movable in its separable direction. Alternatively, the weighting function may calculate a building element/sub-assembly geometry extending in the direction of the connection, determining whether the extending geometry conflicts with any other building element/sub-assembly. How much space a building element occupies can be expressed by a simple geometric volume. For example, a building element with 2x4 knobs as shown in FIG. 4 may have 9 conflict boxes associated with it: one collision box fills the entire building element except 8, while 8 knobs fill each collision box. This information may be used to estimate whether building elements conflict/overlap. The collision box information may be used to calculate an extended geometry that represents the space required to separate the building elements.
An example of how to calculate the stretched geometry may include finding the direction in which building elements may be separated, which is the vector d. The building element has N conflict amounts (e.g., as in the example of building element with 2x4 knobs above) and a position (x, y, z).
With building elements BE, vectors d and models M, the separation process may comprise the following steps: for each collision quantity in BE, p1 represents the position of k. When BE moves from p1 along vector d, p2 represents the position of k. Since each collision volume is a box with 8 corners, there will be 8 points at p1 and 8 points at p 2. In a set of points, there will be 16 points in total. When the collision quantity is convex, this set of points will constitute a convex map f.
The process tests whether the figure f conflicts with any building element in the model M. If diagram f conflicts with any building element in model M, building element BE cannot BE detached. If the graph f does not conflict with any building elements in the model M, the next amount of conflict may be tested.
Finally, if none of the N collision quantities has a collision with any building element in model M, building element BE may BE separated according to a separation strategy.
The effect of this strategy is that it ensures that the disassembly (and thus the reverse structure) of building elements/sub-assemblies is physically possible without imposing physical strain on the model.
The following example of a weighting function avoids the separation of physically inseparable (or at least only easily separable) building elements/sub-assemblies:
Weight(x)=-1,ifatleastoneoftheaboveconditions1)and2)isnotfulfilled
forx,
0,otherwise
joint strategy:
as mentioned above, building elements/subassemblies whose removal results in the decomposition of the model into two or more non-intersecting parts are called articular building elements/subassemblies. Separating the articulating building elements/subassemblies may result in a building instruction showing non-intersecting elements/subassemblies that appear to float/fly in the 3D representation of the building instruction. This may be undesirable because it complicates the disassembly process and, thus, the assembly instructions.
The following weighting functions avoid the separation of the articulating building elements/subassemblies:
Weight(x)=-1ifxisanarticulationbuildingelement/sub-assembly
0ifnot
accordingly, it is imperative to remove articulated building elements, which avoids "dangling" building elements/subassemblies.
In an alternative embodiment, the weighting function specifies a neutral weight, e.g. a weight of 0, if x is an articular building element/sub-assembly, and a positive weight, e.g. a weight of 1, if x is not an articular building element/sub-assembly. Thus, in this embodiment, the separation of the joint components is neither opposed nor advocated. This shows that different weights can be adjusted in order to adapt the weighting pattern to different desired effects. In yet another embodiment, different weights are assigned depending on whether a weighting function is calculated for a single building element or sub-assembly. For example, in one embodiment, weight (x) is set to-1 for an articulation subassembly if x is a subassembly, 0 if x is not an articulation subassembly, and weight (x) is set to 0 for an articulation building element in the case of x being a single building element, and +1 otherwise. Thus, in this embodiment, the separation of the joint sub-assembly is prevented, while the separation of joint building elements is only disfavoured.
An integration strategy is as follows:
there are cases where: it is not possible to avoid separate (or "dangling") building elements/subassemblies in the remaining part models. An example of this is shown in figure 8a, which shows gear element 801 on shaft 802, which protrudes through a corresponding cavity of building element 803. When the model is disassembled, the shaft 802 may be removed, resulting in the gear member 801 being separated from the rest of the model, as shown in FIG. 8 b.
In such a case, it may be desirable to remove the separated member 801 from the model as quickly as possible, resulting in the situation shown in fig. 8 c.
Quick removal of a detached element may be achieved by assigning an increasing weight to a building element/sub-assembly (directly or indirectly) connected to fewer other building elements by a weighting function: an example of such a weighting function is:
Weight(x)=1/(number_of_buildingelements_connected_to_x+1)forall
buildingelements/sub-assembliesx
in the example of fig. 8b, the weighting function above assigns a weight of 1 to pinion 801, since it is not connected to any other building element or sub-assembly. On the other hand, other building elements are assigned a weight 1/6 because they are part of an assembly that includes five elements denoted 803, 804, and 805.
In this manner, the integration strategy reduces the number of steps in which inevitable "flying" building elements or sub-assemblies are displayed in the generated building instructions.
Similarity strategy:
the similarity strategy involves symmetry in assembly/disassembly. When using the similarity strategy during assembly, the structure may become symmetrical, which simplifies the decomposition process. To perform a decomposition based on this, a function indicating that the two building elements a and B are "similar" may be determined as follows.
The weighting function determines the coordinates of a and B in a coordinate system, where the y-axis corresponds to the principle assembly direction, e.g. the vertical direction. The x-axis and z-axis correspond to other major assembly directions, e.g., horizontal.
If B is the last building element to split, then the weighting function used to determine whether A and B are similar may have the form:
Weight(x)=sumof
aifAandBisthesametypeofbuildingelement
bifAandBhavethesamexcoordinateorthesamez
coordinateinthecoordinatesystem
cifAandBarehavingthesameattributes(suchascolor,
decorationetc.)
forpredeterminedweightsa,b,cwherea+b+c=1.
weights above 0 reflect some degree of similarity. Alternative and/or additional conditions may also be considered.
The strategy is to separate building elements/sub-assemblies, similar to the last building element or sub-assembly that was separated. The effect of this strategy is that models containing symmetric pieces are often symmetrically decomposed.
Fig. 9 gives an example of similarity for decomposition, illustrating an example of three consecutive decomposition steps in fig. 9a) -c), respectively. As can be seen from fig. 9, in the left part of the model, first the rectangular building element 901 is separated, and then a similar rectangular building element 902, symmetrical to the first rectangular building element, is separated. The next step may be to separate the two similar rectangular building elements 903 of the right part of the model.
Basic strategy:
a particular building element or sub-assembly, such as a large panel or an irregularly shaped panel, is often the base/starting building element of the model and, therefore, the last separate building element. To check whether a plate or other building element is a starting building element, its type and/or size may be compared to the type/size of the other building elements or to a threshold value indicating that the building element is relatively large, since the starting building element is often relatively large, since it forms the basis of the model. Furthermore, it is also possible to check whether a large building element is a starting building element by analyzing how low a position is placed in the model. Building elements are large and placed at the bottom of the model are likely to be the starting building elements. To this end, the nodes of the connectivity graph may have associated with them respective attributes representing the size/volume of the building elements. Alternatively, the building instruction process may allow the user to indicate the starting building element, for example, by using a mouse or another pointing device. Accordingly, the weighting function that prevents the starting building element from being removed from the model may have the following form:
Weight(x)=-1ifxisastarterbuildingelement
0ifnot.
alternatively, if x is an originating building element/sub-assembly, the weighting function may assign a weight of 0, thus indicating that the splitting of x is disadvantageous, and if x is not an originating building element/sub-assembly, a high positive weight is assigned, e.g. a weight of 1, since the splitting is advantageous.
The effect of this is that in the resulting building instructions, certain common base building elements or sub-assemblies will be connected initially or at an early stage of the building process.
Step-by-step integrity policy:
according to one embodiment, for each candidate subcomponent x, there are two contributing aspects that reflect/contribute to the quality of connectivity. The first aspect is the strength of the internal connectivity between the building elements of sub-assembly x, while the second aspect is the strength of the external connectivity of the building elements of sub-assembly x. If the internal connectivity is relatively strong and the external connectivity is relatively weak, it may be desirable for the subassembly to be easily removable because the building elements in the subassembly are strongly connected to other building elements in the subassembly and only weakly connected to the rest of the model. Accordingly, a subassembly having a strong internal connection and a weak connection to the rest of the model, possibly as a stable subassembly, is relatively easy to assemble during the assembly process and is connected to the rest of the model without the risk of disassembly of the subassembly during the assembly process.
In order to investigate how strongly the sub-assemblies are connected internally, i.e. how the different building elements of the sub-assemblies are connected to each other, a connectivity pattern or another suitable representation of the connectivity between all building elements may be used. Connectivity graphs may include weights reflecting the physical strength between building elements, as described above, e.g., when each edge has an attribute/weight associated with it that represents the strength of the corresponding connection.
For example, each building element may include one or more coupling elements for engaging corresponding coupling elements of other building elements to provide a connection between multiple building elements. For example, FIG. 4 shows an example of a building element with a protrusion in the form of a knob (for engaging a cavity of another building element (also referred to as a counter-knob.) in general, a building element may have one or more different classes of connecting elements, each class of connecting element, or each pair of classes of connecting elements, may provide a connection of corresponding strength. And/or included in nodes and/or edges of the connectivity graph. Examples of data structures supporting the definition of connection elements are described in WO 04/034333.
For example, the strength of the connection between building elements x and y may be calculated as follows:
wherein the sum extends over all connection classes c, ScIs the bond strength of bond class c, and N (c) is the contribution of x and yThe number of connecting elements of class c of the connection between.
An example of how to determine the physical strength of the connection between two building elements x and y (with connecting elements, pegs and shafts in the form of knob/counter-knob (or cavity) pairs) of the type shown in fig. 4 is given below:
Strenght(x,y)=Sumof:
1foreachconnectingknob/anti-knobpair
10foreachpeg
5foreachaxle
it should be understood that the numerical values in the above examples are merely examples.
When the geometry of the building elements is further taken into account when calculating the effective strength, the effective strength of the connectivity can be estimated more accurately.
For example, FIG. 10 shows two sub-assemblies, each comprising two building elements interconnected by a single connecting element of the form described with reference to FIG. 4. However, the subassembly of FIG. 10a is strongly connected, i.e., difficult to disassemble, whereas the subassembly of FIG. 10b is not very easy for a user to remove the building element 1001 from the base plate 1002. This difference can also be adjusted for by incorporating the volume or mass of the smallest/lightest building element relative to the strength of its connection. Alternatively, or in addition, another suitable number representing a geometric property of a building element may be used. This simulates how easily a user grips a building element with a user's finger, for example, because a large building element is easier to grip than a small building element.
Thus, such a modified weighting function may be expressed as:
Connection(x,y)=Strenght(x,y)/Minimum(volumeofx,volumeofy)
thus, in the example shown in FIG. 10, the two subassemblies have the same strength between multiple building elements, since in both cases the small building elements are connected together in one knob-anti-knob pair. However, in the sub-assembly of FIG. 10a, the smallest building element 1003 has a smaller volume, whereas in the sub-assembly of FIG. 10b, the smallest building element 1001 has a larger volume, and thus, the function connection (x, y) will be the largest for the sub-assembly of FIG. 10 a.
An example of a weighting function based on the above connectivity metric may be as follows:
Weight(x)=-1ifxisasub-assemblyand
itsweakestinternalconnection<internalthreshold
value
-1ifxisasub-assemblyand
itsstrongestexternalconnection>external
thresholdvalue
0otherwise
the thresholds for internal and external connections may be predetermined, user controlled, empirically found or otherwise suitably set. Adjusting the threshold is an effective way to adjust the number and quality of the sub-steps of the generated assembly specification. By setting the threshold to a relatively high value, fewer high quality candidate sub-components may be obtained, rather than obtaining many lower quality candidate sub-components. This makes the decomposition process easier and faster.
The closest strategy is as follows:
weights may also be assigned to building elements/sub-assemblies based on distance from previously separated building elements/sub-assemblies. More specifically, weight (x) may be a function of distance, the square of the distance, or another suitable distance measure of the centroid of x from the centroid of a previously separated building element/subassembly. It will be appreciated that another suitable reference point for the building elements/sub-assemblies may be used instead of the centre of mass.
Higher weights may be given to building elements that are closer to previously separated building elements/sub-assemblies. When the building elements are in contact with each other at least at one point, the distance between them may be set to 0. The closest strategy may distinguish building elements having surfaces adjacent to each other, the building elements only contacting each other at their corners, as shown in fig. 11a and 11b, respectively. Thus, in one embodiment, the weighting function may be an increasing function of the size of the area of abutment between two building elements. Whether building elements are adjacent to each other, or otherwise in contact with each other, may be determined based on bounding boxes or other geometric information stored as part of the numerical representation. One way of approximating such a measure is by calculating the maximum distance between points of the respective building elements. Generally, the greater this distance, the smaller the area of abutment, as shown in FIG. 11.
A lamination strategy:
when assembling the mould, the assembly is preferably performed from the bottom up. Thus, weights may be assigned to building elements/subassemblies based on distance from the lowest building element in the model. The further away the building element/sub-assembly is from the base, the higher the weight is given during the disassembly process. Thus, in general, the weighting function may be an increasing function of the coordinates of the building elements along one or more directions of the coordinate system.
Thus, in the above, many examples of weighting functions are described, each corresponding to a corresponding model decomposition strategy. It should be appreciated that the decomposition process may include alternative or additional weighting functions and/or alternative or additional decomposition strategies. Further, alternative and/or additional weighting functions corresponding to the decomposition strategies described herein may also be defined.
It will further be appreciated that certain strategies described herein have one or more parameters that may be varied to enhance one or the other aspect of the results, thereby making the framework a tool for generating building instructions through human interaction rather than a black-box.
The inventors have obtained particularly good results with a combination of weighting functions corresponding to the following strategies, ensuring the integrity of the decomposition. Together they may constitute the backbone of an embodiment of the automatic building description generator that provides good results, without user interaction:
-a separation strategy: only physically removable building elements or sub-assemblies are allowed to be separated, given the geometry and connectivity of the building elements or sub-assemblies.
-step integrity policy: only components that are strongly connected internally and weakly connected externally are allowed to be separated.
As described above, the accuracy requirements may vary to ensure the desired quality of the sub-steps.
-joint strategy: allowing only separation sub-components that do not split the model into two or more separate components. Furthermore, the separation of individual building elements that split the model into two or more separate sub-assemblies is not favored.
-an integration strategy: if a single articulating building element is removed, the separate building elements or subassemblies are removed as quickly as possible.
In one embodiment, the four strategies mentioned above-separation, step-wise integration, articulation and integration-are used in all assembly/disassembly, while one or more further strategies, e.g., one or more of the remaining strategies described herein, e.g., similarity, base, closest and stacking strategies, may be used in different circumstances to adjust the results. Such a policy may be selected by the user. Fig. 4 shows an example of a building element and its connecting elements. Specifically, FIG. 4 shows a perspective view of a building element 401. The building element 401 has a top surface 402 with eight knobs 403a-h that can engage corresponding cavities of another building element, e.g. cavities on the bottom surface of another building element. Accordingly, the building element 401 includes a bottom surface (not shown) with corresponding cavities. The building element 401 further comprises a side 404 without any connecting elements.
In general, the connecting elements can be divided into different classes of connecting elements, such as connectors, receptors, and hybrid components. A connector is a connecting element that may be received by a receptacle of another building element to provide a connection between the building elements. For example, the connector may be installed into a cavity between components of another component. The receptacle is a connecting element which can receive a connecting element of another building element. A hybrid component is a component that can act as both a receptacle and a connector, typically depending on the type of cooperating connecting elements of the other building elements.
Building elements of the type shown in fig. 4 are available under the name LEGO, and come in many shapes, sizes, and colors. Furthermore, there are also such building elements with various connecting elements. It should be understood that the above building elements are only examples of possible building elements.
FIG. 5 shows an embodiment of a data structure that numerically represents a building element model. The data structure 501 may include one or more data records 502, including overall model parameters related to the overall model. Examples of such model parameters include the model name, the name of the model author, the program version number of the modeled application, the creation date, and so forth. Model data structure 501 further includes a list 503 or other suitable structure of building element data records. In the example of fig. 5, the list includes N data records "building element 1", "building element 2", "building element J", ". Each building element data record of list 503 has the structure shown by data structure 504 for "building element J".
Specifically, each building element data record includes a building element ID505, representing an identifier corresponding to the type of building element. Building element ID may uniquely identify an attribute of a building element or a type of building element.
The building element data record may further include a number of building element attributes 506 representing one or more attributes of the building element, such as color, texture, decoration, and the like.
Additionally, building element data record 504 also includes data items 507 and 508, respectively, representing the position and orientation of the building element's internal coordinate system. The position and orientation of a building element is defined by the origin of the building element's internal coordinate system relative to the coordinates of the global "world" coordinate system and by the orientation of the internal coordinate system relative to the global coordinate system.
An example of a data format for storing building element models, including a hierarchy of coordinate systems, is illustrated in us patent No.6,389,375.
Additionally, building element data record 504 may also include data items 509 and 510 representing one or more bounding boxes and connectivity data, respectively, for building elements for detecting connectivity properties of the building element with other building elements. An embodiment of a representation of connectivity data for a type of building element as shown in FIG. 4 includes a data structure representing a plane defined by a surface of a bounding box of the building element. The coupling elements of the building elements, each having an axis associated with it, are located on these planes. The axes of all connecting elements on the same plane correspond to respective grid points of a regular grid (e.g. an orthogonal grid), the distance between adjacent grid points being fixed. The planes associated with the building elements 401 of fig. 4 are parallel to each other in pairs and comprise a set of horizontal planes corresponding to the top and bottom surfaces of the building element and a number of vertical planes corresponding to the sides of the building element. The distance between adjacent grid points may be the same in all horizontal planes. In some embodiments, the distance between adjacent grid points in the vertical plane is different from the distance between adjacent grid points in the horizontal plane. Numerical representations of connectivity attributes for building elements of the type shown in figure 4 are described in WO04/034333, the entire contents of which are incorporated herein by reference.
It will be appreciated that the digital representation may be encoded in any suitable data or file format, for example, as a binary file, as a text file according to a predetermined model flower description language, and so forth. It should be further appreciated that other embodiments of digital information may utilize alternative or additional data structures, and/or represent alternative or additional model data.
FIG. 6 shows an embodiment of a graphical user interface for assembling an illustration application. The user interface includes a viewing area 701 illustrating a graphical representation of a set of steps of the step-by-step assembly instruction. The graphical representation shows a 3D view of a portion of the model 702 displayed from a predetermined camera position. Partial model 701 includes a subset of all the building elements of the complete model, where the subset includes the initially positioned building elements. The viewing area 701 further comprises a graphical representation 703 of the most recently placed building element, i.e. a building element that distinguishes the current partial model 702 from the partial models of the previous steps. In this example, these are building elements 714, 715, and 716 of partial model 702.
The user interface further includes a slider control element 709 that is movable at individual intervals by a corresponding drag operation with a mouse, enabling the user to select any one step of the one-step specification. In the example of FIG. 6, three new building elements are added in each step of the illustration.
The user interface further includes a button control element 705 that enables the user to invoke a number of commonly used functions, such as sequentially browsing the graphical representation in the forward and reverse directions, respectively, jumping to the first and last steps of the description, changing the camera position, printing the generated assembly description, and initiating an "auto-play" function. The auto-play function displays the sequence of partial models one by one so that each partial model is displayed for a predetermined length of time. Preferably, the user can configure the viewing time of each partial model with an auto-play function.
Finally, the user interface also includes a number of drop down menus 704 that enable the user to initiate functions such as a help function, a function to change the camera position, an image magnification function, and the like. Further functionality provided by the build specification application includes loading a digital representation, a print function for printing a graphical representation of the part model, and an export function for exporting a sequence of graphical representations of the part model, for example in HTML format, or any other suitable graphical file format, such as TIF, JPG, BMP, or the like.
Further examples of functionality provided by the building description application include a bill of materials function that enables a user to view or print a list of all building elements in a model.
FIG. 14 shows a flow diagram of another embodiment of the generation of an assembly specification. In step S1, a digital representation M of a building element model is received, e.g., as described with reference to step S1 of FIG. 2.
In subsequent steps S2-S12, the building instruction application generates the building instructions 205 from the loaded digital representation. The generated assembly instructions 205 may be in the form as described with reference to fig. 2.
In step S2, the process is initialized. In particular, a data structure Result is initialized for holding the assembly sequence to be generated. The sequence Result is initialized to a null sequence. A set of candidate building elements, denoted Candidates, is further initialized to the set of all building elements and sub-components in model M. Thus, as in the previous embodiments, one or more candidate sub-components to be removed from the model M may be determined and treated as building elements in general. Candidate sub-components may be found/selected by a set of selection criteria (determining how to separate/cut off the model). Examples of such selection criteria are described in more detail above, in particular, the second set of selection criteria described with reference to step 303 of fig. 3. It should be appreciated that in other embodiments, only building elements may be considered.
In step S3, a determination is made as to whether the set Candidates is empty, i.e., whether all building elements have been processed. If this is the case, step S12 is executed; otherwise, step S4 is executed.
In steps S4-S11 it is determined whether an assembly step b can be found which leads to the generation of a new partial model, so that the complete model M can be decomposed into this new partial model.
Specifically, in step S4, a secondary set C of building elements and sub-components is generated as a copy of the set Candidates.
In step S5, it is determined whether the set C is empty, i.e., whether one candidate b is identified. If this is the case, return to step S3; otherwise, step S6 is executed.
In step S6, a candidate building element b or a candidate sub-assembly is selected from set C.
The selection of candidates in this embodiment may be done in a similar way as the selection in the exploded case of the previous embodiment, i.e. by a set of selection criteria, with building elements removed. In particular, the selection criterion may be based on one or more weighting functions representing different assembly strategies, such as the one or more weighting functions described above, in particular the weighting functions of the first set of selection criteria described with reference to step 304 of fig. 3. Some of the weighting functions are the same or substantially the same in the assembled and disassembled versions, respectively, e.g., as described in more detail above. For example, one strategy may assign a weight to building elements based on their distance from the building element added in the previous step. The closest building element to the previously added building element may then be selected. Other weighting functions may be quite different. For example, the "articulation strategy" of the exploded condition described above avoids the disassembly of the connectivity pattern, while in the assembled condition of the present embodiment, it is merely ensured that a building element is selected that is actually connected to any previously selected building element. In both cases, however, "flying" building elements are avoided. Since the weighting functions described herein may weight sub-components (pseudo-log components) as well as simple building components, both the assembly and disassembly processes may be generalized to process the sub-components. This is not only feasible, but sometimes also desirable, as in the case of pure decomposition.
Alternatively, or in addition, the selection of the candidate may be based in part or in whole on user input/interaction. For example, a user input representing candidate b may be received. Alternatively, one or more possible candidates may be selected, e.g. randomly or based on the weighting function described above, and the candidates indicated to the user. User input may then be received indicating approval or rejection of one or more of the suggested candidates.
In step S7, a partial decomposed sequence is generated from the received digital representation of the model up to the remaining models obtainable by the combination of the current assembled sequence Result and the selected candidate b. The decomposed sequence may be generated in the form of a continuous list of building elements and/or sub-components of the model. Dependent decomposition sequences of sub-components of the contiguous list may be further generated. In one embodiment, the process represents the decomposition sequence as a tree of branches of steps, where each branch may contain an attached decomposition.
An embodiment of a process for generating a partially decomposed sequence will be described in more detail below.
In step S8, it is determined whether or not a decomposition sequence can be found. If the decomposition process of step S7 succeeds in determining the decomposition sequence, then execution continues with step S9; otherwise, execution continues with step S10.
In step S9, the set Candidates, Result, and C are updated. In particular, the selected candidate b is added to the current Result sequence Result, the candidate b is removed from the set of Candidates, and all members are removed from the auxiliary set C (with the successfully identified candidate). Then, the process returns to S5.
In step S10, an attempt is made to remove b from the auxiliary candidate set C. In step S11, it is determined whether candidates remain in C. If this is the case, return to step S5 to identify alternative candidates; otherwise, the process ends, e.g., with an appropriate error flag or message indicating that the generation of the build specification failed. This may occur, for example, if the model is over-constrained and/or if the weighting function used in the decomposition process represents that the assembly of the model is too constrained/restrictive. Thus, in such cases, some or all of the weighting functions used in the decomposition process may be weakened, e.g., automatically or through user interaction, and the process may be restarted with the weakened weighting functions.
In step S12, building instructions are generated from the generated building sequence Result, e.g. as a sequence of images or other representation of part models, wherein in each part model one or more building elements and sub-components from the generated list are added compared to the previous part model. The generated descriptions may be stored and/or output in any suitable form as described herein.
Fig. 15 shows a flowchart of an example of a partial decomposition process of the model M up to the remaining model N. The decomposition process decomposes the model M, including all building elements in the model, according to the complete digital representation of the model M (step 301). The inputs to the model M comprise information about the individual building elements, such as size/dimensions, number of knobs, characteristics such as hinges, pins, shafts, etc. of the building elements. The numerical representation also includes information about where to place each building element in the model, e.g. by specifying the respective (x, y, z) position of the building element relative to an appropriate coordinate system. Information about the remaining set N (i.e. the submodels of the model M) is further received. The partial decomposition process generates a sequence of decomposition steps in which, in each decomposition step, one or more building elements of M \ N (i.e., building elements of model M that are not included in the inherently remaining model N) are removed until only the remaining model N remains.
In step 302, the decomposition process tests whether the building element to be separated is left behind in the model M \ N (or in the part of the model M \ N generated in the previous iteration). If there are still building elements in the model to be removed, execution continues to step 303, in which one or more candidate sub-components to be removed from the model M \ N (or the portion of the model M \ N resulting from the previous iteration) are selected/generated. The candidate sub-assemblies include interconnected building elements. In a subsequent step 304, the building elements to be separated or one of the generated candidate sub-assemblies (E) is selected according to a first set of predetermined selection criteria, e.g. as described with reference to FIG. 3. Candidate sub-components may be found/selected in step 303 by a second set of selection criteria (determining how to separate/cut off the model). Examples of such selection criteria are described in greater detail above.
In step 305, the building element or sub-component E selected in step 304 is separated from the model, i.e. a new partial model M' ═ M \ E is generated, wherein selected building elements of all building elements of the selected candidate sub-component are removed. A data structure representing the decomposed sequence may be maintained and updated with information about the separated sub-components/building elements.
If a sub-component to be separated is selected, the selected sub-component may be decomposed by performing the decomposition process in step 307 in a recursive manner (i.e., with the selected sub-component E and the remaining model N as inputs), and then returning to step 302, continuing the iterative decomposition process, looking for the next building element to be separated from the remaining component model (i.e., model M' \ N \ E \ (E _. N)).
When no more building elements (nor part of the remaining model N) are to be removed from model M, the partial decomposition of model M is completed until the remaining model N, and the decomposition process stops in step 308.
Thus, in general, given a model M, if M can be decomposed into N, then N can be assembled into M. In other words, the structure of the N-stage is an appropriate intermediate model during the sequence of assembly steps, if (and only if) the complete model M can be decomposed into N.
An embodiment of a process for generating the assembly sequence described with reference to fig. 14 and 15 may be expressed by the following pseudo code:
ConstructmodelM:
LetCandidatesbethesetofallbricksandsub-
assembliesinM
LetResuitbeanemptysequenceofbricks
While(Candidatesisnotempty)
LetCbeacopyofCandidates
While(Cisnotempty)
LetbbeabrickfromC
If(DeconstructMdownto(unionofResultandb))
RemoveallbricksfromC
Candidates=Candidates\b
AddbtoResult
Else
RemovebfromC
If(Cisempty)
Error:″Constructionwasnotpossible″
ReturnFalse
DeconstructmodelMdowntoN:
LetCandidatesbethesetofallbricksinM/N;
While(Candidatesisnotempty)
LetDbethesubsetofCandidatesthataredetachable
If(Disempty)
ReturnFalse;
Else
Letbbethe″bestdetachable″brickfromD;
RemovebfromCandidates;
ReturnTrue;
in the above pseudo-code, the selection of the "best separable" brick corresponds to the selection performed in step 304 above, i.e. the selection based on a set of predetermined selection criteria, e.g. one or more of the selection criteria described above.
Embodiments of the process may also be expressed by the following pseudo-code; FIG. 16 shows a flow chart of this embodiment:
ConstructmodelM:
LetCandidatesbethesetofallbricksandsub-
assembliesinM
LetResultbeanemptysequenceofbricks
While(Candidatesisnotempty)
LetCbeacopyofCandidates
If(FindconstructionstepbfromC)
AddbtoResult
Candidates=Candidates\b
Else
Error:″constructiveBuildinginstructionnot
possible″
ReturnFalse
ReturnTrue
FindconstructionstepbfromC:
While(Cisnotempty)
Letbbea′good′brickfromC
If(DeconstructMdownto(unionofResultandb))
ReturnTrue
Else
RemovebfromC
ReturnFa]se.
thus, in this embodiment, it is known whether the next assembly step b is to be determined as a separate function. Fig. 16a shows the overall process, while fig. 16b shows a flow chart of an example of a function identifying a possible/valid next assembly step.
Starting from the input step S1 and the initialization step S2 described with reference to fig. 14. In step S3, a determination is made as to whether the set Candidates is empty, i.e., whether all building elements have been processed. If this is the case, step S12 is performed, as described above, to generate an assembly specification; otherwise, step S4 is executed.
In step S4, a secondary set C of building elements and sub-components is generated as a copy of the set Candidates.
In step S20, it is determined whether a valid next assembly step b can be found. If this is the case, updating the Results and Candidates data structures by appending the identified step b to the Results data structure and by removing the corresponding building element (or sub-component) from the Candidates data structure; then, the process returns to step S3. If no valid assembly steps can be found, the process ends, for example, with an error flag or message indicating that the generation of the assembly specification failed, as described with reference to FIG. 14.
FIG. 16a shows a flowchart of an example of a sub-process implementing step S20: first, it is determined whether the set C is empty, i.e. whether all candidates b have been processed. If so, returning a value indicating that a valid candidate b cannot be found; otherwise, step S6 is executed.
In step S6, a candidate building element b or a candidate sub-assembly is selected from set C, e.g., as described with reference to step S6 of FIG. 14.
In step S7, a partial decomposed sequence is generated from the received digital representation of the model up to the remaining models obtainable by the union of the current assembled sequence Result and the selected candidate b, as described with reference to step S7 of fig. 14.
If the decomposition process of step S7 succeeds in determining the decomposition sequence, returning a value indicating that the process was successful; otherwise, execution continues with step S10.
In step S10, an attempt is made to remove b from the auxiliary candidate set C, and a return is made to the start of the sub-process to determine whether C is empty.
In this example, the function "deconstructmodelmdownon" may be the same function in the above example.
In the embodiment described with reference to fig. 14-16, the building of a model with N building elements requires N building steps, and in general, for each building step, multiple decompositions may have to be performed in order to find a valid candidate brick b.
The number of iterations required can be estimated as follows: a complete assembly specification of N tiles requires roughly N assembly steps. Each assembly step may require approximately N/2 decompositions. Each decomposition comprises approximately N decomposition steps. Each decomposition step requires roughly N/2 times brick weighting. Collectively, a complete building instruction may require weighting of approximately (N ^4)/4 building elements. This is still much better than the x N weighting required for pure traceback search. Similarly, the complete decomposition process described with reference to FIGS. 2 and 3 requires approximately (N ^2)/2 weights.
Claims (72)
1. A computer-implemented method of generating building instructions for a building element model, the building element model comprising a plurality of building elements, the building instructions representing a sequence of construction steps for constructing the building element model, each construction step comprising adding at least one building element to the building element model; the method comprises the following steps:
-determining at least one sequence of decomposition steps for at least partially decomposing said building element model into a number of building elements, each decomposition step comprising removing at least one building element from said building element model, based on a digital representation of said building element model;
-determining at least one assembly step in the sequence of assembly steps based on at least one step of the plurality of disassembly steps;
wherein determining the sequence of decomposition steps comprises performing an iterative process, wherein an iteration of the iterative process comprises:
-obtaining a previous part model resulting from a previous iteration;
-determining at least one building element to be separated from a previous part model resulting in a new part model,
wherein determining at least one building element to be separated from a previous portion of the model comprises:
-determining a set of candidate sub-assemblies of the previous part model, each candidate sub-assembly comprising a respective interconnected building element of the previous part model; wherein determining the set of candidate sub-components comprises selecting the candidate sub-components according to a second set of selection criteria; and wherein at least one of the second set of selection criteria comprises determining a connection strength of one or more candidate sub-components to the previous portion of the model;
-selecting a single building element, or one of the determined sets of candidate sub-components to be separated from the previous part-model resulting in the generation of a new part-model, according to a first set of predetermined selection criteria.
2. A method according to claim 1, wherein building elements are interconnectable along at least two building directions; and wherein at least one of the second set of selection criteria comprises determining one or more locations in the previous portion of the model where the orientation of the assembly changed.
3. A method according to any of claims 1-2, wherein one or more building elements comprise a connector for providing a moveable connection around at least one direction; and wherein at least one of the second set of selection criteria comprises determining one or more sub-components that are removably connected to the previous portion of the model.
4. The method of any of claims 1-2, further comprising determining a sequence of decomposition steps for each sub-component selected for removal in one iteration of an iterative process.
5. A method according to any one of claims 1 to 2, comprising representing the previous part of the model by means of a data structure representing a graph comprising nodes representing respective building elements of the previous part of the model, and edges connecting respective nodes representing connections between corresponding building elements.
6. A method according to claim 5, wherein an edge of the graph has an associated connection strength value representing the connection strength of connections between building elements corresponding to nodes connected by the edge.
7. A method according to claim 6, wherein each building element comprises one or more coupling elements for engaging with one or more corresponding coupling elements of another building element to provide a coupling between that building element and the other building element, each coupling element having a coupling element class associated with it, each coupling element class having a coupling strength associated with it; and wherein the method comprises determining the associated connection strength value corresponding to an edge of a connection between two building elements, based on the number of connecting elements and the respective category at least contributing to the corresponding connection.
8. A method according to claim 6 or 7, wherein determining the associated connection strength value comprises determining the connection strength as a function of the number and respective class of connection elements contributing to the corresponding connection, and as a function of the volume of two building elements.
9. The method of claim 5, comprising performing a graph partitioning process to determine a set of candidate sub-components of a previous portion model.
10. A method according to claim 5, wherein an edge of the graph has a value representing an association of a direction of makeup of connections between building elements corresponding to nodes connected by the edge.
11. The method of claim 5, comprising identifying one or more joint nodes of the graph to determine a set of candidate sub-components of a previous portion model.
12. The method of claim 5, comprising identifying one or more joint node pairs of the graph to determine a set of candidate sub-components of a previous portion model.
13. A method according to claim 5, wherein one or more building elements comprise a connector for providing a moveable connection about at least one direction; and wherein at least one of the nodes and edges of the graph has an associated value indicating the existence of a moveable connection.
14. A method according to any of claims 1-2, wherein determining at least one building element to be separated from a previous part model resulting in a new part model comprises calculating one or more weighting functions for at least one of a subset of building elements and a set of candidate sub-assemblies of building elements; and selecting one of the individual building elements and sub-assemblies based on a comparison of the calculated weighting functions.
15. The method of claim 14, wherein at least one of the one or more weighting functions has a range of possible outcomes including a first sub-range representing a degree of adequacy of separation and a second sub-range representing a degree of inadequacy of separation.
16. A method according to claim 15, wherein selecting an individual building element or sub-assembly based on a comparison of the calculated weighting functions comprises calculating a total weight according to one or more calculated weighting functions; wherein the process of calculating the overall weight comprises assigning a value in a second range to the overall weight if at least one of the calculated weighting functions has a result in the second range.
17. A method according to claim 14, wherein each building element comprises one or more coupling elements for engagement with one or more corresponding coupling elements of another building element; wherein each connecting element defines a direction of separation along which a building element is separable from another building element; and wherein the process of calculating a first of the one or more weighting functions of a building element or sub-assembly comprises determining whether the respective directions of separation of all connectors of a building element or sub-assembly connected to one or more other building elements of a previous part of the model are parallel to each other.
18. A method according to claim 17, wherein the process of calculating a first weighting function for a building element or sub-assembly further comprises determining a minimum distance in the direction of separation between the building element or sub-assembly and any other building element or sub-assembly of the previous part of the model.
19. A method according to claim 17, wherein the process of calculating a first weighting function for a building element or sub-assembly comprises
-determining an extended geometry of a building element or sub-assembly, wherein said extended geometry extends in a separating direction, and
-determining whether the stretched geometry intersects any other building element or sub-assembly of the previous part model.
20. The method of claim 14, wherein calculating a second weighting function of the one or more weighting functions for a building element or sub-assembly further comprises determining whether the building element or sub-assembly is an articulating building element or sub-assembly.
21. The method of claim 14, wherein calculating a third weighting function of the one or more weighting functions for a building element or sub-assembly further comprises determining whether the building element or sub-assembly is part of an articulation pair of a building element or sub-assembly.
22. A method according to claim 14, wherein a fourth weighting function of the one or more weighting functions of a building element or sub-assembly is a function that decreases with the number of other building elements to which the building element or sub-assembly is connected.
23. A method according to claim 14, wherein a fifth weighting function of the one or more weighting functions is a function of the connection strength of connections between building elements of a sub-assembly.
24. A method according to claim 23, wherein calculating a fifth weighting function comprises determining the weakest connection strength between interconnected building elements of the sub-assembly, and wherein the fifth weighting function is a decreasing function of the determined weakest connection strength.
25. A method according to claim 14, wherein a sixth weighting function of said one or more weighting functions is a function of the connection strength of the connections of a building element of a sub-assembly to other building elements of a previous part model.
26. A method according to claim 25, wherein calculating said sixth weighting function comprises determining the strongest connection strength between a building element of a sub-assembly and one or more other building elements of a previous part of the model not included in said sub-assembly, and wherein said sixth weighting function is a decreasing function of said determined strongest connection strength.
27. A method according to claim 14, wherein a seventh weighting function of said one or more weighting functions of a building element or sub-assembly is a function of a position coordinate of the building element or sub-assembly along a predetermined direction relative to a coordinate system.
28. A method according to claim 14, wherein an eighth weighting function of said one or more weighting functions of building elements and sub-assemblies is a function of at least an attribute of a building element and a sub-assembly and an attribute of a building element or sub-assembly that was separated in a previous iteration of said iterative process.
29. A method according to claim 28, wherein said eighth weighting function is a function of the distance between a building element or sub-assembly and a building element or sub-assembly separated in a previous iteration of said iterative process.
30. A method according to claim 28 or 29, wherein said eighth weighting function is a function representing at least a predetermined measure of similarity of a predetermined spatial relationship between a building element or sub-assembly and a building element or sub-assembly separated in a previous iteration of said iterative process, and a comparison of one or more properties associated with a building element or sub-assembly and a building element or sub-assembly separated in a previous iteration of said iterative process.
31. A computer-implemented method of generating building instructions for a building element model, the building element model comprising a plurality of building elements, the building instructions representing a sequence of construction steps for constructing the building element model, each construction step comprising adding at least one building element to the building element model; the method comprises performing an iterative process, wherein an iteration of the iterative process comprises:
obtaining a sequence of assembly steps resulting from a previous iteration, the sequence of assembly steps resulting in a first partial model;
determining a subsequent assembly step in the sequence of assembly steps based on at least one of the plurality of disassembly steps by performing the steps of:
-determining a candidate building step representing the joining of at least one subsequent building element to the first part model, resulting in a second part model;
-determining, from a digital representation of said building element model, at least one sequence of decomposition steps for at least partially decomposing said building element model into a number of building elements, each decomposition step comprising removing at least one building element from said building element model in order to determine whether a building element model can be decomposed by a sequence of decomposition steps for decomposing a building element model resulting in a second partial model;
-if it is determined that the building element model can be decomposed by a sequence of decomposition steps for decomposing the building element model resulting in a second partial model, appending the determined candidate construction steps as subsequent construction steps to the obtained sequence of construction steps.
32. A method according to claim 31, wherein the building elements are interconnected.
33. A method according to claim 1 or 31, wherein said digital representation comprises respective position coordinates of each building element with respect to a predetermined coordinate system.
34. A method according to claim 1 or 31, further comprising generating said digital representation of a virtual building element model by means of a computer-implemented assembly environment for interactively assembling said building element model.
35. The method of claim 1 or 31, comprising generating a sequence of graphical representations of the partial models, the incremental partial models, and the complete model, including a corresponding sequence of partial models of the initial partial model; wherein each incremental part model comprises all building elements of the immediately preceding incremental part model of the sequence, and a predetermined number of additional building elements from the plurality of building elements, wherein the additional building elements are determined by the determined sequence of building steps.
36. The method of claim 35, further comprising providing a user interface to facilitate user-controlled processing of the generated graphical representation.
37. An apparatus for generating building instructions for a building element model, the building element model comprising a plurality of building elements, the building instructions representing a sequence of building steps in which the building element model is to be built, each building step comprising adding at least one building element to the building element model; the device comprises:
-means for determining, on the basis of a digital representation of said building element model, at least one sequence of decomposition steps for at least partially decomposing said building element model into a number of building elements, each decomposition step comprising removing at least one building element from said building element model;
-means for determining at least one assembly step in the sequence of assembly steps based on at least one step of the plurality of disassembly steps;
wherein determining the sequence of decomposition steps comprises performing an iterative process, wherein an iteration of the iterative process comprises:
-obtaining a previous part model resulting from a previous iteration;
-determining at least one building element to be separated from a previous part model resulting in a new part model,
wherein determining at least one building element to be separated from a previous portion of the model comprises:
-determining a set of candidate sub-assemblies of the previous part model, each candidate sub-assembly comprising a respective interconnected building element of the previous part model; wherein determining the set of candidate sub-components comprises selecting the candidate sub-components according to a second set of selection criteria; and wherein at least one of the second set of selection criteria comprises determining a connection strength of one or more candidate sub-components to the previous portion of the model;
-selecting a single building element, or one of the determined sets of candidate sub-components to be separated from the previous part-model resulting in the generation of a new part-model, according to a first set of predetermined selection criteria.
38. A device according to claim 37, wherein building elements are interconnectable along at least two building directions; and wherein at least one of the second set of selection criteria comprises determining one or more locations in the previous portion of the model where the orientation of the assembly changed.
39. An apparatus as claimed in any of claims 37 to 38, wherein one or more building elements comprise a connector for providing a moveable connection about at least one direction; and wherein at least one of the second set of selection criteria comprises determining one or more sub-components that are removably connected to the previous portion of the model.
40. The apparatus of any of claims 37-38, further comprising means for determining a sequence of decomposition steps for each sub-component selected for removal in one iteration of an iterative process.
41. Apparatus as claimed in any of claims 37 to 38, comprising means for representing a previous part of the model by means of a data structure representing a graph comprising nodes representing respective building elements of the previous part of the model, and edges connecting respective nodes representing connections between corresponding building elements.
42. An apparatus as claimed in claim 41, wherein an edge of the graph has an associated connection strength value representing the connection strength of connections between building elements corresponding to nodes connected by the edge.
43. A device according to claim 42, wherein each building element comprises one or more coupling elements for engagement with one or more corresponding coupling elements of another building element to provide a coupling between that building element and the other building element, each coupling element having a coupling element class associated with it, each coupling element class having a coupling strength associated with it; and wherein said means comprise means for determining said associated connection strength value corresponding to an edge of a connection between two building elements, on the basis of the number and respective class of connecting elements at least contributing to the corresponding connection.
44. Apparatus according to claim 42 or 43, wherein the process of determining said associated connection strength value comprises determining the connection strength in dependence on the number and respective class of connection elements contributing to the corresponding connection, and on the volume of two building elements.
45. The apparatus of claim 41, comprising means for performing a graph partitioning process to determine a set of candidate sub-components of a previous part model.
46. An apparatus as defined in claim 41, wherein an edge of the graph has a value representing an association of a direction of make of connections between building elements corresponding to nodes connected by the edge.
47. The apparatus of claim 41, comprising means for identifying one or more joint nodes of the graph in order to determine a set of candidate sub-components of a previous part model.
48. The apparatus of claim 41, comprising means for identifying one or more pairs of articulated nodes of the graph to determine a set of candidate sub-components for a previous portion of the model.
49. A device according to claim 41, wherein one or more building elements comprise a coupling element for providing a movable connection around at least one direction; and wherein at least one of the nodes and edges of the graph has an associated value indicating the existence of a moveable connection.
50. Apparatus as claimed in any of claims 37 to 38, wherein determining at least one building element to be separated from a previous part model resulting in a new part model comprises calculating one or more weighting functions for at least one of a subset of building elements and a set of candidate sub-assemblies of building elements; and selecting one of the individual building elements and sub-assemblies based on a comparison of the calculated weighting functions.
51. The apparatus of claim 50, wherein at least one of the one or more weighting functions has a range of possible outcomes including a first sub-range representing a degree of adequacy of separation and a second sub-range representing a degree of inadequacy of separation.
52. Apparatus according to claim 51, wherein the process of selecting an individual building element or sub-assembly based on a comparison of the calculated weighting functions comprises calculating a total weight from one or more calculated weighting functions; wherein the process of calculating the overall weight comprises assigning a value in a second range to the overall weight if at least one of the calculated weighting functions has a result in the second range.
53. A device according to claim 50, wherein each building element comprises one or more coupling elements for engagement with one or more corresponding coupling elements of another building element; wherein each connecting element defines a direction of separation along which a building element is separable from another building element; and wherein the process of calculating a first of the one or more weighting functions of a building element or sub-assembly comprises determining whether the respective directions of separation of all connectors of a building element or sub-assembly connected to one or more other building elements of a previous part of the model are parallel to each other.
54. A device according to claim 53, wherein the process of calculating a first weighting function for a building element or sub-assembly further comprises determining a minimum distance in the direction of separation between the building element or sub-assembly and any other building element or sub-assembly of the previous part of the model.
55. A device according to claim 53, wherein the process of calculating a first weighting function for a building element or sub-assembly comprises
-determining an extended geometry of a building element or sub-assembly, wherein said extended geometry extends in a separating direction, and
-determining whether the stretched geometry intersects any other building element or sub-assembly of the previous part model.
56. An apparatus according to claim 50, wherein calculating a second one of the one or more weighting functions for a building element or sub-assembly further comprises determining whether the building element or sub-assembly is an articulating building element or sub-assembly.
57. An apparatus according to claim 50, wherein calculating a third one of the one or more weighting functions for a building element or sub-assembly further comprises determining whether the building element or sub-assembly is part of an articulated pair of building elements or sub-assemblies.
58. An apparatus according to claim 50, wherein a fourth weighting function of the one or more weighting functions of a building element or sub-assembly is a function that decreases with the number of other building elements to which the building element or sub-assembly is connected.
59. An apparatus according to claim 50, wherein a fifth weighting function of the one or more weighting functions is a function of a connection strength of connections between building elements of a sub-assembly.
60. An apparatus according to claim 59, wherein the process of calculating the fifth weighting function comprises determining the weakest connection strength between interconnected building elements of the sub-assembly, and wherein the fifth weighting function is a decreasing function of the determined weakest connection strength.
61. An apparatus as claimed in claim 50, wherein a sixth weighting function of the one or more weighting functions is a function of the connection strength of connections of a building element of a sub-assembly to other building elements of a previous part model.
62. Apparatus according to claim 61, wherein the process of calculating said sixth weighting function comprises determining the strongest connection strength between a building element of a sub-assembly and one or more other building elements of a previous part of the model not included in said sub-assembly, and wherein said sixth weighting function is a decreasing function of said determined strongest connection strength.
63. An apparatus as claimed in claim 50, wherein a seventh weighting function of the one or more weighting functions of a building element or sub-assembly is a function of a position coordinate of the building element or sub-assembly along a predetermined direction relative to a coordinate system.
64. An apparatus according to claim 50, wherein an eighth weighting function of the one or more weighting functions of building elements and sub-assemblies is a function of at least an attribute of a building element and sub-assembly and an attribute of a building element or sub-assembly that was separated in a previous iteration of the iterative process.
65. An apparatus as claimed in claim 64, wherein the eighth weighting function is a function of the distance between a building element or sub-assembly and a building element or sub-assembly separated in a previous iteration of the iterative process.
66. An apparatus as claimed in claim 64 or 65, wherein the eighth weighting function is a function representing at least a predetermined measure of similarity of a predetermined spatial relationship between a building element or sub-assembly and a building element or sub-assembly separated in a previous iteration of the iterative process, and a comparison of one or more attributes associated with a building element or sub-assembly and a building element or sub-assembly separated in a previous iteration of the iterative process.
67. An apparatus for generating building instructions for a building element model, the building element model comprising a plurality of building elements, the building instructions representing a sequence of building steps in which the building element model is to be built, each building step comprising adding at least one building element to the building element model; the apparatus comprises means for performing an iterative process, wherein an iteration of the iterative process comprises:
obtaining a sequence of assembly steps resulting from a previous iteration, the sequence of assembly steps resulting in a first partial model;
determining a subsequent assembly step in the sequence of assembly steps based on at least one of the plurality of disassembly steps by performing the steps of:
-determining a candidate building step representing the joining of at least one subsequent building element to the first part model, resulting in a second part model;
-determining, from a digital representation of said building element model, at least one sequence of decomposition steps for at least partially decomposing said building element model into a number of building elements, each decomposition step comprising removing at least one building element from said building element model in order to determine whether a building element model can be decomposed by a sequence of decomposition steps for decomposing a building element model resulting in a second partial model;
-if it is determined that the building element model can be decomposed by a sequence of decomposition steps for decomposing the building element model resulting in a second partial model, appending the determined candidate construction steps as subsequent construction steps to the obtained sequence of construction steps.
68. A device according to claim 67, wherein the building elements are interconnected.
69. A device according to claim 37 or 67, wherein the digital representation comprises respective position coordinates of each building element relative to a predetermined coordinate system.
70. Apparatus as claimed in claim 37 or 67, further comprising means for generating said digital representation of a virtual building element model by a computer-implemented assembly environment for interactively assembling said building element model.
71. Apparatus according to claim 37 or 67, comprising means for generating a corresponding sequence of partial models comprising an initial partial model, a sequence of incremental partial models, and a sequence of graphical representations of a complete model; wherein each incremental part model comprises all building elements of the immediately preceding incremental part model of the sequence, and a predetermined number of additional building elements from the plurality of building elements, wherein the additional building elements are determined by the determined sequence of building steps.
72. The apparatus of claim 71, further comprising means for providing a user interface facilitating user-controlled processing of the generated graphical representation.
Applications Claiming Priority (3)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
US11/724,915 US7979251B2 (en) | 2007-03-16 | 2007-03-16 | Automatic generation of building instructions for building element models |
US11/724,915 | 2007-03-16 | ||
PCT/EP2008/053124 WO2008113768A1 (en) | 2007-03-16 | 2008-03-14 | Automatic generation of building instructions for building element models |
Publications (2)
Publication Number | Publication Date |
---|---|
HK1138092A1 HK1138092A1 (en) | 2010-08-13 |
HK1138092B true HK1138092B (en) | 2017-04-28 |
Family
ID=
Similar Documents
Publication | Publication Date | Title |
---|---|---|
EP2135222B1 (en) | Automatic generation of building instructions for building element models | |
US8374829B2 (en) | Automatic generation of building instructions for building element models | |
Coros et al. | Computational design of mechanical characters | |
Aouad et al. | Computer aided design guide for architecture, engineering and construction | |
Mehta et al. | An end-to-end system for designing mechanical structures for print-and-fold robots | |
Zhang et al. | Functionality-aware retargeting of mechanisms to 3D shapes | |
WO2017193013A1 (en) | Determining manufacturable models | |
Hemberg et al. | Genr8: Architects’ experience with an emergent design tool | |
Merrill et al. | Echidna: Mixed-domain computational implementation via decision trees | |
Aghaei Meibodi | Generative design exploration: Computation and material practice | |
US7088377B2 (en) | System and method for designing, synthesizing and analyzing computer generated mechanisms | |
HK1138092B (en) | Automatic generation of building instructions for building element models | |
Choi et al. | Virtual prototyping for rapid product development | |
Zhu et al. | Cartonist: Automatic Synthesis and Interactive Exploration of Nonstandard Carton Design | |
Hemberg et al. | Exploring generative growth and evolutionary computation for architectural design | |
Muntoni et al. | Split and Mill: User Assisted Height-field Block Decomposition for Fabrication. | |
Merrill | Hungry for Fully Automated Design of Embedded Systems? | |
Watson | Generative Design Of Light-weight Structural Systems | |
Pitzalis et al. | Working with Volumetric Meshes in a Game Engine: a Unity Prototype. | |
Mueller | Automated motion planning for robotic assembly of discrete architectural structures | |
Chattoraj et al. | A Cross-domain, Computational Robot Design Flow from Morphology to Fabrication | |
Svetel et al. | Digital and Architecture: Still Not a Perfect Match | |
da Fonseca | Algorithmic Design for Customizable Products with Additive Manufacturing | |
Arpak | Physical and virtual: transformation of the architectural model | |
Cheng | Interactive design process based on augmented intelligence: a framework and toolkit for designers to interact and collaborate with AI algorithms |