Computer-Generated Floral Ornament Michael T. Wong Douglas E. Zongker David H. Salesin University of Washington Abstract This paper describes some of the principles of traditional floral ornamental design, and explores ways in which these designs can be created algorithmically. It introduces the idea of “adaptive clip art,” which encapsulates the rules for creating a specific ornamental pattern. Adaptive clip art can be used to generate patterns that are tailored to fit a particularly shaped region of the plane. If the region is resized or reshaped, the ornament can be automatically regenerated to fill this new area in an appropriate way. Our ornamental patterns are created in two steps: first, the geometry of the pattern is generated as a set of two-dimensional curves and filled boundaries; second, this geometry is rendered in any number of styles. We demonstrate our approach with a variety of floral ornamental designs. CR Categories: I.3.3 [Computer Graphics]: Picture/Image Generation; I.3.4 [Computer Graphics]: Graphics Utilities— Picture description languages. Additional Keywords: adaptive clip art, conventionalization, pattern generation, plant development, ornamentation, texture generation 1 Introduction If I were asked to say what is at once the most important production of Art and the thing most to be longed for, I should answer, A beautiful House; and if I were further asked to name the production next in importance and the thing next to be longed for, I should answer, A beautiful Book. To enjoy good houses and good books in self-respect and decent comfort, seems to me to be the pleasurable end towards which all societies of human beings ought now to struggle. — William Morris, 1892 [23] Ornament is among the oldest forms of human expression, already well developed by the Neolithic Age [6]. Nearly all the commissioned writing of the Middle Ages was decorated with ornament, and the illuminated manuscripts of the 13th century rank among the most beautiful books ever produced. Even the earliest printed books were often illuminated by hand, but by about 1530 such carefully crafted illumination had all but disappeared [23]. Today, documents are produced with greater ease and in greater number than ever, thanks to ubiquitous desktop publishing tools—yet, beyond the use of static “clip art” elements, these tools provide precious little support for ornamenting the page. Similarly, in architecture, ornament has historically played a critical and famous role. However, most modern buildings, despite the help of sophisticated CAD tools, are largely devoid of these beautiful decorations. Though technological advances have virtually ignored the creation of ornament, they have at the same time provided new opportunities for its use. The dynamic nature of Web documents encourages ornament to be generated on the fly to accommodate different browser configurations and fonts. New printing processes make it feasible to print on fabric or wallpaper in small runs, raising the possibility of their custom design and production. This paper therefore provides an early exploration into how aesthetically pleasing ornaments might be generated algorithmically. The method we describe attempts to capture the “essence” of an ornamental pattern, encoding it as a set of rules, which we call adaptive clip art. This encoding allows the ornament to be defined in a manner that is independent of a specific areal boundary. The adaptive clip art so described can be used to generate ornaments that are automatically tailored to any particular re- Figure 1 Design element categories. (a) Geometric forms (after Alhambra tile) [29, plate 29]. Natural forms (b) plants (Gothic vine) [10, fig. 82], (c) animal/human forms (border detail, Germany 1518) [4, plate 30], (d) physiographic forms (17th century Japanese wave motif) [9], (e) artificial objects (Renaissance torches) [21, plate 80]. gion of interest; moreover, if the region is changed, the ornament can be regenerated to fill the new area in an appropriate way. The automatic creation of aesthetically pleasing ornament is a monumental challenge, which we by no means claim to solve here. Nevertheless, we hope that this paper will offer some interesting new directions, with the hope that further advances may someday help in the creation of beautiful ornaments for our houses and books—and online chat rooms and web pages! 1.1 Problem statement The problem space of all possible ornamental design is simply enormous. In order to approach the problem at all, we need to limit our domain. We therefore make the following taxonomy (adapted from Meyer [21]). First, the elements of ornamental design can be broken down into three broad categories: 1. geometrical elements, such as lines, polygons, ovals, and the like (Figure 1a); 2. natural forms, which can be further classified as 1. plants (Figure 1b), 2. animal/human forms (Figure 1c), 3. physiographic features (Figure 1d); and 3. artificial objects, such as shields, ribbons, or torches (Figure 1e). Second, for our purposes we will similarly divide the applications of ornament into four main contexts: A. to bands, which have finite thickness in one dimension and are infinitely repeating in the other (Figure 2a); B. to half-open borders, which are tightly constrained along one or more edges, but open in other directions (Figure 2b); C. to panels, which are arbitrary bounded regions of the plane (Figure 2c); and D. to the open plane, in which the ornament typically becomes a repeating pattern (Figure 2d). In this paper, we restrict the problem space to the case of producing floral growth within panels (case 2.1-C in the classification above). In particular, we will look at the challenging issues of structuring floral ornament according to various principles of ornamental design, such as balance, analogy, and intention—as described in Section 2. We will not, however, focus here on designs involving strict symmetries. As we shall see, the resulting design space is still quite large; however, it is at least constrained enough that we can explore a series of related approaches within the confines of a single research paper. Moreover, we expect that many of the approaches suggested here will be useful, in some form, for other cases in the taxonomy. In the rest of this paper, we describe a number of principles of floral ornamental design, and we discuss ways in which such designs can be created algorithmically. Figure 2 Applications of ornament: (a) bands (16th century Germany) [31, plate 34] (b) half-open borders [24, opening page of chapter 7], (c) panels (oak leaf vine from the cathedral of Toledo) [10, fig. 104], (d) open plane [35, fig. 270]. 1.2 Related work The area of ornamental design synthesis has received relatively little attention in the computer graphics community, to our knowledge. At SIGGRAPH ’75 (the 2nd annual SIGGRAPH conference), Alexander described a Fortran program for generating the 17 symmetry patterns in the plane [1]. Gr¨unbaum and Shephard used a more sophisticated computer program to generate periodic tilings and patterns in their landmark text on the subject [14]. However, in both of these cases, the ornamental designs produced are purely geometric and purely on the open plane. Glassner examined the synthesis of frieze patterns, which can be used for generating textures for band ornaments [11]. Siromoney and Siromoney examined the synthesis of kolam patterns: a form of ephemeral ornament practiced in India where grains of rice are used to trace out designs forming intricate lattices [32]. Their goal, however, was to show how graph grammars could be used to generate instances of such geometric patterns, rather than to create ornament to fill a specified region. Arvo and Kirk introduced the modeling of plant growth with environmentally sensitive automata [2], Greene examined the growth of plant-like branching structures in voxel space [13], and Prusinkiewicz et al. examined the generation of ornamental topiary plant forms with open L-systems [26]. The synthetic structures described in these papers were adaptive to space, but not designed to grow according to conventions of 2D ornamentation. Smith introduced the graphics community to the modeling of plant growth with a class of parallel rewriting grammars he termed “graftals” [33]. The grammars were used to generate a branching structure, which could then be given visual character through a postprocessing step. We use a similar two-step procedure to create first the structure and then the rendering of our ornaments. In their paper on graphical style sheets, Beach and Stone introduced the idea of procedurally generating a simple repeating border pattern that is warped to follow the path of a spline [3]. This idea was subsequently elaborated by Hsu and Lee, in their papers on “skeletal strokes,” to the warping of predefined vector clip art along a path [15, 16]. Skeletal strokes—whose commercial implementation, MetaCreations Expression, we have used to render many of the illustrations in this paper—may be thought of as a rudimentary form of adaptive clip art along curvilinear paths. The work described in this paper builds on their approach by creating a higher-level mechanism for the automatic arrangement of skeletal strokes within arbitrary regions of the plane. 1.3 Overview The rest of this paper is organized as follows. Section 2 surveys the key principles of floral ornamental design. Section 3 discusses how these principles can be encapsulated algorithmically. Section 4 discusses the framework of our ornamental growth engine. Section 5 presents some of our results, and Section 6 suggests areas for future research. Finally, Appendix A shows in detail some simple examples of using our system. 2 Principles of ornamental design For our purposes, we will define ornament as the aesthetic enrichment of the surfaces of man-made objects in ways not directly contributing to their functional utility. In order to provide a sense of the richness and depth of the problems involved in creating ornament, we will briefly describe some of the principles that underlay its design. The system we have implemented so far addresses only a fraction of these principles. Let’s first look at some of the methods ornamentalists use in conveying a perception of order. We will then explore the particulars of floral ornamental design. 2.1 Order in ornament If there is any one underlying principle of ornament, it is the conveyance of a sense of order or design [12]. Ornamentalists use three principal techniques in conveying a perception of order: repetition, balance, and conformation to geometric constraints [10, 12, 36]. 2.1.1 Repetition Perhaps the most fundamental ordering principle is repetition. The repetition of even the simplest mark can form the basis of an ornament. When forms are repeated, they may be repeated exactly through translation and rotation (Figure 3a). Or they may be reflected about some axis, yielding bilateral symmetry (Figure 3c) or glide reflection (Figure 3b). In many patterns containing rotational symmetries, the point of radiation is positioned off-center from the design elements it controls, leading to a bilaterally symmetric radiation (Figure 3d). A more subtle form of repetition is the use of analogy, in which similar, rhythmic controlling lines are used to place and constrain different floral or figurative elements (Figure 3e). In addition, the recurrence of almost any ratio, or proportion, in a design can impart a pleasing unity of form. Color is another powerful attribute of patterns, orthogonal to shape, that can be used to unify a design through repetition. While designs based on rigid repetition may appeal to a clean, austere aesthetic, other patterns use variation within a class of forms to add organic dynamism to their composition (Figure 3h). This variation may be achieved through alternation of color or form (Figure 3f), or through scaled repetition (Figure 3g). 2.1.2 Balance The principle of balance requires that asymmetrical visual masses be made of equal weight. Figure 4a shows this principle applied to several compositions. We can also speak of balance in the implicit motion of lines. Crane [8] describes this phenomenon as each new Figure 3 Repetition: (a) simple translation [4, plate 142], (b) glide reflection [10, plate 14], (c) reflection [36, cover illustration], (d) radiation (late Gothic “pine” ornament) [10], (e) analogous (rhythmic lines in the frieze of the Parthenon) [8], (f) alternation [34, plate 78], (g) scaled [9], (h) organic variation [34, plate 27]. line posing a question that requires an answering line (Figure 4b). We can see both these principles at work in Figure 4c. The principle of balanced masses, combined with the primal motivation for ornamentation, horror vacui, yields the principle of uniform density: ornament should uniformly fill its allotted space. In some ornaments, elements of similar mass are distributed non-uniformly in space. In this case, their unequal distribution can be balanced with different elements of a smaller scale. This type of ordering leads to a balance within and among levels of hierarchies of visual mass (Figure 4d). 2.1.3 Conformation to geometric constraints Since ornament must live within the boundaries of the objects it seeks to enrich, the design process must generally begin with a consideration of geometric constraints. First and foremost, a careful fitting to boundaries is a hallmark of ornament from many cultures. Often, the period of a meandering vine, for instance, has to be adjusted not only to fit properly between the Figure 4 Balance: (a) in composition [8], (b) question and answer within lines [8], (c) combined [36, fig. 126], (d) hierarchical [5, title page]. top and bottom edges of the panel, but also to provide appropriate positions for secondary shoots to invade other portions of the ornamented region (Figure 5a). In addition, the shapes of the design elements themselves are sometimes deformed to better fill space (Figure 5b). In many vining motifs, elements are made to grow together tangentially. This principle of tangential junction lends a powerful sense of teleological, or ends-driven, design to the composition. For obvious reasons of structural integrity, tangential junction is also important for ornament that is “cut through” or must otherwise hang together, such as the open-work bronze basket in Figure 5c, and the sign support in Figure 5d. A further principle ordering the layout of motifs is placement at signal geometric points such as points of maximum concavity or convexity, as in the rosettes of Figure 5e. When filling a region that has distinct corners, a design element is almost always dedicated to the task of filling each corner. When accomplishing this task with a growth motif, the growth is often coordinated by the skeleton of the region to be filled, as demonstrated by the paisley in Figure 5f. The design of ornament frequently proceeds through the subdivision of an area followed by the filling of the divisions. Figure 5g shows the sequence of steps taken by a 19th-century textile designer from India in laying out a woodblock print. Since the act of filling may also be viewed as one of subdivision, the process may be recursively repeated, leading to a many-tiered hierarchical composition in the final design. 2.2 Floral ornament For our purposes, we will define floral ornament as any ornamental design process involving plant-like growth models, such as branching structures; or plant-like elements, such as vines, leaves, or flow- ers. In this section we will first examine the peculiar qualities of growth that distinguishes it as a progenitor of ornamental design. We will then discuss how plant-like structures can be transformed into ornamental elements through the process of conventionalization. Figure 5 Conformation to geometric constraints: (a) fitting meander period (drawn after [22, p. 35]), (b) deformation of design elements [24], (c) tangential junction (drawn after [19, p. 107]), (d) tangential junction (drawn after [12, fig. 66]), (e) signal geometric points [36, fig. 99], (f) following skeleton of a region [25], (g) hierarchical subdivision [6, fig. 213]. 2.2.1 Growth To begin with, it is worth noting that most of the ornamental principles discussed so far are already principles of growth. As Owen Jones observed in the Grammar of Ornament [17], “whenever any style of ornament commands universal admiration, it will always be found to be in concordance with the laws which regulate the distribution of form in nature.” Growth is a particularly good source for continuous patterns that fill space and that can logically transport a design into new regions. In Figure 6, design elements are transported by linear trunks and sinuous meanders. Space is filled by smaller spiral branches and half- Figure 6 Growth transporting a design [10, plate 77]. spiral leaves. In addition, the non-rigid repetition of forms derived from natural growth can be used to breathe life into a design. Another issue of growth as represented in ornament is that it tends to be more highly structured, or ordered, in this context. This ordering property can be described as intention. Intention can be defined as the aesthetic perception of teleological growth or placement of form, discernible from multiscale features of a design: its high-level layout; its sinuous sub-motifs and their serial and hierarchical compositions; and, at the lowest level, the continuous change in curvature along a line, a line’s modulation in width, and the angles of crossings of lines. In other words, intention is not just the process of growth in the absence of external influences, but rather a way of expressing growth even under such influences. Examples include growth toward pre-placed flowers, or the cooperative formation of symmetric structures, sometimes even from non-analogous locations in an overall branch structure. 2.2.2 Conventionalization While in common usage the term “convention” has a pejorative ring, implying lack of invention, in ornamental design it can have just the opposite meaning. Conventionalization in ornament is the development of abstractions of natural form, a highly creative process. When artists develop a conventionalization they perform a sort of inventive prefiltering of phenomenal reality followed by a creative resynthesis of form. The focus is to extract essential features of form from the vagaries of environmental influence. In Figure 7 we see a side-by-side comparison of a study drawn from nature and a conventional representation based on that study. Note how the subtle wave of the leaf margins of the poppy get amplified and regularized in its conventionalization. Note also how the form of the seed pods has been stylized to fill space. 3 Approach We will represent a given adaptive clip art pattern as a set of elements, which describe the geometric primitives that comprise the ornament, together with a set of growth rules, which describe how the elements are structured in relation to one another and to the boundaries of the panel. The growth rules are invoked by a controlling framework to produce the ornamental pattern, customized for any planar region. L-systems would appear to be the natural choice for expressing our growth rules, as they have been used to model many plant-like structures. In the rest of this section, therefore, we will take a closer look at the use of L-systems for ornament and discuss the reasons we ultimately chose not to use them. We will then discuss the approach Figure 7 Natural vs. conventional representation [8]. we took in encoding our adaptive clip art in more detail. 3.1 Using L-systems for ornament L-systems were developed by biologists seeking to model the development of plants, and they have been extended by the computer graphics community [27, 28, 33] to create realistic plant images and animations. Traditional L-systems do not receive information about the environment. More recently, open L-systems have been introduced to allow information from the model’s environment to also affect growth [20, 26]. Open L-systems are therefore a reasonable choice for encoding growth rules for ornament. As we discuss below, however, the generation of ornament differs from the growth of real plants in several significant ways that we felt limited the applicability of open L-systems in this context. First, while floral ornaments may involve leaves, flowers, vines, and so forth, in their conventionalization these elements are often connected and arranged in ways that no plant would ever produce. Biological models are therefore not directly applicable. Indeed, we felt it would be easier, in most cases, to model the appearance of an ornament rather than some underlying process to produce it. Also, by modeling the appearance of the output directly, we felt we could have tighter control over it. Second, the environmental feedback loop for real plant growth is indirect: the environment at a given point in space produces chemical changes in the plant that act to alter its further growth. Open L-systems model this loop by alternating “rule application” phases with “environment query” phases—productions leave symbols in the L-string to indicate where queries should be answered by the environment process. These answers can only affect productions in future iterations of the simulation. Thus, a rule for growth that incorporates environment queries must be split into a set of productions. We felt that in our case it would be easier to design rules in the form of procedures, which could both query the environment and directly act on the results of those queries in placing graphical elements of the ornament. Finally, L-systems apply all productions to a string in parallel: each element in the string is simultaneously replaced with the result of a rule acting on the element. Rather than trying to define the semantics of parallel rule application when each rule is a procedure, we have chosen to apply our rules serially. A successful iteration of our system, then, consists of the selection of a single element, followed by the incremental growth of that element according to a certain growth rule associated with it. This process also provides an opportunity to integrate some form of global planning into both the selection of the element and the rule being applied. 3.2 Adaptive clip art Adaptive clip art consists of two parts: elements and growth rules. Elements correspond to the 2D geometric primitives that appear in the ornament (e.g., flowers, leaves, and stems); they are the objects upon which the growth rules operate. To provide simplicity without sacrificing the ability to draw detail, each element is defined as a collection of one or more proxies. A proxy is a relatively simple geometric shape that represents the element (or a part of the element) for the purposes of locating empty spaces and testing for intersections. When producing final output, a more complicated rendering procedure can be invoked. The use of proxies, therefore, keeps the details of rendering an element separate from the mechanics of positioning it in the design. Our growth rules are specified as procedures. When a rule is invoked on a parent element, the code associated with that rule (the rule body) is executed. This code can perform environmental queries and create child elements, among other things. A support library is provided for common environmental queries and for conveniently manipulating geometrical primitives such as proxy shapes. Finally, our framework for elaborating adaptive clip art uses a limited form of planning in selecting the element for growth on each new iteration. As described in more detail in the next section, the framework attempts first to grow the ornament into large open space, then shifts to filling in corners of the desired region. 4 Implementation The current implementation consists of approximately 600 lines of Perl (the preprocessor) and 3,600 lines of C++ (the framework). The preprocessor reads a rule file which encodes an ornamental pattern. The preprocessor output is a C++ source file and a corresponding header file, which are compiled with the framework code to produce an executable. This executable can take a region specification and produce the ornamental pattern to fill that particular region. The output generated is a PostScript file. A default rendering is provided for every element, which simply draws each proxy of the element in outline form. The user can attach arbitrary C++ code to each element type within the rule file to generate custom PostScript output if desired. Alternatively, the PostScript output can be converted to paths and rendered with skeletal strokes [15, 16] to produce a wide variety of effects. We will take a top-down approach to describing the implementation in the next three sections, first describing the way in which elements and rules are selected for growth, then covering the details of how they are specified. 4.1 Rule invocation The main job of the framework is to decide which elements to “grow” with the rules in order to fill the given space. Let R represent the region to be filled with a pattern. Our heuristic is simple: it finds the largest circle C (modulo some approximation error) that does not intersect the boundary R or any element of the design, and tries invoking rules on the elements within a distance of that circle. Elements are tried in order of their distance from the circle. When a rule succeeds (or when all possibilities are exhausted), the iteration ends and a new circle C is selected. To find the desired circle, we keep a (relatively) low-resolution buffer into which we render the proxies of already placed elements, along with the boundary of the region R. We start small test circles at various points within the region and increase the radius of each circle until it intersects an element or the boundary. If the inflation procedure for a given circle is stopped because the circle hits a boundary, the circle is discarded, since the circle is not adjacent to the existing ornament. If inflation is stopped by hitting an element, the circle is kept. The largest kept circle is chosen as C. The center and radius of C are made available within rule bodies so that rules may direct their growth based on the circle’s location. To determine at which points to center the test circles, we perform a medial axis transformation (MAT) [30] using the Manhattan distance metric. A circle is centered on each pixel whose transform value is at least as great as those of its neighbors. We use these skele(a) (b) (c) (d) Figure 8 One iteration of the main loop. (a) Elements already in place at the start of the iteration. (b) The render buffer, with points covered by elements and/or the region boundary (in red). Eligible empty-region circles are superimposed in yellow, ineligible circles (on the exclude list) in green. (c) The selected empty circle C (dashed blue lines) and the nearby elements that are candidates for growth (thick purple lines). (d) The ornament after a rule has placed a new leaf. ton points as centers of the candidate circles to avoid having to perform the circle inflation, which is relatively slow, starting at every uncovered point in the region. The MAT is updated incrementally after each new element is placed. It is possible that all the rules on all the elements near a given circle C may fail to place new elements. In this case, C would continue to be the largest empty circle available and would immediately be tried again. To prevent the algorithm from falling into an infinite loop, we keep a list of points called the exclude list. No circle that intersects a point on the exclude list can be selected as C. If all the elements near a given circle fail to produce new elements, then the center of the circle is placed on the exclude list. A point can be removed from the exclude list in one of two ways. Whenever a rule is successful in placing elements for a circle C, all points within of that circle’s center are removed from the list. The idea is that we want to prevent a failed circle from being eligible until some change has occurred in its vicinity; then it can be tried again. The other way is for a rule body to explicitly clear the list (useful, for instance, if some state change within the rule code allows previously unavailable possibilities for placing elements). The overall algorithm can be summarized with the following pseudocode. The FindEmptyCircle procedure locates the largest empty circle in the region, subject to the two restrictions above. The effects of one iteration of the main loop are illustrated in Figure 8. initialize element tree with seed points render boundary elements into buffer compute initial MAT initialize empty exclude list repeat C FindEmptyCircle() find elements within of C try elements in order of distance from C try rules in order specified in rule file if rule succeeds, break if some rule succeeded update element tree render new elements into buffer incrementally update MAT remove points on exclude list within of C else add center of empty circle to exclude list 4.2 Elements and rules Each design element has a type. The set of available types is declared in the rule file. Each element type is associated with one or more proxies, and zero or more user fields. Available proxies include circles (circle), arcs (arc), cubic B´ezier segments (bezier), line segments (linesegment), etc. Each element contains a few standard fields (such as the number of children the element has), any user fields given in the element declaration, and proxy objects of the types specified in the declaration. The fields of each proxy are dependent on its type: a circle proxy, for instance, has center and radius fields. Each rule file must declare the element type seed, with a single point proxy. Seed elements are placed by the framework in userselected locations at the beginning of the run to start the ornament. After the element declaration section of the file is the rule section. Each rule specifies what element type the rule acts on (the parent) and what types of children the rule produces. The set of children created by the rule consists of the static children declared in the rule preamble, plus any dynamic children created within the rule. The only difference between static and dynamic children is how they are initialized and how they are referenced within the rule body. The body of the rule looks very much like a block of C++ code. Anything that is legal within a C++ function is legal within a rule body. Additionally, special dollar-sign tokens provide convenient access to the fields of the parent and child elements. The preprocessor translates these tokens into C++ expressions referring into the data structures of the elements. Each rule returns a flag to indicate success or failure. On success, the children created by the rule are permanently added to the ornament and a new iteration begins. On failure, the children elements are discarded, and the framework proceeds to try other element/rule combinations as discussed in Section 4.1. Two detailed examples of patterns implemented with this system are given in Appendix A. 5 Results Our first set of results shows four different ornamental patterns, each elaborated over two regions. The first pattern (Figure 9) is based on a pattern taken from a Chinese vase [18, plate 47]. The pattern has two types of stylized flowers laid down in a grid pattern and connected by curving stems. The remaining space is filled with small hook-shaped curves, which themselves are adorned with smaller teardrop shapes. In addition to exhibiting constraints to geometric bounds, this example was chosen to demonstrate “intentional” growth: the large vine appears to deliver its flowers to predefined locations on the grid. The second pattern (Figure 10) demonstrates the principle of hierarchical growth. The pattern starts from the seed points by growing the vines. It then adds the red flowers and the yellow and blue shapes, connecting them to the main vine structure with shorter subsidiary vines. Next, leaves are added, either attached to a vine or floating on their own, and finally the small double-quote-shaped structure is used to fill in small gaps. This ordering of rule phases is imposed on the system by adding “state” preconditions to each rule, so that any rule that is invoked when the program is not in the right state automatically fails. The third pattern (Figure 11) is a somewhat less successful attempt, motivated by a William Morris willow-leaf wallpaper. There is only one rule, which grows through the empty circle by adding a curved stem with alternating leaves while preventing the leaves from overlapping too much. This pattern illustrates a shortcoming in our approach, which is that it is difficult to do significant global planning of a design. In our current system, rule invocation is controlled by the empty-space-finding algorithm, so growth always proceeds from the nearest element. For many patterns, it would be better to fill a given space with growth from a more distant element that curves so as to naturally pass through that space. Our “willow” pattern, while covering the region well, is jumbled in comparison to the more elegant original. The fourth pattern (Figure 12) uses a motif based on an equal-angle spiral, a shape that can be seen in diverse natural forms, from the spiral of a nautilus shell to the curve of a vine tendril [7]. This same pattern is also used, with a different rendering style, to generate the border on the first page of this paper. Each spiral is composed of multiple curved segments, making heavy use of dynamic child creation, since spirals of different lengths require different numbers of segments in order to appear smooth. Each spiral curve is given an orientation opposite to that of its parent. Note how the pattern generates a rhythmic repeat with a period that is related to the changing width of the space; the pattern also simplifies as it wanders into narrower spaces. Although the rules that generate this pattern are not explicitly hierarchical, the appearance of hierarchical structuring is nonetheless formed by placing new elements in, and scaling them to, the largest empty circle adjacent to the growing ornament. The resulting ornament reveals large-scale structures placed in relation to the outline of the boundary space, with finer-scale details placed in relation to both the boundary space and the evolving ornament. Figure 13 shows each of these four patterns again, elaborated over differently-shaped panels. Figure 17 shows the breadth of rendering possibilities provided by the skeletal strokes technique [16]. The same spiral design is rendered with four different strokes, producing a variety of effects. Although the underlying spiral growth motif is more subtly felt in the more abstract renderings, its ordering properties structure the distribution and scaled repetition of design elements, creating an organic feel to the compositions. 6 Conclusion In this paper, we have described a mechanism for encapsulating growth principles for ornamental design into “adaptive clip art” pat- terns. Although we have so far implemented only a rudimentary testbed for these ideas, we envision, ultimately, a powerful interactive authoring system for designing these patterns. The artistic tool so derived—unlike most previous work in computer-generated artistic rendering—might be more than just a digital form of an existing artistic medium: it could essentially provide a new medium of artistic expression, one that yields “living,” dynamic patterns that adapt to their environments. As we gain more experience with the novel parameter space of this new medium we hope to encapsulate our knowledge in high-level, interactive tools that novices and artists alike will be able to use for creating new instances of these patterns. In addition to creating better high-level design tools, there are a huge number of other important areas for future research: Ornaments over manifolds. We would like to extend our work to creating ornaments over arbitrary manifolds. Such techniques would allow the ornamentation of 3D objects (vases, mugs, T-shirts, etc.) without the distortion that results from simply mapping a planar ornament onto the surface. Incorporating global planning strategies. Our strategy of growth towards the largest empty region is a simple, relatively local one. A more sophisticated approach might be developed to look at the design more globally and better incorporate ornamental design principles such as balance and symmetry. Putting an artist “in the loop.” In applications such as web page ornamentation, the adaptive clip art must be generated purely automatically, on the fly. However, in other applications, such as wallpaper design, there is no reason not to put an artist in front of the computer to help guide the growth of the pattern and improve its appearance artistically, since both the cost of manufacturing the resulting artwork and the longevity of the finished piece are both relatively high. It would be interesting to explore semi-automatic algorithmic design processes and user interfaces for use in these situations. Acknowledgements We would like to thank Przemyslaw Prusinkiewicz, Ned Greene, and Victor Ostromoukhov for many helpful discussions. This work was supported by an NSF Presidential Faculty Fellow award (CCR- 9553199), an ONR Young Investigator award (N00014-95-1-0728), an NSF Graduate Research Fellowship, and industrial gifts from Microsoft and Pixar. References [1] Howard Alexander. The computer/plotter and the 17 ornamental design types. In Proceedings of SIGGRAPH ’75, pages 160–167. 1975. [2] J. Arvo and D. Kirk. Modeling plants with environment-sensitive automata. In Ausgraph 88 proceedings, pages 27–33. 1988. [3] Richard Beach and Maureen Stone. Graphical style—towards high quality illustrations. In Proceedings of SIGGRAPH ’83, pages 127–135. 1983. [4] Albert Fidelis Butsch. Handbook of Renaissance Ornament: 1290 Designs from Decorated Books. Dover Publications, Inc., New York, 1969. [5] William Caxton. History of Reynard the Foxe. Kelmscott, Hammersmith, England, 1892. [6] Archibald H. Christie. Traditional Methods of Pattern Designing. The Clarendon Press, Oxford, 1929. [7] Theodore A. Cook. The Curves of Life. Constable and Company, London, 1914. Figure 9 Red Chinese vase pattern. [8] Walter Crane. Line and Form. G. Bell & Sons, London, 1902. [9] Joseph D’Addetta. Traditional Japanese Design Motifs. Dover Publications, Inc., New York, 1984. [10] Lewis F. Day. Nature in Ornament. B.T. Batsford, London, 1898. [11] Andrew Glassner. Frieze groups. IEEE Computer Graphics and Applications, 16(3):78–83, May 1996. [12] E.H. Gombrich. The Sense of Order. Phaidon Press Limited, London, 1994. [13] N. Greene. Voxel space automata: Modeling with stocastic growth processes in voxel space. In Proceedings of SIGGRAPH ’89, pages 175–184. 1989. [14] Branko Gr¨unbaum and G. C. Shephard. Tilings and Patterns. W.H. Freeman, New York, 1987. [15] Siu Chi Hsu, I. H. H. Lee, and N. E. Wiseman. Skeletal strokes. In Proceedings of UIST ’93, pages 197–206. 1993. [16] Siu Chi Hsu and Irene H. H. Lee. Drawing and animation using skeletal strokes. In Proceedings of SIGGRAPH ’94, pages 109–118. 1994. [17] Owen Jones. Grammar of Ornament. Day and son, London, 1856. [18] Owen Jones. The Grammar of Chinese Ornament. Portland House, New York, 1987. Figure 10 Flowers and leaves pattern. [19] Sherman E. Lee. The Genius of Japanese Design. Kodansha International, Tokyo, 1981. [20] Radom´ır Mˇech and Przemyslaw Prusinkiewicz. Visual models of plants interacting with their environment. In Proceedings of SIGGRAPH ’96, pages 397–410. 1996. [21] Franz S. Meyer. Handbook of Ornament. Dover Publications, New York, 1957. [22] William Morris. A Book of verse. Kelmscott, Hammersmith, England, 1870. [23] William Morris. Ideal Book: Essays and Lectures on the Arts of the Book. University of California Press, Berkeley, 1982. [24] William Morris and A.J. Wyatt. The Tale of Beowulf. Kelmscott Press, Hammersmith, England, 1895. [25] K. Prakash. Paisleys and Other Textile Designs from India. Dover, New York, 1994. [26] Przemyslaw Prusinkiewicz, Mark James, and Radom´ır Mˇech. Synthetic topiary. In Proceedings of SIGGRAPH ’94, pages 351–358. 1994. [27] Przemyslaw Prusinkiewicz and Aristid Lindenmayer. The Algorithmic Beauty of Plants. Springer-Verlag, New York, 1990. Figure 11 Willow leaf pattern. [28] Przemyslaw Prusinkiewicz, Aristid Lindenmayer, and James Hanan. Developmental models of herbaceous plants for computer imagery purposes. In Proceedings of SIGGRAPH ’88, pages 141–150. 1988. [29] Auguste Racinet. Polychromatic Ornament. Firmin Didot freres, fils & cie, Paris, 1873. [30] A. Rosenfeld and A. C. Kak. Digital Picture Processing. Academic Press, New York, 1976. [31] Henry Shaw. The Encylopedia of Ornament. J. Grant, Edinburgh, 1898. [32] Gift Siromoney and Rani Siromoney. Rosenfeld’s cycle grammars and kolam. In Graph-Grammars and Their Application to Computer Science, pages 564–579. Springer-Verlag, Berlin, 1986. [33] Alvy Ray Smith. Plants, fractals, and formal languages. In Proceedings of SIGGRAPH ’84, pages 1–10. 1984. [34] M.P. Verneuil. Floral Patterns. Dover, New York, 1981. [35] Otto von Falke. Decorative Silks. W. Helburn, Inc., New York, 1922. [36] James Ward. The Principles of Ornament. Scribner, New York, 1896. Figure 12 Bamboo spirals pattern. A Examples Our first example pattern is a simple cluster of circular dots (Figure 14). The first dot is centered on the seed point, and subsequent dots are placed adjacent to the existing ornament. Dots may be at most 3 units in radius. Table 1 explains the dollar-sign tokens used within the rules in this appendix. %element seed point // the seed element is required %endelement %element dot circle int order; // number each dot in order of placement %endelement %source // declare a global variable int dot_count = 0; // to count the dots placed %endsource Figure 13 All four patterns, elaborated over different shapes. The line width variation in the outer spiral arch has been reversed from that of Figure 12 to give a filigreed effect. %rule seed --> dot { // place a maximum-sized dot on the initial seed $0.set( $, 3.0 ); $$0.order = dot_count++; // prevent the seed from being used again $$.sterile = 1; return SUCCESS; } %endrule %rule dot --> dot { // ignore tiny empty spaces. if ( $goal.radius < 0.5 ) return FAILURE; // determine the radius of the new dot. double r = min( 3.0, $goal.radius ); // place the new dot adjacent to the parent dot. $0.set( $.center.offset( $goal.center - $.center, $.radius + r ), r ); $$0.order = dot_count++; return SUCCESS; } %endrule The $0.set call is the critical line. It places the new child dot by taking the center of the parent dot ($.center), and offsetting it by the sum of the parent and child radii ($.radius + r) in the direction from the center of the parent dot to the center of the goal circle C. Figure 14 shows this pattern applied to three different regions. For this example, we have colored the dots, using the order field, to indicate the order in which they were placed, from oldest (red) to newest (purple). This example illustrates how the empty-circle heuristic first extends the ornament along the skeleton of the region, token meaning $$ the parent element $ proxy 0 of the parent $(k) proxy k of the parent $$j the j’th declared child element $j proxy 0 of the j’th declared child $j(k) proxy k of the j’th child $$var dynamic child element in var $var proxy 0 of a dynamic child $var(k) proxy k of a dynamic child $goal the empty circle C Table 1 Explanation of dollar-sign tokens used in rule bodies. (a) (b) (c) Figure 14 A simple example applied to three different regions. Parts (a) and (b) were seeded near the lower left corner, while part (c) was seeded at the center. then fills in smaller and smaller regions successively. A more complex example involves an arrangement of flowers, leaves, and stems. This rule file has the following declaration sec- tion: (a) (b) (c) (d) (e) (f) (g) Figure 15 Two applications of the second example rule. Part (a) shows the parent flower (bold), and the empty goal circle (dashed). The center of the goal circle lies more than 8 units away, so the rule produces (b) a flower, a stem, and a leaf. When the rule is applied in the situation of part (c), where the goal circle is smaller, only the flower and stem are produced (d). Parts (e)–(g) show the elements of part (d) in a variety of rendering styles. %element seed point // the required seed element type %endelement %element flower circle // flower: a circle proxy int color; // this element type has a user field %endelement %element stem linesegment // stem: a line segment proxy %endelement %element leaf bezier bezier // leaf: two Bezier segment proxies %endelement Here three element types are declared, in addition to the required seed type: flower, which is proxied by a single circle; stem, which is proxied by a line segment; and leaf, proxied by two B´ezier segments. The flower element contains an integer user field called color. This pattern also has only two rules. One rule places a flower on top of the initial seed point, and so is invoked only once. We will omit the code for of this rule. The other rule is more interesting: it places a new flower connected to an existing flower with a new stem segment, and adds a leaf to the stem only if the stem is long enough. Thus, the number of children produced is variable (two or three). The effects of this rule are pictured in Figure 15. Here is the preamble to the rule, which creates a set of elements whose relationships are depicted in Figure 16: %rule flower --> stem flower * x leaf The last line of the preamble tells the preprocessor that the variable x within the rule body will point to an element of type leaf. This declaration is necessary so that when the preprocessor sees a dollarsign construction involving the variable x, it knows the type of x and can insert appropriate typecasts. Here is the remainder of the rule: $$ $ flower sterile children color sterile children leaf $$0 $0 $$1 $1 $x $$x $x(0) $x(1) parent children circle center radius bezier c[ ] bezier c[ ] flower sterile children color circle center radius sterile children stem linesegment p0 p1 Figure 16 Data structures and dollar-sign tokens for the rule in the second example. { Direction to_goal = $goal.center - $.center; double distance; // determine how far away to place the child flower. // ˜ on the difference between two points gives // the distance between them. distance = ˜($goal.center - $.center); if ( distance > 10.0 ) distance = 10.0; // place the flower centered "distance" units away // in the direction of the goal, with a radius of 3. $1.set( $.center.offset( to_goal, distance ), 3.0 ); // if the new flower intersects any // already-placed element, cancel this rule. if ( intersection( $$1 ) ) return FAILURE; // the stem extends from the center of the parent // flower to the center of the child flower. $0.set( $.center, $1.center ); // if the new flower was placed far enough away // add a leaf as well. if ( distance > 8.0 ) { leaf *x = new leaf; // the base of the leaf is the stem midpoint. Point leaf_base = ( $1.center - $.center ) / 2; // place the leaf at a right angle to the stem, // and make it 3 units long. Direction leaf_dir = to_goal + M_PI/2; Point leaf_tip = leaf_base.offset(leaf_dir, 3.0); // a leaf is proxied by two Bezier segments. // each is placed giving position and tangent // direction and magnitude. $x(0).set( leaf_base, leaf_dir+M_PI/4, 0.6, leaf_tip, leaf_dir, 0.4 ); $x(1).set( leaf_base, leaf_dir-M_PI/4, 0.6, leaf_tip, leaf_dir, 0.4 ); // add the newly created leaf to the // child set of this rule. new_child( $$x ); } // commit the set of children to the design. return SUCCESS; } %endrule Figure 17 Results of applying different skeletal strokes to a single design.