0010-4485/$ – see front matter © 2010 Elsevier Ltd。 All rights reserved。 doi:10。1016/j。cad。2009。12。003 driven

Fig。 3。   Four bar mechanism and graph of spaces。

Fig。 1。    Folding of an origami tray carton。

Fig。 2。   Tray carton and associated face graph。

sections。 A second example of a skillet carton is given in Section 4。 Section 5 investigates whether the approach can be extended to more complex folding situations and looks at an example taken from origami。 In particular this highlights the large angu- lar changes that may be induced in some gusset folds by relatively small changes in the positions of neighbours。 This means that care is required to ensure that constraint resolution finds the appropri- ate angular positions。

2。Graphs

Consider the tray carton [4] shown in Fig。 1。 The figure gives var- ious stages during the erection process。 The original net is shown in Fig。 2。 It has fifteen face panels in total。 These are numbered with the panel for the base being numbered zero。 This can be regarded as being fixed with the other faces being moved relative to it。 It is likely that a mechanism or machine used to erect the tray acts prin- cipally on the main side walls。 So panels 1, 4, 7 and 10 are turned through 90◦ and panels 13 and 14 are each turned through 180◦ relative to panels 4 and 10。

In the corners of  the  tray  are  four  ‘‘gusset’’  arrangements。 An example comprises the panels 2 and 3。 These need to move inwards, as seen in Fig。 1, and they are finally captured and held inside the short double-wall end as panel 13 is folded over。 The gussets do not require to be pushed explicitly; they move naturally as the main panels to which they are attached move。 However, they may need to be guided during the initial stages of their motion to ensure they move inwards and not   outwards。

Also shown in Fig。 2 is the face graph of the carton [23]。 The nodes of this graph correspond to the panels of the carton, and two nodes are joined if, in the carton net, the two faces have a common edge。 (If the face net is itself regarded as a planar graph, then the face graph is essentially the dual graph。)

Similar graphs are used to represent the interconnection of the links of mechanisms or robots [26], and they have also been used to describe the hierarchy of ‘‘model spaces’’ used to represent such systems [27]。 A model space is a collection of geometric entities described with respect to a local coordinate system。 It also has associated with it a transform which maps from the local space to another coordinate system。 That second system can either be world space or another model space。 A hierarchy is created in which the nodes are the spaces themselves and the edges can be regarded as the transforms mapping between these。 The hierarchy forms a tree in which the root node is world space。 To find how any other space relates to the world it is necessary to map it by each of the transforms along edges between it and world space。 As the hierarchy is a tree, this sequence of transforms is unique。

If each of the transform is specified, then the positions of each of the model spaces is determined。 So, for example, with a conventional robot, if each of the joint angles is known, then the position of the end-effector is established。 However, in practice, one needs to take the end-effector to a given point。 This effectively creates a new edge joining the end-effector directly to world space。 This in turn creates a loop in the hierarchy and it is no longer a tree。 Once there are loops, determining the transforms is more difficult as there is likely to be conflict depending on which way one passes around the loops。

An example is shown in Fig。 3 which shows the three moving links of a four bar mechanism。 The coupler and driven links are not joined。 The corresponding hierarchy is also shown in the figure。 Joining the two links creates an additional edge (shown as a dashed line) and a loop is formed。 One way to establish the assembly is to consider the angles of the coupler and driven links as being free。 Two such links form a ‘‘dyad’’。 Forming the expressions for the ends of the links and setting them equal leads to two simultaneous non- linear equations for the angles。 These can be solved numerically by a variety of techniques。