Breeding new designs

The use of morphing algorithms in design computation

Dipl. Des. Ole Werner

Department of Product-Design, University of Kassel , Germany.

e-mail: Ole_werner@web.de

Abstract

This paper proposes new ways of using morphing algorithms in design computation. The use of morphing algorithms in design processes is not really new however the intention they are used today. If the method so far was exclusively used in the fields of optimization and engineering design, it has the potential to gain new meanings as a generative form-giving tool.

Morphing is the transformation of a form by the effect of forces. These forces can be naturally arising or freely invented forces. Morphing based optimization procedures usually use naturally arising forces such as air resistance.

The approach described with this paper examines the form manipulation on the basis of invented forces, represented by the geometries of goal forms. The use of goal forms allows the intuitive manipulation of product-designs without sophisticated mathematical knowledge and therefore may attract attention to a large group of designers.

Introduction

Discussing the use of morphing algorithms, probably everyone remembers Michael Jackson's music video "Black and White" directed by John Landis in 1991. Different faces are transformed continuously into others. Nowadays these effects are everyday business in the fields of visual media.

While the mentioned music video only transforms two-dimensional picture sequences, morphing became a standard operation in 3D Animation today. The geometry of a character in position A is transferred into a geometry of the same character in position B. The computer calculates the intermediate positions and creates a smooth movement. In animation morphing is the continuous transformation of a given starting geometry into a given goal geometry. Morphing designates the way between two conditions and thereby describes no end of intermediate conditions.

However computer applications permit not only the change into given goal forms, but allow transformations on the basis of physical rules and regularities today. The animation of clothes or water is a well-known example. The appearance of fabric or water corresponds to naturally arising forces like gravity or wind. The necessary models and algorithms were invented by engineering sciences [1]. The best known example is done research on the construction of bridges. The simulation of naturally arising forces determines the construction of airplanes and ships as well. The shape of an airplane depends on the airflow, it depends on the interaction of internal and external forces [2].

While the effect of these forces had to be examined with the help of complex and time-consuming models in the past, nowadays they can be computed on the base of procedures like Computational Fluid Dynamics and Finite Elements Method. The output of these models is the result of a morphologic evaluation focusing on optimization. However to compute constructions like bridges or airplanes, the functional requirements need to be defined by mathematical expressions. The need of sophisticated mathematical knowledge may be one reason why this method was exclusively used in the fields of optimization and engineering design so far (Figure 01).

Figure 01: A supersonic aircraft is optimized for the subsonic region, A. van de Velden [3]

If we try to give a general definition at this point, morphing is the transformation of a form by the effect of forces. These forces can be naturally arising or freely invented forces. Morphing based optimization procedures usually use naturally arising while morphing based animation uses both, naturally arising and freely invented forces.

The use of morphing algorithms as a generative tools

As described above, the use of morphing algorithms to optimize various constructions seems to be a common method in the fields of design. But what is going to happen if one shifts the origin intention to gain variety of forms instead of reducing variety to an optimum? What is going to happen if one excludes the optimization for the time and uses morphing algorithms in the way they are used for animations?

The form of a design A is going to be transformed into the form of a design B. Thereby the computer calculates the intermediate geometries and creates a film sequence, which can be stopped at any point. If one stops this sequence before reaching the end, if the dynamic process of the transformation is frozen before reaching the goal form, one receives a design C showing characteristics of design A and design B.

Regarding the biology one can describe this procedure as a generative process: form C is the result of interbreeding shape A with shape B. But C is just one out of infinitely many solutions. Similarities between this process and breeding animals or plants are obvious: Breeding is the goal-directed evolution within one species and creates variations of already existing species. The advantage of this analogy is in fact that one neither need to know how the characteristics of an individual are represented, nor how they pass on. When humans began to domesticate animals and to cultivate plants, they could only observe the results of interbreeding procedures. Only many years later the first theories of genetics arose.

Nevertheless it is briefly to be dealt with the black box of morphing algorithms: Mesh morphing, meaning the continuous transformation of a three-dimensional starting geometry into a three-dimensional goal geometry, is described as a two-stage process. It is differentiated between preprocessing and interpolation. During the first step, the correspondence between the geometries needs to be determined. Therefore they get divided into corresponding surfaces and transferred into the same virtual space. The intermediate geometries get computed during the interpolation. This sounds simple at first, but if one is looking at today's applications most implemented morphing or blending procedures do not obtain acceptable results in all cases (Figure 02). A good morph should be received as a natural and smooth change, the corresponding elements of the starting and target object should turn into each other (nose to nose, ear to ear etc.) and if possible no artifacts or recognizable errors should occur.

Figure 02: Continuous transformation between a cube and a spere (Maya)

According to the two main processes, preprocessing and interpolation, there can be defined two central problems of mesh morphing. The correspondence problem, which point of the starting-geometry corresponds to which point of the target-geometry, and the vertex path problem (interpolation problem), on which way does the point reach its destination.

The actual solutions to solve the correspondence problem can be divided into two groups: The first relies on dismantling the geometries into corresponding and parametrizised surfaces by the user. It allows control of the correspondence information, however it is connected with substantial work and can only badly be supported by the computer. The second solution suggests an automated dismantling and parametrizing of the geometries. But this gives little control to the user and succeeded so far only for certain model classes. Intensive research at the GRIS (Institute for Graphic Interactive Systems) of the technical University Darmstadt is accomplished to improve this second solution. The goal of the research is to expand the automated correspondence identification to a large class of geometries and to improve the users control [4].

The second large challenge is the interpolation. The frequently used naive-linear interpolation may cause intersections and deformations of the geometries. These problems can be avoided by interpolating lengths and angles instead of points [5] or by introducing an additional skeleton [6].

Although the central problems of mesh morphing are solved, yet, a practically working system is not available [7].

Breeding coffee- and teapots

If one remains with the metaphor breeding, the first step is to select a species. In this case coffee- and teapots were selected. Above all this has practical reasons. Only rotated geometries were selected, since their two-dimensional description contains all information necessary to transfer them into the three-dimensional space. There is no difference whether the coffee- and teapots are morphed in two or three-dimensional space. Thus the problem of missing algorithms to morph three-dimensional geometries can be by-passed.

After this, suitable breeding-pots need to be selected in a second step. The Internet offers a huge stock of images that can be used as gene pool. With the help of the search engine Google the Internet is scanned for images referring to the search words "coffee-pot" and "teapot" in order to meet a preselection. This preselection is reduced to thirty images due to further criteria such as symmetry of the body, distinction or quality of the picture. In a third step the selected images need to be converted into vector geometries (outlines). Thereby potential interference factors (background, unequal resolution etc.) can be avoided (Figure 03).

Figure 03 / 04: Transformation into vector geometries / Morhing of complete pots

In the first series of experiments each of the 30 input-geometries is morphed with the 29 remaining. With every morphing process 20 intermediate geometries are computed. Thus altogether 8,700 new geometries or descendants result (Figure 05). In order to create a second and third generation these new geometries become input-geometries themselves in the next series. That means, a selection of the descendants (first / second generation) becomes parents of the second / third generation.

Figure 05: Selected examples, first series of experiments

Briefly regarded, all resulting bodies appear as suitable new coffeepots. In its appearance some of them are quite close to the original objects, while others do surprise. The following can be held: The more strongly the topologies of the input-geometries deviate from each other, the more frequently surprising results arise. And the more closely the topologies correspond with each other, the easier the results can be predicted. Facts that do not surprise particularly, if one consider the basic principles of morphing algorithms. Nevertheless surprising observation can be made. Some resulting shapes are quite close to well-known coffee or teapots, although these have not been part of the morphing process.

The results of the first two series of experiments refer to a special problem: Because every input-geometry is limited on its body outline, most results can hardly be identified as coffee or teapots. Typical characteristics are missing. The results rather suggest associations to vases or urns. For this reason a selection of complete pots (including handle and spout) is morphed in the next series (Figure 04). This series examines the validity of the principle and thus the validity of the two preceding series of experiments.

The solution space of morphing operations

The morphing operation requires at least two input-geometries. They mark the starting point and end of a linear transformation process. Thus in this case the solution space can be described as a straight line, limited by two input geometries. All descendants of this morphing process, as well as all descendants of the subsequent generations, are positioned on the same straight line. In morphing processes this straight line is usually described as time axis. The starting geometry always obtains the value 0 and the goal form always the value 1.

Figure 06: Solution space of morphing operations based on three input-geometries

According to the number of intermediate stages this time axis is then partitioned equally. If a morphing operation creates two intermediate geometries, the axle is divided into three parts. The first intermediate geometry is described by position 1/3 and second by position 2/3. According to this 10 intermediate geometries are described by the positions 1/11, 2/11, 3/11,4/11 etc.

The solution space of morphing operations based on three input-geometries can be described as a triangular area. Straight lines between the three geometries define the two dimensional area. In order to check the validity of this model the second and third generation were examined. Within the triangular solution space morphing operations can be described with the help of straight lines. These lines are running crosswise and intersect at certain points but every intersection describes only one geometry. In order by-pass peculiarities or inaccuracies, caused by the morphing algorithm, only basic geometries were used in this experiment (Figure 06).

According to the preceding examples the solution space, limited by four geometries, can be described as a three dimensional area. And like before, at every intersection only one geometry is described.

Morphing processes can be controlled with the algorithm and the input-geometries. If one takes the algorithm as given and unchangeable only the geometries remain as variable parameters of the process. They become variable parameters of the solution space and each corresponds to one dimension. Therefore the model of the solution space depends on the number of dimensions. According to this, the solution space of the first series of experiments contains 29 dimensions. One out of 30 input geometries becomes the starting-geometry, which can be manipulated with the help of the 29 remaining geometries (parameters). The solution space of morphing operations can be described as n-dimensional space, whereby n is corresponding to the number of variable parameters.

Evaluation of the solution space

The construction of a solution space does not only include increasing variety but also reducing variety. A solution space can be extended or limited by:

1) Adding and excluding input-geometries.

2) Restrictions of the morphing operation (e.g. permitted number of intermediate geometries or the restriction on a defined range of the transformation axle (time axis)).

3) The use of computer-aided procedures to evaluate resulting geometries according to defined criteria. Geometries that do not fullfill the requirements can either be excluded or modified. All criteria used for automated evaluation must be computable (volume, price, weight, technical negotiability).

Figure 07 / 08: Simulated morpging operation (I-DEAS) / Automated evaluation procedure

To compute defined criteria, the morphing process needs to be transferred into computer-aided-design applications. Because the chosen application I-DEAS does not offer morphing operations, they have to be simulated by using the loft operation. The loft operation creates a three-dimensional solid on the basis of two cross sections (outlines of coffee-pots). The two cross sections are transferred into one another by a constant transformation similar to the morphing operation. New cross sections can be extracted and rotated from this solid (Figure 07). The solids, created in this procedure, can be used for computer-aided evaluation. Defined criteria can be misalignment of weight when pouring out, distance between the centre of gravity and handle necessary angle for emptying the pot (Figure 08) or size of the surface in proportion to volume.

Figure 09: Physical models of morphed nature forms

But even if all used geometries of coffee- and teapots are based on physically existing cans, the additional evaluation of physical models (scale 1:1) can be very helpfull. Physical models supply information, which cannot be computed. Surely one can try to evaluate proportions on the basis of computer representations, but with high probability the evaluation of physical models will come to different results. Experiences, gained thereby, can be formalized again and then be implemented into an automated system.

Increasing variety

In the preceding series of experiments the different geometries were always morphed with geometries of the same species, coffee- and teapots with coffee- and teapots. The solution space convinces by the large portion of suitable solutions (without consideration of aesthetic preferences). But at the same time these solutions offer only little surprises or innovations. The borders, determined by the preselection of geometries of only one species, seem to be quite close.

The following two series of experiments shift these borders and expand the solution space by supplementing by new geometries of different species. This is a big advantage of breeding designs on the computer. One is not limited to interbreed within one species, like breeders normally are. Using morphing algorithms one can interbreed every species with every different one.

The first series is using the outlines of the preselected pots, like before and additionally new outlines of glasses, posts and table legs. In the next series the outlines of coffee- and teapots are excluded. Instead of using already designed input-geometries this experiment is based on grown nature forms like leafs, blooms and branches. They are reduced to their outline and rotated along their center axle (Figure 9 / 10).

Figure 10: Selected examples, series of experiments using nature forms

The results can be summarized quite briefly. The less the input-geometries are predetermined by meanings, the more freely the results can be interpreted. In particular the morphs of nature forms offer space for free associations like vase, candle stand, streetlights or wine glasses (Figure 10). This space is only limited by the dominance of the rotation-symmetry. Thus morphing algorithms can also be used as initial-tools during early stages of the design process.

References

[1-2] Böhm, Florian: Evolutionäres Entwerfen? - Florian Böhm im Gespräch mit Sabine Kraft und Schirin Taraz-Beinholt. In: ARCH +, Zeitschrift für Architektur und Städtebau,

Ausgabe 159/60, ARCH + Verlag GmbH, Aachen 05/2002, S. 128-133

[3] ARCH +, Zeitschrift für Architektur und Städtebau, Ausgabe 159/60, ARCH + Verlag GmbH, Aachen 05/2002, S. 128 –133

[4] Alexa, Marc: Morphing von Polyedermodellen, GRIS / GDV Jahresbericht 1999, Technische Universität Darmstadt 1999

[5] Sederberg, T.W.: 2-D shape blending: an intrinsic solution to the vertex path problem Computer Graphics 27, 1993, S. 15-18

[6] Shapira, M.; Rappoport, A.; Shape blending using the starskeleton representation. IEEE CG&A, 1993, S. 44-51

[7] Alexa, Marc: Mesh Morphing - State of The Art Report. Eurographics Association 2001